The dynamic AABB tree. More...

#include <AABB.h>

Public Member Functions
	Tree (unsigned int dimension_=3, double skinThickness_=0.05, unsigned int nParticles=16)
	Constructor (non-periodic). More...

	Tree (unsigned int, double, const std::vector< bool > &, const std::vector< double > &, unsigned int nParticles=16)
	Constructor (custom periodicity). More...

void	setPeriodicity (const std::vector< bool > &)
	Set the periodicity of the simulation box. More...

void	setBoxSize (const std::vector< double > &)
	Set the size of the simulation box. More...

void	insertParticle (unsigned int, std::vector< double > &, double)
	Insert a particle into the tree (point particle). More...

void	insertParticle (unsigned int, std::vector< double > &, std::vector< double > &)
	Insert a particle into the tree (arbitrary shape with bounding box). More...

void	removeParticle (unsigned int)
	Remove a particle from the tree. More...

bool	updateParticle (unsigned int, std::vector< double > &, double)
	Update the tree if a particle moves outside its fattened AABB. More...

bool	updateParticle (unsigned int, std::vector< double > &, std::vector< double > &)
	Update the tree if a particle moves outside its fattened AABB. More...

std::vector< unsigned int >	query (unsigned int)
	Query the tree to find candidate interactions for a particle. More...

std::vector< unsigned int >	query (unsigned int, const AABB &)
	Query the tree to find candidate interactions for an AABB. More...

std::vector< unsigned int >	query (const AABB &)
	Query the tree to find candidate interactions for an AABB. More...

const AABB &	getAABB (unsigned int)
	Get a particle AABB. More...

unsigned int	getHeight () const
	Get the height of the tree. More...

unsigned int	getNodeCount () const
	Get the number of nodes in the tree. More...

unsigned int	computeMaximumBalance () const
	Compute the maximum balancance of the tree. More...

double	computeSurfaceAreaRatio () const
	Compute the surface area ratio of the tree. More...

void	validate () const
	Validate the tree.

void	rebuild ()
	Rebuild an optimal tree.

Detailed Description

The dynamic AABB tree.

The dynamic AABB tree is a hierarchical data structure that can be used to efficiently query overlaps between objects of arbitrary shape and size that lie inside of a simulation box. Support is provided for periodic and non-periodic boxes, as well as boxes with partial periodicity, e.g. periodic along specific axes.

Constructor & Destructor Documentation

§ Tree() [1/2]

aabb::Tree::Tree	(	unsigned int	dimension_ = `3`,
		double	skinThickness_ = `0.05`,
		unsigned int	nParticles = `16`
	)

Constructor (non-periodic).

Parameters

dimension_	The dimensionality of the system.
skinThickness_	The skin thickness for fattened AABBs, as a fraction of the AABB base length.
nParticles	The number of particles (for fixed particle number systems).

§ Tree() [2/2]

aabb::Tree::Tree	(	unsigned int	dimension_,
		double	skinThickness_,
		const std::vector< bool > &	periodicity_,
		const std::vector< double > &	boxSize_,
		unsigned int	nParticles = `16`
	)

Constructor (custom periodicity).

Parameters

dimension_	The dimensionality of the system.
skinThickness_	The skin thickness for fattened AABBs, as a fraction of the AABB base length.
periodicity_	Whether the system is periodic in each dimension.
boxSize_	The size of the simulation box in each dimension.
nParticles	The number of particles (for fixed particle number systems).

Member Function Documentation

§ computeMaximumBalance()

unsigned int aabb::Tree::computeMaximumBalance ( ) const

Compute the maximum balancance of the tree.

Returns: The maximum difference between the height of two children of a node.

§ computeSurfaceAreaRatio()

double aabb::Tree::computeSurfaceAreaRatio ( ) const

Compute the surface area ratio of the tree.

Returns: The ratio of the sum of the node surface area to the surface area of the root node.

§ getAABB()

const AABB & aabb::Tree::getAABB ( unsigned int particle )

Get a particle AABB.

Parameters

particle The particle index.

§ getHeight()

unsigned int aabb::Tree::getHeight ( ) const

Get the height of the tree.

Returns: The height of the binary tree.

§ getNodeCount()

unsigned int aabb::Tree::getNodeCount ( ) const

Get the number of nodes in the tree.

Returns: The number of nodes in the tree.

§ insertParticle() [1/2]

void aabb::Tree::insertParticle	(	unsigned int	particle,
		std::vector< double > &	position,
		double	radius
	)

Insert a particle into the tree (point particle).

Parameters

index	The index of the particle.
position	The position vector of the particle.
radius	The radius of the particle.

§ insertParticle() [2/2]

void aabb::Tree::insertParticle	(	unsigned int	particle,
		std::vector< double > &	lowerBound,
		std::vector< double > &	upperBound
	)

Insert a particle into the tree (arbitrary shape with bounding box).

Parameters

index	The index of the particle.
lowerBound	The lower bound in each dimension.
upperBound	The upper bound in each dimension.

§ query() [1/3]

std::vector< unsigned int > aabb::Tree::query ( unsigned int particle )

Query the tree to find candidate interactions for a particle.

Parameters

particle The particle index.

Returns: particles A vector of particle indices.

§ query() [2/3]

std::vector< unsigned int > aabb::Tree::query	(	unsigned int	particle,
		const AABB &	aabb
	)

Query the tree to find candidate interactions for an AABB.

Parameters

particle	The particle index.
aabb	The AABB.

Returns: particles A vector of particle indices.

§ query() [3/3]

std::vector< unsigned int > aabb::Tree::query ( const AABB & aabb )

Query the tree to find candidate interactions for an AABB.

Parameters

aabb The AABB.

Returns: particles A vector of particle indices.

§ removeParticle()

void aabb::Tree::removeParticle ( unsigned int particle )

Remove a particle from the tree.

Parameters

particle The particle index (particleMap will be used to map the node).

§ setBoxSize()

void aabb::Tree::setBoxSize ( const std::vector< double > & boxSize_ )

Set the size of the simulation box.

Parameters

boxSize_ The size of the simulation box in each dimension.

§ setPeriodicity()

void aabb::Tree::setPeriodicity ( const std::vector< bool > & periodicity_ )

Set the periodicity of the simulation box.

Parameters

periodicity_ Whether the system is periodic in each dimension.

§ updateParticle() [1/2]

bool aabb::Tree::updateParticle	(	unsigned int	particle,
		std::vector< double > &	position,
		double	radius
	)

Update the tree if a particle moves outside its fattened AABB.

Parameters

particle	The particle index (particleMap will be used to map the node).
position	The position vector of the particle.
radius	The radius of the particle.

Returns: Whether the particle was reinserted.

§ updateParticle() [2/2]

bool aabb::Tree::updateParticle	(	unsigned int	particle,
		std::vector< double > &	lowerBound,
		std::vector< double > &	upperBound
	)

Update the tree if a particle moves outside its fattened AABB.

Parameters

particle	The particle index (particleMap will be used to map the node).
lowerBound	The lower bound in each dimension.
upperBound	The upper bound in each dimension.

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

src/AABB.h
src/AABB.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

§ Tree() [1/2]

§ Tree() [2/2]

Member Function Documentation

§ computeMaximumBalance()

§ computeSurfaceAreaRatio()

§ getAABB()

§ getHeight()

§ getNodeCount()

§ insertParticle() [1/2]

§ insertParticle() [2/2]

§ query() [1/3]

§ query() [2/3]

§ query() [3/3]

§ removeParticle()

§ setBoxSize()

§ setPeriodicity()

§ updateParticle() [1/2]

§ updateParticle() [2/2]