Spatial partitioning data structure that divides 3D space into a set of sparse grids. Allowing for efficient querying of point neighbours within a certain region. Implements [4]. More...

#include <HierarchicalHashGrid.h>

Public Types
using	ScalarType = TScalar
	Type alias for scalar values (e.g., float or double).

using	IndexType = TIndex
	Type alias for index values (e.g., int or long).

Public Member Functions
	HierarchicalHashGrid ()=default
	Default constructor for HierarchicalHashGrid.

	HierarchicalHashGrid (IndexType nPrimitives, IndexType nBuckets=0)
	Construct a HierarchicalHashGrid with a specific number of primitives.

void	Configure (IndexType nPrimitives, IndexType nBuckets=0)
	Configure the hash grid with a specific number of buckets.

template<class TDerivedL, class TDerivedU>
void	Construct (Eigen::DenseBase< TDerivedL > const &L, Eigen::DenseBase< TDerivedU > const &U)
	Construct a HashGrid from lower and upper bounds of input axis-aligned bounding boxes (aabbs).

template<class FOnPair, class TDerivedX>
void	BroadPhase (Eigen::DenseBase< TDerivedX > const &X, FOnPair fOnPair) const
	Find all primitives whose cell overlaps with points `X`.

template<class FOnPair, class TDerivedL, class TDerivedU>
void	BroadPhase (Eigen::DenseBase< TDerivedL > const &L, Eigen::DenseBase< TDerivedU > const &U, FOnPair fOnPair) const
	Find all primitives whose cell overlaps with aabbs (L,U).

template<class FOnPair, class TDerivedLP, class TDerivedUP, class TDerivedX>
void	BroadPhase (Eigen::DenseBase< TDerivedLP > const &LP, Eigen::DenseBase< TDerivedUP > const &UP, Eigen::DenseBase< TDerivedX > const &XQ, FOnPair fOnPair) const
	Find all primitive AABBs overlapping with query points X.

template<class FOnPair, class TDerivedLP, class TDerivedUP, class TDerivedLQ, class TDerivedUQ>
void	BroadPhase (Eigen::DenseBase< TDerivedLP > const &LP, Eigen::DenseBase< TDerivedUP > const &UP, Eigen::DenseBase< TDerivedLQ > const &LQ, Eigen::DenseBase< TDerivedUQ > const &UQ, FOnPair fOnPair) const
	Find all primitive AABBs overlapping with query AABBs.

IndexType	NumberOfBuckets () const
	Get the number of buckets in the hash table.

IndexType	NumberOfLevels () const
	Get the number of levels in the hierarchical grid.

auto	Levels () const -> std::span< std::int16_t const >
	Get the set of levels in the hierarchical grid.

template<class TDerivedX>
auto	ToIntegerCoordinates (Eigen::DenseBase< TDerivedX > const &X, ScalarType const cellSize) const -> Eigen::Vector< IndexType, kDims >
	Convert a point `X` to integer coordinates in the grid.

template<class TDerivedX>
auto	Hash (Eigen::DenseBase< TDerivedX > const &X, std::int16_t l) const
	Hash a point `X` at level `l` in the grid. See [4] for details on the hashing scheme.

Static Public Attributes
static constexpr int	kDims = Dims
	Number of spatial dimensions.

static constexpr int	kMaxCellsPerPrimitive
	Maximum number of cells per primitive in the grid.

Protected Member Functions
void	ClearHashTable ()
	Clear the hash table, resetting all internal data structures.

Detailed Description

template<int Dims, common::CFloatingPoint TScalar = Scalar, common::CIndex TIndex = Index>
class pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >

Spatial partitioning data structure that divides 3D space into a set of sparse grids. Allowing for efficient querying of point neighbours within a certain region. Implements [4].

Template Parameters

Dims	Number of spatial dimensions (2 or 3).
TScalar	Type of scalar values (e.g., float or double).
TIndex	Type of index values (e.g., int or long).

Constructor & Destructor Documentation

◆ HierarchicalHashGrid()

template<int Dims, common::CFloatingPoint TScalar, common::CIndex TIndex>

pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::HierarchicalHashGrid	(	IndexType	nPrimitives,
		IndexType	nBuckets = 0 )

Construct a HierarchicalHashGrid with a specific number of primitives.

Parameters

nPrimitives	Number of primitives in the hash grid.
nBuckets	Number of buckets in the hash grid. The actual number of allocated buckets will be `max(nBuckets, nPrimitives * kMaxCellsPerPrimitive)`.

