BIH Class Reference

#include <BoundingIntervalHierarchy.h>

Classes
struct	buildData
class	BuildStats
struct	StackNode

Public Member Functions
	BIH ()
template<class BoundsFunc , class PrimArray >
void	build (const PrimArray &primitives, BoundsFunc &getBounds, uint32 leafSize=3, bool printStats=false)
uint32	primCount () const
template<typename RayCallback >
void	intersectRay (const G3D::Ray &r, RayCallback &intersectCallback, float &maxDist, bool stopAtFirst=false) const
template<typename IsectCallback >
void	intersectPoint (const G3D::Vector3 &p, IsectCallback &intersectCallback) const
bool	writeToFile (FILE *wf) const
bool	readFromFile (FILE *rf)

Protected Member Functions
void	buildHierarchy (std::vector< uint32 > &tempTree, buildData &dat, BuildStats &stats)
void	createNode (std::vector< uint32 > &tempTree, int nodeIndex, uint32 left, uint32 right) const
void	subdivide (int left, int right, std::vector< uint32 > &tempTree, buildData &dat, AABound &gridBox, AABound &nodeBox, int nodeIndex, int depth, BuildStats &stats)

Protected Attributes
std::vector< uint32 >	tree
std::vector< uint32 >	objects
G3D::AABox	bounds

Private Member Functions
void	init_empty ()

Detailed Description

Bounding Interval Hierarchy Class. Building and Ray-Intersection functions based on BIH from Sunflow, a Java Raytracer, released under MIT/X11 License http://sunflow.sourceforge.net/ Copyright (c) 2003-2007 Christopher Kulla

Constructor & Destructor Documentation

BIH::BIH ( )

inline

{ init_empty(); }

Member Function Documentation

template<class BoundsFunc , class PrimArray >

void BIH::build ( const PrimArray &  primitives, BoundsFunc &  getBounds, uint32  leafSize = 3, bool  printStats = false  )

