6 #if defined(__WATCOMC__) || defined(_MSC_VER) || defined(__DJGPP__)
22 struct bspfile_header {
27 static int count_nodes(struct bspnode *n);
28 static void free_tree(struct bspnode *n);
30 static int init_poly(struct bsppoly *poly, struct g3d_vertex *v, int vnum);
31 static int init_poly_noplane(struct bsppoly *poly, struct g3d_vertex *v, int vnum);
33 static struct bspnode *build_tree(struct bsppoly *polyarr, int num_polys);
35 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir);
37 static void save_bsp_tree(struct bspnode *n, FILE *fp);
38 static struct bspnode *load_bsp_tree(FILE *fp);
40 int init_bsp(struct bsptree *bsp)
47 void destroy_bsp(struct bsptree *bsp)
54 for(i=0; i<dynarr_size(bsp->soup); i++) {
55 free(bsp->soup[i].verts);
57 dynarr_free(bsp->soup);
61 int save_bsp(struct bsptree *bsp, const char *fname)
64 struct bspfile_header hdr;
66 if(!(fp = fopen(fname, "wb"))) {
67 fprintf(stderr, "save_bsp: failed to open %s for writing\n", fname);
71 memcpy(hdr.magic, "MBSP", 4);
72 hdr.num_nodes = count_nodes(bsp->root);
73 fwrite(&hdr, sizeof hdr, 1, fp);
75 save_bsp_tree(bsp->root, fp);
81 int load_bsp(struct bsptree *bsp, const char *fname)
84 struct bspfile_header hdr;
86 if(!(fp = fopen(fname, "rb"))) {
87 fprintf(stderr, "load_bsp: failed to open %s\n", fname);
91 if(fread(&hdr, sizeof hdr, 1, fp) < 1) {
92 fprintf(stderr, "load_bsp: %s: failed to read header\n", fname);
96 if(memcmp(hdr.magic, "MBSP", 4) != 0) {
97 fprintf(stderr, "load_bsp: %s: invalid magic\n", fname);
101 bsp->root = load_bsp_tree(fp);
107 int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum)
109 struct bsppoly poly, *tmp;
111 if(!bsp->soup && !(bsp->soup = dynarr_alloc(0, sizeof *bsp->soup))) {
112 fprintf(stderr, "bsp_add_poly: failed to create polygon soup dynamic array\n");
116 if(init_poly(&poly, v, vnum) == -1) {
120 if(!(tmp = dynarr_push(bsp->soup, &poly))) {
121 fprintf(stderr, "bsp_add_poly: failed to reallocate polygon soup\n");
130 int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
133 struct g3d_vertex v[4];
134 struct g3d_vertex *vptr = m->varr;
135 uint16_t *iptr = m->iarr;
137 nfaces = m->iarr ? m->icount / m->prim : m->vcount / m->prim;
139 for(i=0; i<nfaces; i++) {
140 for(j=0; j<m->prim; j++) {
142 v[j] = m->varr[*iptr++];
147 if(bsp_add_poly(bsp, v, m->prim) == -1) {
154 int bsp_build(struct bsptree *bsp)
157 assert(!dynarr_empty(bsp->soup));
159 free_tree(bsp->root);
161 printf("building BSP tree with %d source polygons ...\n", dynarr_size(bsp->soup));
162 if(!(bsp->root = build_tree(bsp->soup, dynarr_size(bsp->soup)))) {
163 fprintf(stderr, "bsp_build failed\n");
166 printf("done. created a tree with %d nodes\n", count_nodes(bsp->root));
168 /* build_tree has called dynarr_free on bsp->soup */
174 void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z)
183 draw_bsp_tree(bsp->root, &vdir);
186 static int count_nodes(struct bspnode *n)
189 return count_nodes(n->front) + count_nodes(n->back) + 1;
192 static void free_tree(struct bspnode *n)
203 static int init_poly(struct bsppoly *poly, struct g3d_vertex *v, int vnum)
207 if(init_poly_noplane(poly, v, vnum) == -1) {
211 va.x = v[1].x - v[0].x;
212 va.y = v[1].y - v[0].y;
213 va.z = v[1].z - v[0].z;
214 vb.x = v[2].x - v[0].x;
215 vb.y = v[2].y - v[0].y;
216 vb.z = v[2].z - v[0].z;
217 norm = v3_cross(va, vb);
220 poly->plane.x = v[0].x;
221 poly->plane.y = v[0].y;
222 poly->plane.z = v[0].z;
223 poly->plane.nx = norm.x;
224 poly->plane.ny = norm.y;
225 poly->plane.nz = norm.z;
229 static int init_poly_noplane(struct bsppoly *poly, struct g3d_vertex *v, int vnum)
231 if(!(poly->verts = malloc(vnum * sizeof *poly->verts))) {
232 fprintf(stderr, "failed to allocate BSP polygon\n");
236 memcpy(poly->verts, v, vnum * sizeof *poly->verts);
240 static int choose_poly(struct bsppoly *polyarr, int num_polys)
242 int i, j, best, best_splits;
249 best_splits = INT_MAX;
251 for(i=0; i<num_polys; i++) {
252 struct cplane *plane = &polyarr[i].plane;
256 #pragma omp parallel for reduction(+:num_splits)
258 for(j=0; j<num_polys; j++) {
261 if(check_clip_poly(polyarr[j].verts, polyarr[j].vcount, plane) == 0) {
266 if(num_splits < best_splits) {
267 best_splits = num_splits;
272 /*printf("choose_poly(..., %d) -> %d splits\n", num_polys, best_splits);*/
277 static struct bspnode *build_tree(struct bsppoly *polyarr, int num_polys)
280 struct bsppoly *sp, *tmp;
281 struct bsppoly *front_polys, *back_polys;
282 struct bspnode *node;
284 struct bspnode *nres;
285 int clipres, clipres_neg, clipped_vnum, clipped_neg_vnum, max_clipped_vnum = 0;
286 struct g3d_vertex *v, *clipped = 0, *clipped_neg = 0;
287 struct cplane negplane;
289 if((pidx = choose_poly(polyarr, num_polys)) == -1) {
294 negplane.x = sp->plane.x;
295 negplane.y = sp->plane.y;
296 negplane.z = sp->plane.z;
297 negplane.nx = -sp->plane.nx;
298 negplane.ny = -sp->plane.ny;
299 negplane.nz = -sp->plane.nz;
301 if(!(front_polys = dynarr_alloc(0, sizeof *front_polys)) ||
302 !(back_polys = dynarr_alloc(0, sizeof *back_polys))) {
303 fprintf(stderr, "build_tree: failed to allocate front/back polygon arrays\n");
304 dynarr_free(front_polys);
308 for(i=0; i<num_polys; i++) {
309 if(i == pidx) continue;
311 vnum = polyarr[i].vcount;
313 if(vnum * 2 > max_clipped_vnum) {
314 /* resize clipped polygon buffers if necessary */
315 max_clipped_vnum = vnum * 2;
316 if(!(v = realloc(clipped, max_clipped_vnum * sizeof *clipped))) {
317 fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n");
321 if(!(v = realloc(clipped_neg, max_clipped_vnum * sizeof *clipped))) {
322 fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n");
328 v = polyarr[i].verts;
330 clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &sp->plane);
331 clipres_neg = clip_poly(clipped_neg, &clipped_neg_vnum, v, vnum, &negplane);
333 /* detect edge cases where due to floating point imprecision, clipping
334 * by the positive plane clips the polygon, but clipping by the negative
335 * plane doesn't. If that happens, consider the polygon completely on
336 * the side indicated by -clipres_neg
338 if(clipres == 0 && clipres_neg != 0) {
339 clipres = -clipres_neg;
343 /* polygon completely in the positive subspace */
344 if(!(tmp = dynarr_push(front_polys, polyarr + i))) {
345 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
350 } else if(clipres < 0) {
351 /* polygon completely in the negative subspace */
352 if(!(tmp = dynarr_push(back_polys, polyarr + i))) {
353 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
359 /* polygon is straddling the plane */
361 poly.plane = polyarr[i].plane;
363 if(init_poly_noplane(&poly, clipped, clipped_vnum) == -1) {
366 if(!(tmp = dynarr_push(front_polys, &poly))) {
367 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
373 if(init_poly_noplane(&poly, clipped_neg, clipped_neg_vnum) == -1) {
376 if(!(tmp = dynarr_push(back_polys, &poly))) {
377 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
383 /* we allocated new sub-polygons, so we need to free the original vertex array */
384 free(polyarr[i].verts);
388 if(!(node = malloc(sizeof *node))) {
389 fprintf(stderr, "build_tree: failed to allocate new BSP node\n");
393 node->front = node->back = 0;
395 if(dynarr_size(front_polys)) {
396 if(!(node->front = build_tree(front_polys, dynarr_size(front_polys)))) {
400 if(dynarr_size(back_polys)) {
401 if(!(node->back = build_tree(back_polys, dynarr_size(back_polys)))) {
409 /* we no longer need the original polygon array */
410 dynarr_free(polyarr);
418 for(i=0; i<dynarr_size(front_polys); i++) {
419 free(front_polys[i].verts);
421 dynarr_free(front_polys);
423 for(i=0; i<dynarr_size(back_polys); i++) {
424 free(back_polys[i].verts);
426 dynarr_free(back_polys);
434 static void debug_draw_poly(struct g3d_vertex *varr, int vcount)
436 int i, nfaces = vcount - 2;
437 int vbuf_size = nfaces * 3;
438 struct g3d_vertex *vbuf = alloca(vbuf_size * sizeof *vbuf);
439 struct g3d_vertex *vptr = varr + 1;
441 for(i=0; i<nfaces; i++) {
442 vbuf[i * 3] = varr[0];
443 vbuf[i * 3 + 1] = *vptr++;
444 vbuf[i * 3 + 2] = *vptr;
447 g3d_draw_indexed(G3D_TRIANGLES, vbuf, vbuf_size, 0, 0);
451 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir)
460 dot = vdir->x * p->plane.nx + vdir->y * p->plane.ny + vdir->z * p->plane.nz;
462 draw_bsp_tree(n->front, vdir);
464 g3d_draw_indexed(p->vcount, p->verts, p->vcount, 0, 0);
466 debug_draw_poly(p->verts, p->vcount);
468 draw_bsp_tree(n->back, vdir);
470 draw_bsp_tree(n->back, vdir);
472 g3d_draw_indexed(p->vcount, p->verts, p->vcount, 0, 0);
474 debug_draw_poly(p->verts, p->vcount);
476 draw_bsp_tree(n->front, vdir);
480 static void save_bsp_tree(struct bspnode *n, FILE *fp)
485 static struct bspnode *load_bsp_tree(FILE *fp)