Class for hierarchy tree structure. More...

#include <hierarchy_tree_array.h>

Classes
struct	SortByMorton

Public Member Functions
void	balanceBottomup ()
	balance the tree from bottom More...

void	balanceIncremental (int iterations)
	balance the tree in an incremental way More...

void	balanceTopdown ()
	balance the tree from top More...

void	clear ()
	Clear the tree. More...

bool	empty () const
	Whether the tree is empty. More...

void	extractLeaves (size_t root, NodeType *&leaves) const
	extract all the leaves of the tree More...

size_t	getMaxDepth () const
	get the max depth of the tree More...

size_t	getMaxHeight () const
	get the max height of the tree More...

NodeType *	getNodes () const
	get the pointer to the nodes array More...

size_t	getRoot () const
	get the root of the tree More...

	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. More...

void	init (NodeType *leaves, int n_leaves_, int level=0)
	Initialize the tree by a set of leaves using algorithm with a given level. More...

size_t	insert (const BV &bv, void *data)
	Initialize the tree by a set of leaves using algorithm with a given level. More...

void	print (size_t root, int depth)
	print the tree in a recursive way More...

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

void	remove (size_t leaf)
	Remove a leaf node. More...

size_t	size () const
	number of leaves in the tree More...

bool	update (size_t leaf, const BV &bv)
	update the tree when the bounding volume of a given leaf has changed More...

bool	update (size_t leaf, const BV &bv, const Vector3< S > &vel)
	update one leaf's bounding volume, with prediction More...

bool	update (size_t leaf, const BV &bv, const Vector3< S > &vel, S margin)
	update one leaf's bounding volume, with prediction More...

void	update (size_t leaf, int lookahead_level=-1)
	update one leaf node More...

	~HierarchyTree ()

Public Attributes
int	bu_threshold
	decide the depth to use expensive bottom-up algorithm More...

int	topdown_level
	decide which topdown algorithm to use More...

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

using	S = typename BV::S

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 More...

size_t	createNode (size_t parent, const BV &bv, void *data)

size_t	createNode (size_t parent, const BV &bv1, const BV &bv2, void *data)
	create one node (leaf or internal) More...

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. More...

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 More...

size_t	getMaxHeight (size_t node) const
	compute the maximum height of a subtree rooted from a given node More...

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) More...

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. More...

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. More...

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. More...

void	insertLeaf (size_t root, size_t leaf)
	Insert a leaf node and also update its ancestors. More...

size_t	mortonRecurse_0 (size_t lbeg, size_t lend, const uint32 &split, int bits)

