AXOM
Axom provides a robust, flexible software infrastructure for the development of multi-physics applications and computational tools.
axom::spin::BVHTree< T, NDIMS > Class Template Reference

The BVHTree class provides functionality for generating a Bounding Volume Hierarchy (BVH) of axis-aligned bounding boxes, i.e., buckets that spatially partitions a set of objects. Each object is defined by its bounding box and user-supplied data-structure specified as a template argument. Once generated, the BVHTree can then be used as an acceleration structure to speed up the performance of point queries on the given objects, e.g., minimum distance, closest point, orientation, etc. More...

#include </home/docs/checkouts/readthedocs.org/user_builds/axom/checkouts/docs-essman-container_strict/src/axom/spin/BVHTree.hpp>

Public Types

using BoxType = primal::BoundingBox< double, NDIMS >
 
using PointType = primal::Point< double, NDIMS >
 

Public Member Functions

 BVHTree (int maxNumLevel=5)
 Default constructor, creates an empty BVHTree instance. More...
 
 BVHTree (int estNumObjects, int maxNumLevels)
 Creates a BVHTree instance that can grow up to the specified number of levels and can hold approximately the given number of objects. More...
 
 ~BVHTree ()
 Destructor. More...
 
int getMaxNumLevels () const
 Returns the maximum number of levels in the tree possible. More...
 
int getNumLevels () const
 Returns the number of levels in the given BVHTree instance. More...
 
void insert (const BoxType &box, const T &data)
 Inserts an object, identified by its bounding box and user-supplied data, to the bucket tree. More...
 
int getNumberOfObjects () const
 Returns the total number of inserted objects in the tree. More...
 
void build (int threshold=25)
 Builds a hierarchical decomposition of axis-aligned bounding boxes that partitions the set of objects in different buckets. More...
 
bool empty () const
 Checks if the tree is empty. More...
 
void clear ()
 Deletes the tree and all associated objects. More...
 
void writeVtkFile (const std::string &fileName, bool include_objects=false) const
 Writes the hierarchical decomposition in a VTK file. More...
 
void writeVtkFile (const std::string &fileName, const int *bins, int nbins) const
 Writes the user-supplied set of bins in a VTK file. More...
 
Point Query API
bool contains (const PointType &pt) const
 Checks if the point is inside the BVHTree. More...
 
void find (const PointType &pt, std::vector< int > &candidate_buckets) const
 Finds a subset of candidate buckets for the given point query. More...
 
BVHTree Access methods
const BoxTypegetBucketBox (int bucketIdx) const
 Returns a const reference to the bounding box of the given bucket. More...
 
int getBucketNumObjects (int bucketIdx) const
 Returns the number of object within the given bucket. More...
 
const int * getBucketObjectArray (int bucketIdx) const
 Return const pointer to the object array of the given bucket. More...
 
const BoxTypegetObjectBox (int objIdx) const
 Returns a const reference to the bounding box of the given object. More...
 
const T & getObjectData (int objIdx) const
 Returns const reference to the data associated with the given object. More...
 
int getObjectBucketIndex (int objIdx) const
 Returns the bucket index of the given object. More...
 

Detailed Description

template<typename T, int NDIMS>
class axom::spin::BVHTree< T, NDIMS >

The BVHTree class provides functionality for generating a Bounding Volume Hierarchy (BVH) of axis-aligned bounding boxes, i.e., buckets that spatially partitions a set of objects. Each object is defined by its bounding box and user-supplied data-structure specified as a template argument. Once generated, the BVHTree can then be used as an acceleration structure to speed up the performance of point queries on the given objects, e.g., minimum distance, closest point, orientation, etc.

Template Parameters
Tthe type of data inserted in a BVH bin
NDIMSthe number of dimensions
See also
BoundingBox, Point

Member Typedef Documentation

◆ BoxType

template<typename T , int NDIMS>
using axom::spin::BVHTree< T, NDIMS >::BoxType = primal::BoundingBox<double, NDIMS>

◆ PointType

template<typename T , int NDIMS>
using axom::spin::BVHTree< T, NDIMS >::PointType = primal::Point<double, NDIMS>

Constructor & Destructor Documentation

◆ BVHTree() [1/2]

template<typename T , int NDIMS>
axom::spin::BVHTree< T, NDIMS >::BVHTree ( int  maxNumLevel = 5)

Default constructor, creates an empty BVHTree instance.

Parameters
[in]maxNumLevelmaximum number of subdivision levels. Default is 5.

◆ BVHTree() [2/2]

template<typename T , int NDIMS>
axom::spin::BVHTree< T, NDIMS >::BVHTree ( int  estNumObjects,
int  maxNumLevels 
)

Creates a BVHTree instance that can grow up to the specified number of levels and can hold approximately the given number of objects.

