Defines a Bounding Volume Hierarchy (BVH) spatial acceleration data structure over a set of geometric entities. More...

#include </home/docs/checkouts/readthedocs.org/user_builds/axom/checkouts/develop/src/axom/spin/BVH.hpp>

Inheritance diagram for axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >:

[legend]

Public Types
using	BoxType = typename primal::BoundingBox< FloatType, NDIMS >

using	PointType = typename primal::Point< FloatType, NDIMS >

using	RayType = typename primal::Ray< FloatType, NDIMS >

using	TraverserType = typename ImplType::TraverserType

using	ExecSpaceType = ExecSpace

Public Member Functions
	BVH ()
	Default constructor. More...

template<typename BoxIndexable >
	BVH (const BoxIndexable boxes, IndexType numItems, int allocatorID=axom::execution_space< ExecSpace >::allocatorID(), FloatType tolerance=DEFAULT_TOLERANCE, FloatType scaleFactor=DEFAULT_SCALE_FACTOR)
	Constructs a BVH instance of specified dimension over a given set of geometric entities, each represented by its corresponding axis-aligned bounding box. More...

template<typename BoxIndexable >
int	initialize (const BoxIndexable boxes, IndexType numItems)
	Initializes a BVH instance of specified dimension over a given set of geometric entities, each represented by its corresponding axis-aligned bounding box. More...

bool	isInitialized () const

void	setAllocatorID (int allocatorID)
	Sets the ID of the allocator used by the BVH. More...

int	getAllocatorID () const
	Get the ID of the allocator used by the BVH. More...

void	setScaleFactor (FloatType scale_factor)
	Sets the scale factor for scaling the supplied bounding boxes. More...

FloatType	getScaleFactor () const
	Returns the scale factor used when constructing the BVH. More...

void	setTolerance (FloatType EPS)
	Sets the tolerance used for querying the BVH. More...

FloatType	getTolerance () const
	Returns the tolerance value used for BVH queries. More...

BoxType	getBounds () const
	Returns the bounds of the BVH, given by the the root bounding box. More...

TraverserType	getTraverser () const
	Returns a device-copyable object that can be used to traverse the BVH from inside a device kernel. More...

template<typename PointIndexable >
void	findPoints (axom::ArrayView< IndexType > offsets, axom::ArrayView< IndexType > counts, axom::Array< IndexType > &candidates, IndexType numPts, PointIndexable points) const
	Finds the candidate bins that contain each of the query points. More...

template<typename RayIndexable >
void	findRays (axom::ArrayView< IndexType > offsets, axom::ArrayView< IndexType > counts, axom::Array< IndexType > &candidates, IndexType numRays, RayIndexable rays) const
	Finds the candidate bins that intersect the given rays. More...

template<typename BoxIndexable >
void	findBoundingBoxes (axom::ArrayView< IndexType > offsets, axom::ArrayView< IndexType > counts, axom::Array< IndexType > &candidates, IndexType numBoxes, BoxIndexable boxes) const
	Finds the candidate bins that intersect the given bounding boxes. More...

void	writeVtkFile (const std::string &fileName) const
	Writes the BVH to the specified VTK file for visualization. More...

Detailed Description

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>
class axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >

Defines a Bounding Volume Hierarchy (BVH) spatial acceleration data structure over a set of geometric entities.

The BVH class provides functionality for generating a hierarchical spatial partitioning over a set of geometric entities. Each entity in the BVH is represented by a bounding volume, in this case an axis-aligned bounding box. Once the BVH structure is generated, it is used to accelerate various spatial queries, such as, collision detection, ray tracing, etc., by reducing the search space for a given operation to an abbreviated list of candidate geometric entities to check for a particular query.

Template Parameters

NDIMS	the number of dimensions, e.g., 2 or 3.
ExecSpace	the execution space to use, e.g. SEQ_EXEC, CUDA_EXEC, etc.
FloatType	floating precision, e.g., `double` or `float`. Optional.

