From 60922e1e4f0c3aea28e8a1f03b65b8a5370d1473 Mon Sep 17 00:00:00 2001 From: John Tsiombikas Date: Wed, 23 Jun 2021 05:27:14 +0300 Subject: [PATCH] first pass at bvh construction (SAH), untested --- src/bvh.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++-------------- src/geom.c | 19 +++++++++++++++++ src/geom.h | 2 ++ 3 files changed, 73 insertions(+), 15 deletions(-) diff --git a/src/bvh.c b/src/bvh.c index af6ed45..d6d237e 100644 --- a/src/bvh.c +++ b/src/bvh.c @@ -1,22 +1,36 @@ +#include #include #include #include "bvh.h" #define SPLIT_BUCKETS 8 +static float eval_split_cost(struct bvhnode *node, float area, float sp, struct triangle **tribuf, int *part); + int build_bvh_sah(struct bvhnode *tree) { - int i, j, best; + int i, best; float sp, sp0, spgap, area, ext[3]; float spcost[SPLIT_BUCKETS]; int part[SPLIT_BUCKETS]; - struct triangle **tribuf, **src; + struct triangle **tribuf; + struct aabox *aabb = &tree->aabb; + + if(tree->left || tree->right) return 0; + + /* calculate the bounding box for this node */ + aabox_init(aabb); + for(i=0; inum_faces; i++) { + aabox_addface(aabb, tree->faces[i]); + } - if(tree->num_faces < 16 || tree->left || tree->right) return 0; + if(tree->num_faces < 16) { + 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; + ext[0] = aabb->vmax.x - aabb->vmin.x; + ext[1] = aabb->vmax.y - aabb->vmin.y; + ext[2] = aabb->vmax.z - aabb->vmin.z; if((area = surf_area(ext[0], ext[1], ext[2])) <= 0.0f) return 0; @@ -33,7 +47,7 @@ int build_bvh_sah(struct bvhnode *tree) for(i=0; inum_faces, part + i); + spcost[i] = eval_split_cost(tree, area, sp, tribuf + i * tree->num_faces, part + i); } best = 0; @@ -43,6 +57,12 @@ int build_bvh_sah(struct bvhnode *tree) } } + if(spcost[best] > tree->num_faces) { + /* the best split cost is worst than the no-split case */ + free(tribuf); + return 0; + } + /* found the best split, allocate child nodes, split the original array and copy * the pointers from tribuf to each part */ @@ -54,22 +74,28 @@ int build_bvh_sah(struct bvhnode *tree) } memcpy(tree->faces, tribuf + best * tree->num_faces, tree->num_faces * sizeof *tribuf); + free(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); + build_bvh_sah(tree->left); + build_bvh_sah(tree->right); + return 0; } -static float eval_cost(struct bvhnode *node, float area, float sp, struct triangle **tribuf, int *part) +static float eval_split_cost(struct bvhnode *node, float area, float sp, struct triangle **tribuf, int *part) { - int i; - float cost; + int i, nleft, nright; + float cost, sa_left, sa_right, cost_left, cost_right; struct triangle *tri; struct triangle **pleft, **pright; + struct aabox bbleft, bbright; + + aabox_init(&bbleft); + aabox_init(&bbright); /* partition on sp */ pleft = tribuf; @@ -77,16 +103,27 @@ static float eval_cost(struct bvhnode *node, float area, float sp, struct triang for(i=0; inum_faces; i++) { tri = node->faces[i]; - if(cgm_velem(tri->v, node->axis) < sp) { + if(cgm_velem(&tri->v[0].pos, node->axis) < sp) { + aabox_addface(&bbleft, tri); *pleft++ = tri; } else { + aabox_addface(&bbright, tri); *pright-- = tri; } } - /* TODO calc cost */ + nleft = pleft - tribuf; + nright = node->num_faces - nleft; + + sa_left = aabox_surf_area(&bbleft); + sa_right = aabox_surf_area(&bbright); + + /* intersection cost = 1, traversal cost = 0.2 * intesection cost */ + cost_left = sa_left * nleft; + cost_right = sa_right * nright; + cost = 0.2f + (cost_left + cost_right) / area; - *part = pleft - tribuf; + *part = nleft; return cost; } diff --git a/src/geom.c b/src/geom.c index 07f7a9b..a704bab 100644 --- a/src/geom.c +++ b/src/geom.c @@ -68,6 +68,25 @@ int ray_aabox_any(cgm_ray *ray, struct aabox *box, float tmax) return 1; } +void aabox_init(struct aabox *box) +{ + box->vmin.x = box->vmin.y = box->vmin.z = FLT_MAX; + box->vmax.x = box->vmax.y = box->vmax.z = -FLT_MAX; +} + +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; + } +} + 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; diff --git a/src/geom.h b/src/geom.h index 2233c67..b0fbb1d 100644 --- a/src/geom.h +++ b/src/geom.h @@ -30,6 +30,8 @@ struct rayhit { 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); +void aabox_init(struct aabox *box); +void aabox_addface(struct aabox *box, struct triangle *tri); 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); -- 1.7.10.4