#include <DynamicAABBTree.hpp>

Public Member Functions
	DynamicAABBTree ()
	instanciates a new empty DynamicAABBTree object. More...

	~DynamicAABBTree ()
	Default destructor. More...

void	insert_node (AABB anAABB)
	Inserts a new AABB in the AABB tree. More...

void	set_fatness (double fatness)
	Allows to define the expansion factor for fat AABBs. More...

bool	update_primitive (unsigned int primitiveIndex, AABB tightAABB)
	Updates the primitive in case it is out of its bounding box. More...

void	remove_primitive (unsigned int primitiveIndex)
	Removes an AABB from the AABB tree. More...

void	clear ()
	Clears the AABB tree. More...

const unsigned int	node_number () const

const AABBNode	node_at_index (unsigned int nodeIndex) const

const unsigned int	aabb_number () const

const AABB	aabb_at_index (unsigned int aabbIndex) const

const bool	is_node_leaf (unsigned int nodeIndex) const

const int	NodeBalance (unsigned int nodeIndex) const

const bool	Primitiveexists (unsigned int primitiveIndex) const

void	PrimitivesList (std::vector< unsigned int > &primitivesList) const
	Populates the `primitivesList` vector with indices of all primitives contained in the tree. More...

void	collidersPairs (std::vector< std::pair< unsigned int, unsigned int > > &collidersPairs) const
	Queries the AABB tree to find all AABBs overlapping themselves. More...

void	collidersList (unsigned int primitiveIndex, std::vector< unsigned int > &collidersList) const
	Queries the AABB tree to find all AABBs overlapping with the AABB that stores a given primitive. More...

void	printAABBNodes ()

void	saveAABBs ()

void	saveAABBs (std::vector< unsigned int > primitivesList)

Static Public Member Functions
static AABB	new_lonely_aabb (double minPoint[3], double maxPoint[3], double fatness, unsigned int primtiveIndex=-1)
	Creates a new 'lonely' AABB with given extreme points. More...

static AABB	merged_lonely_aabb (AABB aabb1, AABB aabb2, unsigned int primtiveIndex=-1)
	Creates a new AABB which is a combination of two AABB. More...

Private Member Functions
unsigned int	new_aabb_node ()
	Creates a new AABBNode. More...

unsigned int	new_aabb_node (AABB anAABB)
	Creates a new AABBNode associated to a new AABB. More...

unsigned int	new_aabb (double minPoint[3], double maxPoint[3], unsigned int primitiveIndex=-1)
	Creates a new AABB with given extreme points and, optionally, the primitive index. More...

unsigned int	new_aabb (AABB anAABB)
	Creates a new AABB using the provided AABB. More...

void	remove_node (unsigned int leafNode)
	Removes a leaf node from the AABB tree. More...

void	delete_node (unsigned int aNodeIndex)
	Deletes a node and updates the first available space in the AABB nodes list. More...

void	delete_aabb (unsigned int anAABBIndex)
	Deletes an AABB and updates the first available space in the AABBs list. More...

unsigned int	balance_node (unsigned int rootNodeIndex)
	Balances a node according to its height. More...

unsigned int	rotate_left (unsigned int rootNodeIndex)
	Performs a left-side rotation of a sub tree rooted at `rootNodeIndex`. More...

unsigned int	rotate_right (unsigned int rootNodeIndex)
	Performs a right-side rotation of a sub tree rooted at `rootNodeIndex`. More...

void	update_node_aabb (unsigned int aNode)
	Updates the dimensions of a node aabb, according to its childen. More...

void	update_node_height (unsigned int aNode)
	Updates the height of a node, according to its childen. More...

const bool	aabb_do_overlap (unsigned int aabb1, unsigned int aabb2) const
	Checks if two AABBs overlap themselves. More...

const bool	is_aabb_contain_aabb (unsigned int anAABBIndex, AABB anAABB) const
	Checks if an AABB is contained inside another one. More...

Private Attributes
double	_fatness
	The factor by which the AABBs dimensions are expanded. More...

unsigned int	_aabbsCount
	The current number of AABBs in the tree. More...

unsigned int	_node_count
	The current number of AABB nodes in the tree. More...

unsigned int	_rootNodeIndex
	The root node of the AABB tree, necessary when the tree is dynamic. More...

unsigned int	_firstFreeNodeIndex
	The index of the first free node in the `_nodes` list. More...

unsigned int	_firstFreeAABBIndex
	The index of the first free aabb in the `_aabbs` list. More...

