Open CASCADE Technology  7.6.0.dev
Public Types | Public Member Functions | Protected Types | Protected Member Functions
BVH_LinearBuilder< T, N > Class Template Reference

Performs fast BVH construction using LBVH building approach. Algorithm uses spatial Morton codes to reduce the BVH construction problem to a sorting problem (radix sort – O(N) complexity). This Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees of lower quality compared to SAH-based BVH builders but it is over an order of magnitude faster (up to 3M triangles per second). More...

#include <BVH_LinearBuilder.hxx>

Inheritance diagram for BVH_LinearBuilder< T, N >:
Inheritance graph
[legend]

Public Types

typedef BVH::VectorType< T, N >::Type BVH_VecNt
 
- Public Types inherited from Standard_Transient
typedef void base_type
 Returns a type descriptor about this object. More...
 

Public Member Functions

 BVH_LinearBuilder (const Standard_Integer theLeafNodeSize=BVH_Constants_LeafNodeSizeDefault, const Standard_Integer theMaxTreeDepth=BVH_Constants_MaxTreeDepth)
 Creates binned LBVH builder. More...
 
virtual ~BVH_LinearBuilder ()
 Releases resources of LBVH builder. More...
 
virtual void Build (BVH_Set< T, N > *theSet, BVH_Tree< T, N > *theBVH, const BVH_Box< T, N > &theBox) const override
 Builds BVH. More...
 
- Public Member Functions inherited from BVH_BuilderTransient
Standard_Integer MaxTreeDepth () const
 Returns the maximum depth of constructed BVH. More...
 
Standard_Integer LeafNodeSize () const
 Returns the maximum number of sub-elements in the leaf. More...
 
Standard_Boolean IsParallel () const
 Returns parallel flag. More...
 
void SetParallel (const Standard_Boolean isParallel)
 Set parallel flag contolling possibility of parallel execution. More...
 
- Public Member Functions inherited from Standard_Transient
 Standard_Transient ()
 Empty constructor. More...
 
 Standard_Transient (const Standard_Transient &)
 Copy constructor – does nothing. More...
 
Standard_Transientoperator= (const Standard_Transient &)
 Assignment operator, needed to avoid copying reference counter. More...
 
virtual ~Standard_Transient ()
 Destructor must be virtual. More...
 
virtual void Delete () const
 Memory deallocator for transient classes. More...
 
virtual const opencascade::handle< Standard_Type > & DynamicType () const
 Returns a type descriptor about this object. More...
 
Standard_Boolean IsInstance (const opencascade::handle< Standard_Type > &theType) const
 Returns a true value if this is an instance of Type. More...
 
Standard_Boolean IsInstance (const Standard_CString theTypeName) const
 Returns a true value if this is an instance of TypeName. More...
 
Standard_Boolean IsKind (const opencascade::handle< Standard_Type > &theType) const
 Returns true if this is an instance of Type or an instance of any class that inherits from Type. Note that multiple inheritance is not supported by OCCT RTTI mechanism. More...
 
Standard_Boolean IsKind (const Standard_CString theTypeName) const
 Returns true if this is an instance of TypeName or an instance of any class that inherits from TypeName. Note that multiple inheritance is not supported by OCCT RTTI mechanism. More...
 
Standard_TransientThis () const
 Returns non-const pointer to this object (like const_cast). For protection against creating handle to objects allocated in stack or call from constructor, it will raise exception Standard_ProgramError if reference counter is zero. More...
 
Standard_Integer GetRefCount () const
 Get the reference counter of this object. More...
 
void IncrementRefCounter () const
 Increments the reference counter of this object. More...
 
Standard_Integer DecrementRefCounter () const
 Decrements the reference counter of this object; returns the decremented value. More...
 

Protected Types

typedef NCollection_Array1< BVH_EncodedLink >::iterator LinkIterator
 

Protected Member Functions

Standard_Integer emitHierachy (BVH_Tree< T, N > *theBVH, const NCollection_Array1< BVH_EncodedLink > &theEncodedLinks, const Standard_Integer theBit, const Standard_Integer theShift, const Standard_Integer theStart, const Standard_Integer theFinal) const
 Emits hierarchy from sorted Morton codes. More...
 
