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, float *totalmins, float *totalmaxs)
   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         float frontmins[3];
  25         float frontmaxs[3];
  26         float backmins[3];
  27         float backmaxs[3];
  28         // calculate bounds of children
  29         child = bih->leafs + leaflist[0];
  30         mins[0] = child->mins[0];
  31         mins[1] = child->mins[1];
  32         mins[2] = child->mins[2];
  33         maxs[0] = child->maxs[0];
  34         maxs[1] = child->maxs[1];
  35         maxs[2] = child->maxs[2];
  36         for (i = 1;i < numchildren;i++)
  37         {
  38                 child = bih->leafs + leaflist[i];
  39                 if (mins[0] > child->mins[0]) mins[0] = child->mins[0];
  40                 if (mins[1] > child->mins[1]) mins[1] = child->mins[1];
  41                 if (mins[2] > child->mins[2]) mins[2] = child->mins[2];
  42                 if (maxs[0] < child->maxs[0]) maxs[0] = child->maxs[0];
  43                 if (maxs[1] < child->maxs[1]) maxs[1] = child->maxs[1];
  44                 if (maxs[2] < child->maxs[2]) maxs[2] = child->maxs[2];
  45         }
  46         size[0] = maxs[0] - mins[0];
  47         size[1] = maxs[1] - mins[1];
  48         size[2] = maxs[2] - mins[2];
  49         // provide bounds to caller
  50         totalmins[0] = mins[0];
  51         totalmins[1] = mins[1];
  52         totalmins[2] = mins[2];
  53         totalmaxs[0] = maxs[0];
  54         totalmaxs[1] = maxs[1];
  55         totalmaxs[2] = maxs[2];
  56         // if there is only one child this is a leaf
  57         if (numchildren < 2)
  58                 return -1-leaflist[0];
  59         // if we run out of nodes it's the caller's fault, but don't crash
  60         if (bih->numnodes == bih->maxnodes)
  61         {
  62                 if (!bih->error)
  63                         bih->error = BIHERROR_OUT_OF_NODES;
  64                 return -1-leaflist[0];
  65         }
  66         nodenum = bih->numnodes++;
  67         node = bih->nodes + nodenum;
  68         // store bounds for node
  69         node->mins[0] = mins[0];
  70         node->mins[1] = mins[1];
  71         node->mins[2] = mins[2];
  72         node->maxs[0] = maxs[0];
  73         node->maxs[1] = maxs[1];
  74         node->maxs[2] = maxs[2];
  75         // pick longest axis
  76         longestaxis = 0;
  77         if (size[0] < size[1]) longestaxis = 1;
  78         if (size[longestaxis] < size[2]) longestaxis = 2;
  79         // iterate possible split axis choices, starting with the longest axis, if
  80         // all fail it means all children have the same bounds and we simply split
  81         // the list in half because each node can only have two children.
  82         for (j = 0;j < 3;j++)
  83         {
  84                 // pick an axis
  85                 axis = (longestaxis + j) % 3;
  86                 // sort children into front and back lists
  87                 splitdist = (node->mins[axis] + node->maxs[axis]) * 0.5f;
  88                 front = 0;
  89                 back = 0;
  90                 for (i = 0;i < numchildren;i++)
  91                 {
  92                         child = bih->leafs + leaflist[i];
  93                         d = (child->mins[axis] + child->maxs[axis]) * 0.5f;
  94                         if (d < splitdist)
  95                                 bih->leafsortscratch[back++] = leaflist[i];
  96                         else
  97                                 leaflist[front++] = leaflist[i];
  98                 }
  99                 // now copy the back ones into the space made in the leaflist for them
 100                 if (back)
 101                         memcpy(leaflist + front, bih->leafsortscratch, back*sizeof(leaflist[0]));
 102                 // if both sides have some children, it's good enough for us.
 103                 if (front && back)
 104                         break;
 105         }
 106         if (j == 3)
 107         {
 108                 // somewhat common case: no good choice, divide children arbitrarily
 109                 axis = 0;
 110                 back = numchildren >> 1;
 111                 front = numchildren - back;
 112         }
 113
 114         // we now have front and back children divided in leaflist...
 115         node->type = BIH_SPLITX + axis;
 116         node->front = BIH_BuildNode(bih, front, leaflist, frontmins, frontmaxs);
 117         node->frontmin = frontmins[axis];
 118         node->back = BIH_BuildNode(bih, back, leaflist + front, backmins, backmaxs);
 119         node->backmax = backmaxs[axis];
 120         return nodenum;
 121 }
 122
 123 int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch)
 124 {
 125         int i;
 126
 127         memset(bih, 0, sizeof(*bih));
 128         bih->numleafs = numleafs;
 129         bih->leafs = leafs;
 130         bih->leafsort = temp_leafsort;
 131         bih->leafsortscratch = temp_leafsortscratch;
 132         bih->numnodes = 0;
 133         bih->maxnodes = maxnodes;
 134         bih->nodes = nodes;
 135
 136         // clear things we intend to rebuild
 137         memset(bih->nodes, 0, sizeof(bih->nodes[0]) * bih->maxnodes);
 138         for (i = 0;i < bih->numleafs;i++)
 139                 bih->leafsort[i] = i;
 140
 141         bih->rootnode = BIH_BuildNode(bih, bih->numleafs, bih->leafsort, bih->mins, bih->maxs);
 142         return bih->error;
 143 }