Class for hierarchy tree structure. More...
#include <hierarchy_tree.h>
Classes | |
struct | SortByMorton |
Public Types | |
typedef NodeBase< BV > | Node |
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 Node *root, std::vector< Node *> &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... | |
Node * | getRoot () const |
get the root of the tree More... | |
Node *& | getRoot () |
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< Node *> &leaves, int level=0) |
Initialize the tree by a set of leaves using algorithm with a given level. More... | |
Node * | insert (const BV &bv, void *data) |
Insest a node. More... | |
void | print (Node *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 (Node *leaf) |
Remove a leaf node. More... | |
size_t | size () const |
number of leaves in the tree More... | |
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. More... | |
bool | update (Node *leaf, const BV &bv) |
update the tree when the bounding volume of a given leaf has changed More... | |
bool | update (Node *leaf, const BV &bv, const Vec3f &vel, FCL_REAL margin) |
update one leaf's bounding volume, with prediction More... | |
bool | update (Node *leaf, const BV &bv, const Vec3f &vel) |
update one leaf's bounding volume, with prediction 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 | |
Node * | free_node |
int | max_lookahead_level |
size_t | n_leaves |
unsigned int | opath |
Node * | root_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... | |
Node * | createNode (Node *parent, const BV &bv, void *data) |
create one node (leaf or internal) More... | |
Node * | createNode (Node *parent, const BV &bv1, const BV &bv2, void *data) |
Node * | createNode (Node *parent, void *data) |
void | deleteNode (Node *node) |
void | fetchLeaves (Node *root, std::vector< Node *> &leaves, int depth=-1) |
Delete all internal nodes and return all leaves nodes with given depth from root. More... | |
void | getMaxDepth (Node *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 (Node *node) const |
compute the maximum height of a subtree rooted from a given node More... | |
void | init_0 (std::vector< Node *> &leaves) |
init tree from leaves in the topdown manner (topdown_0 or topdown_1) More... | |
void | init_1 (std::vector< Node *> &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< Node *> &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< Node *> &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 (Node *const sub_root, Node *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... | |
Node * | mortonRecurse_0 (const NodeVecIterator lbeg, const NodeVecIterator lend, const uint32_t &split, int bits) |
Node * | mortonRecurse_1 (const NodeVecIterator lbeg, const NodeVecIterator lend, const uint32_t &split, int bits) |
Node * | mortonRecurse_2 (const NodeVecIterator lbeg, const NodeVecIterator lend) |
void | recurseDeleteNode (Node *node) |
void | recurseRefit (Node *node) |
Node * | removeLeaf (Node *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... | |
Node * | sort (Node *n, Node *&r) |
sort node n and its parent according to their memory position More... | |
Node * | topdown (const NodeVecIterator lbeg, const NodeVecIterator lend) |
construct a tree for a set of leaves from top More... | |
Node * | topdown_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... | |
Node * | topdown_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_ (Node *leaf, const BV &bv) |
update one leaf node's bounding volume More... | |
Static Private Member Functions | |
static size_t | indexOf (Node *node) |
Class for hierarchy tree structure.
Definition at line 57 of file hierarchy_tree.h.
typedef NodeBase<BV> hpp::fcl::detail::HierarchyTree< BV >::Node |
Definition at line 59 of file hierarchy_tree.h.
|
private |
Definition at line 145 of file hierarchy_tree.h.
|
private |
Definition at line 143 of file hierarchy_tree.h.
hpp::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 50 of file hierarchy_tree-inl.h.
hpp::fcl::detail::HierarchyTree< BV >::~HierarchyTree | ( | ) |
Definition at line 62 of file hierarchy_tree-inl.h.
void hpp::fcl::detail::HierarchyTree< BV >::balanceBottomup | ( | ) |
balance the tree from bottom
Definition at line 210 of file hierarchy_tree-inl.h.
void hpp::fcl::detail::HierarchyTree< BV >::balanceIncremental | ( | int | iterations | ) |
balance the tree in an incremental way
Definition at line 233 of file hierarchy_tree-inl.h.
void hpp::fcl::detail::HierarchyTree< BV >::balanceTopdown | ( | ) |
balance the tree from top
Definition at line 222 of file hierarchy_tree-inl.h.
|
private |
construct a tree for a set of leaves from bottom – very heavy way
Definition at line 300 of file hierarchy_tree-inl.h.
void hpp::fcl::detail::HierarchyTree< BV >::clear | ( | ) |
Clear the tree.
Definition at line 107 of file hierarchy_tree-inl.h.
|
private |
create one node (leaf or internal)
Definition at line 861 of file hierarchy_tree-inl.h.
|
private |
Definition at line 871 of file hierarchy_tree-inl.h.
|
private |
Definition at line 882 of file hierarchy_tree-inl.h.
|
private |
Definition at line 898 of file hierarchy_tree-inl.h.
bool hpp::fcl::detail::HierarchyTree< BV >::empty | ( | ) | const |
Whether the tree is empty.
Definition at line 118 of file hierarchy_tree-inl.h.
void hpp::fcl::detail::HierarchyTree< BV >::extractLeaves | ( | const Node * | root, |
std::vector< Node *> & | leaves | ||
) | const |
extract all the leaves of the tree
Definition at line 257 of file hierarchy_tree-inl.h.
|
private |
Delete all internal nodes and return all leaves nodes with given depth from root.
Definition at line 841 of file hierarchy_tree-inl.h.
size_t hpp::fcl::detail::HierarchyTree< BV >::getMaxDepth | ( | ) | const |
get the max depth of the tree
Definition at line 200 of file hierarchy_tree-inl.h.
|
private |
compute the maximum depth of a subtree rooted from a given node
Definition at line 360 of file hierarchy_tree-inl.h.
size_t hpp::fcl::detail::HierarchyTree< BV >::getMaxHeight | ( | ) | const |
get the max height of the tree
Definition at line 193 of file hierarchy_tree-inl.h.
|
private |
compute the maximum height of a subtree rooted from a given node
Definition at line 349 of file hierarchy_tree-inl.h.
HierarchyTree< BV >::Node * hpp::fcl::detail::HierarchyTree< BV >::getRoot | ( | ) | const |
get the root of the tree
Definition at line 274 of file hierarchy_tree-inl.h.
HierarchyTree< BV >::Node *& hpp::fcl::detail::HierarchyTree< BV >::getRoot | ( | ) |
Definition at line 280 of file hierarchy_tree-inl.h.
|
staticprivate |
Definition at line 854 of file hierarchy_tree-inl.h.
void hpp::fcl::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.
Definition at line 68 of file hierarchy_tree-inl.h.
|
private |
init tree from leaves in the topdown manner (topdown_0 or topdown_1)
Definition at line 466 of file hierarchy_tree-inl.h.
|
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 476 of file hierarchy_tree-inl.h.
|
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 500 of file hierarchy_tree-inl.h.
|
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 524 of file hierarchy_tree-inl.h.
HierarchyTree< BV >::Node * hpp::fcl::detail::HierarchyTree< BV >::insert | ( | const BV & | bv, |
void * | data | ||
) |
Insest a node.
Definition at line 89 of file hierarchy_tree-inl.h.
|
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.
sub_root | The root of the subtree into which we will insert the |
Definition at line 695 of file hierarchy_tree-inl.h.
|
private |
Definition at line 547 of file hierarchy_tree-inl.h.
|
private |
Definition at line 587 of file hierarchy_tree-inl.h.
|
private |
Definition at line 633 of file hierarchy_tree-inl.h.
void hpp::fcl::detail::HierarchyTree< BV >::print | ( | Node * | root, |
int | depth | ||
) |
print the tree in a recursive way
Definition at line 286 of file hierarchy_tree-inl.h.
|
private |
Definition at line 907 of file hierarchy_tree-inl.h.
|
private |
Definition at line 919 of file hierarchy_tree-inl.h.
void hpp::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 251 of file hierarchy_tree-inl.h.
void hpp::fcl::detail::HierarchyTree< BV >::remove | ( | Node * | leaf | ) |
Remove a leaf node.
Definition at line 99 of file hierarchy_tree-inl.h.
|
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.
Definition at line 776 of file hierarchy_tree-inl.h.
size_t hpp::fcl::detail::HierarchyTree< BV >::size | ( | ) | const |
number of leaves in the tree
Definition at line 268 of file hierarchy_tree-inl.h.
|
private |
sort node n and its parent according to their memory position
Definition at line 667 of file hierarchy_tree-inl.h.
|
private |
construct a tree for a set of leaves from top
Definition at line 333 of file hierarchy_tree-inl.h.
|
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 371 of file hierarchy_tree-inl.h.
|
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 406 of file hierarchy_tree-inl.h.
void hpp::fcl::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.
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 124 of file hierarchy_tree-inl.h.
bool hpp::fcl::detail::HierarchyTree< BV >::update | ( | Node * | leaf, |
const BV & | bv | ||
) |
update the tree when the bounding volume of a given leaf has changed
Definition at line 152 of file hierarchy_tree-inl.h.
bool hpp::fcl::detail::HierarchyTree< BV >::update | ( | Node * | leaf, |
const BV & | bv, | ||
const Vec3f & | vel, | ||
FCL_REAL | margin | ||
) |
update one leaf's bounding volume, with prediction
Definition at line 180 of file hierarchy_tree-inl.h.
bool hpp::fcl::detail::HierarchyTree< BV >::update | ( | Node * | leaf, |
const BV & | bv, | ||
const Vec3f & | vel | ||
) |
update one leaf's bounding volume, with prediction
Definition at line 187 of file hierarchy_tree-inl.h.
|
private |
update one leaf node's bounding volume
Definition at line 651 of file hierarchy_tree-inl.h.
int hpp::fcl::detail::HierarchyTree< BV >::bu_threshold |
decide the depth to use expensive bottom-up algorithm
Definition at line 269 of file hierarchy_tree.h.
|
protected |
This is a one Node cache, the reason is that we need to remove a node and then add it again frequently.
Definition at line 260 of file hierarchy_tree.h.
|
protected |
Definition at line 262 of file hierarchy_tree.h.
|
protected |
Definition at line 254 of file hierarchy_tree.h.
|
protected |
Definition at line 256 of file hierarchy_tree.h.
|
protected |
Definition at line 252 of file hierarchy_tree.h.
int hpp::fcl::detail::HierarchyTree< BV >::topdown_level |
decide which topdown algorithm to use
Definition at line 266 of file hierarchy_tree.h.