first pass at bvh construction (SAH), untested

[cyberay] / src / geom.c

diff --git a/src/geom.c b/src/geom.c
index ba61e87..a704bab 100644 (file)
--- a/src/geom.c
+++ b/src/geom.c
@@ -1,26 +1,10 @@
 #include <float.h>
 #include "geom.h"
 
-void free_bvh_tree(struct bvhnode *tree)
-{
-       struct bvhnode *node, *tmp;
-
-       free(tree->faces);
-
-       node = tree->sub;
-       while(node) {
-               tmp = node;
-               node = node->next;
-               free_bvh_tree(tmp);
-       }
-
-       free(tree);
-}
-
 int ray_triangle(cgm_ray *ray, struct triangle *tri, float tmax, struct rayhit *hit)
 {
        float t, ndotdir;
-       cgm_vec3 vdir, bc;
+       cgm_vec3 vdir, bc, pos;
 
        if(fabs(ndotdir = cgm_vdot(&ray->dir, &tri->norm)) <= 1e-6) {
                return 0;
@@ -29,17 +13,23 @@ int ray_triangle(cgm_ray *ray, struct triangle *tri, float tmax, struct rayhit *
        vdir = tri->v[0].pos;
        cgm_vsub(&vdir, &ray->origin);
 
-       if((t = cgm_vdot(&ray->dir, &vdir) / ndotdir) <= 1e-6 || t > tmax) {
+       if((t = cgm_vdot(&tri->norm, &vdir) / ndotdir) <= 1e-6 || t > tmax) {
                return 0;
        }
 
+       cgm_raypos(&pos, ray, t);
+       cgm_bary(&bc, &tri->v[0].pos, &tri->v[1].pos, &tri->v[2].pos, &pos);
+
+       if(bc.x < 0.0f || bc.x > 1.0f) return 0;
+       if(bc.y < 0.0f || bc.y > 1.0f) return 0;
+       if(bc.z < 0.0f || bc.z > 1.0f) return 0;
+
        if(hit) {
                hit->t = t;
                hit->ray = *ray;
                hit->mtl = tri->mtl;
 
-               cgm_raypos(&hit->v.pos, ray, t);
-               cgm_bary(&bc, &tri->v[0].pos, &tri->v[1].pos, &tri->v[2].pos, &hit->v.pos);
+               hit->v.pos = pos;
 
                hit->v.norm.x = tri->v[0].norm.x * bc.x + tri->v[1].norm.x * bc.y + tri->v[2].norm.x * bc.z;
                hit->v.norm.y = tri->v[0].norm.y * bc.x + tri->v[1].norm.y * bc.y + tri->v[2].norm.y * bc.z;
@@ -78,31 +68,50 @@ int ray_aabox_any(cgm_ray *ray, struct aabox *box, float tmax)
        return 1;
 }
 
-int ray_bvhnode(cgm_ray *ray, struct bvhnode *bn, float tmax, struct rayhit *hit)
+void aabox_init(struct aabox *box)
 {
-       int i, res = 0;
-       struct rayhit hit0;
+       box->vmin.x = box->vmin.y = box->vmin.z = FLT_MAX;
+       box->vmax.x = box->vmax.y = box->vmax.z = -FLT_MAX;
+}
 
-       if(!ray_aabox_any(ray, &bn->aabb, tmax)) {
-               return 0;
+void aabox_addface(struct aabox *box, struct triangle *tri)
+{
+       int i;
+       for(i=0; i<3; i++) {
+               if(tri->v[i].pos.x < box->vmin.x) box->vmin.x = tri->v[i].pos.x;
+               if(tri->v[i].pos.x > box->vmax.x) box->vmax.x = tri->v[i].pos.x;
+               if(tri->v[i].pos.y < box->vmin.y) box->vmin.y = tri->v[i].pos.y;
+               if(tri->v[i].pos.y > box->vmax.y) box->vmax.y = tri->v[i].pos.y;
+               if(tri->v[i].pos.z < box->vmin.z) box->vmin.z = tri->v[i].pos.z;
+               if(tri->v[i].pos.z > box->vmax.z) box->vmax.z = tri->v[i].pos.z;
        }
+}
 
-       if(!hit) {
-               for(i=0; i<bn->num_faces; i++) {
-                       if(ray_triangle(ray, bn->faces + i, tmax, 0)) {
-                               return 1;
-                       }
-               }
-               return 0;
-       }
+void aabox_union(struct aabox *res, struct aabox *a, struct aabox *b)
+{
+       res->vmin.x = a->vmin.x < b->vmin.x ? a->vmin.x : b->vmin.x;
+       res->vmax.x = a->vmax.x > b->vmax.x ? a->vmax.x : b->vmax.x;
+       res->vmin.y = a->vmin.y < b->vmin.y ? a->vmin.y : b->vmin.y;
+       res->vmax.y = a->vmax.y > b->vmax.y ? a->vmax.y : b->vmax.y;
+       res->vmin.z = a->vmin.z < b->vmin.z ? a->vmin.z : b->vmin.z;
+       res->vmax.z = a->vmax.z > b->vmax.z ? a->vmax.z : b->vmax.z;
+}
 
-       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) {
-                       hit0 = *hit;
-                       res = 1;
-               }
+float aabox_surf_area(struct aabox *box)
+{
+       float dx, dy, dz;
+
+       dx = box->vmax.x - box->vmin.x;
+       dy = box->vmax.y - box->vmin.y;
+       dz = box->vmax.z - box->vmin.z;
+
+       return surf_area(dx, dy, dz);
+}
+
+float surf_area(float dx, float dy, float dz)
+{
+       if(dx <= 0 || dy <= 0 || dz <= 0) {
+               return 0.0f;
        }
-       *hit = hit0;
-       return res;
+       return (dx * dy + dx * dz + dy * dz) * 2.0f;
 }