debugging the BSP

[dosdemo] / src / bsptree.c

diff --git a/src/bsptree.c b/src/bsptree.c
index 6ad4046..30f67ef 100644 (file)
--- a/src/bsptree.c
+++ b/src/bsptree.c
@@ -18,6 +18,7 @@ static void free_tree(struct bspnode *n);
 
 static struct bspnode *new_node(struct g3d_vertex *v, int vnum);
 static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, int vnum);
+static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir);
 
 static void save_bsp_tree(struct bspnode *n, FILE *fp);
 static struct bspnode *load_bsp_tree(FILE *fp);
@@ -92,7 +93,7 @@ int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum)
        return 0;
 }
 
-void bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
+int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
 {
        int i, j, nfaces;
        struct g3d_vertex v[4];
@@ -109,12 +110,20 @@ void bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
                                v[j] = *vptr++;
                        }
                }
-               bsp_add_poly(bsp, v, m->prim);
+               if(bsp_add_poly(bsp, v, m->prim) == -1) {
+                       return -1;
+               }
        }
+       return 0;
 }
 
 void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z)
 {
+       vec3_t vdir;
+       vdir.x = view_x;
+       vdir.y = view_y;
+       vdir.z = view_z;
+       draw_bsp_tree(bsp->root, &vdir);
 }
 
 static int count_nodes(struct bspnode *n)
@@ -169,53 +178,85 @@ static struct bspnode *new_node(struct g3d_vertex *v, int vnum)
 static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, int vnum)
 {
        struct bspnode *nres;
-       int clipres, clipped_vnum;
-       struct g3d_vertex *clipped;
+       int clipres, clipres_neg, clipped_vnum, clipped_neg_vnum;
+       struct g3d_vertex *clipped, *clipped_neg;
        struct cplane negplane;
 
+       assert(vnum > 0);
+
        if(!n) {
                return new_node(v, vnum);
        }
 
-       clipped = alloca((vnum + 1) * sizeof *clipped);
+       negplane.x = n->plane.x;
+       negplane.y = n->plane.y;
+       negplane.z = n->plane.z;
+       negplane.nx = -n->plane.nx;
+       negplane.ny = -n->plane.ny;
+       negplane.nz = -n->plane.nz;
+
+       clipped = alloca((vnum * 2) * sizeof *clipped);
+       clipped_neg = alloca((vnum * 2) * sizeof *clipped_neg);
 
        clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &n->plane);
-       if(clipres > 0) {       /* polygon completely in the positive subspace */
+       clipres_neg = clip_poly(clipped_neg, &clipped_neg_vnum, v, vnum, &negplane);
+
+       /* detect edge cases where due to floating point imprecision, clipping
+        * by the positive plane clips the polygon, but clipping by the negative
+        * plane doesn't. If that happens, consider the polygon completely on
+        * the side indicated by -clipres_neg
+        */
+       if(clipres == 0 && clipres_neg != 0) {
+               clipres = -clipres_neg;
+       }
+
+       if(clipres > 0) {
+               /* polygon completely in the positive subspace */
                if(!(nres = add_poly_tree(n->front, v, vnum))) {
                        return 0;
                }
                n->front = nres;
-       }
-       if(clipres < 0) {       /* polygon completely in the negative subspace */
+
+       } else if(clipres < 0) {
+               /* polygon completely in the negative subspace */
                if(!(nres = add_poly_tree(n->back, v, vnum))) {
                        return 0;
                }
                n->back = nres;
-       }
-
-       /* polygon is straddling the plane */
-       if(!(nres = add_poly_tree(n->front, clipped, clipped_vnum))) {
-               return 0;
-       }
-       n->front = nres;
 
-       negplane.x = n->plane.x;
-       negplane.y = n->plane.y;
-       negplane.z = n->plane.z;
-       negplane.nx = -n->plane.nx;
-       negplane.ny = -n->plane.ny;
-       negplane.nz = -n->plane.nz;
-
-       clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &negplane);
-       assert(clipres == 0);
+       } else {
+               /* polygon is straddling the plane */
+               if(!(nres = add_poly_tree(n->front, clipped, clipped_vnum))) {
+                       return 0;
+               }
+               n->front = nres;
 
-       if(!(nres = add_poly_tree(n->back, clipped, clipped_vnum))) {
-               return 0;
+               if(!(nres = add_poly_tree(n->back, clipped_neg, clipped_neg_vnum))) {
+                       return 0;
+               }
+               n->back = nres;
        }
-       n->back = nres;
        return n;
 }
 
+static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir)
+{
+       float dot;
+
+       if(!n) return;
+
+       dot = vdir->x * n->plane.nx + vdir->y * n->plane.ny + vdir->z * n->plane.nz;
+       if(dot >= 0.0f) {
+               draw_bsp_tree(n->front, vdir);
+               g3d_draw_indexed(n->vcount, n->verts, n->vcount, 0, 0);
+               draw_bsp_tree(n->back, vdir);
+       } else {
+               draw_bsp_tree(n->back, vdir);
+               g3d_draw_indexed(n->vcount, n->verts, n->vcount, 0, 0);
+               draw_bsp_tree(n->front, vdir);
+       }
+}
+
 static void save_bsp_tree(struct bspnode *n, FILE *fp)
 {
        /* TODO */