1 |
|
|
/* |
2 |
|
|
* Software License Agreement (BSD License) |
3 |
|
|
* |
4 |
|
|
* Copyright (c) 2011-2014, Willow Garage, Inc. |
5 |
|
|
* Copyright (c) 2014-2016, Open Source Robotics Foundation |
6 |
|
|
* All rights reserved. |
7 |
|
|
* |
8 |
|
|
* Redistribution and use in source and binary forms, with or without |
9 |
|
|
* modification, are permitted provided that the following conditions |
10 |
|
|
* are met: |
11 |
|
|
* |
12 |
|
|
* * Redistributions of source code must retain the above copyright |
13 |
|
|
* notice, this list of conditions and the following disclaimer. |
14 |
|
|
* * Redistributions in binary form must reproduce the above |
15 |
|
|
* copyright notice, this list of conditions and the following |
16 |
|
|
* disclaimer in the documentation and/or other materials provided |
17 |
|
|
* with the distribution. |
18 |
|
|
* * Neither the name of Open Source Robotics Foundation nor the names of its |
19 |
|
|
* contributors may be used to endorse or promote products derived |
20 |
|
|
* from this software without specific prior written permission. |
21 |
|
|
* |
22 |
|
|
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
23 |
|
|
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
24 |
|
|
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS |
25 |
|
|
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
26 |
|
|
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, |
27 |
|
|
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, |
28 |
|
|
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
29 |
|
|
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER |
30 |
|
|
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
31 |
|
|
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN |
32 |
|
|
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
33 |
|
|
* POSSIBILITY OF SUCH DAMAGE. |
34 |
|
|
*/ |
35 |
|
|
|
36 |
|
|
/** @author Jia Pan */ |
37 |
|
|
|
38 |
|
|
#ifndef HPP_FCL_HIERARCHY_TREE_ARRAY_H |
39 |
|
|
#define HPP_FCL_HIERARCHY_TREE_ARRAY_H |
40 |
|
|
|
41 |
|
|
#include <vector> |
42 |
|
|
#include <map> |
43 |
|
|
#include <functional> |
44 |
|
|
|
45 |
|
|
#include "hpp/fcl/fwd.hh" |
46 |
|
|
#include "hpp/fcl/BV/AABB.h" |
47 |
|
|
#include "hpp/fcl/broadphase/detail/morton.h" |
48 |
|
|
#include "hpp/fcl/broadphase/detail/node_base_array.h" |
49 |
|
|
|
50 |
|
|
namespace hpp { |
51 |
|
|
namespace fcl { |
52 |
|
|
|
53 |
|
|
namespace detail { |
54 |
|
|
|
55 |
|
|
namespace implementation_array { |
56 |
|
|
|
57 |
|
|
/// @brief Class for hierarchy tree structure |
58 |
|
|
template <typename BV> |
59 |
|
|
class HierarchyTree { |
60 |
|
|
public: |
61 |
|
|
typedef NodeBase<BV> Node; |
62 |
|
|
|
63 |
|
|
private: |
64 |
|
|
struct SortByMorton { |
65 |
|
43 |
SortByMorton(Node* nodes_in) : nodes(nodes_in) {} |
66 |
|
25000 |
SortByMorton(Node* nodes_in, uint32_t split_in) |
67 |
|
25000 |
: nodes(nodes_in), split(split_in) {} |
68 |
|
209604 |
bool operator()(size_t a, size_t b) const { |
69 |
✓✗✓✓
|
209604 |
if ((a != NULL_NODE) && (b != NULL_NODE)) |
70 |
|
153684 |
return nodes[a].code < nodes[b].code; |
71 |
✗✓ |
55920 |
else if (a == NULL_NODE) |
72 |
|
|
return split < nodes[b].code; |
73 |
✓✗ |
55920 |
else if (b == NULL_NODE) |
74 |
|
55920 |
return nodes[a].code < split; |
75 |
|
|
|
76 |
|
|
return false; |
77 |
|
|
} |
78 |
|
|
|
79 |
|
|
Node* nodes{}; |
80 |
|
|
uint32_t split{}; |
81 |
|
|
}; |
82 |
|
|
|
83 |
|
|
public: |
84 |
|
|
/// @brief Create hierarchy tree with suitable setting. |
85 |
|
|
/// bu_threshold decides the height of tree node to start bottom-up |
86 |
|
|
/// construction / optimization; topdown_level decides different methods to |
87 |
|
|
/// construct tree in topdown manner. lower level method constructs tree with |
88 |
|
|
/// better quality but is slower. |
89 |
|
|
HierarchyTree(int bu_threshold_ = 16, int topdown_level_ = 0); |
90 |
|
|
|
91 |
|
|
~HierarchyTree(); |
92 |
|
|
|
93 |
|
|
/// @brief Initialize the tree by a set of leaves using algorithm with a given |
94 |
|
|
/// level. |
95 |
|
|
void init(Node* leaves, int n_leaves_, int level = 0); |
96 |
|
|
|
97 |
|
|
/// @brief Initialize the tree by a set of leaves using algorithm with a given |
98 |
|
|
/// level. |
99 |
|
|
size_t insert(const BV& bv, void* data); |
100 |
|
|
|
101 |
|
|
/// @brief Remove a leaf node |
102 |
|
|
void remove(size_t leaf); |
103 |
|
|
|
104 |
|
|
/// @brief Clear the tree |
105 |
|
|
void clear(); |
106 |
|
|
|
107 |
|
|
/// @brief Whether the tree is empty |
108 |
|
|
bool empty() const; |
109 |
|
|
|
110 |
|
|
/// @brief update one leaf node |
111 |
|
|
void update(size_t leaf, int lookahead_level = -1); |
112 |
|
|
|
113 |
|
|
/// @brief update the tree when the bounding volume of a given leaf has |
114 |
|
|
/// changed |
115 |
|
|
bool update(size_t leaf, const BV& bv); |
116 |
|
|
|
117 |
|
|
/// @brief update one leaf's bounding volume, with prediction |
118 |
|
|
bool update(size_t leaf, const BV& bv, const Vec3f& vel, FCL_REAL margin); |
119 |
|
|
|
120 |
|
|
/// @brief update one leaf's bounding volume, with prediction |
121 |
|
|
bool update(size_t leaf, const BV& bv, const Vec3f& vel); |
122 |
|
|
|
123 |
|
|
/// @brief get the max height of the tree |
124 |
|
|
size_t getMaxHeight() const; |
125 |
|
|
|
126 |
|
|
/// @brief get the max depth of the tree |
127 |
|
|
size_t getMaxDepth() const; |
128 |
|
|
|
129 |
|
|
/// @brief balance the tree from bottom |
130 |
|
|
void balanceBottomup(); |
131 |
|
|
|
132 |
|
|
/// @brief balance the tree from top |
133 |
|
|
void balanceTopdown(); |
134 |
|
|
|
135 |
|
|
/// @brief balance the tree in an incremental way |
136 |
|
|
void balanceIncremental(int iterations); |
137 |
|
|
|
138 |
|
|
/// @brief refit the tree, i.e., when the leaf nodes' bounding volumes change, |
139 |
|
|
/// update the entire tree in a bottom-up manner |
140 |
|
|
void refit(); |
141 |
|
|
|
142 |
|
|
/// @brief extract all the leaves of the tree |
143 |
|
|
void extractLeaves(size_t root, Node*& leaves) const; |
144 |
|
|
|
145 |
|
|
/// @brief number of leaves in the tree |
146 |
|
|
size_t size() const; |
147 |
|
|
|
148 |
|
|
/// @brief get the root of the tree |
149 |
|
|
size_t getRoot() const; |
150 |
|
|
|
151 |
|
|
/// @brief get the pointer to the nodes array |
152 |
|
|
Node* getNodes() const; |
153 |
|
|
|
154 |
|
|
/// @brief print the tree in a recursive way |
155 |
|
|
void print(size_t root, int depth); |
156 |
|
|
|
157 |
|
|
private: |
158 |
|
|
/// @brief construct a tree for a set of leaves from bottom -- very heavy way |
159 |
|
|
void bottomup(size_t* lbeg, size_t* lend); |
160 |
|
|
|
161 |
|
|
/// @brief construct a tree for a set of leaves from top |
162 |
|
|
size_t topdown(size_t* lbeg, size_t* lend); |
163 |
|
|
|
164 |
|
|
/// @brief compute the maximum height of a subtree rooted from a given node |
165 |
|
|
size_t getMaxHeight(size_t node) const; |
166 |
|
|
|
167 |
|
|
/// @brief compute the maximum depth of a subtree rooted from a given node |
168 |
|
|
void getMaxDepth(size_t node, size_t depth, size_t& max_depth) const; |
169 |
|
|
|
170 |
|
|
/// @brief construct a tree from a list of nodes stored in [lbeg, lend) in a |
171 |
|
|
/// topdown manner. During construction, first compute the best split axis as |
172 |
|
|
/// the axis along with the longest AABB edge. Then compute the median of all |
173 |
|
|
/// nodes' center projection onto the axis and using it as the split |
174 |
|
|
/// threshold. |
175 |
|
|
size_t topdown_0(size_t* lbeg, size_t* lend); |
176 |
|
|
|
177 |
|
|
/// @brief construct a tree from a list of nodes stored in [lbeg, lend) in a |
178 |
|
|
/// topdown manner. During construction, first compute the best split |
179 |
|
|
/// thresholds for different axes as the average of all nodes' center. Then |
180 |
|
|
/// choose the split axis as the axis whose threshold can divide the nodes |
181 |
|
|
/// into two parts with almost similar size. This construction is more |
182 |
|
|
/// expensive then topdown_0, but also can provide tree with better quality. |
183 |
|
|
size_t topdown_1(size_t* lbeg, size_t* lend); |
184 |
|
|
|
185 |
|
|
/// @brief init tree from leaves in the topdown manner (topdown_0 or |
186 |
|
|
/// topdown_1) |
187 |
|
|
void init_0(Node* leaves, int n_leaves_); |
188 |
|
|
|
189 |
|
|
/// @brief init tree from leaves using morton code. It uses morton_0, i.e., |
190 |
|
|
/// for nodes which is of depth more than the maximum bits of the morton code, |
191 |
|
|
/// we use bottomup method to construct the subtree, which is slow but can |
192 |
|
|
/// construct tree with high quality. |
193 |
|
|
void init_1(Node* leaves, int n_leaves_); |
194 |
|
|
|
195 |
|
|
/// @brief init tree from leaves using morton code. It uses morton_0, i.e., |
196 |
|
|
/// for nodes which is of depth more than the maximum bits of the morton code, |
197 |
|
|
/// we split the leaves into two parts with the same size simply using the |
198 |
|
|
/// node index. |
199 |
|
|
void init_2(Node* leaves, int n_leaves_); |
200 |
|
|
|
201 |
|
|
/// @brief init tree from leaves using morton code. It uses morton_2, i.e., |
202 |
|
|
/// for all nodes, we simply divide the leaves into parts with the same size |
203 |
|
|
/// simply using the node index. |
204 |
|
|
void init_3(Node* leaves, int n_leaves_); |
205 |
|
|
|
206 |
|
|
size_t mortonRecurse_0(size_t* lbeg, size_t* lend, const uint32_t& split, |
207 |
|
|
int bits); |
208 |
|
|
|
209 |
|
|
size_t mortonRecurse_1(size_t* lbeg, size_t* lend, const uint32_t& split, |
210 |
|
|
int bits); |
211 |
|
|
|
212 |
|
|
size_t mortonRecurse_2(size_t* lbeg, size_t* lend); |
213 |
|
|
|
214 |
|
|
/// @brief update one leaf node's bounding volume |
215 |
|
|
void update_(size_t leaf, const BV& bv); |
216 |
|
|
|
217 |
|
|
/// @brief Insert a leaf node and also update its ancestors |
218 |
|
|
void insertLeaf(size_t root, size_t leaf); |
219 |
|
|
|
220 |
|
|
/// @brief Remove a leaf. The leaf node itself is not deleted yet, but all the |
221 |
|
|
/// unnecessary internal nodes are deleted. return the node with the smallest |
222 |
|
|
/// depth and is influenced by the remove operation |
223 |
|
|
size_t removeLeaf(size_t leaf); |
224 |
|
|
|
225 |
|
|
/// @brief Delete all internal nodes and return all leaves nodes with given |
226 |
|
|
/// depth from root |
227 |
|
|
void fetchLeaves(size_t root, Node*& leaves, int depth = -1); |
228 |
|
|
|
229 |
|
|
size_t indexOf(size_t node); |
230 |
|
|
|
231 |
|
|
size_t allocateNode(); |
232 |
|
|
|
233 |
|
|
/// @brief create one node (leaf or internal) |
234 |
|
|
size_t createNode(size_t parent, const BV& bv1, const BV& bv2, void* data); |
235 |
|
|
|
236 |
|
|
size_t createNode(size_t parent, const BV& bv, void* data); |
237 |
|
|
|
238 |
|
|
size_t createNode(size_t parent, void* data); |
239 |
|
|
|
240 |
|
|
void deleteNode(size_t node); |
241 |
|
|
|
242 |
|
|
void recurseRefit(size_t node); |
243 |
|
|
|
244 |
|
|
protected: |
245 |
|
|
size_t root_node; |
246 |
|
|
Node* nodes; |
247 |
|
|
size_t n_nodes; |
248 |
|
|
size_t n_nodes_alloc; |
249 |
|
|
|
250 |
|
|
size_t n_leaves; |
251 |
|
|
size_t freelist; |
252 |
|
|
unsigned int opath; |
253 |
|
|
|
254 |
|
|
int max_lookahead_level; |
255 |
|
|
|
256 |
|
|
public: |
257 |
|
|
/// @brief decide which topdown algorithm to use |
258 |
|
|
int topdown_level; |
259 |
|
|
|
260 |
|
|
/// @brief decide the depth to use expensive bottom-up algorithm |
261 |
|
|
int bu_threshold; |
262 |
|
|
|
263 |
|
|
public: |
264 |
|
|
static const size_t NULL_NODE = std::numeric_limits<size_t>::max(); |
265 |
|
|
}; |
266 |
|
|
|
267 |
|
|
template <typename BV> |
268 |
|
|
const size_t HierarchyTree<BV>::NULL_NODE; |
269 |
|
|
|
270 |
|
|
/// @brief Functor comparing two nodes |
271 |
|
|
template <typename BV> |
272 |
|
|
struct nodeBaseLess { |
273 |
|
|
nodeBaseLess(const NodeBase<BV>* nodes_, size_t d_); |
274 |
|
|
|
275 |
|
|
bool operator()(size_t i, size_t j) const; |
276 |
|
|
|
277 |
|
|
private: |
278 |
|
|
/// @brief the nodes array |
279 |
|
|
const NodeBase<BV>* nodes; |
280 |
|
|
|
281 |
|
|
/// @brief the dimension to compare |
282 |
|
|
size_t d; |
283 |
|
|
}; |
284 |
|
|
|
285 |
|
|
/// @brief select the node from node1 and node2 which is close to the query-th |
286 |
|
|
/// node in the nodes. 0 for node1 and 1 for node2. |
287 |
|
|
template <typename BV> |
288 |
|
|
size_t select(size_t query, size_t node1, size_t node2, NodeBase<BV>* nodes); |
289 |
|
|
|
290 |
|
|
/// @brief select the node from node1 and node2 which is close to the query |
291 |
|
|
/// AABB. 0 for node1 and 1 for node2. |
292 |
|
|
template <typename BV> |
293 |
|
|
size_t select(const BV& query, size_t node1, size_t node2, NodeBase<BV>* nodes); |
294 |
|
|
|
295 |
|
|
} // namespace implementation_array |
296 |
|
|
} // namespace detail |
297 |
|
|
} // namespace fcl |
298 |
|
|
} // namespace hpp |
299 |
|
|
|
300 |
|
|
#include "hpp/fcl/broadphase/detail/hierarchy_tree_array-inl.h" |
301 |
|
|
|
302 |
|
|
#endif |