Parameters
[in]estNumObjectsuser-supplied estimated number of objects.
[in]maxNumLevelsthe maximum number of levels.
Note
It is recommended to use this constructor for best-performance.

◆ ~BVHTree()

template<typename T , int NDIMS>
axom::spin::BVHTree< T, NDIMS >::~BVHTree ( )

Member Function Documentation

◆ getMaxNumLevels()

template<typename T , int NDIMS>
int axom::spin::BVHTree< T, NDIMS >::getMaxNumLevels ( ) const
inline

Returns the maximum number of levels in the tree possible.

Returns
N the maximum number of levels in the tree.

◆ getNumLevels()

template<typename T , int NDIMS>
int axom::spin::BVHTree< T, NDIMS >::getNumLevels ( ) const
inline

Returns the number of levels in the given BVHTree instance.

Returns
N the number of levels in the BVHTree.

References axom::spin::BVHTree< T, NDIMS >::insert().

◆ insert()

template<typename T , int NDIMS>
void axom::spin::BVHTree< T, NDIMS >::insert ( const BoxType box,
const T &  data 
)

Inserts an object, identified by its bounding box and user-supplied data, to the bucket tree.

Parameters
[in]boxAxis-Aligned bounding box enclosing the object.
[in]datauser-supplied data associated with the object.

References axom::primal::BoundingBox< T, NDIMS >::contains(), axom::spin::BVHTree< T, NDIMS >::empty(), axom::spin::BVHTree< T, NDIMS >::getBucketNumObjects(), axom::primal::BoundingBox< T, NDIMS >::isValid(), SLIC_ASSERT, and SLIC_ERROR.

Referenced by axom::spin::BVHTree< T, NDIMS >::getNumLevels(), and axom::quest::SignedDistance< NDIMS >::SignedDistance().

◆ getNumberOfObjects()

template<typename T , int NDIMS>
int axom::spin::BVHTree< T, NDIMS >::getNumberOfObjects ( ) const
inline

Returns the total number of inserted objects in the tree.

Returns
N the total number of objects.
Postcondition
N >= 0.

References axom::spin::BVHTree< T, NDIMS >::build().

◆ build()

template<typename T , int NDIMS>
void axom::spin::BVHTree< T, NDIMS >::build ( int  threshold = 25)

Builds a hierarchical decomposition of axis-aligned bounding boxes that partitions the set of objects in different buckets.

Parameters
[in]thresholdsubdivision threshold, buckets consisting of a number of objects greater than the given threshold will be subdivided.

References axom::spin::BVHTree< T, NDIMS >::empty(), and SLIC_ASSERT.

Referenced by axom::spin::BVHTree< T, NDIMS >::getNumberOfObjects(), and axom::quest::SignedDistance< NDIMS >::SignedDistance().

◆ empty()

◆ clear()

template<typename T , int NDIMS>
void axom::spin::BVHTree< T, NDIMS >::clear ( )

Deletes the tree and all associated objects.

Postcondition
this->empty() == true.
this->getNumberOfObjects() == 0.

Referenced by axom::spin::BVHTree< T, NDIMS >::empty(), and axom::spin::BVHTree< T, NDIMS >::~BVHTree().

◆ contains()

template<typename T , int NDIMS>
bool axom::spin::BVHTree< T, NDIMS >::contains ( const PointType pt) const

Checks if the point is inside the BVHTree.

Parameters
[in]ptthe point in query.
Returns
status true if the point is inside, else false.

References axom::spin::BVHTree< T, NDIMS >::empty(), axom::primal::BoundingBox< double, NDIMS >::getPoints(), axom::utilities::max(), axom::utilities::min(), SLIC_ASSERT, and axom::primal::squared_distance().

Referenced by axom::spin::BVHTree< T, NDIMS >::empty().

◆ find()

template<typename T , int NDIMS>
void axom::spin::BVHTree< T, NDIMS >::find ( const PointType pt,
std::vector< int > &  candidate_buckets 
) const

Finds a subset of candidate buckets for the given point query.

Parameters
[in]ptthe point in query.
[out]candidate_bucketslist of bucket IDs for the given point query.
Precondition
this->empty()==false.
candidate_buckets.size()==0

References axom::spin::BVHTree< T, NDIMS >::empty(), axom::utilities::max(), axom::utilities::min(), and SLIC_ASSERT.

Referenced by axom::quest::SignedDistance< NDIMS >::computeDistance(), and axom::spin::BVHTree< T, NDIMS >::empty().

◆ getBucketBox()

template<typename T , int NDIMS>
const primal::BoundingBox< double, NDIMS > & axom::spin::BVHTree< T, NDIMS >::getBucketBox ( int  bucketIdx) const

Returns a const reference to the bounding box of the given bucket.

