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

Public Member Functions
	AXOM_STATIC_ASSERT_MSG (((NDIMS==2)\|\|(NDIMS==3)), "The BVH class may be used only in 2D or 3D.")

	AXOM_STATIC_ASSERT_MSG (std::is_floating_point< FloatType >::value, "A valid FloatingType must be used for the BVH.")

	AXOM_STATIC_ASSERT_MSG (axom::execution_space< ExecSpace >::valid(), "A valid execution space must be supplied to the BVH.")

	BVH ()=delete
	Default constructor. Disabled. More...

	BVH (const FloatType *boxes, IndexType numItems)
	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...

void	setScaleFactor (FloatType scale_factor)
	Sets the scale factor for scaling the supplied bounding boxes. 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	writeVtkFile (const std::string &fileName) const
	Writes the BVH to the specified VTK file for visualization. More...


void	find (IndexType offsets, IndexType counts, IndexType &candidates, IndexType numPts, const FloatType x, const FloatType *y) const
	Finds the candidate geometric entities that contain each of the given query points. More...

void	find (IndexType offsets, IndexType counts, IndexType &candidates, IndexType numPts, const FloatType x, const FloatType y, const FloatType z) const

Detailed Description

template<int NDIMS, typename ExecSpace, 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.find( 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 , typename FloatType = double>

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

delete

Default constructor. Disabled.

◆ BVH() [2/2]

template<int NDIMS, typename ExecSpace , typename FloatType >

axom::spin::BVH< NDIMS, ExecSpace, FloatType >::BVH	(	const FloatType *	boxes,
		IndexType	numItems
	)

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.

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

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 , typename FloatType >

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

Destructor.

Member Function Documentation

◆ AXOM_STATIC_ASSERT_MSG() [1/3]

template<int NDIMS, typename ExecSpace , typename FloatType = double>

axom::spin::BVH< NDIMS, ExecSpace, FloatType >::AXOM_STATIC_ASSERT_MSG	(	((NDIMS==2)\|\|(NDIMS==3))	,
		"The BVH< NDIMS, ExecSpace, FloatType > class may be used only in 2D or 3D."
	)

Referenced by axom::spin::BVH< NDIMS, ExecSpace, FloatType >::find().

◆ AXOM_STATIC_ASSERT_MSG() [2/3]

template<int NDIMS, typename ExecSpace , typename FloatType = double>

axom::spin::BVH< NDIMS, ExecSpace, FloatType >::AXOM_STATIC_ASSERT_MSG	(	std::is_floating_point< FloatType >::value	,
		"A valid FloatingType must be used for the BVH< NDIMS, ExecSpace, FloatType >."
	)

◆ AXOM_STATIC_ASSERT_MSG() [3/3]

template<int NDIMS, typename ExecSpace , typename FloatType = double>

axom::spin::BVH< NDIMS, ExecSpace, FloatType >::AXOM_STATIC_ASSERT_MSG	(	axom::execution_space< ExecSpace >	::valid(),
		"A valid execution space must be supplied to the BVH< NDIMS, ExecSpace, FloatType >."
	)

◆ setScaleFactor()

template<int NDIMS, typename ExecSpace , 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

References AXOM_HOST_DEVICE, axom::spin::BVH< NDIMS, ExecSpace, FloatType >::build(), axom::spin::BVH< NDIMS, ExecSpace, FloatType >::find(), axom::spin::BVH< NDIMS, ExecSpace, FloatType >::getBounds(), axom::utilities::max(), axom::utilities::min(), and axom::spin::BVH< NDIMS, ExecSpace, FloatType >::writeVtkFile().

◆ build()

template<int NDIMS, typename ExecSpace , typename FloatType >

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

Generates the BVH.

Returns: status set to BVH_BUILD_OK on success.

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

Referenced by axom::spin::BVH< NDIMS, ExecSpace, FloatType >::setScaleFactor().

◆ getBounds()

template<int NDIMS, typename ExecSpace , typename FloatType >

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

References SLIC_ASSERT.

Referenced by axom::spin::BVH< NDIMS, ExecSpace, FloatType >::setScaleFactor().

◆ find() [1/2]

template<int NDIMS, typename ExecSpace , typename FloatType >

void axom::spin::BVH< NDIMS, ExecSpace, FloatType >::find	(	IndexType *	offsets,
		IndexType *	counts,
		IndexType *&	candidates,
		IndexType	numPts,
		const FloatType *	x,
		const FloatType *	y
	)		const

Finds the candidate geometric entities that contain each of the given 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 find().

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

References AXOM_LAMBDA, axom::spin::BVH< NDIMS, ExecSpace, FloatType >::AXOM_STATIC_ASSERT_MSG(), and SLIC_ASSERT.

Referenced by axom::spin::BVH< NDIMS, ExecSpace, FloatType >::setScaleFactor().

◆ find() [2/2]

template<int NDIMS, typename ExecSpace , typename FloatType >

void axom::spin::BVH< NDIMS, ExecSpace, FloatType >::find	(	IndexType *	offsets,
		IndexType *	counts,
		IndexType *&	candidates,
		IndexType	numPts,
		const FloatType *	x,
		const FloatType *	y,
		const FloatType *	z
	)		const

References AXOM_LAMBDA, axom::spin::BVH< NDIMS, ExecSpace, FloatType >::AXOM_STATIC_ASSERT_MSG(), and SLIC_ASSERT.

◆ writeVtkFile()

template<int NDIMS, typename ExecSpace , typename FloatType >

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.

Referenced by axom::spin::BVH< NDIMS, ExecSpace, FloatType >::setScaleFactor().

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

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

Public Member Functions

Detailed Description

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

Constructor & Destructor Documentation

◆ BVH() [1/2]

◆ BVH() [2/2]

◆ ~BVH()

Member Function Documentation

◆ AXOM_STATIC_ASSERT_MSG() [1/3]

◆ AXOM_STATIC_ASSERT_MSG() [2/3]

◆ AXOM_STATIC_ASSERT_MSG() [3/3]

◆ setScaleFactor()

◆ build()

◆ getBounds()

◆ find() [1/2]

◆ find() [2/2]

◆ writeVtkFile()

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