Axis-aligned radix tree hierarchy of axis-aligned bounding boxes. More...

#include <AabbRadixTreeHierarchy.h>

Public Types
using	IndexType = Index
	Type of the indices.

using	SelfType = AabbRadixTreeHierarchy<kDims>
	Type of this template instantiation.

Public Member Functions
template<class TDerivedL, class TDerivedU>
	AabbRadixTreeHierarchy (Eigen::DenseBase< TDerivedL > const &L, Eigen::DenseBase< TDerivedU > const &U)
	Construct an AabbRadixTreeHierarchy from an input AABB matrix B.

template<class TDerivedL, class TDerivedU>
void	Construct (Eigen::DenseBase< TDerivedL > const &L, Eigen::DenseBase< TDerivedU > const &U)
	Construct an AabbRadixTreeHierarchy from an input AABB matrix B.

template<class TDerivedL, class TDerivedU>
void	Update (Eigen::DenseBase< TDerivedL > const &L, Eigen::DenseBase< TDerivedU > const &U)
	Recomputes k-D tree node AABBs given the object AABBs.

template<class FNodeOverlaps, class FObjectOverlaps, class FOnOverlap>
void	Overlaps (FNodeOverlaps fNodeOverlaps, FObjectOverlaps fObjectOverlaps, FOnOverlap fOnOverlap) const
	Find all objects that overlap with some user-defined query.

template<class FDistanceToNode, class FDistanceToObject, class FOnNearestNeighbour>
void	NearestNeighbours (FDistanceToNode fDistanceToNode, FDistanceToObject fDistanceToObject, FOnNearestNeighbour fOnNearestNeighbour, Scalar radius=std::numeric_limits< Scalar >::max(), Scalar eps=Scalar(0)) const
	Find the nearest neighbour to some user-defined query. If there are multiple nearest neighbours, we may return a certain number > 1 of them.

template<class FDistanceToNode, class FDistanceToObject, class FOnNearestNeighbour>
void	KNearestNeighbours (FDistanceToNode fDistanceToNode, FDistanceToObject fDistanceToObject, FOnNearestNeighbour fOnNearestNeighbour, Index K, Scalar radius=std::numeric_limits< Scalar >::max()) const
	Find the K nearest neighbours to some user-defined query.

template<class FObjectsOverlap, class FOnSelfOverlap>
void	SelfOverlaps (FObjectsOverlap fObjectsOverlap, FOnSelfOverlap fOnSelfOverlap) const
	Find all object pairs that overlap.

template<class FObjectsOverlap, class FOnOverlap>
void	Overlaps (SelfType const &rhs, FObjectsOverlap fObjectsOverlap, FOnOverlap fOnOverlap) const
	Find all object pairs that overlap with another hierarchy.

auto	InternalNodeBoundingBoxes () const
	Get the internal node bounding boxes.

auto	Tree () const -> common::BinaryRadixTree< IndexType > const &
	Get the underlying tree hierarchy.

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

Protected Member Functions
template<class TDerivedL, class TDerivedU>
void	ComputeMortonCodes (Eigen::DenseBase< TDerivedL > const &L, Eigen::DenseBase< TDerivedU > const &U)
	Compute Morton codes for the AABBs.

void	SortMortonCodes ()
	Sort the Morton codes.

Detailed Description

template<auto Dims>
class pbat::geometry::AabbRadixTreeHierarchy< Dims >

Axis-aligned radix tree hierarchy of axis-aligned bounding boxes.

This BVH does not store the AABBs themselves, only the tree topology and the AABBs of the tree nodes. The user is responsible for storing the objects and their AABBs. Doing so allows this BVH implementation to support arbitrary object types.

Note: This BVH implementation relies on a binary radix tree, thus tree topology should be rebuilt from scratch whenever updates are required. However, this aabb radix tree construction has average time complexity of \( O(n) \) and worst-case time complexity of \( O(n log n) \).

Template Parameters

Dims	Number of spatial dimensions

Constructor & Destructor Documentation

◆ AabbRadixTreeHierarchy()

template<auto Dims>

template<class TDerivedL, class TDerivedU>

pbat::geometry::AabbRadixTreeHierarchy< Dims >::AabbRadixTreeHierarchy	(	Eigen::DenseBase< TDerivedL > const &	L,
		Eigen::DenseBase< TDerivedU > const &	U )

