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