#include <stdlib.h>
#include <string.h>
#include <assert.h>
+#if defined(__WATCOMC__) || defined(_MSC_VER) || defined(__DJGPP__)
+#include <malloc.h>
+#else
+#include <alloca.h>
+#endif
#include "bsptree.h"
#include "dynarr.h"
#include "inttypes.h"
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);
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];
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)
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;
+#undef DRAW_NGONS
- clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &negplane);
- assert(clipres == 0);
+#ifndef DRAW_NGONS
+static 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;
- if(!(nres = add_poly_tree(n->back, clipped, clipped_vnum))) {
- return 0;
+ for(i=0; i<nfaces; i++) {
+ vbuf[i * 3] = varr[0];
+ vbuf[i * 3 + 1] = *vptr++;
+ vbuf[i * 3 + 2] = *vptr;
+ }
+
+ g3d_draw_indexed(G3D_TRIANGLES, vbuf, vbuf_size, 0, 0);
+}
+#endif
+
+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);
+#ifdef DRAW_NGONS
+ g3d_draw_indexed(n->vcount, n->verts, n->vcount, 0, 0);
+#else
+ debug_draw_poly(n->verts, n->vcount);
+#endif
+ draw_bsp_tree(n->back, vdir);
+ } else {
+ draw_bsp_tree(n->back, vdir);
+#ifdef DRAW_NGONS
+ g3d_draw_indexed(n->vcount, n->verts, n->vcount, 0, 0);
+#else
+ debug_draw_poly(n->verts, n->vcount);
+#endif
+ draw_bsp_tree(n->front, vdir);
}
- n->back = nres;
- return n;
}
static void save_bsp_tree(struct bspnode *n, FILE *fp)