Open CASCADE Technology  7.0.0
Public Types | Public Member Functions | Protected Attributes
BVH_Tree< T, N > Class Template Reference

Stores parameters of bounding volume hierarchy (BVH). Bounding volume hierarchy (BVH) organizes geometric objects in the tree based on spatial relationships. Each node in the tree contains an axis-aligned bounding box of all the objects below it. Bounding volume hierarchies are used in many algorithms to support efficient operations on the sets of geometric objects, such as collision detection, ray-tracing, searching of nearest objects, and view frustum culling. More...

#include <BVH_Tree.hxx>

Public Types

typedef BVH_Box< T, N >::BVH_VecNt BVH_VecNt
 

Public Member Functions

 BVH_Tree ()
 Creates new empty BVH tree. More...
 
void Reserve (const Standard_Integer theNbNodes)
 Reserves internal BVH storage, so that it can contain specified number of tree nodes. More...
 
BVH_VecNtMinPoint (const Standard_Integer theNodeIndex)
 Returns minimum point of the given node. More...
 
BVH_VecNtMaxPoint (const Standard_Integer theNodeIndex)
 Returns maximum point of the given node. More...
 
const BVH_VecNtMinPoint (const Standard_Integer theNodeIndex) const
 Returns minimum point of the given node. More...
 
const BVH_VecNtMaxPoint (const Standard_Integer theNodeIndex) const
 Returns maximum point of the given node. More...
 
Standard_IntegerLeftChild (const Standard_Integer theNodeIndex)
 Returns index of left child of the given inner node. More...
 
Standard_Integer LeftChild (const Standard_Integer theNodeIndex) const
 Returns index of left child of the given inner node. More...
 
Standard_IntegerRightChild (const Standard_Integer theNodeIndex)
 Returns index of right child of the given inner node. More...
 
Standard_Integer RightChild (const Standard_Integer theNodeIndex) const
 Returns index of right child of the given inner node. More...
 
Standard_IntegerBegPrimitive (const Standard_Integer theNodeIndex)
 Returns index of first primitive of the given leaf node. More...
 
Standard_Integer BegPrimitive (const Standard_Integer theNodeIndex) const
 Returns index of first primitive of the given leaf node. More...
 
Standard_IntegerEndPrimitive (const Standard_Integer theNodeIndex)
 Returns index of last primitive of the given leaf node. More...
 
Standard_Integer EndPrimitive (const Standard_Integer theNodeIndex) const
 Returns index of last primitive of the given leaf node. More...
 
Standard_Integer NbPrimitives (const Standard_Integer theNodeIndex) const
 Returns number of primitives for the given tree node. More...
 
Standard_IntegerLevel (const Standard_Integer theNodeIndex)
 Returns level (depth) of the given node. More...
 
Standard_Integer Level (const Standard_Integer theNodeIndex) const
 Returns level (depth) of the given node. More...
 
Standard_Boolean IsOuter (const Standard_Integer theNodeIndex) const
 Is node a leaf (outer)? More...
 
void SetOuter (const Standard_Integer theNodeIndex)
 Sets node type to 'outer'. More...
 
void SetInner (const Standard_Integer theNodeIndex)
 Sets node type to 'inner'. More...
 
Standard_Integer Length () const
 Returns total number of BVH nodes. More...
 
Standard_Integer Depth () const
 Returns depth of BVH tree from last build. More...
 
void Clear ()
 Removes all BVH nodes. More...
 
Standard_Integer AddLeafNode (const BVH_VecNt &theMinPoint, const BVH_VecNt &theMaxPoint, const Standard_Integer theBegElem, const Standard_Integer theEndElem)
 Adds new leaf node to the BVH. More...
 
Standard_Integer AddInnerNode (const BVH_VecNt &theMinPoint, const BVH_VecNt &theMaxPoint, const Standard_Integer theLftChild, const Standard_Integer theRghChild)
 Adds new inner node to the BVH. More...
 
Standard_Integer AddLeafNode (const BVH_Box< T, N > &theAABB, const Standard_Integer theBegElem, const Standard_Integer theEndElem)
 Adds new leaf node to the BVH. More...
 
Standard_Integer AddInnerNode (const BVH_Box< T, N > &theAABB, const Standard_Integer theLftChild, const Standard_Integer theRghChild)
 Adds new inner node to the BVH. More...
 
