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
  22 static void save_bsp_tree(struct bspnode *n, FILE *fp);
  23 static struct bspnode *load_bsp_tree(FILE *fp);
  24
  25 int init_bsp(struct bsptree *bsp)
  26 {
  27         bsp->root = 0;
  28         return 0;
  29 }
  30
  31 void destroy_bsp(struct bsptree *bsp)
  32 {
  33         free_tree(bsp->root);
  34 }
  35
  36 int save_bsp(struct bsptree *bsp, const char *fname)
  37 {
  38         FILE *fp;
  39         struct bspfile_header hdr;
  40
  41         if(!(fp = fopen(fname, "wb"))) {
  42                 fprintf(stderr, "save_bsp: failed to open %s for writing\n", fname);
  43                 return -1;
  44         }
  45
  46         memcpy(hdr.magic, "MBSP", 4);
  47         hdr.num_nodes = count_nodes(bsp->root);
  48         fwrite(&hdr, sizeof hdr, 1, fp);
  49
  50         save_bsp_tree(bsp->root, fp);
  51
  52         fclose(fp);
  53         return 0;
  54 }
  55
  56 int load_bsp(struct bsptree *bsp, const char *fname)
  57 {
  58         FILE *fp;
  59         struct bspfile_header hdr;
  60
  61         if(!(fp = fopen(fname, "rb"))) {
  62                 fprintf(stderr, "load_bsp: failed to open %s\n", fname);
  63                 return -1;
  64         }
  65
  66         if(fread(&hdr, sizeof hdr, 1, fp) < 1) {
  67                 fprintf(stderr, "load_bsp: %s: failed to read header\n", fname);
  68                 fclose(fp);
  69                 return -1;
  70         }
  71         if(memcmp(hdr.magic, "MBSP", 4) != 0) {
  72                 fprintf(stderr, "load_bsp: %s: invalid magic\n", fname);
  73                 fclose(fp);
  74                 return -1;
  75         }
  76         bsp->root = load_bsp_tree(fp);
  77
  78         fclose(fp);
  79         return 0;
  80 }
  81
  82 int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum)
  83 {
  84         struct bspnode *n;
  85         assert(vnum >= 3);
  86
  87         if(!(n = add_poly_tree(bsp->root, v, vnum))) {
  88                 fprintf(stderr, "bsp_add_poly: failed to add polygon\n");
  89                 return -1;
  90         }
  91         bsp->root = n;
  92         return 0;
  93 }
  94
  95 int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
  96 {
  97         int i, j, nfaces;
  98         struct g3d_vertex v[4];
  99         struct g3d_vertex *vptr = m->varr;
 100         uint16_t *iptr = m->iarr;
 101
 102         nfaces = m->iarr ? m->icount / m->prim : m->vcount / m->prim;
 103
 104         for(i=0; i<nfaces; i++) {
 105                 for(j=0; j<m->prim; j++) {
 106                         if(m->iarr) {
 107                                 v[j] = m->varr[*iptr++];
 108                         } else {
 109                                 v[j] = *vptr++;
 110                         }
 111                 }
 112                 if(bsp_add_poly(bsp, v, m->prim) == -1) {
 113                         return -1;
 114                 }
 115         }
 116         return 0;
 117 }
 118
 119 void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z)
 120 {
 121 }
 122
 123 static int count_nodes(struct bspnode *n)
 124 {
 125         if(!n) return 0;
 126         return count_nodes(n->front) + count_nodes(n->back) + 1;
 127 }
 128
 129 static void free_tree(struct bspnode *n)
 130 {
 131         if(n) {
 132                 free_tree(n->front);
 133                 free_tree(n->back);
 134                 free(n);
 135         }
 136 }
 137
 138
 139 static struct bspnode *new_node(struct g3d_vertex *v, int vnum)
 140 {
 141         struct bspnode *n;
 142         vec3_t va, vb, norm;
 143
 144         if(!(n = malloc(sizeof *n)) || !(n->verts = malloc(vnum * sizeof *n->verts))) {
 145                 fprintf(stderr, "failed to allocate BSP tree node\n");
 146                 free(n);
 147                 return 0;
 148         }
 149         va.x = v[1].x - v[0].x;
 150         va.y = v[1].y - v[0].y;
 151         va.z = v[1].z - v[0].z;
 152         vb.x = v[2].x - v[0].x;
 153         vb.y = v[2].y - v[0].y;
 154         vb.z = v[2].z - v[0].z;
 155         norm = v3_cross(va, vb);
 156         v3_normalize(&norm);
 157
 158         n->plane.x = v[0].x;
 159         n->plane.y = v[0].y;
 160         n->plane.z = v[0].z;
 161         n->plane.nx = norm.x;
 162         n->plane.ny = norm.y;
 163         n->plane.nz = norm.z;
 164
 165         n->vcount = vnum;
 166         memcpy(n->verts, v, vnum * sizeof *n->verts);
 167
 168         n->front = n->back = 0;
 169         return n;
 170 }
 171
 172 static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, int vnum)
 173 {
 174         struct bspnode *nres;
 175         int clipres, clipped_vnum;
 176         struct g3d_vertex *clipped;
 177         struct cplane negplane;
 178
 179         if(!n) {
 180                 return new_node(v, vnum);
 181         }
 182
 183         clipped = alloca((vnum + 1) * sizeof *clipped);
 184
 185         clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &n->plane);
 186         if(clipres > 0) {
 187                 /* polygon completely in the positive subspace */
 188                 if(!(nres = add_poly_tree(n->front, v, vnum))) {
 189                         return 0;
 190                 }
 191                 n->front = nres;
 192
 193         } else if(clipres < 0) {
 194                 /* polygon completely in the negative subspace */
 195                 if(!(nres = add_poly_tree(n->back, v, vnum))) {
 196                         return 0;
 197                 }
 198                 n->back = nres;
 199
 200         } else {
 201                 /* polygon is straddling the plane */
 202                 if(!(nres = add_poly_tree(n->front, clipped, clipped_vnum))) {
 203                         return 0;
 204                 }
 205                 n->front = nres;
 206
 207                 negplane.x = n->plane.x;
 208                 negplane.y = n->plane.y;
 209                 negplane.z = n->plane.z;
 210                 negplane.nx = -n->plane.nx;
 211                 negplane.ny = -n->plane.ny;
 212                 negplane.nz = -n->plane.nz;
 213
 214                 clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &negplane);
 215                 /*assert(clipres == 0);*/
 216
 217                 if(!(nres = add_poly_tree(n->back, clipped, clipped_vnum))) {
 218                         return 0;
 219                 }
 220                 n->back = nres;
 221         }
 222         return n;
 223 }
 224
 225 static void save_bsp_tree(struct bspnode *n, FILE *fp)
 226 {
 227         /* TODO */
 228 }
 229
 230 static struct bspnode *load_bsp_tree(FILE *fp)
 231 {
 232         return 0;       /* TODO */
 233 }