std::vector< unsigned int >	_primitivesToNode
	stores the relationship from primitives to nodes indices. More...

std::vector< AABB >	_aabbs
	The AABBs container. More...

std::vector< AABBNode >	_nodes
	The leaves AABB nodes container. More...

Static Private Attributes
static const unsigned int	NotInList = (unsigned int)(-1)
	A flag to determine if an index is in a list. More...

Constructor & Destructor Documentation

◆ DynamicAABBTree()

DynamicAABBTree::DynamicAABBTree ( )

instanciates a new empty DynamicAABBTree object.

◆ ~DynamicAABBTree()

DynamicAABBTree::~DynamicAABBTree ( )

Default destructor.

Member Function Documentation

◆ aabb_at_index()

const AABB DynamicAABBTree::aabb_at_index ( unsigned int aabbIndex ) const

inline

Returns: The AABB stored at index nodeIndex.

◆ aabb_do_overlap()

const bool DynamicAABBTree::aabb_do_overlap	(	unsigned int	aabb1,
		unsigned int	aabb2
	)		const

private

Checks if two AABBs overlap themselves.

Returns: true or false whether the AABBs defined by their indices aabb1 and aabb2 overlap themselves.

◆ aabb_number()

const unsigned int DynamicAABBTree::aabb_number ( ) const

inline

Returns: The number of AABBs in the data structure.

◆ balance_node()

unsigned int DynamicAABBTree::balance_node ( unsigned int rootNodeIndex )

private

Balances a node according to its height.

This method performs the required rotations in order to balance the node with index rootNodeIndex. According to the required rotations, this method will call rotate_left() and/or rotate_right() methods.

◆ clear()

void DynamicAABBTree::clear ( )

Clears the AABB tree.

Clears the contents of vectors containing informations related to the tree, i.e. _aabbsCount, _aabbs, _nodeCount, _nodes and _primitivesToNode.

◆ collidersList()

void DynamicAABBTree::collidersList	(	unsigned int	primitiveIndex,
		std::vector< unsigned int > &	collidersList
	)		const

Queries the AABB tree to find all AABBs overlapping with the AABB that stores a given primitive.

Queries the AABB tree to find all AABBs overlapping with the AABB that stores the primitive with index primitiveIndex. The colliders possibly in contact with the primitive AABB are stored as a list. This method is mainly usefull for contact broad_phase processing.

◆ collidersPairs()

void DynamicAABBTree::collidersPairs ( std::vector< std::pair< unsigned int, unsigned int > > & collidersPairs ) const

Queries the AABB tree to find all AABBs overlapping themselves.

Queries the AABB tree to find all AABBs in contact, i.e. which overlap themselves, and thus the primitives stored in AABBs possibly in contact. The colliders possibly in contact are stored as pairs, and all colliders pairs found in the tree are stored in vector collidersPairs. This method is mainly usefull for contact broad_phase processing.

◆ delete_aabb()

void DynamicAABBTree::delete_aabb ( unsigned int anAABBIndex )

private

Deletes an AABB and updates the first available space in the AABBs list.

This method deletes the AABB with index anAABBIndex and updates the first available space in _aabbs.

◆ delete_node()

void DynamicAABBTree::delete_node ( unsigned int aNodeIndex )

private

Deletes a node and updates the first available space in the AABB nodes list.

This method deletes the AABB node with index aNodeIndex and updates the first available space in _nodes.

◆ insert_node()

void DynamicAABBTree::insert_node ( AABB anAABB )

Inserts a new AABB in the AABB tree.

This method allows to insert a new AABB in the AABB tree.

◆ is_aabb_contain_aabb()

const bool DynamicAABBTree::is_aabb_contain_aabb	(	unsigned int	anAABBIndex,
		AABB	anAABB
	)		const

private

Checks if an AABB is contained inside another one.

Returns: true or false whether the AABB defined by its index anAABBIndex contains the AABB defined by anAABB.

◆ is_node_leaf()

const bool DynamicAABBTree::is_node_leaf ( unsigned int nodeIndex ) const

inline

Returns: true or false whether the node with index nodeIndex is a leaf node.

◆ merged_lonely_aabb()

AABB DynamicAABBTree::merged_lonely_aabb	(	AABB	aabb1,
		AABB	aabb2,
		unsigned int	primtiveIndex = `-1`
	)

static

Creates a new AABB which is a combination of two AABB.

Creates a new AABB which is a combination of two aabbs aabb1 and aabb2 and compute its parameters, such as its mid point, length in the three directions and volume. Optionally, a reference of the primitive it contains can be given with the primtiveIndex argument, which defaults to -1.

