From: John Tsiombikas <nuclear@member.fsf.org>
Date: Tue, 22 Jun 2021 09:37:49 +0000 (+0300)
Subject: implementing build_bvh_sah
X-Git-Url: http://git.mutantstargoat.com/user/nuclear/?p=cyberay;a=commitdiff_plain;h=822cd054970ea5bc971c04eb2726333cccc5fb1a

implementing build_bvh_sah
---

diff --git a/src/bvh.c b/src/bvh.c
index dced9d9..af6ed45 100644
--- a/src/bvh.c
+++ b/src/bvh.c
@@ -2,27 +2,105 @@
 #include <float.h>
 #include "bvh.h"
 
+#define SPLIT_BUCKETS	8
+
 int build_bvh_sah(struct bvhnode *tree)
 {
-	int i, j;
-	float sarea;
+	int i, j, best;
+	float sp, sp0, spgap, area, ext[3];
+	float spcost[SPLIT_BUCKETS];
+	int part[SPLIT_BUCKETS];
+	struct triangle **tribuf, **src;
+
+	if(tree->num_faces < 16 || tree->left || tree->right) return 0;
+
+	ext[0] = tree->aabb.vmax.x - tree->aabb.vmin.x;
+	ext[1] = tree->aabb.vmax.y - tree->aabb.vmin.y;
+	ext[2] = tree->aabb.vmax.z - tree->aabb.vmin.z;
+
+	if((area = surf_area(ext[0], ext[1], ext[2])) <= 0.0f) return 0;
+
+	tree->axis = ext[0] > ext[1] ? (ext[0] > ext[2] ? 0 : 2) : (ext[1] > ext[2] ? 1 : 2);
+
+	spgap = ext[tree->axis] / SPLIT_BUCKETS;
+	sp0 = cgm_velem(&tree->aabb.vmin, tree->axis) + spgap / 2.0f;
+
+	/* allocate N arrays worth of triangle pointers, one for each bucket */
+	if(!(tribuf = malloc(tree->num_faces * SPLIT_BUCKETS * sizeof *tribuf))) {
+		fprintf(stderr, "failed to allocate buffer for BVH construction\n");
+		return -1;
+	}
+
+	for(i=0; i<SPLIT_BUCKETS; i++) {
+		sp = sp0 + i * spgap;
+		spcost[i] = eval_cost(tree, area, sp, tribuf + i * tree->num_faces, part + i);
+	}
+
+	best = 0;
+	for(i=1; i<SPLIT_BUCKETS; i++) {
+		if(spcost[i] < spcost[best]) {
+			best = i;
+		}
+	}
+
+	/* found the best split, allocate child nodes, split the original array and copy
+	 * the pointers from tribuf to each part
+	 */
+	if(!(tree->left = calloc(1, sizeof *tree->left)) || !(tree->right = calloc(1, sizeof *tree->right))) {
+		fprintf(stderr, "failed to allocate tree nodes during BVH construction\n");
+		free(tree->left);
+		free(tribuf);
+		return -1;
+	}
+
+	memcpy(tree->faces, tribuf + best * tree->num_faces, tree->num_faces * sizeof *tribuf);
+
+	tree->left->faces = tree->faces;
+	tree->left->num_faces = part[best];
+	tree->right->faces = tree->faces + part[best];
+	tree->right->num_faces = tree->faces - tree->left->faces;
+
+	/* TODO: calc aabox for each child node */
+	free(tribuf);
+}
 
