6 #define SPLIT_BUCKETS 8
8 static float eval_split_cost(struct bvhnode *node, float area, float sp, struct triangle **tribuf, int *part);
10 int build_bvh_sah(struct bvhnode *tree)
13 float sp, sp0, spgap, area, ext[3];
14 float spcost[SPLIT_BUCKETS];
15 int part[SPLIT_BUCKETS];
16 struct triangle **tribuf;
17 struct aabox *aabb = &tree->aabb;
19 if(tree->left || tree->right) return 0;
21 /* calculate the bounding box for this node */
23 for(i=0; i<tree->num_faces; i++) {
24 aabox_addface(aabb, tree->faces[i]);
27 if(tree->num_faces < 16) {
31 ext[0] = aabb->vmax.x - aabb->vmin.x;
32 ext[1] = aabb->vmax.y - aabb->vmin.y;
33 ext[2] = aabb->vmax.z - aabb->vmin.z;
35 if((area = surf_area(ext[0], ext[1], ext[2])) <= 0.0f) return 0;
37 tree->axis = ext[0] > ext[1] ? (ext[0] > ext[2] ? 0 : 2) : (ext[1] > ext[2] ? 1 : 2);
39 spgap = ext[tree->axis] / SPLIT_BUCKETS;
40 sp0 = cgm_velem(&tree->aabb.vmin, tree->axis) + spgap / 2.0f;
42 /* allocate N arrays worth of triangle pointers, one for each bucket */
43 if(!(tribuf = malloc(tree->num_faces * SPLIT_BUCKETS * sizeof *tribuf))) {
44 fprintf(stderr, "failed to allocate buffer for BVH construction\n");
48 for(i=0; i<SPLIT_BUCKETS; i++) {
50 spcost[i] = eval_split_cost(tree, area, sp, tribuf + i * tree->num_faces, part + i);
54 for(i=1; i<SPLIT_BUCKETS; i++) {
55 if(spcost[i] < spcost[best]) {
60 if(spcost[best] > tree->num_faces) {
61 /* the best split cost is worst than the no-split case */
66 /* found the best split, allocate child nodes, split the original array and copy
67 * the pointers from tribuf to each part
69 if(!(tree->left = calloc(1, sizeof *tree->left)) || !(tree->right = calloc(1, sizeof *tree->right))) {
70 fprintf(stderr, "failed to allocate tree nodes during BVH construction\n");
76 memcpy(tree->faces, tribuf + best * tree->num_faces, tree->num_faces * sizeof *tribuf);
79 tree->left->faces = tree->faces;
80 tree->left->num_faces = part[best];
81 tree->right->faces = tree->faces + part[best];
82 tree->right->num_faces = tree->faces - tree->left->faces;
84 build_bvh_sah(tree->left);
85 build_bvh_sah(tree->right);
89 static float eval_split_cost(struct bvhnode *node, float area, float sp, struct triangle **tribuf, int *part)
92 float cost, sa_left, sa_right, cost_left, cost_right;
94 struct triangle **pleft, **pright;
95 struct aabox bbleft, bbright;
100 /* partition on sp */
102 pright = tribuf + node->num_faces - 1;
104 for(i=0; i<node->num_faces; i++) {
105 tri = node->faces[i];
106 if(cgm_velem(&tri->v[0].pos, node->axis) < sp) {
107 aabox_addface(&bbleft, tri);
110 aabox_addface(&bbright, tri);
115 nleft = pleft - tribuf;
116 nright = node->num_faces - nleft;
118 sa_left = aabox_surf_area(&bbleft);
119 sa_right = aabox_surf_area(&bbright);
121 /* intersection cost = 1, traversal cost = 0.2 * intesection cost */
122 cost_left = sa_left * nleft;
123 cost_right = sa_right * nright;
124 cost = 0.2f + (cost_left + cost_right) / area;
130 void free_bvh_tree(struct bvhnode *tree)
134 if(tree->max_faces) {
135 /* only nodes with max_faces != 0 have ownership of the faces array. all
136 * the rest of the nodes only have pointers in the same array belonging
137 * to an ancestor node
141 free_bvh_tree(tree->left);
142 free_bvh_tree(tree->right);
146 int ray_bvhnode(cgm_ray *ray, struct bvhnode *bn, float tmax, struct rayhit *hit)
151 if(!ray_aabox_any(ray, &bn->aabb, tmax)) {
156 for(i=0; i<bn->num_faces; i++) {
157 if(ray_triangle(ray, bn->faces[i], tmax, 0)) {
165 for(i=0; i<bn->num_faces; i++) {
166 if(ray_triangle(ray, bn->faces[i], tmax, hit) && hit->t < hit0.t) {