size_t	mortonRecurse_1 (size_t lbeg, size_t lend, const 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 More...

size_t	topdown (size_t lbeg, size_t lend)
	construct a tree for a set of leaves from top More...

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.~~ More...

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. More...

void	update_ (size_t leaf, const BV &bv)
	update one leaf node's bounding volume More...

Detailed Description

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

Class for hierarchy tree structure.

Definition at line 61 of file hierarchy_tree_array.h.

Member Typedef Documentation

◆ NodeType

template<typename BV >

typedef NodeBase<BV> fcl::detail::implementation_array::HierarchyTree< BV >::NodeType

private

Definition at line 64 of file hierarchy_tree_array.h.

◆ S

template<typename BV >

using fcl::detail::implementation_array::HierarchyTree< BV >::S = typename BV::S

private

Definition at line 63 of file hierarchy_tree_array.h.

Constructor & Destructor Documentation

◆ HierarchyTree()

template<typename BV >

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

Definition at line 58 of file hierarchy_tree_array-inl.h.

◆ ~HierarchyTree()

template<typename BV >

fcl::detail::implementation_array::HierarchyTree< BV >::~HierarchyTree

Definition at line 77 of file hierarchy_tree_array-inl.h.

Member Function Documentation

◆ allocateNode()

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::allocateNode

private

Definition at line 944 of file hierarchy_tree_array-inl.h.

◆ balanceBottomup()

template<typename BV >

void fcl::detail::implementation_array::HierarchyTree< BV >::balanceBottomup

balance the tree from bottom

Definition at line 382 of file hierarchy_tree_array-inl.h.

◆ balanceIncremental()

template<typename BV >

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

balance the tree in an incremental way

Definition at line 437 of file hierarchy_tree_array-inl.h.

◆ balanceTopdown()

template<typename BV >

void fcl::detail::implementation_array::HierarchyTree< BV >::balanceTopdown

balance the tree from top

Definition at line 411 of file hierarchy_tree_array-inl.h.

◆ bottomup()

template<typename BV >

void fcl::detail::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

Definition at line 549 of file hierarchy_tree_array-inl.h.

◆ clear()

template<typename BV >

void fcl::detail::implementation_array::HierarchyTree< BV >::clear

Clear the tree.

Definition at line 286 of file hierarchy_tree_array-inl.h.

◆ createNode() [1/3]

template<typename BV >

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

private

Definition at line 985 of file hierarchy_tree_array-inl.h.

◆ createNode() [2/3]

template<typename BV >

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

private

create one node (leaf or internal)

Definition at line 971 of file hierarchy_tree_array-inl.h.

◆ createNode() [3/3]

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::createNode	(	size_t	parent,
		void *	data
	)

private

Definition at line 998 of file hierarchy_tree_array-inl.h.

◆ deleteNode()

template<typename BV >

void fcl::detail::implementation_array::HierarchyTree< BV >::deleteNode ( size_t node )

private

Definition at line 1009 of file hierarchy_tree_array-inl.h.

◆ empty()

template<typename BV >

bool fcl::detail::implementation_array::HierarchyTree< BV >::empty

Whether the tree is empty.

Definition at line 304 of file hierarchy_tree_array-inl.h.

◆ extractLeaves()

template<typename BV >

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

extract all the leaves of the tree

Definition at line 467 of file hierarchy_tree_array-inl.h.

◆ fetchLeaves()

template<typename BV >

void fcl::detail::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.

Definition at line 1032 of file hierarchy_tree_array-inl.h.

◆ getMaxDepth() [1/2]

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::getMaxDepth

get the max depth of the tree

Definition at line 371 of file hierarchy_tree_array-inl.h.

◆ getMaxDepth() [2/2]

template<typename BV >

void fcl::detail::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

Definition at line 536 of file hierarchy_tree_array-inl.h.

◆ getMaxHeight() [1/2]

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::getMaxHeight

get the max height of the tree

Definition at line 362 of file hierarchy_tree_array-inl.h.

◆ getMaxHeight() [2/2]

template<typename BV >

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

private

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

Definition at line 522 of file hierarchy_tree_array-inl.h.

◆ getNodes()

template<typename BV >

HierarchyTree< BV >::NodeType * fcl::detail::implementation_array::HierarchyTree< BV >::getNodes

get the pointer to the nodes array

Definition at line 497 of file hierarchy_tree_array-inl.h.

◆ getRoot()

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::getRoot

get the root of the tree

Definition at line 490 of file hierarchy_tree_array-inl.h.

◆ indexOf()

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::indexOf ( size_t node )

private

Definition at line 937 of file hierarchy_tree_array-inl.h.

◆ init()

template<typename BV >

void fcl::detail::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.

Definition at line 84 of file hierarchy_tree_array-inl.h.

◆ init_0()

template<typename BV >

void fcl::detail::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)

Definition at line 107 of file hierarchy_tree_array-inl.h.

◆ init_1()

template<typename BV >

void fcl::detail::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.

Definition at line 135 of file hierarchy_tree_array-inl.h.

◆ init_2()

template<typename BV >

void fcl::detail::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.

Definition at line 179 of file hierarchy_tree_array-inl.h.

◆ init_3()

template<typename BV >

