GCC Code Coverage Report

Directory: ./
File: mesh/triangle_intersection.cpp
Date: 2026-11-07 04:21:38
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 1007424 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 6044544 times.
✓ Branch 2 taken 1007424 times.
 7051968 ) : result_(result) {
105 1007424 p_[0] = p0;
106 1007424 p_[1] = p1;
107 1007424 p_[2] = p2;
108 1007424 p_[3] = q0;
109 1007424 p_[4] = q1;
110 1007424 p_[5] = q2;
111
2/2
✓ Branch 0 taken 64475136 times.
✓ Branch 1 taken 1007424 times.
 65482560 for(index_t i=0; i<64; ++i) {
112 64475136 o3d_cache_[i] = CACHE_UNINITIALIZED;
113 }
114 1007424 has_non_degenerate_intersection_ = false;
115 1007424 p_index_[0] = p0_index;
116 1007424 p_index_[1] = p1_index;
117 1007424 p_index_[2] = p2_index;
118 1007424 p_index_[3] = q0_index;
119 1007424 p_index_[4] = q1_index;
120 1007424 p_index_[5] = q2_index;
121 1007424 has_global_indices_ = true;
122 1007424 }
123
124 1007424 void compute() {
125 #ifdef TT_DEBUG
126 Logger::out("TT") << "Call compute()" << std::endl;
127 #endif
128
129
1/2
✓ Branch 0 taken 1007424 times.
✗ Branch 1 not taken.
 1007424 if(result_ != nullptr) {
130 1007424 result_->resize(0);
131 }
132
133 // Test for degenerate triangles
134 1007424 if(
135
2/4
✓ Branch 1 taken 1007424 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1007424 times.
 2014848 triangle_dim(T1_RGN_P0, T1_RGN_P1, T1_RGN_P2) != 2 ||
136
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1007424 times.
 1007424 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 1007424 times.
✗ Branch 1 not taken.
 1007424 if(has_global_indices_) {
148
149 1007424 index_t q_index[3] = {
150 NO_INDEX, NO_INDEX, NO_INDEX
151 };
152
153
2/2
✓ Branch 0 taken 3022272 times.
✓ Branch 1 taken 1007424 times.
 4029696 for(index_t i=0; i<3; ++i) {
154
2/2
✓ Branch 0 taken 9066816 times.
✓ Branch 1 taken 3022272 times.
 12089088 for(index_t j=0; j<3; ++j) {
155
2/2
✓ Branch 0 taken 911777 times.
✓ Branch 1 taken 8155039 times.
 9066816 if(p_index_[i+3] == p_index_[j]) {
156 911777 q_index[i] = j;
157 }
158 }
159 }
160
161 // Early exit tests for configurations where 1 or 2 vertices
162 // are shared.
163 1007424 int nb_shared = (
164 1007424 (q_index[0] != NO_INDEX) +
165 1007424 (q_index[1] != NO_INDEX) +
166 1007424 (q_index[2] != NO_INDEX) ) ;
167
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 1007424 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 1007424 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 555741 times.
✓ Branch 1 taken 451683 times.
 1007424 if(nb_shared == 1) {
172 555741 int shared_q =
173
2/2
✓ Branch 0 taken 183840 times.
✓ Branch 1 taken 371901 times.
 555741 (q_index[1] != NO_INDEX) + (q_index[2] != NO_INDEX)*2;
174
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 555741 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 555741 geo_debug_assert(q_index[shared_q] != NO_INDEX);
175 555741 TriangleRegion q1 =
176 555741 TriangleRegion(T2_RGN_P0 + ((shared_q+1))%3);
177 555741 TriangleRegion q2 =
178 555741 TriangleRegion(T2_RGN_P0 + ((shared_q+2))%3);
179 TriangleRegion p1,p2,p3;
180
1/2
✓ Branch 1 taken 555741 times.
✗ Branch 2 not taken.
 555741 get_triangle_vertices(T1_RGN_T, p1,p2,p3);
181
1/2
✓ Branch 1 taken 555741 times.
✗ Branch 2 not taken.
 555741 Sign o1 = orient3d(p1,p2,p3,q1);
182
1/2
✓ Branch 1 taken 555741 times.
✗ Branch 2 not taken.
 555741 Sign o2 = orient3d(p1,p2,p3,q2);
183
2/2
✓ Branch 0 taken 460977 times.
✓ Branch 1 taken 94764 times.
 555741 if(int(o1)*int(o2) > 0) {
184 460977 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 178018 times.
✓ Branch 1 taken 368429 times.
 546447 if(nb_shared == 2) {
191 178018 int non_shared_q =
192
2/2
✓ Branch 0 taken 59905 times.
✓ Branch 1 taken 118113 times.
 178018 (q_index[1] == NO_INDEX) + (q_index[2] == NO_INDEX)*2;
193
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 178018 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 178018 geo_debug_assert(q_index[non_shared_q] == NO_INDEX);
194 178018 TriangleRegion q = TriangleRegion(T2_RGN_P0 + non_shared_q);
195 TriangleRegion p1,p2,p3;
196
1/2
✓ Branch 1 taken 178018 times.
✗ Branch 2 not taken.
 178018 get_triangle_vertices(T1_RGN_T, p1,p2,p3);
197
3/4
✓ Branch 1 taken 178018 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 166284 times.
✓ Branch 4 taken 11734 times.
 178018 if(orient3d(p1,p2,p3,q) != ZERO) {
198 166284 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 380163 times.
✗ Branch 2 not taken.
 380163 get_triangle_vertices(T1_RGN_T, p1,p2,p3);
210
1/2
✓ Branch 1 taken 380163 times.
✗ Branch 2 not taken.
 380163 get_triangle_vertices(T2_RGN_T, q1,q2,q3);
211
1/2
✓ Branch 1 taken 380163 times.
✗ Branch 2 not taken.
 380163 Sign o1 = orient3d(q1,q2,q3,p1);
212
1/2
✓ Branch 1 taken 380163 times.
✗ Branch 2 not taken.
 380163 Sign o2 = orient3d(q1,q2,q3,p2);
213
1/2
✓ Branch 1 taken 380163 times.
✗ Branch 2 not taken.
 380163 Sign o3 = orient3d(q1,q2,q3,p3);
214 380163 if(
215
2/2
✓ Branch 0 taken 135184 times.
✓ Branch 1 taken 244979 times.
 380163 int(o1)*int(o2) == 1 &&
216
2/2
✓ Branch 0 taken 88530 times.
✓ Branch 1 taken 46654 times.
 135184 int(o2)*int(o3) == 1 &&
217
1/2
✓ Branch 0 taken 88530 times.
✗ Branch 1 not taken.
 88530 int(o3)*int(o1) == 1
218 ) {
219 88530 return;
220 }
221 }
222
223 291633 intersect_edge_triangle(T1_RGN_E0, T2_RGN_T);
224
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 291633 times.
 291633 if(finished()) { return; }
225 291633 intersect_edge_triangle(T1_RGN_E1, T2_RGN_T);
226
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 291633 times.
 291633 if(finished()) { return; }
227 291633 intersect_edge_triangle(T1_RGN_E2, T2_RGN_T);
228
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 291633 times.
 291633 if(finished()) { return; }
229
230 291633 intersect_edge_triangle(T2_RGN_E0, T1_RGN_T);
231
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 291633 times.
 291633 if(finished()) { return; }
232 291633 intersect_edge_triangle(T2_RGN_E1, T1_RGN_T);
233
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 291633 times.
 291633 if(finished()) { return; }
234 291633 intersect_edge_triangle(T2_RGN_E2, T1_RGN_T);
235
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 291633 times.
 291633 if(finished()) { return; }
236
237 // The same intersection can appear several times,
238 // remove the duplicates
239
1/2
✓ Branch 0 taken 291633 times.
✗ Branch 1 not taken.
 291633 if(result_ != nullptr) {
240 291633 std::sort(result_->begin(), result_->end());
241 291633 auto p = std::unique(result_->begin(), result_->end());
242 291633 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 1007424 bool has_non_degenerate_intersection() const {
261 1007424 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 3454533 bool finished() const {
272 #ifdef TT_DEBUG
273 return false;
274 #endif
275
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 3454533 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 3454533 return (result_ == nullptr && has_non_degenerate_intersection_);
276 }
277
278 1749798 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 1749798 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1749798 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 1749798 geo_debug_assert(region_dim(E) == 1);
286
2/8
✓ Branch 1 taken 1749798 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1749798 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 1749798 geo_debug_assert(region_dim(T) == 2);
287
288 1749798 TriangleRegion R1 = E;
289 1749798 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 1749798 times.
✗ Branch 2 not taken.
 1749798 get_triangle_vertices(T,p1,p2,p3);
296
1/2
✓ Branch 1 taken 1749798 times.
✗ Branch 2 not taken.
 1749798 get_triangle_edges(T,e1,e2,e3);
297
1/2
✓ Branch 1 taken 1749798 times.
✗ Branch 2 not taken.
 1749798 get_edge_vertices(E,q1,q2);
298
299
1/2
✓ Branch 1 taken 1749798 times.
✗ Branch 2 not taken.
 1749798 Sign o1 = orient3d(p1,p2,p3,q1);
300
1/2
✓ Branch 1 taken 1749798 times.
✗ Branch 2 not taken.
 1749798 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 347808 times.
✓ Branch 1 taken 1401990 times.
 1749798 if(int(o1) * int(o2) == 1) {
306 645191 return;
307 }
308
309
4/4
✓ Branch 0 taken 817186 times.
✓ Branch 1 taken 584804 times.
✓ Branch 2 taken 562705 times.
✓ Branch 3 taken 254481 times.
 1401990 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 562705 times.
✗ Branch 2 not taken.
 562705 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 562705 times.
✗ Branch 2 not taken.
 562705 Sign a1 = orient2d(q1,p1,p2,nax);
320
1/2
✓ Branch 1 taken 562705 times.
✗ Branch 2 not taken.
 562705 Sign a2 = orient2d(q1,p2,p3,nax);
321
1/2
✓ Branch 1 taken 562705 times.
✗ Branch 2 not taken.
 562705 Sign a3 = orient2d(q1,p3,p1,nax);
322
323
1/2
✓ Branch 1 taken 562705 times.
✗ Branch 2 not taken.
 562705 Sign b1 = orient2d(q2,p1,p2,nax);
324
1/2
✓ Branch 1 taken 562705 times.
✗ Branch 2 not taken.
 562705 Sign b2 = orient2d(q2,p2,p3,nax);
325
1/2
✓ Branch 1 taken 562705 times.
✗ Branch 2 not taken.
 562705 Sign b3 = orient2d(q2,p3,p1,nax);
326
327 562705 if(
328
2/2
✓ Branch 0 taken 118650 times.
✓ Branch 1 taken 444055 times.
 562705 int(a1)*int(a2) > 0 &&
329
2/2
✓ Branch 0 taken 8310 times.
✓ Branch 1 taken 110340 times.
 118650 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 562705 if(
337
2/2
✓ Branch 0 taken 117860 times.
✓ Branch 1 taken 444845 times.
 562705 int(b1)*int(b2) > 0 &&
338
2/2
✓ Branch 0 taken 8310 times.
✓ Branch 1 taken 109550 times.
 117860 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 562705 times.
✗ Branch 2 not taken.
 562705 intersect_edge_edge_2d(E,e1,nax);
347
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 562705 times.
 562705 if(finished()) { return; }
348
1/2
✓ Branch 1 taken 562705 times.
✗ Branch 2 not taken.
 562705 intersect_edge_edge_2d(E,e2,nax);
349
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 562705 times.
 562705 if(finished()) { return; }
350
1/2
✓ Branch 1 taken 562705 times.
✗ Branch 2 not taken.
 562705 intersect_edge_edge_2d(E,e3,nax);
351
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 562705 times.
 562705 if(finished()) { return; }
352
353 562705 } 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 254481 times.
✓ Branch 1 taken 584804 times.
 839285 if(o1 == ZERO) {
361 254481 R1 = q1;
362
2/2
✓ Branch 0 taken 254481 times.
✓ Branch 1 taken 330323 times.
 584804 } else if(o2 == ZERO) {
363 254481 R1 = q2;
364 }
365
366
1/2
✓ Branch 1 taken 839285 times.
✗ Branch 2 not taken.
 839285 Sign oo1 = orient3d(p2,p3,q1,q2);
367
1/2
✓ Branch 1 taken 839285 times.
✗ Branch 2 not taken.
 839285 Sign oo2 = orient3d(p3,p1,q1,q2);
368
369
2/2
✓ Branch 0 taken 297383 times.
✓ Branch 1 taken 541902 times.
 839285 if(int(oo1)*int(oo2) == -1) {
370 297383 return;
371 }
372
373
1/2
✓ Branch 1 taken 541902 times.
✗ Branch 2 not taken.
 541902 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 541902 int nb_zeros = (oo1 == ZERO) + (oo2 == ZERO) + (oo3 == ZERO);
379
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 541902 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 541902 geo_debug_assert(nb_zeros != 3);
380
2/2
✓ Branch 0 taken 45431 times.
✓ Branch 1 taken 496471 times.
 541902 if(nb_zeros == 1) {
381
2/2
✓ Branch 0 taken 22300 times.
✓ Branch 1 taken 23131 times.
 45431 if(oo1 == ZERO) {
382 22300 R2 = e1;
383
2/2
✓ Branch 0 taken 18903 times.
✓ Branch 1 taken 4228 times.
 23131 } else if(oo2 == ZERO) {
384 18903 R2 = e2;
385 } else {
386 4228 R2 = e3;
387 }
388
2/2
✓ Branch 0 taken 289772 times.
✓ Branch 1 taken 206699 times.
 496471 } else if(nb_zeros == 2) {
389
2/2
✓ Branch 0 taken 92369 times.
✓ Branch 1 taken 197403 times.
 289772 if(oo1 != ZERO) {
390 92369 R2 = p1;
391
2/2
✓ Branch 0 taken 95013 times.
✓ Branch 1 taken 102390 times.
 197403 } else if(oo2 != ZERO) {
392 95013 R2 = p2;
393 } else {
394 102390 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 541902 bool outside =
407 1083804 (int(oo1) * int(oo2) == -1) ||
408
3/4
✓ Branch 0 taken 541902 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 356965 times.
✓ Branch 3 taken 184937 times.
 898867 (int(oo2) * int(oo3) == -1) ||
409
2/2
✓ Branch 0 taken 13399 times.
✓ Branch 1 taken 343566 times.
 356965 (int(oo3) * int(oo1) == -1) ;
410
411
2/2
✓ Branch 0 taken 343566 times.
✓ Branch 1 taken 198336 times.
 541902 if(!outside) {
412
1/2
✓ Branch 1 taken 343566 times.
✗ Branch 2 not taken.
 343566 add_intersection(R1,R2);
413 }
414 }
415 }
416
417
418 1688115 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 1688115 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1688115 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 1688115 geo_debug_assert(region_dim(E1) == 1);
426
2/8
✓ Branch 1 taken 1688115 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1688115 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 1688115 geo_debug_assert(region_dim(E2) == 1);
427
428 1688115 TriangleRegion R1 = E1;
429 1688115 TriangleRegion R2 = E2;
430
431 TriangleRegion p1,p2;
432
1/2
✓ Branch 1 taken 1688115 times.
✗ Branch 2 not taken.
 1688115 get_edge_vertices(E1,p1,p2);
433
434 TriangleRegion q1,q2;
435
1/2
✓ Branch 1 taken 1688115 times.
✗ Branch 2 not taken.
 1688115 get_edge_vertices(E2,q1,q2);
436
437
1/2
✓ Branch 1 taken 1688115 times.
✗ Branch 2 not taken.
 1688115 Sign a1 = orient2d(q1,q2,p1,nax);
438
1/2
✓ Branch 1 taken 1688115 times.
✗ Branch 2 not taken.
 1688115 Sign a2 = orient2d(q1,q2,p2,nax);
439
440
4/4
✓ Branch 0 taken 204484 times.
✓ Branch 1 taken 1483631 times.
✓ Branch 2 taken 36300 times.
✓ Branch 3 taken 168184 times.
 1688115 if(a1 == ZERO && a2 == ZERO) {
441 // Special case: 1D
442 // (the 2x2 edge extremities are aligned)
443
1/2
✓ Branch 1 taken 36300 times.
✗ Branch 2 not taken.
 36300 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 168184 times.
✓ Branch 1 taken 1483631 times.
 1651815 if(a1 == ZERO) {
448 168184 R1 = p1;
449
2/2
✓ Branch 0 taken 168318 times.
✓ Branch 1 taken 1315313 times.
 1483631 } else if(a2 == ZERO) {
450 168318 R1 = p2;
451 }
452
453
1/2
✓ Branch 1 taken 1651815 times.
✗ Branch 2 not taken.
 1651815 Sign b1 = orient2d(p1,p2,q1,nax);
454
1/2
✓ Branch 1 taken 1651815 times.
✗ Branch 2 not taken.
 1651815 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 177651 times.
✓ Branch 1 taken 1474164 times.
 1651815 if(b1 == ZERO) {
459 177651 R2 = q1;
460
2/2
✓ Branch 0 taken 177651 times.
✓ Branch 1 taken 1296513 times.
 1474164 } else if(b2 == ZERO) {
461 177651 R2 = q2;
462 }
463
464
4/4
✓ Branch 0 taken 512489 times.
✓ Branch 1 taken 1139326 times.
✓ Branch 2 taken 396342 times.
✓ Branch 3 taken 116147 times.
 1651815 if( int(a1)*int(a2) != 1 && int(b1)*int(b2) != 1) {
465
1/2
✓ Branch 1 taken 396342 times.
✗ Branch 2 not taken.
 396342 add_intersection(R1,R2);
466 }
467 }
468 1688115 }
469
470 36300 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 36300 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 36300 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 36300 geo_debug_assert(region_dim(E1) == 1);
478
2/8
✓ Branch 1 taken 36300 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 36300 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 36300 geo_debug_assert(region_dim(E2) == 1);
479
480 TriangleRegion p1,p2;
481
1/2
✓ Branch 1 taken 36300 times.
✗ Branch 2 not taken.
 36300 get_edge_vertices(E1,p1,p2);
482
483 TriangleRegion q1,q2;
484
1/2
✓ Branch 1 taken 36300 times.
✗ Branch 2 not taken.
 36300 get_edge_vertices(E2,q1,q2);
485
486
1/2
✓ Branch 1 taken 36300 times.
✗ Branch 2 not taken.
 36300 Sign d1 = dot3d(p1,q1,q2);
487
1/2
✓ Branch 1 taken 36300 times.
✗ Branch 2 not taken.
 36300 Sign d2 = dot3d(p2,q1,q2);
488
1/2
✓ Branch 1 taken 36300 times.
✗ Branch 2 not taken.
 36300 Sign d3 = dot3d(q1,p1,p2);
489
1/2
✓ Branch 1 taken 36300 times.
✗ Branch 2 not taken.
 36300 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 26261 times.
✓ Branch 1 taken 10039 times.
✓ Branch 2 taken 24864 times.
✓ Branch 3 taken 1397 times.
✓ Branch 5 taken 24864 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1456 times.
✓ Branch 8 taken 23408 times.
✓ Branch 9 taken 1456 times.
✓ Branch 10 taken 34844 times.
 36300 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 26263 times.
✓ Branch 1 taken 10037 times.
✓ Branch 2 taken 24865 times.
✓ Branch 3 taken 1398 times.
✓ Branch 5 taken 24865 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 24805 times.
✓ Branch 8 taken 60 times.
✓ Branch 9 taken 24805 times.
✓ Branch 10 taken 11495 times.
 36300 if(d2 == ZERO && d3 == ZERO && points_are_identical(p2,q1)) {
501
1/2
✓ Branch 1 taken 24805 times.
✗ Branch 2 not taken.
 24805 add_intersection(p2,q1);
502 }
503
504
9/10
✓ Branch 0 taken 26261 times.
✓ Branch 1 taken 10039 times.
✓ Branch 2 taken 24865 times.
✓ Branch 3 taken 1396 times.
✓ Branch 5 taken 24865 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 24805 times.
✓ Branch 8 taken 60 times.
✓ Branch 9 taken 24805 times.
✓ Branch 10 taken 11495 times.
 36300 if(d1 == ZERO && d4 == ZERO && points_are_identical(p1,q2)) {
505
1/2
✓ Branch 1 taken 24805 times.
✗ Branch 2 not taken.
 24805 add_intersection(p1,q2);
506 }
507
508
9/10
✓ Branch 0 taken 26263 times.
✓ Branch 1 taken 10037 times.
✓ Branch 2 taken 24866 times.
✓ Branch 3 taken 1397 times.
✓ Branch 5 taken 24866 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1458 times.
✓ Branch 8 taken 23408 times.
✓ Branch 9 taken 1458 times.
✓ Branch 10 taken 34842 times.
 36300 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 36122 times.
 36300 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 36122 times.
 36300 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 36122 times.
 36300 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 36122 times.
 36300 if(d4 == NEGATIVE) {
528
1/2
✓ Branch 1 taken 178 times.
✗ Branch 2 not taken.
 178 add_intersection(E1,q2);
529 }
530 36300 }
531
532 809764 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 688374 times.
✓ Branch 2 taken 121390 times.
✓ Branch 4 taken 31586 times.
✓ Branch 5 taken 656788 times.
✓ Branch 6 taken 152976 times.
✓ Branch 7 taken 656788 times.
 809764 if(region_dim(R1) >= 1 || region_dim(R2) >= 1) {
538 152976 has_non_degenerate_intersection_ = true;
539 }
540
2/2
✓ Branch 1 taken 392769 times.
✓ Branch 2 taken 416995 times.
 809764 if(is_in_T1(R1)) {
541
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 392769 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 392769 geo_debug_assert(!is_in_T1(R2));
542
1/2
✓ Branch 0 taken 392769 times.
✗ Branch 1 not taken.
 392769 if(result_ != nullptr) {
543
2/4
✓ Branch 1 taken 392769 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 392769 times.
✗ Branch 5 not taken.
 392769 result_->push_back(std::make_pair(R1,R2));
544 }
545 } else {
546
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 416995 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 416995 geo_debug_assert(is_in_T1(R2));
547
1/2
✓ Branch 0 taken 416995 times.
✗ Branch 1 not taken.
 416995 if(result_ != nullptr) {
548
2/4
✓ Branch 1 taken 416995 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 416995 times.
✗ Branch 5 not taken.
 416995 result_->push_back(std::make_pair(R2,R1));
549 }
550 }
551 809764 }
552
553 8150057 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 8150057 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 8150057 geo_debug_assert(region_dim(i) == 0);
559
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 8150057 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 8150057 geo_debug_assert(region_dim(j) == 0);
560
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 8150057 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 8150057 geo_debug_assert(region_dim(k) == 0);
561
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 8150057 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 8150057 geo_debug_assert(region_dim(l) == 0);
562
563 // Index for the cache (1 bit set for
564 // each vertex)
565
566 8150057 index_t o3d_idx =
567 8150057 (1u << index_t(i)) |
568 8150057 (1u << index_t(j)) |
569 8150057 (1u << index_t(k)) |
570 8150057 (1u << index_t(l)) ;
571
572
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 8150057 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 8150057 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 8150057 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 4598015 times.
✓ Branch 1 taken 3552042 times.
 8150057 if(o3d_cache_[o3d_idx] == CACHE_UNINITIALIZED) {
582
2/2
✓ Branch 0 taken 1822703 times.
✓ Branch 1 taken 2775312 times.
 4598015 int o = flip ? -int(PCK::orient_3d(p_[i],p_[j],p_[k],p_[l])) :
583 4598015 int(PCK::orient_3d(p_[i],p_[j],p_[k],p_[l])) ;
584 4598015 o3d_cache_[o3d_idx] = Numeric::int8(o);
585 }
586
587 // Get result from the cache
588
589
2/2
✓ Branch 0 taken 3903651 times.
✓ Branch 1 taken 4246406 times.
 8150057 Sign result = flip ? Sign(-o3d_cache_[o3d_idx])
590 4246406 : 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 8150057 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 8150057 geo_debug_assert(
595 result == PCK::orient_3d(p_[i], p_[j], p_[k], p_[l])
596 );
597
598 8150057 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 8150057 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 8150057 index_t tab[4] = { i, j, k, l };
610 8150057 constexpr int N = 4;
611 8150057 bool result = false;
612
2/2
✓ Branch 0 taken 24450171 times.
✓ Branch 1 taken 8150057 times.
 32600228 for (int I = 0; I < N - 1; ++I) {
613
2/2
✓ Branch 0 taken 48900342 times.
✓ Branch 1 taken 24450171 times.
 73350513 for (int J = 0; J < N - I - 1; ++J) {
614
2/2
✓ Branch 0 taken 14842317 times.
✓ Branch 1 taken 34058025 times.
 48900342 if (tab[J] > tab[J + 1]) {
615 14842317 std::swap(tab[J], tab[J + 1]);
616 14842317 result = !result;
617 }
618 }
619 }
620 8150057 return result;
621 }
622
623 10056090 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 10056090 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 10056090 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 10056090 geo_debug_assert(region_dim(i) == 0);
630
2/8
✓ Branch 1 taken 10056090 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 10056090 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 10056090 geo_debug_assert(region_dim(j) == 0);
631
2/8
✓ Branch 1 taken 10056090 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 10056090 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 10056090 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 20112180 times.
✓ Branch 1 taken 10056090 times.
 30168270 for(coord_index_t c = 0; c < 2; c++) {
636
1/2
✓ Branch 1 taken 20112180 times.
✗ Branch 2 not taken.
 20112180 pi[c] = p_[i][index_t((normal_axis + 1 + c) % 3)];
637
1/2
✓ Branch 1 taken 20112180 times.
✗ Branch 2 not taken.
 20112180 pj[c] = p_[j][index_t((normal_axis + 1 + c) % 3)];
638
1/2
✓ Branch 1 taken 20112180 times.
✗ Branch 2 not taken.
 20112180 pk[c] = p_[k][index_t((normal_axis + 1 + c) % 3)];
639 }
640
1/2
✓ Branch 1 taken 10056090 times.
✗ Branch 2 not taken.
 20112180 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 145200 Sign dot3d(
650 TriangleRegion i, TriangleRegion j, TriangleRegion k
651 ) const {
652
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 145200 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 145200 geo_debug_assert(region_dim(i) == 0);
653
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 145200 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 145200 geo_debug_assert(region_dim(j) == 0);
654
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 145200 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 145200 geo_debug_assert(region_dim(k) == 0);
655 145200 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 562705 coord_index_t normal_axis(
666 TriangleRegion v1, TriangleRegion v2, TriangleRegion v3
667 ) {
668
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 562705 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 562705 geo_debug_assert(region_dim(v1) == 0);
669
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 562705 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 562705 geo_debug_assert(region_dim(v2) == 0);
670
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 562705 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 562705 geo_debug_assert(region_dim(v3) == 0);
671
672 562705 const vec3& p1 = p_[v1];
673 562705 const vec3& p2 = p_[v2];
674 562705 const vec3& p3 = p_[v3];
675
676 562705 return PCK::triangle_normal_axis(p1,p2,p3);
677 }
678
679
680 99460 bool points_are_identical(TriangleRegion i, TriangleRegion j) {
681
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 99460 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 99460 geo_debug_assert(region_dim(i) == 0);
682
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 99460 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 99460 geo_debug_assert(region_dim(j) == 0);
683 99460 const vec3& p1 = p_[i];
684 99460 const vec3& p2 = p_[j];
685 return
686 99460 (p1[0] == p2[0]) &&
687
4/4
✓ Branch 0 taken 61644 times.
✓ Branch 1 taken 37816 times.
✓ Branch 4 taken 54444 times.
✓ Branch 5 taken 7200 times.
 153904 (p1[1] == p2[1]) &&
688
2/2
✓ Branch 2 taken 52524 times.
✓ Branch 3 taken 1920 times.
 153904 (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 2014848 index_t triangle_dim(
698 TriangleRegion i, TriangleRegion j, TriangleRegion k
699 ) {
700
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 2014848 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 2014848 geo_debug_assert(region_dim(i) == 0);
701
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 2014848 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 2014848 geo_debug_assert(region_dim(j) == 0);
702
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 2014848 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 2014848 geo_debug_assert(region_dim(k) == 0);
703
704 2014848 const vec3& p1 = p_[i];
705 2014848 const vec3& p2 = p_[j];
706 2014848 const vec3& p3 = p_[k];
707
708
1/2
✓ Branch 4 taken 2014848 times.
✗ Branch 5 not taken.
 2014848 if(!PCK::aligned_3d(p1.data(), p2.data(), p3.data())) {
709 2014848 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 1007424 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 1007424 times.
✗ Branch 2 not taken.
 1007424 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 1007424 times.
✗ Branch 2 not taken.
 1007424 );
790
1/2
✓ Branch 1 taken 1007424 times.
✗ Branch 2 not taken.
 1007424 I.compute();
791 2014848 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 93242203 coord_index_t region_dim(TriangleRegion r) {
810
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 93242203 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 93242203 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 93242203 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 4427 times.
✓ Branch 1 taken 3746 times.
✓ Branch 2 taken 4725 times.
✓ Branch 3 taken 5951 times.
✓ Branch 4 taken 3638 times.
✓ Branch 5 taken 4003 times.
✓ Branch 6 taken 32382 times.
✓ Branch 7 taken 28797 times.
✓ Branch 8 taken 35682 times.
✓ Branch 9 taken 32854 times.
✓ Branch 10 taken 28581 times.
✓ Branch 11 taken 36316 times.
✓ Branch 12 taken 26007 times.
✓ Branch 13 taken 24423 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
 271532 switch(R) {
820 4427 case T1_RGN_P0:
821 4427 result = T2_RGN_P0;
822 4427 break;
823 3746 case T1_RGN_P1:
824 3746 result = T2_RGN_P1;
825 3746 break;
826 4725 case T1_RGN_P2:
827 4725 result = T2_RGN_P2;
828 4725 break;
829 5951 case T2_RGN_P0:
830 5951 result = T1_RGN_P0;
831 5951 break;
832 3638 case T2_RGN_P1:
833 3638 result = T1_RGN_P1;
834 3638 break;
835 4003 case T2_RGN_P2:
836 4003 result = T1_RGN_P2;
837 4003 break;
838 32382 case T1_RGN_E0:
839 32382 result = T2_RGN_E0;
840 32382 break;
841 28797 case T1_RGN_E1:
842 28797 result = T2_RGN_E1;
843 28797 break;
844 35682 case T1_RGN_E2:
845 35682 result = T2_RGN_E2;
846 35682 break;
847 32854 case T2_RGN_E0:
848 32854 result = T1_RGN_E0;
849 32854 break;
850 28581 case T2_RGN_E1:
851 28581 result = T1_RGN_E1;
852 28581 break;
853 36316 case T2_RGN_E2:
854 36316 result = T1_RGN_E2;
855 36316 break;
856 26007 case T1_RGN_T:
857 26007 result = T2_RGN_T;
858 26007 break;
859 24423 case T2_RGN_T:
860 24423 result = T1_RGN_T;
861 24423 break;
862 ✗ case T_RGN_NB:
863 ✗ geo_assert_not_reached;
864 }
865 271532 return result;
866 }
867
868 3243883 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 3243883 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 3243883 geo_debug_assert(region_dim(T) == 2);
873
2/3
✓ Branch 0 taken 1988821 times.
✓ Branch 1 taken 1255062 times.
✗ Branch 2 not taken.
 3243883 switch(T) {
874 1988821 case T1_RGN_T: {
875 1988821 p0 = T1_RGN_P0; p1 = T1_RGN_P1; p2 = T1_RGN_P2;
876 1988821 } break;
877 1255062 case T2_RGN_T: {
878 1255062 p0 = T2_RGN_P0; p1 = T2_RGN_P1; p2 = T2_RGN_P2;
879 1255062 } break;
880 ✗ default:
881 ✗ geo_assert_not_reached;
882 }
883 3243883 }
884
885 1749798 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 1749798 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 1749798 geo_debug_assert(region_dim(T) == 2);
890
2/3
✓ Branch 0 taken 874899 times.
✓ Branch 1 taken 874899 times.
✗ Branch 2 not taken.
 1749798 switch(T) {
891 874899 case T1_RGN_T: {
892 874899 e0 = T1_RGN_E0; e1 = T1_RGN_E1; e2 = T1_RGN_E2;
893 874899 } break;
894 874899 case T2_RGN_T: {
895 874899 e0 = T2_RGN_E0; e1 = T2_RGN_E1; e2 = T2_RGN_E2;
896 874899 } break;
897 ✗ default:
898 ✗ geo_assert_not_reached;
899 }
900 1749798 }
901
902 5264839 void get_edge_vertices(
903 TriangleRegion E, TriangleRegion& q0, TriangleRegion& q1
904 ) {
905
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 5264839 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 5264839 geo_debug_assert(region_dim(E) == 1);
906
6/7
✓ Branch 0 taken 887337 times.
✓ Branch 1 taken 875647 times.
✓ Branch 2 taken 877695 times.
✓ Branch 3 taken 872917 times.
✓ Branch 4 taken 878801 times.
✓ Branch 5 taken 872442 times.
✗ Branch 6 not taken.
 5264839 switch(E) {
907 887337 case T1_RGN_E0: {
908 887337 q0 = T1_RGN_P1;
909 887337 q1 = T1_RGN_P2;
910 887337 } break;
911 875647 case T1_RGN_E1: {
912 875647 q0 = T1_RGN_P2;
913 875647 q1 = T1_RGN_P0;
914 875647 } break;
915 877695 case T1_RGN_E2: {
916 877695 q0 = T1_RGN_P0;
917 877695 q1 = T1_RGN_P1;
918 877695 } break;
919 872917 case T2_RGN_E0: {
920 872917 q0 = T2_RGN_P1;
921 872917 q1 = T2_RGN_P2;
922 872917 } break;
923 878801 case T2_RGN_E1: {
924 878801 q0 = T2_RGN_P2;
925 878801 q1 = T2_RGN_P0;
926 878801 } break;
927 872442 case T2_RGN_E2: {
928 872442 q0 = T2_RGN_P0;
929 872442 q1 = T2_RGN_P1;
930 872442 } break;
931 ✗ default:
932 ✗ geo_assert_not_reached;
933 }
934 5264839 }
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 126144 times.
✓ Branch 2 taken 80149 times.
 206293 TriangleRegion R = is_in_T1(R1) ? T1_RGN_T : T2_RGN_T;
945
946
6/6
✓ Branch 1 taken 160498 times.
✓ Branch 2 taken 45795 times.
✓ Branch 4 taken 17152 times.
✓ Branch 5 taken 143346 times.
✓ Branch 6 taken 17152 times.
✓ Branch 7 taken 189141 times.
 206293 if(region_dim(R1) == 1 && region_dim(R2) == 0) {
947 TriangleRegion v1,v2;
948
1/2
✓ Branch 1 taken 17152 times.
✗ Branch 2 not taken.
 17152 get_edge_vertices(R1,v1,v2);
949
4/4
✓ Branch 0 taken 9483 times.
✓ Branch 1 taken 7669 times.
✓ Branch 2 taken 7576 times.
✓ Branch 3 taken 1907 times.
 17152 if(R2 == v1 || R2 == v2) {
950 15245 R = R1;
951 }
952
6/6
✓ Branch 1 taken 155176 times.
✓ Branch 2 taken 33965 times.
✓ Branch 4 taken 14648 times.
✓ Branch 5 taken 140528 times.
✓ Branch 6 taken 14648 times.
✓ Branch 7 taken 174493 times.
 189141 } else if(region_dim(R2) == 1 && region_dim(R1) == 0) {
953 TriangleRegion v1,v2;
954
1/2
✓ Branch 1 taken 14648 times.
✗ Branch 2 not taken.
 14648 get_edge_vertices(R2,v1,v2);
955
4/4
✓ Branch 0 taken 8346 times.
✓ Branch 1 taken 6302 times.
✓ Branch 2 taken 6397 times.
✓ Branch 3 taken 1949 times.
 14648 if(R1 == v1 || R1 == v2) {
956 12699 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 34411 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 34411 times.
✗ Branch 3 not taken.
 44648 }
963 ) {
964 TriangleRegion v1,v2;
965
1/2
✓ Branch 1 taken 34411 times.
✗ Branch 2 not taken.
 34411 get_edge_vertices(E,v1,v2);
966
8/8
✓ Branch 0 taken 6739 times.
✓ Branch 1 taken 27672 times.
✓ Branch 2 taken 2336 times.
✓ Branch 3 taken 4403 times.
✓ Branch 4 taken 8929 times.
✓ Branch 5 taken 21079 times.
✓ Branch 6 taken 5834 times.
✓ Branch 7 taken 3095 times.
 34411 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