From 68f8983b5a92709e92355c2d6e756890b4348319 Mon Sep 17 00:00:00 2001 From: John Tsiombikas Date: Tue, 22 Jun 2021 05:47:39 +0300 Subject: [PATCH] started on the BVH build --- src/bvh.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/bvh.h | 24 ++++++++++++++++++++++++ src/geom.c | 55 ++++++++++++++++++++++--------------------------------- src/geom.h | 16 ++++------------ src/level.h | 2 +- 5 files changed, 109 insertions(+), 46 deletions(-) create mode 100644 src/bvh.c create mode 100644 src/bvh.h diff --git a/src/bvh.c b/src/bvh.c new file mode 100644 index 0000000..dced9d9 --- /dev/null +++ b/src/bvh.c @@ -0,0 +1,58 @@ +#include +#include +#include "bvh.h" + +int build_bvh_sah(struct bvhnode *tree) +{ + int i, j; + float sarea; + + if(tree->num_faces < 5 || tree->left || tree->right) return 0; + + 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; + + if((sarea = surf_area(dx, dy, dz)) <= 0.0f) return 0; + + tree->axis = dx > dy ? (dx > dz ? dx : dz) : (dy > dz ? dy : dz); + + /* TODO */ +} + +void free_bvh_tree(struct bvhnode *tree) +{ + free(tree->faces); + free_bvh_tree(tree->left); + free_bvh_tree(tree->right); + free(tree); +} + +int ray_bvhnode(cgm_ray *ray, struct bvhnode *bn, float tmax, struct rayhit *hit) +{ + int i, res = 0; + struct rayhit hit0; + + if(!ray_aabox_any(ray, &bn->aabb, tmax)) { + return 0; + } + + if(!hit) { + for(i=0; inum_faces; i++) { + if(ray_triangle(ray, bn->faces + i, tmax, 0)) { + return 1; + } + } + return 0; + } + + hit0.t = FLT_MAX; + for(i=0; inum_faces; i++) { + if(ray_triangle(ray, bn->faces + i, tmax, hit) && hit->t < hit0.t) { + hit0 = *hit; + res = 1; + } + } + *hit = hit0; + return res; +} diff --git a/src/bvh.h b/src/bvh.h new file mode 100644 index 0000000..03bc726 --- /dev/null +++ b/src/bvh.h @@ -0,0 +1,24 @@ +#ifndef BVH_H_ +#define BVH_H_ + +#include "geom.h" + +struct bvhnode { + struct aabox aabb; + int axis; + + struct triangle *faces; + int num_faces, max_faces; + + struct bvhnode *left, *right; +}; + +/* build_bvh* needs to be called with a pointer to a single-node tree, + * containing all the faces, left/right as null, and a pre-computed aabb + */ +int build_bvh_sah(struct bvhnode *tree); +void free_bvh_tree(struct bvhnode *tree); + +int ray_bvhnode(cgm_ray *ray, struct bvhnode *bn, float tmax, struct rayhit *hit); + +#endif /* BVH_H_ */ diff --git a/src/geom.c b/src/geom.c index ef15156..07f7a9b 100644 --- a/src/geom.c +++ b/src/geom.c @@ -1,17 +1,6 @@ #include #include "geom.h" -void free_bvh_tree(struct bvhnode *tree) -{ - struct bvhnode *node, *tmp; - - free(tree->faces); - - free_bvh_tree(tree->left); - free_bvh_tree(tree->right); - free(tree); -} - int ray_triangle(cgm_ray *ray, struct triangle *tri, float tmax, struct rayhit *hit) { float t, ndotdir; @@ -79,31 +68,31 @@ 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_union(struct aabox *res, struct aabox *a, struct aabox *b) { - int i, res = 0; - struct rayhit hit0; + 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; +} - if(!ray_aabox_any(ray, &bn->aabb, tmax)) { - return 0; - } +float aabox_surf_area(struct aabox *box) +{ + float dx, dy, dz; - if(!hit) { - for(i=0; inum_faces; i++) { - if(ray_triangle(ray, bn->faces + i, tmax, 0)) { - return 1; - } - } - return 0; - } + dx = box->vmax.x - box->vmin.x; + dy = box->vmax.y - box->vmin.y; + dz = box->vmax.z - box->vmin.z; - hit0.t = FLT_MAX; - for(i=0; inum_faces; i++) { - if(ray_triangle(ray, bn->faces + i, tmax, hit) && hit->t < hit0.t) { - hit0 = *hit; - res = 1; - } + 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; } diff --git a/src/geom.h b/src/geom.h index 7f71094..2233c67 100644 --- a/src/geom.h +++ b/src/geom.h @@ -20,15 +20,6 @@ struct aabox { cgm_vec3 vmin, vmax; }; -struct bvhnode { - struct aabox aabb; - - struct triangle *faces; - int num_faces; - - struct bvhnode *left, *right; -}; - struct rayhit { float t; struct vertex v; @@ -36,10 +27,11 @@ struct rayhit { struct material *mtl; }; -void free_bvh_tree(struct bvhnode *tree); - int ray_triangle(cgm_ray *ray, struct triangle *tri, float tmax, struct rayhit *hit); int ray_aabox_any(cgm_ray *ray, struct aabox *box, float tmax); -int ray_bvhnode(cgm_ray *ray, struct bvhnode *bn, float tmax, struct rayhit *hit); + +void aabox_union(struct aabox *res, struct aabox *a, struct aabox *b); +float aabox_surf_area(struct aabox *box); +float surf_area(float dx, float dy, float dz); #endif /* GEOM_H_ */ diff --git a/src/level.h b/src/level.h index c65fc2d..010e050 100644 --- a/src/level.h +++ b/src/level.h @@ -2,7 +2,7 @@ #define LEVEL_H_ #include "rt.h" -#include "geom.h" +#include "bvh.h" struct level { struct bvhnode *st_root; -- 1.7.10.4