An implicit grid is an occupancy-based spatial index over an indexed set of objects in space. More...

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

Classes
struct	QueryObject
	Device-copyable query object for running implicit grid queries on the GPU. More...

Public Types
using	IndexType = TheIndexType

using	GridCell = primal::Point< IndexType, NDIMS >

using	SpacePoint = primal::Point< double, NDIMS >

using	SpaceVec = primal::Vector< double, NDIMS >

using	SpatialBoundingBox = primal::BoundingBox< double, NDIMS >

using	LatticeType = RectangularLattice< NDIMS, double, IndexType >

using	SizePolicy = slam::policies::RuntimeSize< IndexType >

using	ElementSet = slam::OrderedSet< IndexType, IndexType, SizePolicy >

using	BinSet = slam::OrderedSet< IndexType, IndexType, SizePolicy >

using	BitsetType = slam::BitSet

using	BinBitMap = slam::Map< BitsetType, slam::Set< IndexType, IndexType >, slam::policies::ArrayIndirection< IndexType, BitsetType >, slam::policies::StrideOne< IndexType > >

Public Member Functions
	ImplicitGrid ()
	Default constructor for an ImplicitGrid. More...

	ImplicitGrid (const SpatialBoundingBox &boundingBox, const GridCell *gridRes, int numElts, int allocatorID=axom::execution_space< ExecSpace >::allocatorID())
	Constructor for an implicit grid from a bounding box, a grid resolution a number of elements. More...

	ImplicitGrid (const double bbMin, const double bbMax, const int *gridRes, int numElts, int allocatorID=axom::execution_space< ExecSpace >::allocatorID())
	Constructor for an implicit grid from arrays of primitive types. More...

bool	isInitialized () const

QueryObject	getQueryObject () const

void	initialize (const SpatialBoundingBox &boundingBox, const GridCell *gridRes, int numElts, int allocatorID=axom::execution_space< ExecSpace >::allocatorID())
	Initializes an implicit grid or resolution gridRes over an axis aligned domain covered by boundingBox. The implicit grid indexes a set with numElts elements. More...

const GridCell &	gridResolution () const

int	numIndexElements () const

void	insert (const SpatialBoundingBox &bbox, IndexType idx)
	Inserts an element with index idx and bounding box bbox into the implicit grid. More...

void	insert (IndexType nelems, const SpatialBoundingBox *bboxes, IndexType startIdx=0)
	Inserts a set of elements represented by bounding boxes bboxes and beginning at index startIdx into the implicit grid. More...

BitsetType	getCandidates (const SpacePoint &pt) const

BitsetType	getCandidates (const GridCell &gridCell) const

BitsetType	getCandidates (const SpatialBoundingBox &box) const

template<typename QueryGeom >
std::vector< IndexType >	getCandidatesAsArray (const QueryGeom &query) const

template<typename QueryGeom >
void	getCandidatesAsArray (axom::IndexType qsize, const QueryGeom *queryObjs, axom::ArrayView< IndexType > outOffsets, axom::ArrayView< IndexType > outCounts, axom::Array< IndexType > &outCandidates) const
	Returns a list of candidates in the vicinity of a set of query objects. More...

void	getCandidatesAsArray (axom::ArrayView< const SpacePoint > queryObjs, axom::ArrayView< IndexType > outOffsets, axom::ArrayView< IndexType > outCounts, axom::Array< IndexType > &outCandidates) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

void	getCandidatesAsArray (axom::ArrayView< const SpatialBoundingBox > queryObjs, axom::ArrayView< IndexType > outOffsets, axom::ArrayView< IndexType > outCounts, axom::Array< IndexType > &outCandidates) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

bool	contains (const GridCell &gridCell, IndexType idx) const

Detailed Description

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename TheIndexType = int>
class axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >

An implicit grid is an occupancy-based spatial index over an indexed set of objects in space.

An ImplicitGrid divides a given rectilinear slab of space (defined by an axis aligned bounding box) into uniformly sized cells of a specified resolution. The GridCells of the ImplicitGrid index a subset of the items from an indexed set whose cardinality is specified during the ImplicitGrid's initialization. Users can insert items from the indexed set into an ImplicitGrid by providing the item's bounding box and index.

In contrast to a spin::UniformGrid, which encodes an array of indices for each cell in the underlying multidimensional grid, the ImplicitGrid encodes a single array of bins per dimension, each of which has a bitset over the index space. Thus, the storage overhead of an ImplicitGrid is fixed at initialization time to \( numElts * sum_i { res[i] } \) bits. Queries are implemented in terms of unions and intersections of bitsets.