Member Function Documentation

◆ BroadPhase() [1/4]

template<int Dims, common::CFloatingPoint TScalar, common::CIndex TIndex>

template<class FOnPair, class TDerivedL, class TDerivedU>

void pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::BroadPhase	(	Eigen::DenseBase< TDerivedL > const &	L,
		Eigen::DenseBase< TDerivedU > const &	U,
		FOnPair	fOnPair ) const

inline

Find all primitives whose cell overlaps with aabbs (L,U).

Template Parameters

FOnPair	Function with signature `void(Index q, Index p)` where `q` is the index of a query point and `p` is the index of a primitive that potentially overlaps with the query point.
TDerivedL	Eigen type of query lower bounds.
TDerivedU	Eigen type of query upper bounds.

Parameters

L	`\|# dims\| x \|# query aabbs\|` matrix of query aabb lower bounds.
U	`\|# dims\| x \|# query aabbs\|` matrix of query aabb upper bounds.
fOnPair	Function to process a broad-phase pair

◆ BroadPhase() [2/4]

template<int Dims, common::CFloatingPoint TScalar, common::CIndex TIndex>

template<class FOnPair, class TDerivedLP, class TDerivedUP, class TDerivedLQ, class TDerivedUQ>

void pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::BroadPhase	(	Eigen::DenseBase< TDerivedLP > const &	LP,
		Eigen::DenseBase< TDerivedUP > const &	UP,
		Eigen::DenseBase< TDerivedLQ > const &	LQ,
		Eigen::DenseBase< TDerivedUQ > const &	UQ,
		FOnPair	fOnPair ) const

inline

Find all primitive AABBs overlapping with query AABBs.

Template Parameters

FOnPair	Function with signature `void(Index q, Index p)` where `q` is the index of a query AABB and `p` is the index of a primitive AABB overlaps with the query AABB.
TDerivedLP	Eigen type of lower bounds of primitive AABBs.
TDerivedUP	Eigen type of upper bounds of primitive AABBs.
TDerivedLQ	Eigen type of lower bounds of query AABBs.
TDerivedUQ	Eigen type of upper bounds of query AABBs.

Parameters

LP	`\|# dims\| x \|# primitives\|` lower bounds of the primitive AABBs.
UP	`\|# dims\| x \|# primitives\|` upper bounds of the primitive AABBs.
LQ	`\|# dims\| x \|# query aabbs\|` lower bounds of the query AABBs.
UQ	`\|# dims\| x \|# query aabbs\|` upper bounds of the query AABBs.
fOnPair	Function to process a broad-phase pair

◆ BroadPhase() [3/4]

template<int Dims, common::CFloatingPoint TScalar, common::CIndex TIndex>

template<class FOnPair, class TDerivedLP, class TDerivedUP, class TDerivedX>

void pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::BroadPhase	(	Eigen::DenseBase< TDerivedLP > const &	LP,
		Eigen::DenseBase< TDerivedUP > const &	UP,
		Eigen::DenseBase< TDerivedX > const &	XQ,
		FOnPair	fOnPair ) const

inline

Find all primitive AABBs overlapping with query points X.

Template Parameters

FOnPair	Function with signature `void(Index q, Index p)` where `q` is the index of a query point and `p` is the index of a primitive that potentially overlaps with the query point.
TDerivedLP	Eigen type of lower bounds of primitive AABBs.
TDerivedUP	Eigen type of upper bounds of primitive AABBs.
TDerivedX	Eigen type of query points.

Parameters

LP	`\|# dims\| x \|# primitives\|` lower bounds of the primitive AABBs.
UP	`\|# dims\| x \|# primitives\|` upper bounds of the primitive AABBs.
XQ	`\|# dims\| x \|# query points\|` matrix of query points.
fOnPair	Function to process a broad-phase pair

◆ BroadPhase() [4/4]

template<int Dims, common::CFloatingPoint TScalar, common::CIndex TIndex>

template<class FOnPair, class TDerivedX>

void pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::BroadPhase	(	Eigen::DenseBase< TDerivedX > const &	X,
		FOnPair	fOnPair ) const

Find all primitives whose cell overlaps with points X.

Template Parameters

FOnPair	Function with signature `void(Index q, Index p)` where `q` is the index of a query point and `p` is the index of a primitive that potentially overlaps with the query point.
TDerivedX	Eigen type of query points.

Parameters

X	`\|# dims\| x \|# query points\|` matrix of query points.
fOnPair	Function to process a broad-phase pair