void fcl::detail::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.

Definition at line 223 of file hierarchy_tree_array-inl.h.

◆ insert()

template<typename BV >

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

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

Definition at line 267 of file hierarchy_tree_array-inl.h.

◆ insertLeaf()

template<typename BV >

void fcl::detail::implementation_array::HierarchyTree< BV >::insertLeaf	(	size_t	root,
		size_t	leaf
	)

private

Insert a leaf node and also update its ancestors.

Definition at line 831 of file hierarchy_tree_array-inl.h.

◆ mortonRecurse_0()

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::mortonRecurse_0	(	size_t *	lbeg,
		size_t *	lend,
		const uint32 &	split,
		int	bits
	)

private

Definition at line 711 of file hierarchy_tree_array-inl.h.

◆ mortonRecurse_1()

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::mortonRecurse_1	(	size_t *	lbeg,
		size_t *	lend,
		const uint32 &	split,
		int	bits
	)

private

Definition at line 758 of file hierarchy_tree_array-inl.h.

◆ mortonRecurse_2()

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::mortonRecurse_2	(	size_t *	lbeg,
		size_t *	lend
	)

private

Definition at line 811 of file hierarchy_tree_array-inl.h.

◆ print()

template<typename BV >

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

print the tree in a recursive way

Definition at line 504 of file hierarchy_tree_array-inl.h.

◆ recurseRefit()

template<typename BV >

void fcl::detail::implementation_array::HierarchyTree< BV >::recurseRefit ( size_t node )

private

Definition at line 1018 of file hierarchy_tree_array-inl.h.

◆ refit()

template<typename BV >

void fcl::detail::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

Definition at line 459 of file hierarchy_tree_array-inl.h.

◆ remove()

template<typename BV >

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

Remove a leaf node.

Definition at line 277 of file hierarchy_tree_array-inl.h.

◆ removeLeaf()

template<typename BV >

size_t fcl::detail::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

Definition at line 876 of file hierarchy_tree_array-inl.h.

◆ size()

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::size

number of leaves in the tree

Definition at line 483 of file hierarchy_tree_array-inl.h.

◆ topdown()

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::topdown	(	size_t *	lbeg,
		size_t *	lend
	)

private

construct a tree for a set of leaves from top

Definition at line 585 of file hierarchy_tree_array-inl.h.

◆ topdown_0()

template<typename BV >

size_t fcl::detail::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.~~

Definition at line 602 of file hierarchy_tree_array-inl.h.

◆ topdown_1()

template<typename BV >

size_t fcl::detail::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.

Definition at line 640 of file hierarchy_tree_array-inl.h.

◆ update() [1/4]

template<typename BV >

bool fcl::detail::implementation_array::HierarchyTree< BV >::update	(	size_t	leaf,
		const BV &	bv
	)

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

Definition at line 329 of file hierarchy_tree_array-inl.h.

◆ update() [2/4]

template<typename BV >

bool fcl::detail::implementation_array::HierarchyTree< BV >::update	(	size_t	leaf,
		const BV &	bv,
		const Vector3< S > &	vel
	)

update one leaf's bounding volume, with prediction

Definition at line 351 of file hierarchy_tree_array-inl.h.

◆ update() [3/4]

template<typename BV >

bool fcl::detail::implementation_array::HierarchyTree< BV >::update	(	size_t	leaf,
		const BV &	bv,
		const Vector3< S > &	vel,
		S	margin
	)

update one leaf's bounding volume, with prediction

Definition at line 338 of file hierarchy_tree_array-inl.h.

◆ update() [4/4]

template<typename BV >

void fcl::detail::implementation_array::HierarchyTree< BV >::update	(	size_t	leaf,
		int	lookahead_level = `-1`
	)

update one leaf node

Definition at line 311 of file hierarchy_tree_array-inl.h.

◆ update_()

template<typename BV >

