HashGrid is a spatial partitioning data structure that divides 3D space into a sparse grid of cells, allowing for efficient querying of point neighbours within a certain region. More...

#include <HashGrid.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
	HashGrid ()=default
	Default constructor for HashGrid.

	HashGrid (ScalarType cellSize, IndexType nBuckets)
	Construct a HashGrid with a specific cell size and number of buckets.

void	Configure (ScalarType cellSize, IndexType nBuckets)
	Configure the hash grid with a specific cell size and number of buckets.

void	Reserve (IndexType nPrimitives)
	Reserve space for a specific number of primitives in the hash grid.

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

template<class FHash, class TDerivedX>
void	Construct (Eigen::DenseBase< TDerivedX > const &X, FHash fHash)
	Construct a HashGrid from points.

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

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

template<class TDerivedX>
auto	Cell (Eigen::DenseBase< TDerivedX > const &X) const -> Eigen::Matrix< ScalarType, kDims, 2 >
	Get the hash grid's cell (i.e. aabb) corresponding to a point `X`.

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

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

Detailed Description

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

HashGrid is a spatial partitioning data structure that divides 3D space into a sparse grid of cells, allowing for efficient querying of point neighbours within a certain region.

Note: This implementation performs poorly when primitive sizes have high variance, as it uses a fixed cell size. It is best suited for scenarios where the size of primitives is relatively uniform.

Template Parameters

TScalar	Type of scalar values (e.g., float or double).
TIndex	Type of index values (e.g., int or long).

Constructor & Destructor Documentation

◆ HashGrid()

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

pbat::geometry::HashGrid< Dims, TScalar, TIndex >::HashGrid	(	ScalarType	cellSize,
		IndexType	nBuckets )

inline

Construct a HashGrid with a specific cell size and number of buckets.

Parameters

cellSize	Size of each grid cell along each dimension.
nBuckets	Number of buckets in the hash table.

Member Function Documentation

◆ BroadPhase()

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

template<class FOnPair, class FHash, class TDerivedX>

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

inline

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.
FHash	Function with signature `IndexType(Eigen::DenseBase<TDerivedIX> const& ixyz)`
TDerivedX	Eigen type of query points.

Parameters

X	`\|# dims\| x \|# query points\|` matrix of query points.
fOnPair	Function to process a broad-phase pair
fHash	Hash function for IndexType `# dims` point coordinates.

◆ Cell()

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

template<class TDerivedX>

auto pbat::geometry::HashGrid< Dims, TScalar, TIndex >::Cell ( Eigen::DenseBase< TDerivedX > const & X ) const -> Eigen::Matrix<ScalarType, kDims, 2>

inline

Get the hash grid's cell (i.e. aabb) corresponding to a point X.

Parameters

X	`\|# dims\| x 1` point in space.

Returns: |# dims| x 2 matrix representing the cell's lower and upper bounds in columns.

◆ Configure()

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

void pbat::geometry::HashGrid< Dims, TScalar, TIndex >::Configure	(	ScalarType	cellSize,
		IndexType	nBuckets )

inline

Configure the hash grid with a specific cell size and number of buckets.

Parameters

cellSize	Size of each grid cell along each dimension.
nBuckets	Number of buckets in the hash table.

◆ Construct() [1/2]

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

template<class FHash, class TDerivedL, class TDerivedU>

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

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.

Template Parameters

FHash	Type of the hash function with signature `template <class TDerivedIX> IndexType(Eigen::DenseBase<TDerivedIX> const& ixyz)`.
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.
fHash	Hash function for IndexType `# dims` point coordinates.

◆ Construct() [2/2]

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

template<class FHash, class TDerivedX>

void pbat::geometry::HashGrid< Dims, TScalar, TIndex >::Construct	(	Eigen::DenseBase< TDerivedX > const &	X,
		FHash	fHash )

inline

Construct a HashGrid from points.

Template Parameters

FHash	Type of the hash function with signature `template <class TDerivedIX> IndexType(Eigen::DenseBase<TDerivedIX> const& ixyz)`.
TDerivedX	Type of the points matrix.

Parameters

X	`\|# dims\| x \|# points\|` points.
fHash	Hash function for IndexType `# dims` point coordinates.

◆ NumberOfBuckets()

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

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

inline

Get the number of buckets in the hash table.

Returns: The number of buckets in the hash table.

◆ Reserve()

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

void pbat::geometry::HashGrid< Dims, TScalar, TIndex >::Reserve ( IndexType nPrimitives )

inline

Reserve space for a specific number of primitives in the hash grid.

Parameters

nPrimitives Number of primitives to reserve space for.

◆ ToIntegerCoordinates()

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

template<class TDerivedX>

auto pbat::geometry::HashGrid< Dims, TScalar, TIndex >::ToIntegerCoordinates ( Eigen::DenseBase< TDerivedX > const & X ) 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.

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

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

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

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ HashGrid()

Member Function Documentation

◆ BroadPhase()

◆ Cell()

◆ Configure()

◆ Construct() [1/2]

◆ Construct() [2/2]

◆ NumberOfBuckets()

◆ Reserve()

◆ ToIntegerCoordinates()