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/v0.5.0/src/axom/spin/BVH.hpp>

Public Member Functions
	BVH ()=delete
	Default constructor. Disabled. More...

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

	~BVH ()
	Destructor. 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	getScaleFacor () const
	Returns the scale factor used when constructing the BVH. More...

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

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

int	build ()
	Generates the BVH. More...

void	getBounds (FloatType min, FloatType max) const
	Returns the bounds of the BVH, given by the the root bounding box. More...

void	findPoints (IndexType offsets, IndexType counts, IndexType &candidates, IndexType numPts, const FloatType x, const FloatType y, const FloatType z=nullptr) const
	Finds the candidate bins that contain each of the query points. More...

void	findRays (IndexType offsets, IndexType counts, IndexType &candidates, IndexType numRays, const FloatType x0, const FloatType nx, const FloatType y0, const FloatType ny, const FloatType z0=nullptr, const FloatType *nz=nullptr) const
	Finds the candidate bins that intersect the given rays. More...

void	findBoundingBoxes (IndexType offsets, IndexType counts, IndexType &candidates, IndexType numBoxes, const FloatType xmin, const FloatType xmax, const FloatType ymin, const FloatType ymax, const FloatType zmin=nullptr, const FloatType *zmax=nullptr) 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>
class axom::spin::BVH< NDIMS, ExecSpace, FloatType >

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. For a CPU-only, sequential implementation, see the spin::BVHTree class.

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 double* aabbs = ...
// create a 3D BVH instance in parallel on the CPU using OpenMP
spin::BVH< DIMENSION, axom::OMP_EXEC > bvh( aabbs, numItems );
bvh.build();
// query points supplied in arrays, qx, qy, qz,
const axom::IndexType numPoints = ...
const double* qx = ...
const double* qy = ...
const double* 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, qx, qy, qz );
SLIC_ASSERT( candidates != nullptr );
...
// caller is responsible for properly de-allocating the candidates array
axom::deallocate( candidates );

Constructor & Destructor Documentation

◆ BVH() [1/2]

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

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

delete

Default constructor. Disabled.

◆ BVH() [2/2]

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

axom::spin::BVH< NDIMS, ExecSpace, FloatType >::BVH	(	const FloatType *	boxes,
		IndexType	numItems,
		int	allocatorID = `axom::execution_space< ExecSpace >::allocatorID()`
	)

Creates 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	Umpire allocator ID to use (optional)

Note: boxes is an array of length 2*dimension*numItems, that stores the two corners of the axis-aligned bounding box corresponding to a given geometric entity. For example, in 3D, the two corners of the ith bounding box are given by:
const int offset = i*6;
double xmin = boxes[ offset ];
double ymin = boxes[ offset+1 ];
double zmin = boxes[ offset+2 ];
double xmax = boxes[ offset+3 ];
double ymax = boxes[ offset+4 ];
double zmax = boxes[ offset+5 ];; If an allocatorID is not specified, the code will use the default allocator ID for the execution space specified via the template argument 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

◆ ~BVH()

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

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

Destructor.

Member Function Documentation

◆ getAllocatorID()

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

int axom::spin::BVH< NDIMS, ExecSpace, FloatType >::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>

void axom::spin::BVH< NDIMS, ExecSpace, FloatType >::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.001

◆ getScaleFacor()

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

FloatType axom::spin::BVH< NDIMS, ExecSpace, FloatType >::getScaleFacor ( ) 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>

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

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>

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

inline

Returns the tolerance value used for BVH queries.

Returns: TOL the tolerance

References DISABLE_COPY_AND_ASSIGNMENT, DISABLE_MOVE_AND_ASSIGNMENT, axom::utilities::max(), and axom::utilities::min().

◆ build()

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

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

Generates the BVH.

Returns: status set to BVH_BUILD_OK on success.

Referenced by axom::quest::getMeshTriangle().

◆ getBounds()

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

void axom::spin::BVH< NDIMS, ExecSpace, FloatType >::getBounds	(	FloatType *	min,
		FloatType *	max
	)		const

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

Parameters

[out]	min	buffer to store the lower corner of the root bounding box.
[out]	max	buffer to store the upper corner of the root bounding box.

Note: min/max point to arrays that are at least NDIMS long.

Precondition: min != nullptr; max != nullptr