inline

Construct an AabbRadixTreeHierarchy from an input AABB matrix B.

Template Parameters

TDerived Type of the input matrix

Parameters

L	kDims x \|# objects\| matrix of object AABB lower bounds, such that for an object o, L.col(o).head<kDims>() is the lower bound.
U	kDims x \|# objects\| matrix of object AABB upper bounds, such that for an object o, U.col(o).head<kDims>() is the upper bound.

Member Function Documentation

◆ ComputeMortonCodes()

template<auto Dims>

template<class TDerivedL, class TDerivedU>

void pbat::geometry::AabbRadixTreeHierarchy< Dims >::ComputeMortonCodes	(	Eigen::DenseBase< TDerivedL > const &	L,
		Eigen::DenseBase< TDerivedU > const &	U )

inlineprotected

Compute Morton codes for the AABBs.

Template Parameters

TDerivedB Type of the input matrix

Parameters

L	kDims x \|# objects\| matrix of object AABB lower bounds, such that for an object o, L.col(o).head<kDims>() is the lower bound.
U	kDims x \|# objects\| matrix of object AABB upper bounds, such that for an object o, U.col(o).head<kDims>() is the upper bound.

◆ Construct()

template<auto Dims>

template<class TDerivedL, class TDerivedU>

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

inline

Construct an AabbRadixTreeHierarchy from an input AABB matrix B.

Construction has \( O(n log n) \) average time complexity due to morton code sorting.

Template Parameters

TDerived Type of the input matrix

Parameters

L	kDims x \|# objects\| matrix of object AABB lower bounds, such that for an object o, L.col(o).head<kDims>() is the lower bound.
U	kDims x \|# objects\| matrix of object AABB upper bounds, such that for an object o, U.col(o).head<kDims>() is the upper bound.

◆ InternalNodeBoundingBoxes()

template<auto Dims>

auto pbat::geometry::AabbRadixTreeHierarchy< Dims >::InternalNodeBoundingBoxes ( ) const

inline

Get the internal node bounding boxes.

Returns: 2*kDims x |# internal nodes| matrix of AABBs, such that for an internal node node, IB.col(node).head<kDims>() is the lower bound and IB.col(node).tail<kDims>() is the upper bound.

◆ KNearestNeighbours()

template<auto Dims>

template<class FDistanceToNode, class FDistanceToObject, class FOnNearestNeighbour>

void pbat::geometry::AabbRadixTreeHierarchy< Dims >::KNearestNeighbours	(	FDistanceToNode	fDistanceToNode,
		FDistanceToObject	fDistanceToObject,
		FOnNearestNeighbour	fOnNearestNeighbour,
		Index	K,
		Scalar	radius = std::numeric_limits<Scalar>::max() ) const

inline

Find the K nearest neighbours to some user-defined query.

Template Parameters

FDistanceToNode	Function with signature `template <class TDerivedL, class TDerivedU> Scalar(TDerivedL const& L, TDerivedU const& U)`
FDistanceToObject	Function with signature `Scalar(Index o)`
FOnNearestNeighbour	Function with signature `void(Index o, Scalar d, Index k)`

Parameters

fDistanceToNode	Function to compute the distance to a node
fDistanceToObject	Function to compute the distance to an object
fOnNearestNeighbour	Function to process a nearest neighbour
K	Number of nearest neighbours to find
radius	Maximum distance to search for nearest neighbours

◆ NearestNeighbours()

template<auto Dims>

template<class FDistanceToNode, class FDistanceToObject, class FOnNearestNeighbour>

void pbat::geometry::AabbRadixTreeHierarchy< Dims >::NearestNeighbours	(	FDistanceToNode	fDistanceToNode,
		FDistanceToObject	fDistanceToObject,
		FOnNearestNeighbour	fOnNearestNeighbour,
		Scalar	radius = std::numeric_limits<Scalar>::max(),
		Scalar	eps = Scalar(0) ) const

inline

Find the nearest neighbour to some user-defined query. If there are multiple nearest neighbours, we may return a certain number > 1 of them.

Template Parameters

FDistanceToNode	Function with signature `template <class TDerivedL, class TDerivedU> Scalar(TDerivedL const& L, TDerivedU const& U)`
FDistanceToObject	Function with signature `Scalar(Index o)`
FOnNearestNeighbour	Function with signature `void(Index o, Scalar d, Index k)`