Parameters
[in]bucketIdxthe index of the bucket in query.
Returns
Box the bounding box of the bucket.
Precondition
bucketIdx >= 0 && bucketIdx < m_tree.size()
Postcondition
Box.isValid() == true.

References SLIC_ASSERT.

Referenced by axom::spin::BVHTree< T, NDIMS >::empty().

◆ getBucketNumObjects()

template<typename T , int NDIMS>
int axom::spin::BVHTree< T, NDIMS >::getBucketNumObjects ( int  bucketIdx) const

Returns the number of object within the given bucket.

Parameters
[in]bucketIdxthe index of the bucket in query.
Returns
N the number of object within the given bucket.
Precondition
bucketIdx >= 0 && bucketIdx < m_tree.size()
Postcondition
N >= 0

References SLIC_ASSERT.

Referenced by axom::quest::SignedDistance< NDIMS >::computeDistance(), axom::spin::BVHTree< T, NDIMS >::empty(), and axom::spin::BVHTree< T, NDIMS >::insert().

◆ getBucketObjectArray()

template<typename T , int NDIMS>
const int * axom::spin::BVHTree< T, NDIMS >::getBucketObjectArray ( int  bucketIdx) const

Return const pointer to the object array of the given bucket.

Parameters
[in]bucketIdxthe index of the bucket in query.
Returns
arrayPtr pointer to the buckets object array
Precondition
bucketIdx >= 0 && bucketIdx < m_tree.size()
Postcondition
arryPtr != nullptr

References SLIC_ASSERT.

Referenced by axom::quest::SignedDistance< NDIMS >::computeDistance(), and axom::spin::BVHTree< T, NDIMS >::empty().

◆ getObjectBox()

template<typename T , int NDIMS>
const primal::BoundingBox< double, NDIMS > & axom::spin::BVHTree< T, NDIMS >::getObjectBox ( int  objIdx) const

Returns a const reference to the bounding box of the given object.

Parameters
[in]objIdxthe ID of the object in query.
Returns
Box the bounding box of the given object.
Postcondition
Box.isValid() == true.

References SLIC_ASSERT.

Referenced by axom::quest::SignedDistance< NDIMS >::computeDistance(), and axom::spin::BVHTree< T, NDIMS >::empty().

◆ getObjectData()

template<typename T , int NDIMS>
const T & axom::spin::BVHTree< T, NDIMS >::getObjectData ( int  objIdx) const

Returns const reference to the data associated with the given object.

Parameters
objIdxthe ID of the object in query.
Returns
data the data associated with the object.
Note
The return data is the data supplied when the object was inserted.
Precondition
objIdx >= 0 && objIdx < this->getNumberOfObjects()

References SLIC_ASSERT.

Referenced by axom::quest::SignedDistance< NDIMS >::computeDistance(), and axom::spin::BVHTree< T, NDIMS >::empty().

◆ getObjectBucketIndex()

template<typename T , int NDIMS>
int axom::spin::BVHTree< T, NDIMS >::getObjectBucketIndex ( int  objIdx) const

Returns the bucket index of the given object.

Parameters
[in]objIdxthe ID of the object in query.
Returns
bucketIdx the bucket index.
Precondition
objIdx >= 0 && objIdx < this->getNumberOfObjects()
Postcondition
The return value, butcketIdx will be:
  • bucketIdx < 0, iff the tree is not built
  • bucketIdx >= 0 && bucektIdx < this->getNumberO

References SLIC_ASSERT.

Referenced by axom::spin::BVHTree< T, NDIMS >::empty().

◆ writeVtkFile() [1/2]

template<typename T , int NDIMS>
void axom::spin::BVHTree< T, NDIMS >::writeVtkFile ( const std::string &  fileName,
bool  include_objects = false 
) const

Writes the hierarchical decomposition in a VTK file.

Parameters
[in]fileNamethe name of the VTK formatted file to generate.
[in]include_objectsoptional parameter, when true it also writes out the bounding boxes of the supplied objects.

Referenced by axom::spin::BVHTree< T, NDIMS >::empty(), and axom::spin::BVHTree< T, NDIMS >::writeVtkFile().

◆ writeVtkFile() [2/2]

template<typename T , int NDIMS>
void axom::spin::BVHTree< T, NDIMS >::writeVtkFile ( const std::string &  fileName,
const int *  bins,
int  nbins 
) const

Writes the user-supplied set of bins in a VTK file.

Parameters
[in]fileNamethe name of the VTK formatted file to generate.
[in]binsarray of bins to dump in the VTK file.
[in]nbinsthe number of bins.
Note
Primarily used for debugging.

References AXOM_NOT_USED, SLIC_ASSERT, and axom::spin::BVHTree< T, NDIMS >::writeVtkFile().


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