◆ findPoints()

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

void axom::spin::BVH< NDIMS, ExecSpace, FloatType >::findPoints	(	IndexType *	offsets,
		IndexType *	counts,
		IndexType *&	candidates,
		IndexType	numPts,
		const FloatType *	x,
		const FloatType *	y,
		const FloatType *	z = `nullptr`
	)		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]	x	array of x-coordinates
[in]	y	array of y-coordinates
[in]	z	array of z-coordinates, may be nullptr if 2D

Note

offsets and counts are pointers to arrays of size numPts that are pre-allocated by the caller before calling findPoints().

The candidates array is allocated internally by the method and ownership of the memory is transferred to the caller. Consequently, the caller is responsible for properly deallocating the candidates buffer.

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 ] ]

Precondition: offsets != nullptr; counts != nullptr; candidates == nullptr; x != nullptr; y != nullptr if dimension==2 || dimension==3; z != nullptr if dimension==3

◆ findRays()

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

void axom::spin::BVH< NDIMS, ExecSpace, FloatType >::findRays	(	IndexType *	offsets,
		IndexType *	counts,
		IndexType *&	candidates,
		IndexType	numRays,
		const FloatType *	x0,
		const FloatType *	nx,
		const FloatType *	y0,
		const FloatType *	ny,
		const FloatType *	z0 = `nullptr`,
		const FloatType *	nz = `nullptr`
	)		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]	x0	array consisting the ray source point x-coordinates.
[in]	nx	array consisting the ray normal x-components.
[in]	y0	array consisting the ray source point y-coordinates
[in]	ny	array consisting the ray normal y-components
[in]	z0	array consisting the ray source point z-coorindates (in 3D)
[in]	nz	array consisting the ray normal z-components (in 3D)

Note

offsets and counts are arrays of size numRays that are pre-allocated by the caller, prior to the calling findRays().

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

counts[ i ] candidates
candidates stored in [ offsets[ i ], offsets[i]+counts[i] ]

Precondition: offsets != nullptr; counts != nullptr; candidates == nullptr; x0 != nullptr; nx != nullptr; y0 != nullptr; ny != nullptr; z0 != nullptr if dimension==3; nz != nullptr if dimension==3

◆ findBoundingBoxes()

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

void axom::spin::BVH< NDIMS, ExecSpace, FloatType >::findBoundingBoxes	(	IndexType *	offsets,
		IndexType *	counts,
		IndexType *&	candidates,
		IndexType	numBoxes,
		const FloatType *	xmin,
		const FloatType *	xmax,
		const FloatType *	ymin,
		const FloatType *	ymax,
		const FloatType *	zmin = `nullptr`,
		const FloatType *	zmax = `nullptr`
	)		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]	xmin	array of x-coordinates of lower bounding box corner
[in]	xmax	array of x-coordinates of upper bounding box corner
[in]	ymin	array of y-coordinates of lower bounding box corner
[in]	ymax	array of y-coordinates of upper bounding box corner
[in]	zmin	array of z-coordinates of lower bounding box corner, may be nullptr if 2D
[in]	zmax	array of z-coordinates of upper bounding box corner, may be nullptr if 2D

Note

offsets and counts are pointers to arrays of size numBoxes that are pre-allocated by the caller before calling findBoundingBoxes().

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

counts[ i ] candidates
candidates stored in [ offsets[ i ], offsets[i]+counts[i] ]

Precondition: offsets != nullptr; counts != nullptr; candidates == nullptr; xmin != nullptr; xmax != nullptr; ymin != nullptr; ymax != nullptr; zmin != nullptr if dimension==3; zmax != nullptr if dimension==3

Referenced by axom::quest::getMeshTriangle().

◆ writeVtkFile()

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

void axom::spin::BVH< NDIMS, ExecSpace, FloatType >::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.

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/BVH.hpp

Public Member Functions

Detailed Description

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

Constructor & Destructor Documentation

◆ BVH() [1/2]

◆ BVH() [2/2]

◆ ~BVH()

Member Function Documentation

◆ getAllocatorID()

◆ setScaleFactor()

◆ getScaleFacor()

◆ setTolerance()

◆ getTolerance()

◆ build()

◆ getBounds()

◆ findPoints()

◆ findRays()

◆ findBoundingBoxes()

◆ writeVtkFile()

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