Class for hierarchy tree structure. More...
#include <hierarchy_tree_array.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 (size_t root, 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 * | 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 (Node *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 Vec3f &vel) |
update one leaf's bounding volume, with prediction More... | |
bool | update (size_t leaf, const BV &bv, const Vec3f &vel, FCL_REAL 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 = std::numeric_limits<size_t>::max() |
Protected Attributes | |
size_t | freelist |
int | max_lookahead_level |
size_t | n_leaves |
size_t | n_nodes |
size_t | n_nodes_alloc |
Node * | nodes |
unsigned int | opath |
size_t | root_node |
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, Node *&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 (Node *leaves, int n_leaves_) |
init tree from leaves in the topdown manner (topdown_0 or topdown_1) More... | |
void | init_1 (Node *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 (Node *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 (Node *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_t &split, int bits) |
size_t | mortonRecurse_1 (size_t *lbeg, size_t *lend, const uint32_t &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... | |
Class for hierarchy tree structure.
Definition at line 59 of file hierarchy_tree_array.h.
typedef NodeBase<BV> hpp::fcl::detail::implementation_array::HierarchyTree< BV >::Node |
Definition at line 61 of file hierarchy_tree_array.h.
hpp::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 55 of file hierarchy_tree_array-inl.h.
hpp::fcl::detail::implementation_array::HierarchyTree< BV >::~HierarchyTree |
Definition at line 72 of file hierarchy_tree_array-inl.h.
|
private |
Definition at line 808 of file hierarchy_tree_array-inl.h.
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::balanceBottomup |
balance the tree from bottom
Definition at line 340 of file hierarchy_tree_array-inl.h.
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::balanceIncremental | ( | int | iterations | ) |
balance the tree in an incremental way
Definition at line 386 of file hierarchy_tree_array-inl.h.
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::balanceTopdown |
balance the tree from top
Definition at line 364 of file hierarchy_tree_array-inl.h.
|
private |
construct a tree for a set of leaves from bottom – very heavy way
Definition at line 477 of file hierarchy_tree_array-inl.h.
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::clear |
Clear the tree.
Definition at line 254 of file hierarchy_tree_array-inl.h.
|
private |
Definition at line 843 of file hierarchy_tree_array-inl.h.
|
private |
create one node (leaf or internal)
Definition at line 832 of file hierarchy_tree_array-inl.h.
|
private |
Definition at line 853 of file hierarchy_tree_array-inl.h.
|
private |
Definition at line 862 of file hierarchy_tree_array-inl.h.
bool hpp::fcl::detail::implementation_array::HierarchyTree< BV >::empty |
Whether the tree is empty.
Definition at line 270 of file hierarchy_tree_array-inl.h.
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::extractLeaves | ( | size_t | root, |
Node *& | leaves | ||
) | const |
extract all the leaves of the tree
Definition at line 410 of file hierarchy_tree_array-inl.h.
|
private |
Delete all internal nodes and return all leaves nodes with given depth from root.
Definition at line 882 of file hierarchy_tree_array-inl.h.
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::getMaxDepth |
get the max depth of the tree
Definition at line 330 of file hierarchy_tree_array-inl.h.
|
private |
compute the maximum depth of a subtree rooted from a given node
Definition at line 466 of file hierarchy_tree_array-inl.h.
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::getMaxHeight |
get the max height of the tree
Definition at line 322 of file hierarchy_tree_array-inl.h.
|
private |
compute the maximum height of a subtree rooted from a given node
Definition at line 455 of file hierarchy_tree_array-inl.h.
HierarchyTree< BV >::Node * hpp::fcl::detail::implementation_array::HierarchyTree< BV >::getNodes |
get the pointer to the nodes array
Definition at line 434 of file hierarchy_tree_array-inl.h.
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::getRoot |
get the root of the tree
Definition at line 428 of file hierarchy_tree_array-inl.h.
|
private |
Definition at line 802 of file hierarchy_tree_array-inl.h.
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::init | ( | Node * | leaves, |
int | n_leaves_, | ||
int | level = 0 |
||
) |
Initialize the tree by a set of leaves using algorithm with a given level.
Definition at line 78 of file hierarchy_tree_array-inl.h.
|
private |
init tree from leaves in the topdown manner (topdown_0 or topdown_1)
Definition at line 99 of file hierarchy_tree_array-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 124 of file hierarchy_tree_array-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 162 of file hierarchy_tree_array-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 200 of file hierarchy_tree_array-inl.h.
size_t hpp::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 237 of file hierarchy_tree_array-inl.h.
|
private |
Insert a leaf node and also update its ancestors.
Definition at line 711 of file hierarchy_tree_array-inl.h.
|
private |
Definition at line 614 of file hierarchy_tree_array-inl.h.
|
private |
Definition at line 651 of file hierarchy_tree_array-inl.h.
|
private |
Definition at line 694 of file hierarchy_tree_array-inl.h.
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::print | ( | size_t | root, |
int | depth | ||
) |
print the tree in a recursive way
Definition at line 440 of file hierarchy_tree_array-inl.h.
|
private |
Definition at line 870 of file hierarchy_tree_array-inl.h.
void hpp::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 404 of file hierarchy_tree_array-inl.h.
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::remove | ( | size_t | leaf | ) |
Remove a leaf node.
Definition at line 246 of file hierarchy_tree_array-inl.h.
|
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 751 of file hierarchy_tree_array-inl.h.
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::size |
number of leaves in the tree
Definition at line 422 of file hierarchy_tree_array-inl.h.
|
private |
construct a tree for a set of leaves from top
Definition at line 509 of file hierarchy_tree_array-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 524 of file hierarchy_tree_array-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 556 of file hierarchy_tree_array-inl.h.
bool hpp::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 291 of file hierarchy_tree_array-inl.h.
bool hpp::fcl::detail::implementation_array::HierarchyTree< BV >::update | ( | size_t | leaf, |
const BV & | bv, | ||
const Vec3f & | vel | ||
) |
update one leaf's bounding volume, with prediction
Definition at line 312 of file hierarchy_tree_array-inl.h.
bool hpp::fcl::detail::implementation_array::HierarchyTree< BV >::update | ( | size_t | leaf, |
const BV & | bv, | ||
const Vec3f & | vel, | ||
FCL_REAL | margin | ||
) |
update one leaf's bounding volume, with prediction
Definition at line 299 of file hierarchy_tree_array-inl.h.
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::update | ( | size_t | leaf, |
int | lookahead_level = -1 |
||
) |
update one leaf node
Definition at line 276 of file hierarchy_tree_array-inl.h.
|
private |
update one leaf node's bounding volume
Definition at line 786 of file hierarchy_tree_array-inl.h.
int hpp::fcl::detail::implementation_array::HierarchyTree< BV >::bu_threshold |
decide the depth to use expensive bottom-up algorithm
Definition at line 261 of file hierarchy_tree_array.h.
|
protected |
Definition at line 251 of file hierarchy_tree_array.h.
|
protected |
Definition at line 254 of file hierarchy_tree_array.h.
|
protected |
Definition at line 250 of file hierarchy_tree_array.h.
|
protected |
Definition at line 247 of file hierarchy_tree_array.h.
|
protected |
Definition at line 248 of file hierarchy_tree_array.h.
|
protected |
Definition at line 246 of file hierarchy_tree_array.h.
|
static |
Definition at line 264 of file hierarchy_tree_array.h.
|
protected |
Definition at line 252 of file hierarchy_tree_array.h.
|
protected |
Definition at line 245 of file hierarchy_tree_array.h.
int hpp::fcl::detail::implementation_array::HierarchyTree< BV >::topdown_level |
decide which topdown algorithm to use
Definition at line 258 of file hierarchy_tree_array.h.