bih.c

   1
   2 // This code written in 2010 by Ashley Rose Hale (LadyHavoc) (darkplacesengine gmail 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 we run out of nodes it's the caller's fault, but don't crash
  57         if (bih->numnodes == bih->maxnodes)
  58         {
  59                 if (!bih->error)
  60                         bih->error = BIHERROR_OUT_OF_NODES;
  61                 return 0;
  62         }
  63         nodenum = bih->numnodes++;
  64         node = bih->nodes + nodenum;
  65         // store bounds for node
  66         node->mins[0] = mins[0];
  67         node->mins[1] = mins[1];
  68         node->mins[2] = mins[2];
  69         node->maxs[0] = maxs[0];
  70         node->maxs[1] = maxs[1];
  71         node->maxs[2] = maxs[2];
  72         node->front = 0;
  73         node->back = 0;
  74         node->frontmin = 0;
  75         node->backmax = 0;
  76         memset(node->children, -1, sizeof(node->children));
  77         // check if there are few enough children to store an unordered node
  78         if (numchildren <= BIH_MAXUNORDEREDCHILDREN)
  79         {
  80                 node->type = BIH_UNORDERED;
  81                 for (j = 0;j < numchildren;j++)
  82                         node->children[j] = leaflist[j];
  83                 return nodenum;
  84         }
  85         // pick longest axis
  86         longestaxis = 0;
  87         if (size[0] < size[1]) longestaxis = 1;
  88         if (size[longestaxis] < size[2]) longestaxis = 2;
  89         // iterate possible split axis choices, starting with the longest axis, if
  90         // all fail it means all children have the same bounds and we simply split
  91         // the list in half because each node can only have two children.
  92         for (j = 0;j < 3;j++)
  93         {
  94                 // pick an axis
  95                 axis = (longestaxis + j) % 3;
  96                 // sort children into front and back lists
  97                 splitdist = (node->mins[axis] + node->maxs[axis]) * 0.5f;
  98                 front = 0;
  99                 back = 0;
 100                 for (i = 0;i < numchildren;i++)
 101                 {
 102                         child = bih->leafs + leaflist[i];
 103                         d = (child->mins[axis] + child->maxs[axis]) * 0.5f;
 104                         if (d < splitdist)
 105                                 bih->leafsortscratch[back++] = leaflist[i];
 106                         else
 107                                 leaflist[front++] = leaflist[i];
 108                 }
 109                 // now copy the back ones into the space made in the leaflist for them
 110                 if (back)
 111                         memcpy(leaflist + front, bih->leafsortscratch, back*sizeof(leaflist[0]));
 112                 // if both sides have some children, it's good enough for us.
 113                 if (front && back)
 114                         break;
 115         }
 116         if (j == 3)
 117         {
 118                 // somewhat common case: no good choice, divide children arbitrarily
 119                 axis = 0;
 120                 back = numchildren >> 1;
 121                 front = numchildren - back;
 122         }
 123
 124         // we now have front and back children divided in leaflist...
 125         node->type = (bih_nodetype_t)((int)BIH_SPLITX + axis);
 126         node->front = BIH_BuildNode(bih, front, leaflist, frontmins, frontmaxs);
 127         node->frontmin = frontmins[axis];
 128         node->back = BIH_BuildNode(bih, back, leaflist + front, backmins, backmaxs);
 129         node->backmax = backmaxs[axis];
 130         return nodenum;
 131 }
 132
 133 int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch)
 134 {
 135         int i;
 136
 137         memset(bih, 0, sizeof(*bih));
 138         bih->numleafs = numleafs;
 139         bih->leafs = leafs;
 140         bih->leafsort = temp_leafsort;
 141         bih->leafsortscratch = temp_leafsortscratch;
 142         bih->numnodes = 0;
 143         bih->maxnodes = maxnodes;
 144         bih->nodes = nodes;
 145
 146         // clear things we intend to rebuild
 147         memset(bih->nodes, 0, sizeof(bih->nodes[0]) * bih->maxnodes);
 148         for (i = 0;i < bih->numleafs;i++)
 149                 bih->leafsort[i] = i;
 150
 151         bih->rootnode = BIH_BuildNode(bih, bih->numleafs, bih->leafsort, bih->mins, bih->maxs);
 152         return bih->error;
 153 }
 154
 155 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)
 156 {
 157         int axis;
 158         bih_node_t *node;
 159         bih_leaf_t *leaf;
 160         for(;;)
 161         {
 162                 node = bih->nodes + nodenum;
 163                 // check if this is an unordered node (which holds an array of leaf numbers)
 164                 if (node->type == BIH_UNORDERED)
 165                 {
 166                         for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
 167                         {
 168                                 leaf = bih->leafs + node->children[axis];
 169                                 if (mins[0] > leaf->maxs[0] || maxs[0] < leaf->mins[0]
 170                                  || mins[1] > leaf->maxs[1] || maxs[1] < leaf->mins[1]
 171                                  || mins[2] > leaf->maxs[2] || maxs[2] < leaf->mins[2])
 172                                         continue;
 173                                 switch(leaf->type)
 174                                 {
 175                                 case BIH_RENDERTRIANGLE:
 176                                         if (*numtrianglespointer >= maxtriangles)
 177                                         {
 178                                                 ++*numtrianglespointer; // so the caller can detect overflow
 179                                                 break;
 180                                         }
 181                                         if(trianglelist_surf)
 182                                                 trianglelist_surf[*numtrianglespointer] = leaf->surfaceindex;
 183                                         trianglelist_idx[*numtrianglespointer] = leaf->itemindex;
 184                                         ++*numtrianglespointer;
 185                                         break;
 186                                 default:
 187                                         break;
 188                                 }
 189                         }
 190                         return;
 191                 }
 192                 // splitting node
 193                 axis = node->type - BIH_SPLITX;
 194                 if (mins[axis] < node->backmax)
 195                 {
 196                         if (maxs[axis] > node->frontmin)
 197                                 BIH_GetTriangleListForBox_Node(bih, node->front, maxtriangles, trianglelist_idx, trianglelist_surf, numtrianglespointer, mins, maxs);
 198                         nodenum = node->back;
 199                         continue;
 200                 }
 201                 if (maxs[axis] > node->frontmin)
 202                 {
 203                         nodenum = node->front;
 204                         continue;
 205                 }
 206                 // fell between the child groups, nothing here
 207                 return;
 208         }
 209 }
 210
 211 int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, const float *mins, const float *maxs)
 212 {
 213         int numtriangles = 0;
 214         BIH_GetTriangleListForBox_Node(bih, bih->rootnode, maxtriangles, trianglelist_idx, trianglelist_surf, &numtriangles, mins, maxs);
 215         return numtriangles;
 216 }