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 <string.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 = 0;
  14         int nodenum;
  15         int front = 0;
  16         int back = 0;
  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         node->front = 0;
  76         node->back = 0;
  77         node->frontmin = 0;
  78         node->backmax = 0;
  79         memset(node->children, -1, sizeof(node->children));
  80         // check if this should be an unordered node to reduce recursion depth
  81         if (numchildren <= bih->maxchildrenunordered)
  82         {
  83                 node->type = BIH_UNORDERED;
  84                 for (j = 0;j < numchildren;j++)
  85                         node->children[j] = leaflist[j];
  86                 return nodenum;
  87         }
  88         // pick longest axis
  89         longestaxis = 0;
  90         if (size[0] < size[1]) longestaxis = 1;
  91         if (size[longestaxis] < size[2]) longestaxis = 2;
  92         // iterate possible split axis choices, starting with the longest axis, if
  93         // all fail it means all children have the same bounds and we simply split
  94         // the list in half because each node can only have two children.
  95         for (j = 0;j < 3;j++)
  96         {
  97                 // pick an axis
  98                 axis = (longestaxis + j) % 3;
  99                 // sort children into front and back lists
 100                 splitdist = (node->mins[axis] + node->maxs[axis]) * 0.5f;
 101                 front = 0;
 102                 back = 0;
 103                 for (i = 0;i < numchildren;i++)
 104                 {
 105                         child = bih->leafs + leaflist[i];
 106                         d = (child->mins[axis] + child->maxs[axis]) * 0.5f;
 107                         if (d < splitdist)
 108                                 bih->leafsortscratch[back++] = leaflist[i];
 109                         else
 110                                 leaflist[front++] = leaflist[i];
 111                 }
 112                 // now copy the back ones into the space made in the leaflist for them
 113                 if (back)
 114                         memcpy(leaflist + front, bih->leafsortscratch, back*sizeof(leaflist[0]));
 115                 // if both sides have some children, it's good enough for us.
 116                 if (front && back)
 117                         break;
 118         }
 119         if (j == 3)
 120         {
 121                 // somewhat common case: no good choice, divide children arbitrarily
 122                 axis = 0;
 123                 back = numchildren >> 1;
 124                 front = numchildren - back;
 125         }
 126
 127         // we now have front and back children divided in leaflist...
 128         node->type = (bih_nodetype_t)((int)BIH_SPLITX + axis);
 129         node->front = BIH_BuildNode(bih, front, leaflist, frontmins, frontmaxs);
 130         node->frontmin = frontmins[axis];
 131         node->back = BIH_BuildNode(bih, back, leaflist + front, backmins, backmaxs);
 132         node->backmax = backmaxs[axis];
 133         return nodenum;
 134 }
 135
 136 int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch, int maxchildrenunordered)
 137 {
 138         int i;
 139
 140         memset(bih, 0, sizeof(*bih));
 141         bih->numleafs = numleafs;
 142         bih->leafs = leafs;
 143         bih->leafsort = temp_leafsort;
 144         bih->leafsortscratch = temp_leafsortscratch;
 145         bih->numnodes = 0;
 146         bih->maxnodes = maxnodes;
 147         bih->nodes = nodes;
 148         bih->maxchildrenunordered = maxchildrenunordered;
 149         if (bih->maxchildrenunordered > BIH_MAXUNORDEREDCHILDREN)
 150                 bih->maxchildrenunordered = BIH_MAXUNORDEREDCHILDREN;
 151
 152         // clear things we intend to rebuild
 153         memset(bih->nodes, 0, sizeof(bih->nodes[0]) * bih->maxnodes);
 154         for (i = 0;i < bih->numleafs;i++)
 155                 bih->leafsort[i] = i;
 156
 157         bih->rootnode = BIH_BuildNode(bih, bih->numleafs, bih->leafsort, bih->mins, bih->maxs);
 158         return bih->error;
 159 }
 160
 161 static void BIH_GetTriangleListForBox_Node(const bih_t *bih, int nodenum, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, int *numtrianglespointer, const float *mins, const float *maxs)
 162 {
 163         int axis;
 164         bih_node_t *node;
 165         bih_leaf_t *leaf;
 166         while (nodenum >= 0)
 167         {
 168                 node = bih->nodes + nodenum;
 169                 // check if this is an unordered node (which holds an array of leaf numbers)
 170                 if (node->type == BIH_UNORDERED)
 171                 {
 172                         for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
 173                         {
 174                                 leaf = bih->leafs + node->children[axis];
 175                                 if (mins[0] > leaf->maxs[0] || maxs[0] < leaf->mins[0]
 176                                  || mins[1] > leaf->maxs[1] || maxs[1] < leaf->mins[1]
 177                                  || mins[2] > leaf->maxs[2] || maxs[2] < leaf->mins[2])
 178                                         continue;
 179                                 switch(leaf->type)
 180                                 {
 181                                 case BIH_RENDERTRIANGLE:
 182                                         if (*numtrianglespointer >= maxtriangles)
 183                                         {
 184                                                 ++*numtrianglespointer; // so the caller can detect overflow
 185                                                 break;
 186                                         }
 187                                         if(trianglelist_surf)
 188                                                 trianglelist_surf[*numtrianglespointer] = leaf->surfaceindex;
 189                                         trianglelist_idx[*numtrianglespointer] = leaf->itemindex;
 190                                         ++*numtrianglespointer;
 191                                         break;
 192                                 default:
 193                                         break;
 194                                 }
 195                         }
 196                         return;
 197                 }
 198                 // splitting node
 199                 axis = node->type - BIH_SPLITX;
 200                 if (mins[axis] < node->backmax)
 201                 {
 202                         if (maxs[axis] > node->frontmin)
 203                                 BIH_GetTriangleListForBox_Node(bih, node->front, maxtriangles, trianglelist_idx, trianglelist_surf, numtrianglespointer, mins, maxs);
 204                         nodenum = node->back;
 205                         continue;
 206                 }
 207                 if (maxs[axis] > node->frontmin)
 208                 {
 209                         nodenum = node->front;
 210                         continue;
 211                 }
 212                 // fell between the child groups, nothing here
 213                 return;
 214         }
 215         leaf = bih->leafs + (-1-nodenum);
 216         if (mins[0] > leaf->maxs[0] || maxs[0] < leaf->mins[0]
 217          || mins[1] > leaf->maxs[1] || maxs[1] < leaf->mins[1]
 218          || mins[2] > leaf->maxs[2] || maxs[2] < leaf->mins[2])
 219                 return;
 220         switch(leaf->type)
 221         {
 222         case BIH_RENDERTRIANGLE:
 223                 if (*numtrianglespointer >= maxtriangles)
 224                 {
 225                         ++*numtrianglespointer; // so the caller can detect overflow
 226                         break;
 227                 }
 228                 if(trianglelist_surf)
 229                         trianglelist_surf[*numtrianglespointer] = leaf->surfaceindex;
 230                 trianglelist_idx[*numtrianglespointer] = leaf->itemindex;
 231                 ++*numtrianglespointer;
 232                 break;
 233         default:
 234                 break;
 235         }
 236 }
 237
 238 int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, const float *mins, const float *maxs)
 239 {
 240         int numtriangles = 0;
 241         BIH_GetTriangleListForBox_Node(bih, 0, maxtriangles, trianglelist_idx, trianglelist_surf, &numtriangles, mins, maxs);
 242         return numtriangles;
 243 }