From 00a81988c5c6c91997f2f9346ac94858622490bd Mon Sep 17 00:00:00 2001 From: John Tsiombikas Date: Thu, 30 Aug 2018 09:01:30 +0300 Subject: [PATCH] backported fixes from rtxon: BSP tree construction and mouse handling --- src/bsptree.c | 330 +++++++++++++++++++++++++++++++++++++++++++------------- src/bsptree.h | 9 +- src/demo.c | 4 +- src/demo.h | 6 ++ src/sdl/main.c | 21 +++- 5 files changed, 289 insertions(+), 81 deletions(-) diff --git a/src/bsptree.c b/src/bsptree.c index cd8e356..7783e25 100644 --- a/src/bsptree.c +++ b/src/bsptree.c @@ -1,6 +1,7 @@ #include #include #include +#include #include #if defined(__WATCOMC__) || defined(_MSC_VER) || defined(__DJGPP__) #include @@ -22,8 +23,11 @@ struct bspfile_header { static int count_nodes(struct bspnode *n); 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 int init_poly(struct bsppoly *poly, struct g3d_vertex *v, int vnum); +static int init_poly_noplane(struct bsppoly *poly, struct g3d_vertex *v, int vnum); + +static struct bspnode *build_tree(struct bsppoly *polyarr, int num_polys); + static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir); static void save_bsp_tree(struct bspnode *n, FILE *fp); @@ -32,12 +36,22 @@ static struct bspnode *load_bsp_tree(FILE *fp); int init_bsp(struct bsptree *bsp) { bsp->root = 0; + bsp->soup = 0; return 0; } void destroy_bsp(struct bsptree *bsp) { + int i; + free_tree(bsp->root); + + if(bsp->soup) { + for(i=0; isoup); i++) { + free(bsp->soup[i].verts); + } + dynarr_free(bsp->soup); + } } int save_bsp(struct bsptree *bsp, const char *fname) @@ -88,14 +102,24 @@ int load_bsp(struct bsptree *bsp, const char *fname) int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum) { - struct bspnode *n; - assert(vnum >= 3); + struct bsppoly poly, *tmp; + + if(!bsp->soup && !(bsp->soup = dynarr_alloc(0, sizeof *bsp->soup))) { + fprintf(stderr, "bsp_add_poly: failed to create polygon soup dynamic array\n"); + return -1; + } + + if(init_poly(&poly, v, vnum) == -1) { + return -1; + } - if(!(n = add_poly_tree(bsp->root, v, vnum))) { - fprintf(stderr, "bsp_add_poly: failed to add polygon\n"); + if(!(tmp = dynarr_push(bsp->soup, &poly))) { + fprintf(stderr, "bsp_add_poly: failed to reallocate polygon soup\n"); + free(poly.verts); return -1; } - bsp->root = n; + bsp->soup = tmp; + return 0; } @@ -123,9 +147,32 @@ int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m) return 0; } +int bsp_build(struct bsptree *bsp) +{ + assert(bsp->soup); + assert(!dynarr_empty(bsp->soup)); + + free_tree(bsp->root); + + printf("building BSP tree with %d source polygons ...\n", dynarr_size(bsp->soup)); + if(!(bsp->root = build_tree(bsp->soup, dynarr_size(bsp->soup)))) { + fprintf(stderr, "bsp_build failed\n"); + return -1; + } + printf("done. created a tree with %d nodes\n", count_nodes(bsp->root)); + + /* build_tree has called dynarr_free on bsp->soup */ + bsp->soup = 0; + + return 0; +} + void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z) { vec3_t vdir; + + assert(bsp->root); + vdir.x = view_x; vdir.y = view_y; vdir.z = view_z; @@ -143,21 +190,20 @@ static void free_tree(struct bspnode *n) if(n) { free_tree(n->front); free_tree(n->back); + free(n->poly.verts); free(n); } } -static struct bspnode *new_node(struct g3d_vertex *v, int vnum) +static int init_poly(struct bsppoly *poly, struct g3d_vertex *v, int vnum) { - struct bspnode *n; vec3_t va, vb, norm; - if(!(n = malloc(sizeof *n)) || !(n->verts = malloc(vnum * sizeof *n->verts))) { - fprintf(stderr, "failed to allocate BSP tree node\n"); - free(n); - return 0; + if(init_poly_noplane(poly, v, vnum) == -1) { + return -1; } + va.x = v[1].x - v[0].x; va.y = v[1].y - v[0].y; va.z = v[1].z - v[0].z; @@ -167,82 +213,213 @@ static struct bspnode *new_node(struct g3d_vertex *v, int vnum) norm = v3_cross(va, vb); v3_normalize(&norm); - n->plane.x = v[0].x; - n->plane.y = v[0].y; - n->plane.z = v[0].z; - n->plane.nx = norm.x; - n->plane.ny = norm.y; - n->plane.nz = norm.z; + poly->plane.x = v[0].x; + poly->plane.y = v[0].y; + poly->plane.z = v[0].z; + poly->plane.nx = norm.x; + poly->plane.ny = norm.y; + poly->plane.nz = norm.z; + return 0; +} - n->vcount = vnum; - memcpy(n->verts, v, vnum * sizeof *n->verts); +static int init_poly_noplane(struct bsppoly *poly, struct g3d_vertex *v, int vnum) +{ + if(!(poly->verts = malloc(vnum * sizeof *poly->verts))) { + fprintf(stderr, "failed to allocate BSP polygon\n"); + return -1; + } + poly->vcount = vnum; + memcpy(poly->verts, v, vnum * sizeof *poly->verts); + return 0; +} + +static int choose_poly(struct bsppoly *polyarr, int num_polys) +{ + int i, j, best, best_splits; - n->front = n->back = 0; - return n; + if(num_polys <= 1) { + return 0; + } + + best = -1; + best_splits = INT_MAX; + + for(i=0; i %d splits\n", num_polys, best_splits); + + return best; } -static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, int vnum) +static struct bspnode *build_tree(struct bsppoly *polyarr, int num_polys) { + int i, pidx, vnum; + struct bsppoly *sp, *tmp; + struct bsppoly *front_polys, *back_polys; + struct bspnode *node; + struct bspnode *nres; - int clipres, clipres_neg, clipped_vnum, clipped_neg_vnum; - struct g3d_vertex *clipped, *clipped_neg; + int clipres, clipres_neg, clipped_vnum, clipped_neg_vnum, max_clipped_vnum = 0; + struct g3d_vertex *v, *clipped = 0, *clipped_neg = 0; struct cplane negplane; - assert(vnum > 0); - - if(!n) { - return new_node(v, vnum); + if((pidx = choose_poly(polyarr, num_polys)) == -1) { + return 0; } - - 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; + sp = polyarr + pidx; + + negplane.x = sp->plane.x; + negplane.y = sp->plane.y; + negplane.z = sp->plane.z; + negplane.nx = -sp->plane.nx; + negplane.ny = -sp->plane.ny; + negplane.nz = -sp->plane.nz; + + if(!(front_polys = dynarr_alloc(0, sizeof *front_polys)) || + !(back_polys = dynarr_alloc(0, sizeof *back_polys))) { + fprintf(stderr, "build_tree: failed to allocate front/back polygon arrays\n"); + dynarr_free(front_polys); + return 0; } - if(clipres > 0) { - /* polygon completely in the positive subspace */ - if(!(nres = add_poly_tree(n->front, v, vnum))) { - return 0; + for(i=0; i max_clipped_vnum) { + /* resize clipped polygon buffers if necessary */ + max_clipped_vnum = vnum * 2; + if(!(v = realloc(clipped, max_clipped_vnum * sizeof *clipped))) { + fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n"); + goto fail; + } + clipped = v; + if(!(v = realloc(clipped_neg, max_clipped_vnum * sizeof *clipped))) { + fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n"); + goto fail; + } + clipped_neg = v; } - n->front = nres; - } else if(clipres < 0) { - /* polygon completely in the negative subspace */ - if(!(nres = add_poly_tree(n->back, v, vnum))) { - return 0; + v = polyarr[i].verts; + + clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &sp->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; } - n->back = nres; - } else { - /* polygon is straddling the plane */ - if(!(nres = add_poly_tree(n->front, clipped, clipped_vnum))) { - return 0; + if(clipres > 0) { + /* polygon completely in the positive subspace */ + if(!(tmp = dynarr_push(front_polys, polyarr + i))) { + fprintf(stderr, "build_tree: failed to reallocate polygon array\n"); + goto fail; + } + front_polys = tmp; + + } else if(clipres < 0) { + /* polygon completely in the negative subspace */ + if(!(tmp = dynarr_push(back_polys, polyarr + i))) { + fprintf(stderr, "build_tree: failed to reallocate polygon array\n"); + goto fail; + } + back_polys = tmp; + + } else { + /* polygon is straddling the plane */ + struct bsppoly poly; + poly.plane = polyarr[i].plane; + + if(init_poly_noplane(&poly, clipped, clipped_vnum) == -1) { + goto fail; + } + if(!(tmp = dynarr_push(front_polys, &poly))) { + fprintf(stderr, "build_tree: failed to reallocate polygon array\n"); + free(poly.verts); + goto fail; + } + front_polys = tmp; + + if(init_poly_noplane(&poly, clipped_neg, clipped_neg_vnum) == -1) { + goto fail; + } + if(!(tmp = dynarr_push(back_polys, &poly))) { + fprintf(stderr, "build_tree: failed to reallocate polygon array\n"); + free(poly.verts); + goto fail; + } + back_polys = tmp; + + /* we allocated new sub-polygons, so we need to free the original vertex array */ + free(polyarr[i].verts); } - n->front = nres; + } + + if(!(node = malloc(sizeof *node))) { + fprintf(stderr, "build_tree: failed to allocate new BSP node\n"); + goto fail; + } + node->poly = *sp; + node->front = node->back = 0; - if(!(nres = add_poly_tree(n->back, clipped_neg, clipped_neg_vnum))) { - return 0; + if(dynarr_size(front_polys)) { + if(!(node->front = build_tree(front_polys, dynarr_size(front_polys)))) { + goto fail; + } + } + if(dynarr_size(back_polys)) { + if(!(node->back = build_tree(back_polys, dynarr_size(back_polys)))) { + goto fail; } - n->back = nres; } - return n; + + free(clipped); + free(clipped_neg); + + /* we no longer need the original polygon array */ + dynarr_free(polyarr); + + return node; + +fail: + free(clipped); + free(clipped_neg); + + for(i=0; ix * n->plane.nx + vdir->y * n->plane.ny + vdir->z * n->plane.nz; + p = &n->poly; + + dot = vdir->x * p->plane.nx + vdir->y * p->plane.ny + vdir->z * p->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); + g3d_draw_indexed(p->vcount, p->verts, p->vcount, 0, 0); #else - debug_draw_poly(n->verts, n->vcount); + debug_draw_poly(p->verts, p->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); + g3d_draw_indexed(p->vcount, p->verts, p->vcount, 0, 0); #else - debug_draw_poly(n->verts, n->vcount); + debug_draw_poly(p->verts, p->vcount); #endif draw_bsp_tree(n->front, vdir); } diff --git a/src/bsptree.h b/src/bsptree.h index ff29051..2839ab0 100644 --- a/src/bsptree.h +++ b/src/bsptree.h @@ -5,15 +5,20 @@ #include "vmath.h" #include "polyclip.h" -struct bspnode { +struct bsppoly { struct cplane plane; int vcount; struct g3d_vertex *verts; +}; + +struct bspnode { + struct bsppoly poly; struct bspnode *front, *back; }; struct bsptree { struct bspnode *root; + struct bsppoly *soup; /* dynarr: see dynarr.h */ }; int init_bsp(struct bsptree *bsp); @@ -25,6 +30,8 @@ int load_bsp(struct bsptree *bsp, const char *fname); int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum); int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m); +int bsp_build(struct bsptree *bsp); + void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z); #endif /* BSPMESH_H_ */ diff --git a/src/demo.c b/src/demo.c index 072b6ce..2ff25a7 100644 --- a/src/demo.c +++ b/src/demo.c @@ -211,7 +211,7 @@ void mouse_orbit_update(float *theta, float *phi, float *dist) int dy = mouse_y - prev_my; if(dx || dy) { - if(mouse_bmask & 1) { + if(mouse_bmask & MOUSE_LEFT) { float p = *phi; *theta += dx * 1.0; p += dy * 1.0; @@ -220,7 +220,7 @@ void mouse_orbit_update(float *theta, float *phi, float *dist) if(p > 90) p = 90; *phi = p; } - if(mouse_bmask & 4) { + if(mouse_bmask & MOUSE_RIGHT) { *dist += dy * 0.5; if(*dist < 0) *dist = 0; diff --git a/src/demo.h b/src/demo.h index fdb238b..63489c7 100644 --- a/src/demo.h +++ b/src/demo.h @@ -13,6 +13,12 @@ extern unsigned long time_msec; extern int mouse_x, mouse_y; extern unsigned int mouse_bmask; +enum { + MOUSE_LEFT = 1, + MOUSE_RIGHT = 2, + MOUSE_MIDDLE = 4 +}; + extern float sball_matrix[16]; int demo_init(int argc, char **argv); diff --git a/src/sdl/main.c b/src/sdl/main.c index 3165e31..358d774 100644 --- a/src/sdl/main.c +++ b/src/sdl/main.c @@ -38,7 +38,7 @@ int main(int argc, char **argv) } vmem_front = vmem_back = fb_pixels; - SDL_Init(SDL_INIT_VIDEO | SDL_INIT_TIMER); + SDL_Init(SDL_INIT_VIDEO | SDL_INIT_TIMER | SDL_INIT_NOPARACHUTE); if(!(fbsurf = SDL_SetVideoMode(xsz, ysz, fb_bpp, sdl_flags))) { fprintf(stderr, "failed to set video mode %dx%d %dbpp\n", fb_width, fb_height, fb_bpp); free(fb_pixels); @@ -119,6 +119,21 @@ void swap_buffers(void *pixels) } } +static int bnmask(int sdlbn) +{ + switch(sdlbn) { + case SDL_BUTTON_LEFT: + return MOUSE_LEFT; + case SDL_BUTTON_RIGHT: + return MOUSE_RIGHT; + case SDL_BUTTON_MIDDLE: + return MOUSE_MIDDLE; + default: + break; + } + return 0; +} + static void handle_event(SDL_Event *ev) { switch(ev->type) { @@ -142,10 +157,10 @@ static void handle_event(SDL_Event *ev) break; case SDL_MOUSEBUTTONDOWN: - mouse_bmask |= 1 << (ev->button.button - SDL_BUTTON_LEFT); + mouse_bmask |= bnmask(ev->button.button); if(0) { case SDL_MOUSEBUTTONUP: - mouse_bmask &= ~(1 << (ev->button.button - SDL_BUTTON_LEFT)); + mouse_bmask &= ~bnmask(ev->button.button); } mouse_x = ev->button.x / fbscale; mouse_y = ev->button.y / fbscale; -- 1.7.10.4