Standard_Integer AddLeafNode (const Standard_Integer theBegElem, const Standard_Integer theEndElem)
 Adds new leaf node to the BVH with UNINITIALIZED bounds. More...
 
Standard_Integer AddInnerNode (const Standard_Integer theLftChild, const Standard_Integer theRghChild)
 Adds new inner node to the BVH with UNINITIALIZED bounds. More...
 
EstimateSAH () const
 Returns value of SAH (surface area heuristic). Allows to compare the quality of BVH trees constructed for the same sets of geometric objects with different methods. More...
 
BVH::ArrayType< T, N >::Type & MinPointBuffer ()
 Returns array of node min points. More...
 
const BVH::ArrayType< T, N >::Type & MinPointBuffer () const
 Returns array of node min points. More...
 
BVH::ArrayType< T, N >::Type & MaxPointBuffer ()
 Returns array of node max points. More...
 
const BVH::ArrayType< T, N >::Type & MaxPointBuffer () const
 Returns array of node max points. More...
 
BVH_Array4iNodeInfoBuffer ()
 Returns array of node data records. More...
 
const BVH_Array4iNodeInfoBuffer () const
 Returns array of node data records. More...
 

Protected Attributes

BVH::ArrayType< T, N >::Type myMinPointBuffer
 Array of node minimum points. More...
 
BVH::ArrayType< T, N >::Type myMaxPointBuffer
 Array of node maximum points. More...
 
BVH_Array4i myNodeInfoBuffer
 Array of node data records. More...
 
Standard_Integer myDepth
 Current depth of BVH tree. More...
 

Detailed Description

template<class T, int N>
class BVH_Tree< T, N >

Stores parameters of bounding volume hierarchy (BVH). Bounding volume hierarchy (BVH) organizes geometric objects in the tree based on spatial relationships. Each node in the tree contains an axis-aligned bounding box of all the objects below it. Bounding volume hierarchies are used in many algorithms to support efficient operations on the sets of geometric objects, such as collision detection, ray-tracing, searching of nearest objects, and view frustum culling.

Member Typedef Documentation

template<class T , int N>
typedef BVH_Box<T, N>::BVH_VecNt BVH_Tree< T, N >::BVH_VecNt

Constructor & Destructor Documentation

template<class T , int N>
BVH_Tree< T, N >::BVH_Tree ( )
inline

Creates new empty BVH tree.

Member Function Documentation

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::AddInnerNode ( const BVH_VecNt theMinPoint,
const BVH_VecNt theMaxPoint,
const Standard_Integer  theLftChild,
const Standard_Integer  theRghChild 
)

Adds new inner node to the BVH.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::AddInnerNode ( const BVH_Box< T, N > &  theAABB,
const Standard_Integer  theLftChild,
const Standard_Integer  theRghChild 
)

Adds new inner node to the BVH.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::AddInnerNode ( const Standard_Integer  theLftChild,
const Standard_Integer  theRghChild 
)

Adds new inner node to the BVH with UNINITIALIZED bounds.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::AddLeafNode ( const BVH_VecNt theMinPoint,
const BVH_VecNt theMaxPoint,
const Standard_Integer  theBegElem,
const Standard_Integer  theEndElem 
)

Adds new leaf node to the BVH.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::AddLeafNode ( const BVH_Box< T, N > &  theAABB,
const Standard_Integer  theBegElem,
const Standard_Integer  theEndElem 
)

Adds new leaf node to the BVH.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::AddLeafNode ( const Standard_Integer  theBegElem,
const Standard_Integer  theEndElem 
)

Adds new leaf node to the BVH with UNINITIALIZED bounds.

template<class T , int N>
Standard_Integer& BVH_Tree< T, N >::BegPrimitive ( const Standard_Integer  theNodeIndex)
inline

Returns index of first primitive of the given leaf node.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::BegPrimitive ( const Standard_Integer  theNodeIndex) const
inline

Returns index of first primitive of the given leaf node.

template<class T , int N>
void BVH_Tree< T, N >::Clear ( )

Removes all BVH nodes.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::Depth ( ) const
inline

Returns depth of BVH tree from last build.

template<class T , int N>
Standard_Integer& BVH_Tree< T, N >::EndPrimitive ( const Standard_Integer  theNodeIndex)
inline

Returns index of last primitive of the given leaf node.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::EndPrimitive ( const Standard_Integer  theNodeIndex) const
inline

