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

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <limits.h>
   5 #include <assert.h>
   6 #if defined(__WATCOMC__) || defined(_MSC_VER) || defined(__DJGPP__)
   7 #include <malloc.h>
   8 #else
   9 #include <alloca.h>
  10 #endif
  11 #include "bsptree.h"
  12 #include "dynarr.h"
  13 #include "inttypes.h"
  14 #include "polyclip.h"
  15 #include "vmath.h"
  16 #include "util.h"
  17
  18 struct bspfile_header {
  19         char magic[4];
  20         uint32_t num_nodes;
  21 };
  22
  23 static int count_nodes(struct bspnode *n);
  24 static void free_tree(struct bspnode *n);
  25
  26 static int init_poly(struct bsppoly *poly, struct g3d_vertex *v, int vnum);
  27 static int init_poly_noplane(struct bsppoly *poly, struct g3d_vertex *v, int vnum);
  28
  29 static struct bspnode *build_tree(struct bsppoly *polyarr, int num_polys);
  30
  31 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir);
  32
  33 static void save_bsp_tree(struct bspnode *n, FILE *fp);
  34 static struct bspnode *load_bsp_tree(FILE *fp);
  35
  36 int init_bsp(struct bsptree *bsp)
  37 {
  38         bsp->root = 0;
  39         bsp->soup = 0;
  40         return 0;
  41 }
  42
  43 void destroy_bsp(struct bsptree *bsp)
  44 {
  45         int i;
  46
  47         free_tree(bsp->root);
  48
  49         if(bsp->soup) {
  50                 for(i=0; i<dynarr_size(bsp->soup); i++) {
  51                         free(bsp->soup[i].verts);
  52                 }
  53                 dynarr_free(bsp->soup);
  54         }
  55 }
  56
  57 int save_bsp(struct bsptree *bsp, const char *fname)
  58 {
  59         FILE *fp;
  60         struct bspfile_header hdr;
  61
  62         if(!(fp = fopen(fname, "wb"))) {
  63                 fprintf(stderr, "save_bsp: failed to open %s for writing\n", fname);
  64                 return -1;
  65         }
  66
  67         memcpy(hdr.magic, "MBSP", 4);
  68         hdr.num_nodes = count_nodes(bsp->root);
  69         fwrite(&hdr, sizeof hdr, 1, fp);
  70
  71         save_bsp_tree(bsp->root, fp);
  72
  73         fclose(fp);
  74         return 0;
  75 }
  76
  77 int load_bsp(struct bsptree *bsp, const char *fname)
  78 {
  79         FILE *fp;
  80         struct bspfile_header hdr;
  81
  82         if(!(fp = fopen(fname, "rb"))) {
  83                 fprintf(stderr, "load_bsp: failed to open %s\n", fname);
  84                 return -1;
  85         }
  86
  87         if(fread(&hdr, sizeof hdr, 1, fp) < 1) {
  88                 fprintf(stderr, "load_bsp: %s: failed to read header\n", fname);
  89                 fclose(fp);
  90                 return -1;
  91         }
  92         if(memcmp(hdr.magic, "MBSP", 4) != 0) {
  93                 fprintf(stderr, "load_bsp: %s: invalid magic\n", fname);
  94                 fclose(fp);
  95                 return -1;
  96         }
  97         bsp->root = load_bsp_tree(fp);
  98
  99         fclose(fp);
 100         return 0;
 101 }
 102
 103 int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum)
 104 {
 105         struct bsppoly poly, *tmp;
 106
 107         if(!bsp->soup && !(bsp->soup = dynarr_alloc(0, sizeof *bsp->soup))) {
 108                 fprintf(stderr, "bsp_add_poly: failed to create polygon soup dynamic array\n");
 109                 return -1;
 110         }
 111
 112         if(init_poly(&poly, v, vnum) == -1) {
 113                 return -1;
 114         }
 115
 116         if(!(tmp = dynarr_push(bsp->soup, &poly))) {
 117                 fprintf(stderr, "bsp_add_poly: failed to reallocate polygon soup\n");
 118                 free(poly.verts);
 119                 return -1;
 120         }
 121         bsp->soup = tmp;
 122
 123         return 0;
 124 }
 125
 126 int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
 127 {
 128         int i, j, nfaces;
 129         struct g3d_vertex v[4];
 130         struct g3d_vertex *vptr = m->varr;
 131         uint16_t *iptr = m->iarr;
 132
 133         nfaces = m->iarr ? m->icount / m->prim : m->vcount / m->prim;
 134
 135         for(i=0; i<nfaces; i++) {
 136                 for(j=0; j<m->prim; j++) {
 137                         if(m->iarr) {
 138                                 v[j] = m->varr[*iptr++];
 139                         } else {
 140                                 v[j] = *vptr++;
 141                         }
 142                 }
 143                 if(bsp_add_poly(bsp, v, m->prim) == -1) {
 144                         return -1;
 145                 }
 146         }
 147         return 0;
 148 }
 149
 150 int bsp_build(struct bsptree *bsp)
 151 {
 152         assert(bsp->soup);
 153         assert(!dynarr_empty(bsp->soup));
 154
 155         free_tree(bsp->root);
 156
 157         printf("building BSP tree with %d source polygons ...\n", dynarr_size(bsp->soup));
 158         if(!(bsp->root = build_tree(bsp->soup, dynarr_size(bsp->soup)))) {
 159                 fprintf(stderr, "bsp_build failed\n");
 160                 return -1;
 161         }
 162         printf("done. created a tree with %d nodes\n", count_nodes(bsp->root));
 163
 164         /* build_tree has called dynarr_free on bsp->soup */
 165         bsp->soup = 0;
 166
 167         return 0;
 168 }
 169
 170 void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z)
 171 {
 172         vec3_t vdir;
 173
 174         assert(bsp->root);
 175
 176         vdir.x = view_x;
 177         vdir.y = view_y;
 178         vdir.z = view_z;
 179         draw_bsp_tree(bsp->root, &vdir);
 180 }
 181
 182 static int count_nodes(struct bspnode *n)
 183 {
 184         if(!n) return 0;
 185         return count_nodes(n->front) + count_nodes(n->back) + 1;
 186 }
 187
 188 static void free_tree(struct bspnode *n)
 189 {
 190         if(n) {
 191                 free_tree(n->front);
 192                 free_tree(n->back);
 193                 free(n->poly.verts);
 194                 free(n);
 195         }
 196 }
 197
 198
 199 static int init_poly(struct bsppoly *poly, struct g3d_vertex *v, int vnum)
 200 {
 201         vec3_t va, vb, norm;
 202
 203         if(init_poly_noplane(poly, v, vnum) == -1) {
 204                 return -1;
 205         }
 206
 207         va.x = v[1].x - v[0].x;
 208         va.y = v[1].y - v[0].y;
 209         va.z = v[1].z - v[0].z;
 210         vb.x = v[2].x - v[0].x;
 211         vb.y = v[2].y - v[0].y;
 212         vb.z = v[2].z - v[0].z;
 213         norm = v3_cross(va, vb);
 214         v3_normalize(&norm);
 215
 216         poly->plane.x = v[0].x;
 217         poly->plane.y = v[0].y;
 218         poly->plane.z = v[0].z;
 219         poly->plane.nx = norm.x;
 220         poly->plane.ny = norm.y;
 221         poly->plane.nz = norm.z;
 222         return 0;
 223 }
 224
 225 static int init_poly_noplane(struct bsppoly *poly, struct g3d_vertex *v, int vnum)
 226 {
 227         if(!(poly->verts = malloc(vnum * sizeof *poly->verts))) {
 228                 fprintf(stderr, "failed to allocate BSP polygon\n");
 229                 return -1;
 230         }
 231         poly->vcount = vnum;
 232         memcpy(poly->verts, v, vnum * sizeof *poly->verts);
 233         return 0;
 234 }
 235
 236 static int choose_poly(struct bsppoly *polyarr, int num_polys)
 237 {
 238         int i, j, best, best_splits;
 239
 240         if(num_polys <= 1) {
 241                 return 0;
 242         }
 243
 244         best = -1;
 245         best_splits = INT_MAX;
 246
 247         for(i=0; i<num_polys; i++) {
 248                 struct cplane *plane = &polyarr[i].plane;
 249                 int num_splits = 0;
 250
 251 #pragma omp parallel for reduction(+:num_splits)
 252                 for(j=0; j<num_polys; j++) {
 253                         if(i == j) continue;
 254
 255                         if(check_clip_poly(polyarr[j].verts, polyarr[j].vcount, plane) == 0) {
 256                                 num_splits++;
 257                         }
 258                 }
 259
 260                 if(num_splits < best_splits) {
 261                         best_splits = num_splits;
 262                         best = i;
 263                 }
 264         }
 265
 266         //printf("choose_poly(..., %d) -> %d splits\n", num_polys, best_splits);
 267
 268         return best;
 269 }
 270
 271 static struct bspnode *build_tree(struct bsppoly *polyarr, int num_polys)
 272 {
 273         int i, pidx, vnum;
 274         struct bsppoly *sp, *tmp;
 275         struct bsppoly *front_polys, *back_polys;
 276         struct bspnode *node;
 277
 278         struct bspnode *nres;
 279         int clipres, clipres_neg, clipped_vnum, clipped_neg_vnum, max_clipped_vnum = 0;
 280         struct g3d_vertex *v, *clipped = 0, *clipped_neg = 0;
 281         struct cplane negplane;
 282
 283         if((pidx = choose_poly(polyarr, num_polys)) == -1) {
 284                 return 0;
 285         }
 286         sp = polyarr + pidx;
 287
 288         negplane.x = sp->plane.x;
 289         negplane.y = sp->plane.y;
 290         negplane.z = sp->plane.z;
 291         negplane.nx = -sp->plane.nx;
 292         negplane.ny = -sp->plane.ny;
 293         negplane.nz = -sp->plane.nz;
 294
 295         if(!(front_polys = dynarr_alloc(0, sizeof *front_polys)) ||
 296                         !(back_polys = dynarr_alloc(0, sizeof *back_polys))) {
 297                 fprintf(stderr, "build_tree: failed to allocate front/back polygon arrays\n");
 298                 dynarr_free(front_polys);
 299                 return 0;
 300         }
 301
 302         for(i=0; i<num_polys; i++) {
 303                 if(i == pidx) continue;
 304
 305                 vnum = polyarr[i].vcount;
 306
 307                 if(vnum * 2 > max_clipped_vnum) {
 308                         /* resize clipped polygon buffers if necessary */
 309                         max_clipped_vnum = vnum * 2;
 310                         if(!(v = realloc(clipped, max_clipped_vnum * sizeof *clipped))) {
 311                                 fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n");
 312                                 goto fail;
 313                         }
 314                         clipped = v;
 315                         if(!(v = realloc(clipped_neg, max_clipped_vnum * sizeof *clipped))) {
 316                                 fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n");
 317                                 goto fail;
 318                         }
 319                         clipped_neg = v;
 320                 }
 321
 322                 v = polyarr[i].verts;
 323
 324                 clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &sp->plane);
 325                 clipres_neg = clip_poly(clipped_neg, &clipped_neg_vnum, v, vnum, &negplane);
 326
 327                 /* detect edge cases where due to floating point imprecision, clipping
 328                  * by the positive plane clips the polygon, but clipping by the negative
 329                  * plane doesn't. If that happens, consider the polygon completely on
 330                  * the side indicated by -clipres_neg
 331                  */
 332                 if(clipres == 0 && clipres_neg != 0) {
 333                         clipres = -clipres_neg;
 334                 }
 335
 336                 if(clipres > 0) {
 337                         /* polygon completely in the positive subspace */
 338                         if(!(tmp = dynarr_push(front_polys, polyarr + i))) {
 339                                 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
 340                                 goto fail;
 341                         }
 342                         front_polys = tmp;
 343
 344                 } else if(clipres < 0) {
 345                         /* polygon completely in the negative subspace */
 346                         if(!(tmp = dynarr_push(back_polys, polyarr + i))) {
 347                                 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
 348                                 goto fail;
 349                         }
 350                         back_polys = tmp;
 351
 352                 } else {
 353                         /* polygon is straddling the plane */
 354                         struct bsppoly poly;
 355                         poly.plane = polyarr[i].plane;
 356
 357                         if(init_poly_noplane(&poly, clipped, clipped_vnum) == -1) {
 358                                 goto fail;
 359                         }
 360                         if(!(tmp = dynarr_push(front_polys, &poly))) {
 361                                 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
 362                                 free(poly.verts);
 363                                 goto fail;
 364                         }
 365                         front_polys = tmp;
 366
 367                         if(init_poly_noplane(&poly, clipped_neg, clipped_neg_vnum) == -1) {
 368                                 goto fail;
 369                         }
 370                         if(!(tmp = dynarr_push(back_polys, &poly))) {
 371                                 fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
 372                                 free(poly.verts);
 373                                 goto fail;
 374                         }
 375                         back_polys = tmp;
 376
 377                         /* we allocated new sub-polygons, so we need to free the original vertex array */
 378                         free(polyarr[i].verts);
 379                 }
 380         }
 381
 382         if(!(node = malloc(sizeof *node))) {
 383                 fprintf(stderr, "build_tree: failed to allocate new BSP node\n");
 384                 goto fail;
 385         }
 386         node->poly = *sp;
 387         node->front = node->back = 0;
 388
 389         if(dynarr_size(front_polys)) {
 390                 if(!(node->front = build_tree(front_polys, dynarr_size(front_polys)))) {
 391                         goto fail;
 392                 }
 393         }
 394         if(dynarr_size(back_polys)) {
 395                 if(!(node->back = build_tree(back_polys, dynarr_size(back_polys)))) {
 396                         goto fail;
 397                 }
 398         }
 399
 400         free(clipped);
 401         free(clipped_neg);
 402
 403         /* we no longer need the original polygon array */
 404         dynarr_free(polyarr);
 405
 406         return node;
 407
 408 fail:
 409         free(clipped);
 410         free(clipped_neg);
 411
 412         for(i=0; i<dynarr_size(front_polys); i++) {
 413                 free(front_polys[i].verts);
 414         }
 415         dynarr_free(front_polys);
 416
 417         for(i=0; i<dynarr_size(back_polys); i++) {
 418                 free(back_polys[i].verts);
 419         }
 420         dynarr_free(back_polys);
 421
 422         return 0;
 423 }
 424
 425 #undef DRAW_NGONS
 426
 427 #ifndef DRAW_NGONS
 428 static void debug_draw_poly(struct g3d_vertex *varr, int vcount)
 429 {
 430         int i, nfaces = vcount - 2;
 431         int vbuf_size = nfaces * 3;
 432         struct g3d_vertex *vbuf = alloca(vbuf_size * sizeof *vbuf);
 433         struct g3d_vertex *vptr = varr + 1;
 434
 435         for(i=0; i<nfaces; i++) {
 436                 vbuf[i * 3] = varr[0];
 437                 vbuf[i * 3 + 1] = *vptr++;
 438                 vbuf[i * 3 + 2] = *vptr;
 439         }
 440
 441         g3d_draw_indexed(G3D_TRIANGLES, vbuf, vbuf_size, 0, 0);
 442 }
 443 #endif
 444
 445 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir)
 446 {
 447         float dot;
 448         struct bsppoly *p;
 449
 450         if(!n) return;
 451
 452         p = &n->poly;
 453
 454         dot = vdir->x * p->plane.nx + vdir->y * p->plane.ny + vdir->z * p->plane.nz;
 455         if(dot >= 0.0f) {
 456                 draw_bsp_tree(n->front, vdir);
 457 #ifdef DRAW_NGONS
 458                 g3d_draw_indexed(p->vcount, p->verts, p->vcount, 0, 0);
 459 #else
 460                 debug_draw_poly(p->verts, p->vcount);
 461 #endif
 462                 draw_bsp_tree(n->back, vdir);
 463         } else {
 464                 draw_bsp_tree(n->back, vdir);
 465 #ifdef DRAW_NGONS
 466                 g3d_draw_indexed(p->vcount, p->verts, p->vcount, 0, 0);
 467 #else
 468                 debug_draw_poly(p->verts, p->vcount);
 469 #endif
 470                 draw_bsp_tree(n->front, vdir);
 471         }
 472 }
 473
 474 static void save_bsp_tree(struct bspnode *n, FILE *fp)
 475 {
 476         /* TODO */
 477 }
 478
 479 static struct bspnode *load_bsp_tree(FILE *fp)
 480 {
 481         return 0;       /* TODO */
 482 }