BVHTree< T > Class Template Reference

BVHTree class is an abstract class for any Boundary Volume Hierarchy Tree. More...

#include <TAPsBVHTree.hpp>

Inheritance diagram for BVHTree< T >:

Inheritance graph
[legend]

List of all members.

Public Member Functions

 BVHTree (TransformationSupport< T > &transform, HEFaceList< T > *heFaceList)
 BVHTree (TransformationSupport< T > &transform, Enum::CD type=Enum::UNDEFINED_TREE, int numOfNodes=0, BVHNode< T > *rootNode=NULL)
int CountLeafNodes () const
int CountNodes () const
virtual std::vector
< BVsAndNodesList< T > > & 		GetListOfCollidedBoundingVolumesAndNodes ()
virtual std::vector< BVHNode
< T > * > & 		GetListOfCollidedNodes ()
virtual std::vector< BVHNode
< T > * > & 		GetListOfCollidedNodesThat ()
int GetNumOfNodes () const
TransformationSupport< T > & GetTransform ()
TransformationSupport< T > const & GetTransform () const
Enum::CD GetType () const
void Root (BVHNode< T > *root)
BVHNode< T > const *const Root () const
BVHNode< T > * Root ()
void SetNumOfNodes (int n)
virtual bool TestIntersectionWithLineSegmentTillLeafNodes (Vector3< T > const *const ptA, Vector3< T > const *const ptB)=0
virtual bool TestOverlapWith (BoundingVolume< T > const *const pBV)=0
virtual bool TestOverlapWith (MultiBoundingVolume< T > const *const pMBV)=0
virtual bool TestOverlapWith (BVHNode< T > const *const node)=0
virtual bool TestOverlapWith (BVHTree< T > const *const that)=0
virtual bool TestOverlapWithTillLeafNodes (BoundingVolume< T > const *const pBV)=0
virtual bool TestOverlapWithTillLeafNodes (MultiBoundingVolume< T > const *const pMBV)=0
virtual bool TestOverlapWithTillLeafNodes (BVHNode< T > const *const node)=0
virtual bool TestOverlapWithTillLeafNodes (BVHTree< T > const *const that)=0
virtual void Update (std::set< BVHNode< T > * > &nodeSet)
 Update the BVH tree with a set of nodes to update.
virtual void Update ()
 Update the whole BVH tree.
virtual ~BVHTree ()

Protected Member Functions

int CountLeafNodes (BVHNode< T > const *const node) const
int CountNodes (BVHNode< T > const *const node) const
void FindListOfLeafNodes ()
 Find and store the list of leaf nodes of this BVH tree.
void FindListOfLeafNodes (BVHNode< T > *node, std::set< BVHNode< T > * > &leafNodeSet)
 Find and return the list of leaf nodes of the argument node.
std::set< BVHNode< T > * > & GetListOfLeafNodes ()
 Get the stored list of leaf nodes of this BVH tree.
virtual bool TestOverlap_vs_BinarySphere (BVHNode< T > const *const nodeA, Matrix4x4< T > const &transformA, BVHNode< T > const *const nodeB, Matrix4x4< T > const &transformB)=0
virtual bool TestOverlap_vs_BinarySphere (BVHNode< T > const *const nodeA, Matrix4x4< T > const &transformA, BVHNode< T > const *const nodeB)=0
virtual bool TestOverlap_vs_BinarySphere (BVHNode< T > const *const nodeA, BVHNode< T > const *const nodeB, Matrix4x4< T > const &transformB)=0
virtual bool TestOverlap_vs_BinarySphere (BVHNode< T > const *const nodeA, BVHNode< T > const *const nodeB)=0
virtual bool TestOverlap_vs_BinarySphere_TillLeafNodes (BVHNode< T > const *const nodeA, Matrix4x4< T > const &transformA, BVHNode< T > const *const nodeB, Matrix4x4< T > const &transformB)=0
virtual bool TestOverlap_vs_BinarySphere_TillLeafNodes (BVHNode< T > const *const nodeA, Matrix4x4< T > const &transformA, BVHNode< T > const *const nodeB)=0
virtual bool TestOverlap_vs_BinarySphere_TillLeafNodes (BVHNode< T > const *const nodeA, BVHNode< T > const *const nodeB, Matrix4x4< T > const &transformB)=0
virtual bool TestOverlap_vs_BinarySphere_TillLeafNodes (BVHNode< T > const *const nodeA, BVHNode< T > const *const nodeB)=0
virtual bool TestOverlap_vs_BV (BVHNode< T > const *const nodeA, Matrix4x4< T > const &transformA, BoundingVolume< T > const *const pBV, Matrix4x4< T > const &transformB)=0
virtual bool TestOverlap_vs_BV (BVHNode< T > const *const nodeA, Matrix4x4< T > const &transformA, BoundingVolume< T > const *const pBV)=0
virtual bool TestOverlap_vs_BV (BVHNode< T > const *const nodeA, BoundingVolume< T > const *const pBV, Matrix4x4< T > const &transformB)=0
virtual bool TestOverlap_vs_BV (BVHNode< T > const *const nodeA, BoundingVolume< T > const *const pBV)=0
virtual bool TestOverlap_vs_BV_TillLeafNodes (BVHNode< T > const *const nodeA, Matrix4x4< T > const &transformA, BoundingVolume< T > const *const pBV, Matrix4x4< T > const &transformB)=0
virtual bool TestOverlap_vs_BV_TillLeafNodes (BVHNode< T > const *const nodeA, Matrix4x4< T > const &transformA, BoundingVolume< T > const *const pBV)=0
virtual bool TestOverlap_vs_BV_TillLeafNodes (BVHNode< T > const *const nodeA, BoundingVolume< T > const *const pBV, Matrix4x4< T > const &transformB)=0
virtual bool TestOverlap_vs_BV_TillLeafNodes (BVHNode< T > const *const nodeA, BoundingVolume< T > const *const pBV)=0

Static Protected Member Functions

static BVHTree< T > * BAABBBuild (TransformationSupport< T > &transform, const std::list< HEFace< T > * > &heFaceList, BVHTree< T > *cdtree)
static void BAABBBuildChildren (BVHNode< T > *pParentNode, const std::list< HEFace< T > * > &heFaceList, Vector3< T > const &principleVector)
static int BAABBDetermineFaceGroup (HEFace< T > *face, const Vector3< T > &center, const Vector3< T > &direction)
static void BAABBDivideToFaceGroups (const std::list< HEFace< T > * > &faces, std::list< HEFace< T > * > &group1, std::list< HEFace< T > * > &group2, const Vector3< T > &center, const Vector3< T > &direction)
static BVHTree< T > * BOBBBuild (TransformationSupport< T > &transform, const std::list< HEFace< T > * > &heFaceList, BVHTree< T > *cdtree)
static void BOBBBuildChildren (BVHNode< T > *pParentNode, const std::list< HEFace< T > * > &heFaceList, Vector3< T > const &principleVector)
static int BOBBDetermineFaceGroup (HEFace< T > *face, const Vector3< T > &center, const Vector3< T > &direction)
static void BOBBDivideToFaceGroups (const std::list< HEFace< T > * > &faces, std::list< HEFace< T > * > &group1, std::list< HEFace< T > * > &group2, const Vector3< T > &center, const Vector3< T > &direction)
static BVHNode< T > * CreateBVHNodeBAABB (BVHNode< T > *pParentNode, const std::list< HEFace< T > * > &heFaceList)
static BVHNode< T > * CreateBVHNodeBOBB (BVHNode< T > *pParentNode, const std::list< HEFace< T > * > &heFaceList)
static void FindOBBOfFaceList (const std::list< HEFace< T > * > &heFaceList, Vector3< T > &center, Vector3< T > &U, Vector3< T > &V, Vector3< T > &W)

Protected Attributes

Enum::CD m_eType
 type identifier (see TAPsEnumList.hpp)
int m_iTotalNodes
 number of nodes
