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