coal::detail::HierarchyTree< BV > Class Template Reference

Class for hierarchy tree structure. More...

#include <coal/broadphase/detail/hierarchy_tree.h>

Public Types
typedef NodeBase< BV >	Node

Public Member Functions
	HierarchyTree (int bu_threshold_=16, int topdown_level_=0)
	Create hierarchy tree with suitable setting. bu_threshold decides the height of tree node to start bottom-up construction / optimization; topdown_level decides different methods to construct tree in topdown manner. lower level method constructs tree with better quality but is slower.
	~HierarchyTree ()
void	init (std::vector< Node * > &leaves, int level=0)
	Initialize the tree by a set of leaves using algorithm with a given level.
Node *	insert (const BV &bv, void *data)
	Insest a node.
void	remove (Node *leaf)
	Remove a leaf node.
void	clear ()
	Clear the tree.
bool	empty () const
	Whether the tree is empty.
void	update (Node *leaf, int lookahead_level=-1)
	Updates a leaf node. A use case is when the bounding volume of an object changes. Ensure every parent node has its bounding volume expand or shrink to fit the bounding volumes of its children.
bool	update (Node *leaf, const BV &bv)
	update the tree when the bounding volume of a given leaf has changed
bool	update (Node *leaf, const BV &bv, const Vec3s &vel, CoalScalar margin)
	update one leaf's bounding volume, with prediction
bool	update (Node *leaf, const BV &bv, const Vec3s &vel)
	update one leaf's bounding volume, with prediction
size_t	getMaxHeight () const
	get the max height of the tree
size_t	getMaxDepth () const
	get the max depth of the tree
void	balanceBottomup ()
	balance the tree from bottom
void	balanceTopdown ()
	balance the tree from top
void	balanceIncremental (int iterations)
	balance the tree in an incremental way
void	refit ()
	refit the tree, i.e., when the leaf nodes' bounding volumes change, update the entire tree in a bottom-up manner
void	extractLeaves (const Node *root, std::vector< Node * > &leaves) const
	extract all the leaves of the tree
size_t	size () const
	number of leaves in the tree
Node *	getRoot () const
	get the root of the tree
Node *&	getRoot ()
void	print (Node *root, int depth)
	print the tree in a recursive way

Public Attributes
int	topdown_level
	decide which topdown algorithm to use
int	bu_threshold
	decide the depth to use expensive bottom-up algorithm

Protected Attributes
Node *	root_node
size_t	n_leaves
unsigned int	opath
Node *	free_node
int	max_lookahead_level

Detailed Description

template<typename BV>
class coal::detail::HierarchyTree< BV >

Class for hierarchy tree structure.

Member Typedef Documentation

Node

template<typename BV>

typedef NodeBase<BV> coal::detail::HierarchyTree< BV >::Node

Constructor & Destructor Documentation

HierarchyTree()

template<typename BV>

coal::detail::HierarchyTree< BV >::HierarchyTree	(	int	bu_threshold_ = 16,
		int	topdown_level_ = 0 )

Create hierarchy tree with suitable setting. bu_threshold decides the height of tree node to start bottom-up construction / optimization; topdown_level decides different methods to construct tree in topdown manner. lower level method constructs tree with better quality but is slower.

~HierarchyTree()

template<typename BV>

coal::detail::HierarchyTree< BV >::~HierarchyTree

(

)

Member Function Documentation

balanceBottomup()

template<typename BV>

void coal::detail::HierarchyTree< BV >::balanceBottomup

(

)

balance the tree from bottom

balanceIncremental()

template<typename BV>

void coal::detail::HierarchyTree< BV >::balanceIncremental

(

int

iterations

)

balance the tree in an incremental way

balanceTopdown()

template<typename BV>

void coal::detail::HierarchyTree< BV >::balanceTopdown

(

)

balance the tree from top

clear()

template<typename BV>

void coal::detail::HierarchyTree< BV >::clear

(

)

Clear the tree.

empty()

template<typename BV>

bool coal::detail::HierarchyTree< BV >::empty

(

)

const

Whether the tree is empty.

extractLeaves()

template<typename BV>