One might prefer an ImplicitGrid over a UniformGrid when one expects a relatively dense index relative to the grid resolution (i.e. that there will be many items indexed per bucket). The ImplicitGrid is designed for quick indexing and searching over a static (and relatively small index space) in a relatively coarse grid.

Member Typedef Documentation

◆ IndexType

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::IndexType = TheIndexType

◆ GridCell

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::GridCell = primal::Point<IndexType, NDIMS>

◆ SpacePoint

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::SpacePoint = primal::Point<double, NDIMS>

◆ SpaceVec

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::SpaceVec = primal::Vector<double, NDIMS>

◆ SpatialBoundingBox

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::SpatialBoundingBox = primal::BoundingBox<double, NDIMS>

◆ LatticeType

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::LatticeType = RectangularLattice<NDIMS, double, IndexType>

◆ SizePolicy

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::SizePolicy = slam::policies::RuntimeSize<IndexType>

◆ ElementSet

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::ElementSet = slam::OrderedSet<IndexType, IndexType, SizePolicy>

◆ BinSet

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::BinSet = slam::OrderedSet<IndexType, IndexType, SizePolicy>

◆ BitsetType

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::BitsetType = slam::BitSet

◆ BinBitMap

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

using axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::BinBitMap = slam::Map<BitsetType, slam::Set<IndexType, IndexType>, slam::policies::ArrayIndirection<IndexType, BitsetType>, slam::policies::StrideOne<IndexType> >

Constructor & Destructor Documentation

◆ ImplicitGrid() [1/3]

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

axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::ImplicitGrid ( )

inline

Default constructor for an ImplicitGrid.

Note: Users must call initialize() to initialize the ImplicitGrid after constructing with the default constructor

◆ ImplicitGrid() [2/3]

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

axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::ImplicitGrid	(	const SpatialBoundingBox &	boundingBox,
		const GridCell *	gridRes,
		int	numElts,
		int	allocatorID = `axom::execution_space<ExecSpace>::allocatorID()`
	)

inline

Constructor for an implicit grid from a bounding box, a grid resolution a number of elements.

Parameters

[in]	boundingBox	Bounding box of domain to index
[in]	gridRes	Pointer to resolution for lattice covering bounding box
[in]	numElts	The number of elements to be indexed

Precondition: gridRes is either NULL or has NDIMS coordinates

See also: initialize() for details on setting grid resolution when gridRes is NULL

References axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::initialize().

◆ ImplicitGrid() [3/3]

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

axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::ImplicitGrid	(	const double *	bbMin,
		const double *	bbMax,
		const int *	gridRes,
		int	numElts,
		int	allocatorID = `axom::execution_space<ExecSpace>::allocatorID()`
	)

inline

Constructor for an implicit grid from arrays of primitive types.

Parameters

[in]	bbMin	Lower bounds of mesh bounding box
[in]	bbMax	Upper bounds of mesh bounding box
[in]	gridRes	Resolution for lattice covering mesh bounding box
[in]	numElts	The number of elements in the index space

Precondition: bbMin and bbMax are not NULL and have NDIMS coordinates; gridRes is either NULL or has NDIMS coordinates

See also: initialize() for details on setting grid resolution when gridRes is NULL

References axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::initialize(), and SLIC_ASSERT.

Member Function Documentation

◆ isInitialized()

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

bool axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::isInitialized ( ) const

inline

Predicate to check if the ImplicitGrid has been initialized

◆ getQueryObject()

template<int NDIMS, typename ExecSpace , typename IndexType >

ImplicitGrid< NDIMS, ExecSpace, IndexType >::QueryObject axom::spin::ImplicitGrid< NDIMS, ExecSpace, IndexType >::getQueryObject

References SLIC_ASSERT.

◆ initialize()

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

void axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::initialize	(	const SpatialBoundingBox &	boundingBox,
		const GridCell *	gridRes,
		int	numElts,
		int	allocatorID = `axom::execution_space<ExecSpace>::allocatorID()`
	)

inline

Initializes an implicit grid or resolution gridRes over an axis aligned domain covered by boundingBox. The implicit grid indexes a set with numElts elements.

Parameters

[in]	boundingBox	Bounding box of domain to index
[in]	gridRes	Resolution for lattice covering bounding box
[in]	numElts	The number of elements to be indexed

