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/v0.5.0/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 BoxType &	getBucketBox (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 BoxType &	getObjectBox (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

T	the type of data inserted in a BVH bin
NDIMS	the 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] maxNumLevel maximum 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]	estNumObjects	user-supplied estimated number of objects.
[in]	maxNumLevels	the 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 ( )

Destructor.

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

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]	box	Axis-Aligned bounding box enclosing the object.
[in]	data	user-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] threshold subdivision 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()

template<typename T , int NDIMS>

bool axom::spin::BVHTree< T, NDIMS >::empty ( ) const

inline

Checks if the tree is empty.

Returns: status true if the tree is empty, otherwise, false.

Referenced by axom::spin::BVHTree< T, NDIMS >::build(), axom::spin::BVHTree< T, NDIMS >::contains(), axom::spin::BVHTree< T, NDIMS >::find(), and axom::spin::BVHTree< T, NDIMS >::insert().

◆ 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] pt the 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]	pt	the point in query.
[out]	candidate_buckets	list 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] bucketIdx the 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] bucketIdx the 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] bucketIdx the 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] objIdx the 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

objIdx the 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] objIdx the 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]	fileName	the name of the VTK formatted file to generate.
[in]	include_objects	optional 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]	fileName	the name of the VTK formatted file to generate.
[in]	bins	array of bins to dump in the VTK file.
[in]	nbins	the 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:

/home/docs/checkouts/readthedocs.org/user_builds/axom/checkouts/v0.5.0/src/axom/spin/BVHTree.hpp

Public Types

Public Member Functions

Detailed Description

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

Member Typedef Documentation

◆ BoxType

◆ PointType

Constructor & Destructor Documentation

◆ BVHTree() [1/2]

◆ BVHTree() [2/2]

◆ ~BVHTree()

Member Function Documentation

◆ getMaxNumLevels()

◆ getNumLevels()

◆ insert()

◆ getNumberOfObjects()

◆ build()

◆ empty()

◆ clear()

◆ contains()

◆ find()

◆ getBucketBox()

◆ getBucketNumObjects()

◆ getBucketObjectArray()

◆ getObjectBox()

◆ getObjectData()

◆ getObjectBucketIndex()

◆ writeVtkFile() [1/2]

◆ writeVtkFile() [2/2]

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