BVHNode< T > * m_pRoot
std::vector< BVsAndNodesList< T > > m_svCollidedBVAndNodeList
 for collision detection with a MultiBoundingVolume object
std::vector< BVHNode< T > * > m_svCollidedNode
 for collision detection
std::vector< BVHNode< T > * > m_svCollidedNodeThat
 for collision detection (and for collision detection with a(n) (M)BV
std::set< BVHNode< T > * > m_svLeafNodes
 a set of pointers to the leaf nodes in the BVH tree
TransformationSupport< T > & m_Transform
 a link to a transformation support

Friends

std::ostream & operator<< (std::ostream &output, BVHTree< T > const &obj)

Detailed Description

template<typename T>
class BVHTree< T >

BVHTree class is an abstract class for any Boundary Volume Hierarchy Tree.

Support
Currently only BVHTree of Binary Sphere (BVH_NODE_BINARY_SPHERE) is supported. The extended class is named BVHTree_BinSphere.
Future Plan
To support BVHTree of Binary AABB (BVH_NODE_BINARY_AABB)
To support BVHTree of Binary OBB (BVH_NODE_BINARY_OBB)
Complete Plan
To support BVHTree of Quad (BVH_NODE_QUAD_SPHERE), Octant (BVH_NODE_OCTANT_SPHERE), and Generic Sphere (BVH_NODE_GENERIC_SPHERE)
To support BVHTree of Quad (BVH_NODE_QUAD_AABB), Octant (BVH_NODE_OCTANT_AABB), and Generic AABB (BVH_NODE_GENERIC_AABB)
To support BVHTree of Quad (BVH_NODE_QUAD_OBB), Octant (BVH_NODE_OCTANT_OBB), and Generic OBB (BVH_NODE_GENERIC_OBB)
See also:
TAPsCDLib.hpp for details about Collision Detection implemented in TAPs.

Definition at line 54 of file TAPsBVHTree.hpp.

Constructor & Destructor Documentation

template<typename T>
BEGIN_NAMESPACE_TAPs BVHTree< T >::BVHTree ( TransformationSupport< T > &  transform,
Enum::CD  type = Enum::UNDEFINED_TREE,
int  numOfNodes = 0,
BVHNode< T > *  rootNode = NULL 
) [inline]

Definition at line 18 of file TAPsBVHTree.cpp.

00023     : m_eType( type ), 
00024       m_iTotalNodes( numOfNodes ), 
00025       m_pRoot( rootNode ), 
00026       m_Transform( transform )
00027 {}

template<typename T>
BVHTree< T >::BVHTree ( TransformationSupport< T > &  transform,
HEFaceList< T > *  heFaceList 
) [inline]

Parameters:
transform  I/O: Transform
heFaceList  I/P: half-edge face list

Definition at line 130 of file TAPsBVHTree.hpp.

00130                                                                 : Transform
00131                 HEFaceList<T> * heFaceList )            
00132     {}

template<typename T>
BVHTree< T >::~BVHTree (  )  [inline, virtual]

Definition at line 30 of file TAPsBVHTree.cpp.

00031 {
00032     if ( m_pRoot ) {
00033         delete m_pRoot;
00034         m_pRoot = NULL;
00035     }
00036 }

Member Function Documentation

template<typename T>
BVHTree< T > * BVHTree< T >::BAABBBuild ( TransformationSupport< T > &  transform,
const std::list< HEFace< T > * > &  heFaceList,
BVHTree< T > *  cdtree 
) [inline, static, protected]

Definition at line 269 of file TAPsBVHTree.cpp.

00270                                                       : Transform
00271         const std::list< HEFace<T> * > & heFaceList,    // I/P half-edge face list
00272         BVHTree<T> * cdtree )           // O/P pointer to BVHTree
00273 {
00274     //std::cout << "BAABBBuild (before): " << cdtree << std::endl;
00275     BVHNode<T> *node = CreateBVHNodeBAABB( NULL, heFaceList );
00276     cdtree = new BVHTree<T>( transform, Enum::BVH_TREE_BINARY_AABB, 1, node );
00277     //FindOBBOfFaceList( heFaceList, node );
00278     Vector3<T> U, V, W;
00279     FindOBBOfFaceList( heFaceList, node->GetCenter(), U, V, W );
00280 //  node->listHEFace  = heFaceList;         // DEBUG
00281     if ( node ) BAABBBuildChildren( node, heFaceList, U );
00282     //std::cout << "BAABBBuild (after): " << cdtree << std::endl;
00283     return cdtree;
00284 }

template<typename T>
void BVHTree< T >::BAABBBuildChildren ( BVHNode< T > *  pParentNode,
const std::list< HEFace< T > * > &  heFaceList,
Vector3< T > const &  principleVector 
) [inline, static, protected]

Definition at line 288 of file TAPsBVHTree.cpp.

00292 {
00293     int size = static_cast<int>( heFaceList.size() );
00294     std::list< HEFace<T> * > leftGroup, rightGroup;
00295     //---------------------------------------------------------------
00296     assert( pParentNode );          // ASSERT
00297     BVHNode<T> * leftChild  = NULL;
00298     BVHNode<T> * rightChild = NULL;
00299     //---------------------------------------------------------------
00300     // CASE: one face
00301     // This is a leaf node.
00302     assert( size > 0 );         // ASSERT
00303     if ( 1 == size ) {
00304         return;
00305     }
00306     //---------------------------------------------------------------
00307     // CASE: two faces
00308     // Create Two Leaf Nodes
00309     if ( 2 == size ) {
00310         //-------------------------------------------------
00311         // Separate two faces into left and right groups
00312         std::list< HEFace<T> * >::const_iterator face = heFaceList.begin();
00313         leftGroup.push_back( *face );
00314         ++face;
00315         rightGroup.push_back( *face );
00316         //-------------------------------------------------
00317         // Create Left Leaf Node
00318         leftChild  = CreateBVHNodeBAABB( pParentNode, leftGroup );
00319 //      leftChild->listHEFace  = leftGroup;         // DEBUG
00320         pParentNode->Child( 0, leftChild );
00321         //-------------------------------------------------
00322         // Create Right Leaf Node
00323         rightChild = CreateBVHNodeBAABB( pParentNode, rightGroup );
00324 //      rightChild->listHEFace = rightGroup;        // DEBUG
00325         pParentNode->Child( 1, rightChild );
00326         return;
00327     }
00328     //---------------------------------------------------------------
00329     // CASE: more than two faces
00330     // Didive into two groups
00331     BAABBDivideToFaceGroups(    heFaceList, leftGroup, rightGroup, 
00332                                 pParentNode->GetCenter(), 
00333                                 principleVector );
00334     //---------------------------------------------------------------
00335     // CASE: more than two faces and the divider failed to divide the face list
00336     if (   static_cast<int>( leftGroup.size() )  == size 
00337         || static_cast<int>( rightGroup.size() ) == size ) {
00338         //std::cout << "Total    : " << size;
00339         //std::cout << "; Left  Grp: " << leftGroup.size();
00340         //std::cout << "; Right Grp: " << rightGroup.size() << std::endl;
00341         leftGroup.clear();
00342         rightGroup.clear();
00343         std::list< HEFace<T> * >::const_iterator face = heFaceList.begin();
00344         int i = 0;
00345         for ( ; i < size/2; ++i ) {
00346             leftGroup.push_back( *face );
00347             ++face;
00348         }
00349         for ( ; i < size; ++i ) {
00350             rightGroup.push_back( *face );
00351             ++face;
00352         }
00353     }
00354     Vector3<T> U, V, W;
00355     //---------------------------------------------------------------
00356     // Create Left Child Node
00357     leftChild  = CreateBVHNodeBAABB( pParentNode, leftGroup );
00358     FindOBBOfFaceList( leftGroup, leftChild->GetCenter(), U, V, W );
00359 //  leftChild->listHEFace  = leftGroup;         // DEBUG
00360     pParentNode->Child( 0, leftChild );
00361     BAABBBuildChildren( leftChild, leftGroup, U );
00362     //---------------------------------------------------------------
00363     // Create Right Child Node
00364     rightChild = CreateBVHNodeBAABB( pParentNode, rightGroup );
00365     FindOBBOfFaceList( rightGroup, rightChild->GetCenter(), U, V, W );
00366 //  rightChild->listHEFace = rightGroup;        // DEBUG
00367     pParentNode->Child( 1, rightChild );
00368     BAABBBuildChildren( rightChild, rightGroup, U );
00369 
00370     /*
00371     int size = static_cast<int>( heFaceList.size() );
00372     std::list< HEFace<T> * > leftGroup, rightGroup;
00373     //---------------------------------------------------------------
00374     // Didive into two groups
00375     BAABBDivideToFaceGroups(    heFaceList, leftGroup, rightGroup, 
00376                                 pParentNode->GetCenter(), 
00377                                 principleVector );
00378     //---------------------------------------------------------------
00379     assert( pParentNode );          // ASSERT
00380     BVHNode<T> * leftChild = NULL;
00381     BVHNode<T> * rightChild = NULL;
00382     if ( 2 < static_cast<int>( leftGroup.size() ) && static_cast<int>( leftGroup.size() ) < size ) {
00383         leftChild  = CreateBVHNodeBAABB( pParentNode, leftGroup );
00384         //FindOBBOfFaceList( leftGroup, leftChild );
00385         Vector3<T> U, V, W;
00386         FindOBBOfFaceList( leftGroup, leftChild->GetCenter(), U, V, W );
00387         leftChild->listHEFace  = leftGroup;         // DEBUG
00388         pParentNode->Child( 0, leftChild );
00389         BAABBBuildChildren( leftChild, leftGroup, U );
00390     }
00391     if ( 2 < static_cast<int>( rightGroup.size() ) && static_cast<int>( rightGroup.size() ) < size ) {
00392         rightChild = CreateBVHNodeBAABB( pParentNode, rightGroup );
00393         //FindOBBOfFaceList( rightGroup, rightChild );
00394         Vector3<T> U, V, W;
00395         FindOBBOfFaceList( rightGroup, rightChild->GetCenter(), U, V, W );
00396         rightChild->listHEFace = rightGroup;        // DEBUG
00397         pParentNode->Child( 1, rightChild );
00398         BAABBBuildChildren( rightChild, rightGroup, U );
00399     }
00400     //*/
00401 }