inline

 {
 if (primitives.size() == 0)
 {
 init_empty();
 return;
 }

 buildData dat;
 dat.maxPrims = leafSize;
 dat.numPrims = uint32(primitives.size());
 dat.indices = new uint32[dat.numPrims];
 dat.primBound = new G3D::AABox[dat.numPrims];
 getBounds(primitives[0], bounds);
 for (uint32 i=0; i<dat.numPrims; ++i)
 {
 dat.indices[i] = i;
 getBounds(primitives[i], dat.primBound[i]);
 bounds.merge(dat.primBound[i]);
 }
 std::vector<uint32> tempTree;
 BuildStats stats;
 buildHierarchy(tempTree, dat, stats);
 if (printStats)
 stats.printStats();

 objects.resize(dat.numPrims);
 for (uint32 i=0; i<dat.numPrims; ++i)
 objects[i] = dat.indices[i];
 //nObjects = dat.numPrims;
 tree = tempTree;
 delete[] dat.primBound;
 delete[] dat.indices;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void BIH::buildHierarchy ( std::vector< uint32 > &  tempTree, buildData &  dat, BuildStats &  stats  )

protected

{
 // create space for the first node
 tempTree.push_back(uint32(3 << 30)); // dummy leaf
 tempTree.insert(tempTree.end(), 2, 0);
 //tempTree.add(0);

 // seed bbox
 AABound gridBox = { bounds.low(), bounds.high() };
 AABound nodeBox = gridBox;
 // seed subdivide function
 subdivide(0, dat.numPrims - 1, tempTree, dat, gridBox, nodeBox, 0, 1, stats);
}

Here is the call graph for this function:

void BIH::createNode ( std::vector< uint32 > &  tempTree, int  nodeIndex, uint32  left, uint32  right  ) const

inlineprotected

 {
 // write leaf node
 tempTree[nodeIndex + 0] = (3 << 30) | left;
 tempTree[nodeIndex + 1] = right - left + 1;
 }

Here is the caller graph for this function:

void BIH::init_empty ( )

inlineprivate

 {
 tree.clear();
 objects.clear();
 // create space for the first node
 tree.push_back(3u << 30u); // dummy leaf
 tree.insert(tree.end(), 2, 0);
 }

template<typename IsectCallback >

void BIH::intersectPoint ( const G3D::Vector3 &  p, IsectCallback &  intersectCallback  ) const

inline

 {
 if (!bounds.contains(p))
 return;

 StackNode stack[MAX_STACK_SIZE];
 int stackPos = 0;
 int node = 0;

 while (true) {
 while (true)
 {
 uint32 tn = tree[node];
 uint32 axis = (tn & (3 << 30)) >> 30;
 bool BVH2 = (tn & (1 << 29)) != 0;
 int offset = tn & ~(7 << 29);
 if (!BVH2)
 {
 if (axis < 3)
 {
 // "normal" interior node
 float tl = intBitsToFloat(tree[node + 1]);
 float tr = intBitsToFloat(tree[node + 2]);
 // point is between clip zones
 if (tl < p[axis] && tr > p[axis])
 break;
 int right = offset + 3;
 node = right;
 // point is in right node only
 if (tl < p[axis]) {
 continue;
 }
 node = offset; // left
 // point is in left node only
 if (tr > p[axis]) {
 continue;
 }
 // point is in both nodes
 // push back right node
 stack[stackPos].node = right;
 stackPos++;
 continue;
 }
 else
 {
 // leaf - test some objects
 int n = tree[node + 1];
 while (n > 0) {
 intersectCallback(p, objects[offset]); // !!!
 --n;
 ++offset;
 }
 break;
 }
 }
 else // BVH2 node (empty space cut off left and right)
 {
 if (axis>2)
 return; // should not happen
 float tl = intBitsToFloat(tree[node + 1]);
 float tr = intBitsToFloat(tree[node + 2]);
 node = offset;
 if (tl > p[axis] || tr < p[axis])
 break;
 continue;
 }
 } // traversal loop

 // stack is empty?
 if (stackPos == 0)
 return;
 // move back up the stack
 stackPos--;
 node = stack[stackPos].node;
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename RayCallback >

void BIH::intersectRay ( const G3D::Ray &  r, RayCallback &  intersectCallback, float &  maxDist, bool  stopAtFirst = false  ) const

inline

 {
 float intervalMin = -1.f;
 float intervalMax = -1.f;
 G3D::Vector3 org = r.origin();
 G3D::Vector3 dir = r.direction();
 G3D::Vector3 invDir;
 for (int i=0; i<3; ++i)
 {
 invDir[i] = 1.f / dir[i];
 if (G3D::fuzzyNe(dir[i], 0.0f))
 {
 float t1 = (bounds.low()[i] - org[i]) * invDir[i];
 float t2 = (bounds.high()[i] - org[i]) * invDir[i];
 if (t1 > t2)
 std::swap(t1, t2);
 if (t1 > intervalMin)
 intervalMin = t1;
 if (t2 < intervalMax || intervalMax < 0.f)
 intervalMax = t2;
 // intervalMax can only become smaller for other axis,
 // and intervalMin only larger respectively, so stop early
 if (intervalMax <= 0 || intervalMin >= maxDist)
 return;
 }
 }

 if (intervalMin > intervalMax)
 return;
 intervalMin = std::max(intervalMin, 0.f);
 intervalMax = std::min(intervalMax, maxDist);

 uint32 offsetFront[3];
 uint32 offsetBack[3];
 uint32 offsetFront3[3];
 uint32 offsetBack3[3];
 // compute custom offsets from direction sign bit

 for (int i=0; i<3; ++i)
 {
 offsetFront[i] = floatToRawIntBits(dir[i]) >> 31;
 offsetBack[i] = offsetFront[i] ^ 1;
 offsetFront3[i] = offsetFront[i] * 3;
 offsetBack3[i] = offsetBack[i] * 3;

 // avoid always adding 1 during the inner loop
 ++offsetFront[i];
 ++offsetBack[i];
 }

 StackNode stack[MAX_STACK_SIZE];
 int stackPos = 0;
 int node = 0;

 while (true) {
 while (true)
 {
 uint32 tn = tree[node];
 uint32 axis = (tn & (3 << 30)) >> 30;
 bool BVH2 = (tn & (1 << 29)) != 0;
 int offset = tn & ~(7 << 29);
 if (!BVH2)
 {
 if (axis < 3)
 {
 // "normal" interior node
 float tf = (intBitsToFloat(tree[node + offsetFront[axis]]) - org[axis]) * invDir[axis];
 float tb = (intBitsToFloat(tree[node + offsetBack[axis]]) - org[axis]) * invDir[axis];
 // ray passes between clip zones
 if (tf < intervalMin && tb > intervalMax)
 break;
 int back = offset + offsetBack3[axis];
 node = back;
 // ray passes through far node only
 if (tf < intervalMin) {
 intervalMin = (tb >= intervalMin) ? tb : intervalMin;
 continue;
 }
 node = offset + offsetFront3[axis]; // front
 // ray passes through near node only
 if (tb > intervalMax) {
 intervalMax = (tf <= intervalMax) ? tf : intervalMax;
 continue;
 }
 // ray passes through both nodes
 // push back node
 stack[stackPos].node = back;
 stack[stackPos].tnear = (tb >= intervalMin) ? tb : intervalMin;
 stack[stackPos].tfar = intervalMax;
 stackPos++;
 // update ray interval for front node
 intervalMax = (tf <= intervalMax) ? tf : intervalMax;
 continue;
 }
 else
 {
 // leaf - test some objects
 int n = tree[node + 1];
 while (n > 0) {
 bool hit = intersectCallback(r, objects[offset], maxDist, stopAtFirst);
 if (stopAtFirst && hit) return;
 --n;
 ++offset;
 }
 break;
 }
 }
 else
 {
 if (axis>2)
 return; // should not happen
 float tf = (intBitsToFloat(tree[node + offsetFront[axis]]) - org[axis]) * invDir[axis];
 float tb = (intBitsToFloat(tree[node + offsetBack[axis]]) - org[axis]) * invDir[axis];
 node = offset;
 intervalMin = (tf >= intervalMin) ? tf : intervalMin;
 intervalMax = (tb <= intervalMax) ? tb : intervalMax;
 if (intervalMin > intervalMax)
 break;
 continue;
 }
 } // traversal loop
 do
 {
 // stack is empty?
 if (stackPos == 0)
 return;
 // move back up the stack
 stackPos--;
 intervalMin = stack[stackPos].tnear;
 if (maxDist < intervalMin)
 continue;
 node = stack[stackPos].node;
 intervalMax = stack[stackPos].tfar;
 break;
 } while (true);
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

uint32 BIH::primCount ( ) const

inline

{ return uint32(objects.size()); }

Here is the caller graph for this function:

bool BIH::readFromFile

(

FILE *

rf

)

{
 uint32 treeSize;
 G3D::Vector3 lo, hi;
 uint32 check=0, count=0;
 check += fread(&lo, sizeof(float), 3, rf);
 check += fread(&hi, sizeof(float), 3, rf);
 bounds = G3D::AABox(lo, hi);
 check += fread(&treeSize, sizeof(uint32), 1, rf);
 tree.resize(treeSize);
 check += fread(&tree[0], sizeof(uint32), treeSize, rf);
 check += fread(&count, sizeof(uint32), 1, rf);
 objects.resize(count); // = new uint32[nObjects];
 check += fread(&objects[0], sizeof(uint32), count, rf);
 return uint64(check) == uint64(3 + 3 + 1 + 1 + uint64(treeSize) + uint64(count));
}

Here is the call graph for this function:

Here is the caller graph for this function:

void BIH::subdivide ( int  left, int  right, std::vector< uint32 > &  tempTree, buildData &  dat, AABound &  gridBox, AABound &  nodeBox, int  nodeIndex, int  depth, BuildStats &  stats  )

protected

{
 if ((right - left + 1) <= dat.maxPrims || depth >= MAX_STACK_SIZE)
 {
 // write leaf node
 stats.updateLeaf(depth, right - left + 1);
 createNode(tempTree, nodeIndex, left, right);
 return;
 }
 // calculate extents
 int axis = -1, prevAxis, rightOrig;
 float clipL = G3D::fnan(), clipR = G3D::fnan(), prevClip = G3D::fnan();
 float split = G3D::fnan(), prevSplit;
 bool wasLeft = true;
 while (true)
 {
 prevAxis = axis;
 prevSplit = split;
 // perform quick consistency checks
 G3D::Vector3 d( gridBox.hi - gridBox.lo );
 if (d.x < 0 || d.y < 0 || d.z < 0)
 throw std::logic_error("negative node extents");
 for (int i = 0; i < 3; i++)
 {
 if (nodeBox.hi[i] < gridBox.lo[i] || nodeBox.lo[i] > gridBox.hi[i])
 {
 //UI.printError(Module.ACCEL, "Reached tree area in error - discarding node with: %d objects", right - left + 1);
 throw std::logic_error("invalid node overlap");
 }
 }
 // find longest axis
 axis = d.primaryAxis();
 split = 0.5f * (gridBox.lo[axis] + gridBox.hi[axis]);
 // partition L/R subsets
 clipL = -G3D::finf();
 clipR = G3D::finf();
 rightOrig = right; // save this for later
 float nodeL = G3D::finf();
 float nodeR = -G3D::finf();
 for (int i = left; i <= right;)
 {
 int obj = dat.indices[i];
 float minb = dat.primBound[obj].low()[axis];
 float maxb = dat.primBound[obj].high()[axis];
 float center = (minb + maxb) * 0.5f;
 if (center <= split)
 {
 // stay left
 i++;
 if (clipL < maxb)
 clipL = maxb;
 }
 else
 {
 // move to the right most
 int t = dat.indices[i];
 dat.indices[i] = dat.indices[right];
 dat.indices[right] = t;
 right--;
 if (clipR > minb)
 clipR = minb;
 }
 nodeL = std::min(nodeL, minb);
 nodeR = std::max(nodeR, maxb);
 }
 // check for empty space
 if (nodeL > nodeBox.lo[axis] && nodeR < nodeBox.hi[axis])
 {
 float nodeBoxW = nodeBox.hi[axis] - nodeBox.lo[axis];
 float nodeNewW = nodeR - nodeL;
 // node box is too big compare to space occupied by primitives?
 if (1.3f * nodeNewW < nodeBoxW)
 {
 stats.updateBVH2();
 int nextIndex = tempTree.size();
 // allocate child
 tempTree.push_back(0);
 tempTree.push_back(0);
 tempTree.push_back(0);
 // write bvh2 clip node
 stats.updateInner();
 tempTree[nodeIndex + 0] = (axis << 30) | (1 << 29) | nextIndex;
 tempTree[nodeIndex + 1] = floatToRawIntBits(nodeL);
 tempTree[nodeIndex + 2] = floatToRawIntBits(nodeR);
 // update nodebox and recurse
 nodeBox.lo[axis] = nodeL;
 nodeBox.hi[axis] = nodeR;
 subdivide(left, rightOrig, tempTree, dat, gridBox, nodeBox, nextIndex, depth + 1, stats);
 return;
 }
 }
 // ensure we are making progress in the subdivision
 if (right == rightOrig)
 {
 // all left
 if (prevAxis == axis && G3D::fuzzyEq(prevSplit, split)) {
 // we are stuck here - create a leaf
 stats.updateLeaf(depth, right - left + 1);
 createNode(tempTree, nodeIndex, left, right);
 return;
 }
 if (clipL <= split) {
 // keep looping on left half
 gridBox.hi[axis] = split;
 prevClip = clipL;
 wasLeft = true;
 continue;
 }
 gridBox.hi[axis] = split;
 prevClip = G3D::fnan();
 }
 else if (left > right)
 {
 // all right
 if (prevAxis == axis && G3D::fuzzyEq(prevSplit, split)) {
 // we are stuck here - create a leaf
 stats.updateLeaf(depth, right - left + 1);
 createNode(tempTree, nodeIndex, left, right);
 return;
 }
 right = rightOrig;
 if (clipR >= split) {
 // keep looping on right half
 gridBox.lo[axis] = split;
 prevClip = clipR;
 wasLeft = false;
 continue;
 }
 gridBox.lo[axis] = split;
 prevClip = G3D::fnan();
 }
 else
 {
 // we are actually splitting stuff
 if (prevAxis != -1 && !isnan(prevClip))
 {
 // second time through - lets create the previous split
 // since it produced empty space
 int nextIndex = tempTree.size();
 // allocate child node
 tempTree.push_back(0);
 tempTree.push_back(0);
 tempTree.push_back(0);
 if (wasLeft) {
 // create a node with a left child
 // write leaf node
 stats.updateInner();
 tempTree[nodeIndex + 0] = (prevAxis << 30) | nextIndex;
 tempTree[nodeIndex + 1] = floatToRawIntBits(prevClip);
 tempTree[nodeIndex + 2] = floatToRawIntBits(G3D::finf());
 } else {
 // create a node with a right child
 // write leaf node
 stats.updateInner();
 tempTree[nodeIndex + 0] = (prevAxis << 30) | (nextIndex - 3);
 tempTree[nodeIndex + 1] = floatToRawIntBits(-G3D::finf());
 tempTree[nodeIndex + 2] = floatToRawIntBits(prevClip);
 }
 // count stats for the unused leaf
 depth++;
 stats.updateLeaf(depth, 0);
 // now we keep going as we are, with a new nodeIndex:
 nodeIndex = nextIndex;
 }
 break;
 }
 }
 // compute index of child nodes
 int nextIndex = tempTree.size();
 // allocate left node
 int nl = right - left + 1;
 int nr = rightOrig - (right + 1) + 1;
 if (nl > 0) {
 tempTree.push_back(0);
 tempTree.push_back(0);
 tempTree.push_back(0);
 } else
 nextIndex -= 3;
 // allocate right node
 if (nr > 0) {
 tempTree.push_back(0);
 tempTree.push_back(0);
 tempTree.push_back(0);
 }
 // write leaf node
 stats.updateInner();
 tempTree[nodeIndex + 0] = (axis << 30) | nextIndex;
 tempTree[nodeIndex + 1] = floatToRawIntBits(clipL);
 tempTree[nodeIndex + 2] = floatToRawIntBits(clipR);
 // prepare L/R child boxes
 AABound gridBoxL(gridBox), gridBoxR(gridBox);
 AABound nodeBoxL(nodeBox), nodeBoxR(nodeBox);
 gridBoxL.hi[axis] = gridBoxR.lo[axis] = split;
 nodeBoxL.hi[axis] = clipL;
 nodeBoxR.lo[axis] = clipR;
 // recurse
 if (nl > 0)
 subdivide(left, right, tempTree, dat, gridBoxL, nodeBoxL, nextIndex, depth + 1, stats);
 else
 stats.updateLeaf(depth + 1, 0);
 if (nr > 0)
 subdivide(right + 1, rightOrig, tempTree, dat, gridBoxR, nodeBoxR, nextIndex + 3, depth + 1, stats);
 else
 stats.updateLeaf(depth + 1, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool BIH::writeToFile

(

FILE *

wf

)

const

{
 uint32 treeSize = tree.size();
 uint32 check=0, count;
 check += fwrite(&bounds.low(), sizeof(float), 3, wf);
 check += fwrite(&bounds.high(), sizeof(float), 3, wf);
 check += fwrite(&treeSize, sizeof(uint32), 1, wf);
 check += fwrite(&tree[0], sizeof(uint32), treeSize, wf);
 count = objects.size();
 check += fwrite(&count, sizeof(uint32), 1, wf);
 check += fwrite(&objects[0], sizeof(uint32), count, wf);
 return check == (3 + 3 + 2 + treeSize + count);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

G3D::AABox BIH::bounds

protected

std::vector<uint32> BIH::objects

protected

std::vector<uint32> BIH::tree

protected

---

The documentation for this class was generated from the following files:

• src/common/Collision/BoundingIntervalHierarchy.h
• src/common/Collision/BoundingIntervalHierarchy.cpp