git.mutantstargoat.com Git - cyberay/blob - src/bvh.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <float.h>
   4 #include "bvh.h"
   5
   6 #define SPLIT_BUCKETS   8
   7
   8 static float eval_split_cost(struct bvhnode *node, float area, float sp, struct triangle **tribuf, int *part);
   9
  10 int build_bvh_sah(struct bvhnode *tree)
  11 {
  12         int i, best;
  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;
  18
  19         if(tree->left || tree->right) return 0;
  20
  21         /* calculate the bounding box for this node */
  22         aabox_init(aabb);
  23         for(i=0; i<tree->num_faces; i++) {
  24                 aabox_addface(aabb, tree->faces[i]);
  25         }
  26
  27         if(tree->num_faces < 16) {
  28                 return 0;
  29         }
  30
  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;
  34
  35         if((area = surf_area(ext[0], ext[1], ext[2])) <= 0.0f) return 0;
  36
  37         tree->axis = ext[0] > ext[1] ? (ext[0] > ext[2] ? 0 : 2) : (ext[1] > ext[2] ? 1 : 2);
  38
  39         spgap = ext[tree->axis] / SPLIT_BUCKETS;
  40         sp0 = cgm_velem(&tree->aabb.vmin, tree->axis) + spgap / 2.0f;
  41
  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");
  45                 return -1;
  46         }
  47
  48         for(i=0; i<SPLIT_BUCKETS; i++) {
  49                 sp = sp0 + i * spgap;
  50                 spcost[i] = eval_split_cost(tree, area, sp, tribuf + i * tree->num_faces, part + i);
  51         }
  52
  53         best = 0;
  54         for(i=1; i<SPLIT_BUCKETS; i++) {
  55                 if(spcost[i] < spcost[best]) {
  56                         best = i;
  57                 }
  58         }
  59
  60         if(spcost[best] > tree->num_faces) {
  61                 /* the best split cost is worst than the no-split case */
  62                 free(tribuf);
  63                 return 0;
  64         }
  65
  66         /* found the best split, allocate child nodes, split the original array and copy
  67          * the pointers from tribuf to each part
  68          */
  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");
  71                 free(tree->left);
  72                 free(tribuf);
  73                 return -1;
  74         }
  75
  76         memcpy(tree->faces, tribuf + best * tree->num_faces, tree->num_faces * sizeof *tribuf);
  77         free(tribuf);
  78
  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;
  83
  84         build_bvh_sah(tree->left);
  85         build_bvh_sah(tree->right);
  86         return 0;
  87 }
  88
  89 static float eval_split_cost(struct bvhnode *node, float area, float sp, struct triangle **tribuf, int *part)
  90 {
  91         int i, nleft, nright;
  92         float cost, sa_left, sa_right, cost_left, cost_right;
  93         struct triangle *tri;
  94         struct triangle **pleft, **pright;
  95         struct aabox bbleft, bbright;
  96
  97         aabox_init(&bbleft);
  98         aabox_init(&bbright);
  99
 100         /* partition on sp */
 101         pleft = tribuf;
 102         pright = tribuf + node->num_faces - 1;
 103
 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);
 108                         *pleft++ = tri;
 109                 } else {
 110                         aabox_addface(&bbright, tri);
 111                         *pright-- = tri;
 112                 }
 113         }
 114
 115         nleft = pleft - tribuf;
 116         nright = node->num_faces - nleft;
 117
 118         sa_left = aabox_surf_area(&bbleft);
 119         sa_right = aabox_surf_area(&bbright);
 120
 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;
 125
 126         *part = nleft;
 127         return cost;
 128 }
 129
 130 void free_bvh_tree(struct bvhnode *tree)
 131 {
 132         if(!tree) return;
 133
 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
 138                  */
 139                 free(tree->faces);
 140         }
 141         free_bvh_tree(tree->left);
 142         free_bvh_tree(tree->right);
 143         free(tree);
 144 }
 145
 146 int ray_bvhnode(cgm_ray *ray, struct bvhnode *bn, float tmax, struct rayhit *hit)
 147 {
 148         int i, res = 0;
 149         struct rayhit hit0;
 150
 151         if(!ray_aabox_any(ray, &bn->aabb, tmax)) {
 152                 return 0;
 153         }
 154
 155         if(!hit) {
 156                 for(i=0; i<bn->num_faces; i++) {
 157                         if(ray_triangle(ray, bn->faces[i], tmax, 0)) {
 158                                 return 1;
 159                         }
 160                 }
 161                 return 0;
 162         }
 163
 164         hit0.t = FLT_MAX;
 165         for(i=0; i<bn->num_faces; i++) {
 166                 if(ray_triangle(ray, bn->faces[i], tmax, hit) && hit->t < hit0.t) {
 167                         hit0 = *hit;
 168                         res = 1;
 169                 }
 170         }
 171         *hit = hit0;
 172         return res;
 173 }