It is said 'lonely' since it is not added to the list of AABBs _aabbs.

Returns: The created AABB instance.

◆ new_aabb() [1/2]

unsigned int DynamicAABBTree::new_aabb ( AABB anAABB )

private

Creates a new AABB using the provided AABB.

Creates a new AABB based on the extreme points of anAABB, and stores it into the _aabbs vector.

Returns: The index of the newly created AABB.

◆ new_aabb() [2/2]

unsigned int DynamicAABBTree::new_aabb	(	double	minPoint[3],
		double	maxPoint[3],
		unsigned int	primitiveIndex = `-1`
	)

private

Creates a new AABB with given extreme points and, optionally, the primitive index.

Creates a new AABB based on the extreme points minPoint and maxPoint and, optionally, the primitive index, primitiveIndex. This method invokes the static method new_lonely_aabb to create the AABB and compute its parameters. It is then added to the list of AABBs of the tree _aabbs.

Returns: The index of the newly created AABB.

◆ new_aabb_node() [1/2]

unsigned int DynamicAABBTree::new_aabb_node ( )

private

Creates a new AABBNode.

Creates a new empty AABBNode and add it to the list of AABB nodes, _nodes.

Returns: The index of the newly created node.

◆ new_aabb_node() [2/2]

unsigned int DynamicAABBTree::new_aabb_node ( AABB anAABB )

private

Creates a new AABBNode associated to a new AABB.

Creates a new AABBNode and set its AABB with a copy of anAABB, through a call to new_aabb() method.

Returns: The index of the newly created node.

◆ new_lonely_aabb()

AABB DynamicAABBTree::new_lonely_aabb	(	double	minPoint[3],
		double	maxPoint[3],
		double	fatness,
		unsigned int	primtiveIndex = `-1`
	)

static

Creates a new 'lonely' AABB with given extreme points.

Creates a new AABB based on the extreme points minPoint and maxPoint, and compute its parameters, such as its mid point, length in the three directions and volume. The dimentions of the AABB and related parameters are affected by parameter fatness as follows

2*factor*length[ii]

where ii in [0,2] is the dimension axis.

Optionally, a reference of the primitive it contains can be given with the primtiveIndex argument, which defaults to -1.

It is said 'lonely' since it is not added to the list of AABBs _aabbs.

Returns: The created AABB instance.

◆ node_at_index()

const AABBNode DynamicAABBTree::node_at_index ( unsigned int nodeIndex ) const

inline

Returns: The AABB node stored at index nodeIndex.

◆ node_number()

const unsigned int DynamicAABBTree::node_number ( ) const

inline

Returns: The number of nodes in the data structure.

◆ NodeBalance()

const int DynamicAABBTree::NodeBalance ( unsigned int nodeIndex ) const

inline

Returns: The balance state of the node with index nodeIndex.

◆ Primitiveexists()

const bool DynamicAABBTree::Primitiveexists ( unsigned int primitiveIndex ) const

Returns: true or false whether the primitive with index primitiveIndex exists in the tree.

◆ PrimitivesList()

void DynamicAABBTree::PrimitivesList ( std::vector< unsigned int > & primitivesList ) const

Populates the primitivesList vector with indices of all primitives contained in the tree.

◆ printAABBNodes()

void DynamicAABBTree::printAABBNodes ( )

◆ remove_node()

void DynamicAABBTree::remove_node ( unsigned int leafNode )

private

Removes a leaf node from the AABB tree.

This method allows to remove the leaf node with index leafNode from the AABB tree.

◆ remove_primitive()

void DynamicAABBTree::remove_primitive ( unsigned int primitiveIndex )

Removes an AABB from the AABB tree.

This method allows to remove the AABB with index anAABB from the AABB tree.

◆ rotate_left()

unsigned int DynamicAABBTree::rotate_left ( unsigned int rootNodeIndex )

private

Performs a left-side rotation of a sub tree rooted at rootNodeIndex.

This method performs a left-side rotation of a sub tree rooted at rootNodeIndex in order to balance it.

Returns: The index of the new root.

◆ rotate_right()

unsigned int DynamicAABBTree::rotate_right ( unsigned int rootNodeIndex )

private

Performs a right-side rotation of a sub tree rooted at rootNodeIndex.

This method performs a right-side rotation of a sub tree rooted at rootNodeIndex in order to balance it.

Returns: The index of the new root.

◆ saveAABBs() [1/2]