-	if(tree->num_faces < 5 || tree->left || tree->right) return 0;
+static float eval_cost(struct bvhnode *node, float area, float sp, struct triangle **tribuf, int *part)
+{
+	int i;
+	float cost;
+	struct triangle *tri;
+	struct triangle **pleft, **pright;
 
-	dx = tree->aabb.vmax.x - tree->aabb.vmin.x;
-	dy = tree->aabb.vmax.y - tree->aabb.vmin.y;
-	dz = tree->aabb.vmax.z - tree->aabb.vmin.z;
+	/* partition on sp */
+	pleft = tribuf;
+	pright = tribuf + node->num_faces - 1;
 
-	if((sarea = surf_area(dx, dy, dz)) <= 0.0f) return 0;
+	for(i=0; i<node->num_faces; i++) {
+		tri = node->faces[i];
+		if(cgm_velem(tri->v, node->axis) < sp) {
+			*pleft++ = tri;
+		} else {
+			*pright-- = tri;
+		}
+	}
 
-	tree->axis = dx > dy ? (dx > dz ? dx : dz) : (dy > dz ? dy : dz);
+	/* TODO calc cost */
 
-	/* TODO */
+	*part = pleft - tribuf;
+	return cost;
 }
 
 void free_bvh_tree(struct bvhnode *tree)
 {
-	free(tree->faces);
+	if(!tree) return;
+
+	if(tree->max_faces) {
+		/* only nodes with max_faces != 0 have ownership of the faces array. all
+		 * the rest of the nodes only have pointers in the same array belonging
+		 * to an ancestor node
+		 */
+		free(tree->faces);
+	}
 	free_bvh_tree(tree->left);
 	free_bvh_tree(tree->right);
 	free(tree);
@@ -39,7 +117,7 @@ int ray_bvhnode(cgm_ray *ray, struct bvhnode *bn, float tmax, struct rayhit *hit
 
 	if(!hit) {
 		for(i=0; i<bn->num_faces; i++) {
-			if(ray_triangle(ray, bn->faces + i, tmax, 0)) {
+			if(ray_triangle(ray, bn->faces[i], tmax, 0)) {
 				return 1;
 			}
 		}
@@ -48,7 +126,7 @@ int ray_bvhnode(cgm_ray *ray, struct bvhnode *bn, float tmax, struct rayhit *hit
 
 	hit0.t = FLT_MAX;
 	for(i=0; i<bn->num_faces; i++) {
-		if(ray_triangle(ray, bn->faces + i, tmax, hit) && hit->t < hit0.t) {
+		if(ray_triangle(ray, bn->faces[i], tmax, hit) && hit->t < hit0.t) {
 			hit0 = *hit;
 			res = 1;
 		}
diff --git a/src/bvh.h b/src/bvh.h
index 03bc726..9288fdb 100644
--- a/src/bvh.h
+++ b/src/bvh.h
@@ -7,7 +7,7 @@ struct bvhnode {
 	struct aabox aabb;
 	int axis;
 
-	struct triangle *faces;
+	struct triangle **faces;
 	int num_faces, max_faces;
 
 	struct bvhnode *left, *right;
diff --git a/src/level.c b/src/level.c
index 21a82f9..0016a70 100644
--- a/src/level.c
+++ b/src/level.c
@@ -5,8 +5,7 @@
 #include "treestore.h"
 #include "mesh.h"
 
-static struct material *add_material(struct level *lvl, struct material *mtl);
-static int append_polygons(struct bvhnode *bnode, struct triangle *faces, int num_faces, struct material *mtl);
+static int add_mesh_faces(struct bvhnode *bnode, struct mesh *mesh);
 
 int load_level(struct level *lvl, const char *fname)
 {
@@ -14,8 +13,7 @@ int load_level(struct level *lvl, const char *fname)
 	char path[256];
 	struct ts_node *root, *node;
 	struct scenefile scn;
-	struct mesh *mesh;
-	struct material *mtl;
+	struct mesh *mesh, *tail;
 
 	memset(lvl, 0, sizeof *lvl);
 	if(!(lvl->st_root = calloc(1, sizeof *lvl->st_root)) ||
@@ -60,13 +58,18 @@ int load_level(struct level *lvl, const char *fname)
 			if(load_scenefile(&scn, path) == -1) {
 				goto cont;
 			}
-			mesh = scn.meshlist;
+			mesh = tail = scn.meshlist;
 			while(mesh) {
-				mtl = add_material(lvl, &mesh->mtl);
-				append_polygons(lvl->st_root, mesh->faces, mesh->num_faces, mtl);
+				add_mesh_faces(lvl->st_root, mesh);
+				tail = mesh;
 				mesh = mesh->next;
 			}
 
+			if(tail) {
+				tail->next = lvl->meshlist;
+				lvl->meshlist = scn.meshlist;
+				scn.meshlist = 0;
+			}
 			destroy_scenefile(&scn);
 		}
 cont:	node = node->next;
@@ -78,9 +81,16 @@ cont:	node = node->next;
 
 void destroy_level(struct level *lvl)
 {
+	struct mesh *mesh;
+
 	free_bvh_tree(lvl->st_root);
 	free_bvh_tree(lvl->dyn_root);
-	free(lvl->mtls);
+
+	while(lvl->meshlist) {
+		mesh = lvl->meshlist;
+		lvl->meshlist = lvl->meshlist->next;
+		destroy_mesh(mesh);
+	}
 }
 
 
@@ -122,11 +132,11 @@ static void draw_level_rec(struct bvhnode *bn)
 	if(!bn) return;
 
 	if(bn->faces) {
-		tri = bn->faces;
-		curmtl = tri->mtl;
+		curmtl = bn->faces[0]->mtl;
 
 		glBegin(GL_TRIANGLES);
 		for(i=0; i<bn->num_faces; i++) {
+			tri = bn->faces[i];
 			if(tri->mtl != curmtl) {
 				glEnd();
 				color[0] = tri->mtl->color.x;
@@ -142,7 +152,6 @@ static void draw_level_rec(struct bvhnode *bn)
 				glTexCoord2fv(&tri->v[j].tex.x);
 				glVertex3fv(&tri->v[j].pos.x);
 			}
-			tri++;
 		}
 		glEnd();
 	}
@@ -157,49 +166,24 @@ void draw_level(struct level *lvl)
 	draw_level_rec(lvl->dyn_root);
 }
 
-static struct material *add_material(struct level *lvl, struct material *mtl)
-{
-	int i, newsz;
-	struct material *tmp;
-
-	for(i=0; i<lvl->num_mtls; i++) {
-		if(memcmp(lvl->mtls + i, mtl, sizeof *mtl) == 0) {
-			return lvl->mtls + i;
-		}
-	}
-
-	if(lvl->num_mtls >= lvl->max_mtls) {
-		newsz = lvl->max_mtls ? lvl->max_mtls * 2 : 16;
-		if(!(tmp = realloc(lvl->mtls, newsz * sizeof *lvl->mtls))) {
-			fprintf(stderr, "add_material: failed to resize materials array to %d\n", newsz);
-			return 0;
-		}
-		lvl->mtls = tmp;
-		lvl->max_mtls = newsz;
-	}
-	lvl->mtls[lvl->num_mtls] = *mtl;
-
-	return lvl->mtls + lvl->num_mtls++;
-}
-
-static int append_polygons(struct bvhnode *bnode, struct triangle *faces, int num_faces, struct material *mtl)
+static int add_mesh_faces(struct bvhnode *bnode, struct mesh *mesh)
 {
 	int i, j, newsz;
-	struct triangle *tri;
+	void *tmp;
+	struct triangle *tri, **triptr;
 
-	newsz = bnode->num_faces + num_faces;
-	if(!(tri = realloc(bnode->faces, newsz * sizeof *bnode->faces))) {
+	newsz = bnode->num_faces + mesh->num_faces;
+	if(!(tmp = realloc(bnode->faces, newsz * sizeof *bnode->faces))) {
 		fprintf(stderr, "append_polygons: failed to resize faces array to %d\n", newsz);
 		return -1;
 	}
-	bnode->faces = tri;
-	tri += bnode->num_faces;
+	bnode->faces = tmp;
+	triptr = bnode->faces + bnode->num_faces;
 	bnode->num_faces = newsz;
 
-	for(i=0; i<num_faces; i++) {
-		*tri = *faces++;
-		tri->mtl = mtl;
-
+	tri = mesh->faces;
+	for(i=0; i<mesh->num_faces; i++) {
+		*triptr++ = tri;
 		for(j=0; j<3; j++) {
 			cgm_vec3 *p = &tri->v[j].pos;
 			if(p->x < bnode->aabb.vmin.x) bnode->aabb.vmin.x = p->x;
diff --git a/src/level.h b/src/level.h
index 010e050..fad5463 100644
--- a/src/level.h
+++ b/src/level.h
@@ -8,8 +8,7 @@ struct level {
 	struct bvhnode *st_root;
 	struct bvhnode *dyn_root;
 
-	struct material *mtls;
-	int num_mtls, max_mtls;
+	struct mesh *meshlist;
 };
 
 int load_level(struct level *lvl, const char *fname);
diff --git a/src/main.c b/src/main.c
index 51faaa0..b3b96cc 100644
--- a/src/main.c
+++ b/src/main.c
@@ -46,8 +46,6 @@ static void mouse(int bn, int st, int x, int y);
 static void motion(int x, int y);
 static unsigned int nextpow2(unsigned int x);
 
-static long start_time;
-
 static float cam_theta, cam_phi;
 static cgm_vec3 cam_pos = {0, 1.6, 0};
 
@@ -69,6 +67,9 @@ static int tex_width, tex_height;
 static int tex_intfmt;
 static float tex_xform[16];
 
+static unsigned long nframes;
+static unsigned long start_time;
+
 
 int main(int argc, char **argv)
 {
@@ -98,6 +99,8 @@ int main(int argc, char **argv)
 	}
 	atexit(cleanup);
 
+	start_time = glutGet(GLUT_ELAPSED_TIME);
+
 	glutMainLoop();
 	return 0;
 }
@@ -122,13 +125,16 @@ static int init(void)
 	if(load_level(&lvl, "data/test.lvl") == -1) {
 		return -1;
 	}
-
-	start_time = glutGet(GLUT_ELAPSED_TIME);
 	return 0;
 }
 
 static void cleanup(void)
 {
+	float tsec;
+
+	tsec = (glutGet(GLUT_ELAPSED_TIME) - start_time) / 1000.0f;
+	printf("avg framerate: %.2f fps\n", (float)nframes / tsec);
+
 	destroy_level(&lvl);
 
 	glDeleteTextures(1, &tex);
@@ -140,7 +146,7 @@ static void cleanup(void)
 static void update(void)
 {
 	static unsigned int prev_upd;
-	unsigned int msec;
+	unsigned long msec;
 	float dt, vfwd, vright;
 
 	msec = glutGet(GLUT_ELAPSED_TIME) - start_time;
@@ -193,6 +199,8 @@ static void display(void)
 
 	glutSwapBuffers();
 	assert(glGetError() == GL_NO_ERROR);
+
+	nframes++;
 }
 
 static void idle(void)
diff --git a/src/mesh.c b/src/mesh.c
index 9f7aeec..483923d 100644
--- a/src/mesh.c
+++ b/src/mesh.c
@@ -201,8 +201,6 @@ int load_scenefile(struct scenefile *scn, const char *fname)
 		mesh->next = scn->meshlist;
 		scn->meshlist = mesh;
 		scn->num_meshes++;
-
-		printf("added mesh with mtl: %s\n", curmtl.name);
 	} else {
 		free(mesh);
 	}