GCC Code Coverage Report

Directory: ./
File: mesh/triangle_intersection.cpp
Date: 2026-10-17 02:51:58
Exec Total Coverage
Lines: 408 448 91.1%
Functions: 22 26 84.6%
Branches: 353 689 51.2%
Line Branch Exec Source
1 /*
2 * Copyright (c) 2000-2022 Inria
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 * * Neither the name of the ALICE Project-Team nor the names of its
14 * contributors may be used to endorse or promote products derived from this
15 * software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 *
29 * Contact: Bruno Levy
30 *
31 * https://www.inria.fr/fr/bruno-levy
32 *
33 * Inria,
34 * Domaine de Voluceau,
35 * 78150 Le Chesnay - Rocquencourt
36 * FRANCE
37 *
38 */
39
40 #include <geogram/mesh/triangle_intersection.h>
41 #include <geogram/numerics/predicates.h>
42 #include <geogram/numerics/exact_geometry.h>
43 #include <geogram/basic/string.h>
44 #include <geogram/basic/geometry.h>
45 #include <geogram/basic/argused.h>
46 #include <geogram/basic/logger.h>
47 #include <geogram/basic/algorithm.h>
48
49
50 #ifdef GEO_COMPILER_CLANG
51 #pragma GCC diagnostic ignored "-Wswitch-enum"
52 #endif
53
54 // Uncomment to activate debug messages
55 //#define TT_DEBUG
56
57 namespace {
58
59 using namespace GEO;
60
61 /**
62 * \brief Internal implementation class for
63 * triangles_intersections()
64 * \details Keeps the coordinates of the 2x3
65 * vertices of the triangles and a reference
66 * to the result symbolic information
67 */
68 class TriangleTriangleIntersection {
69 public:
70
71 static constexpr int CACHE_UNINITIALIZED = -2;
72
73 ✗ TriangleTriangleIntersection(
74 const vec3& p0, const vec3& p1, const vec3& p2,
75 const vec3& q0, const vec3& q1, const vec3& q2,
76 TriangleIsects* result = nullptr
77 ✗ ) : result_(result) {
78 ✗ p_[0] = p0;
79 ✗ p_[1] = p1;
80 ✗ p_[2] = p2;
81 ✗ p_[3] = q0;
82 ✗ p_[4] = q1;
83 ✗ p_[5] = q2;
84 ✗ for(index_t i=0; i<64; ++i) {
85 ✗ o3d_cache_[i] = CACHE_UNINITIALIZED;
86 }
87 ✗ has_non_degenerate_intersection_ = false;
88 ✗ for(index_t i=0; i<6; ++i) {
89 ✗ p_index_[i] = NO_INDEX;
90 }
91 ✗ has_global_indices_ = false;
92 ✗ }
93
94 981368 TriangleTriangleIntersection(
95 const vec3& p0, const vec3& p1, const vec3& p2,
96 const vec3& q0, const vec3& q1, const vec3& q2,
97 index_t p0_index,
98 index_t p1_index,
99 index_t p2_index,
100 index_t q0_index,
101 index_t q1_index,
102 index_t q2_index,
103 TriangleIsects* result = nullptr
104
2/2
✓ Branch 1 taken 5888208 times.
✓ Branch 2 taken 981368 times.
 6869576 ) : result_(result) {
105 981368 p_[0] = p0;
106 981368 p_[1] = p1;
107 981368 p_[2] = p2;
108 981368 p_[3] = q0;
109 981368 p_[4] = q1;
110 981368 p_[5] = q2;
111
2/2
✓ Branch 0 taken 62807552 times.
✓ Branch 1 taken 981368 times.
 63788920 for(index_t i=0; i<64; ++i) {
112 62807552 o3d_cache_[i] = CACHE_UNINITIALIZED;
113 }
114 981368 has_non_degenerate_intersection_ = false;
115 981368 p_index_[0] = p0_index;
116 981368 p_index_[1] = p1_index;
117 981368 p_index_[2] = p2_index;
118 981368 p_index_[3] = q0_index;
119 981368 p_index_[4] = q1_index;
120 981368 p_index_[5] = q2_index;
121 981368 has_global_indices_ = true;
122 981368 }
123
124 981368 void compute() {
125 #ifdef TT_DEBUG
126 Logger::out("TT") << "Call compute()" << std::endl;
127 #endif
128
129
1/2
✓ Branch 0 taken 981368 times.
✗ Branch 1 not taken.
 981368 if(result_ != nullptr) {
130 981368 result_->resize(0);
131 }
132
133 // Test for degenerate triangles
134 981368 if(
135
2/4
✓ Branch 1 taken 981368 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 981368 times.
 1962736 triangle_dim(T1_RGN_P0, T1_RGN_P1, T1_RGN_P2) != 2 ||
136
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 981368 times.
 981368 triangle_dim(T2_RGN_P0, T2_RGN_P1, T2_RGN_P2) != 2
137 ) {
138 /*
139 Logger::warn("PCK")
140 << "Tri tri intersect: degenerate triangle "
141 << "(not supported)"
142 << std::endl;
143 */
144 ✗ return;
145 }
146
147
1/2
✓ Branch 0 taken 981368 times.
✗ Branch 1 not taken.
 981368 if(has_global_indices_) {
148
149 981368 index_t q_index[3] = {
150 NO_INDEX, NO_INDEX, NO_INDEX
151 };
152
153
2/2
✓ Branch 0 taken 2944104 times.
✓ Branch 1 taken 981368 times.
 3925472 for(index_t i=0; i<3; ++i) {
154
2/2
✓ Branch 0 taken 8832312 times.
✓ Branch 1 taken 2944104 times.
 11776416 for(index_t j=0; j<3; ++j) {
155
2/2
✓ Branch 0 taken 881112 times.
✓ Branch 1 taken 7951200 times.
 8832312 if(p_index_[i+3] == p_index_[j]) {
156 881112 q_index[i] = j;
157 }
158 }
159 }
160
161 // Early exit tests for configurations where 1 or 2 vertices
162 // are shared.
163 981368 int nb_shared = (
164 981368 (q_index[0] != NO_INDEX) +
165 981368 (q_index[1] != NO_INDEX) +
166 981368 (q_index[2] != NO_INDEX) ) ;
167
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 981368 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 981368 geo_debug_assert(nb_shared != 3);
168
169 // If there is a single shared vertex, early exit if non-shared
170 // edge [q1,q2] is strictly on one side of [p1,p2,p3]
171
2/2
✓ Branch 0 taken 537076 times.
✓ Branch 1 taken 444292 times.
 981368 if(nb_shared == 1) {
172 537076 int shared_q =
173
2/2
✓ Branch 0 taken 177190 times.
✓ Branch 1 taken 359886 times.
 537076 (q_index[1] != NO_INDEX) + (q_index[2] != NO_INDEX)*2;
174
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 537076 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 537076 geo_debug_assert(q_index[shared_q] != NO_INDEX);
175 537076 TriangleRegion q1 =
176 537076 TriangleRegion(T2_RGN_P0 + ((shared_q+1))%3);
177 537076 TriangleRegion q2 =
178 537076 TriangleRegion(T2_RGN_P0 + ((shared_q+2))%3);
179 TriangleRegion p1,p2,p3;
180
1/2
✓ Branch 1 taken 537076 times.
✗ Branch 2 not taken.
 537076 get_triangle_vertices(T1_RGN_T, p1,p2,p3);
181
1/2
✓ Branch 1 taken 537076 times.
✗ Branch 2 not taken.
 537076 Sign o1 = orient3d(p1,p2,p3,q1);
182
1/2
✓ Branch 1 taken 537076 times.
✗ Branch 2 not taken.
 537076 Sign o2 = orient3d(p1,p2,p3,q2);
183
2/2
✓ Branch 0 taken 447935 times.
✓ Branch 1 taken 89141 times.
 537076 if(int(o1)*int(o2) > 0) {
184 447935 return;
185 }
186 }
187
188 // If there are two shared vertices, early exit if non-shared
189 // vertex q is not on support plane of [p1,p2,p3]
190
2/2
✓ Branch 0 taken 172018 times.
✓ Branch 1 taken 361415 times.
 533433 if(nb_shared == 2) {
191 172018 int non_shared_q =
192
2/2
✓ Branch 0 taken 57957 times.
✓ Branch 1 taken 114061 times.
 172018 (q_index[1] == NO_INDEX) + (q_index[2] == NO_INDEX)*2;
193
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 172018 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 172018 geo_debug_assert(q_index[non_shared_q] == NO_INDEX);
194 172018 TriangleRegion q = TriangleRegion(T2_RGN_P0 + non_shared_q);
195 TriangleRegion p1,p2,p3;
196
1/2
✓ Branch 1 taken 172018 times.
✗ Branch 2 not taken.
 172018 get_triangle_vertices(T1_RGN_T, p1,p2,p3);
197
3/4
✓ Branch 1 taken 172018 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 160285 times.
✓ Branch 4 taken 11733 times.
 172018 if(orient3d(p1,p2,p3,q) != ZERO) {
198 160285 return;
199 }
200 }
201 }
202
203 // If T1 is strictly on one side of the supporting
204 // plane of T2, then we are sure there is no intersection
205 // and we can stop there.
206 {
207 TriangleRegion p1,p2,p3;
208 TriangleRegion q1,q2,q3;
209
1/2
✓ Branch 1 taken 373148 times.
✗ Branch 2 not taken.
 373148 get_triangle_vertices(T1_RGN_T, p1,p2,p3);
210
1/2
✓ Branch 1 taken 373148 times.
✗ Branch 2 not taken.
 373148 get_triangle_vertices(T2_RGN_T, q1,q2,q3);
211
1/2
✓ Branch 1 taken 373148 times.
✗ Branch 2 not taken.
 373148 Sign o1 = orient3d(q1,q2,q3,p1);
212
1/2
✓ Branch 1 taken 373148 times.
✗ Branch 2 not taken.
 373148 Sign o2 = orient3d(q1,q2,q3,p2);
213
1/2
✓ Branch 1 taken 373148 times.
✗ Branch 2 not taken.
 373148 Sign o3 = orient3d(q1,q2,q3,p3);
214 373148 if(
215
2/2
✓ Branch 0 taken 133028 times.
✓ Branch 1 taken 240120 times.
 373148 int(o1)*int(o2) == 1 &&
216
2/2
✓ Branch 0 taken 87885 times.
✓ Branch 1 taken 45143 times.
 133028 int(o2)*int(o3) == 1 &&
217
1/2
✓ Branch 0 taken 87885 times.
✗ Branch 1 not taken.
 87885 int(o3)*int(o1) == 1
218 ) {
219 87885 return;
220 }
221 }
222
223 285263 intersect_edge_triangle(T1_RGN_E0, T2_RGN_T);
224
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 285263 times.
 285263 if(finished()) { return; }
225 285263 intersect_edge_triangle(T1_RGN_E1, T2_RGN_T);
226
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 285263 times.
 285263 if(finished()) { return; }
227 285263 intersect_edge_triangle(T1_RGN_E2, T2_RGN_T);
228
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 285263 times.
 285263 if(finished()) { return; }
229
230 285263 intersect_edge_triangle(T2_RGN_E0, T1_RGN_T);
231
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 285263 times.
 285263 if(finished()) { return; }
232 285263 intersect_edge_triangle(T2_RGN_E1, T1_RGN_T);
233
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 285263 times.
 285263 if(finished()) { return; }
234 285263 intersect_edge_triangle(T2_RGN_E2, T1_RGN_T);
235
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 285263 times.
 285263 if(finished()) { return; }
236
237 // The same intersection can appear several times,
238 // remove the duplicates
239
1/2
✓ Branch 0 taken 285263 times.
✗ Branch 1 not taken.
 285263 if(result_ != nullptr) {
240 285263 std::sort(result_->begin(), result_->end());
241 285263 auto p = std::unique(result_->begin(), result_->end());
242 285263 result_->resize(index_t(p - result_->begin()));
243 // sort_unique(*result_); // HERE
244 #ifdef TT_DEBUG
245 std::string message;
246 for(TriangleIsect I: *result_) {
247 message += (" " + String::to_string(I));
248 }
249 Logger::out("II") << "result: " << message << std::endl;
250 #endif
251 }
252 }
253
254 /**
255 * \brief Tests if there as a non-degenerate intersection
256 * \retval true if an intersection different from two colocated
257 * vertices was found.
258 * \retval false otherwise.
259 */
260 981368 bool has_non_degenerate_intersection() const {
261 981368 return has_non_degenerate_intersection_;
262 }
263
264 protected:
265
266 /**
267 * \brief Tests whether computation is finished
268 * \details If we just want to know whether there is an intersection
269 * then we can stop sooner.
270 */
271 3416286 bool finished() const {
272 #ifdef TT_DEBUG
273 return false;
274 #endif
275
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 3416286 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 3416286 return (result_ == nullptr && has_non_degenerate_intersection_);
276 }
277
278 1711578 void intersect_edge_triangle(TriangleRegion E, TriangleRegion T) {
279
280 #ifdef TT_DEBUG
281 Logger::out("TT") << std::endl;
282 Logger::out("TT") << " ET " << std::make_pair(E,T) << std::endl;
283 #endif
284
285
2/8
✓ Branch 1 taken 1711578 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1711578 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 1711578 geo_debug_assert(region_dim(E) == 1);
286
2/8
✓ Branch 1 taken 1711578 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1711578 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 1711578 geo_debug_assert(region_dim(T) == 2);
287
288 1711578 TriangleRegion R1 = E;
289 1711578 TriangleRegion R2 = T;
290
291 TriangleRegion p1,p2,p3;
292 TriangleRegion e1,e2,e3;
293 TriangleRegion q1,q2;
294
295
1/2
✓ Branch 1 taken 1711578 times.
✗ Branch 2 not taken.
 1711578 get_triangle_vertices(T,p1,p2,p3);
296
1/2
✓ Branch 1 taken 1711578 times.
✗ Branch 2 not taken.
 1711578 get_triangle_edges(T,e1,e2,e3);
297
1/2
✓ Branch 1 taken 1711578 times.
✗ Branch 2 not taken.
 1711578 get_edge_vertices(E,q1,q2);
298
299
1/2
✓ Branch 1 taken 1711578 times.
✗ Branch 2 not taken.
 1711578 Sign o1 = orient3d(p1,p2,p3,q1);
300
1/2
✓ Branch 1 taken 1711578 times.
✗ Branch 2 not taken.
 1711578 Sign o2 = orient3d(p1,p2,p3,q2);
301
302 // If both extremities of the segment on same side of triangle
303 // plane, then we are sure there is no intersection and we can
304 // stop there.
305
2/2
✓ Branch 0 taken 342859 times.
✓ Branch 1 taken 1368719 times.
 1711578 if(int(o1) * int(o2) == 1) {
306 632456 return;
307 }
308
309
4/4
✓ Branch 0 taken 805944 times.
✓ Branch 1 taken 562775 times.
✓ Branch 2 taken 562696 times.
✓ Branch 3 taken 243248 times.
 1368719 if(o1 == 0 && o2 == 0) {
310 #ifdef TT_DEBUG
311 Logger::out("TT") << " ET coplanar" << std::endl;
312 #endif
313 // Special case: triangle and segment are co-planar
314
1/2
✓ Branch 1 taken 562696 times.
✗ Branch 2 not taken.
 562696 index_t nax = normal_axis(p1,p2,p3);
315
316 // Test whether the extremities of the segment
317 // are in the triangle
318 {
319
1/2
✓ Branch 1 taken 562696 times.
✗ Branch 2 not taken.
 562696 Sign a1 = orient2d(q1,p1,p2,nax);
320
1/2
✓ Branch 1 taken 562696 times.
✗ Branch 2 not taken.
 562696 Sign a2 = orient2d(q1,p2,p3,nax);
321
1/2
✓ Branch 1 taken 562696 times.
✗ Branch 2 not taken.
 562696 Sign a3 = orient2d(q1,p3,p1,nax);
322
323
1/2
✓ Branch 1 taken 562696 times.
✗ Branch 2 not taken.
 562696 Sign b1 = orient2d(q2,p1,p2,nax);
324
1/2
✓ Branch 1 taken 562696 times.
✗ Branch 2 not taken.
 562696 Sign b2 = orient2d(q2,p2,p3,nax);
325
1/2
✓ Branch 1 taken 562696 times.
✗ Branch 2 not taken.
 562696 Sign b3 = orient2d(q2,p3,p1,nax);
326
327 562696 if(
328
2/2
✓ Branch 0 taken 118502 times.
✓ Branch 1 taken 444194 times.
 562696 int(a1)*int(a2) > 0 &&
329
2/2
✓ Branch 0 taken 8310 times.
✓ Branch 1 taken 110192 times.
 118502 int(a2)*int(a3) > 0 &&
330
1/2
✓ Branch 0 taken 8310 times.
✗ Branch 1 not taken.
 8310 int(a3)*int(a1) > 0
331 ) {
332
1/2
✓ Branch 1 taken 8310 times.
✗ Branch 2 not taken.
 8310 add_intersection(q1,T);
333
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 8310 times.
 8310 if(finished()) { return; }
334 }
335
336 562696 if(
337
2/2
✓ Branch 0 taken 117697 times.
✓ Branch 1 taken 444999 times.
 562696 int(b1)*int(b2) > 0 &&
338
2/2
✓ Branch 0 taken 8310 times.
✓ Branch 1 taken 109387 times.
 117697 int(b2)*int(b3) > 0 &&
339
1/2
✓ Branch 0 taken 8310 times.
✗ Branch 1 not taken.
 8310 int(b3)*int(b1) > 0
340 ) {
341
1/2
✓ Branch 1 taken 8310 times.
✗ Branch 2 not taken.
 8310 add_intersection(q2,T);
342
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 8310 times.
 8310 if(finished()) { return; }
343 }
344 }
345
346
1/2
✓ Branch 1 taken 562696 times.
✗ Branch 2 not taken.
 562696 intersect_edge_edge_2d(E,e1,nax);
347
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 562696 times.
 562696 if(finished()) { return; }
348
1/2
✓ Branch 1 taken 562696 times.
✗ Branch 2 not taken.
 562696 intersect_edge_edge_2d(E,e2,nax);
349
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 562696 times.
 562696 if(finished()) { return; }
350
1/2
✓ Branch 1 taken 562696 times.
✗ Branch 2 not taken.
 562696 intersect_edge_edge_2d(E,e3,nax);
351
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 562696 times.
 562696 if(finished()) { return; }
352
353 562696 } else {
354
355
356 // Update symbolic information of segment
357 // if one of the segment vertices is on
358 // the triangle's supporting plane.
359
360
2/2
✓ Branch 0 taken 243248 times.
✓ Branch 1 taken 562775 times.
 806023 if(o1 == ZERO) {
361 243248 R1 = q1;
362
2/2
✓ Branch 0 taken 243248 times.
✓ Branch 1 taken 319527 times.
 562775 } else if(o2 == ZERO) {
363 243248 R1 = q2;
364 }
365
366
1/2
✓ Branch 1 taken 806023 times.
✗ Branch 2 not taken.
 806023 Sign oo1 = orient3d(p2,p3,q1,q2);
367
1/2
✓ Branch 1 taken 806023 times.
✗ Branch 2 not taken.
 806023 Sign oo2 = orient3d(p3,p1,q1,q2);
368
369
2/2
✓ Branch 0 taken 289597 times.
✓ Branch 1 taken 516426 times.
 806023 if(int(oo1)*int(oo2) == -1) {
370 289597 return;
371 }
372
373
1/2
✓ Branch 1 taken 516426 times.
✗ Branch 2 not taken.
 516426 Sign oo3 = orient3d(p1,p2,q1,q2);
374
375 // Update symbolic information of triangle
376 // if intersection is
377 // on a vertex or on an edge
378 516426 int nb_zeros = (oo1 == ZERO) + (oo2 == ZERO) + (oo3 == ZERO);
379
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 516426 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 516426 geo_debug_assert(nb_zeros != 3);
380
2/2
✓ Branch 0 taken 45465 times.
✓ Branch 1 taken 470961 times.
 516426 if(nb_zeros == 1) {
381
2/2
✓ Branch 0 taken 22304 times.
✓ Branch 1 taken 23161 times.
 45465 if(oo1 == ZERO) {
382 22304 R2 = e1;
383
2/2
✓ Branch 0 taken 18943 times.
✓ Branch 1 taken 4218 times.
 23161 } else if(oo2 == ZERO) {
384 18943 R2 = e2;
385 } else {
386 4218 R2 = e3;
387 }
388
2/2
✓ Branch 0 taken 267296 times.
✓ Branch 1 taken 203665 times.
 470961 } else if(nb_zeros == 2) {
389
2/2
✓ Branch 0 taken 84799 times.
✓ Branch 1 taken 182497 times.
 267296 if(oo1 != ZERO) {
390 84799 R2 = p1;
391
2/2
✓ Branch 0 taken 87598 times.
✓ Branch 1 taken 94899 times.
 182497 } else if(oo2 != ZERO) {
392 87598 R2 = p2;
393 } else {
394 94899 R2 = p3;
395 }
396 }
397
398 #ifdef TT_DEBUG
399 Logger::out("TT") << o1 << " " << o2
400 << " "
401 << oo1 << " " << oo2 << " " << oo3
402 << std::endl;
403 #endif
404 // Intersection is outside triangle if oo1, oo2 and oo3
405 // do not have the same sign (or zero)
406 516426 bool outside =
407 1032852 (int(oo1) * int(oo2) == -1) ||
408
3/4
✓ Branch 0 taken 516426 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 334523 times.
✓ Branch 3 taken 181903 times.
 850949 (int(oo2) * int(oo3) == -1) ||
409
2/2
✓ Branch 0 taken 13433 times.
✓ Branch 1 taken 321090 times.
 334523 (int(oo3) * int(oo1) == -1) ;
410
411
2/2
✓ Branch 0 taken 321090 times.
✓ Branch 1 taken 195336 times.
 516426 if(!outside) {
412
1/2
✓ Branch 1 taken 321090 times.
✗ Branch 2 not taken.
 321090 add_intersection(R1,R2);
413 }
414 }
415 }
416
417
418 1688088 void intersect_edge_edge_2d(
419 TriangleRegion E1, TriangleRegion E2, index_t nax
420 ) {
421 #ifdef TT_DEBUG
422 Logger::out("TT") << " EE 2d " << std::make_pair(E1,E2)
423 << " axis: " << nax << std::endl;
424 #endif
425
2/8
✓ Branch 1 taken 1688088 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1688088 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 1688088 geo_debug_assert(region_dim(E1) == 1);
426
2/8
✓ Branch 1 taken 1688088 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1688088 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 1688088 geo_debug_assert(region_dim(E2) == 1);
427
428 1688088 TriangleRegion R1 = E1;
429 1688088 TriangleRegion R2 = E2;
430
431 TriangleRegion p1,p2;
432
1/2
✓ Branch 1 taken 1688088 times.
✗ Branch 2 not taken.
 1688088 get_edge_vertices(E1,p1,p2);
433
434 TriangleRegion q1,q2;
435
1/2
✓ Branch 1 taken 1688088 times.
✗ Branch 2 not taken.
 1688088 get_edge_vertices(E2,q1,q2);
436
437
1/2
✓ Branch 1 taken 1688088 times.
✗ Branch 2 not taken.
 1688088 Sign a1 = orient2d(q1,q2,p1,nax);
438
1/2
✓ Branch 1 taken 1688088 times.
✗ Branch 2 not taken.
 1688088 Sign a2 = orient2d(q1,q2,p2,nax);
439
440
4/4
✓ Branch 0 taken 204443 times.
✓ Branch 1 taken 1483645 times.
✓ Branch 2 taken 36298 times.
✓ Branch 3 taken 168145 times.
 1688088 if(a1 == ZERO && a2 == ZERO) {
441 // Special case: 1D
442 // (the 2x2 edge extremities are aligned)
443
1/2
✓ Branch 1 taken 36298 times.
✗ Branch 2 not taken.
 36298 intersect_edge_edge_1d(E1,E2);
444 } else {
445 // Update symbolic information if one of E1's vertices is
446 // on the supporting line of E2
447
2/2
✓ Branch 0 taken 168145 times.
✓ Branch 1 taken 1483645 times.
 1651790 if(a1 == ZERO) {
448 168145 R1 = p1;
449
2/2
✓ Branch 0 taken 168313 times.
✓ Branch 1 taken 1315332 times.
 1483645 } else if(a2 == ZERO) {
450 168313 R1 = p2;
451 }
452
453
1/2
✓ Branch 1 taken 1651790 times.
✗ Branch 2 not taken.
 1651790 Sign b1 = orient2d(p1,p2,q1,nax);
454
1/2
✓ Branch 1 taken 1651790 times.
✗ Branch 2 not taken.
 1651790 Sign b2 = orient2d(p1,p2,q2,nax);
455
456 // Update symbolic information if one of E2's vertices is
457 // on the supporting line of E1
458
2/2
✓ Branch 0 taken 177629 times.
✓ Branch 1 taken 1474161 times.
 1651790 if(b1 == ZERO) {
459 177629 R2 = q1;
460
2/2
✓ Branch 0 taken 177629 times.
✓ Branch 1 taken 1296532 times.
 1474161 } else if(b2 == ZERO) {
461 177629 R2 = q2;
462 }
463
464
4/4
✓ Branch 0 taken 512468 times.
✓ Branch 1 taken 1139322 times.
✓ Branch 2 taken 396298 times.
✓ Branch 3 taken 116170 times.
 1651790 if( int(a1)*int(a2) != 1 && int(b1)*int(b2) != 1) {
465
1/2
✓ Branch 1 taken 396298 times.
✗ Branch 2 not taken.
 396298 add_intersection(R1,R2);
466 }
467 }
468 1688088 }
469
470 36298 void intersect_edge_edge_1d(
471 TriangleRegion E1, TriangleRegion E2
472 ) {
473 #ifdef TT_DEBUG
474 Logger::out("TT") << " EE 1d " << std::make_pair(E1,E2)
475 << std::endl;
476 #endif
477
2/8
✓ Branch 1 taken 36298 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 36298 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 36298 geo_debug_assert(region_dim(E1) == 1);
478
2/8
✓ Branch 1 taken 36298 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 36298 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 36298 geo_debug_assert(region_dim(E2) == 1);
479
480 TriangleRegion p1,p2;
481
1/2
✓ Branch 1 taken 36298 times.
✗ Branch 2 not taken.
 36298 get_edge_vertices(E1,p1,p2);
482
483 TriangleRegion q1,q2;
484
1/2
✓ Branch 1 taken 36298 times.
✗ Branch 2 not taken.
 36298 get_edge_vertices(E2,q1,q2);
485
486
1/2
✓ Branch 1 taken 36298 times.
✗ Branch 2 not taken.
 36298 Sign d1 = dot3d(p1,q1,q2);
487
1/2
✓ Branch 1 taken 36298 times.
✗ Branch 2 not taken.
 36298 Sign d2 = dot3d(p2,q1,q2);
488
1/2
✓ Branch 1 taken 36298 times.
✗ Branch 2 not taken.
 36298 Sign d3 = dot3d(q1,p1,p2);
489
1/2
✓ Branch 1 taken 36298 times.
✗ Branch 2 not taken.
 36298 Sign d4 = dot3d(q2,p1,p2);
490
491 // Test for identical vertices
492 // (small optimization, each time there is an identical pair
493 // of points, the two dot3d predicates they participiate to
494 // should return ZERO, so we can filter)
495
496
9/10
✓ Branch 0 taken 26259 times.
✓ Branch 1 taken 10039 times.
✓ Branch 2 taken 24862 times.
✓ Branch 3 taken 1397 times.
✓ Branch 5 taken 24862 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1456 times.
✓ Branch 8 taken 23406 times.
✓ Branch 9 taken 1456 times.
✓ Branch 10 taken 34842 times.
 36298 if(d1 == ZERO && d3 == ZERO && points_are_identical(p1,q1)) {
497
1/2
✓ Branch 1 taken 1456 times.
✗ Branch 2 not taken.
 1456 add_intersection(p1,q1);
498 }
499
500
9/10
✓ Branch 0 taken 26261 times.
✓ Branch 1 taken 10037 times.
✓ Branch 2 taken 24863 times.
✓ Branch 3 taken 1398 times.
✓ Branch 5 taken 24863 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 24803 times.
✓ Branch 8 taken 60 times.
✓ Branch 9 taken 24803 times.
✓ Branch 10 taken 11495 times.
 36298 if(d2 == ZERO && d3 == ZERO && points_are_identical(p2,q1)) {
501
1/2
✓ Branch 1 taken 24803 times.
✗ Branch 2 not taken.
 24803 add_intersection(p2,q1);
502 }
503
504
9/10
✓ Branch 0 taken 26259 times.
✓ Branch 1 taken 10039 times.
✓ Branch 2 taken 24863 times.
✓ Branch 3 taken 1396 times.
✓ Branch 5 taken 24863 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 24803 times.
✓ Branch 8 taken 60 times.
✓ Branch 9 taken 24803 times.
✓ Branch 10 taken 11495 times.
 36298 if(d1 == ZERO && d4 == ZERO && points_are_identical(p1,q2)) {
505
1/2
✓ Branch 1 taken 24803 times.
✗ Branch 2 not taken.
 24803 add_intersection(p1,q2);
506 }
507
508
9/10
✓ Branch 0 taken 26261 times.
✓ Branch 1 taken 10037 times.
✓ Branch 2 taken 24864 times.
✓ Branch 3 taken 1397 times.
✓ Branch 5 taken 24864 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1458 times.
✓ Branch 8 taken 23406 times.
✓ Branch 9 taken 1458 times.
✓ Branch 10 taken 34840 times.
 36298 if(d2 == ZERO && d4 == ZERO && points_are_identical(p2,q2)) {
509
1/2
✓ Branch 1 taken 1458 times.
✗ Branch 2 not taken.
 1458 add_intersection(p2,q2);
510 }
511
512 // Test for point in segment:
513 // c is in segment [a,b] if (c-a).(c-b) < 0
514
515
2/2
✓ Branch 0 taken 178 times.
✓ Branch 1 taken 36120 times.
 36298 if(d1 == NEGATIVE) {
516
1/2
✓ Branch 1 taken 178 times.
✗ Branch 2 not taken.
 178 add_intersection(p1,E2);
517 }
518
519
2/2
✓ Branch 0 taken 178 times.
✓ Branch 1 taken 36120 times.
 36298 if(d2 == NEGATIVE) {
520
1/2
✓ Branch 1 taken 178 times.
✗ Branch 2 not taken.
 178 add_intersection(p2,E2);
521 }
522
523
2/2
✓ Branch 0 taken 178 times.
✓ Branch 1 taken 36120 times.
 36298 if(d3 == NEGATIVE) {
524
1/2
✓ Branch 1 taken 178 times.
✗ Branch 2 not taken.
 178 add_intersection(E1,q1);
525 }
526
527
2/2
✓ Branch 0 taken 178 times.
✓ Branch 1 taken 36120 times.
 36298 if(d4 == NEGATIVE) {
528
1/2
✓ Branch 1 taken 178 times.
✗ Branch 2 not taken.
 178 add_intersection(E1,q2);
529 }
530 36298 }
531
532 787240 void add_intersection(TriangleRegion R1, TriangleRegion R2) {
533 #ifdef TT_DEBUG
534 Logger::out("TT") << " ==>I: " << std::make_pair(R1,R2)
535 << std::endl;
536 #endif
537
6/6
✓ Branch 1 taken 665850 times.
✓ Branch 2 taken 121390 times.
✓ Branch 4 taken 31586 times.
✓ Branch 5 taken 634264 times.
✓ Branch 6 taken 152976 times.
✓ Branch 7 taken 634264 times.
 787240 if(region_dim(R1) >= 1 || region_dim(R2) >= 1) {
538 152976 has_non_degenerate_intersection_ = true;
539 }
540
2/2
✓ Branch 1 taken 381524 times.
✓ Branch 2 taken 405716 times.
 787240 if(is_in_T1(R1)) {
541
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 381524 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 381524 geo_debug_assert(!is_in_T1(R2));
542
1/2
✓ Branch 0 taken 381524 times.
✗ Branch 1 not taken.
 381524 if(result_ != nullptr) {
543
2/4
✓ Branch 1 taken 381524 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 381524 times.
✗ Branch 5 not taken.
 381524 result_->push_back(std::make_pair(R1,R2));
544 }
545 } else {
546
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 405716 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 405716 geo_debug_assert(is_in_T1(R2));
547
1/2
✓ Branch 0 taken 405716 times.
✗ Branch 1 not taken.
 405716 if(result_ != nullptr) {
548
2/4
✓ Branch 1 taken 405716 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 405716 times.
✗ Branch 5 not taken.
 405716 result_->push_back(std::make_pair(R2,R1));
549 }
550 }
551 787240 }
552
553 7917242 Sign orient3d(
554 TriangleRegion i, TriangleRegion j,
555 TriangleRegion k, TriangleRegion l
556 ) const {
557
558
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 7917242 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 7917242 geo_debug_assert(region_dim(i) == 0);
559
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 7917242 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 7917242 geo_debug_assert(region_dim(j) == 0);
560
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 7917242 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 7917242 geo_debug_assert(region_dim(k) == 0);
561
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 7917242 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 7917242 geo_debug_assert(region_dim(l) == 0);
562
563 // Index for the cache (1 bit set for
564 // each vertex)
565
566 7917242 index_t o3d_idx =
567 7917242 (1u << index_t(i)) |
568 7917242 (1u << index_t(j)) |
569 7917242 (1u << index_t(k)) |
570 7917242 (1u << index_t(l)) ;
571
572
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 7917242 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 7917242 geo_debug_assert(o3d_idx < 64);
573
574 // Result of the predicate should be flipped if the
575 // order of the arguments is permutted by an odd permutation
576
577 7917242 bool flip = odd_order(index_t(i),index_t(j),index_t(k),index_t(l));
578
579 // If cache not initialized, set cache value
580
581
2/2
✓ Branch 0 taken 4471998 times.
✓ Branch 1 taken 3445244 times.
 7917242 if(o3d_cache_[o3d_idx] == CACHE_UNINITIALIZED) {
582
2/2
✓ Branch 0 taken 1777291 times.
✓ Branch 1 taken 2694707 times.
 4471998 int o = flip ? -int(PCK::orient_3d(p_[i],p_[j],p_[k],p_[l])) :
583 4471998 int(PCK::orient_3d(p_[i],p_[j],p_[k],p_[l])) ;
584 4471998 o3d_cache_[o3d_idx] = Numeric::int8(o);
585 }
586
587 // Get result from the cache
588
589
2/2
✓ Branch 0 taken 3802664 times.
✓ Branch 1 taken 4114578 times.
 7917242 Sign result = flip ? Sign(-o3d_cache_[o3d_idx])
590 4114578 : Sign( o3d_cache_[o3d_idx]);
591
592 // Sanity check: did our cache return the same result as
593 // directly calling the predicate ?
594
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 7917242 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 7917242 geo_debug_assert(
595 result == PCK::orient_3d(p_[i], p_[j], p_[k], p_[l])
596 );
597
598 7917242 return result;
599 }
600
601 /**
602 * \brief Tests the parity of the permutation of a list of
603 * four distinct indices with respect to the canonical order.
604 */
605 7917242 static bool odd_order(index_t i, index_t j, index_t k, index_t l) {
606 // Implementation: sort the elements (bubble sort is OK for
607 // such a small number), and invert parity each time
608 // two elements are swapped.
609 7917242 index_t tab[4] = { i, j, k, l };
610 7917242 constexpr int N = 4;
611 7917242 bool result = false;
612
2/2
✓ Branch 0 taken 23751726 times.
✓ Branch 1 taken 7917242 times.
 31668968 for (int I = 0; I < N - 1; ++I) {
613
2/2
✓ Branch 0 taken 47503452 times.
✓ Branch 1 taken 23751726 times.
 71255178 for (int J = 0; J < N - I - 1; ++J) {
614
2/2
✓ Branch 0 taken 14427880 times.
✓ Branch 1 taken 33075572 times.
 47503452 if (tab[J] > tab[J + 1]) {
615 14427880 std::swap(tab[J], tab[J + 1]);
616 14427880 result = !result;
617 }
618 }
619 }
620 7917242 return result;
621 }
622
623 10055932 Sign orient2d(
624 TriangleRegion i, TriangleRegion j, TriangleRegion k,
625 index_t normal_axis
626 ) const {
627 // Note: no cache for orient2d (tested, did not bring
628 // any performance gain).
629
2/8
✓ Branch 1 taken 10055932 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 10055932 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 10055932 geo_debug_assert(region_dim(i) == 0);
630
2/8
✓ Branch 1 taken 10055932 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 10055932 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 10055932 geo_debug_assert(region_dim(j) == 0);
631
2/8
✓ Branch 1 taken 10055932 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 10055932 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 10055932 geo_debug_assert(region_dim(k) == 0);
632 double pi[2];
633 double pj[2];
634 double pk[2];
635
2/2
✓ Branch 0 taken 20111864 times.
✓ Branch 1 taken 10055932 times.
 30167796 for(coord_index_t c = 0; c < 2; c++) {
636
1/2
✓ Branch 1 taken 20111864 times.
✗ Branch 2 not taken.
 20111864 pi[c] = p_[i][index_t((normal_axis + 1 + c) % 3)];
637
1/2
✓ Branch 1 taken 20111864 times.
✗ Branch 2 not taken.
 20111864 pj[c] = p_[j][index_t((normal_axis + 1 + c) % 3)];
638
1/2
✓ Branch 1 taken 20111864 times.
✗ Branch 2 not taken.
 20111864 pk[c] = p_[k][index_t((normal_axis + 1 + c) % 3)];
639 }
640
1/2
✓ Branch 1 taken 10055932 times.
✗ Branch 2 not taken.
 20111864 return PCK::orient_2d(pi,pj,pk);
641 }
642
643 /**
644 * \brief Computes the dot product between two vectors supported
645 * by three points.
646 * \param[in] i , j , k the three points
647 * \return sign(dot(pj-pi,pk-pi))
648 */
649 145192 Sign dot3d(
650 TriangleRegion i, TriangleRegion j, TriangleRegion k
651 ) const {
652
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 145192 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 145192 geo_debug_assert(region_dim(i) == 0);
653
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 145192 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 145192 geo_debug_assert(region_dim(j) == 0);
654
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 145192 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 145192 geo_debug_assert(region_dim(k) == 0);
655 145192 return PCK::dot_3d(p_[i].data(), p_[j].data(), p_[k].data());
656 }
657
658
659 /**
660 * \brief Computes the coordinate along which a triangle can be
661 * projected without introducting degeneracies.
662 * \param[in] v1 , v2 , v3 the three vertices of the triangle
663 * \return the coordinate to be used for 2d computations (0,1 or 2)
664 */
665 562696 coord_index_t normal_axis(
666 TriangleRegion v1, TriangleRegion v2, TriangleRegion v3
667 ) {
668
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 562696 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 562696 geo_debug_assert(region_dim(v1) == 0);
669
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 562696 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 562696 geo_debug_assert(region_dim(v2) == 0);
670
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 562696 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 562696 geo_debug_assert(region_dim(v3) == 0);
671
672 562696 const vec3& p1 = p_[v1];
673 562696 const vec3& p2 = p_[v2];
674 562696 const vec3& p3 = p_[v3];
675
676 562696 return PCK::triangle_normal_axis(p1,p2,p3);
677 }
678
679
680 99452 bool points_are_identical(TriangleRegion i, TriangleRegion j) {
681
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 99452 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 99452 geo_debug_assert(region_dim(i) == 0);
682
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 99452 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 99452 geo_debug_assert(region_dim(j) == 0);
683 99452 const vec3& p1 = p_[i];
684 99452 const vec3& p2 = p_[j];
685 return
686 99452 (p1[0] == p2[0]) &&
687
4/4
✓ Branch 0 taken 61652 times.
✓ Branch 1 taken 37800 times.
✓ Branch 4 taken 54440 times.
✓ Branch 5 taken 7212 times.
 153892 (p1[1] == p2[1]) &&
688
2/2
✓ Branch 2 taken 52520 times.
✓ Branch 3 taken 1920 times.
 153892 (p1[2] == p2[2]) ;
689 }
690
691 /**
692 * \brief Detects degenerate triangles
693 * \retval 0 if all the vertices of the triangle are the same point
694 * \retval 1 if the vertices of the triangle are co-linear
695 * \retval 2 otherwise
696 */
697 1962736 index_t triangle_dim(
698 TriangleRegion i, TriangleRegion j, TriangleRegion k
699 ) {
700
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 1962736 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 1962736 geo_debug_assert(region_dim(i) == 0);
701
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 1962736 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 1962736 geo_debug_assert(region_dim(j) == 0);
702
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 1962736 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 1962736 geo_debug_assert(region_dim(k) == 0);
703
704 1962736 const vec3& p1 = p_[i];
705 1962736 const vec3& p2 = p_[j];
706 1962736 const vec3& p3 = p_[k];
707
708
1/2
✓ Branch 4 taken 1962736 times.
✗ Branch 5 not taken.
 1962736 if(!PCK::aligned_3d(p1.data(), p2.data(), p3.data())) {
709 1962736 return 2;
710 }
711 ✗ if(points_are_identical(i,j) && points_are_identical(j,k)) {
712 ✗ return 0;
713 }
714 ✗ return 1;
715 }
716
717
718 private:
719 vec3 p_[6];
720 TriangleIsects* result_;
721 bool has_non_degenerate_intersection_;
722 mutable Numeric::int8 o3d_cache_[64];
723 index_t p_index_[6];
724 bool has_global_indices_;
725 };
726
727 }
728
729 /****************************************************************************/
730
731 namespace GEO {
732
733 ✗ std::string region_to_string(TriangleRegion rgn) {
734 ✗ const char* strs[T_RGN_NB] = {
735 "T1.P0",
736 "T1.P1",
737 "T1.P2",
738
739 "T2.P0",
740 "T2.P1",
741 "T2.P2",
742
743 "T1.E0",
744 "T1.E1",
745 "T1.E2",
746
747 "T2.E0",
748 "T2.E1",
749 "T2.E2",
750
751 "T1.T",
752 "T2.T"
753 };
754 ✗ geo_assert(int(rgn) < int(T_RGN_NB));
755 ✗ return strs[int(rgn)];
756 }
757
758 // This version returns the symbolic information.
759 ✗ bool triangles_intersections(
760 const vec3& p0, const vec3& p1, const vec3& p2,
761 const vec3& q0, const vec3& q1, const vec3& q2,
762 TriangleIsects& result
763 ) {
764 ✗ result.resize(0);
765 TriangleTriangleIntersection I(
766 p0, p1, p2,
767 q0, q1, q2,
768 &result
769 ✗ );
770 ✗ I.compute();
771 ✗ return I.has_non_degenerate_intersection();
772 }
773
774 // This version returns the symbolic information.
775 981368 bool triangles_intersections(
776 const vec3& p0, const vec3& p1, const vec3& p2,
777 const vec3& q0, const vec3& q1, const vec3& q2,
778 index_t p0_index, index_t p1_index, index_t p2_index,
779 index_t q0_index, index_t q1_index, index_t q2_index,
780 TriangleIsects& result
781 ) {
782
1/2
✓ Branch 1 taken 981368 times.
✗ Branch 2 not taken.
 981368 result.resize(0);
783 TriangleTriangleIntersection I(
784 p0, p1, p2,
785 q0, q1, q2,
786 p0_index, p1_index, p2_index,
787 q0_index, q1_index, q2_index,
788 &result
789
1/2
✓ Branch 1 taken 981368 times.
✗ Branch 2 not taken.
 981368 );
790
1/2
✓ Branch 1 taken 981368 times.
✗ Branch 2 not taken.
 981368 I.compute();
791 1962736 return I.has_non_degenerate_intersection();
792 }
793
794 // This version is just a predicate (returns true if
795 // there is a non-degenerate intersection, false
796 // otherwise).
797 ✗ bool triangles_intersections(
798 const vec3& p0, const vec3& p1, const vec3& p2,
799 const vec3& q0, const vec3& q1, const vec3& q2
800 ) {
801 TriangleTriangleIntersection I(
802 p0, p1, p2,
803 q0, q1, q2
804 ✗ );
805 ✗ I.compute();
806 ✗ return I.has_non_degenerate_intersection();
807 }
808
809 91879042 coord_index_t region_dim(TriangleRegion r) {
810
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 91879042 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 91879042 geo_debug_assert(index_t(r) < T_RGN_NB);
811 static coord_index_t trgl_rgn_dim[T_RGN_NB] = {
812 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2
813 };
814 91879042 return trgl_rgn_dim[index_t(r)];
815 }
816
817 271532 TriangleRegion swap_T1_T2(TriangleRegion R) {
818 271532 TriangleRegion result=T_RGN_NB;
819
14/16
✓ Branch 0 taken 4425 times.
✓ Branch 1 taken 3745 times.
✓ Branch 2 taken 4727 times.
✓ Branch 3 taken 5954 times.
✓ Branch 4 taken 3639 times.
✓ Branch 5 taken 4000 times.
✓ Branch 6 taken 32379 times.
✓ Branch 7 taken 28793 times.
✓ Branch 8 taken 35689 times.
✓ Branch 9 taken 32849 times.
✓ Branch 10 taken 28592 times.
✓ Branch 11 taken 36310 times.
✓ Branch 12 taken 26008 times.
✓ Branch 13 taken 24422 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
 271532 switch(R) {
820 4425 case T1_RGN_P0:
821 4425 result = T2_RGN_P0;
822 4425 break;
823 3745 case T1_RGN_P1:
824 3745 result = T2_RGN_P1;
825 3745 break;
826 4727 case T1_RGN_P2:
827 4727 result = T2_RGN_P2;
828 4727 break;
829 5954 case T2_RGN_P0:
830 5954 result = T1_RGN_P0;
831 5954 break;
832 3639 case T2_RGN_P1:
833 3639 result = T1_RGN_P1;
834 3639 break;
835 4000 case T2_RGN_P2:
836 4000 result = T1_RGN_P2;
837 4000 break;
838 32379 case T1_RGN_E0:
839 32379 result = T2_RGN_E0;
840 32379 break;
841 28793 case T1_RGN_E1:
842 28793 result = T2_RGN_E1;
843 28793 break;
844 35689 case T1_RGN_E2:
845 35689 result = T2_RGN_E2;
846 35689 break;
847 32849 case T2_RGN_E0:
848 32849 result = T1_RGN_E0;
849 32849 break;
850 28592 case T2_RGN_E1:
851 28592 result = T1_RGN_E1;
852 28592 break;
853 36310 case T2_RGN_E2:
854 36310 result = T1_RGN_E2;
855 36310 break;
856 26008 case T1_RGN_T:
857 26008 result = T2_RGN_T;
858 26008 break;
859 24422 case T2_RGN_T:
860 24422 result = T1_RGN_T;
861 24422 break;
862 ✗ case T_RGN_NB:
863 ✗ geo_assert_not_reached;
864 }
865 271532 return result;
866 }
867
868 3166968 void get_triangle_vertices(
869 TriangleRegion T,
870 TriangleRegion& p0, TriangleRegion& p1, TriangleRegion& p2
871 ) {
872
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 3166968 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 3166968 geo_debug_assert(region_dim(T) == 2);
873
2/3
✓ Branch 0 taken 1938031 times.
✓ Branch 1 taken 1228937 times.
✗ Branch 2 not taken.
 3166968 switch(T) {
874 1938031 case T1_RGN_T: {
875 1938031 p0 = T1_RGN_P0; p1 = T1_RGN_P1; p2 = T1_RGN_P2;
876 1938031 } break;
877 1228937 case T2_RGN_T: {
878 1228937 p0 = T2_RGN_P0; p1 = T2_RGN_P1; p2 = T2_RGN_P2;
879 1228937 } break;
880 ✗ default:
881 ✗ geo_assert_not_reached;
882 }
883 3166968 }
884
885 1711578 void get_triangle_edges(
886 TriangleRegion T,
887 TriangleRegion& e0, TriangleRegion& e1, TriangleRegion& e2
888 ) {
889
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 1711578 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 1711578 geo_debug_assert(region_dim(T) == 2);
890
2/3
✓ Branch 0 taken 855789 times.
✓ Branch 1 taken 855789 times.
✗ Branch 2 not taken.
 1711578 switch(T) {
891 855789 case T1_RGN_T: {
892 855789 e0 = T1_RGN_E0; e1 = T1_RGN_E1; e2 = T1_RGN_E2;
893 855789 } break;
894 855789 case T2_RGN_T: {
895 855789 e0 = T2_RGN_E0; e1 = T2_RGN_E1; e2 = T2_RGN_E2;
896 855789 } break;
897 ✗ default:
898 ✗ geo_assert_not_reached;
899 }
900 1711578 }
901
902 5226573 void get_edge_vertices(
903 TriangleRegion E, TriangleRegion& q0, TriangleRegion& q1
904 ) {
905
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 5226573 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 5226573 geo_debug_assert(region_dim(E) == 1);
906
6/7
✓ Branch 0 taken 881068 times.
✓ Branch 1 taken 869300 times.
✓ Branch 2 taken 871185 times.
✓ Branch 3 taken 866480 times.
✓ Branch 4 taken 872549 times.
✓ Branch 5 taken 865991 times.
✗ Branch 6 not taken.
 5226573 switch(E) {
907 881068 case T1_RGN_E0: {
908 881068 q0 = T1_RGN_P1;
909 881068 q1 = T1_RGN_P2;
910 881068 } break;
911 869300 case T1_RGN_E1: {
912 869300 q0 = T1_RGN_P2;
913 869300 q1 = T1_RGN_P0;
914 869300 } break;
915 871185 case T1_RGN_E2: {
916 871185 q0 = T1_RGN_P0;
917 871185 q1 = T1_RGN_P1;
918 871185 } break;
919 866480 case T2_RGN_E0: {
920 866480 q0 = T2_RGN_P1;
921 866480 q1 = T2_RGN_P2;
922 866480 } break;
923 872549 case T2_RGN_E1: {
924 872549 q0 = T2_RGN_P2;
925 872549 q1 = T2_RGN_P0;
926 872549 } break;
927 865991 case T2_RGN_E2: {
928 865991 q0 = T2_RGN_P0;
929 865991 q1 = T2_RGN_P1;
930 865991 } break;
931 ✗ default:
932 ✗ geo_assert_not_reached;
933 }
934 5226573 }
935
936 328516 TriangleRegion GEOGRAM_API regions_convex_hull(
937 TriangleRegion R1, TriangleRegion R2
938 ) {
939
1/6
✗ Branch 2 not taken.
✓ Branch 3 taken 328516 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 328516 geo_debug_assert(is_in_T1(R1) == is_in_T1(R2));
940
2/2
✓ Branch 0 taken 122223 times.
✓ Branch 1 taken 206293 times.
 328516 if(R1 == R2) {
941 122223 return R1;
942 }
943
944
2/2
✓ Branch 1 taken 126143 times.
✓ Branch 2 taken 80150 times.
 206293 TriangleRegion R = is_in_T1(R1) ? T1_RGN_T : T2_RGN_T;
945
946
6/6
✓ Branch 1 taken 160544 times.
✓ Branch 2 taken 45749 times.
✓ Branch 4 taken 17178 times.
✓ Branch 5 taken 143366 times.
✓ Branch 6 taken 17178 times.
✓ Branch 7 taken 189115 times.
 206293 if(region_dim(R1) == 1 && region_dim(R2) == 0) {
947 TriangleRegion v1,v2;
948
1/2
✓ Branch 1 taken 17178 times.
✗ Branch 2 not taken.
 17178 get_edge_vertices(R1,v1,v2);
949
4/4
✓ Branch 0 taken 9498 times.
✓ Branch 1 taken 7680 times.
✓ Branch 2 taken 7587 times.
✓ Branch 3 taken 1911 times.
 17178 if(R2 == v1 || R2 == v2) {
950 15267 R = R1;
951 }
952
6/6
✓ Branch 1 taken 155130 times.
✓ Branch 2 taken 33985 times.
✓ Branch 4 taken 14622 times.
✓ Branch 5 taken 140508 times.
✓ Branch 6 taken 14622 times.
✓ Branch 7 taken 174493 times.
 189115 } else if(region_dim(R2) == 1 && region_dim(R1) == 0) {
953 TriangleRegion v1,v2;
954
1/2
✓ Branch 1 taken 14622 times.
✗ Branch 2 not taken.
 14622 get_edge_vertices(R2,v1,v2);
955
4/4
✓ Branch 0 taken 8331 times.
✓ Branch 1 taken 6291 times.
✓ Branch 2 taken 6386 times.
✓ Branch 3 taken 1945 times.
 14622 if(R1 == v1 || R1 == v2) {
956 12677 R = R2;
957 }
958
6/6
✓ Branch 1 taken 10417 times.
✓ Branch 2 taken 164076 times.
✓ Branch 4 taken 10237 times.
✓ Branch 5 taken 180 times.
✓ Branch 6 taken 10237 times.
✓ Branch 7 taken 164256 times.
 174493 } else if(region_dim(R1) == 0 && region_dim(R2) == 0) {
959 34423 for(TriangleRegion E: {
960 T1_RGN_E0, T1_RGN_E1, T1_RGN_E2,
961 T2_RGN_E0, T2_RGN_E1, T2_RGN_E2
962
1/2
✓ Branch 2 taken 34423 times.
✗ Branch 3 not taken.
 44660 }
963 ) {
964 TriangleRegion v1,v2;
965
1/2
✓ Branch 1 taken 34423 times.
✗ Branch 2 not taken.
 34423 get_edge_vertices(E,v1,v2);
966
8/8
✓ Branch 0 taken 6739 times.
✓ Branch 1 taken 27684 times.
✓ Branch 2 taken 2336 times.
✓ Branch 3 taken 4403 times.
✓ Branch 4 taken 8929 times.
✓ Branch 5 taken 21091 times.
✓ Branch 6 taken 5834 times.
✓ Branch 7 taken 3095 times.
 34423 if((R1 == v1 && R2 == v2) || (R1 == v2 && R2 == v1)) {
967 10237 R = E;
968 10237 break;
969 }
970 }
971 }
972
973 206293 return R;
974 }
975
976 }
977