Note: The last template parameter is optional. Defaults to double precision if not specified.

Precondition: The spin::BVH class requires RAJA and Umpire with CUDA_EXEC.

Note: The Execution Space, supplied as the 2nd template argument, specifies

Where and how the BVH is generated and stored
Where and how subsequent queries are performed
The default memory space, bound to the corresponding execution space

See also: axom::execution_space for more details.

A simple example illustrating how to use the BVH class is given below:

namespace spin = axom::spin;
constexpr int DIMENSION = 3;
 
// get a list of axis-aligned bounding boxes in a flat array
const primal::BoundingBox<float, DIMENSION>* aabbs = ...
 
// create a 3D BVH instance in parallel on the CPU using OpenMP
spin::BVH< DIMENSION, axom::OMP_EXEC > bvh;
bvh.initialize( aabbs, numItems );
 
// query points supplied in arrays, qx, qy, qz
const axom::IndexType numPoints = ...
const double* qx = ...
const double* qy = ...
const double* qz = ...
//use the ZipPoint class to tie them together
ZipPoint qpts {{qx,qy,qz}};
 
// output array buffers
axom::IndexType* offsets    = axom::allocate< IndexType >( numPoints );
axom::IndexType* counts     = axom::allocate< IndexType >( numPoints );
axom::IndexType* candidates = nullptr;
 
// find candidates in parallel, allocates and populates the supplied
// candidates array
bvh.findPoints( offsets, counts, candidates, numPoints, qpts );
SLIC_ASSERT( candidates != nullptr );
 
...
 
// caller is responsible for properly de-allocating the candidates array
axom::deallocate( candidates );

Member Typedef Documentation

◆ BoxType

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

using axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::BoxType = typename primal::BoundingBox<FloatType, NDIMS>

◆ PointType

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

using axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::PointType = typename primal::Point<FloatType, NDIMS>

◆ RayType

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

using axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::RayType = typename primal::Ray<FloatType, NDIMS>

◆ TraverserType

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

using axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::TraverserType = typename ImplType::TraverserType

◆ ExecSpaceType

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

using axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::ExecSpaceType = ExecSpace

Constructor & Destructor Documentation

◆ BVH() [1/2]

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::BVH ( )

inline

Default constructor.

◆ BVH() [2/2]

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

template<typename BoxIndexable >

axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::BVH	(	const BoxIndexable	boxes,
		IndexType	numItems,
		int	allocatorID = `axom::execution_space<ExecSpace>::allocatorID()`,
		FloatType	tolerance = `DEFAULT_TOLERANCE`,
		FloatType	scaleFactor = `DEFAULT_SCALE_FACTOR`
	)

inline

Constructs a BVH instance of specified dimension over a given set of geometric entities, each represented by its corresponding axis-aligned bounding box.

Parameters

[in]	boxes	buffer consisting of bounding boxes for each entity.
[in]	numItems	the total number of items to store in the BVH.
[in]	allocatorID	the ID of the allocator to use in BVH construction.
[in]	scaleFactor	the scale factor for the given bounding boxes.
[in]	tolerance	the tolerance to use when querying the BVH.

Warning: The supplied boxes array must point to a buffer in a memory space that is compatible with the execution space. For example, when using CUDA_EXEC, boxes must be in unified memory or GPU memory. The supplied allocator ID must also correspond to an umpire allocator and be compatible with the execution space. The code currently does not check for these conditions.

Precondition: boxes != nullptr; numItems > 0; allocatorID must correspond to an Umpire allocator and be compatible with the execution space

References axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::initialize().

Member Function Documentation

◆ initialize()

template<int NDIMS, typename ExecSpace , typename FloatType , BVHType Impl>

template<typename BoxIndexable >

int axom::spin::BVH< NDIMS, ExecSpace, FloatType, Impl >::initialize	(	const BoxIndexable	boxes,
		IndexType	numItems
	)