template<typename T>
int BVHTree< T >::BAABBDetermineFaceGroup ( HEFace< T > *  face,
const Vector3< T > &  center,
const Vector3< T > &  direction 
) [inline, static, protected]

Definition at line 405 of file TAPsBVHTree.cpp.

00408 {
00409     //-------------------------------------------------------------------------
00410     // Divided into an axis positive and negative
00411     //---------------------------------------------------------------
00412     // REMARK:
00413     //   To speed thing up, we can evaluate only the first vertex of the polygon.
00414     //---------------------------------------------------------------
00415     // Determine from all vertices
00416     int value = 0;
00417     HEHalfEdge<T> * firstHalfEdge = face->IncidentHalfEdge();
00418     HEHalfEdge<T> * halfEdge = firstHalfEdge;
00419     Vector3<T> vertex;
00420     do {
00421         //vertex = halfEdge->Vertex()->GetPosition() - center;
00422         //if ( vertex.GetX() >= 0 ) ++value;
00423         //else                      --value;
00424         if ( (halfEdge->Vertex()->GetPosition() - center) * direction >= 0 )
00425             ++value;
00426         else
00427             --value;
00428         halfEdge = halfEdge->Next();
00429     } while ( halfEdge != firstHalfEdge );
00430     //---------------------------------------------------------------
00431     // Determine the group (left or right)
00432     return  value >= 0 ? 1 : 0;
00433 }

template<typename T>
void BVHTree< T >::BAABBDivideToFaceGroups ( const std::list< HEFace< T > * > &  faces,
std::list< HEFace< T > * > &  group1,
std::list< HEFace< T > * > &  group2,
const Vector3< T > &  center,
const Vector3< T > &  direction 
) [inline, static, protected]

Definition at line 436 of file TAPsBVHTree.cpp.

00442 {
00443     std::list< HEFace<T> * >::const_iterator face;
00444     for ( face = inputFaces.begin(); face != inputFaces.end(); ++face ) {
00445         if ( BAABBDetermineFaceGroup( *face, center, direction ) == 1 )
00446             group1.push_back( *face );
00447         else
00448             group2.push_back( *face );
00449     }
00450 }

template<typename T>
BVHTree< T > * BVHTree< T >::BOBBBuild ( TransformationSupport< T > &  transform,
const std::list< HEFace< T > * > &  heFaceList,
BVHTree< T > *  cdtree 
) [inline, static, protected]

Definition at line 547 of file TAPsBVHTree.cpp.

00548                                                       : Transform
00549         const std::list< HEFace<T> * > & heFaceList,    // I/P half-edge face list
00550         BVHTree<T> * cdtree )           // O/P pointer to BVHTree
00551 {
00552     //std::cout << "BOBBBuild (before): " << cdtree << std::endl;
00553     BVHNode<T> *node = CreateBVHNodeBOBB( NULL, heFaceList );
00554     cdtree = new BVHTree<T>( transform, Enum::BVH_TREE_BINARY_OBB, 1, node );
00555     //FindOBBOfFaceList( heFaceList, node );
00556     Vector3<T> U, V, W;
00557     FindOBBOfFaceList( heFaceList, node->GetCenter(), U, V, W );
00558     node->SetPrincipleComponents( U, V, W );
00559 //  node->listHEFace  = heFaceList;         // DEBUG
00560     if ( node ) BOBBBuildChildren( node, heFaceList, U );
00561     //std::cout << "BOBBBuild (after): " << cdtree << std::endl;
00562 
00563     FindListOfLeafNodes();
00564 
00565     return cdtree;
00566 }

template<typename T>
void BVHTree< T >::BOBBBuildChildren ( BVHNode< T > *  pParentNode,
const std::list< HEFace< T > * > &  heFaceList,
Vector3< T > const &  principleVector 
) [inline, static, protected]

Definition at line 570 of file TAPsBVHTree.cpp.

