git.mutantstargoat.com Git - dosdemo/blob - src/bsptree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <assert.h>
   5 #include "bsptree.h"
   6 #include "dynarr.h"
   7 #include "inttypes.h"
   8 #include "polyclip.h"
   9 #include "vmath.h"
  10
  11 struct bspfile_header {
  12         char magic[4];
  13         uint32_t num_nodes;
  14 };
  15
  16 static int count_nodes(struct bspnode *n);
  17 static void free_tree(struct bspnode *n);
  18
  19 static struct bspnode *new_node(struct g3d_vertex *v, int vnum);
  20 static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, int vnum);
  21 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir);
  22
  23 static void save_bsp_tree(struct bspnode *n, FILE *fp);
  24 static struct bspnode *load_bsp_tree(FILE *fp);
  25
  26 int init_bsp(struct bsptree *bsp)
  27 {
  28         bsp->root = 0;
  29         return 0;
  30 }
  31
  32 void destroy_bsp(struct bsptree *bsp)
  33 {
  34         free_tree(bsp->root);
  35 }
  36
  37 int save_bsp(struct bsptree *bsp, const char *fname)
  38 {
  39         FILE *fp;
  40         struct bspfile_header hdr;
  41
  42         if(!(fp = fopen(fname, "wb"))) {
  43                 fprintf(stderr, "save_bsp: failed to open %s for writing\n", fname);
  44                 return -1;
  45         }
  46
  47         memcpy(hdr.magic, "MBSP", 4);
  48         hdr.num_nodes = count_nodes(bsp->root);
  49         fwrite(&hdr, sizeof hdr, 1, fp);
  50
  51         save_bsp_tree(bsp->root, fp);
  52
  53         fclose(fp);
  54         return 0;
  55 }
  56
  57 int load_bsp(struct bsptree *bsp, const char *fname)
  58 {
  59         FILE *fp;
  60         struct bspfile_header hdr;
  61
  62         if(!(fp = fopen(fname, "rb"))) {
  63                 fprintf(stderr, "load_bsp: failed to open %s\n", fname);
  64                 return -1;
  65         }
  66
  67         if(fread(&hdr, sizeof hdr, 1, fp) < 1) {
  68                 fprintf(stderr, "load_bsp: %s: failed to read header\n", fname);
  69                 fclose(fp);
  70                 return -1;
  71         }
  72         if(memcmp(hdr.magic, "MBSP", 4) != 0) {
  73                 fprintf(stderr, "load_bsp: %s: invalid magic\n", fname);
  74                 fclose(fp);
  75                 return -1;
  76         }
  77         bsp->root = load_bsp_tree(fp);
  78
  79         fclose(fp);
  80         return 0;
  81 }
  82
  83 int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum)
  84 {
  85         struct bspnode *n;
  86         assert(vnum >= 3);
  87
  88         if(!(n = add_poly_tree(bsp->root, v, vnum))) {
  89                 fprintf(stderr, "bsp_add_poly: failed to add polygon\n");
  90                 return -1;
  91         }
  92         bsp->root = n;
  93         return 0;
  94 }
  95
  96 int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
  97 {
  98         int i, j, nfaces;
  99         struct g3d_vertex v[4];
 100         struct g3d_vertex *vptr = m->varr;
 101         uint16_t *iptr = m->iarr;
 102
 103         nfaces = m->iarr ? m->icount / m->prim : m->vcount / m->prim;
 104
 105         for(i=0; i<nfaces; i++) {
 106                 for(j=0; j<m->prim; j++) {
 107                         if(m->iarr) {
 108                                 v[j] = m->varr[*iptr++];
 109                         } else {
 110                                 v[j] = *vptr++;
 111                         }
 112                 }
 113                 if(bsp_add_poly(bsp, v, m->prim) == -1) {
 114                         return -1;
 115                 }
 116         }
 117         return 0;
 118 }
 119
 120 void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z)
 121 {
 122         vec3_t vdir;
 123         vdir.x = view_x;
 124         vdir.y = view_y;
 125         vdir.z = view_z;
 126         draw_bsp_tree(bsp->root, &vdir);
 127 }
 128
 129 static int count_nodes(struct bspnode *n)
 130 {
 131         if(!n) return 0;
 132         return count_nodes(n->front) + count_nodes(n->back) + 1;
 133 }
 134
 135 static void free_tree(struct bspnode *n)
 136 {
 137         if(n) {
 138                 free_tree(n->front);
 139                 free_tree(n->back);
 140                 free(n);
 141         }
 142 }
 143
 144
 145 static struct bspnode *new_node(struct g3d_vertex *v, int vnum)
 146 {
 147         struct bspnode *n;
 148         vec3_t va, vb, norm;
 149
 150         if(!(n = malloc(sizeof *n)) || !(n->verts = malloc(vnum * sizeof *n->verts))) {
 151                 fprintf(stderr, "failed to allocate BSP tree node\n");
 152                 free(n);
 153                 return 0;
 154         }
 155         va.x = v[1].x - v[0].x;
 156         va.y = v[1].y - v[0].y;
 157         va.z = v[1].z - v[0].z;
 158         vb.x = v[2].x - v[0].x;
 159         vb.y = v[2].y - v[0].y;
 160         vb.z = v[2].z - v[0].z;
 161         norm = v3_cross(va, vb);
 162         v3_normalize(&norm);
 163
 164         n->plane.x = v[0].x;
 165         n->plane.y = v[0].y;
 166         n->plane.z = v[0].z;
 167         n->plane.nx = norm.x;
 168         n->plane.ny = norm.y;
 169         n->plane.nz = norm.z;
 170
 171         n->vcount = vnum;
 172         memcpy(n->verts, v, vnum * sizeof *n->verts);
 173
 174         n->front = n->back = 0;
 175         return n;
 176 }
 177
 178 static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, int vnum)
 179 {
 180         struct bspnode *nres;
 181         int clipres, clipres_neg, clipped_vnum, clipped_neg_vnum;
 182         struct g3d_vertex *clipped, *clipped_neg;
 183         struct cplane negplane;
 184
 185         assert(vnum > 0);
 186
 187         if(!n) {
 188                 return new_node(v, vnum);
 189         }
 190
 191         negplane.x = n->plane.x;
 192         negplane.y = n->plane.y;
 193         negplane.z = n->plane.z;
 194         negplane.nx = -n->plane.nx;
 195         negplane.ny = -n->plane.ny;
 196         negplane.nz = -n->plane.nz;
 197
 198         clipped = alloca((vnum * 2) * sizeof *clipped);
 199         clipped_neg = alloca((vnum * 2) * sizeof *clipped_neg);
 200
 201         clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &n->plane);
 202         clipres_neg = clip_poly(clipped_neg, &clipped_neg_vnum, v, vnum, &negplane);
 203
 204         /* detect edge cases where due to floating point imprecision, clipping
 205          * by the positive plane clips the polygon, but clipping by the negative
 206          * plane doesn't. If that happens, consider the polygon completely on
 207          * the side indicated by -clipres_neg
 208          */
 209         if(clipres == 0 && clipres_neg != 0) {
 210                 clipres = -clipres_neg;
 211         }
 212
 213         if(clipres > 0) {
 214                 /* polygon completely in the positive subspace */
 215                 if(!(nres = add_poly_tree(n->front, v, vnum))) {
 216                         return 0;
 217                 }
 218                 n->front = nres;
 219
 220         } else if(clipres < 0) {
 221                 /* polygon completely in the negative subspace */
 222                 if(!(nres = add_poly_tree(n->back, v, vnum))) {
 223                         return 0;
 224                 }
 225                 n->back = nres;
 226
 227         } else {
 228                 /* polygon is straddling the plane */
 229                 if(!(nres = add_poly_tree(n->front, clipped, clipped_vnum))) {
 230                         return 0;
 231                 }
 232                 n->front = nres;
 233
 234                 if(!(nres = add_poly_tree(n->back, clipped_neg, clipped_neg_vnum))) {
 235                         return 0;
 236                 }
 237                 n->back = nres;
 238         }
 239         return n;
 240 }
 241
 242 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir)
 243 {
 244         float dot;
 245
 246         if(!n) return;
 247
 248         dot = vdir->x * n->plane.nx + vdir->y * n->plane.ny + vdir->z * n->plane.nz;
 249         if(dot >= 0.0f) {
 250                 draw_bsp_tree(n->front, vdir);
 251                 g3d_draw_indexed(n->vcount, n->verts, n->vcount, 0, 0);
 252                 draw_bsp_tree(n->back, vdir);
 253         } else {
 254                 draw_bsp_tree(n->back, vdir);
 255                 g3d_draw_indexed(n->vcount, n->verts, n->vcount, 0, 0);
 256                 draw_bsp_tree(n->front, vdir);
 257         }
 258 }
 259
 260 static void save_bsp_tree(struct bspnode *n, FILE *fp)
 261 {
 262         /* TODO */
 263 }
 264
 265 static struct bspnode *load_bsp_tree(FILE *fp)
 266 {
 267         return 0;       /* TODO */
 268 }