// This code written in 2010 by Forest Hale (lordhavoc ghdigital com), and placed into public domain.
#include <stdlib.h>
-#include <memory.h>
+#include <string.h>
#include "bih.h"
-static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist)
+static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist, float *totalmins, float *totalmaxs)
{
int i;
int j;
int longestaxis;
- int axis;
+ int axis = 0;
int nodenum;
- int front;
- int back;
+ int front = 0;
+ int back = 0;
bih_node_t *node;
bih_leaf_t *child;
float splitdist;
float mins[3];
float maxs[3];
float size[3];
- if (numchildren < 2)
- return -1-leaflist[0];
- // if we run out of nodes it's the caller's fault, but don't crash
- if (bih->numnodes == bih->maxnodes)
- {
- if (!bih->error)
- bih->error = BIHERROR_OUT_OF_NODES;
- return -1-leaflist[0];
- }
- nodenum = bih->numnodes++;
- node = bih->nodes + nodenum;
+ float frontmins[3];
+ float frontmaxs[3];
+ float backmins[3];
+ float backmaxs[3];
// calculate bounds of children
child = bih->leafs + leaflist[0];
mins[0] = child->mins[0];
size[0] = maxs[0] - mins[0];
size[1] = maxs[1] - mins[1];
size[2] = maxs[2] - mins[2];
+ // provide bounds to caller
+ totalmins[0] = mins[0];
+ totalmins[1] = mins[1];
+ totalmins[2] = mins[2];
+ totalmaxs[0] = maxs[0];
+ totalmaxs[1] = maxs[1];
+ totalmaxs[2] = maxs[2];
+ // if we run out of nodes it's the caller's fault, but don't crash
+ if (bih->numnodes == bih->maxnodes)
+ {
+ if (!bih->error)
+ bih->error = BIHERROR_OUT_OF_NODES;
+ return 0;
+ }
+ nodenum = bih->numnodes++;
+ node = bih->nodes + nodenum;
// store bounds for node
node->mins[0] = mins[0];
node->mins[1] = mins[1];
node->maxs[0] = maxs[0];
node->maxs[1] = maxs[1];
node->maxs[2] = maxs[2];
+ node->front = 0;
+ node->back = 0;
+ node->frontmin = 0;
+ node->backmax = 0;
+ memset(node->children, -1, sizeof(node->children));
+ // check if there are few enough children to store an unordered node
+ if (numchildren <= BIH_MAXUNORDEREDCHILDREN)
+ {
+ node->type = BIH_UNORDERED;
+ for (j = 0;j < numchildren;j++)
+ node->children[j] = leaflist[j];
+ return nodenum;
+ }
// pick longest axis
longestaxis = 0;
if (size[0] < size[1]) longestaxis = 1;
if (size[longestaxis] < size[2]) longestaxis = 2;
- // iterate possible split axis choices:
- // longest (best raytracing performance)
- // x (longest had identical children, try X axis)
- // y (longest and X axis had identical children, try Y axis)
- // z (longest and X and Y axes had identical children, try Z axis)
- // arbitrary (all children have same bounds, divide the list)
+ // iterate possible split axis choices, starting with the longest axis, if
+ // all fail it means all children have the same bounds and we simply split
+ // the list in half because each node can only have two children.
for (j = 0;j < 3;j++)
{
- // if longest axis fails, we try each one until something works
- // (this also can fail, see below)
- switch(j)
- {
- default:
- case 0: axis = longestaxis;break;
- case 1: axis = (longestaxis + 1) % 3;break;
- case 2: axis = (longestaxis + 2) % 3;break;
- }
+ // pick an axis
+ axis = (longestaxis + j) % 3;
// sort children into front and back lists
- node->type = BIH_SPLITX + axis;
splitdist = (node->mins[axis] + node->maxs[axis]) * 0.5f;
front = 0;
back = 0;
}
if (j == 3)
{
- // the almost impossible case happened; all children have identical
- // bounds, so just divide them arbitrarily into two lists.
- node->type = BIH_SPLITX;
+ // somewhat common case: no good choice, divide children arbitrarily
+ axis = 0;
back = numchildren >> 1;
front = numchildren - back;
}
// we now have front and back children divided in leaflist...
- node->children[0] = BIH_BuildNode(bih, front, leaflist);
- node->children[1] = BIH_BuildNode(bih, back, leaflist + front);
+ node->type = (bih_nodetype_t)((int)BIH_SPLITX + axis);
+ node->front = BIH_BuildNode(bih, front, leaflist, frontmins, frontmaxs);
+ node->frontmin = frontmins[axis];
+ node->back = BIH_BuildNode(bih, back, leaflist + front, backmins, backmaxs);
+ node->backmax = backmaxs[axis];
return nodenum;
}
for (i = 0;i < bih->numleafs;i++)
bih->leafsort[i] = i;
- BIH_BuildNode(bih, bih->numleafs, bih->leafsort);
+ bih->rootnode = BIH_BuildNode(bih, bih->numleafs, bih->leafsort, bih->mins, bih->maxs);
return bih->error;
}
+
+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)
+{
+ int axis;
+ bih_node_t *node;
+ bih_leaf_t *leaf;
+ for(;;)
+ {
+ node = bih->nodes + nodenum;
+ // check if this is an unordered node (which holds an array of leaf numbers)
+ if (node->type == BIH_UNORDERED)
+ {
+ for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
+ {
+ leaf = bih->leafs + node->children[axis];
+ if (mins[0] > leaf->maxs[0] || maxs[0] < leaf->mins[0]
+ || mins[1] > leaf->maxs[1] || maxs[1] < leaf->mins[1]
+ || mins[2] > leaf->maxs[2] || maxs[2] < leaf->mins[2])
+ continue;
+ switch(leaf->type)
+ {
+ case BIH_RENDERTRIANGLE:
+ if (*numtrianglespointer >= maxtriangles)
+ {
+ ++*numtrianglespointer; // so the caller can detect overflow
+ break;
+ }
+ if(trianglelist_surf)
+ trianglelist_surf[*numtrianglespointer] = leaf->surfaceindex;
+ trianglelist_idx[*numtrianglespointer] = leaf->itemindex;
+ ++*numtrianglespointer;
+ break;
+ default:
+ break;
+ }
+ }
+ return;
+ }
+ // splitting node
+ axis = node->type - BIH_SPLITX;
+ if (mins[axis] < node->backmax)
+ {
+ if (maxs[axis] > node->frontmin)
+ BIH_GetTriangleListForBox_Node(bih, node->front, maxtriangles, trianglelist_idx, trianglelist_surf, numtrianglespointer, mins, maxs);
+ nodenum = node->back;
+ continue;
+ }
+ if (maxs[axis] > node->frontmin)
+ {
+ nodenum = node->front;
+ continue;
+ }
+ // fell between the child groups, nothing here
+ return;
+ }
+}
+
+int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, const float *mins, const float *maxs)
+{
+ int numtriangles = 0;
+ BIH_GetTriangleListForBox_Node(bih, bih->rootnode, maxtriangles, trianglelist_idx, trianglelist_surf, &numtriangles, mins, maxs);
+ return numtriangles;
+}
projects / xonotic / darkplaces.git / blobdiff