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