Standard_Integer lowerBound (const NCollection_Array1< BVH_EncodedLink > &theEncodedLinks, Standard_Integer theStart, Standard_Integer theFinal, Standard_Integer theDigit) const
 Returns index of the first element which does not compare less than the given one. More...
 
- Protected Member Functions inherited from BVH_Builder< T, N >
 BVH_Builder (const Standard_Integer theLeafNodeSize, const Standard_Integer theMaxTreeDepth)
 Creates new abstract BVH builder. More...
 
void updateDepth (BVH_Tree< T, N > *theBVH, const Standard_Integer theLevel) const
 Updates depth of constructed BVH tree. More...
 
- Protected Member Functions inherited from BVH_BuilderTransient
 BVH_BuilderTransient (const Standard_Integer theLeafNodeSize, const Standard_Integer theMaxTreeDepth)
 Creates new abstract BVH builder. More...
 

Additional Inherited Members

- Static Public Member Functions inherited from Standard_Transient
static const char * get_type_name ()
 Returns a type descriptor about this object. More...
 
static const opencascade::handle< Standard_Type > & get_type_descriptor ()
 Returns type descriptor of Standard_Transient class. More...
 
- Protected Attributes inherited from BVH_BuilderTransient
Standard_Integer myMaxTreeDepth
 Maximum depth of constructed BVH. More...
 
Standard_Integer myLeafNodeSize
 Maximum number of objects per leaf. More...
 
Standard_Boolean myIsParallel
 Parallel execution flag. More...
 

Detailed Description

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

Performs fast BVH construction using LBVH building approach. Algorithm uses spatial Morton codes to reduce the BVH construction problem to a sorting problem (radix sort – O(N) complexity). This Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees of lower quality compared to SAH-based BVH builders but it is over an order of magnitude faster (up to 3M triangles per second).

For more details see: C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha. Fast BVH construction on GPUs. Eurographics, 2009.

Member Typedef Documentation

◆ BVH_VecNt

template<class T , int N>
typedef BVH::VectorType<T, N>::Type BVH_LinearBuilder< T, N >::BVH_VecNt

◆ LinkIterator

template<class T , int N>
typedef NCollection_Array1<BVH_EncodedLink>::iterator BVH_LinearBuilder< T, N >::LinkIterator
protected

Constructor & Destructor Documentation

◆ BVH_LinearBuilder()

template<class T , int N>
BVH_LinearBuilder< T, N >::BVH_LinearBuilder ( const Standard_Integer  theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault,
const Standard_Integer  theMaxTreeDepth = BVH_Constants_MaxTreeDepth 
)

Creates binned LBVH builder.

◆ ~BVH_LinearBuilder()

template<class T , int N>
BVH_LinearBuilder< T, N >::~BVH_LinearBuilder ( )
virtual

Releases resources of LBVH builder.

Member Function Documentation

◆ Build()

template<class T , int N>
void BVH_LinearBuilder< T, N >::Build ( BVH_Set< T, N > *  theSet,
BVH_Tree< T, N > *  theBVH,
const BVH_Box< T, N > &  theBox 
) const
overridevirtual

Builds BVH.

Implements BVH_Builder< T, N >.

◆ emitHierachy()

template<class T , int N>
Standard_Integer BVH_LinearBuilder< T, N >::emitHierachy ( BVH_Tree< T, N > *  theBVH,
const NCollection_Array1< BVH_EncodedLink > &  theEncodedLinks,
const Standard_Integer  theBit,
const Standard_Integer  theShift,
const Standard_Integer  theStart,
const Standard_Integer  theFinal 
) const
protected

Emits hierarchy from sorted Morton codes.

◆ lowerBound()

template<class T , int N>
Standard_Integer BVH_LinearBuilder< T, N >::lowerBound ( const NCollection_Array1< BVH_EncodedLink > &  theEncodedLinks,
Standard_Integer  theStart,
Standard_Integer  theFinal,
Standard_Integer  theDigit 
) const
protected

Returns index of the first element which does not compare less than the given one.


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