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

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...
 
NodegetNodes () 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
 
Nodenodes
 
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...
 

Detailed Description

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

Class for hierarchy tree structure.

Definition at line 59 of file hierarchy_tree_array.h.

Member Typedef Documentation

◆ Node

template<typename BV >
typedef NodeBase<BV> hpp::fcl::detail::implementation_array::HierarchyTree< BV >::Node

Definition at line 61 of file hierarchy_tree_array.h.

Constructor & Destructor Documentation

◆ HierarchyTree()

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

◆ ~HierarchyTree()

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

Member Function Documentation

◆ allocateNode()

template<typename BV >
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::allocateNode
private

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

◆ balanceBottomup()

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

◆ balanceIncremental()

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

◆ balanceTopdown()

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

◆ bottomup()

template<typename BV >
void hpp::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 477 of file hierarchy_tree_array-inl.h.

◆ clear()

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

Clear the tree.

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

◆ createNode() [1/3]

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

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

◆ createNode() [2/3]

template<typename BV >
size_t hpp::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 832 of file hierarchy_tree_array-inl.h.

◆ createNode() [3/3]

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

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

◆ deleteNode()

template<typename BV >
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::deleteNode ( size_t  node)
private

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

◆ empty()

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

◆ extractLeaves()

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

◆ fetchLeaves()

template<typename BV >
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::fetchLeaves ( size_t  root,
Node *&  leaves,
int  depth = -1 
)
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.

◆ getMaxDepth() [1/2]

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

◆ getMaxDepth() [2/2]

template<typename BV >
void hpp::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 466 of file hierarchy_tree_array-inl.h.

◆ getMaxHeight() [1/2]

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

◆ getMaxHeight() [2/2]

template<typename BV >
size_t hpp::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 455 of file hierarchy_tree_array-inl.h.

◆ getNodes()

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

◆ getRoot()

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

◆ indexOf()

template<typename BV >
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::indexOf ( size_t  node)
private

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

◆ init()

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

◆ init_0()

template<typename BV >
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::init_0 ( Node leaves,
int  n_leaves_ 
)
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.

◆ init_1()

template<typename BV >
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::init_1 ( Node 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 124 of file hierarchy_tree_array-inl.h.

◆ init_2()

template<typename BV >
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::init_2 ( Node 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 162 of file hierarchy_tree_array-inl.h.

◆ init_3()

template<typename BV >
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::init_3 ( Node 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 200 of file hierarchy_tree_array-inl.h.

◆ insert()

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

◆ insertLeaf()

template<typename BV >
void hpp::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 711 of file hierarchy_tree_array-inl.h.

◆ mortonRecurse_0()

template<typename BV >
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::mortonRecurse_0 ( size_t *  lbeg,
size_t *  lend,
const uint32_t split,
int  bits 
)
private

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

◆ mortonRecurse_1()

template<typename BV >
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::mortonRecurse_1 ( size_t *  lbeg,
size_t *  lend,
const uint32_t split,
int  bits 
)
private

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

◆ mortonRecurse_2()

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

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

◆ print()

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

◆ recurseRefit()

template<typename BV >
void hpp::fcl::detail::implementation_array::HierarchyTree< BV >::recurseRefit ( size_t  node)
private

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

◆ refit()

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

◆ remove()

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

◆ removeLeaf()

template<typename BV >
size_t hpp::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 751 of file hierarchy_tree_array-inl.h.

◆ size()

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

◆ topdown()

template<typename BV >
size_t hpp::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 509 of file hierarchy_tree_array-inl.h.

◆ topdown_0()

template<typename BV >
size_t hpp::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 524 of file hierarchy_tree_array-inl.h.

◆ topdown_1()

template<typename BV >
size_t hpp::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 556 of file hierarchy_tree_array-inl.h.

◆ update() [1/4]

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

◆ update() [2/4]

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

◆ update() [3/4]

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

◆ update() [4/4]

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

◆ update_()

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

update one leaf node's bounding volume

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

Member Data Documentation

◆ bu_threshold

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

◆ freelist

template<typename BV >
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::freelist
protected

Definition at line 251 of file hierarchy_tree_array.h.

◆ max_lookahead_level

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

Definition at line 254 of file hierarchy_tree_array.h.

◆ n_leaves

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

Definition at line 250 of file hierarchy_tree_array.h.

◆ n_nodes

template<typename BV >
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::n_nodes
protected

Definition at line 247 of file hierarchy_tree_array.h.

◆ n_nodes_alloc

template<typename BV >
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::n_nodes_alloc
protected

Definition at line 248 of file hierarchy_tree_array.h.

◆ nodes

template<typename BV >
Node* hpp::fcl::detail::implementation_array::HierarchyTree< BV >::nodes
protected

Definition at line 246 of file hierarchy_tree_array.h.

◆ NULL_NODE

template<typename BV >
const size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::NULL_NODE = std::numeric_limits<size_t>::max()
static

Definition at line 264 of file hierarchy_tree_array.h.

◆ opath

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

Definition at line 252 of file hierarchy_tree_array.h.

◆ root_node

template<typename BV >
size_t hpp::fcl::detail::implementation_array::HierarchyTree< BV >::root_node
protected

Definition at line 245 of file hierarchy_tree_array.h.

◆ topdown_level

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


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


hpp-fcl
Author(s):
autogenerated on Fri Aug 2 2024 02:45:17