bih.c

   1
   2 // This code written in 2010 by Forest Hale (lordhavoc ghdigital com), and placed into public domain.
   3
   4 #include <stdlib.h>
   5 #include <memory.h>
   6 #include "bih.h"
   7
   8 static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist)
   9 {
  10         int i;
  11         int j;
  12         int longestaxis;
  13         int axis;
  14         int nodenum;
  15         int front;
  16         int back;
  17         bih_node_t *node;
  18         bih_leaf_t *child;
  19         float splitdist;
  20         float d;
  21         float mins[3];
  22         float maxs[3];
  23         float size[3];
  24         if (numchildren < 2)
  25                 return -1-leaflist[0];
  26         // if we run out of nodes it's the caller's fault, but don't crash
  27         if (bih->numnodes == bih->maxnodes)
  28         {
  29                 if (!bih->error)
  30                         bih->error = BIHERROR_OUT_OF_NODES;
  31                 return -1-leaflist[0];
  32         }
  33         nodenum = bih->numnodes++;
  34         node = bih->nodes + nodenum;
  35         // calculate bounds of children
  36         child = bih->leafs + leaflist[0];
  37         mins[0] = child->mins[0];
  38         mins[1] = child->mins[1];
  39         mins[2] = child->mins[2];
  40         maxs[0] = child->maxs[0];
  41         maxs[1] = child->maxs[1];
  42         maxs[2] = child->maxs[2];
  43         for (i = 1;i < numchildren;i++)
  44         {
  45                 child = bih->leafs + leaflist[i];
  46                 if (mins[0] > child->mins[0]) mins[0] = child->mins[0];
  47                 if (mins[1] > child->mins[1]) mins[1] = child->mins[1];
  48                 if (mins[2] > child->mins[2]) mins[2] = child->mins[2];
  49                 if (maxs[0] < child->maxs[0]) maxs[0] = child->maxs[0];
  50                 if (maxs[1] < child->maxs[1]) maxs[1] = child->maxs[1];
  51                 if (maxs[2] < child->maxs[2]) maxs[2] = child->maxs[2];
  52         }
  53         size[0] = maxs[0] - mins[0];
  54         size[1] = maxs[1] - mins[1];
  55         size[2] = maxs[2] - mins[2];
  56         // store bounds for node
  57         node->mins[0] = mins[0];
  58         node->mins[1] = mins[1];
  59         node->mins[2] = mins[2];
  60         node->maxs[0] = maxs[0];
  61         node->maxs[1] = maxs[1];
  62         node->maxs[2] = maxs[2];
  63         // pick longest axis
  64         longestaxis = 0;
  65         if (size[0] < size[1]) longestaxis = 1;
  66         if (size[longestaxis] < size[2]) longestaxis = 2;
  67         // iterate possible split axis choices:
  68         // longest (best raytracing performance)
  69         // x (longest had identical children, try X axis)
  70         // y (longest and X axis had identical children, try Y axis)
  71         // z (longest and X and Y axes had identical children, try Z axis)
  72         // arbitrary (all children have same bounds, divide the list)
  73         for (j = 0;j < 3;j++)
  74         {
  75                 // if longest axis fails, we try each one until something works
  76                 // (this also can fail, see below)
  77                 switch(j)
  78                 {
  79                 default:
  80                 case 0: axis = longestaxis;break;
  81                 case 1: axis = (longestaxis + 1) % 3;break;
  82                 case 2: axis = (longestaxis + 2) % 3;break;
  83                 }
  84                 // sort children into front and back lists
  85                 node->type = BIH_SPLITX + axis;
  86                 splitdist = (node->mins[axis] + node->maxs[axis]) * 0.5f;
  87                 front = 0;
  88                 back = 0;
  89                 for (i = 0;i < numchildren;i++)
  90                 {
  91                         child = bih->leafs + leaflist[i];
  92                         d = (child->mins[axis] + child->maxs[axis]) * 0.5f;
  93                         if (d < splitdist)
  94                                 bih->leafsortscratch[back++] = leaflist[i];
  95                         else
  96                                 leaflist[front++] = leaflist[i];
  97                 }
  98                 // now copy the back ones into the space made in the leaflist for them
  99                 if (back)
 100                         memcpy(leaflist + front, bih->leafsortscratch, back*sizeof(leaflist[0]));
 101                 // if both sides have some children, it's good enough for us.
 102                 if (front && back)
 103                         break;
 104         }
 105         if (j == 3)
 106         {
 107                 // the almost impossible case happened; all children have identical
 108                 // bounds, so just divide them arbitrarily into two lists.
 109                 node->type = BIH_SPLITX;
 110                 back = numchildren >> 1;
 111                 front = numchildren - back;
 112         }
 113
 114         // we now have front and back children divided in leaflist...
 115         node->children[0] = BIH_BuildNode(bih, front, leaflist);
 116         node->children[1] = BIH_BuildNode(bih, back, leaflist + front);
 117         return nodenum;
 118 }
 119
 120 int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch)
 121 {
 122         int i;
 123
 124         memset(bih, 0, sizeof(*bih));
 125         bih->numleafs = numleafs;
 126         bih->leafs = leafs;
 127         bih->leafsort = temp_leafsort;
 128         bih->leafsortscratch = temp_leafsortscratch;
 129         bih->numnodes = 0;
 130         bih->maxnodes = maxnodes;
 131         bih->nodes = nodes;
 132
 133         // clear things we intend to rebuild
 134         memset(bih->nodes, 0, sizeof(bih->nodes[0]) * bih->maxnodes);
 135         for (i = 0;i < bih->numleafs;i++)
 136                 bih->leafsort[i] = i;
 137
 138         BIH_BuildNode(bih, bih->numleafs, bih->leafsort);
 139         return bih->error;
 140 }