Class for hierarchy tree structure. More...

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

Collaboration diagram for coal::detail::HierarchyTree< BV >:

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, Scalar 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,
		Scalar	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

Public Types

Public Member Functions

Public Attributes

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ Node

Constructor & Destructor Documentation

◆ HierarchyTree()

◆ ~HierarchyTree()

Member Function Documentation

◆ balanceBottomup()

◆ balanceIncremental()

◆ balanceTopdown()

◆ clear()

◆ empty()

◆ extractLeaves()

◆ getMaxDepth()

◆ getMaxHeight()

◆ getRoot() [1/2]

◆ getRoot() [2/2]

◆ init()

◆ insert()

◆ print()

◆ refit()

◆ remove()

◆ size()

◆ update() [1/4]

◆ update() [2/4]

◆ update() [3/4]

◆ update() [4/4]

Member Data Documentation

◆ bu_threshold

◆ free_node

◆ max_lookahead_level

◆ n_leaves

◆ opath

◆ root_node

◆ topdown_level