Parameters

fDistanceToNode	Function to compute the distance to a node
fDistanceToObject	Function to compute the distance to an object
fOnNearestNeighbour	Function to process a nearest neighbour
radius	Maximum distance to search for nearest neighbours
eps	Maximum distance error

◆ Overlaps() [1/2]

template<auto Dims>

template<class FNodeOverlaps, class FObjectOverlaps, class FOnOverlap>

void pbat::geometry::AabbRadixTreeHierarchy< Dims >::Overlaps	(	FNodeOverlaps	fNodeOverlaps,
		FObjectOverlaps	fObjectOverlaps,
		FOnOverlap	fOnOverlap ) const

inline

Find all objects that overlap with some user-defined query.

Template Parameters

FNodeOverlaps	Function with signature `template <class TDerivedL, class TDerivedU> bool(TDerivedL const& L, TDerivedU const& U)`
FObjectOverlaps	Function with signature `bool(Index o)`
FOnOverlap	Function with signature `void(Index n, Index o)`

Parameters

fNodeOverlaps	Function to determine if a node overlaps with the query
fObjectOverlaps	Function to determine if an object overlaps with the query
fOnOverlap	Function to process an overlap

◆ Overlaps() [2/2]

template<auto Dims>

template<class FObjectsOverlap, class FOnOverlap>

void pbat::geometry::AabbRadixTreeHierarchy< Dims >::Overlaps	(	SelfType const &	rhs,
		FObjectsOverlap	fObjectsOverlap,
		FOnOverlap	fOnOverlap ) const

inline

Find all object pairs that overlap with another hierarchy.

Template Parameters

FObjectsOverlap	Callable with signature `bool(Index o1, Index o2)`
FOnOverlap	Callable with signature `void(Index o1, Index o2, Index k)`

Parameters

rhs	Other hierarchy to compare against
fObjectsOverlap	Function to determine if 2 objects (o1,o2) overlap, where o1 is an object from this tree and o2 is an object from the rhs tree
fOnOverlap	Function to process an overlap (o1,o2) where o1 is an object from this tree and o2 is an object from the rhs tree

◆ SelfOverlaps()

template<auto Dims>

template<class FObjectsOverlap, class FOnSelfOverlap>

void pbat::geometry::AabbRadixTreeHierarchy< Dims >::SelfOverlaps	(	FObjectsOverlap	fObjectsOverlap,
		FOnSelfOverlap	fOnSelfOverlap ) const

inline

Find all object pairs that overlap.

Template Parameters

FObjectsOverlap	Function with signature `bool(Index o1, Index o2)`
FOnSelfOverlap	Function with signature `void(Index o1, Index o2, Index k)`

Parameters

fObjectsOverlap	Function to determine if 2 objects from this tree overlap
fOnSelfOverlap	Function to process an overlap

◆ Tree()

template<auto Dims>

auto pbat::geometry::AabbRadixTreeHierarchy< Dims >::Tree ( ) const -> common::BinaryRadixTree<IndexType> const&

inline

Get the underlying tree hierarchy.

Returns: Binary radix tree

◆ Update()

template<auto Dims>

template<class TDerivedL, class TDerivedU>

void pbat::geometry::AabbRadixTreeHierarchy< Dims >::Update	(	Eigen::DenseBase< TDerivedL > const &	L,
		Eigen::DenseBase< TDerivedU > const &	U )

inline

Recomputes k-D tree node AABBs given the object AABBs.

A sequential post-order traversal of the k-D tree is performed, i.e. bottom up nodal AABB computation, leading to \( O(n) \) time complexity.

Template Parameters

TDerivedB Type of the input matrix

Parameters

L	kDims x \|# objects\| matrix of object AABB lower bounds, such that for an object o, L.col(o).head<kDims>() is the lower bound.
U	kDims x \|# objects\| matrix of object AABB upper bounds, such that for an object o, U.col(o).head<kDims>() is the upper bound.

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

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

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ AabbRadixTreeHierarchy()

Member Function Documentation

◆ ComputeMortonCodes()

◆ Construct()

◆ InternalNodeBoundingBoxes()

◆ KNearestNeighbours()

◆ NearestNeighbours()

◆ Overlaps() [1/2]

◆ Overlaps() [2/2]

◆ SelfOverlaps()

◆ Tree()

◆ Update()