void coal::detail::HierarchyTree< BV >::extractLeaves	(	const Node *	root,
		std::vector< Node * > &	leaves ) const

extract all the leaves of the tree

getMaxDepth()

template<typename BV>

size_t coal::detail::HierarchyTree< BV >::getMaxDepth

(

)

const

get the max depth of the tree

getMaxHeight()

template<typename BV>

size_t coal::detail::HierarchyTree< BV >::getMaxHeight

(

)

const

get the max height of the tree

getRoot() [1/2]

template<typename BV>

HierarchyTree< BV >::Node *& coal::detail::HierarchyTree< BV >::getRoot

(

)

getRoot() [2/2]

template<typename BV>

HierarchyTree< BV >::Node * coal::detail::HierarchyTree< BV >::getRoot

(

)

const

get the root of the tree

init()

template<typename BV>

void coal::detail::HierarchyTree< BV >::init	(	std::vector< Node * > &	leaves,
		int	level = 0 )

Initialize the tree by a set of leaves using algorithm with a given level.

insert()

template<typename BV>

HierarchyTree< BV >::Node * coal::detail::HierarchyTree< BV >::insert	(	const BV &	bv,
		void *	data )

Insest a node.

print()

template<typename BV>

void coal::detail::HierarchyTree< BV >::print	(	Node *	root,
		int	depth )

print the tree in a recursive way

refit()

template<typename BV>

void coal::detail::HierarchyTree< BV >::refit

(

)

refit the tree, i.e., when the leaf nodes' bounding volumes change, update the entire tree in a bottom-up manner

remove()

template<typename BV>

void coal::detail::HierarchyTree< BV >::remove

(

Node *

leaf

)

Remove a leaf node.

size()

template<typename BV>

size_t coal::detail::HierarchyTree< BV >::size

(

)

const

number of leaves in the tree

update() [1/4]

template<typename BV>

bool coal::detail::HierarchyTree< BV >::update	(	Node *	leaf,
		const BV &	bv )

update the tree when the bounding volume of a given leaf has changed

update() [2/4]

template<typename BV>

bool coal::detail::HierarchyTree< BV >::update	(	Node *	leaf,
		const BV &	bv,
		const Vec3s &	vel )

update one leaf's bounding volume, with prediction

update() [3/4]

template<typename BV>

bool coal::detail::HierarchyTree< BV >::update	(	Node *	leaf,
		const BV &	bv,
		const Vec3s &	vel,
		CoalScalar	margin )

update one leaf's bounding volume, with prediction

update() [4/4]

template<typename BV>

void coal::detail::HierarchyTree< BV >::update	(	Node *	leaf,
		int	lookahead_level = -1 )

Updates a leaf node. A use case is when the bounding volume of an object changes. Ensure every parent node has its bounding volume expand or shrink to fit the bounding volumes of its children.

Note

Strangely the structure of the tree may change even if the bounding volume of the leaf node does not change. It is just another valid tree of the same set of objects. This is because update() works by first removing leaf and then inserting leaf back. The structural change could be as simple as switching the order of two leaves if the sibling of the leaf is also a leaf. Or it could be more complicated if the sibling is an internal node.

Member Data Documentation

bu_threshold

template<typename BV>

int coal::detail::HierarchyTree< BV >::bu_threshold

decide the depth to use expensive bottom-up algorithm

free_node

template<typename BV>

Node* coal::detail::HierarchyTree< BV >::free_node

protected

This is a one Node cache, the reason is that we need to remove a node and then add it again frequently.

max_lookahead_level

template<typename BV>

int coal::detail::HierarchyTree< BV >::max_lookahead_level

protected

n_leaves

template<typename BV>

size_t coal::detail::HierarchyTree< BV >::n_leaves

protected

opath

template<typename BV>

unsigned int coal::detail::HierarchyTree< BV >::opath

protected

root_node

template<typename BV>

Node* coal::detail::HierarchyTree< BV >::root_node

protected

topdown_level

template<typename BV>

int coal::detail::HierarchyTree< BV >::topdown_level

decide which topdown algorithm to use

---

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

• include/coal/broadphase/detail/hierarchy_tree.h
• include/coal/broadphase/detail/hierarchy_tree-inl.h