Precondition: The ImplicitGrid has not already been initialized

Note: When gridRes is NULL, we use a heuristic to set the grid resolution to the N^th root of numElts. We also ensure that the resolution along any dimension is at least one.

References axom::primal::Point< T, NDIMS >::array(), axom::Array< T, DIM, SPACE >::fill(), axom::utilities::max(), axom::primal::Vector< T, NDIMS >::norm(), axom::primal::BoundingBox< T, NDIMS >::range(), axom::spin::rectangular_lattice_from_bounding_box(), and SLIC_ASSERT.

◆ gridResolution()

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

const GridCell& axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::gridResolution ( ) const

inline

Accessor for ImplicitGrid's resolution

◆ numIndexElements()

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

int axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::numIndexElements ( ) const

inline

Returns the number of elements in the ImplicitGrid's index set

References axom::slam::OrderedSet< PosType, ElemType, SizePolicy, OffsetPolicy, StridePolicy, IndirectionPolicy, SubsettingPolicy, InterfacePolicy >::size().

◆ insert() [1/2]

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

void axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::insert	(	const SpatialBoundingBox &	bbox,
		IndexType	idx
	)

inline

Inserts an element with index idx and bounding box bbox into the implicit grid.

Parameters

[in]	bbox	The bounding box of the element
[in]	idx	The index of the element

References axom::execution_space< ExecSpace >::allocatorID(), and axom::Array< T, DIM, SPACE >::data().

◆ insert() [2/2]

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

void axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::insert	(	IndexType	nelems,
		const SpatialBoundingBox *	bboxes,
		IndexType	startIdx = `0`
	)

inline

Inserts a set of elements represented by bounding boxes bboxes and beginning at index startIdx into the implicit grid.

Parameters

[in]	nelems	the number of elements to insert
[in]	bboxes	an array of bounding boxes for each element
[in]	startIdx	the index of the first bounding box in bboxes

References AXOM_LAMBDA, axom::Array< T, DIM, SPACE >::data(), axom::slam::Map< T, S, IndPol, StrPol, IfacePol >::data(), axom::primal::BoundingBox< T, NDIMS >::expand(), axom::primal::BoundingBox< T, NDIMS >::getMax(), axom::primal::BoundingBox< T, NDIMS >::getMin(), axom::spin::RectangularLattice< NDIMS, SpaceCoordType, CellCoordType >::gridCell(), axom::slam::Map< T, S, IndPol, StrPol, IfacePol >::set(), axom::slam::Set< PosType, ElemType >::size(), and SLIC_ASSERT.

◆ getCandidates() [1/3]

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

BitsetType axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::getCandidates ( const SpacePoint & pt ) const

inline

Finds the candidate elements in the vicinity of query point pt

Parameters

[in] pt The query point

Returns: A bitset bSet whose bits correspond to the elements of the IndexSet. The bits of bSet are set if their corresponding element bounding boxes overlap the grid cell containing pt.

References axom::utilities::clampUpper().

◆ getCandidates() [2/3]

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

BitsetType axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::getCandidates ( const GridCell & gridCell ) const

inline

Finds the candidate elements in the given gridCell of the grid

Parameters

[in] gridCell The cell of the grid

Returns: A bitset whose bits correspond to the elements of the IndexSet. The bits are set if their corresponding element bounding boxes overlap gridCell

◆ getCandidates() [3/3]

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

BitsetType axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::getCandidates ( const SpatialBoundingBox & box ) const

inline

Finds the candidate elements in the vicinity of query box box

Parameters

[in] box The query box

Returns: A bitset bSet whose bits correspond to the elements of the IndexSet. The bits of bSet are set if their corresponding element bounding boxes overlap the grid cell containing box

References axom::primal::BoundingBox< T, NDIMS >::getMax(), and axom::primal::BoundingBox< T, NDIMS >::getMin().

◆ getCandidatesAsArray() [1/4]

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

template<typename QueryGeom >

std::vector<IndexType> axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::getCandidatesAsArray ( const QueryGeom & query ) const

inline

Returns an explicit list of candidates in the vicinity of a query object

Template Parameters

QueryGeom The type of the query object (e.g. point or box)

Parameters

[in] query The query object

Returns: A list of indexes from the IndexSet whose corresponding bounding boxes overlap the grid cell containing query

Precondition: This function is implemented in terms of ImplicitGrid::getCandidates(const QueryGeom& ). An overload for the actual QueryGeom type (e.g. SpacePoint or SpatialBoundingBox) must exist.