00574 {
00575     int size = static_cast<int>( heFaceList.size() );
00576     std::list< HEFace<T> * > leftGroup, rightGroup;
00577     //---------------------------------------------------------------
00578     assert( pParentNode );          // ASSERT
00579     BVHNode<T> * leftChild  = NULL;
00580     BVHNode<T> * rightChild = NULL;
00581     //---------------------------------------------------------------
00582     // CASE: one face
00583     // This is a leaf node.
00584     assert( size > 0 );         // ASSERT
00585     if ( 1 == size ) {
00586         return;
00587     }
00588     //---------------------------------------------------------------
00589     // CASE: two faces
00590     // Create Two Leaf Nodes
00591     if ( 2 == size ) {
00592         //-------------------------------------------------
00593         // Separate two faces into left and right groups
00594         std::list< HEFace<T> * >::const_iterator face = heFaceList.begin();
00595         leftGroup.push_back( *face );
00596         ++face;
00597         rightGroup.push_back( *face );
00598         //-------------------------------------------------
00599         // Create Left Leaf Node
00600         leftChild  = CreateBVHNodeBOBB( pParentNode, leftGroup );
00601 //      leftChild->listHEFace  = leftGroup;         // DEBUG
00602         pParentNode->Child( 0, leftChild );
00603         //-------------------------------------------------
00604         // Create Right Leaf Node
00605         rightChild = CreateBVHNodeBOBB( pParentNode, rightGroup );
00606 //      rightChild->listHEFace = rightGroup;        // DEBUG
00607         pParentNode->Child( 1, rightChild );
00608         return;
00609     }
00610     //---------------------------------------------------------------
00611     // Didive into two groups
00612     // CASE: more than two faces
00613     BOBBDivideToFaceGroups( heFaceList, leftGroup, rightGroup, 
00614                                 pParentNode->GetCenter(), 
00615                                 principleVector );
00616     //---------------------------------------------------------------
00617     // CASE: more than two faces and the divider failed to divide the face list
00618     if (   static_cast<int>( leftGroup.size() )  == size 
00619         || static_cast<int>( rightGroup.size() ) == size ) {
00620         //std::cout << "Total    : " << size;
00621         //std::cout << "; Left  Grp: " << leftGroup.size();
00622         //std::cout << "; Right Grp: " << rightGroup.size() << std::endl;
00623         leftGroup.clear();
00624         rightGroup.clear();
00625         std::list< HEFace<T> * >::const_iterator face = heFaceList.begin();
00626         int i = 0;
00627         for ( ; i < size/2; ++i ) {
00628             leftGroup.push_back( *face );
00629             ++face;
00630         }
00631         for ( ; i < size; ++i ) {
00632             rightGroup.push_back( *face );
00633             ++face;
00634         }
00635     }
00636     Vector3<T> U, V, W;
00637     //---------------------------------------------------------------
00638     // Create Left Child Node
00639     leftChild  = CreateBVHNodeBOBB( pParentNode, leftGroup );
00640     FindOBBOfFaceList( leftGroup, leftChild->GetCenter(), U, V, W );
00641     leftChild->SetPrincipleComponents( U, V, W );
00642 //  leftChild->listHEFace  = leftGroup;         // DEBUG
00643     pParentNode->Child( 0, leftChild );
00644     BOBBBuildChildren( leftChild, leftGroup, U );
00645     //---------------------------------------------------------------
00646     // Create Right Child Node
00647     rightChild = CreateBVHNodeBOBB( pParentNode, rightGroup );
00648     FindOBBOfFaceList( rightGroup, rightChild->GetCenter(), U, V, W );
00649     rightChild->SetPrincipleComponents( U, V, W );
00650 //  rightChild->listHEFace = rightGroup;        // DEBUG
00651     pParentNode->Child( 1, rightChild );
00652     BOBBBuildChildren( rightChild, rightGroup, U );
00653 
00654     /*
00655     int size = static_cast<int>( heFaceList.size() );
00656     std::list< HEFace<T> * > leftGroup, rightGroup;
00657     //---------------------------------------------------------------
00658     // Didive into two groups
00659     BOBBDivideToFaceGroups( heFaceList, leftGroup, rightGroup, 
00660                                 pParentNode->GetCenter(), 
00661                                 principleVector );
00662     //---------------------------------------------------------------
00663     assert( pParentNode );          // ASSERT
00664     BVHNode<T> * leftChild = NULL;
00665     BVHNode<T> * rightChild = NULL;
00666     if ( 2 < static_cast<int>( leftGroup.size() ) && static_cast<int>( leftGroup.size() ) < size ) {
00667         leftChild  = CreateBVHNodeBOBB( pParentNode, leftGroup );
00668         //FindOBBOfFaceList( leftGroup, leftChild );
00669         Vector3<T> U, V, W;
00670         FindOBBOfFaceList( leftGroup, leftChild->GetCenter(), U, V, W );
00671         leftChild->SetPrincipleComponents( U, V, W );
00672         leftChild->listHEFace  = leftGroup;         // DEBUG
00673         pParentNode->Child( 0, leftChild );
00674         BOBBBuildChildren( leftChild, leftGroup, U );
00675     }
00676     if ( 2 < static_cast<int>( rightGroup.size() ) && static_cast<int>( rightGroup.size() ) < size ) {
00677         rightChild = CreateBVHNodeBOBB( pParentNode, rightGroup );
00678         //FindOBBOfFaceList( rightGroup, rightChild );
00679         Vector3<T> U, V, W;
00680         FindOBBOfFaceList( rightGroup, rightChild->GetCenter(), U, V, W );
00681         rightChild->SetPrincipleComponents( U, V, W );
00682         rightChild->listHEFace = rightGroup;        // DEBUG
00683         pParentNode->Child( 1, rightChild );
00684         BOBBBuildChildren( rightChild, rightGroup, U );
00685     }
00686     //*/
00687 }

template<typename T>
int BVHTree< T >::BOBBDetermineFaceGroup ( HEFace< T > *  face,
const Vector3< T > &  center,
const Vector3< T > &  direction 
) [inline, static, protected]

Definition at line 691 of file TAPsBVHTree.cpp.

00694 {
00695     //-------------------------------------------------------------------------
00696     // Divided into an axis positive and negative
00697     //---------------------------------------------------------------
00698     // REMARK:
00699     //   To speed thing up, we can evaluate only the first vertex of the polygon.
00700     //---------------------------------------------------------------
00701     // Determine from all vertices
00702     int value = 0;
00703     HEHalfEdge<T> * firstHalfEdge = face->IncidentHalfEdge();
00704     HEHalfEdge<T> * halfEdge = firstHalfEdge;
00705     Vector3<T> vertex;
00706     do {
00707         //vertex = halfEdge->Vertex()->GetPosition() - center;
00708         //if ( vertex.GetX() >= 0 ) ++value;
00709         //else                      --value;
00710         if ( (halfEdge->Vertex()->GetPosition() - center) * direction >= 0 )
00711             ++value;
00712         else
00713             --value;
00714         halfEdge = halfEdge->Next();
00715     } while ( halfEdge != firstHalfEdge );
00716     //---------------------------------------------------------------
00717     // Determine the group (left or right)
00718     return  value >= 0 ? 1 : 0;
00719 }

template<typename T>
void BVHTree< T >::BOBBDivideToFaceGroups ( const std::list< HEFace< T > * > &  faces,
std::list< HEFace< T > * > &  group1,
std::list< HEFace< T > * > &  group2,
const Vector3< T > &  center,
const Vector3< T > &  direction 
) [inline, static, protected]

Definition at line 722 of file TAPsBVHTree.cpp.

00728 {
00729     std::list< HEFace<T> * >::const_iterator face;
00730     for ( face = inputFaces.begin(); face != inputFaces.end(); ++face ) {
00731         if ( BOBBDetermineFaceGroup( *face, center, direction ) == 1 )
00732             group1.push_back( *face );
00733         else
00734             group2.push_back( *face );
00735     }
00736 }

template<typename T>
int BVHTree< T >::CountLeafNodes ( BVHNode< T > const *const   node  )  const [inline, protected]

Definition at line 106 of file TAPsBVHTree.cpp.

00107 {
00108     //if ( node->listHEFace.size() == 1 ) {
00109     if ( node->IsLeaf() ) {
00110         return 1;
00111     }
00112     //---------------------------------------------------------------
00113     int numOfLeafNodes = 0;
00114     for ( int i = 0; i < node->GetNumOfChildren(); ++i ) {
00115         if ( node->Child(i) != NULL ) {
00116             numOfLeafNodes += CountLeafNodes( node->Child(i) );
00117         }
00118     }
00119     return numOfLeafNodes;
00120 }

template<typename T>
int BVHTree< T >::CountLeafNodes (  )  const [inline]

Definition at line 97 of file TAPsBVHTree.cpp.

00098 {
00099     if ( m_pRoot == NULL )      return 0;
00100     //---------------------------------------------------------------
00101     return CountLeafNodes( m_pRoot );
00102 }

template<typename T>
int BVHTree< T >::CountNodes ( BVHNode< T > const *const   node  )  const [inline, protected]

Definition at line 83 of file TAPsBVHTree.cpp.

00084 {
00085     //---------------------------------------------------------------
00086     int numOfNodes = 1;
00087     for ( int i = 0; i < node->GetNumOfChildren(); ++i ) {
00088         if ( node->Child(i) != NULL ) {
00089             numOfNodes += CountNodes( node->Child(i) );
00090         }
00091     }
00092     return numOfNodes;
00093 }

template<typename T>
int BVHTree< T >::CountNodes (  )  const [inline]

Definition at line 74 of file TAPsBVHTree.cpp.

