Go to the documentation of this file.
38 #ifndef HPP_FCL_HIERARCHY_TREE_ARRAY_H
39 #define HPP_FCL_HIERARCHY_TREE_ARRAY_H
55 namespace implementation_array {
58 template <
typename BV>
89 HierarchyTree(
int bu_threshold_ = 16,
int topdown_level_ = 0);
95 void init(
Node* leaves,
int n_leaves_,
int level = 0);
99 size_t insert(
const BV& bv,
void* data);
111 void update(
size_t leaf,
int lookahead_level = -1);
115 bool update(
size_t leaf,
const BV& bv);
121 bool update(
size_t leaf,
const BV& bv,
const Vec3f& vel);
155 void print(
size_t root,
int depth);
159 void bottomup(
size_t* lbeg,
size_t* lend);
162 size_t topdown(
size_t* lbeg,
size_t* lend);
168 void getMaxDepth(
size_t node,
size_t depth,
size_t& max_depth)
const;
175 size_t topdown_0(
size_t* lbeg,
size_t* lend);
183 size_t topdown_1(
size_t* lbeg,
size_t* lend);
206 size_t mortonRecurse_0(
size_t* lbeg,
size_t* lend,
const uint32_t& split,
209 size_t mortonRecurse_1(
size_t* lbeg,
size_t* lend,
const uint32_t& split,
215 void update_(
size_t leaf,
const BV& bv);
234 size_t createNode(
size_t parent,
const BV& bv1,
const BV& bv2,
void* data);
236 size_t createNode(
size_t parent,
const BV& bv,
void* data);
264 static const size_t NULL_NODE = std::numeric_limits<size_t>::max();
267 template <
typename BV>
271 template <
typename BV>
287 template <
typename BV>
292 template <
typename BV>
size_t getMaxHeight() const
get the max height of the tree
Eigen::Matrix< FCL_REAL, 3, 1 > Vec3f
bool operator()(size_t a, size_t b) const
const NodeBase< BV > * nodes
the nodes array
void print(size_t root, int depth)
print the tree in a recursive way
void remove(size_t leaf)
Remove a leaf node.
size_t indexOf(size_t node)
SortByMorton(Node *nodes_in)
void init_0(Node *leaves, int n_leaves_)
init tree from leaves in the topdown manner (topdown_0 or topdown_1)
SortByMorton(Node *nodes_in, uint32_t split_in)
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...
Functor comparing two nodes.
void clear()
Clear the tree.
size_t size() const
number of leaves in the tree
void fetchLeaves(size_t root, Node *&leaves, int depth=-1)
Delete all internal nodes and return all leaves nodes with given depth from root.
size_t getRoot() const
get the root of the tree
void recurseRefit(size_t node)
void init(Node *leaves, int n_leaves_, int level=0)
Initialize the tree by a set of leaves using algorithm with a given level.
static const size_t NULL_NODE
int topdown_level
decide which topdown algorithm to use
size_t select(size_t query, size_t node1, size_t node2, NodeBase< BV > *nodes)
select the node from node1 and node2 which is close to the query-th node in the nodes....
Class for hierarchy tree structure.
size_t topdown(size_t *lbeg, size_t *lend)
construct a tree for a set of leaves from top
void update(size_t leaf, int lookahead_level=-1)
update one leaf node
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 tha...
size_t mortonRecurse_0(size_t *lbeg, size_t *lend, const uint32_t &split, int bits)
size_t getMaxDepth() const
get the max depth of the tree
void balanceIncremental(int iterations)
balance the tree in an incremental way
size_t removeLeaf(size_t leaf)
Remove a leaf. The leaf node itself is not deleted yet, but all the unnecessary internal nodes are de...
size_t createNode(size_t parent, const BV &bv1, const BV &bv2, void *data)
create one node (leaf or internal)
bool empty() const
Whether the tree is empty.
void update_(size_t leaf, const BV &bv)
update one leaf node's bounding volume
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 ...
void balanceBottomup()
balance the tree from bottom
size_t mortonRecurse_2(size_t *lbeg, size_t *lend)
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 bo...
int bu_threshold
decide the depth to use expensive bottom-up algorithm
size_t d
the dimension to compare
size_t insert(const BV &bv, void *data)
Initialize the tree by a set of leaves using algorithm with a given level.
void balanceTopdown()
balance the tree from top
bool operator()(size_t i, size_t j) const
void deleteNode(size_t node)
void bottomup(size_t *lbeg, size_t *lend)
construct a tree for a set of leaves from bottom – very heavy way
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...
nodeBaseLess(const NodeBase< BV > *nodes_, size_t d_)
void insertLeaf(size_t root, size_t leaf)
Insert a leaf node and also update its ancestors.
void refit()
refit the tree, i.e., when the leaf nodes' bounding volumes change, update the entire tree in a botto...
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 tha...
void extractLeaves(size_t root, Node *&leaves) const
extract all the leaves of the tree
size_t mortonRecurse_1(size_t *lbeg, size_t *lend, const uint32_t &split, int bits)
Node * getNodes() const
get the pointer to the nodes array
hpp-fcl
Author(s):
autogenerated on Fri Aug 2 2024 02:45:14