5 #if defined(__WATCOMC__) || defined(_MSC_VER) || defined(__DJGPP__)
16 struct bspfile_header {
21 static int count_nodes(struct bspnode *n);
22 static void free_tree(struct bspnode *n);
24 static struct bspnode *new_node(struct g3d_vertex *v, int vnum);
25 static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, int vnum);
26 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir);
28 static void save_bsp_tree(struct bspnode *n, FILE *fp);
29 static struct bspnode *load_bsp_tree(FILE *fp);
31 int init_bsp(struct bsptree *bsp)
37 void destroy_bsp(struct bsptree *bsp)
42 int save_bsp(struct bsptree *bsp, const char *fname)
45 struct bspfile_header hdr;
47 if(!(fp = fopen(fname, "wb"))) {
48 fprintf(stderr, "save_bsp: failed to open %s for writing\n", fname);
52 memcpy(hdr.magic, "MBSP", 4);
53 hdr.num_nodes = count_nodes(bsp->root);
54 fwrite(&hdr, sizeof hdr, 1, fp);
56 save_bsp_tree(bsp->root, fp);
62 int load_bsp(struct bsptree *bsp, const char *fname)
65 struct bspfile_header hdr;
67 if(!(fp = fopen(fname, "rb"))) {
68 fprintf(stderr, "load_bsp: failed to open %s\n", fname);
72 if(fread(&hdr, sizeof hdr, 1, fp) < 1) {
73 fprintf(stderr, "load_bsp: %s: failed to read header\n", fname);
77 if(memcmp(hdr.magic, "MBSP", 4) != 0) {
78 fprintf(stderr, "load_bsp: %s: invalid magic\n", fname);
82 bsp->root = load_bsp_tree(fp);
88 int bsp_add_poly(struct bsptree *bsp, struct g3d_vertex *v, int vnum)
93 if(!(n = add_poly_tree(bsp->root, v, vnum))) {
94 fprintf(stderr, "bsp_add_poly: failed to add polygon\n");
101 int bsp_add_mesh(struct bsptree *bsp, struct g3d_mesh *m)
104 struct g3d_vertex v[4];
105 struct g3d_vertex *vptr = m->varr;
106 uint16_t *iptr = m->iarr;
108 nfaces = m->iarr ? m->icount / m->prim : m->vcount / m->prim;
110 for(i=0; i<nfaces; i++) {
111 for(j=0; j<m->prim; j++) {
113 v[j] = m->varr[*iptr++];
118 if(bsp_add_poly(bsp, v, m->prim) == -1) {
125 void draw_bsp(struct bsptree *bsp, float view_x, float view_y, float view_z)
131 draw_bsp_tree(bsp->root, &vdir);
134 static int count_nodes(struct bspnode *n)
137 return count_nodes(n->front) + count_nodes(n->back) + 1;
140 static void free_tree(struct bspnode *n)
150 static struct bspnode *new_node(struct g3d_vertex *v, int vnum)
155 if(!(n = malloc(sizeof *n)) || !(n->verts = malloc(vnum * sizeof *n->verts))) {
156 fprintf(stderr, "failed to allocate BSP tree node\n");
160 va.x = v[1].x - v[0].x;
161 va.y = v[1].y - v[0].y;
162 va.z = v[1].z - v[0].z;
163 vb.x = v[2].x - v[0].x;
164 vb.y = v[2].y - v[0].y;
165 vb.z = v[2].z - v[0].z;
166 norm = v3_cross(va, vb);
172 n->plane.nx = norm.x;
173 n->plane.ny = norm.y;
174 n->plane.nz = norm.z;
177 memcpy(n->verts, v, vnum * sizeof *n->verts);
179 n->front = n->back = 0;
183 static struct bspnode *add_poly_tree(struct bspnode *n, struct g3d_vertex *v, int vnum)
185 struct bspnode *nres;
186 int clipres, clipres_neg, clipped_vnum, clipped_neg_vnum;
187 struct g3d_vertex *clipped, *clipped_neg;
188 struct cplane negplane;
193 return new_node(v, vnum);
196 negplane.x = n->plane.x;
197 negplane.y = n->plane.y;
198 negplane.z = n->plane.z;
199 negplane.nx = -n->plane.nx;
200 negplane.ny = -n->plane.ny;
201 negplane.nz = -n->plane.nz;
203 clipped = alloca((vnum * 2) * sizeof *clipped);
204 clipped_neg = alloca((vnum * 2) * sizeof *clipped_neg);
206 clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &n->plane);
207 clipres_neg = clip_poly(clipped_neg, &clipped_neg_vnum, v, vnum, &negplane);
209 /* detect edge cases where due to floating point imprecision, clipping
210 * by the positive plane clips the polygon, but clipping by the negative
211 * plane doesn't. If that happens, consider the polygon completely on
212 * the side indicated by -clipres_neg
214 if(clipres == 0 && clipres_neg != 0) {
215 clipres = -clipres_neg;
219 /* polygon completely in the positive subspace */
220 if(!(nres = add_poly_tree(n->front, v, vnum))) {
225 } else if(clipres < 0) {
226 /* polygon completely in the negative subspace */
227 if(!(nres = add_poly_tree(n->back, v, vnum))) {
233 /* polygon is straddling the plane */
234 if(!(nres = add_poly_tree(n->front, clipped, clipped_vnum))) {
239 if(!(nres = add_poly_tree(n->back, clipped_neg, clipped_neg_vnum))) {
250 static void debug_draw_poly(struct g3d_vertex *varr, int vcount)
252 int i, nfaces = vcount - 2;
253 int vbuf_size = nfaces * 3;
254 struct g3d_vertex *vbuf = alloca(vbuf_size * sizeof *vbuf);
255 struct g3d_vertex *vptr = varr + 1;
257 for(i=0; i<nfaces; i++) {
258 vbuf[i * 3] = varr[0];
259 vbuf[i * 3 + 1] = *vptr++;
260 vbuf[i * 3 + 2] = *vptr;
263 g3d_draw_indexed(G3D_TRIANGLES, vbuf, vbuf_size, 0, 0);
267 static void draw_bsp_tree(struct bspnode *n, const vec3_t *vdir)
273 dot = vdir->x * n->plane.nx + vdir->y * n->plane.ny + vdir->z * n->plane.nz;
275 draw_bsp_tree(n->front, vdir);
277 g3d_draw_indexed(n->vcount, n->verts, n->vcount, 0, 0);
279 debug_draw_poly(n->verts, n->vcount);
281 draw_bsp_tree(n->back, vdir);
283 draw_bsp_tree(n->back, vdir);
285 g3d_draw_indexed(n->vcount, n->verts, n->vcount, 0, 0);
287 debug_draw_poly(n->verts, n->vcount);
289 draw_bsp_tree(n->front, vdir);
293 static void save_bsp_tree(struct bspnode *n, FILE *fp)
298 static struct bspnode *load_bsp_tree(FILE *fp)