00075 {
00076     if ( m_pRoot == NULL )      return 0;
00077     //---------------------------------------------------------------
00078     return CountNodes( m_pRoot );
00079 }

template<typename T>
BVHNode< T > * BVHTree< T >::CreateBVHNodeBAABB ( BVHNode< T > *  pParentNode,
const std::list< HEFace< T > * > &  heFaceList 
) [inline, static, protected]

Definition at line 454 of file TAPsBVHTree.cpp.

00457 {
00458     //*
00459     Vector3<T> AABB[2];
00460     //HEVertex<T> * vertex = m_listVertex->Head();
00461     std::list< HEFace<T> * >::const_iterator face = heFaceList.begin();
00462     HEHalfEdge<T> * firstHalfEdge = (*face)->IncidentHalfEdge();
00463     HEHalfEdge<T> * halfEdge = firstHalfEdge;
00464     Vector3<T> vertex = halfEdge->Vertex()->GetPosition();
00465     AABB[0] = AABB[1] = vertex;
00466     //---------------------------------------------------------------
00467     // For Each Face
00468     for ( ; face != heFaceList.end(); ++face ) {
00469         halfEdge = firstHalfEdge = (*face)->IncidentHalfEdge();
00470         //-------------------------------------------------
00471         // For Each Vertex
00472         do {
00473             vertex = halfEdge->Vertex()->GetPosition();
00474             // Find the lowest an the highest of x, y, and z
00475             // AABB[0] is min and AABB[1] is max
00476             if      ( AABB[0][0] > vertex[0] )  AABB[0][0] = vertex[0];
00477             else if ( AABB[1][0] < vertex[0] )  AABB[1][0] = vertex[0];
00478             if      ( AABB[0][1] > vertex[1] )  AABB[0][1] = vertex[1];
00479             else if ( AABB[1][1] < vertex[1] )  AABB[1][1] = vertex[1];
00480             if      ( AABB[0][2] > vertex[2] )  AABB[0][2] = vertex[2];
00481             else if ( AABB[1][2] < vertex[2] )  AABB[1][2] = vertex[2];
00482             // Next vertex
00483             halfEdge = halfEdge->Next();
00484         } while ( halfEdge != firstHalfEdge );
00485     }
00486     /*
00487     //---------------------------------------------------------------
00488     // Find the bounding volume center from the AABB
00489     Vector3<T> vCenter( ( AABB[0][0] + AABB[1][0] ) / 2.0,
00490                         ( AABB[0][1] + AABB[1][1] ) / 2.0,
00491                         ( AABB[0][2] + AABB[1][2] ) / 2.0 );
00492     //*/
00493     /*
00494     //---------------------------------------------------------------
00495     // Find the Sphere Bounding Volume
00496     T radius = 0, squaredLength;
00497     for ( face = heFaceList.begin(); face != heFaceList.end(); ++face ) {
00498         halfEdge = firstHalfEdge = (*face)->IncidentHalfEdge();
00499         //-------------------------------------------------
00500         do {
00501             vertex = halfEdge->Vertex()->GetPosition();
00502             squaredLength = (vertex - vCenter).SquaredLength();
00503             if ( squaredLength > radius )   radius = squaredLength;
00504             halfEdge = halfEdge->Next();
00505         } while ( halfEdge != firstHalfEdge );
00506     }
00507     radius = sqrt( radius );
00508     //*/
00509     //---------------------------------------------------------------
00510     // Make the root node
00511     //-------------------------------------------
00512     // BVHNode Constructor
00513     //   BVHNode<T>(    Enum::CD type,
00514     //                  int id, 
00515     //                  BVHNode<T> * parent, 
00516     //                  BVHNode<T> ** children )
00517     //-------------------------------------------
00518     BVHNode<T> * node = new BVHNode<T>( Enum::BVH_NODE_BINARY_AABB, 
00519                                 -1, pParentNode, NULL );
00520     //std::cout << node << "\n";
00521     //std::cout << node->GetCenter() << std::endl;
00522     //node->SetCenter( vCenter );
00523     node->SetMinPt( AABB[0] );
00524     node->SetMaxPt( AABB[1] );
00525     //std::cout << node->GetCenter() << std::endl;
00526     //node->SetRadius( radius );
00527     return node;
00528 }

template<typename T>
BVHNode< T > * BVHTree< T >::CreateBVHNodeBOBB ( BVHNode< T > *  pParentNode,
const std::list< HEFace< T > * > &  heFaceList 
) [inline, static, protected]

Definition at line 740 of file TAPsBVHTree.cpp.

00743 {
00744     //*
00745     Vector3<T> AABB[2];
00746     //HEVertex<T> * vertex = m_listVertex->Head();
00747     std::list< HEFace<T> * >::const_iterator face = heFaceList.begin();
00748     HEHalfEdge<T> * firstHalfEdge = (*face)->IncidentHalfEdge();
00749     HEHalfEdge<T> * halfEdge = firstHalfEdge;
00750     Vector3<T> vertex = halfEdge->Vertex()->GetPosition();
00751     AABB[0] = AABB[1] = vertex;
00752     //---------------------------------------------------------------
00753     // For Each Face
00754     for ( ; face != heFaceList.end(); ++face ) {
00755         halfEdge = firstHalfEdge = (*face)->IncidentHalfEdge();
00756         //-------------------------------------------------
00757         // For Each Vertex
00758         do {
00759             vertex = halfEdge->Vertex()->GetPosition();
00760             // Find the lowest an the highest of x, y, and z
00761             // AABB[0] is min and AABB[1] is max
00762             if      ( AABB[0][0] > vertex[0] )  AABB[0][0] = vertex[0];
00763             else if ( AABB[1][0] < vertex[0] )  AABB[1][0] = vertex[0];
00764             if      ( AABB[0][1] > vertex[1] )  AABB[0][1] = vertex[1];
00765             else if ( AABB[1][1] < vertex[1] )  AABB[1][1] = vertex[1];
00766             if      ( AABB[0][2] > vertex[2] )  AABB[0][2] = vertex[2];
00767             else if ( AABB[1][2] < vertex[2] )  AABB[1][2] = vertex[2];
00768             // Next vertex
00769             halfEdge = halfEdge->Next();
00770         } while ( halfEdge != firstHalfEdge );
00771     }
00772     //---------------------------------------------------------------
00773     // Find the bounding volume center from the AABB
00774     Vector3<T> vCenter( ( AABB[0][0] + AABB[1][0] ) / 2.0,
00775                         ( AABB[0][1] + AABB[1][1] ) / 2.0,
00776                         ( AABB[0][2] + AABB[1][2] ) / 2.0 );
00777     /*
00778     //---------------------------------------------------------------
00779     // Find the Sphere Bounding Volume
00780     T radius = 0, squaredLength;
00781     for ( face = heFaceList.begin(); face != heFaceList.end(); ++face ) {
00782         halfEdge = firstHalfEdge = (*face)->IncidentHalfEdge();
00783         //-------------------------------------------------
00784         do {
00785             vertex = halfEdge->Vertex()->GetPosition();
00786             squaredLength = (vertex - vCenter).SquaredLength();
00787             if ( squaredLength > radius )   radius = squaredLength;
00788             halfEdge = halfEdge->Next();
00789         } while ( halfEdge != firstHalfEdge );
00790     }
00791     radius = sqrt( radius );
00792     //*/
00793     //---------------------------------------------------------------
00794     // Make the root node
00795     //-------------------------------------------
00796     // BVHNode Constructor
00797     //   BVHNode<T>(    Enum::CD type,
00798     //                  int id, 
00799     //                  BVHNode<T> * parent, 
00800     //                  BVHNode<T> ** children )
00801     //-------------------------------------------
00802     BVHNode<T> * node = new BVHNode<T>( Enum::BVH_NODE_BINARY_OBB, 
00803                                 -1, pParentNode, NULL );
00804     //std::cout << node << "\n";
00805     //std::cout << node->GetCenter() << std::endl;
00806     node->SetCenter( vCenter );
00807     //std::cout << node->GetCenter() << std::endl;
00808     //node->SetRadius( radius );
00809     return node;
00810 }

