X-Git-Url: http://git.mutantstargoat.com/user/nuclear/?p=dosdemo;a=blobdiff_plain;f=src%2Fbsptree.c;h=30f67eff08fb3d87eca861a91a10bb1ab60fdddd;hp=dc8f2af6b2b2cacf998d24a3d520bd906167c35d;hb=45f6f46fe758d15aafccdb69ae837fc7d84ee466;hpb=32ff3cf2d7d7a5ae82f5ca400b320c67e6984ad6

diff --git a/src/bsptree.c b/src/bsptree.c
index dc8f2af..30f67ef 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);
@@ -118,6 +119,11 @@ int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
 
 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)
@@ -172,17 +178,38 @@ 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);
+	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))) {
@@ -204,17 +231,7 @@ static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, in
 		}
 		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);*/
-
-		if(!(nres = add_poly_tree(n->back, clipped, clipped_vnum))) {
+		if(!(nres = add_poly_tree(n->back, clipped_neg, clipped_neg_vnum))) {
 			return 0;
 		}
 		n->back = nres;
@@ -222,6 +239,24 @@ static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, in
 	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 */