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;
252 #pragma omp parallel for reduction(+:num_splits)
254 for(j=0; j<num_polys; j++) {
257 if(check_clip_poly(polyarr[j].verts, polyarr[j].vcount, plane) == 0) {
262 if(num_splits < best_splits) {
263 best_splits = num_splits;
268 /*printf("choose_poly(..., %d) -> %d splits\n", num_polys, best_splits);*/
273 static struct bspnode *build_tree(struct bsppoly *polyarr, int num_polys)
276 struct bsppoly *sp, *tmp;
277 struct bsppoly *front_polys, *back_polys;
278 struct bspnode *node;
280 struct bspnode *nres;
281 int clipres, clipres_neg, clipped_vnum, clipped_neg_vnum, max_clipped_vnum = 0;
282 struct g3d_vertex *v, *clipped = 0, *clipped_neg = 0;
283 struct cplane negplane;
285 if((pidx = choose_poly(polyarr, num_polys)) == -1) {
290 negplane.x = sp->plane.x;
291 negplane.y = sp->plane.y;
292 negplane.z = sp->plane.z;
293 negplane.nx = -sp->plane.nx;
294 negplane.ny = -sp->plane.ny;
295 negplane.nz = -sp->plane.nz;
297 if(!(front_polys = dynarr_alloc(0, sizeof *front_polys)) ||
298 !(back_polys = dynarr_alloc(0, sizeof *back_polys))) {
299 fprintf(stderr, "build_tree: failed to allocate front/back polygon arrays\n");
300 dynarr_free(front_polys);
304 for(i=0; i<num_polys; i++) {
305 if(i == pidx) continue;
307 vnum = polyarr[i].vcount;
309 if(vnum * 2 > max_clipped_vnum) {
310 /* resize clipped polygon buffers if necessary */
311 max_clipped_vnum = vnum * 2;
312 if(!(v = realloc(clipped, max_clipped_vnum * sizeof *clipped))) {
313 fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n");
317 if(!(v = realloc(clipped_neg, max_clipped_vnum * sizeof *clipped))) {
318 fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n");
324 v = polyarr[i].verts;
326 clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &sp->plane);
327 clipres_neg = clip_poly(clipped_neg, &clipped_neg_vnum, v, vnum, &negplane);
329 /* detect edge cases where due to floating point imprecision, clipping
330 * by the positive plane clips the polygon, but clipping by the negative
331 * plane doesn't. If that happens, consider the polygon completely on
332 * the side indicated by -clipres_neg
334 if(clipres == 0 && clipres_neg != 0) {
335 clipres = -clipres_neg;
339 /* polygon completely in the positive subspace */
340 if(!(tmp = dynarr_push(front_polys, polyarr + i))) {
341 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
346 } else if(clipres < 0) {
347 /* polygon completely in the negative subspace */
348 if(!(tmp = dynarr_push(back_polys, polyarr + i))) {
349 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
355 /* polygon is straddling the plane */
357 poly.plane = polyarr[i].plane;
359 if(init_poly_noplane(&poly, clipped, clipped_vnum) == -1) {
362 if(!(tmp = dynarr_push(front_polys, &poly))) {
363 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
369 if(init_poly_noplane(&poly, clipped_neg, clipped_neg_vnum) == -1) {
372 if(!(tmp = dynarr_push(back_polys, &poly))) {
373 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
379 /* we allocated new sub-polygons, so we need to free the original vertex array */
380 free(polyarr[i].verts);
384 if(!(node = malloc(sizeof *node))) {
385 fprintf(stderr, "build_tree: failed to allocate new BSP node\n");
389 node->front = node->back = 0;
391 if(dynarr_size(front_polys)) {
392 if(!(node->front = build_tree(front_polys, dynarr_size(front_polys)))) {
396 if(dynarr_size(back_polys)) {
397 if(!(node->back = build_tree(back_polys, dynarr_size(back_polys)))) {
405 /* we no longer need the original polygon array */
406 dynarr_free(polyarr);
414 for(i=0; i<dynarr_size(front_polys); i++) {
415 free(front_polys[i].verts);
417 dynarr_free(front_polys);
419 for(i=0; i<dynarr_size(back_polys); i++) {
420 free(back_polys[i].verts);
422 dynarr_free(back_polys);
430 static void debug_draw_poly(struct g3d_vertex *varr, int vcount)
432 int i, nfaces = vcount - 2;
433 int vbuf_size = nfaces * 3;
434 struct g3d_vertex *vbuf = alloca(vbuf_size * sizeof *vbuf);
435 struct g3d_vertex *vptr = varr + 1;
437 for(i=0; i<nfaces; i++) {
438 vbuf[i * 3] = varr[0];
439 vbuf[i * 3 + 1] = *vptr++;
440 vbuf[i * 3 + 2] = *vptr;
443 g3d_draw_indexed(G3D_TRIANGLES, vbuf, vbuf_size, 0, 0);
447 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir)
456 dot = vdir->x * p->plane.nx + vdir->y * p->plane.ny + vdir->z * p->plane.nz;
458 draw_bsp_tree(n->front, vdir);
460 g3d_draw_indexed(p->vcount, p->verts, p->vcount, 0, 0);
462 debug_draw_poly(p->verts, p->vcount);
464 draw_bsp_tree(n->back, vdir);
466 draw_bsp_tree(n->back, vdir);
468 g3d_draw_indexed(p->vcount, p->verts, p->vcount, 0, 0);
470 debug_draw_poly(p->verts, p->vcount);
472 draw_bsp_tree(n->front, vdir);
476 static void save_bsp_tree(struct bspnode *n, FILE *fp)
481 static struct bspnode *load_bsp_tree(FILE *fp)