template<typename T>
void BVHTree< T >::FindListOfLeafNodes (  )  [inline, protected]

Find and store the list of leaf nodes of this BVH tree.

Definition at line 167 of file TAPsBVHTree.hpp.

00168     { FindListOfLeafNodes( m_pRoot, m_svLeafNodes ); }

template<typename T>
void BVHTree< T >::FindListOfLeafNodes ( BVHNode< T > *  node,
std::set< BVHNode< T > * > &  leafNodeSet 
) [inline, protected]

Find and return the list of leaf nodes of the argument node.

Definition at line 124 of file TAPsBVHTree.cpp.

00126 {
00127     if ( node->IsLeaf() ) {
00128         leafNodeSet.insert( node );
00129         return;
00130     }
00131     //---------------------------------------------------------------
00132     for ( int i = 0; i < node->GetNumOfChildren(); ++i ) {
00133         if ( node->Child(i) != NULL ) {
00134             FindListOfLeafNodes( node->Child(i), leafNodeSet );
00135         }
00136     }
00137 }

template<typename T>
void BVHTree< T >::FindOBBOfFaceList ( const std::list< HEFace< T > * > &  heFaceList,
Vector3< T > &  center,
Vector3< T > &  U,
Vector3< T > &  V,
Vector3< T > &  W 
) [inline, static, protected]

Definition at line 857 of file TAPsBVHTree.cpp.

00858                                                               : face list
00859             Vector3<T> & center,    // O/P: center
00860             Vector3<T> & U,         // O/P: 1st principle component
00861             Vector3<T> & V,         // O/P: 2nd principle component
00862             Vector3<T> & W )        // O/P: 3rd principle component
00863 {
00864     //if ( heFaceList.size() == 0 ) return;
00865     assert( heFaceList.size() > 0 );            // ASSERT
00866     Vector3<T>      M( 0,0,0 );                 // Mean
00867     Matrix3x3<T>    C( 0,0,0,0,0,0,0,0,0 );     // Covariance Matrix
00868     //---------------------------------------------------------------
00869     std::list< HEFace<T> * >::const_iterator face;
00870     HEHalfEdge<T> * firstHalfEdge;
00871     HEHalfEdge<T> * halfEdge;
00872     Vector3<T>      vertex;
00873     Vector3<T>      centroid;
00874     int count, totalVertices = 0;
00875     //---------------------------------------------------------------
00876     // Calculate MEAN
00877     // For each face (polygon)
00878     for ( face = heFaceList.begin(); face != heFaceList.end(); ++face ) {
00879         //-------------------------------------------------
00880         // Determine the number of vertices of the face
00881         firstHalfEdge = halfEdge = (*face)->IncidentHalfEdge();
00882         count = 0;
00883         do {
00884             ++count;
00885             halfEdge = halfEdge->Next();    // next halfedge
00886         } while ( halfEdge != firstHalfEdge );
00887         //-------------------------------------------------
00888         // Triangle (or lower) Case
00889         if ( count <= 3 ) {
00890             totalVertices += count;
00891             do {
00892                 //-------------------------------
00893                 // Find Mean
00894                 M += halfEdge->Vertex()->GetPosition();
00895                 //-------------------------------
00896                 halfEdge = halfEdge->Next();    // next halfedge
00897             } while ( halfEdge != firstHalfEdge );
00898         }
00899         //-------------------------------------------------
00900         // Four or More Vertices Case
00901         else {
00902             totalVertices += 3*count;   // increased by 3 * count
00903             centroid.SetXYZ( 0,0,0 );
00904             do {
00905                 vertex = halfEdge->Vertex()->GetPosition();
00906                 centroid += vertex;
00907                 //-------------------------------
00908                 // Find Mean
00909                 M += vertex*2;
00910                 //-------------------------------
00911                 halfEdge = halfEdge->Next();    // next halfedge
00912             } while ( halfEdge != firstHalfEdge );
00913             //centroid /= count;
00914             M += centroid;
00915         }
00916         //-------------------------------------------------
00917     }
00918     M /= totalVertices;     // Final Mean
00919     //---------------------------------------------------------------
00920     // Calculate COVARIANCE MATRIX
00921     // For each face (polygon)
00922     for ( face = heFaceList.begin(); face != heFaceList.end(); ++face ) {
00923         //-------------------------------------------------
00924         // Determine the number of vertices of the face
00925         firstHalfEdge = halfEdge = (*face)->IncidentHalfEdge();
00926         count = 0;
00927         do {
00928             ++count;
00929             halfEdge = halfEdge->Next();    // next halfedge
00930         } while ( halfEdge != firstHalfEdge );
00931         //-------------------------------------------------
00932         // Triangle (or lower) Case
00933         if ( count <= 3 ) {
00934             //totalVertices += count;
00935             do {
00936                 vertex = halfEdge->Vertex()->GetPosition() - M;
00937                 //-------------------------------
00938                 // Covariance Matrix is a 3x3 symmatric matrix
00939                 C[0] += vertex.GetX() * vertex.GetX() * 2;  // C_{11}
00940                 C[4] += vertex.GetY() * vertex.GetY() * 2;  // C_{22}
00941                 C[8] += vertex.GetZ() * vertex.GetZ() * 2;  // C_{33}
00942                 C[1] += vertex.GetX() * vertex.GetY() * 2;  // C_{12} = C_{21}
00943                 C[2] += vertex.GetX() * vertex.GetZ() * 2;  // C_{13} = C_{31}
00944                 C[5] += vertex.GetY() * vertex.GetZ() * 2;  // C_{23} = C_{32}
00945                 //-------------------------------
00946                 halfEdge = halfEdge->Next();    // next halfedge
00947             } while ( halfEdge != firstHalfEdge );
00948         }
00949         //-------------------------------------------------
00950         // Four or More Vertices Case
00951         else {
00952             //totalVertices += 3*count; // increased by 3 * count
00953             centroid.SetXYZ( 0,0,0 );
00954             do {
00955                 vertex = halfEdge->Vertex()->GetPosition() - M;
00956                 centroid += vertex;
00957                 //-------------------------------
00958                 // Covariance Matrix is a 3x3 symmatric matrix
00959                 C[0] += vertex.GetX() * vertex.GetX();      // C_{11}
00960                 C[4] += vertex.GetY() * vertex.GetY();      // C_{22}
00961                 C[8] += vertex.GetZ() * vertex.GetZ();      // C_{33}
00962                 C[1] += vertex.GetX() * vertex.GetY();      // C_{12} = C_{21}
00963                 C[2] += vertex.GetX() * vertex.GetZ();      // C_{13} = C_{31}
00964                 C[5] += vertex.GetY() * vertex.GetZ();      // C_{23} = C_{32}
00965                 //-------------------------------
00966                 halfEdge = halfEdge->Next();    // next halfedge
00967             } while ( halfEdge != firstHalfEdge );
00968             vertex = centroid/count - M;
00969             C[0] += vertex.GetX() * vertex.GetX();      // C_{11}
00970             C[4] += vertex.GetY() * vertex.GetY();      // C_{22}
00971             C[8] += vertex.GetZ() * vertex.GetZ();      // C_{33}
00972             C[1] += vertex.GetX() * vertex.GetY();      // C_{12} = C_{21}
00973             C[2] += vertex.GetX() * vertex.GetZ();      // C_{13} = C_{31}
00974             C[5] += vertex.GetY() * vertex.GetZ();      // C_{23} = C_{32}
00975         }
00976         //-------------------------------------------------
00977     }
00978     //---------------------------------------------------------------
00979     C[3] = C[1];
00980     C[6] = C[2];
00981     C[7] = C[5];
00982     C /= totalVertices;     // Final Covariance Matrix
00983     //---------------------------------------------------------------
00984     T l[3];
00985     CGMath<T>::EigValsVecsOf3x3SymMatrix( 
00986         C, l[0], l[1], l[2], U, V, W );
00987     //---------------------------------------------------------------
00988     // Find the length of each principle component
00989     Vector3<T> vec;
00990     T length, positive[3] = {0,0,0}, negative[3] = {0,0,0};
00991     //---------------------------------------------------------------
00992     // For each face (polygon)
00993     for ( face = heFaceList.begin(); face != heFaceList.end(); ++face ) {
00994         //-------------------------------------------------
00995         // For each vertex of the face
00996         firstHalfEdge = halfEdge = (*face)->IncidentHalfEdge();
00997         do {
00998             vec = halfEdge->Vertex()->GetPosition() - center;
00999             length = vec * U;
01000             if      ( length > positive[0] )    positive[0] = length;
01001             else if ( length < negative[0] )    negative[0] = length;
01002             length = vec * V;
01003             if      ( length > positive[1] )    positive[1] = length;
01004             else if ( length < negative[1] )    negative[1] = length;
01005             length = vec * W;
01006             if      ( length > positive[2] )    positive[2] = length;
01007             else if ( length < negative[2] )    negative[2] = length;
01008             halfEdge = halfEdge->Next();    // next halfedge
01009         } while ( halfEdge != firstHalfEdge );
01010         //-------------------------------------------------
01011     }
01012     //---------------------------------------------------------------
01013     // Adjust the center and the length of principle components
01014     T adjustedValue;
01015     length = (positive[0] - negative[0]) / 2.0;
01016     adjustedValue = positive[0] - length;
01017     center = center + U*adjustedValue;
01018     U *= length;
01019     length = (positive[1] - negative[1]) / 2.0;
01020     adjustedValue = positive[1] - length;
01021     center = center + V*adjustedValue;
01022     V *= length;
01023     length = (positive[2] - negative[2]) / 2.0;
01024     adjustedValue = positive[2] - length;
01025     center = center + W*adjustedValue;
01026     W *= length;
01027     //---------------------------------------------------------------
01028 }