Note: This function returns the same information as getCandidates(), but in a different format. While the latter returns a bitset of the candidates, this function returns an explicit list of indices.

See also: getCandidates()

References axom::slam::BitSet::count(), axom::slam::BitSet::find_first(), and axom::slam::BitSet::find_next().

◆ getCandidatesAsArray() [2/4]

template<int NDIMS, typename ExecSpace , typename IndexType >

template<typename QueryGeom >

void axom::spin::ImplicitGrid< NDIMS, ExecSpace, IndexType >::getCandidatesAsArray	(	axom::IndexType	qsize,
		const QueryGeom *	queryObjs,
		axom::ArrayView< IndexType >	outOffsets,
		axom::ArrayView< IndexType >	outCounts,
		axom::Array< IndexType > &	outCandidates
	)		const

Returns a list of candidates in the vicinity of a set of query objects.

Template Parameters

QueryGeom The type of the query object (e.g. point or box)

Parameters

[in]	qsize	The number of objects to query against the implicit grid
[in]	queryObjs	The array of query objects, of length qsize
[out]	outOffsets	Offsets into the candidates array for each query object
[out]	outCounts	The number of candidates for each query object
[out]	outCandidates	The candidate IDs for each query object

Note

outOffsets and outCounts should point to arrays allocated in a memory space accessible from the given execution space, and be of length qsize.

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

References AXOM_LAMBDA, axom::ArrayView< T, DIM, SPACE >::data(), axom::Array< T, DIM, SPACE >::push_back(), axom::ArrayView< T, DIM, SPACE >::size(), SLIC_ERROR_IF, and axom::Array< T, DIM, SPACE >::view().

◆ getCandidatesAsArray() [3/4]

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

void axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::getCandidatesAsArray	(	axom::ArrayView< const SpacePoint >	queryObjs,
		axom::ArrayView< IndexType >	outOffsets,
		axom::ArrayView< IndexType >	outCounts,
		axom::Array< IndexType > &	outCandidates
	)		const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

References axom::ArrayView< T, DIM, SPACE >::data(), and axom::ArrayView< T, DIM, SPACE >::size().

◆ getCandidatesAsArray() [4/4]

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

void axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::getCandidatesAsArray	(	axom::ArrayView< const SpatialBoundingBox >	queryObjs,
		axom::ArrayView< IndexType >	outOffsets,
		axom::ArrayView< IndexType >	outCounts,
		axom::Array< IndexType > &	outCandidates
	)		const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

References axom::ArrayView< T, DIM, SPACE >::data(), and axom::ArrayView< T, DIM, SPACE >::size().

◆ contains()

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

bool axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >::contains	(	const GridCell &	gridCell,
		IndexType	idx
	)		const

inline

Tests whether grid cell gridPt indexes the element with index idx

Parameters

[in]	gridCell	The cell within the ImplicitGrid that we are testing
[in]	idx	An element index from the IndexSet to test

Precondition: idx should be in the IndexSet. I.e. 0 <= idx < numIndexElements()

Returns: True if the bounding box of element idx overlaps with GridCell gridCell.

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

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

Classes

Public Types

Public Member Functions

Detailed Description

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename TheIndexType = int> class axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >

Member Typedef Documentation

◆ IndexType

◆ GridCell

◆ SpacePoint

◆ SpaceVec

◆ SpatialBoundingBox

◆ LatticeType

◆ SizePolicy

◆ ElementSet

◆ BinSet

◆ BitsetType

◆ BinBitMap

Constructor & Destructor Documentation

◆ ImplicitGrid() [1/3]

◆ ImplicitGrid() [2/3]

◆ ImplicitGrid() [3/3]

Member Function Documentation

◆ isInitialized()

◆ getQueryObject()

◆ initialize()

◆ gridResolution()

◆ numIndexElements()

◆ insert() [1/2]

◆ insert() [2/2]

◆ getCandidates() [1/3]

◆ getCandidates() [2/3]

◆ getCandidates() [3/3]

◆ getCandidatesAsArray() [1/4]

◆ getCandidatesAsArray() [2/4]

◆ getCandidatesAsArray() [3/4]

◆ getCandidatesAsArray() [4/4]

◆ contains()

template<int NDIMS, typename ExecSpace = axom::SEQ_EXEC, typename TheIndexType = int>
class axom::spin::ImplicitGrid< NDIMS, ExecSpace, TheIndexType >