GCC Code Coverage Report | |||||||||||||||||||||
|
|||||||||||||||||||||
Line | Branch | Exec | Source |
1 |
/* |
||
2 |
* Software License Agreement (BSD License) |
||
3 |
* |
||
4 |
* Copyright (c) 2011-2014, Willow Garage, Inc. |
||
5 |
* Copyright (c) 2014-2015, 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_BV_SPLITTER_H |
||
39 |
#define HPP_FCL_BV_SPLITTER_H |
||
40 |
|||
41 |
#include <hpp/fcl/BVH/BVH_internal.h> |
||
42 |
#include <hpp/fcl/BV/kIOS.h> |
||
43 |
#include <hpp/fcl/BV/OBBRSS.h> |
||
44 |
#include <vector> |
||
45 |
#include <iostream> |
||
46 |
|||
47 |
namespace hpp { |
||
48 |
namespace fcl { |
||
49 |
|||
50 |
/// @brief Three types of split algorithms are provided in FCL as default |
||
51 |
enum SplitMethodType { |
||
52 |
SPLIT_METHOD_MEAN, |
||
53 |
SPLIT_METHOD_MEDIAN, |
||
54 |
SPLIT_METHOD_BV_CENTER |
||
55 |
}; |
||
56 |
|||
57 |
/// @brief A class describing the split rule that splits each BV node |
||
58 |
template <typename BV> |
||
59 |
class BVSplitter { |
||
60 |
public: |
||
61 |
7028 |
BVSplitter(SplitMethodType method) |
|
62 |
✓✗ | 7028 |
: split_vector(0, 0, 0), split_method(method) {} |
63 |
|||
64 |
/// @brief Default deconstructor |
||
65 |
13788 |
virtual ~BVSplitter() {} |
|
66 |
|||
67 |
/// @brief Set the geometry data needed by the split rule |
||
68 |
6338 |
void set(Vec3f* vertices_, Triangle* tri_indices_, BVHModelType type_) { |
|
69 |
6338 |
vertices = vertices_; |
|
70 |
6338 |
tri_indices = tri_indices_; |
|
71 |
6338 |
type = type_; |
|
72 |
6338 |
} |
|
73 |
|||
74 |
/// @brief Compute the split rule according to a subset of geometry and the |
||
75 |
/// corresponding BV node |
||
76 |
4487706 |
void computeRule(const BV& bv, unsigned int* primitive_indices, |
|
77 |
unsigned int num_primitives) { |
||
78 |
✓✓✓✗ |
4487706 |
switch (split_method) { |
79 |
2802958 |
case SPLIT_METHOD_MEAN: |
|
80 |
2802958 |
computeRule_mean(bv, primitive_indices, num_primitives); |
|
81 |
2802958 |
break; |
|
82 |
814496 |
case SPLIT_METHOD_MEDIAN: |
|
83 |
814496 |
computeRule_median(bv, primitive_indices, num_primitives); |
|
84 |
814496 |
break; |
|
85 |
870252 |
case SPLIT_METHOD_BV_CENTER: |
|
86 |
870252 |
computeRule_bvcenter(bv, primitive_indices, num_primitives); |
|
87 |
870252 |
break; |
|
88 |
default: |
||
89 |
std::cerr << "Split method not supported" << std::endl; |
||
90 |
} |
||
91 |
4487706 |
} |
|
92 |
|||
93 |
/// @brief Apply the split rule on a given point |
||
94 |
6132606 |
bool apply(const Vec3f& q) const { return q[split_axis] > split_value; } |
|
95 |
|||
96 |
/// @brief Clear the geometry data set before |
||
97 |
6338 |
void clear() { |
|
98 |
6338 |
vertices = NULL; |
|
99 |
6338 |
tri_indices = NULL; |
|
100 |
6338 |
type = BVH_MODEL_UNKNOWN; |
|
101 |
6338 |
} |
|
102 |
|||
103 |
protected: |
||
104 |
/// @brief The axis based on which the split decision is made. For most BV, |
||
105 |
/// the axis is aligned with one of the world coordinate, so only split_axis |
||
106 |
/// is needed. For oriented node, we can use a vector to make a better split |
||
107 |
/// decision. |
||
108 |
int split_axis; |
||
109 |
Vec3f split_vector; |
||
110 |
|||
111 |
/// @brief The split threshold, different primitives are splitted according |
||
112 |
/// whether their projection on the split_axis is larger or smaller than the |
||
113 |
/// threshold |
||
114 |
FCL_REAL split_value; |
||
115 |
|||
116 |
/// @brief The mesh vertices or points handled by the splitter |
||
117 |
Vec3f* vertices; |
||
118 |
|||
119 |
/// @brief The triangles handled by the splitter |
||
120 |
Triangle* tri_indices; |
||
121 |
|||
122 |
/// @brief Whether the geometry is mesh or point cloud |
||
123 |
BVHModelType type; |
||
124 |
|||
125 |
/// @brief The split algorithm used |
||
126 |
SplitMethodType split_method; |
||
127 |
|||
128 |
/// @brief Split algorithm 1: Split the node from center |
||
129 |
328404 |
void computeRule_bvcenter(const BV& bv, unsigned int*, unsigned int) { |
|
130 |
✓✗ | 328404 |
Vec3f center = bv.center(); |
131 |
328404 |
int axis = 2; |
|
132 |
|||
133 |
✓✗✓✗ ✓✓✓✗ ✓✗✓✓ ✓✓ |
328404 |
if (bv.width() >= bv.height() && bv.width() >= bv.depth()) |
134 |
91286 |
axis = 0; |
|
135 |
✓✗✓✗ ✓✓✓✗ ✓✗✓✓ ✓✓ |
237118 |
else if (bv.height() >= bv.width() && bv.height() >= bv.depth()) |
136 |
73150 |
axis = 1; |
|
137 |
|||
138 |
328404 |
split_axis = axis; |
|
139 |
✓✗ | 328404 |
split_value = center[axis]; |
140 |
328404 |
} |
|
141 |
|||
142 |
/// @brief Split algorithm 2: Split the node according to the mean of the data |
||
143 |
/// contained |
||
144 |
399236 |
void computeRule_mean(const BV& bv, unsigned int* primitive_indices, |
|
145 |
unsigned int num_primitives) { |
||
146 |
399236 |
int axis = 2; |
|
147 |
|||
148 |
✓✓✓✓ ✓✓ |
399236 |
if (bv.width() >= bv.height() && bv.width() >= bv.depth()) |
149 |
95332 |
axis = 0; |
|
150 |
✓✓✓✓ ✓✓ |
303904 |
else if (bv.height() >= bv.width() && bv.height() >= bv.depth()) |
151 |
78370 |
axis = 1; |
|
152 |
|||
153 |
399236 |
split_axis = axis; |
|
154 |
399236 |
FCL_REAL sum = 0; |
|
155 |
|||
156 |
✓✓ | 399236 |
if (type == BVH_MODEL_TRIANGLES) { |
157 |
✓✓ | 2894658 |
for (unsigned int i = 0; i < num_primitives; ++i) { |
158 |
2495662 |
const Triangle& t = tri_indices[primitive_indices[i]]; |
|
159 |
4991324 |
sum += (vertices[t[0]][split_axis] + vertices[t[1]][split_axis] + |
|
160 |
2495662 |
vertices[t[2]][split_axis]); |
|
161 |
} |
||
162 |
|||
163 |
398996 |
sum /= 3; |
|
164 |
✓✗ | 240 |
} else if (type == BVH_MODEL_POINTCLOUD) { |
165 |
✓✓ | 752 |
for (unsigned int i = 0; i < num_primitives; ++i) { |
166 |
512 |
sum += vertices[primitive_indices[i]][split_axis]; |
|
167 |
} |
||
168 |
} |
||
169 |
|||
170 |
399236 |
split_value = sum / num_primitives; |
|
171 |
399236 |
} |
|
172 |
|||
173 |
/// @brief Split algorithm 3: Split the node according to the median of the |
||
174 |
/// data contained |
||
175 |
328404 |
void computeRule_median(const BV& bv, unsigned int* primitive_indices, |
|
176 |
unsigned int num_primitives) { |
||
177 |
328404 |
int axis = 2; |
|
178 |
|||
179 |
✓✗✓✗ ✓✓✓✗ ✓✗✓✓ ✓✓ |
328404 |
if (bv.width() >= bv.height() && bv.width() >= bv.depth()) |
180 |
87446 |
axis = 0; |
|
181 |
✓✗✓✗ ✓✓✓✗ ✓✗✓✓ ✓✓ |
240958 |
else if (bv.height() >= bv.width() && bv.height() >= bv.depth()) |
182 |
76932 |
axis = 1; |
|
183 |
|||
184 |
328404 |
split_axis = axis; |
|
185 |
✓✗ | 656808 |
std::vector<FCL_REAL> proj((size_t)num_primitives); |
186 |
|||
187 |
✓✗ | 328404 |
if (type == BVH_MODEL_TRIANGLES) { |
188 |
✓✓ | 2301304 |
for (unsigned int i = 0; i < num_primitives; ++i) { |
189 |
1972900 |
const Triangle& t = tri_indices[primitive_indices[i]]; |
|
190 |
✓✗✓✗ ✓✗ |
3945800 |
proj[i] = (vertices[t[0]][split_axis] + vertices[t[1]][split_axis] + |
191 |
3945800 |
vertices[t[2]][split_axis]) / |
|
192 |
3; |
||
193 |
} |
||
194 |
} else if (type == BVH_MODEL_POINTCLOUD) { |
||
195 |
for (unsigned int i = 0; i < num_primitives; ++i) |
||
196 |
proj[i] = vertices[primitive_indices[i]][split_axis]; |
||
197 |
} |
||
198 |
|||
199 |
✓✗ | 328404 |
std::sort(proj.begin(), proj.end()); |
200 |
|||
201 |
✓✓ | 328404 |
if (num_primitives % 2 == 1) { |
202 |
207716 |
split_value = proj[(num_primitives - 1) / 2]; |
|
203 |
} else { |
||
204 |
120688 |
split_value = |
|
205 |
120688 |
(proj[num_primitives / 2] + proj[num_primitives / 2 - 1]) / 2; |
|
206 |
} |
||
207 |
328404 |
} |
|
208 |
}; |
||
209 |
|||
210 |
template <> |
||
211 |
bool HPP_FCL_DLLAPI BVSplitter<OBB>::apply(const Vec3f& q) const; |
||
212 |
|||
213 |
template <> |
||
214 |
bool HPP_FCL_DLLAPI BVSplitter<RSS>::apply(const Vec3f& q) const; |
||
215 |
|||
216 |
template <> |
||
217 |
bool HPP_FCL_DLLAPI BVSplitter<kIOS>::apply(const Vec3f& q) const; |
||
218 |
|||
219 |
template <> |
||
220 |
bool HPP_FCL_DLLAPI BVSplitter<OBBRSS>::apply(const Vec3f& q) const; |
||
221 |
|||
222 |
template <> |
||
223 |
void HPP_FCL_DLLAPI BVSplitter<OBB>::computeRule_bvcenter( |
||
224 |
const OBB& bv, unsigned int* primitive_indices, |
||
225 |
unsigned int num_primitives); |
||
226 |
|||
227 |
template <> |
||
228 |
void HPP_FCL_DLLAPI BVSplitter<OBB>::computeRule_mean( |
||
229 |
const OBB& bv, unsigned int* primitive_indices, |
||
230 |
unsigned int num_primitives); |
||
231 |
|||
232 |
template <> |
||
233 |
void HPP_FCL_DLLAPI BVSplitter<OBB>::computeRule_median( |
||
234 |
const OBB& bv, unsigned int* primitive_indices, |
||
235 |
unsigned int num_primitives); |
||
236 |
|||
237 |
template <> |
||
238 |
void HPP_FCL_DLLAPI BVSplitter<RSS>::computeRule_bvcenter( |
||
239 |
const RSS& bv, unsigned int* primitive_indices, |
||
240 |
unsigned int num_primitives); |
||
241 |
|||
242 |
template <> |
||
243 |
void HPP_FCL_DLLAPI BVSplitter<RSS>::computeRule_mean( |
||
244 |
const RSS& bv, unsigned int* primitive_indices, |
||
245 |
unsigned int num_primitives); |
||
246 |
|||
247 |
template <> |
||
248 |
void HPP_FCL_DLLAPI BVSplitter<RSS>::computeRule_median( |
||
249 |
const RSS& bv, unsigned int* primitive_indices, |
||
250 |
unsigned int num_primitives); |
||
251 |
|||
252 |
template <> |
||
253 |
void HPP_FCL_DLLAPI BVSplitter<kIOS>::computeRule_bvcenter( |
||
254 |
const kIOS& bv, unsigned int* primitive_indices, |
||
255 |
unsigned int num_primitives); |
||
256 |
|||
257 |
template <> |
||
258 |
void HPP_FCL_DLLAPI BVSplitter<kIOS>::computeRule_mean( |
||
259 |
const kIOS& bv, unsigned int* primitive_indices, |
||
260 |
unsigned int num_primitives); |
||
261 |
|||
262 |
template <> |
||
263 |
void HPP_FCL_DLLAPI BVSplitter<kIOS>::computeRule_median( |
||
264 |
const kIOS& bv, unsigned int* primitive_indices, |
||
265 |
unsigned int num_primitives); |
||
266 |
|||
267 |
template <> |
||
268 |
void HPP_FCL_DLLAPI BVSplitter<OBBRSS>::computeRule_bvcenter( |
||
269 |
const OBBRSS& bv, unsigned int* primitive_indices, |
||
270 |
unsigned int num_primitives); |
||
271 |
|||
272 |
template <> |
||
273 |
void HPP_FCL_DLLAPI BVSplitter<OBBRSS>::computeRule_mean( |
||
274 |
const OBBRSS& bv, unsigned int* primitive_indices, |
||
275 |
unsigned int num_primitives); |
||
276 |
|||
277 |
template <> |
||
278 |
void HPP_FCL_DLLAPI BVSplitter<OBBRSS>::computeRule_median( |
||
279 |
const OBBRSS& bv, unsigned int* primitive_indices, |
||
280 |
unsigned int num_primitives); |
||
281 |
|||
282 |
} // namespace fcl |
||
283 |
|||
284 |
} // namespace hpp |
||
285 |
|||
286 |
#endif |
Generated by: GCOVR (Version 4.2) |