Initializes a BVH instance of specified dimension over a given set of geometric entities, each represented by its corresponding axis-aligned bounding box.

Parameters

[in]	boxes	buffer consisting of bounding boxes for each entity.
[in]	numItems	the total number of items to store in the BVH.

Returns: status set to BVH_BUILD_OK on success.

Note: If an allocatorID has not been set in a call to setAllocatorID(), the code will use the default allocator ID for the execution space specified via axom::execution_space<ExecSpace>::allocatorID() when the BVH object is instantiated.

Warning: The supplied boxes array must point to a buffer in a memory space that is compatible with the execution space. For example, when using CUDA_EXEC, boxes must be in unified memory or GPU memory. The code currently does not check for that.

Precondition: boxes != nullptr; numItems > 0

References AXOM_ANNOTATE_SCOPE, AXOM_LAMBDA, axom::spin::BVH_BUILD_OK, axom::deallocate(), and SLIC_ASSERT.

◆ isInitialized()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

bool axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::isInitialized ( ) const

inline

◆ setAllocatorID()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

void axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::setAllocatorID ( int allocatorID )

inline

Sets the ID of the allocator used by the BVH.

Parameters

[in] allocatorID the ID of the allocator to use in BVH construction

◆ getAllocatorID()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

int axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::getAllocatorID ( ) const

inline

Get the ID of the allocator used by the BVH.

Returns: allocatorID the ID of the allocator used by the BVH.

◆ setScaleFactor()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

void axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::setScaleFactor ( FloatType scale_factor )

inline

Sets the scale factor for scaling the supplied bounding boxes.

Parameters

[in] scale_factor the scale factor

Note: The default scale factor is set to 1.000123

◆ getScaleFactor()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

FloatType axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::getScaleFactor ( ) const

inline

Returns the scale factor used when constructing the BVH.

Returns: scale_factor the scale factor

◆ setTolerance()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

void axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::setTolerance ( FloatType EPS )

inline

Sets the tolerance used for querying the BVH.

Parameters

[in] TOL the tolerance to use.

Note: Default tolerance set to floating_point_limits<FloatType>::epsilon()

◆ getTolerance()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

FloatType axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::getTolerance ( ) const

inline

Returns the tolerance value used for BVH queries.

Returns: TOL the tolerance

◆ getBounds()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

BoxType axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::getBounds ( ) const

inline

Returns the bounds of the BVH, given by the the root bounding box.

Returns: box the bounding box of the constructed BVH, or an invalid bounding box if the BVH has not been initialized.

◆ getTraverser()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>

TraverserType axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >::getTraverser ( ) const

inline

Returns a device-copyable object that can be used to traverse the BVH from inside a device kernel.

Returns: it the traverser object for the current BVH.

\node The traverser object may only be used in the same execution space as the one that the BVH class was instantiated with.

◆ findPoints()

template<int NDIMS, typename ExecSpace , typename FloatType , BVHType Impl>

template<typename PointIndexable >

void axom::spin::BVH< NDIMS, ExecSpace, FloatType, Impl >::findPoints	(	axom::ArrayView< IndexType >	offsets,
		axom::ArrayView< IndexType >	counts,
		axom::Array< IndexType > &	candidates,
		IndexType	numPts,
		PointIndexable	points
	)		const

Finds the candidate bins that contain each of the query points.

Parameters

[out]	offsets	offset to the candidates array for each query point
[out]	counts	stores the number of candidates per query point
[out]	candidates	array of the candidate IDs for each query point
[in]	numPts	the total number of query points supplied
[in]	points	array of points to query against the BVH

Note

Upon completion, the ith query point has:

counts[ i ] candidates
Stored in the candidates array in the following range: [ offsets[ i ], offsets[ i ]+counts[ i ] ]
The sum of all counts is the size of the candidates array, candidates.size()

Precondition: offsets.size() == numPts; counts.size() == numPts; points != nullptr

References AXOM_ANNOTATE_SCOPE, AXOM_HOST_DEVICE, and SLIC_ASSERT.

