Class for hierarchy tree structure. More...

#include <hierarchy_tree.h>

Classes
struct	SortByMorton
Public Member Functions
void	balanceBottomup ()
	balance the tree from bottom
void	balanceIncremental (int iterations)
	balance the tree in an incremental way
void	balanceTopdown ()
	balance the tree from top
void	clear ()
	Clear the tree.
bool	empty () const
	Whether the tree is empty.
void	extractLeaves (size_t root, NodeType *&leaves) const
	extract all the leaves of the tree
size_t	getMaxDepth () const
	get the max depth of the tree
size_t	getMaxHeight () const
	get the max height of the tree
NodeType *	getNodes () const
	get the pointer to the nodes array
size_t	getRoot () const
	get the root of the tree
	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.
void	init (NodeType *leaves, int n_leaves_, int level=0)
	Initialize the tree by a set of leaves using algorithm with a given level.
size_t	insert (const BV &bv, void *data)
	Initialize the tree by a set of leaves using algorithm with a given level.
void	print (size_t root, int depth)
	print the tree in a recursive 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	remove (size_t leaf)
	Remove a leaf node.
size_t	size () const
	number of leaves in the tree
void	update (size_t leaf, int lookahead_level=-1)
	update one leaf node
bool	update (size_t leaf, const BV &bv)
	update the tree when the bounding volume of a given leaf has changed
bool	update (size_t leaf, const BV &bv, const Vec3f &vel, FCL_REAL margin)
	update one leaf's bounding volume, with prediction
bool	update (size_t leaf, const BV &bv, const Vec3f &vel)
	update one leaf's bounding volume, with prediction
	~HierarchyTree ()
Public Attributes
int	bu_threshold
	decide the depth to use expensive bottom-up algorithm
int	topdown_level
	decide which topdown algorithm to use
Static Public Attributes
static const size_t	NULL_NODE = -1
Protected Attributes
size_t	freelist
int	max_lookahead_level
size_t	n_leaves
size_t	n_nodes
size_t	n_nodes_alloc
NodeType *	nodes
unsigned int	opath
size_t	root_node
Private Types
typedef NodeBase< BV >	NodeType
Private Member Functions
size_t	allocateNode ()
void	bottomup (size_t lbeg, size_t lend)
	construct a tree for a set of leaves from bottom -- very heavy way
size_t	createNode (size_t parent, const BV &bv1, const BV &bv2, void *data)
	create one node (leaf or internal)
size_t	createNode (size_t parent, const BV &bv, void *data)
size_t	createNode (size_t parent, void *data)
void	deleteNode (size_t node)
void	fetchLeaves (size_t root, NodeType *&leaves, int depth=-1)
	Delete all internal nodes and return all leaves nodes with given depth from root.
void	getMaxDepth (size_t node, size_t depth, size_t &max_depth) const
	compute the maximum depth of a subtree rooted from a given node
size_t	getMaxHeight (size_t node) const
	compute the maximum height of a subtree rooted from a given node
size_t	indexOf (size_t node)
void	init_0 (NodeType *leaves, int n_leaves_)
	init tree from leaves in the topdown manner (topdown_0 or topdown_1)
void	init_1 (NodeType *leaves, int n_leaves_)
	init tree from leaves using morton code. It uses morton_0, i.e., for nodes which is of depth more than the maximum bits of the morton code, we use bottomup method to construct the subtree, which is slow but can construct tree with high quality.
void	init_2 (NodeType *leaves, int n_leaves_)
	init tree from leaves using morton code. It uses morton_0, i.e., for nodes which is of depth more than the maximum bits of the morton code, we split the leaves into two parts with the same size simply using the node index.
void	init_3 (NodeType *leaves, int n_leaves_)
	init tree from leaves using morton code. It uses morton_2, i.e., for all nodes, we simply divide the leaves into parts with the same size simply using the node index.
void	insertLeaf (size_t root, size_t leaf)
	Insert a leaf node and also update its ancestors.
size_t	mortonRecurse_0 (size_t lbeg, size_t lend, const FCL_UINT32 &split, int bits)
size_t	mortonRecurse_1 (size_t lbeg, size_t lend, const FCL_UINT32 &split, int bits)
size_t	mortonRecurse_2 (size_t lbeg, size_t lend)
void	recurseRefit (size_t node)
size_t	removeLeaf (size_t leaf)
	Remove a leaf. The leaf node itself is not deleted yet, but all the unnecessary internal nodes are deleted. return the node with the smallest depth and is influenced by the remove operation.
size_t	topdown (size_t lbeg, size_t lend)
	construct a tree for a set of leaves from top
size_t	topdown_0 (size_t lbeg, size_t lend)
	construct a tree from a list of nodes stored in [lbeg, lend) in a topdown manner. During construction, first compute the best split axis as the axis along with the longest AABB edge. Then compute the median of all nodes' center projection onto the axis and using it as the split threshold.
size_t	topdown_1 (size_t lbeg, size_t lend)
	construct a tree from a list of nodes stored in [lbeg, lend) in a topdown manner. During construction, first compute the best split thresholds for different axes as the average of all nodes' center. Then choose the split axis as the axis whose threshold can divide the nodes into two parts with almost similar size. This construction is more expensive then topdown_0, but also can provide tree with better quality.
void	update_ (size_t leaf, const BV &bv)
	update one leaf node's bounding volume

Detailed Description

template<typename BV>
class fcl::implementation_array::HierarchyTree< BV >

Class for hierarchy tree structure.

Definition at line 388 of file hierarchy_tree.h.

