X-Git-Url: http://git.mutantstargoat.com/user/nuclear/?p=dosdemo;a=blobdiff_plain;f=src%2Fbsptree.c;h=334e53073c66f7ce10a7f7ee0019176eb71931da;hp=6ad4046904aaaba688974581d57e9a1900ae5b4e;hb=e5393153629cb39ea6af0ca4a35370442127c5c2;hpb=b546d1a5227ee3a263447e279434842d230f700a

diff --git a/src/bsptree.c b/src/bsptree.c
index 6ad4046..334e530 100644
--- 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,51 +178,101 @@ 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;
+	} 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_neg, clipped_neg_vnum))) {
+			return 0;
+		}
+		n->back = nres;
 	}
-	n->front = nres;
+	return n;
+}
 
-	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;
+void debug_draw_poly(struct g3d_vertex *varr, int vcount)
+{
+	int i, nfaces = vcount - 2;
+	int vbuf_size = nfaces * 3;
+	struct g3d_vertex *vbuf = alloca(vbuf_size * sizeof *vbuf);
+	struct g3d_vertex *vptr = varr + 1;
 
-	clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &negplane);
-	assert(clipres == 0);
+	for(i=0; i<nfaces; i++) {
+		vbuf[i * 3] = varr[0];
+		vbuf[i * 3 + 1] = *vptr++;
+		vbuf[i * 3 + 2] = *vptr;
+	}
 
-	if(!(nres = add_poly_tree(n->back, clipped, clipped_vnum))) {
-		return 0;
+	g3d_draw_indexed(G3D_TRIANGLES, vbuf, vbuf_size, 0, 0);
+}
+
+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);
+		debug_draw_poly(n->verts, n->vcount);
+		draw_bsp_tree(n->back, vdir);
+	} else {
+		draw_bsp_tree(n->back, vdir);
+		//g3d_draw_indexed(n->vcount, n->verts, n->vcount, 0, 0);
+		debug_draw_poly(n->verts, n->vcount);
+		draw_bsp_tree(n->front, vdir);
 	}
-	n->back = nres;
-	return n;
 }
 
 static void save_bsp_tree(struct bspnode *n, FILE *fp)