Axis-aligned k-D tree hierarchy of axis-aligned bounding boxes. More...

#include <AabbKdTreeHierarchy.h>

Public Types
using	SelfType = AabbKdTreeHierarchy<kDims>
	Type of this template instantiation.

Public Member Functions
template<class TDerivedL, class TDerivedU>
	AabbKdTreeHierarchy (Eigen::DenseBase< TDerivedL > const &L, Eigen::DenseBase< TDerivedU > const &U, Index maxPointsInLeaf=8)
	Construct an Aabb Hierarchy from an input AABB matrices L, U.

template<class TDerivedL, class TDerivedU>
void	Construct (Eigen::DenseBase< TDerivedL > const &L, Eigen::DenseBase< TDerivedU > const &U, Index maxPointsInLeaf=8)
	Construct an Aabb Hierarchy 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 -> Matrix< 2 *kDims, Eigen::Dynamic > const &
	Get the internal node bounding boxes.

auto	Tree () const -> KdTree< kDims > const &
	Get the underlying k-D tree.

auto	Lower (Index node) const
	Obtain the lower bound of the AABB of a node.

auto	Upper (Index node) const
	Obtain the upper bound of the AABB of a node.

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

Detailed Description

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

Axis-aligned k-D 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. When objects move, the user should update the AABBs and call AabbKdTreeHierarchy::Update() to recompute the tree node AABBs.

Note: This BVH implementation relies on a static k-D tree, thus tree topology cannot be modified after construction. In other words, dynamic insertion/deletion of objects is only supported by reconstructing the tree from scratch.

Template Parameters

Dims	Number of spatial dimensions

Constructor & Destructor Documentation

◆ AabbKdTreeHierarchy()

template<auto Dims>

template<class TDerivedL, class TDerivedU>

pbat::geometry::AabbKdTreeHierarchy< Dims >::AabbKdTreeHierarchy	(	Eigen::DenseBase< TDerivedL > const &	L,
		Eigen::DenseBase< TDerivedU > const &	U,
		Index	maxPointsInLeaf = 8 )

inline

Construct an Aabb Hierarchy from an input AABB matrices L, U.

Template Parameters

TDerivedL	Type of the lower bound matrix
TDerivedU	Type of the upper bound matrix

Parameters

L	kDims x \|# objects\| matrix of object AABB lower bounds, such that for an object o, L.col(o) is the lower bound.
U	kDims x \|# objects\| matrix of object AABB upper bounds, such that for an object o, U.col(o) is the upper bound.
maxPointsInLeaf	Maximum number of points in a leaf node

Member Function Documentation

◆ Construct()

template<auto Dims>

template<class TDerivedL, class TDerivedU>

void pbat::geometry::AabbKdTreeHierarchy< Dims >::Construct	(	Eigen::DenseBase< TDerivedL > const &	L,
		Eigen::DenseBase< TDerivedU > const &	U,
		Index	maxPointsInLeaf = 8 )

inline

Construct an Aabb Hierarchy from an input AABB matrix B.

Template Parameters

TDerivedL	Type of the lower bound matrix
TDerivedU	Type of the upper bound matrix

Parameters

L	kDims x \|# objects\| matrix of object AABB lower bounds, such that for an object o, L.col(o) is the lower bound.
U	kDims x \|# objects\| matrix of object AABB upper bounds, such that for an object o, U.col(o) is the upper bound.
maxPointsInLeaf	Maximum number of points in a leaf node

◆ InternalNodeBoundingBoxes()

template<auto Dims>

auto pbat::geometry::AabbKdTreeHierarchy< Dims >::InternalNodeBoundingBoxes ( ) const -> Matrix<2 * kDims, Eigen::Dynamic> 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::AabbKdTreeHierarchy< 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

◆ Lower()

template<auto Dims>

auto pbat::geometry::AabbKdTreeHierarchy< Dims >::Lower ( Index node ) const

inline

Obtain the lower bound of the AABB of a node.

Parameters

node	Node index

Returns: Lower bound of the AABB of the node

Precondition: 0 <= node < InternalNodeBoundingBoxes().cols()

◆ NearestNeighbours()

template<auto Dims>

template<class FDistanceToNode, class FDistanceToObject, class FOnNearestNeighbour>

void pbat::geometry::AabbKdTreeHierarchy< 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::AabbKdTreeHierarchy< 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::AabbKdTreeHierarchy< 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::AabbKdTreeHierarchy< 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::AabbKdTreeHierarchy< Dims >::Tree ( ) const -> KdTree<kDims> const&

inline

Get the underlying k-D tree.

Returns: The k-D tree hierarchy

◆ Update()

template<auto Dims>

template<class TDerivedL, class TDerivedU>

void pbat::geometry::AabbKdTreeHierarchy< 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. The traversal should be have some respectable cache-efficiency at the tree-level, since nodes and their 2 children are stored contiguously in memory. However, objects stored in leaves are generally spread out in memory.

Template Parameters

TDerivedL	Type of the lower bound matrix
TDerivedU	Type of the upper bound matrix

Parameters

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

◆ Upper()

template<auto Dims>

auto pbat::geometry::AabbKdTreeHierarchy< Dims >::Upper ( Index node ) const

inline

Obtain the upper bound of the AABB of a node.

Parameters

node	Node index

Returns: Upper bound of the AABB of the node

Precondition: 0 <= node < InternalNodeBoundingBoxes().cols()

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

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

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ AabbKdTreeHierarchy()

Member Function Documentation

◆ Construct()

◆ InternalNodeBoundingBoxes()

◆ KNearestNeighbours()

◆ Lower()

◆ NearestNeighbours()

◆ Overlaps() [1/2]

◆ Overlaps() [2/2]

◆ SelfOverlaps()

◆ Tree()

◆ Update()

◆ Upper()