void fcl::detail::implementation_array::HierarchyTree< BV >::update_	(	size_t	leaf,
		const BV &	bv
	)

private

update one leaf node's bounding volume

Definition at line 919 of file hierarchy_tree_array-inl.h.

Member Data Documentation

◆ bu_threshold

template<typename BV >

int fcl::detail::implementation_array::HierarchyTree< BV >::bu_threshold

decide the depth to use expensive bottom-up algorithm

Definition at line 252 of file hierarchy_tree_array.h.

◆ freelist

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::freelist

protected

Definition at line 242 of file hierarchy_tree_array.h.

◆ max_lookahead_level

template<typename BV >

int fcl::detail::implementation_array::HierarchyTree< BV >::max_lookahead_level

protected

Definition at line 245 of file hierarchy_tree_array.h.

◆ n_leaves

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::n_leaves

protected

Definition at line 241 of file hierarchy_tree_array.h.

◆ n_nodes

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::n_nodes

protected

Definition at line 238 of file hierarchy_tree_array.h.

◆ n_nodes_alloc

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::n_nodes_alloc

protected

Definition at line 239 of file hierarchy_tree_array.h.

◆ nodes

template<typename BV >

NodeType* fcl::detail::implementation_array::HierarchyTree< BV >::nodes

protected

Definition at line 237 of file hierarchy_tree_array.h.

◆ NULL_NODE

template<typename BV >

const size_t fcl::detail::implementation_array::HierarchyTree< BV >::NULL_NODE = -1

static

Definition at line 255 of file hierarchy_tree_array.h.

◆ opath

template<typename BV >

unsigned int fcl::detail::implementation_array::HierarchyTree< BV >::opath

protected

Definition at line 243 of file hierarchy_tree_array.h.

◆ root_node

template<typename BV >

size_t fcl::detail::implementation_array::HierarchyTree< BV >::root_node

protected

Definition at line 236 of file hierarchy_tree_array.h.

◆ topdown_level

template<typename BV >

int fcl::detail::implementation_array::HierarchyTree< BV >::topdown_level

decide which topdown algorithm to use

Definition at line 249 of file hierarchy_tree_array.h.

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

Classes

Public Member Functions

Public Attributes

Static Public Attributes

Protected Attributes

Private Types

Private Member Functions

Detailed Description

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

Member Typedef Documentation

◆ NodeType

◆ S

Constructor & Destructor Documentation

◆ HierarchyTree()

◆ ~HierarchyTree()

Member Function Documentation

◆ allocateNode()

◆ balanceBottomup()

◆ balanceIncremental()

◆ balanceTopdown()

◆ bottomup()

◆ clear()

◆ createNode() [1/3]

◆ createNode() [2/3]

◆ createNode() [3/3]

◆ deleteNode()

◆ empty()

◆ extractLeaves()

◆ fetchLeaves()

◆ getMaxDepth() [1/2]

◆ getMaxDepth() [2/2]

◆ getMaxHeight() [1/2]

◆ getMaxHeight() [2/2]

◆ getNodes()

◆ getRoot()

◆ indexOf()

◆ init()

◆ init_0()

◆ init_1()

◆ init_2()

◆ init_3()

◆ insert()

◆ insertLeaf()

◆ mortonRecurse_0()

◆ mortonRecurse_1()

◆ mortonRecurse_2()

◆ print()

◆ recurseRefit()

◆ refit()

◆ remove()

◆ removeLeaf()

◆ size()

◆ topdown()

◆ topdown_0()

◆ topdown_1()

◆ update() [1/4]

◆ update() [2/4]

◆ update() [3/4]

◆ update() [4/4]

◆ update_()

Member Data Documentation

◆ bu_threshold

◆ freelist

◆ max_lookahead_level

◆ n_leaves

◆ n_nodes

◆ n_nodes_alloc

◆ nodes

◆ NULL_NODE

◆ opath

◆ root_node

◆ topdown_level

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