◆ findRays()

template<int NDIMS, typename ExecSpace , typename FloatType , BVHType Impl>

template<typename RayIndexable >

void axom::spin::BVH< NDIMS, ExecSpace, FloatType, Impl >::findRays	(	axom::ArrayView< IndexType >	offsets,
		axom::ArrayView< IndexType >	counts,
		axom::Array< IndexType > &	candidates,
		IndexType	numRays,
		RayIndexable	rays
	)		const

Finds the candidate bins that intersect the given rays.

Parameters

[out]	offsets	offset to the candidates array for each ray
[out]	counts	stores the number of candidates for each ray
[out]	candidates	array of candidate IDs for each ray
[in]	numRays	the total number of rays
[in]	rays	array of the rays to query against the BVH

Note

After the call to findRays(), the ith ray has:

counts[ i ] candidates
candidates stored in [ offsets[ i ], offsets[i]+counts[i] ]
The sum of all counts is the size of the candidates array, candidates.size()

Precondition: offsets.size() == numRays; counts.size() == numRays; rays != nullptr

References AXOM_ANNOTATE_SCOPE, AXOM_HOST_DEVICE, and SLIC_ASSERT.

◆ findBoundingBoxes()

template<int NDIMS, typename ExecSpace , typename FloatType , BVHType Impl>

template<typename BoxIndexable >

void axom::spin::BVH< NDIMS, ExecSpace, FloatType, Impl >::findBoundingBoxes	(	axom::ArrayView< IndexType >	offsets,
		axom::ArrayView< IndexType >	counts,
		axom::Array< IndexType > &	candidates,
		IndexType	numBoxes,
		BoxIndexable	boxes
	)		const

Finds the candidate bins that intersect the given bounding boxes.

Parameters

[out]	offsets	offset to the candidates array for each bounding box
[out]	counts	stores the number of candidates for each bounding box
[out]	candidates	array of candidate IDs for each bounding box
[in]	numBoxes	the total number of bounding boxes
[in]	boxes	array of boxes to query against the BVH

Note

After the call to findBoundingBoxes(), the ith bounding box has:

counts[ i ] candidates
candidates stored in [ offsets[ i ], offsets[i]+counts[i] ]
The sum of all counts is the size of the candidates array, candidates.size()

Precondition: offsets.size() == numBoxes; counts.size() == numBoxes; boxes != nullptr

References AXOM_ANNOTATE_SCOPE, AXOM_HOST_DEVICE, and SLIC_ASSERT.

◆ writeVtkFile()

template<int NDIMS, typename ExecSpace , typename FloatType , BVHType Impl>

void axom::spin::BVH< NDIMS, ExecSpace, FloatType, Impl >::writeVtkFile ( const std::string & fileName ) const

Writes the BVH to the specified VTK file for visualization.

Parameters

[in] fileName the name of VTK file.

Note: Primarily used for debugging.

References SLIC_ASSERT.

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

/home/docs/checkouts/readthedocs.org/user_builds/axom/checkouts/develop/src/axom/spin/BVH.hpp

Public Types

Public Member Functions

Detailed Description

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH> class axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >

Member Typedef Documentation

◆ BoxType

◆ PointType

◆ RayType

◆ TraverserType

◆ ExecSpaceType

Constructor & Destructor Documentation

◆ BVH() [1/2]

◆ BVH() [2/2]

Member Function Documentation

◆ initialize()

◆ isInitialized()

◆ setAllocatorID()

◆ getAllocatorID()

◆ setScaleFactor()

◆ getScaleFactor()

◆ setTolerance()

◆ getTolerance()

◆ getBounds()

◆ getTraverser()

◆ findPoints()

◆ findRays()

◆ findBoundingBoxes()

◆ writeVtkFile()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename FloatType = double, BVHType BVHImpl = BVHType::LinearBVH>
class axom::spin::BVH< NDIMS, ExecSpace, FloatType, BVHImpl >