template<typename T>
virtual std::vector< BVsAndNodesList<T> >& BVHTree< T >::GetListOfCollidedBoundingVolumesAndNodes (  )  [inline, virtual]

Definition at line 236 of file TAPsBVHTree.hpp.

00236 { return m_svCollidedBVAndNodeList; }

template<typename T>
virtual std::vector< BVHNode<T> * >& BVHTree< T >::GetListOfCollidedNodes (  )  [inline, virtual]

Definition at line 234 of file TAPsBVHTree.hpp.

00234 { return m_svCollidedNode; }

template<typename T>
virtual std::vector< BVHNode<T> * >& BVHTree< T >::GetListOfCollidedNodesThat (  )  [inline, virtual]

Definition at line 235 of file TAPsBVHTree.hpp.

00235 { return m_svCollidedNodeThat; }

template<typename T>
std::set< BVHNode<T> * >& BVHTree< T >::GetListOfLeafNodes (  )  [inline, protected]

Get the stored list of leaf nodes of this BVH tree.

Definition at line 163 of file TAPsBVHTree.hpp.

00164     { return m_svLeafNodes; }

template<typename T>
int BVHTree< T >::GetNumOfNodes (  )  const [inline]

Definition at line 138 of file TAPsBVHTree.hpp.

00138 { return m_iTotalNodes; }

template<typename T>
TransformationSupport<T>& BVHTree< T >::GetTransform (  )  [inline]

Definition at line 148 of file TAPsBVHTree.hpp.

00149         { return m_Transform; }

template<typename T>
TransformationSupport<T> const& BVHTree< T >::GetTransform (  )  const [inline]

Definition at line 146 of file TAPsBVHTree.hpp.

00147         { return m_Transform; }

template<typename T>
Enum::CD BVHTree< T >::GetType (  )  const [inline]

Definition at line 137 of file TAPsBVHTree.hpp.

00137 { return m_eType; }

template<typename T>
void BVHTree< T >::Root ( BVHNode< T > *  root  )  [inline]

Definition at line 142 of file TAPsBVHTree.hpp.

00142 { m_pRoot = root; }

template<typename T>
BVHNode<T> const* const BVHTree< T >::Root (  )  const [inline]

Definition at line 141 of file TAPsBVHTree.hpp.

00141 { return m_pRoot; }

template<typename T>
BVHNode<T>* BVHTree< T >::Root (  )  [inline]

Definition at line 140 of file TAPsBVHTree.hpp.

00140 { return m_pRoot; }

template<typename T>
void BVHTree< T >::SetNumOfNodes ( int  n  )  [inline]

Definition at line 139 of file TAPsBVHTree.hpp.

00139 { m_iTotalNodes = n; }

template<typename T>
virtual bool BVHTree< T >::TestIntersectionWithLineSegmentTillLeafNodes ( Vector3< T > const *const   ptA,
Vector3< T > const *const   ptB 
) [pure virtual]

