Classes | Public Types | Public Member Functions | Public Attributes | Protected Attributes | Private Types | Private Member Functions | Static Private Member Functions | List of all members
fcl::detail::HierarchyTree< BV > Class Template Reference

Class for hierarchy tree structure. More...

#include <hierarchy_tree.h>

Classes

struct  SortByMorton
 

Public Types

typedef NodeBase< BV > NodeType
 
using S = typename BV::S
 

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 (const NodeType *root, std::vector< 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 *& getRoot ()
 
NodeTypegetRoot () 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 (std::vector< NodeType * > &leaves, int level=0)
 Initialize the tree by a set of leaves using algorithm with a given level. More...
 
NodeTypeinsert (const BV &bv, void *data)
 Insest a node. More...
 
void print (NodeType *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 (NodeType *leaf)
 Remove a leaf node. More...
 
size_t size () const
 number of leaves in the tree More...
 
bool update (NodeType *leaf, const BV &bv)
 update the tree when the bounding volume of a given leaf has changed More...
 
bool update (NodeType *leaf, const BV &bv, const Vector3< S > &vel)
 update one leaf's bounding volume, with prediction More...
 
bool update (NodeType *leaf, const BV &bv, const Vector3< S > &vel, S margin)
 update one leaf's bounding volume, with prediction More...
 
void update (NodeType *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. 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...
 

Protected Attributes

NodeTypefree_node
 This is a one NodeType cache, the reason is that we need to remove a node and then add it again frequently. More...
 
int max_lookahead_level
 
size_t n_leaves
 
unsigned int opath
 
NodeTyperoot_node
 

Private Types

typedef std::vector< NodeBase< BV > * >::const_iterator NodeVecConstIterator
 
typedef std::vector< NodeBase< BV > * >::iterator NodeVecIterator
 

Private Member Functions

void bottomup (const NodeVecIterator lbeg, const NodeVecIterator lend)
 construct a tree for a set of leaves from bottom – very heavy way More...
 
NodeTypecreateNode (NodeType *parent, const BV &bv, void *data)
 create one node (leaf or internal)
More...
 
NodeTypecreateNode (NodeType *parent, const BV &bv1, const BV &bv2, void *data)
 
NodeTypecreateNode (NodeType *parent, void *data)
 
void deleteNode (NodeType *node)
 
void fetchLeaves (NodeType *root, std::vector< NodeType * > &leaves, int depth=-1)
 Delete all internal nodes and return all leaves nodes with given depth from root. More...
 
void getMaxDepth (NodeType *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 (NodeType *node) const
 compute the maximum height of a subtree rooted from a given node More...
 
void init_0 (std::vector< NodeType * > &leaves)
 init tree from leaves in the topdown manner (topdown_0 or topdown_1) More...
 
void init_1 (std::vector< NodeType * > &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 (std::vector< NodeType * > &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 (std::vector< NodeType * > &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 (NodeType *const sub_root, NodeType *const leaf)
 Insert a leaf node and also update its ancestors. Maintain the tree as a full binary tree (every interior node has exactly two children). Furthermore, adjust the BV of interior nodes so that each parent's BV tightly fits its children's BVs. More...
 
NodeTypemortonRecurse_0 (const NodeVecIterator lbeg, const NodeVecIterator lend, const uint32 &split, int bits)
 
NodeTypemortonRecurse_1 (const NodeVecIterator lbeg, const NodeVecIterator lend, const uint32 &split, int bits)
 
NodeTypemortonRecurse_2 (const NodeVecIterator lbeg, const NodeVecIterator lend)
 
void recurseDeleteNode (NodeType *node)
 
void recurseRefit (NodeType *node)
 
NodeTyperemoveLeaf (NodeType *const leaf)
 Remove a leaf. Maintain the tree as a full binary tree (every interior node has exactly two children). Furthermore, adjust the BV of interior nodes so that each parent's BV tightly fits its children's BVs. More...
 
NodeTypesort (NodeType *n, NodeType *&r)
 sort node n and its parent according to their memory position More...
 
NodeTypetopdown (const NodeVecIterator lbeg, const NodeVecIterator lend)
 construct a tree for a set of leaves from top More...
 
NodeTypetopdown_0 (const NodeVecIterator lbeg, const NodeVecIterator 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...
 
NodeTypetopdown_1 (const NodeVecIterator lbeg, const NodeVecIterator 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_ (NodeType *leaf, const BV &bv)
 update one leaf node's bounding volume More...
 

Static Private Member Functions

static size_t indexOf (NodeType *node)
 

Detailed Description

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

Class for hierarchy tree structure.

Definition at line 58 of file hierarchy_tree.h.

Member Typedef Documentation

◆ NodeType

template<typename BV >
typedef NodeBase<BV> fcl::detail::HierarchyTree< BV >::NodeType

Definition at line 64 of file hierarchy_tree.h.

◆ NodeVecConstIterator

template<typename BV >
typedef std::vector<NodeBase<BV>* >::const_iterator fcl::detail::HierarchyTree< BV >::NodeVecConstIterator
private

Definition at line 146 of file hierarchy_tree.h.

◆ NodeVecIterator

template<typename BV >
typedef std::vector<NodeBase<BV>* >::iterator fcl::detail::HierarchyTree< BV >::NodeVecIterator
private

Definition at line 145 of file hierarchy_tree.h.

◆ S

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

Definition at line 62 of file hierarchy_tree.h.

Constructor & Destructor Documentation

◆ HierarchyTree()

template<typename BV >
fcl::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.

Definition at line 51 of file hierarchy_tree-inl.h.

◆ ~HierarchyTree()

template<typename BV >
fcl::detail::HierarchyTree< BV >::~HierarchyTree

Definition at line 64 of file hierarchy_tree-inl.h.

Member Function Documentation

◆ balanceBottomup()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::balanceBottomup

balance the tree from bottom

Definition at line 236 of file hierarchy_tree-inl.h.

◆ balanceIncremental()

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

balance the tree in an incremental way

Definition at line 263 of file hierarchy_tree-inl.h.

◆ balanceTopdown()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::balanceTopdown

balance the tree from top

Definition at line 250 of file hierarchy_tree-inl.h.

◆ bottomup()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::bottomup ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend 
)
private

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

Definition at line 344 of file hierarchy_tree-inl.h.

◆ clear()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::clear

Clear the tree.

Definition at line 113 of file hierarchy_tree-inl.h.

◆ createNode() [1/3]

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::createNode ( NodeType parent,
const BV &  bv,
void *  data 
)
private

create one node (leaf or internal)

Definition at line 970 of file hierarchy_tree-inl.h.

◆ createNode() [2/3]

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::createNode ( NodeType parent,
const BV &  bv1,
const BV &  bv2,
void *  data 
)
private

Definition at line 981 of file hierarchy_tree-inl.h.

◆ createNode() [3/3]

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::createNode ( NodeType parent,
void *  data 
)
private

Definition at line 993 of file hierarchy_tree-inl.h.

◆ deleteNode()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::deleteNode ( NodeType node)
private

Definition at line 1011 of file hierarchy_tree-inl.h.

◆ empty()

template<typename BV >
bool fcl::detail::HierarchyTree< BV >::empty

Whether the tree is empty.

Definition at line 126 of file hierarchy_tree-inl.h.

◆ extractLeaves()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::extractLeaves ( const NodeType root,
std::vector< NodeType * > &  leaves 
) const

extract all the leaves of the tree

Definition at line 293 of file hierarchy_tree-inl.h.

◆ fetchLeaves()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::fetchLeaves ( NodeType root,
std::vector< NodeType * > &  leaves,
int  depth = -1 
)
private

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

Definition at line 946 of file hierarchy_tree-inl.h.

◆ getMaxDepth() [1/2]

template<typename BV >
size_t fcl::detail::HierarchyTree< BV >::getMaxDepth

get the max depth of the tree

Definition at line 225 of file hierarchy_tree-inl.h.

◆ getMaxDepth() [2/2]

template<typename BV >
void fcl::detail::HierarchyTree< BV >::getMaxDepth ( NodeType 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 412 of file hierarchy_tree-inl.h.

◆ getMaxHeight() [1/2]

template<typename BV >
size_t fcl::detail::HierarchyTree< BV >::getMaxHeight

get the max height of the tree

Definition at line 216 of file hierarchy_tree-inl.h.

◆ getMaxHeight() [2/2]

template<typename BV >
size_t fcl::detail::HierarchyTree< BV >::getMaxHeight ( NodeType node) const
private

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

Definition at line 398 of file hierarchy_tree-inl.h.

◆ getRoot() [1/2]

template<typename BV >
NodeType*& fcl::detail::HierarchyTree< BV >::getRoot ( )

◆ getRoot() [2/2]

template<typename BV >
HierarchyTree< BV >::NodeType *& fcl::detail::HierarchyTree< BV >::getRoot

get the root of the tree

Definition at line 313 of file hierarchy_tree-inl.h.

◆ indexOf()

template<typename BV >
size_t fcl::detail::HierarchyTree< BV >::indexOf ( NodeType node)
staticprivate

Definition at line 962 of file hierarchy_tree-inl.h.

◆ init()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::init ( std::vector< NodeType * > &  leaves,
int  level = 0 
)

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

Definition at line 71 of file hierarchy_tree-inl.h.

◆ init_0()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::init_0 ( std::vector< NodeType * > &  leaves)
private

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

Definition at line 535 of file hierarchy_tree-inl.h.

◆ init_1()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::init_1 ( std::vector< NodeType * > &  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 546 of file hierarchy_tree-inl.h.

◆ init_2()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::init_2 ( std::vector< NodeType * > &  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 572 of file hierarchy_tree-inl.h.

◆ init_3()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::init_3 ( std::vector< NodeType * > &  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 598 of file hierarchy_tree-inl.h.

◆ insert()

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::insert ( const BV &  bv,
void *  data 
)

Insest a node.

Definition at line 94 of file hierarchy_tree-inl.h.

◆ insertLeaf()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::insertLeaf ( NodeType *const  sub_root,
NodeType *const  leaf 
)
private

Insert a leaf node and also update its ancestors. Maintain the tree as a full binary tree (every interior node has exactly two children). Furthermore, adjust the BV of interior nodes so that each parent's BV tightly fits its children's BVs.

Parameters
sub_rootThe root of the subtree into which we will insert the

Definition at line 793 of file hierarchy_tree-inl.h.

◆ mortonRecurse_0()

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::mortonRecurse_0 ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend,
const uint32 split,
int  bits 
)
private

Definition at line 624 of file hierarchy_tree-inl.h.

◆ mortonRecurse_1()

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::mortonRecurse_1 ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend,
const uint32 split,
int  bits 
)
private

Definition at line 672 of file hierarchy_tree-inl.h.

◆ mortonRecurse_2()

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::mortonRecurse_2 ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend 
)
private

Definition at line 726 of file hierarchy_tree-inl.h.

◆ print()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::print ( NodeType root,
int  depth 
)

print the tree in a recursive way

Definition at line 327 of file hierarchy_tree-inl.h.

◆ recurseDeleteNode()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::recurseDeleteNode ( NodeType node)
private

Definition at line 1022 of file hierarchy_tree-inl.h.

◆ recurseRefit()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::recurseRefit ( NodeType node)
private

Definition at line 1036 of file hierarchy_tree-inl.h.

◆ refit()

template<typename BV >
void fcl::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

Definition at line 285 of file hierarchy_tree-inl.h.

◆ remove()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::remove ( NodeType leaf)

Remove a leaf node.

Definition at line 104 of file hierarchy_tree-inl.h.

◆ removeLeaf()

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::removeLeaf ( NodeType *const  leaf)
private

Remove a leaf. Maintain the tree as a full binary tree (every interior node has exactly two children). Furthermore, adjust the BV of interior nodes so that each parent's BV tightly fits its children's BVs.

Note
The leaf node itself is not deleted yet, but all the unnecessary internal nodes are deleted.
Returns
the root of the subtree containing the nodes whose BVs were

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

◆ size()

template<typename BV >
size_t fcl::detail::HierarchyTree< BV >::size

number of leaves in the tree

Definition at line 306 of file hierarchy_tree-inl.h.

◆ sort()

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::sort ( NodeType n,
NodeType *&  r 
)
private

sort node n and its parent according to their memory position

Definition at line 766 of file hierarchy_tree-inl.h.

◆ topdown()

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::topdown ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend 
)
private

construct a tree for a set of leaves from top

Definition at line 381 of file hierarchy_tree-inl.h.

◆ topdown_0()

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::topdown_0 ( const NodeVecIterator  lbeg,
const NodeVecIterator  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 425 of file hierarchy_tree-inl.h.

◆ topdown_1()

template<typename BV >
HierarchyTree< BV >::NodeType * fcl::detail::HierarchyTree< BV >::topdown_1 ( const NodeVecIterator  lbeg,
const NodeVecIterator  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 463 of file hierarchy_tree-inl.h.

◆ update() [1/4]

template<typename BV >
bool fcl::detail::HierarchyTree< BV >::update ( NodeType leaf,
const BV &  bv 
)

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

Definition at line 165 of file hierarchy_tree-inl.h.

◆ update() [2/4]

template<typename BV >
bool fcl::detail::HierarchyTree< BV >::update ( NodeType leaf,
const BV &  bv,
const Vector3< S > &  vel 
)

update one leaf's bounding volume, with prediction

Definition at line 209 of file hierarchy_tree-inl.h.

◆ update() [3/4]

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

update one leaf's bounding volume, with prediction

Definition at line 202 of file hierarchy_tree-inl.h.

◆ update() [4/4]

template<typename BV >
void fcl::detail::HierarchyTree< BV >::update ( NodeType 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.

Definition at line 133 of file hierarchy_tree-inl.h.

◆ update_()

template<typename BV >
void fcl::detail::HierarchyTree< BV >::update_ ( NodeType leaf,
const BV &  bv 
)
private

update one leaf node's bounding volume

Definition at line 746 of file hierarchy_tree-inl.h.

Member Data Documentation

◆ bu_threshold

template<typename BV >
int fcl::detail::HierarchyTree< BV >::bu_threshold

decide the depth to use expensive bottom-up algorithm

Definition at line 263 of file hierarchy_tree.h.

◆ free_node

template<typename BV >
NodeType* fcl::detail::HierarchyTree< BV >::free_node
protected

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

Definition at line 254 of file hierarchy_tree.h.

◆ max_lookahead_level

template<typename BV >
int fcl::detail::HierarchyTree< BV >::max_lookahead_level
protected

Definition at line 256 of file hierarchy_tree.h.

◆ n_leaves

template<typename BV >
size_t fcl::detail::HierarchyTree< BV >::n_leaves
protected

Definition at line 249 of file hierarchy_tree.h.

◆ opath

template<typename BV >
unsigned int fcl::detail::HierarchyTree< BV >::opath
protected

Definition at line 251 of file hierarchy_tree.h.

◆ root_node

template<typename BV >
NodeType* fcl::detail::HierarchyTree< BV >::root_node
protected

Definition at line 247 of file hierarchy_tree.h.

◆ topdown_level

template<typename BV >
int fcl::detail::HierarchyTree< BV >::topdown_level

decide which topdown algorithm to use

Definition at line 260 of file hierarchy_tree.h.


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


fcl
Author(s):
autogenerated on Fri Apr 2 2021 02:38:02