Member Typedef Documentation

template<typename BV>

typedef NodeBase<BV> fcl::implementation_array::HierarchyTree< BV >::NodeType [private]

Definition at line 390 of file hierarchy_tree.h.

Constructor & Destructor Documentation

template<typename BV>

fcl::implementation_array::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.

template<typename BV>

fcl::implementation_array::HierarchyTree< BV >::~HierarchyTree ( )

Member Function Documentation

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::allocateNode ( ) [private]

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::balanceBottomup ( )

balance the tree from bottom

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::balanceIncremental ( int iterations )

balance the tree in an incremental way

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::balanceTopdown ( )

balance the tree from top

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::bottomup	(	size_t *	lbeg,
		size_t *	lend
	)		`[private]`

construct a tree for a set of leaves from bottom -- very heavy way

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::clear ( )

Clear the tree.

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::createNode	(	size_t	parent,
		const BV &	bv1,
		const BV &	bv2,
		void *	data
	)		`[private]`

create one node (leaf or internal)

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::createNode	(	size_t	parent,
		const BV &	bv,
		void *	data
	)		`[private]`

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::createNode	(	size_t	parent,
		void *	data
	)		`[private]`

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::deleteNode ( size_t node ) [private]

template<typename BV>

bool fcl::implementation_array::HierarchyTree< BV >::empty ( ) const

Whether the tree is empty.

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::extractLeaves	(	size_t	root,
		NodeType *&	leaves
	)		const

extract all the leaves of the tree

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::fetchLeaves	(	size_t	root,
		NodeType *&	leaves,
		int	depth = `-1`
	)		`[private]`

Delete all internal nodes and return all leaves nodes with given depth from root.

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::getMaxDepth ( ) const

get the max depth of the tree

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::getMaxDepth	(	size_t	node,
		size_t	depth,
		size_t &	max_depth
	)		const `[private]`

compute the maximum depth of a subtree rooted from a given node

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::getMaxHeight ( ) const

get the max height of the tree

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::getMaxHeight ( size_t node ) const [private]

compute the maximum height of a subtree rooted from a given node

template<typename BV>

NodeType* fcl::implementation_array::HierarchyTree< BV >::getNodes ( ) const

get the pointer to the nodes array

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::getRoot ( ) const

get the root of the tree

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::indexOf ( size_t node ) [private]

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::init	(	NodeType *	leaves,
		int	n_leaves_,
		int	level = `0`
	)

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

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::init_0	(	NodeType *	leaves,
		int	n_leaves_
	)		`[private]`

init tree from leaves in the topdown manner (topdown_0 or topdown_1)

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::init_1	(	NodeType *	leaves,
		int	n_leaves_
	)		`[private]`

init tree from leaves using morton code. It uses morton_0, i.e., for nodes which is of depth more than the maximum bits of the morton code, we use bottomup method to construct the subtree, which is slow but can construct tree with high quality.

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::init_2	(	NodeType *	leaves,
		int	n_leaves_
	)		`[private]`

init tree from leaves using morton code. It uses morton_0, i.e., for nodes which is of depth more than the maximum bits of the morton code, we split the leaves into two parts with the same size simply using the node index.

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::init_3	(	NodeType *	leaves,
		int	n_leaves_
	)		`[private]`

init tree from leaves using morton code. It uses morton_2, i.e., for all nodes, we simply divide the leaves into parts with the same size simply using the node index.

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::insert	(	const BV &	bv,
		void *	data
	)

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

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::insertLeaf	(	size_t	root,
		size_t	leaf
	)		`[private]`

Insert a leaf node and also update its ancestors.

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::mortonRecurse_0	(	size_t *	lbeg,
		size_t *	lend,
		const FCL_UINT32 &	split,
		int	bits
	)		`[private]`

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::mortonRecurse_1	(	size_t *	lbeg,
		size_t *	lend,
		const FCL_UINT32 &	split,
		int	bits
	)		`[private]`

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::mortonRecurse_2	(	size_t *	lbeg,
		size_t *	lend
	)		`[private]`

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::print	(	size_t	root,
		int	depth
	)

print the tree in a recursive way

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::recurseRefit ( size_t node ) [private]

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::refit ( )

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

template<typename BV>

void fcl::implementation_array::HierarchyTree< BV >::remove ( size_t leaf )

Remove a leaf node.

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::removeLeaf ( size_t leaf ) [private]

Remove a leaf. The leaf node itself is not deleted yet, but all the unnecessary internal nodes are deleted. return the node with the smallest depth and is influenced by the remove operation.

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::size ( ) const

number of leaves in the tree

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::topdown	(	size_t *	lbeg,
		size_t *	lend
	)		`[private]`

construct a tree for a set of leaves from top

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::topdown_0	(	size_t *	lbeg,
		size_t *	lend
	)		`[private]`

construct a tree from a list of nodes stored in [lbeg, lend) in a topdown manner. During construction, first compute the best split axis as the axis along with the longest AABB edge. Then compute the median of all nodes' center projection onto the axis and using it as the split threshold.

template<typename BV>

size_t fcl::implementation_array::HierarchyTree< BV >::topdown_1	(	size_t *	lbeg,
		size_t *	lend
	)		`[private]`

construct a tree from a list of nodes stored in [lbeg, lend) in a topdown manner. During construction, first compute the best split thresholds for different axes as the average of all nodes' center. Then choose the split axis as the axis whose threshold can divide the nodes into two parts with almost similar size. This construction is more expensive then topdown_0, but also can provide tree with better quality.

template<typename BV>