From b546d1a5227ee3a263447e279434842d230f700a Mon Sep 17 00:00:00 2001 From: John Tsiombikas Date: Sun, 18 Feb 2018 08:59:33 +0200 Subject: [PATCH] started BSP tree --- src/bsptree.c | 227 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/bsptree.h | 30 ++++++++ src/vmath.h | 27 +++++++ 3 files changed, 284 insertions(+) create mode 100644 src/bsptree.c create mode 100644 src/bsptree.h diff --git a/src/bsptree.c b/src/bsptree.c new file mode 100644 index 0000000..6ad4046 --- /dev/null +++ b/src/bsptree.c @@ -0,0 +1,227 @@ +#include +#include +#include +#include +#include "bsptree.h" +#include "dynarr.h" +#include "inttypes.h" +#include "polyclip.h" +#include "vmath.h" + +struct bspfile_header { + char magic[4]; + uint32_t num_nodes; +}; + +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 void save_bsp_tree(struct bspnode *n, FILE *fp); +static struct bspnode *load_bsp_tree(FILE *fp); + +int init_bsp(struct bsptree *bsp) +{ + bsp->root = 0; + return 0; +} + +void destroy_bsp(struct bsptree *bsp) +{ + free_tree(bsp->root); +} + +int save_bsp(struct bsptree *bsp, const char *fname) +{ + FILE *fp; + struct bspfile_header hdr; + + if(!(fp = fopen(fname, "wb"))) { + fprintf(stderr, "save_bsp: failed to open %s for writing\n", fname); + return -1; + } + + memcpy(hdr.magic, "MBSP", 4); + hdr.num_nodes = count_nodes(bsp->root); + fwrite(&hdr, sizeof hdr, 1, fp); + + save_bsp_tree(bsp->root, fp); + + fclose(fp); + return 0; +} + +int load_bsp(struct bsptree *bsp, const char *fname) +{ + FILE *fp; + struct bspfile_header hdr; + + if(!(fp = fopen(fname, "rb"))) { + fprintf(stderr, "load_bsp: failed to open %s\n", fname); + return -1; + } + + if(fread(&hdr, sizeof hdr, 1, fp) < 1) { + fprintf(stderr, "load_bsp: %s: failed to read header\n", fname); + fclose(fp); + return -1; + } + if(memcmp(hdr.magic, "MBSP", 4) != 0) { + fprintf(stderr, "load_bsp: %s: invalid magic\n", fname); + fclose(fp); + return -1; + } + bsp->root = load_bsp_tree(fp); + + fclose(fp); + return 0; +} + +int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum) +{ + struct bspnode *n; + assert(vnum >= 3); + + if(!(n = add_poly_tree(bsp->root, v, vnum))) { + fprintf(stderr, "bsp_add_poly: failed to add polygon\n"); + return -1; + } + bsp->root = n; + return 0; +} + +void bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m) +{ + int i, j, nfaces; + struct g3d_vertex v[4]; + struct g3d_vertex *vptr = m->varr; + uint16_t *iptr = m->iarr; + + nfaces = m->iarr ? m->icount / m->prim : m->vcount / m->prim; + + for(i=0; iprim; j++) { + if(m->iarr) { + v[j] = m->varr[*iptr++]; + } else { + v[j] = *vptr++; + } + } + bsp_add_poly(bsp, v, m->prim); + } +} + +void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z) +{ +} + +static int count_nodes(struct bspnode *n) +{ + if(!n) return 0; + return count_nodes(n->front) + count_nodes(n->back) + 1; +} + +static void free_tree(struct bspnode *n) +{ + if(n) { + free_tree(n->front); + free_tree(n->back); + free(n); + } +} + + +static struct bspnode *new_node(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; + } + va.x = v[1].x - v[0].x; + va.y = v[1].y - v[0].y; + va.z = v[1].z - v[0].z; + vb.x = v[2].x - v[0].x; + vb.y = v[2].y - v[0].y; + vb.z = v[2].z - v[0].z; + 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; + + n->vcount = vnum; + memcpy(n->verts, v, vnum * sizeof *n->verts); + + n->front = n->back = 0; + return 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; + struct cplane negplane; + + if(!n) { + return new_node(v, vnum); + } + + clipped = alloca((vnum + 1) * sizeof *clipped); + + clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &n->plane); + 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 */ + 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); + + if(!(nres = add_poly_tree(n->back, clipped, clipped_vnum))) { + return 0; + } + n->back = nres; + return n; +} + +static void save_bsp_tree(struct bspnode *n, FILE *fp) +{ + /* TODO */ +} + +static struct bspnode *load_bsp_tree(FILE *fp) +{ + return 0; /* TODO */ +} diff --git a/src/bsptree.h b/src/bsptree.h new file mode 100644 index 0000000..53b4cd2 --- /dev/null +++ b/src/bsptree.h @@ -0,0 +1,30 @@ +#ifndef BSPMESH_H_ +#define BSPMESH_H_ + +#include "mesh.h" +#include "vmath.h" +#include "polyclip.h" + +struct bspnode { + struct cplane plane; + int vcount; + struct g3d_vertex *verts; + struct bspnode *front, *back; +}; + +struct bsptree { + struct bspnode *root; +}; + +int init_bsp(struct bsptree *bsp); +void destroy_bsp(struct bsptree *bsp); + +int save_bsp(struct bsptree *bsp, const char *fname); +int load_bsp(struct bsptree *bsp, const char *fname); + +int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum); +void 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); + +#endif /* BSPMESH_H_ */ diff --git a/src/vmath.h b/src/vmath.h index 7e35cc8..6d1add9 100644 --- a/src/vmath.h +++ b/src/vmath.h @@ -29,11 +29,38 @@ static INLINE vec3_t v3_cons(float x, float y, float z) return res; } +static INLINE void v3_negate(vec3_t *v) +{ + v->x = -v->x; + v->y = -v->y; + v->z = -v->z; +} + static INLINE float v3_dot(vec3_t v1, vec3_t v2) { return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z; } +static INLINE vec3_t v3_cross(vec3_t v1, vec3_t v2) +{ + vec3_t res; + res.x = v1.y * v2.z - v1.z * v2.y; + res.y = v1.z * v2.x - v1.x * v2.z; + res.z = v1.x * v2.y - v1.y * v2.x; + return res; +} + +static INLINE void v3_normalize(vec3_t *v) +{ + float mag = sqrt(v->x * v->x + v->y * v->y + v->z * v->z); + if(mag != 0.0f) { + float s = 1.0f / mag; + v->x *= s; + v->y *= s; + v->z *= s; + } +} + /* quaternion functions */ static INLINE quat_t quat_cons(float s, float x, float y, float z) { -- 1.7.10.4