Skip to content
Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
397 lines (335 sloc) 16 KB
// cyCodeBase by Cem Yuksel
// [www.cemyuksel.com]
//-------------------------------------------------------------------------------
//! \file cyBVH.h
//! \author Cem Yuksel
//!
//! \brief Bounding Volume Hierarchy class.
//!
//! BVH is a storage class for Bounding Volume Hierarchies.
//!
//-------------------------------------------------------------------------------
//
// Copyright (c) 2016, Cem Yuksel <cem@cemyuksel.com>
// All rights reserved.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
//
//-------------------------------------------------------------------------------
#ifndef _CY_BVH_H_INCLUDED_
#define _CY_BVH_H_INCLUDED_
//-------------------------------------------------------------------------------
namespace cy {
//-------------------------------------------------------------------------------
#ifndef CY_BVH_ELEMENT_COUNT_BITS
#define CY_BVH_ELEMENT_COUNT_BITS 3 //!< Determines the number of bits needed to represent the maximum number of elements in a node (8)
#endif
#ifndef CY_BVH_MAX_ELEMENT_COUNT
#define CY_BVH_MAX_ELEMENT_COUNT (1<<CY_BVH_ELEMENT_COUNT_BITS) //!< Determines the maximum number of elements in a node (8)
#endif
#define _CY_BVH_NODE_DATA_BITS (sizeof(unsigned int)*8)
#define _CY_BVH_ELEMENT_COUNT_MASK ((1<<CY_BVH_ELEMENT_COUNT_BITS)-1)
#define _CY_BVH_LEAF_BIT_MASK ((unsigned int)1<<(_CY_BVH_NODE_DATA_BITS-1))
#define _CY_BVH_CHILD_INDEX_BITS (_CY_BVH_NODE_DATA_BITS-1)
#define _CY_BVH_CHILD_INDEX_MASK (_CY_BVH_LEAF_BIT_MASK-1)
#define _CY_BVH_ELEMENT_OFFSET_BITS (_CY_BVH_NODE_DATA_BITS-1-CY_BVH_ELEMENT_COUNT_BITS)
#define _CY_BVH_ELEMENT_OFFSET_MASK ((1<<_CY_BVH_ELEMENT_OFFSET_BITS)-1)
//-------------------------------------------------------------------------------
//! Bounding Volume Hierarchy class
class BVH
{
public:
//!@name Constructor and destructor
BVH() : nodes(0), elements(0) {}
virtual ~BVH() { Clear(); }
//////////////////////////////////////////////////////////////////////////!//!//!
//@ Node Access Methods
//////////////////////////////////////////////////////////////////////////!//!//!
//! Returns the index of the root node.
unsigned int GetRootNodeID() const { return 1; }
//! Returns the bounding box of the node as 6 float values.
//! The first 3 values are the minimum x, y, and z coordinates and
//! the last 3 values are the maximum x, y, and z coordinates of the box.
const float* GetNodeBounds(unsigned int nodeID) const { return nodes[nodeID].GetBounds(); }
//! Returns true if the node is a leaf node.
bool IsLeafNode(unsigned int nodeID) const { return nodes[nodeID].IsLeafNode(); }
//! Returns the index of the first child node (parent must be an internal node).
unsigned int GetFirstChildNode(unsigned int parentNodeID) const { return nodes[parentNodeID].ChildIndex(); }
//! Returns the index of the second child node (parent must be an internal node).
unsigned int GetSecondChildNode(unsigned int parentNodeID) const { return nodes[parentNodeID].ChildIndex()+1; }
//! Given the first child node index, returns the index of the second child node.
unsigned int GetSiblingNode(unsigned int firstChildNodeID) const { return firstChildNodeID+1; }
//! Returns the child nodes of the given node (parent must be an internal node).
void GetChildNodes(unsigned int parent, unsigned int &child1, unsigned int &child2) const
{
child1 = GetFirstChildNode(parent);
child2 = GetSiblingNode(child1);
}
//! Returns the number of elements inside the given node (must be a leaf node).
unsigned int GetNodeElementCount(unsigned int nodeID) const { return nodes[nodeID].ElementCount(); }
//! Returns the list of element inside the given node (must be a leaf node).
const unsigned int* GetNodeElements(unsigned int nodeID) const { return &elements[nodes[nodeID].ElementOffset()]; }
//////////////////////////////////////////////////////////////////////////!//!//!
//@ Clear and Build Methods
//////////////////////////////////////////////////////////////////////////!//!//!
//! Clears the tree structure
void Clear()
{
if (nodes) delete [] nodes;
nodes = 0;
if (elements) delete [] elements;
elements = 0;
}
//! Builds the tree structure by recursively splitting the nodes. maxElementsPerNode cannot be larger than 8.
void Build( unsigned int numElements, unsigned int maxElementsPerNode=CY_BVH_MAX_ELEMENT_COUNT )
{
Clear();
if ( numElements == 0 ) return;
if ( maxElementsPerNode > CY_BVH_MAX_ELEMENT_COUNT ) maxElementsPerNode = CY_BVH_MAX_ELEMENT_COUNT;
elements = new unsigned int[numElements];
for ( unsigned int i=0; i<numElements; i++ ) elements[i] = i;
Box box;
box.Init();
for ( unsigned int i=0; i<numElements; i++ ) {
Box b;
GetElementBounds(i,b.b);
box += b;
}
TempNode *tempRoot = new TempNode( numElements, 0, box );
SplitTempNode(tempRoot,maxElementsPerNode);
unsigned int numNodes = tempRoot->GetNumNodes();
nodes = new Node[ numNodes+1 ];
ConvertTempData( 1, tempRoot, 2 );
delete tempRoot;
}
//////////////////////////////////////////////////////////////////////////!//!//!
protected:
//////////////////////////////////////////////////////////////////////////!//!//!
//@ Methods to be implemented by sub-classes
//////////////////////////////////////////////////////////////////////////!//!//!
virtual void GetElementBounds(unsigned int i, float box[6]) const=0; //!< Sets box as the i^th element's bounding box.
virtual float GetElementCenter(unsigned int i, int dimension) const=0; //!< Returns the center of the i^th element in the given dimension
//////////////////////////////////////////////////////////////////////////!//!//!
//@ Building method that can be overloaded
//////////////////////////////////////////////////////////////////////////!//!//!
//! Sorts the given elements of a temporary node while building the BVH hierarchy,
//! such that first N elements are to be assigned to the first child and the
//! remaining elements are to be assigned to the second child node, then returns N.
//! Returns zero, if the node is not to be split.
//! The default implementation splits the temporary node down the middle of the
//! widest axis of its bounding box.
virtual unsigned int FindSplit(unsigned int elementCount, unsigned int *elements, const float *box, unsigned int maxElementsPerNode )
{
return MeanSplit(elementCount,elements,box,maxElementsPerNode);
}
//////////////////////////////////////////////////////////////////////////!//!//!
private:
//////////////////////////////////////////////////////////////////////////!//!//!
//@ Internal storage
//////////////////////////////////////////////////////////////////////////!//!//!
struct Box
{
float b[6];
Box() { Init(); }
Box(const Box &box) { for(int i=0; i<6; i++) b[i]=box.b[i]; }
void Init() { b[0]=b[1]=b[2]=1e30f; b[3]=b[4]=b[5]=-1e30f; }
void operator += (const Box &box) { for(int i=0; i<3; i++) { if(b[i]>box.b[i])b[i]=box.b[i]; if(b[i+3]<box.b[i+3])b[i+3]=box.b[i+3]; } }
};
class Node
{
public:
void SetLeafNode( const Box &bound, unsigned int elemCount, unsigned int elemOffset ) { box=bound; data=(elemOffset&_CY_BVH_ELEMENT_OFFSET_MASK)|((elemCount-1)<<_CY_BVH_ELEMENT_OFFSET_BITS)|_CY_BVH_LEAF_BIT_MASK; }
void SetInternalNode( const Box &bound, unsigned int chilIndex ) { box=bound; data=(chilIndex&_CY_BVH_CHILD_INDEX_MASK); }
unsigned int ChildIndex() const { return (data&_CY_BVH_CHILD_INDEX_MASK); } //!< returns the index to the first child (must be internal node)
unsigned int ElementOffset() const { return (data&_CY_BVH_ELEMENT_OFFSET_MASK); } //!< returns the offset to the first element (must be leaf node)
unsigned int ElementCount() const { return ((data>>_CY_BVH_ELEMENT_OFFSET_BITS)&_CY_BVH_ELEMENT_COUNT_MASK)+1; } //!< returns the number of elements in this node (must be leaf node)
bool IsLeafNode() const { return (data&_CY_BVH_LEAF_BIT_MASK)>0; } //!< returns true if this is a leaf node
const float* GetBounds() const { return box.b; } //!< returns the bounding box of the node
private:
Box box; //!< bounding box of the node
unsigned int data; //!< node data bits that keep the leaf node flag and the child node index or element count and element offset.
};
Node *nodes; //!< the tree structure that keeps all the node data (nodeData[0] is not used for cache coherency)
unsigned int *elements; //!< indices of all elements in all nodes
//////////////////////////////////////////////////////////////////////////!//!//!
//@ Internal methods for building the BVH tree
//////////////////////////////////////////////////////////////////////////!//!//!
//! Temporary node class used for building the hierarchy and then converted to NodeData.
class TempNode
{
public:
TempNode( unsigned int count, unsigned int offset, const Box &boundBox) : child1(0), child2(0), elementCount(count), elementOffset(offset), box(boundBox) {}
~TempNode() { if ( child1 ) delete child1; if ( child2 ) delete child2; }
void Split( unsigned int child1ElementCount, const Box &child1Box, const Box &child2Box )
{
child1 = new TempNode(child1ElementCount,elementOffset,child1Box);
child2 = new TempNode(ElementCount()-child1ElementCount,elementOffset+child1ElementCount,child2Box);
}
unsigned int GetNumNodes() const
{
unsigned int n = 1;
if ( child1 ) n += child1->GetNumNodes();
if ( child2 ) n += child2->GetNumNodes();
return n;
}
bool IsLeafNode() const { return child1==0; }
unsigned int ElementCount() const { return elementCount; }
unsigned int ElementOffset() const { return elementOffset; }
TempNode* GetChild1() { return child1; }
TempNode* GetChild2() { return child2; }
const Box& GetBounds() const { return box; }
private:
TempNode *child1, *child2;
Box box;
unsigned int elementCount;
unsigned int elementOffset;
};
//! Recursively splits the given temporary node.
void SplitTempNode(TempNode *tNode, unsigned int maxElementsPerNode)
{
const float *box = tNode->GetBounds().b;
unsigned int *nodeElements = &elements[tNode->ElementOffset()];
unsigned int child1ElemCount = FindSplit(tNode->ElementCount(),nodeElements,box,maxElementsPerNode);
// If the FindSplit call does not return a valid split position
if ( child1ElemCount == 0 || child1ElemCount >= tNode->ElementCount() ) {
// if we must split anyway
if ( tNode->ElementCount() > CY_BVH_MAX_ELEMENT_COUNT ) {
// we split in half arbitrarily.
child1ElemCount = tNode->ElementCount() / 2;
} else {
// otherwise, we reached a leaf node and no more split is necessary.
return;
}
}
// Compute child bounding boxes
Box child1Box;
Box child2Box;
for ( unsigned int i=0; i<child1ElemCount; i++ ) {
Box eBox;
GetElementBounds( nodeElements[i], eBox.b );
child1Box += eBox;
}
for ( unsigned int i=child1ElemCount; i<tNode->ElementCount(); i++ ) {
Box eBox;
GetElementBounds( nodeElements[i], eBox.b );
child2Box += eBox;
}
// Split recursively
tNode->Split( child1ElemCount, child1Box, child2Box );
SplitTempNode(tNode->GetChild1(),maxElementsPerNode);
SplitTempNode(tNode->GetChild2(),maxElementsPerNode);
}
//! Recursively converts the temporary node data to NodeData.
unsigned int ConvertTempData( unsigned int nodeID, TempNode *tNode, unsigned int childIndex )
{
if ( tNode->IsLeafNode() ) {
nodes[nodeID].SetLeafNode( tNode->GetBounds(), tNode->ElementCount(), tNode->ElementOffset() );
return childIndex;
} else {
nodes[nodeID].SetInternalNode( tNode->GetBounds(), childIndex );
unsigned int newChildIndex = ConvertTempData( childIndex, tNode->GetChild1(), childIndex+2 );
return ConvertTempData( childIndex+1, tNode->GetChild2(), newChildIndex );
}
}
//! Called by the default implementation of FindSplit.
//! Splits the elements using the widest axis of the given bounding box.
unsigned int MeanSplit(unsigned int elementCount, unsigned int *nodeElements, const float *box, unsigned int maxElementsPerNode )
{
if ( elementCount <= maxElementsPerNode ) return 0;
float d[3] = { box[3]-box[0], box[4]-box[1], box[5]-box[2] };
unsigned int sd[3]; // split dimensions
sd[0] = d[0] >= d[1] ? ( d[0] >= d[2] ? 0 : 2 ) : ( d[1] >= d[2] ? 1 : 2 );
sd[1] = (sd[0]+1) % 3;
sd[2] = (sd[0]+2) % 3;
if ( d[sd[1]] < d[sd[2]] ) { int t=sd[1]; sd[1]=sd[2]; sd[2]=t; }
unsigned int child1ElemCount = 0;
for ( int s=0; s<3; s++ ) {
unsigned int splitDim = sd[s];
float splitPos = 0.5f * ( box[splitDim] + box[splitDim+3] );
unsigned int i=0, j=elementCount;
while ( i<j ) {
float center = GetElementCenter( nodeElements[i], splitDim );
if ( center <= splitPos ) {
i++;
} else {
j--;
unsigned int t = nodeElements[i];
nodeElements[i] = nodeElements[j];
nodeElements[j] = t;
}
}
if ( i < elementCount && i > 0 ) {
child1ElemCount = i;
break;
}
}
return child1ElemCount;
}
//////////////////////////////////////////////////////////////////////////!//!//!
};
//-------------------------------------------------------------------------------
#ifdef _CY_TRIMESH_H_INCLUDED_
//! Bounding Volume Hierarchy for triangular meshes (TriMesh)
class BVHTriMesh : public BVH
{
public:
//!@name Constructors
BVHTriMesh() : mesh(0) {}
BVHTriMesh(const TriMesh *m) { SetMesh(m); }
//! Sets the mesh pointer and builds the BVH structure.
void SetMesh(const TriMesh *m, unsigned int maxElementsPerNode=CY_BVH_MAX_ELEMENT_COUNT)
{
mesh = m;
Clear();
Build(mesh->NF(),maxElementsPerNode);
}
protected:
//! Sets box as the i^th element's bounding box.
virtual void GetElementBounds(unsigned int i, float box[6]) const
{
const TriMesh::TriFace &f = mesh->F(i);
cyPoint3f p = mesh->V( f.v[0] );
box[0]=box[3]=p.x; box[1]=box[4]=p.y; box[2]=box[5]=p.z;
for ( int j=1; j<3; j++ ) { // for each triangle
cyPoint3f p = mesh->V( f.v[j] );
for ( int k=0; k<3; k++ ) { // for each dimension
if ( box[k] > p[k] ) box[k] = p[k];
if ( box[k+3] < p[k] ) box[k+3] = p[k];
}
}
}
//! Returns the center of the i^th element in the given dimension.
virtual float GetElementCenter(unsigned int i, int dim) const
{
const TriMesh::TriFace &f = mesh->F(i);
return ( mesh->V(f.v[0])[dim] + mesh->V(f.v[1])[dim] + mesh->V(f.v[2])[dim] ) / 3.0f;
}
private:
const TriMesh *mesh;
};
#endif
//-------------------------------------------------------------------------------
} // namespace cy
//-------------------------------------------------------------------------------
typedef cy::BVH cyBVH; //!< Bounding Volume Hierarchy class
#ifdef _CY_TRIMESH_H_INCLUDED_
typedef cy::BVHTriMesh cyBVHTriMesh; //!< BVH hierarchy for triangular meshes (TriMesh)
#endif
//-------------------------------------------------------------------------------
#endif
You can’t perform that action at this time.