6 #if defined(__WATCOMC__) || defined(_MSC_VER) || defined(__DJGPP__)
18 struct bspfile_header {
23 static int count_nodes(struct bspnode *n);
24 static void free_tree(struct bspnode *n);
26 static int init_poly(struct bsppoly *poly, struct g3d_vertex *v, int vnum);
27 static int init_poly_noplane(struct bsppoly *poly, struct g3d_vertex *v, int vnum);
29 static struct bspnode *build_tree(struct bsppoly *polyarr, int num_polys);
31 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir);
33 static void save_bsp_tree(struct bspnode *n, FILE *fp);
34 static struct bspnode *load_bsp_tree(FILE *fp);
36 int init_bsp(struct bsptree *bsp)
43 void destroy_bsp(struct bsptree *bsp)
50 for(i=0; i<dynarr_size(bsp->soup); i++) {
51 free(bsp->soup[i].verts);
53 dynarr_free(bsp->soup);
57 int save_bsp(struct bsptree *bsp, const char *fname)
60 struct bspfile_header hdr;
62 if(!(fp = fopen(fname, "wb"))) {
63 fprintf(stderr, "save_bsp: failed to open %s for writing\n", fname);
67 memcpy(hdr.magic, "MBSP", 4);
68 hdr.num_nodes = count_nodes(bsp->root);
69 fwrite(&hdr, sizeof hdr, 1, fp);
71 save_bsp_tree(bsp->root, fp);
77 int load_bsp(struct bsptree *bsp, const char *fname)
80 struct bspfile_header hdr;
82 if(!(fp = fopen(fname, "rb"))) {
83 fprintf(stderr, "load_bsp: failed to open %s\n", fname);
87 if(fread(&hdr, sizeof hdr, 1, fp) < 1) {
88 fprintf(stderr, "load_bsp: %s: failed to read header\n", fname);
92 if(memcmp(hdr.magic, "MBSP", 4) != 0) {
93 fprintf(stderr, "load_bsp: %s: invalid magic\n", fname);
97 bsp->root = load_bsp_tree(fp);
103 int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum)
105 struct bsppoly poly, *tmp;
107 if(!bsp->soup && !(bsp->soup = dynarr_alloc(0, sizeof *bsp->soup))) {
108 fprintf(stderr, "bsp_add_poly: failed to create polygon soup dynamic array\n");
112 if(init_poly(&poly, v, vnum) == -1) {
116 if(!(tmp = dynarr_push(bsp->soup, &poly))) {
117 fprintf(stderr, "bsp_add_poly: failed to reallocate polygon soup\n");
126 int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
129 struct g3d_vertex v[4];
130 struct g3d_vertex *vptr = m->varr;
131 uint16_t *iptr = m->iarr;
133 nfaces = m->iarr ? m->icount / m->prim : m->vcount / m->prim;
135 for(i=0; i<nfaces; i++) {
136 for(j=0; j<m->prim; j++) {
138 v[j] = m->varr[*iptr++];
143 if(bsp_add_poly(bsp, v, m->prim) == -1) {
150 int bsp_build(struct bsptree *bsp)
153 assert(!dynarr_empty(bsp->soup));
155 free_tree(bsp->root);
157 printf("building BSP tree with %d source polygons ...\n", dynarr_size(bsp->soup));
158 if(!(bsp->root = build_tree(bsp->soup, dynarr_size(bsp->soup)))) {
159 fprintf(stderr, "bsp_build failed\n");
162 printf("done. created a tree with %d nodes\n", count_nodes(bsp->root));
164 /* build_tree has called dynarr_free on bsp->soup */
170 void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z)
179 draw_bsp_tree(bsp->root, &vdir);
182 static int count_nodes(struct bspnode *n)
185 return count_nodes(n->front) + count_nodes(n->back) + 1;
188 static void free_tree(struct bspnode *n)
199 static int init_poly(struct bsppoly *poly, struct g3d_vertex *v, int vnum)
203 if(init_poly_noplane(poly, v, vnum) == -1) {
207 va.x = v[1].x - v[0].x;
208 va.y = v[1].y - v[0].y;
209 va.z = v[1].z - v[0].z;
210 vb.x = v[2].x - v[0].x;
211 vb.y = v[2].y - v[0].y;
212 vb.z = v[2].z - v[0].z;
213 norm = v3_cross(va, vb);
216 poly->plane.x = v[0].x;
217 poly->plane.y = v[0].y;
218 poly->plane.z = v[0].z;
219 poly->plane.nx = norm.x;
220 poly->plane.ny = norm.y;
221 poly->plane.nz = norm.z;
225 static int init_poly_noplane(struct bsppoly *poly, struct g3d_vertex *v, int vnum)
227 if(!(poly->verts = malloc(vnum * sizeof *poly->verts))) {
228 fprintf(stderr, "failed to allocate BSP polygon\n");
232 memcpy(poly->verts, v, vnum * sizeof *poly->verts);
236 static int choose_poly(struct bsppoly *polyarr, int num_polys)
238 int i, j, best, best_splits;
245 best_splits = INT_MAX;
247 for(i=0; i<num_polys; i++) {
248 struct cplane *plane = &polyarr[i].plane;
251 #pragma omp parallel for reduction(+:num_splits)
252 for(j=0; j<num_polys; j++) {
255 if(check_clip_poly(polyarr[j].verts, polyarr[j].vcount, plane) == 0) {
260 if(num_splits < best_splits) {
261 best_splits = num_splits;
266 /*printf("choose_poly(..., %d) -> %d splits\n", num_polys, best_splits);*/
271 static struct bspnode *build_tree(struct bsppoly *polyarr, int num_polys)
274 struct bsppoly *sp, *tmp;
275 struct bsppoly *front_polys, *back_polys;
276 struct bspnode *node;
278 struct bspnode *nres;
279 int clipres, clipres_neg, clipped_vnum, clipped_neg_vnum, max_clipped_vnum = 0;
280 struct g3d_vertex *v, *clipped = 0, *clipped_neg = 0;
281 struct cplane negplane;
283 if((pidx = choose_poly(polyarr, num_polys)) == -1) {
288 negplane.x = sp->plane.x;
289 negplane.y = sp->plane.y;
290 negplane.z = sp->plane.z;
291 negplane.nx = -sp->plane.nx;
292 negplane.ny = -sp->plane.ny;
293 negplane.nz = -sp->plane.nz;
295 if(!(front_polys = dynarr_alloc(0, sizeof *front_polys)) ||
296 !(back_polys = dynarr_alloc(0, sizeof *back_polys))) {
297 fprintf(stderr, "build_tree: failed to allocate front/back polygon arrays\n");
298 dynarr_free(front_polys);
302 for(i=0; i<num_polys; i++) {
303 if(i == pidx) continue;
305 vnum = polyarr[i].vcount;
307 if(vnum * 2 > max_clipped_vnum) {
308 /* resize clipped polygon buffers if necessary */
309 max_clipped_vnum = vnum * 2;
310 if(!(v = realloc(clipped, max_clipped_vnum * sizeof *clipped))) {
311 fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n");
315 if(!(v = realloc(clipped_neg, max_clipped_vnum * sizeof *clipped))) {
316 fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n");
322 v = polyarr[i].verts;
324 clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &sp->plane);
325 clipres_neg = clip_poly(clipped_neg, &clipped_neg_vnum, v, vnum, &negplane);
327 /* detect edge cases where due to floating point imprecision, clipping
328 * by the positive plane clips the polygon, but clipping by the negative
329 * plane doesn't. If that happens, consider the polygon completely on
330 * the side indicated by -clipres_neg
332 if(clipres == 0 && clipres_neg != 0) {
333 clipres = -clipres_neg;
337 /* polygon completely in the positive subspace */
338 if(!(tmp = dynarr_push(front_polys, polyarr + i))) {
339 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
344 } else if(clipres < 0) {
345 /* polygon completely in the negative subspace */
346 if(!(tmp = dynarr_push(back_polys, polyarr + i))) {
347 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
353 /* polygon is straddling the plane */
355 poly.plane = polyarr[i].plane;
357 if(init_poly_noplane(&poly, clipped, clipped_vnum) == -1) {
360 if(!(tmp = dynarr_push(front_polys, &poly))) {
361 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
367 if(init_poly_noplane(&poly, clipped_neg, clipped_neg_vnum) == -1) {
370 if(!(tmp = dynarr_push(back_polys, &poly))) {
371 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
377 /* we allocated new sub-polygons, so we need to free the original vertex array */
378 free(polyarr[i].verts);
382 if(!(node = malloc(sizeof *node))) {
383 fprintf(stderr, "build_tree: failed to allocate new BSP node\n");
387 node->front = node->back = 0;
389 if(dynarr_size(front_polys)) {
390 if(!(node->front = build_tree(front_polys, dynarr_size(front_polys)))) {
394 if(dynarr_size(back_polys)) {
395 if(!(node->back = build_tree(back_polys, dynarr_size(back_polys)))) {
403 /* we no longer need the original polygon array */
404 dynarr_free(polyarr);
412 for(i=0; i<dynarr_size(front_polys); i++) {
413 free(front_polys[i].verts);
415 dynarr_free(front_polys);
417 for(i=0; i<dynarr_size(back_polys); i++) {
418 free(back_polys[i].verts);
420 dynarr_free(back_polys);
428 static void debug_draw_poly(struct g3d_vertex *varr, int vcount)
430 int i, nfaces = vcount - 2;
431 int vbuf_size = nfaces * 3;
432 struct g3d_vertex *vbuf = alloca(vbuf_size * sizeof *vbuf);
433 struct g3d_vertex *vptr = varr + 1;
435 for(i=0; i<nfaces; i++) {
436 vbuf[i * 3] = varr[0];
437 vbuf[i * 3 + 1] = *vptr++;
438 vbuf[i * 3 + 2] = *vptr;
441 g3d_draw_indexed(G3D_TRIANGLES, vbuf, vbuf_size, 0, 0);
445 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir)
454 dot = vdir->x * p->plane.nx + vdir->y * p->plane.ny + vdir->z * p->plane.nz;
456 draw_bsp_tree(n->front, vdir);
458 g3d_draw_indexed(p->vcount, p->verts, p->vcount, 0, 0);
460 debug_draw_poly(p->verts, p->vcount);
462 draw_bsp_tree(n->back, vdir);
464 draw_bsp_tree(n->back, vdir);
466 g3d_draw_indexed(p->vcount, p->verts, p->vcount, 0, 0);
468 debug_draw_poly(p->verts, p->vcount);
470 draw_bsp_tree(n->front, vdir);
474 static void save_bsp_tree(struct bspnode *n, FILE *fp)
479 static struct bspnode *load_bsp_tree(FILE *fp)