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

   1 #include <stdlib.h>
   2 #include <float.h>
   3 #include "bvh.h"
   4
   5 #define SPLIT_BUCKETS   8
   6
   7 int build_bvh_sah(struct bvhnode *tree)
   8 {
   9         int i, j, best;
  10         float sp, sp0, spgap, area, ext[3];
  11         float spcost[SPLIT_BUCKETS];
  12         int part[SPLIT_BUCKETS];
  13         struct triangle **tribuf, **src;
  14
  15         if(tree->num_faces < 16 || tree->left || tree->right) return 0;
  16
  17         ext[0] = tree->aabb.vmax.x - tree->aabb.vmin.x;
  18         ext[1] = tree->aabb.vmax.y - tree->aabb.vmin.y;
  19         ext[2] = tree->aabb.vmax.z - tree->aabb.vmin.z;
  20
  21         if((area = surf_area(ext[0], ext[1], ext[2])) <= 0.0f) return 0;
  22
  23         tree->axis = ext[0] > ext[1] ? (ext[0] > ext[2] ? 0 : 2) : (ext[1] > ext[2] ? 1 : 2);
  24
  25         spgap = ext[tree->axis] / SPLIT_BUCKETS;
  26         sp0 = cgm_velem(&tree->aabb.vmin, tree->axis) + spgap / 2.0f;
  27
  28         /* allocate N arrays worth of triangle pointers, one for each bucket */
  29         if(!(tribuf = malloc(tree->num_faces * SPLIT_BUCKETS * sizeof *tribuf))) {
  30                 fprintf(stderr, "failed to allocate buffer for BVH construction\n");
  31                 return -1;
  32         }
  33
  34         for(i=0; i<SPLIT_BUCKETS; i++) {
  35                 sp = sp0 + i * spgap;
  36                 spcost[i] = eval_cost(tree, area, sp, tribuf + i * tree->num_faces, part + i);
  37         }
  38
  39         best = 0;
  40         for(i=1; i<SPLIT_BUCKETS; i++) {
  41                 if(spcost[i] < spcost[best]) {
  42                         best = i;
  43                 }
  44         }
  45
  46         /* found the best split, allocate child nodes, split the original array and copy
  47          * the pointers from tribuf to each part
  48          */
  49         if(!(tree->left = calloc(1, sizeof *tree->left)) || !(tree->right = calloc(1, sizeof *tree->right))) {
  50                 fprintf(stderr, "failed to allocate tree nodes during BVH construction\n");
  51                 free(tree->left);
  52                 free(tribuf);
  53                 return -1;
  54         }
  55
  56         memcpy(tree->faces, tribuf + best * tree->num_faces, tree->num_faces * sizeof *tribuf);
  57
  58         tree->left->faces = tree->faces;
  59         tree->left->num_faces = part[best];
  60         tree->right->faces = tree->faces + part[best];
  61         tree->right->num_faces = tree->faces - tree->left->faces;
  62
  63         /* TODO: calc aabox for each child node */
  64         free(tribuf);
  65 }
  66
  67 static float eval_cost(struct bvhnode *node, float area, float sp, struct triangle **tribuf, int *part)
  68 {
  69         int i;
  70         float cost;
  71         struct triangle *tri;
  72         struct triangle **pleft, **pright;
  73
  74         /* partition on sp */
  75         pleft = tribuf;
  76         pright = tribuf + node->num_faces - 1;
  77
  78         for(i=0; i<node->num_faces; i++) {
  79                 tri = node->faces[i];
  80                 if(cgm_velem(tri->v, node->axis) < sp) {
  81                         *pleft++ = tri;
  82                 } else {
  83                         *pright-- = tri;
  84                 }
  85         }
  86
  87         /* TODO calc cost */
  88
  89         *part = pleft - tribuf;
  90         return cost;
  91 }
  92
  93 void free_bvh_tree(struct bvhnode *tree)
  94 {
  95         if(!tree) return;
  96
  97         if(tree->max_faces) {
  98                 /* only nodes with max_faces != 0 have ownership of the faces array. all
  99                  * the rest of the nodes only have pointers in the same array belonging
 100                  * to an ancestor node
 101                  */
 102                 free(tree->faces);
 103         }
 104         free_bvh_tree(tree->left);
 105         free_bvh_tree(tree->right);
 106         free(tree);
 107 }
 108
 109 int ray_bvhnode(cgm_ray *ray, struct bvhnode *bn, float tmax, struct rayhit *hit)
 110 {
 111         int i, res = 0;
 112         struct rayhit hit0;
 113
 114         if(!ray_aabox_any(ray, &bn->aabb, tmax)) {
 115                 return 0;
 116         }
 117
 118         if(!hit) {
 119                 for(i=0; i<bn->num_faces; i++) {
 120                         if(ray_triangle(ray, bn->faces[i], tmax, 0)) {
 121                                 return 1;
 122                         }
 123                 }
 124                 return 0;
 125         }
 126
 127         hit0.t = FLT_MAX;
 128         for(i=0; i<bn->num_faces; i++) {
 129                 if(ray_triangle(ray, bn->faces[i], tmax, hit) && hit->t < hit0.t) {
 130                         hit0 = *hit;
 131                         res = 1;
 132                 }
 133         }
 134         *hit = hit0;
 135         return res;
 136 }