GCC Code Coverage Report

Directory: ./
File: src/BVH/BV_splitter.cpp
Date: 2025-04-13 14:25:19
Exec Total Coverage
Lines: 109 120 90.8%
Branches: 36 84 42.9%
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 #include "coal/internal/BV_splitter.h"
39
40 namespace coal {
41
42 template <typename BV>
43 1129992 void computeSplitVector(const BV& bv, Vec3s& split_vector) {
44
1/2
✓ Branch 2 taken 564996 times.
✗ Branch 3 not taken.
 1129992 split_vector = bv.axes.col(0);
45 1129992 }
46
47 template <>
48 138119 void computeSplitVector<kIOS>(const kIOS& bv, Vec3s& split_vector) {
49 /*
50 switch(bv.num_spheres)
51 {
52 case 1:
53 split_vector = Vec3s(1, 0, 0);
54 break;
55 case 3:
56 {
57 Vec3s v[3];
58 v[0] = bv.spheres[1].o - bv.spheres[0].o;
59 v[0].normalize();
60 generateCoordinateSystem(v[0], v[1], v[2]);
61 split_vector = v[1];
62 }
63 break;
64 case 5:
65 {
66 Vec3s v[2];
67 v[0] = bv.spheres[1].o - bv.spheres[0].o;
68 v[1] = bv.spheres[3].o - bv.spheres[0].o;
69 split_vector = v[0].cross(v[1]);
70 split_vector.normalize();
71 }
72 break;
73 default:
74 ;
75 }
76 */
77
1/2
✓ Branch 2 taken 138119 times.
✗ Branch 3 not taken.
 138119 split_vector = bv.obb.axes.col(0);
78 138119 }
79
80 template <>
81 1024786 void computeSplitVector<OBBRSS>(const OBBRSS& bv, Vec3s& split_vector) {
82
1/2
✓ Branch 2 taken 1024786 times.
✗ Branch 3 not taken.
 1024786 split_vector = bv.obb.axes.col(0);
83 1024786 }
84
85 template <typename BV>
86 541848 void computeSplitValue_bvcenter(const BV& bv, Scalar& split_value) {
87
1/2
✓ Branch 2 taken 270924 times.
✗ Branch 3 not taken.
 541848 Vec3s center = bv.center();
88
1/2
✓ Branch 1 taken 270924 times.
✗ Branch 2 not taken.
 541848 split_value = center[0];
89 541848 }
90
91 template <typename BV>
92 2427862 void computeSplitValue_mean(const BV&, Vec3s* vertices, Triangle* triangles,
93 unsigned int* primitive_indices,
94 unsigned int num_primitives, BVHModelType type,
95 const Vec3s& split_vector, Scalar& split_value) {
96
1/2
✓ Branch 0 taken 1213931 times.
✗ Branch 1 not taken.
 2427862 if (type == BVH_MODEL_TRIANGLES) {
97
2/4
✓ Branch 1 taken 1213931 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1213931 times.
✗ Branch 5 not taken.
 2427862 Vec3s c(Vec3s::Zero());
98
99
2/2
✓ Branch 0 taken 6564995 times.
✓ Branch 1 taken 1213931 times.
 15557852 for (unsigned int i = 0; i < num_primitives; ++i) {
100 13129990 const Triangle& t = triangles[primitive_indices[i]];
101 13129990 const Vec3s& p1 = vertices[t[0]];
102 13129990 const Vec3s& p2 = vertices[t[1]];
103 13129990 const Vec3s& p3 = vertices[t[2]];
104
105
3/6
✓ Branch 1 taken 6564995 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6564995 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 6564995 times.
✗ Branch 8 not taken.
 13129990 c += p1 + p2 + p3;
106 }
107
1/2
✓ Branch 1 taken 1213931 times.
✗ Branch 2 not taken.
 2427862 split_value = c.dot(split_vector) / Scalar(3 * num_primitives);
108 ✗ } else if (type == BVH_MODEL_POINTCLOUD) {
109 ✗ Scalar sum = 0;
110 ✗ for (unsigned int i = 0; i < num_primitives; ++i) {
111 ✗ const Vec3s& p = vertices[primitive_indices[i]];
112 ✗ sum += p.dot(split_vector);
113 }
114
115 ✗ split_value = sum / Scalar(num_primitives);
116 }
117 2427862 }
118
119 template <typename BV>
120 486092 void computeSplitValue_median(const BV&, Vec3s* vertices, Triangle* triangles,
121 unsigned int* primitive_indices,
122 unsigned int num_primitives, BVHModelType type,
123 const Vec3s& split_vector, Scalar& split_value) {
124
1/2
✓ Branch 2 taken 243046 times.
✗ Branch 3 not taken.
 486092 std::vector<Scalar> proj(num_primitives);
125
126
1/2
✓ Branch 0 taken 243046 times.
✗ Branch 1 not taken.
 486092 if (type == BVH_MODEL_TRIANGLES) {
127
2/2
✓ Branch 0 taken 1446441 times.
✓ Branch 1 taken 243046 times.
 3378974 for (unsigned int i = 0; i < num_primitives; ++i) {
128 2892882 const Triangle& t = triangles[primitive_indices[i]];
129 2892882 const Vec3s& p1 = vertices[t[0]];
130 2892882 const Vec3s& p2 = vertices[t[1]];
131 2892882 const Vec3s& p3 = vertices[t[2]];
132
6/12
✓ Branch 1 taken 1446441 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1446441 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1446441 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1446441 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 1446441 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 1446441 times.
✗ Branch 17 not taken.
 2892882 Vec3s centroid3(p1[0] + p2[0] + p3[0], p1[1] + p2[1] + p3[1],
133
4/8
✓ Branch 1 taken 1446441 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1446441 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1446441 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1446441 times.
✗ Branch 11 not taken.
 2892882 p1[2] + p2[2] + p3[2]);
134
135
1/2
✓ Branch 1 taken 1446441 times.
✗ Branch 2 not taken.
 2892882 proj[i] = centroid3.dot(split_vector) / 3;
136 }
137 ✗ } else if (type == BVH_MODEL_POINTCLOUD) {
138 ✗ for (unsigned int i = 0; i < num_primitives; ++i) {
139 ✗ const Vec3s& p = vertices[primitive_indices[i]];
140 ✗ Vec3s v(p[0], p[1], p[2]);
141 ✗ proj[i] = v.dot(split_vector);
142 }
143 }
144
145
1/2
✓ Branch 3 taken 243046 times.
✗ Branch 4 not taken.
 486092 std::sort(proj.begin(), proj.end());
146
147
2/2
✓ Branch 0 taken 152731 times.
✓ Branch 1 taken 90315 times.
 486092 if (num_primitives % 2 == 1) {
148 305462 split_value = proj[(num_primitives - 1) / 2];
149 } else {
150 180630 split_value = (proj[num_primitives / 2] + proj[num_primitives / 2 - 1]) / 2;
151 }
152 486092 }
153
154 template <>
155 88424 void BVSplitter<OBB>::computeRule_bvcenter(const OBB& bv, unsigned int*,
156 unsigned int) {
157 88424 computeSplitVector<OBB>(bv, split_vector);
158 88424 computeSplitValue_bvcenter<OBB>(bv, split_value);
159 88424 }
160
161 template <>
162 110639 void BVSplitter<OBB>::computeRule_mean(const OBB& bv,
163 unsigned int* primitive_indices,
164 unsigned int num_primitives) {
165 110639 computeSplitVector<OBB>(bv, split_vector);
166 110639 computeSplitValue_mean<OBB>(bv, vertices, tri_indices, primitive_indices,
167 110639 num_primitives, type, split_vector, split_value);
168 110639 }
169
170 template <>
171 88424 void BVSplitter<OBB>::computeRule_median(const OBB& bv,
172 unsigned int* primitive_indices,
173 unsigned int num_primitives) {
174 88424 computeSplitVector<OBB>(bv, split_vector);
175 88424 computeSplitValue_median<OBB>(bv, vertices, tri_indices, primitive_indices,
176 88424 num_primitives, type, split_vector,
177 88424 split_value);
178 88424 }
179
180 template <>
181 98004 void BVSplitter<RSS>::computeRule_bvcenter(const RSS& bv, unsigned int*,
182 unsigned int) {
183 98004 computeSplitVector<RSS>(bv, split_vector);
184 98004 computeSplitValue_bvcenter<RSS>(bv, split_value);
185 98004 }
186
187 template <>
188 109379 void BVSplitter<RSS>::computeRule_mean(const RSS& bv,
189 unsigned int* primitive_indices,
190 unsigned int num_primitives) {
191 109379 computeSplitVector<RSS>(bv, split_vector);
192 109379 computeSplitValue_mean<RSS>(bv, vertices, tri_indices, primitive_indices,
193 109379 num_primitives, type, split_vector, split_value);
194 109379 }
195
196 template <>
197 70126 void BVSplitter<RSS>::computeRule_median(const RSS& bv,
198 unsigned int* primitive_indices,
199 unsigned int num_primitives) {
200 70126 computeSplitVector<RSS>(bv, split_vector);
201 70126 computeSplitValue_median<RSS>(bv, vertices, tri_indices, primitive_indices,
202 70126 num_primitives, type, split_vector,
203 70126 split_value);
204 70126 }
205
206 template <>
207 42248 void BVSplitter<kIOS>::computeRule_bvcenter(const kIOS& bv, unsigned int*,
208 unsigned int) {
209 42248 computeSplitVector<kIOS>(bv, split_vector);
210 42248 computeSplitValue_bvcenter<kIOS>(bv, split_value);
211 42248 }
212
213 template <>
214 53623 void BVSplitter<kIOS>::computeRule_mean(const kIOS& bv,
215 unsigned int* primitive_indices,
216 unsigned int num_primitives) {
217 53623 computeSplitVector<kIOS>(bv, split_vector);
218 53623 computeSplitValue_mean<kIOS>(bv, vertices, tri_indices, primitive_indices,
219 53623 num_primitives, type, split_vector, split_value);
220 53623 }
221
222 template <>
223 42248 void BVSplitter<kIOS>::computeRule_median(const kIOS& bv,
224 unsigned int* primitive_indices,
225 unsigned int num_primitives) {
226 42248 computeSplitVector<kIOS>(bv, split_vector);
227 42248 computeSplitValue_median<kIOS>(bv, vertices, tri_indices, primitive_indices,
228 42248 num_primitives, type, split_vector,
229 42248 split_value);
230 42248 }
231
232 template <>
233 42248 void BVSplitter<OBBRSS>::computeRule_bvcenter(const OBBRSS& bv, unsigned int*,
234 unsigned int) {
235 42248 computeSplitVector<OBBRSS>(bv, split_vector);
236 42248 computeSplitValue_bvcenter<OBBRSS>(bv, split_value);
237 42248 }
238
239 template <>
240 940290 void BVSplitter<OBBRSS>::computeRule_mean(const OBBRSS& bv,
241 unsigned int* primitive_indices,
242 unsigned int num_primitives) {
243 940290 computeSplitVector<OBBRSS>(bv, split_vector);
244 940290 computeSplitValue_mean<OBBRSS>(bv, vertices, tri_indices, primitive_indices,
245 940290 num_primitives, type, split_vector,
246 940290 split_value);
247 940290 }
248
249 template <>
250 42248 void BVSplitter<OBBRSS>::computeRule_median(const OBBRSS& bv,
251 unsigned int* primitive_indices,
252 unsigned int num_primitives) {
253 42248 computeSplitVector<OBBRSS>(bv, split_vector);
254 42248 computeSplitValue_median<OBBRSS>(bv, vertices, tri_indices, primitive_indices,
255 42248 num_primitives, type, split_vector,
256 42248 split_value);
257 42248 }
258
259 template <>
260 1685027 bool BVSplitter<OBB>::apply(const Vec3s& q) const {
261
1/2
✓ Branch 5 taken 1685027 times.
✗ Branch 6 not taken.
 1685027 return split_vector.dot(Vec3s(q[0], q[1], q[2])) > split_value;
262 }
263
264 template <>
265 1623891 bool BVSplitter<RSS>::apply(const Vec3s& q) const {
266
1/2
✓ Branch 5 taken 1623891 times.
✗ Branch 6 not taken.
 1623891 return split_vector.dot(Vec3s(q[0], q[1], q[2])) > split_value;
267 }
268
269 template <>
270 809058 bool BVSplitter<kIOS>::apply(const Vec3s& q) const {
271
1/2
✓ Branch 5 taken 809058 times.
✗ Branch 6 not taken.
 809058 return split_vector.dot(Vec3s(q[0], q[1], q[2])) > split_value;
272 }
273
274 template <>
275 4870728 bool BVSplitter<OBBRSS>::apply(const Vec3s& q) const {
276
1/2
✓ Branch 5 taken 4870728 times.
✗ Branch 6 not taken.
 4870728 return split_vector.dot(Vec3s(q[0], q[1], q[2])) > split_value;
277 }
278
279 template class BVSplitter<RSS>;
280 template class BVSplitter<OBBRSS>;
281 template class BVSplitter<OBB>;
282 template class BVSplitter<kIOS>;
283
284 } // namespace coal
285