◆ Configure()

template<int Dims, common::CFloatingPoint TScalar, common::CIndex TIndex>

void pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::Configure	(	IndexType	nPrimitives,
		IndexType	nBuckets = 0 )

inline

Configure the hash grid with a specific number of buckets.

Parameters

nPrimitives	Number of primitives in the hash grid.
nBuckets	Number of buckets in the hash grid. The actual number of allocated buckets will be `max(nBuckets, nPrimitives * kMaxCellsPerPrimitive)`.

Precondition: nBuckets >= nPrimitives * kMaxCellsPerPrimitive

◆ Construct()

template<int Dims, common::CFloatingPoint TScalar, common::CIndex TIndex>

template<class TDerivedL, class TDerivedU>

void pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::Construct	(	Eigen::DenseBase< TDerivedL > const &	L,
		Eigen::DenseBase< TDerivedU > const &	U )

Construct a HashGrid from lower and upper bounds of input axis-aligned bounding boxes (aabbs).

Time complexity is \( O(n) \) where n is the number of buckets.

Note: Does not handle zero aabb extents.

Template Parameters

TDerivedL	Type of the lower bounds matrix.
TDerivedU	Type of the upper bounds matrix.

Parameters

L	`\|# dims\| x \|# aabbs\|` lower bounds of the aabbs.
U	`\|# dims\| x \|# aabbs\|` upper bounds of the aabbs.

◆ Hash()

template<int Dims, common::CFloatingPoint TScalar, common::CIndex TIndex>

template<class TDerivedX>

auto pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::Hash	(	Eigen::DenseBase< TDerivedX > const &	X,
		std::int16_t	l ) const

inline

Hash a point X at level l in the grid. See [4] for details on the hashing scheme.

Parameters

X	`\|# dims\| x 1` point in space.
l	Level of the grid at which to hash the point.

Returns: Hash value for the point at level l.

◆ Levels()

template<int Dims, common::CFloatingPoint TScalar = Scalar, common::CIndex TIndex = Index>

auto pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::Levels ( ) const -> std::span<std::int16_t const>

inline

Get the set of levels in the hierarchical grid.

Returns: |# levels| x 1 vector of levels in the hierarchical grid.

◆ NumberOfBuckets()

template<int Dims, common::CFloatingPoint TScalar = Scalar, common::CIndex TIndex = Index>

IndexType pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::NumberOfBuckets ( ) const

inline

Get the number of buckets in the hash table.

Returns: The number of buckets in the hash table.

◆ NumberOfLevels()

template<int Dims, common::CFloatingPoint TScalar = Scalar, common::CIndex TIndex = Index>

IndexType pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::NumberOfLevels ( ) const

inline

Get the number of levels in the hierarchical grid.

Returns: The number of levels in the hierarchical grid.

◆ ToIntegerCoordinates()

template<int Dims, common::CFloatingPoint TScalar, common::CIndex TIndex>

template<class TDerivedX>

auto pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::ToIntegerCoordinates	(	Eigen::DenseBase< TDerivedX > const &	X,
		ScalarType const	cellSize ) const -> Eigen::Vector<IndexType, kDims>

inline

Convert a point X to integer coordinates in the grid.

Template Parameters

TDerivedX Eigen type of the point.

Parameters

X	`\|# dims\| x 1` point in space.
cellSize	Size of each grid cell.

Returns: |# dims| x 1 vector of integer coordinates in the grid.

Member Data Documentation

◆ kMaxCellsPerPrimitive

template<int Dims, common::CFloatingPoint TScalar = Scalar, common::CIndex TIndex = Index>

int pbat::geometry::HierarchicalHashGrid< Dims, TScalar, TIndex >::kMaxCellsPerPrimitive

staticconstexpr

Initial value:

=

Dims == 2 ? 4 : 8

Maximum number of cells per primitive in the grid.

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

C:/git/PhysicsBasedAnimationToolkit/source/pbat/geometry/HierarchicalHashGrid.h

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ HierarchicalHashGrid()

Member Function Documentation

◆ BroadPhase() [1/4]

◆ BroadPhase() [2/4]

◆ BroadPhase() [3/4]

◆ BroadPhase() [4/4]

◆ Configure()

◆ Construct()

◆ Hash()

◆ Levels()

◆ NumberOfBuckets()

◆ NumberOfLevels()

◆ ToIntegerCoordinates()

Member Data Documentation

◆ kMaxCellsPerPrimitive