#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);
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;
}
}
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;
}
struct aabox aabb;
int axis;
- struct triangle *faces;
+ struct triangle **faces;
int num_faces, max_faces;
struct bvhnode *left, *right;
#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)
{
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)) ||
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;
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);
+ }
}
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;
glTexCoord2fv(&tri->v[j].tex.x);
glVertex3fv(&tri->v[j].pos.x);
}
- tri++;
}
glEnd();
}
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;
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);
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};
static int tex_intfmt;
static float tex_xform[16];
+static unsigned long nframes;
+static unsigned long start_time;
+
int main(int argc, char **argv)
{
}
atexit(cleanup);
+ start_time = glutGet(GLUT_ELAPSED_TIME);
+
glutMainLoop();
return 0;
}
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);
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;
glutSwapBuffers();
assert(glGetError() == GL_NO_ERROR);
+
+ nframes++;
}
static void idle(void)
mesh->next = scn->meshlist;
scn->meshlist = mesh;
scn->num_meshes++;
-
- printf("added mesh with mtl: %s\n", curmtl.name);
} else {
free(mesh);
}
projects / cyberay / commitdiff