void DynamicAABBTree::saveAABBs ( )

◆ saveAABBs() [2/2]

void DynamicAABBTree::saveAABBs ( std::vector< unsigned int > primitivesList )

◆ set_fatness()

void DynamicAABBTree::set_fatness ( double fatness )

inline

Allows to define the expansion factor for fat AABBs.

All dimensions of the AABBs are increased by

2*factor*length[ii]

where ii in [0,2] is the dimension axis.

◆ update_node_aabb()

void DynamicAABBTree::update_node_aabb ( unsigned int aNode )

private

Updates the dimensions of a node aabb, according to its childen.

This method allows to update the dimensions and all related parameters, such as its volume and mid point, according to the node children aabbs.

◆ update_node_height()

void DynamicAABBTree::update_node_height ( unsigned int aNode )

private

Updates the height of a node, according to its childen.

This method allows to update the height, which corresponds to 1 plus the maximum height of its children.

◆ update_primitive()

bool DynamicAABBTree::update_primitive	(	unsigned int	primitiveIndex,
		AABB	tightAABB
	)

Updates the primitive in case it is out of its bounding box.

This method checks if the primitive with index primitiveIndex moved out of its internal AABB, comparing it to its current, tight, AABB given by tightAABB. If it overlaps it is out of its internal AABB, the node that holds primitive is removed and re-inserted into the tree. This procedure allows to keep the AABB tree balanced while the primitives move during a dynamic simulation.

Member Data Documentation

◆ _aabbs

std::vector<AABB> DynamicAABBTree::_aabbs

private

The AABBs container.

◆ _aabbsCount

unsigned int DynamicAABBTree::_aabbsCount

private

The current number of AABBs in the tree.

◆ _fatness

double DynamicAABBTree::_fatness

private

The factor by which the AABBs dimensions are expanded.

◆ _firstFreeAABBIndex

unsigned int DynamicAABBTree::_firstFreeAABBIndex

private

The index of the first free aabb in the _aabbs list.

◆ _firstFreeNodeIndex

unsigned int DynamicAABBTree::_firstFreeNodeIndex

private

The index of the first free node in the _nodes list.

◆ _node_count

unsigned int DynamicAABBTree::_node_count

private

The current number of AABB nodes in the tree.

◆ _nodes

std::vector<AABBNode> DynamicAABBTree::_nodes

private

The leaves AABB nodes container.

◆ _primitivesToNode

std::vector<unsigned int> DynamicAABBTree::_primitivesToNode

private

stores the relationship from primitives to nodes indices.

◆ _rootNodeIndex

unsigned int DynamicAABBTree::_rootNodeIndex

private

The root node of the AABB tree, necessary when the tree is dynamic.

◆ NotInList

const unsigned int DynamicAABBTree::NotInList = (unsigned int)(-1)

staticprivate

A flag to determine if an index is in a list.

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

/home/granoo/granoo/Lib/GranOO3/Algo/DynamicAABBTree.hpp
/home/granoo/granoo/Lib/GranOO3/Algo/DynamicAABBTree.cpp

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Constructor & Destructor Documentation

◆ DynamicAABBTree()

◆ ~DynamicAABBTree()

Member Function Documentation

◆ aabb_at_index()

◆ aabb_do_overlap()

◆ aabb_number()

◆ balance_node()

◆ clear()

◆ collidersList()

◆ collidersPairs()

◆ delete_aabb()

◆ delete_node()

◆ insert_node()

◆ is_aabb_contain_aabb()

◆ is_node_leaf()

◆ merged_lonely_aabb()

◆ new_aabb() [1/2]

◆ new_aabb() [2/2]

◆ new_aabb_node() [1/2]

◆ new_aabb_node() [2/2]

◆ new_lonely_aabb()

◆ node_at_index()

◆ node_number()

◆ NodeBalance()

◆ Primitiveexists()

◆ PrimitivesList()

◆ printAABBNodes()

◆ remove_node()

◆ remove_primitive()

◆ rotate_left()

◆ rotate_right()

◆ saveAABBs() [1/2]

◆ saveAABBs() [2/2]

◆ set_fatness()

◆ update_node_aabb()

◆ update_node_height()

◆ update_primitive()

Member Data Documentation

◆ _aabbs

◆ _aabbsCount

◆ _fatness

◆ _firstFreeAABBIndex

◆ _firstFreeNodeIndex

◆ _node_count

◆ _nodes

◆ _primitivesToNode

◆ _rootNodeIndex

◆ NotInList