11 struct bspfile_header {
16 static int count_nodes(struct bspnode *n);
17 static void free_tree(struct bspnode *n);
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);
22 static void save_bsp_tree(struct bspnode *n, FILE *fp);
23 static struct bspnode *load_bsp_tree(FILE *fp);
25 int init_bsp(struct bsptree *bsp)
31 void destroy_bsp(struct bsptree *bsp)
36 int save_bsp(struct bsptree *bsp, const char *fname)
39 struct bspfile_header hdr;
41 if(!(fp = fopen(fname, "wb"))) {
42 fprintf(stderr, "save_bsp: failed to open %s for writing\n", fname);
46 memcpy(hdr.magic, "MBSP", 4);
47 hdr.num_nodes = count_nodes(bsp->root);
48 fwrite(&hdr, sizeof hdr, 1, fp);
50 save_bsp_tree(bsp->root, fp);
56 int load_bsp(struct bsptree *bsp, const char *fname)
59 struct bspfile_header hdr;
61 if(!(fp = fopen(fname, "rb"))) {
62 fprintf(stderr, "load_bsp: failed to open %s\n", fname);
66 if(fread(&hdr, sizeof hdr, 1, fp) < 1) {
67 fprintf(stderr, "load_bsp: %s: failed to read header\n", fname);
71 if(memcmp(hdr.magic, "MBSP", 4) != 0) {
72 fprintf(stderr, "load_bsp: %s: invalid magic\n", fname);
76 bsp->root = load_bsp_tree(fp);
82 int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum)
87 if(!(n = add_poly_tree(bsp->root, v, vnum))) {
88 fprintf(stderr, "bsp_add_poly: failed to add polygon\n");
95 int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
98 struct g3d_vertex v[4];
99 struct g3d_vertex *vptr = m->varr;
100 uint16_t *iptr = m->iarr;
102 nfaces = m->iarr ? m->icount / m->prim : m->vcount / m->prim;
104 for(i=0; i<nfaces; i++) {
105 for(j=0; j<m->prim; j++) {
107 v[j] = m->varr[*iptr++];
112 if(bsp_add_poly(bsp, v, m->prim) == -1) {
119 void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z)
123 static int count_nodes(struct bspnode *n)
126 return count_nodes(n->front) + count_nodes(n->back) + 1;
129 static void free_tree(struct bspnode *n)
139 static struct bspnode *new_node(struct g3d_vertex *v, int vnum)
144 if(!(n = malloc(sizeof *n)) || !(n->verts = malloc(vnum * sizeof *n->verts))) {
145 fprintf(stderr, "failed to allocate BSP tree node\n");
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);
161 n->plane.nx = norm.x;
162 n->plane.ny = norm.y;
163 n->plane.nz = norm.z;
166 memcpy(n->verts, v, vnum * sizeof *n->verts);
168 n->front = n->back = 0;
172 static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, int vnum)
174 struct bspnode *nres;
175 int clipres, clipped_vnum;
176 struct g3d_vertex *clipped;
177 struct cplane negplane;
180 return new_node(v, vnum);
183 clipped = alloca((vnum + 1) * sizeof *clipped);
185 clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &n->plane);
187 /* polygon completely in the positive subspace */
188 if(!(nres = add_poly_tree(n->front, v, vnum))) {
193 } else if(clipres < 0) {
194 /* polygon completely in the negative subspace */
195 if(!(nres = add_poly_tree(n->back, v, vnum))) {
201 /* polygon is straddling the plane */
202 if(!(nres = add_poly_tree(n->front, clipped, clipped_vnum))) {
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;
214 clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &negplane);
215 /*assert(clipres == 0);*/
217 if(!(nres = add_poly_tree(n->back, clipped, clipped_vnum))) {
225 static void save_bsp_tree(struct bspnode *n, FILE *fp)
230 static struct bspnode *load_bsp_tree(FILE *fp)