Test intersection with a line segment (without primitive tests) The collided nodes of this BVH tree are stored. Call GetListOfCollidedNodes() to get the collided nodes of this BVH tree.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BinarySphere ( BVHNode< T > const *const   nodeA,
Matrix4x4< T > const &  transformA,
BVHNode< T > const *const   nodeB,
Matrix4x4< T > const &  transformB 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BinarySphere ( BVHNode< T > const *const   nodeA,
Matrix4x4< T > const &  transformA,
BVHNode< T > const *const   nodeB 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BinarySphere ( BVHNode< T > const *const   nodeA,
BVHNode< T > const *const   nodeB,
Matrix4x4< T > const &  transformB 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BinarySphere ( BVHNode< T > const *const   nodeA,
BVHNode< T > const *const   nodeB 
) [protected, pure virtual]

Currently Both TestOverlap_vs_BinarySphere is the same as TestOverlap_vs_BinarySphere_TillLeafNodes. So TestOverlap_vs_BinarySphere need to be complete!!!

Test overlap of a BVH tree with another binary sphere tree with primitive-primitive intersection test.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BinarySphere_TillLeafNodes ( BVHNode< T > const *const   nodeA,
Matrix4x4< T > const &  transformA,
BVHNode< T > const *const   nodeB,
Matrix4x4< T > const &  transformB 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BinarySphere_TillLeafNodes ( BVHNode< T > const *const   nodeA,
Matrix4x4< T > const &  transformA,
BVHNode< T > const *const   nodeB 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BinarySphere_TillLeafNodes ( BVHNode< T > const *const   nodeA,
BVHNode< T > const *const   nodeB,
Matrix4x4< T > const &  transformB 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BinarySphere_TillLeafNodes ( BVHNode< T > const *const   nodeA,
BVHNode< T > const *const   nodeB 
) [protected, pure virtual]

Test overlap of a BVH tree with another binary sphere tree without primitive-primitive intersection test. I.e., stop at leaf-leaf-node intersection test.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BV ( BVHNode< T > const *const   nodeA,
Matrix4x4< T > const &  transformA,
BoundingVolume< T > const *const   pBV,
Matrix4x4< T > const &  transformB 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BV ( BVHNode< T > const *const   nodeA,
Matrix4x4< T > const &  transformA,
BoundingVolume< T > const *const   pBV 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BV ( BVHNode< T > const *const   nodeA,
BoundingVolume< T > const *const   pBV,
Matrix4x4< T > const &  transformB 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BV ( BVHNode< T > const *const   nodeA,
BoundingVolume< T > const *const   pBV 
) [protected, pure virtual]

Calculate forward transformation for collision detection with a bounding volume. Currently Both TestOverlap_vs_BV is the same as TestOverlap_vs_BV_TillLeafNodes. So TestOverlap_vs_BV need to be complete!!!

Test overlap of a binary sphere tree with a bounding volume with primitive-primitive intersection test.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BV_TillLeafNodes ( BVHNode< T > const *const   nodeA,
Matrix4x4< T > const &  transformA,
BoundingVolume< T > const *const   pBV,
Matrix4x4< T > const &  transformB 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BV_TillLeafNodes ( BVHNode< T > const *const   nodeA,
Matrix4x4< T > const &  transformA,
BoundingVolume< T > const *const   pBV 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BV_TillLeafNodes ( BVHNode< T > const *const   nodeA,
BoundingVolume< T > const *const   pBV,
Matrix4x4< T > const &  transformB 
) [protected, pure virtual]

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlap_vs_BV_TillLeafNodes ( BVHNode< T > const *const   nodeA,
BoundingVolume< T > const *const   pBV 
) [protected, pure virtual]

Test overlap of a binary sphere tree with a bounding volume without primitive-primitive intersection test. I.e., stop at leaf-leaf-node intersection test.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlapWith ( BoundingVolume< T > const *const   pBV  )  [pure virtual]

Test overlap with a Bounding Volume object (with primitive tests) The collided nodes of this BVH tree are stored. Call GetListOfCollidedNodes() to get the collided nodes of this BVH tree.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlapWith ( MultiBoundingVolume< T > const *const   pMBV  )  [pure virtual]

Test overlap with a Multi Bounding Volume object (with primitive tests) The collided nodes of this BVH tree and the collided bounding volume of the multi bounding volume are stored. Call GetListOfCollidedBoundingVolumesAndNodes() to get the collided bounding volumes of the MultiBoundingVolume object and the collided nodes of this BVH tree.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlapWith ( BVHNode< T > const *const   node  )  [pure virtual]

Test overlap with a BVH node (with primitive tests) The collided nodes of this BVH tree are stored. Call GetListOfCollidedNodes() to get the collided nodes of this BVH tree.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlapWith ( BVHTree< T > const *const   that  )  [pure virtual]

Test overlap with another BVH tree (with primitive tests) The collided nodes of both BVH trees are stored. Call GetListOfCollidedNodes() to get the collided nodes of this BVH tree. Call GetListOfCollidedNodesThat() to get the collided nodes of the other BVH tree.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlapWithTillLeafNodes ( BoundingVolume< T > const *const   pBV  )  [pure virtual]

Test overlap with a Bounding Volume object (without primitive tests) The collided nodes of this BVH tree are stored. Call GetListOfCollidedNodes() to get the collided nodes of this BVH tree.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlapWithTillLeafNodes ( MultiBoundingVolume< T > const *const   pMBV  )  [pure virtual]

Test overlap with a Multi Bounding Volume object (without primitive tests) The collided nodes of this BVH tree and the collided bounding volume of the multi bounding volume are stored. Call GetListOfCollidedBoundingVolumesAndNodes() to get the collided bounding volumes of the MultiBoundingVolume object and the collided nodes of this BVH tree.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlapWithTillLeafNodes ( BVHNode< T > const *const   node  )  [pure virtual]

Test overlap with a BVH node (without primitive tests) The collided nodes of this BVH tree are stored. Call GetListOfCollidedNodes() to get the collided nodes of this BVH tree.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
virtual bool BVHTree< T >::TestOverlapWithTillLeafNodes ( BVHTree< T > const *const   that  )  [pure virtual]

Test overlap with another BVH tree (without primitive tests) The collided nodes of both BVH trees are stored. Call GetListOfCollidedNodes() to get the collided nodes of this BVH tree. Call GetListOfCollidedNodesThat() to get the collided nodes of the other BVH tree.

Implemented in BVHTree_BinarySphere< T >.

template<typename T>
void BVHTree< T >::Update ( std::set< BVHNode< T > * > &  nodeSet  )  [inline, virtual]

Update the BVH tree with a set of nodes to update.

Definition at line 154 of file TAPsBVHTree.cpp.

00155 {
00156     if ( nodeSet.empty() )  return;
00157     std::set< BVHNode<T> * >::iterator nodeSetIterator;
00158     std::set< BVHNode<T> * > parentNodeSet;
00159     for ( nodeSetIterator = nodeSet.begin(); nodeSetIterator != nodeSet.end(); ++nodeSetIterator ) {
00160         (*nodeSetIterator)->Update();
00161         if ( (*nodeSetIterator)->Parent() ) {
00162             parentNodeSet.insert( (*nodeSetIterator)->Parent() );
00163         }
00164     }
00165     Update( parentNodeSet );
00166 }

template<typename T>
void BVHTree< T >::Update (  )  [inline, virtual]

Update the whole BVH tree.

Definition at line 141 of file TAPsBVHTree.cpp.

00142 {
00143     //std::cout << "BVHTree<T>::Update()\n";
00144 
00145     std::set< BVHNode<T> * > leafNodeSet;
00146     if ( !m_pRoot ) return;
00147     //FindListOfLeafNodes( m_pRoot, leafNodeSet );
00148     //Update( leafNodeSet );
00149     Update( GetListOfLeafNodes() );
00150 }

Friends And Related Function Documentation

template<typename T>
std::ostream& operator<< ( std::ostream &  output,
BVHTree< T > const &  obj 
) [friend]

The use of transformation for collision detection with a MultiBoundingVolume (MBV) object
This BVHTree has transformA (m_Transform), while the MBV has its own transfromM and can have an extra transformB. Each bounding volume from the MBV also has its own transformV.
First a node (pt) of BVHTree has to be transformed to the world coordinates (wpt = transformA * pt).
Second wpt has to be transformed into the canonical form of a BV from the MBV. (m_FwdTransformMatrix[1] = m_FwdTransformMatrix[0] * transformV; where m_FwdTransformMatrix[0] = transformB * transformM).
m_InvTransformMatrix[0] is the inverse of transformA.
m_InvTransformMatrix[1] is the inverse of m_FwdTransformMatrix[1].
cwpt = m_InvTransformMatrix[1] * wpt
Then the collision detection can be performed by testing the intersection of the point (cwpt) with the BV in the world coordinates.
The intersection distance has to be transformed back to the canonical form of the node (distance_in_node_canonical_form = m_InvTransformMatrix[0] * m_FwdTransformMatrix[1] * distance).

Definition at line 114 of file TAPsBVHTree.hpp.

00115     {
00116         output  << "BVHTree<" << typeid(T).name() << ">"
00117                 << " with " << obj.GetNumOfNodes() << " nodes"
00118                 << " (" << obj.CountLeafNodes() << " are Leaf nodes)"
00119                 << " and the root ptr is " << obj.m_pRoot 
00120                 << "\n";
00121         return output;
00122     }

Member Data Documentation

template<typename T>
Enum::CD BVHTree< T >::m_eType [protected]

type identifier (see TAPsEnumList.hpp)

Definition at line 58 of file TAPsBVHTree.hpp.

template<typename T>
int BVHTree< T >::m_iTotalNodes [protected]

number of nodes

Definition at line 59 of file TAPsBVHTree.hpp.

template<typename T>
BVHNode<T>* BVHTree< T >::m_pRoot [protected]

Definition at line 62 of file TAPsBVHTree.hpp.

template<typename T>
std::vector< BVsAndNodesList<T> > BVHTree< T >::m_svCollidedBVAndNodeList [protected]

for collision detection with a MultiBoundingVolume object

Definition at line 66 of file TAPsBVHTree.hpp.

template<typename T>
std::vector< BVHNode<T> * > BVHTree< T >::m_svCollidedNode [protected]

for collision detection

Definition at line 64 of file TAPsBVHTree.hpp.

template<typename T>
std::vector< BVHNode<T> * > BVHTree< T >::m_svCollidedNodeThat [protected]

for collision detection (and for collision detection with a(n) (M)BV

Definition at line 65 of file TAPsBVHTree.hpp.

template<typename T>
std::set< BVHNode<T> * > BVHTree< T >::m_svLeafNodes [protected]

a set of pointers to the leaf nodes in the BVH tree

Definition at line 68 of file TAPsBVHTree.hpp.

template<typename T>
TransformationSupport<T>& BVHTree< T >::m_Transform [protected]

a link to a transformation support

Definition at line 72 of file TAPsBVHTree.hpp.

The documentation for this class was generated from the following files:
Generated on Mon Oct 13 11:44:26 2008 for TAPs by  doxygen 1.5.6