Returns index of last primitive of the given leaf node.

template<class T , int N>
T BVH_Tree< T, N >::EstimateSAH ( ) const

Returns value of SAH (surface area heuristic). Allows to compare the quality of BVH trees constructed for the same sets of geometric objects with different methods.

template<class T , int N>
Standard_Boolean BVH_Tree< T, N >::IsOuter ( const Standard_Integer  theNodeIndex) const
inline

Is node a leaf (outer)?

template<class T , int N>
Standard_Integer& BVH_Tree< T, N >::LeftChild ( const Standard_Integer  theNodeIndex)
inline

Returns index of left child of the given inner node.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::LeftChild ( const Standard_Integer  theNodeIndex) const
inline

Returns index of left child of the given inner node.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::Length ( void  ) const
inline

Returns total number of BVH nodes.

template<class T , int N>
Standard_Integer& BVH_Tree< T, N >::Level ( const Standard_Integer  theNodeIndex)
inline

Returns level (depth) of the given node.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::Level ( const Standard_Integer  theNodeIndex) const
inline

Returns level (depth) of the given node.

template<class T , int N>
BVH_VecNt& BVH_Tree< T, N >::MaxPoint ( const Standard_Integer  theNodeIndex)
inline

Returns maximum point of the given node.

template<class T , int N>
const BVH_VecNt& BVH_Tree< T, N >::MaxPoint ( const Standard_Integer  theNodeIndex) const
inline

Returns maximum point of the given node.

template<class T , int N>
BVH::ArrayType<T, N>::Type& BVH_Tree< T, N >::MaxPointBuffer ( )
inline

Returns array of node max points.

template<class T , int N>
const BVH::ArrayType<T, N>::Type& BVH_Tree< T, N >::MaxPointBuffer ( ) const
inline

Returns array of node max points.

template<class T , int N>
BVH_VecNt& BVH_Tree< T, N >::MinPoint ( const Standard_Integer  theNodeIndex)
inline

Returns minimum point of the given node.

template<class T , int N>
const BVH_VecNt& BVH_Tree< T, N >::MinPoint ( const Standard_Integer  theNodeIndex) const
inline

Returns minimum point of the given node.

template<class T , int N>
BVH::ArrayType<T, N>::Type& BVH_Tree< T, N >::MinPointBuffer ( )
inline

Returns array of node min points.

template<class T , int N>
const BVH::ArrayType<T, N>::Type& BVH_Tree< T, N >::MinPointBuffer ( ) const
inline

Returns array of node min points.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::NbPrimitives ( const Standard_Integer  theNodeIndex) const
inline

Returns number of primitives for the given tree node.

template<class T , int N>
BVH_Array4i& BVH_Tree< T, N >::NodeInfoBuffer ( )
inline

Returns array of node data records.

template<class T , int N>
const BVH_Array4i& BVH_Tree< T, N >::NodeInfoBuffer ( ) const
inline

Returns array of node data records.

template<class T , int N>
void BVH_Tree< T, N >::Reserve ( const Standard_Integer  theNbNodes)

Reserves internal BVH storage, so that it can contain specified number of tree nodes.

template<class T , int N>
Standard_Integer& BVH_Tree< T, N >::RightChild ( const Standard_Integer  theNodeIndex)
inline

Returns index of right child of the given inner node.

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::RightChild ( const Standard_Integer  theNodeIndex) const
inline

Returns index of right child of the given inner node.

template<class T , int N>
void BVH_Tree< T, N >::SetInner ( const Standard_Integer  theNodeIndex)
inline

Sets node type to 'inner'.

template<class T , int N>
void BVH_Tree< T, N >::SetOuter ( const Standard_Integer  theNodeIndex)
inline

Sets node type to 'outer'.

Field Documentation

template<class T , int N>
Standard_Integer BVH_Tree< T, N >::myDepth
protected

Current depth of BVH tree.

template<class T , int N>
BVH::ArrayType<T, N>::Type BVH_Tree< T, N >::myMaxPointBuffer
protected

Array of node maximum points.

template<class T , int N>
BVH::ArrayType<T, N>::Type BVH_Tree< T, N >::myMinPointBuffer
protected

Array of node minimum points.

template<class T , int N>
BVH_Array4i BVH_Tree< T, N >::myNodeInfoBuffer
protected

Array of node data records.


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