| 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 | 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 0 taken 5888106 times.
✓ Branch 1 taken 981351 times.
|
6869457 | ) : result_(result) { |
| 105 | 981351 | p_[0] = p0; | |
| 106 | 981351 | p_[1] = p1; | |
| 107 | 981351 | p_[2] = p2; | |
| 108 | 981351 | p_[3] = q0; | |
| 109 | 981351 | p_[4] = q1; | |
| 110 | 981351 | p_[5] = q2; | |
| 111 |
2/2✓ Branch 0 taken 62806464 times.
✓ Branch 1 taken 981351 times.
|
63787815 | for(index_t i=0; i<64; ++i) { |
| 112 | 62806464 | o3d_cache_[i] = CACHE_UNINITIALIZED; | |
| 113 | } | ||
| 114 | 981351 | has_non_degenerate_intersection_ = false; | |
| 115 | 981351 | p_index_[0] = p0_index; | |
| 116 | 981351 | p_index_[1] = p1_index; | |
| 117 | 981351 | p_index_[2] = p2_index; | |
| 118 | 981351 | p_index_[3] = q0_index; | |
| 119 | 981351 | p_index_[4] = q1_index; | |
| 120 | 981351 | p_index_[5] = q2_index; | |
| 121 | 981351 | has_global_indices_ = true; | |
| 122 | } | ||
| 123 | |||
| 124 | 981351 | void compute() { | |
| 125 | #ifdef TT_DEBUG | ||
| 126 | Logger::out("TT") << "Call compute()" << std::endl; | ||
| 127 | #endif | ||
| 128 | |||
| 129 |
1/2✓ Branch 0 taken 981351 times.
✗ Branch 1 not taken.
|
981351 | if(result_ != nullptr) { |
| 130 | result_->resize(0); | ||
| 131 | } | ||
| 132 | |||
| 133 | // Test for degenerate triangles | ||
| 134 | if( | ||
| 135 |
2/4✓ Branch 1 taken 981351 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 981351 times.
|
1962702 | triangle_dim(T1_RGN_P0, T1_RGN_P1, T1_RGN_P2) != 2 || |
| 136 | 981351 | 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 981351 times.
✗ Branch 1 not taken.
|
981351 | if(has_global_indices_) { |
| 148 | |||
| 149 | 981351 | index_t q_index[3] = { | |
| 150 | NO_INDEX, NO_INDEX, NO_INDEX | ||
| 151 | }; | ||
| 152 | |||
| 153 |
2/2✓ Branch 0 taken 2944053 times.
✓ Branch 1 taken 981351 times.
|
3925404 | for(index_t i=0; i<3; ++i) { |
| 154 |
2/2✓ Branch 0 taken 8832159 times.
✓ Branch 1 taken 2944053 times.
|
11776212 | for(index_t j=0; j<3; ++j) { |
| 155 |
2/2✓ Branch 0 taken 881093 times.
✓ Branch 1 taken 7951066 times.
|
8832159 | if(p_index_[i+3] == p_index_[j]) { |
| 156 | 881093 | q_index[i] = j; | |
| 157 | } | ||
| 158 | } | ||
| 159 | } | ||
| 160 | |||
| 161 | // Early exit tests for configurations where 1 or 2 vertices | ||
| 162 | // are shared. | ||
| 163 | 981351 | int nb_shared = ( | |
| 164 | 981351 | (q_index[0] != NO_INDEX) + | |
| 165 | 981351 | (q_index[1] != NO_INDEX) + | |
| 166 | 981351 | (q_index[2] != NO_INDEX) ) ; | |
| 167 | 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 537057 times.
✓ Branch 1 taken 444294 times.
|
981351 | if(nb_shared == 1) { |
| 172 | 537057 | int shared_q = | |
| 173 |
2/2✓ Branch 0 taken 359869 times.
✓ Branch 1 taken 177188 times.
|
537057 | (q_index[1] != NO_INDEX) + (q_index[2] != NO_INDEX)*2; |
| 174 | geo_debug_assert(q_index[shared_q] != NO_INDEX); | ||
| 175 | 537057 | TriangleRegion q1 = | |
| 176 | 537057 | TriangleRegion(T2_RGN_P0 + ((shared_q+1))%3); | |
| 177 | 537057 | TriangleRegion q2 = | |
| 178 | 537057 | TriangleRegion(T2_RGN_P0 + ((shared_q+2))%3); | |
| 179 | TriangleRegion p1,p2,p3; | ||
| 180 | 537057 | get_triangle_vertices(T1_RGN_T, p1,p2,p3); | |
| 181 | 537057 | Sign o1 = orient3d(p1,p2,p3,q1); | |
| 182 | 537057 | Sign o2 = orient3d(p1,p2,p3,q2); | |
| 183 |
2/2✓ Branch 0 taken 447929 times.
✓ Branch 1 taken 89128 times.
|
537057 | if(int(o1)*int(o2) > 0) { |
| 184 | 447929 | 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 361404 times.
|
533422 | if(nb_shared == 2) { |
| 191 | 172018 | int non_shared_q = | |
| 192 |
2/2✓ Branch 0 taken 114076 times.
✓ Branch 1 taken 57942 times.
|
172018 | (q_index[1] == NO_INDEX) + (q_index[2] == NO_INDEX)*2; |
| 193 | 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 | 172018 | get_triangle_vertices(T1_RGN_T, p1,p2,p3); | |
| 197 |
2/2✓ Branch 1 taken 160286 times.
✓ Branch 2 taken 11732 times.
|
172018 | if(orient3d(p1,p2,p3,q) != ZERO) { |
| 198 | 160286 | 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 | 373136 | get_triangle_vertices(T1_RGN_T, p1,p2,p3); | |
| 210 | 373136 | get_triangle_vertices(T2_RGN_T, q1,q2,q3); | |
| 211 | 373136 | Sign o1 = orient3d(q1,q2,q3,p1); | |
| 212 | 373136 | Sign o2 = orient3d(q1,q2,q3,p2); | |
| 213 | 373136 | Sign o3 = orient3d(q1,q2,q3,p3); | |
| 214 | 373136 | if( | |
| 215 |
2/2✓ Branch 0 taken 133102 times.
✓ Branch 1 taken 240034 times.
|
373136 | int(o1)*int(o2) == 1 && |
| 216 |
2/2✓ Branch 0 taken 87898 times.
✓ Branch 1 taken 45204 times.
|
133102 | int(o2)*int(o3) == 1 && |
| 217 |
1/2✓ Branch 0 taken 87898 times.
✗ Branch 1 not taken.
|
87898 | int(o3)*int(o1) == 1 |
| 218 | ) { | ||
| 219 | 87898 | return; | |
| 220 | } | ||
| 221 | } | ||
| 222 | |||
| 223 | 285238 | intersect_edge_triangle(T1_RGN_E0, T2_RGN_T); | |
| 224 | ✗ | if(finished()) { return; } | |
| 225 | 285238 | intersect_edge_triangle(T1_RGN_E1, T2_RGN_T); | |
| 226 | ✗ | if(finished()) { return; } | |
| 227 | 285238 | intersect_edge_triangle(T1_RGN_E2, T2_RGN_T); | |
| 228 | ✗ | if(finished()) { return; } | |
| 229 | |||
| 230 | 285238 | intersect_edge_triangle(T2_RGN_E0, T1_RGN_T); | |
| 231 | ✗ | if(finished()) { return; } | |
| 232 | 285238 | intersect_edge_triangle(T2_RGN_E1, T1_RGN_T); | |
| 233 | ✗ | if(finished()) { return; } | |
| 234 | 285238 | intersect_edge_triangle(T2_RGN_E2, T1_RGN_T); | |
| 235 | ✗ | if(finished()) { return; } | |
| 236 | |||
| 237 | // The same intersection can appear several times, | ||
| 238 | // remove the duplicates | ||
| 239 |
1/2✓ Branch 0 taken 285238 times.
✗ Branch 1 not taken.
|
285238 | if(result_ != nullptr) { |
| 240 | std::sort(result_->begin(), result_->end()); | ||
| 241 | auto p = std::unique(result_->begin(), result_->end()); | ||
| 242 | 285238 | 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 | bool has_non_degenerate_intersection() const { | ||
| 261 | 981351 | 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 | bool finished() const { | ||
| 272 | #ifdef TT_DEBUG | ||
| 273 | return false; | ||
| 274 | #endif | ||
| 275 |
11/34✗ Branch 0 not taken.
✓ Branch 1 taken 8310 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8310 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 562659 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 562659 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 562659 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 285238 times.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 285238 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✓ Branch 19 taken 285238 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✓ Branch 23 taken 285238 times.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✓ Branch 27 taken 285238 times.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✓ Branch 31 taken 285238 times.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
|
3416025 | return (result_ == nullptr && has_non_degenerate_intersection_); |
| 276 | } | ||
| 277 | |||
| 278 | 1711428 | 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 | geo_debug_assert(region_dim(E) == 1); | ||
| 286 | geo_debug_assert(region_dim(T) == 2); | ||
| 287 | |||
| 288 | TriangleRegion R1 = E; | ||
| 289 | TriangleRegion R2 = T; | ||
| 290 | |||
| 291 | TriangleRegion p1,p2,p3; | ||
| 292 | TriangleRegion e1,e2,e3; | ||
| 293 | TriangleRegion q1,q2; | ||
| 294 | |||
| 295 | 1711428 | get_triangle_vertices(T,p1,p2,p3); | |
| 296 | 1711428 | get_triangle_edges(T,e1,e2,e3); | |
| 297 | 1711428 | get_edge_vertices(E,q1,q2); | |
| 298 | |||
| 299 | 1711428 | Sign o1 = orient3d(p1,p2,p3,q1); | |
| 300 | 1711428 | 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 1368604 times.
✓ Branch 1 taken 342824 times.
|
1711428 | if(int(o1) * int(o2) == 1) { |
| 306 | 632408 | return; | |
| 307 | } | ||
| 308 | |||
| 309 |
2/2✓ Branch 0 taken 562659 times.
✓ Branch 1 taken 805945 times.
|
1368604 | 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 | 1125318 | index_t nax = normal_axis(p1,p2,p3); | |
| 315 | |||
| 316 | // Test whether the extremities of the segment | ||
| 317 | // are in the triangle | ||
| 318 | { | ||
| 319 | 562659 | Sign a1 = orient2d(q1,p1,p2,nax); | |
| 320 | 562659 | Sign a2 = orient2d(q1,p2,p3,nax); | |
| 321 | 562659 | Sign a3 = orient2d(q1,p3,p1,nax); | |
| 322 | |||
| 323 | 562659 | Sign b1 = orient2d(q2,p1,p2,nax); | |
| 324 | 562659 | Sign b2 = orient2d(q2,p2,p3,nax); | |
| 325 | 562659 | Sign b3 = orient2d(q2,p3,p1,nax); | |
| 326 | |||
| 327 | 562659 | if( | |
| 328 |
2/2✓ Branch 0 taken 118462 times.
✓ Branch 1 taken 444197 times.
|
562659 | int(a1)*int(a2) > 0 && |
| 329 |
2/2✓ Branch 0 taken 8310 times.
✓ Branch 1 taken 110152 times.
|
118462 | 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 | 8310 | add_intersection(q1,T); | |
| 333 | ✗ | if(finished()) { return; } | |
| 334 | } | ||
| 335 | |||
| 336 | 562659 | if( | |
| 337 |
2/2✓ Branch 0 taken 117688 times.
✓ Branch 1 taken 444971 times.
|
562659 | int(b1)*int(b2) > 0 && |
| 338 |
2/2✓ Branch 0 taken 8310 times.
✓ Branch 1 taken 109378 times.
|
117688 | 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 | 8310 | add_intersection(q2,T); | |
| 342 | ✗ | if(finished()) { return; } | |
| 343 | } | ||
| 344 | } | ||
| 345 | |||
| 346 | 562659 | intersect_edge_edge_2d(E,e1,nax); | |
| 347 | ✗ | if(finished()) { return; } | |
| 348 | 562659 | intersect_edge_edge_2d(E,e2,nax); | |
| 349 | ✗ | if(finished()) { return; } | |
| 350 | 562659 | intersect_edge_edge_2d(E,e3,nax); | |
| 351 | ✗ | if(finished()) { return; } | |
| 352 | |||
| 353 | } 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 243258 times.
✓ Branch 1 taken 562687 times.
|
805945 | if(o1 == ZERO) { |
| 361 | 243258 | R1 = q1; | |
| 362 |
2/2✓ Branch 0 taken 243258 times.
✓ Branch 1 taken 319429 times.
|
562687 | } else if(o2 == ZERO) { |
| 363 | 243258 | R1 = q2; | |
| 364 | } | ||
| 365 | |||
| 366 | 805945 | Sign oo1 = orient3d(p2,p3,q1,q2); | |
| 367 | 805945 | Sign oo2 = orient3d(p3,p1,q1,q2); | |
| 368 | |||
| 369 |
2/2✓ Branch 0 taken 516361 times.
✓ Branch 1 taken 289584 times.
|
805945 | if(int(oo1)*int(oo2) == -1) { |
| 370 | return; | ||
| 371 | } | ||
| 372 | |||
| 373 | 516361 | 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 | 516361 | int nb_zeros = (oo1 == ZERO) + (oo2 == ZERO) + (oo3 == ZERO); | |
| 379 | geo_debug_assert(nb_zeros != 3); | ||
| 380 |
2/2✓ Branch 0 taken 45473 times.
✓ Branch 1 taken 470888 times.
|
516361 | if(nb_zeros == 1) { |
| 381 |
2/2✓ Branch 0 taken 22328 times.
✓ Branch 1 taken 23145 times.
|
45473 | if(oo1 == ZERO) { |
| 382 | 22328 | R2 = e1; | |
| 383 |
2/2✓ Branch 0 taken 18913 times.
✓ Branch 1 taken 4232 times.
|
23145 | } else if(oo2 == ZERO) { |
| 384 | 18913 | R2 = e2; | |
| 385 | } else { | ||
| 386 | 4232 | R2 = e3; | |
| 387 | } | ||
| 388 |
2/2✓ Branch 0 taken 267262 times.
✓ Branch 1 taken 203626 times.
|
470888 | } else if(nb_zeros == 2) { |
| 389 |
2/2✓ Branch 0 taken 84868 times.
✓ Branch 1 taken 182394 times.
|
267262 | if(oo1 != ZERO) { |
| 390 | 84868 | R2 = p1; | |
| 391 |
2/2✓ Branch 0 taken 87496 times.
✓ Branch 1 taken 94898 times.
|
182394 | } else if(oo2 != ZERO) { |
| 392 | 87496 | R2 = p2; | |
| 393 | } else { | ||
| 394 | 94898 | 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 | bool outside = | ||
| 407 | 516361 | (int(oo1) * int(oo2) == -1) || | |
| 408 |
2/2✓ Branch 0 taken 334469 times.
✓ Branch 1 taken 181892 times.
|
516361 | (int(oo2) * int(oo3) == -1) || |
| 409 |
2/2✓ Branch 0 taken 321054 times.
✓ Branch 1 taken 13415 times.
|
334469 | (int(oo3) * int(oo1) == -1) ; |
| 410 | |||
| 411 | if(!outside) { | ||
| 412 | 321054 | add_intersection(R1,R2); | |
| 413 | } | ||
| 414 | } | ||
| 415 | } | ||
| 416 | |||
| 417 | |||
| 418 | 1687977 | 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 | geo_debug_assert(region_dim(E1) == 1); | ||
| 426 | geo_debug_assert(region_dim(E2) == 1); | ||
| 427 | |||
| 428 | TriangleRegion R1 = E1; | ||
| 429 | TriangleRegion R2 = E2; | ||
| 430 | |||
| 431 | TriangleRegion p1,p2; | ||
| 432 | 1687977 | get_edge_vertices(E1,p1,p2); | |
| 433 | |||
| 434 | TriangleRegion q1,q2; | ||
| 435 | 1687977 | get_edge_vertices(E2,q1,q2); | |
| 436 | |||
| 437 | 1687977 | Sign a1 = orient2d(q1,q2,p1,nax); | |
| 438 | 1687977 | Sign a2 = orient2d(q1,q2,p2,nax); | |
| 439 | |||
| 440 |
2/2✓ Branch 0 taken 36296 times.
✓ Branch 1 taken 1651681 times.
|
1687977 | if(a1 == ZERO && a2 == ZERO) { |
| 441 | // Special case: 1D | ||
| 442 | // (the 2x2 edge extremities are aligned) | ||
| 443 | 36296 | 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 168157 times.
✓ Branch 1 taken 1483524 times.
|
1651681 | if(a1 == ZERO) { |
| 448 | 168157 | R1 = p1; | |
| 449 |
2/2✓ Branch 0 taken 168251 times.
✓ Branch 1 taken 1315273 times.
|
1483524 | } else if(a2 == ZERO) { |
| 450 | 168251 | R1 = p2; | |
| 451 | } | ||
| 452 | |||
| 453 | 1651681 | Sign b1 = orient2d(p1,p2,q1,nax); | |
| 454 | 1651681 | 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 177605 times.
✓ Branch 1 taken 1474076 times.
|
1651681 | if(b1 == ZERO) { |
| 459 | 177605 | R2 = q1; | |
| 460 |
2/2✓ Branch 0 taken 177605 times.
✓ Branch 1 taken 1296471 times.
|
1474076 | } else if(b2 == ZERO) { |
| 461 | 177605 | R2 = q2; | |
| 462 | } | ||
| 463 | |||
| 464 |
4/4✓ Branch 0 taken 512402 times.
✓ Branch 1 taken 1139279 times.
✓ Branch 2 taken 396250 times.
✓ Branch 3 taken 116152 times.
|
1651681 | if( int(a1)*int(a2) != 1 && int(b1)*int(b2) != 1) { |
| 465 | 396250 | add_intersection(R1,R2); | |
| 466 | } | ||
| 467 | } | ||
| 468 | 1687977 | } | |
| 469 | |||
| 470 | 36296 | 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 | geo_debug_assert(region_dim(E1) == 1); | ||
| 478 | geo_debug_assert(region_dim(E2) == 1); | ||
| 479 | |||
| 480 | TriangleRegion p1,p2; | ||
| 481 | 36296 | get_edge_vertices(E1,p1,p2); | |
| 482 | |||
| 483 | TriangleRegion q1,q2; | ||
| 484 | 36296 | get_edge_vertices(E2,q1,q2); | |
| 485 | |||
| 486 | 36296 | Sign d1 = dot3d(p1,q1,q2); | |
| 487 | 36296 | Sign d2 = dot3d(p2,q1,q2); | |
| 488 | 36296 | Sign d3 = dot3d(q1,p1,p2); | |
| 489 | 36296 | 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 |
2/2✓ Branch 0 taken 24860 times.
✓ Branch 1 taken 11436 times.
|
36296 | if(d1 == ZERO && d3 == ZERO && points_are_identical(p1,q1)) { |
| 497 | 1458 | add_intersection(p1,q1); | |
| 498 | } | ||
| 499 | |||
| 500 |
2/2✓ Branch 0 taken 24861 times.
✓ Branch 1 taken 11435 times.
|
36296 | if(d2 == ZERO && d3 == ZERO && points_are_identical(p2,q1)) { |
| 501 | 24799 | add_intersection(p2,q1); | |
| 502 | } | ||
| 503 | |||
| 504 |
2/2✓ Branch 0 taken 24861 times.
✓ Branch 1 taken 11435 times.
|
36296 | if(d1 == ZERO && d4 == ZERO && points_are_identical(p1,q2)) { |
| 505 | 24799 | add_intersection(p1,q2); | |
| 506 | } | ||
| 507 | |||
| 508 |
2/2✓ Branch 0 taken 24862 times.
✓ Branch 1 taken 11434 times.
|
36296 | if(d2 == ZERO && d4 == ZERO && points_are_identical(p2,q2)) { |
| 509 | 1460 | 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 36118 times.
|
36296 | if(d1 == NEGATIVE) { |
| 516 | 178 | add_intersection(p1,E2); | |
| 517 | } | ||
| 518 | |||
| 519 |
2/2✓ Branch 0 taken 178 times.
✓ Branch 1 taken 36118 times.
|
36296 | if(d2 == NEGATIVE) { |
| 520 | 178 | add_intersection(p2,E2); | |
| 521 | } | ||
| 522 | |||
| 523 |
2/2✓ Branch 0 taken 178 times.
✓ Branch 1 taken 36118 times.
|
36296 | if(d3 == NEGATIVE) { |
| 524 | 178 | add_intersection(E1,q1); | |
| 525 | } | ||
| 526 | |||
| 527 |
2/2✓ Branch 0 taken 178 times.
✓ Branch 1 taken 36118 times.
|
36296 | if(d4 == NEGATIVE) { |
| 528 | 178 | add_intersection(E1,q2); | |
| 529 | } | ||
| 530 | 36296 | } | |
| 531 | |||
| 532 | 787152 | 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 |
4/4✓ Branch 1 taken 665764 times.
✓ Branch 2 taken 121388 times.
✓ Branch 4 taken 31586 times.
✓ Branch 5 taken 634178 times.
|
787152 | if(region_dim(R1) >= 1 || region_dim(R2) >= 1) { |
| 538 | 152974 | has_non_degenerate_intersection_ = true; | |
| 539 | } | ||
| 540 | if(is_in_T1(R1)) { | ||
| 541 | geo_debug_assert(!is_in_T1(R2)); | ||
| 542 |
1/2✓ Branch 0 taken 381323 times.
✗ Branch 1 not taken.
|
381323 | if(result_ != nullptr) { |
| 543 | 381323 | result_->push_back(std::make_pair(R1,R2)); | |
| 544 | } | ||
| 545 | } else { | ||
| 546 | geo_debug_assert(is_in_T1(R2)); | ||
| 547 |
1/2✓ Branch 0 taken 405829 times.
✗ Branch 1 not taken.
|
405829 | if(result_ != nullptr) { |
| 548 | 405829 | result_->push_back(std::make_pair(R2,R1)); | |
| 549 | } | ||
| 550 | } | ||
| 551 | 787152 | } | |
| 552 | |||
| 553 | 7916647 | Sign orient3d( | |
| 554 | TriangleRegion i, TriangleRegion j, | ||
| 555 | TriangleRegion k, TriangleRegion l | ||
| 556 | ) const { | ||
| 557 | |||
| 558 | geo_debug_assert(region_dim(i) == 0); | ||
| 559 | geo_debug_assert(region_dim(j) == 0); | ||
| 560 | geo_debug_assert(region_dim(k) == 0); | ||
| 561 | geo_debug_assert(region_dim(l) == 0); | ||
| 562 | |||
| 563 | // Index for the cache (1 bit set for | ||
| 564 | // each vertex) | ||
| 565 | |||
| 566 | 7916647 | index_t o3d_idx = | |
| 567 | 7916647 | (1u << index_t(i)) | | |
| 568 | 7916647 | (1u << index_t(j)) | | |
| 569 | 7916647 | (1u << index_t(k)) | | |
| 570 | 7916647 | (1u << index_t(l)) ; | |
| 571 | |||
| 572 | 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 | 7916647 | 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 4471737 times.
✓ Branch 1 taken 3444910 times.
|
7916647 | if(o3d_cache_[o3d_idx] == CACHE_UNINITIALIZED) { |
| 582 |
2/2✓ Branch 0 taken 1777203 times.
✓ Branch 1 taken 2694534 times.
|
4471737 | int o = flip ? -int(PCK::orient_3d(p_[i],p_[j],p_[k],p_[l])) : |
| 583 | 4471737 | int(PCK::orient_3d(p_[i],p_[j],p_[k],p_[l])) ; | |
| 584 | 4471737 | o3d_cache_[o3d_idx] = Numeric::int8(o); | |
| 585 | } | ||
| 586 | |||
| 587 | // Get result from the cache | ||
| 588 | |||
| 589 |
2/2✓ Branch 0 taken 3802405 times.
✓ Branch 1 taken 4114242 times.
|
7916647 | Sign result = flip ? Sign(-o3d_cache_[o3d_idx]) |
| 590 | 4114242 | : Sign( o3d_cache_[o3d_idx]); | |
| 591 | |||
| 592 | // Sanity check: did our cache return the same result as | ||
| 593 | // directly calling the predicate ? | ||
| 594 | geo_debug_assert( | ||
| 595 | result == PCK::orient_3d(p_[i], p_[j], p_[k], p_[l]) | ||
| 596 | ); | ||
| 597 | |||
| 598 | 7916647 | 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 | 7916647 | 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 | 7916647 | index_t tab[4] = { i, j, k, l }; | |
| 610 | constexpr int N = 4; | ||
| 611 | bool result = false; | ||
| 612 |
2/2✓ Branch 0 taken 23749941 times.
✓ Branch 1 taken 7916647 times.
|
31666588 | for (int I = 0; I < N - 1; ++I) { |
| 613 |
2/2✓ Branch 0 taken 47499882 times.
✓ Branch 1 taken 23749941 times.
|
71249823 | for (int J = 0; J < N - I - 1; ++J) { |
| 614 |
2/2✓ Branch 0 taken 14427515 times.
✓ Branch 1 taken 33072367 times.
|
47499882 | if (tab[J] > tab[J + 1]) { |
| 615 | std::swap(tab[J], tab[J + 1]); | ||
| 616 | 14427515 | result = !result; | |
| 617 | } | ||
| 618 | } | ||
| 619 | } | ||
| 620 | 7916647 | return result; | |
| 621 | } | ||
| 622 | |||
| 623 | 10055270 | 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 | geo_debug_assert(region_dim(i) == 0); | ||
| 630 | geo_debug_assert(region_dim(j) == 0); | ||
| 631 | 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 20110540 times.
✓ Branch 1 taken 10055270 times.
|
30165810 | for(coord_index_t c = 0; c < 2; c++) { |
| 636 | 20110540 | pi[c] = p_[i][index_t((normal_axis + 1 + c) % 3)]; | |
| 637 | 20110540 | pj[c] = p_[j][index_t((normal_axis + 1 + c) % 3)]; | |
| 638 | 20110540 | pk[c] = p_[k][index_t((normal_axis + 1 + c) % 3)]; | |
| 639 | } | ||
| 640 | 10055270 | 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 | Sign dot3d( | ||
| 650 | TriangleRegion i, TriangleRegion j, TriangleRegion k | ||
| 651 | ) const { | ||
| 652 | geo_debug_assert(region_dim(i) == 0); | ||
| 653 | geo_debug_assert(region_dim(j) == 0); | ||
| 654 | geo_debug_assert(region_dim(k) == 0); | ||
| 655 | 36296 | 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 | coord_index_t normal_axis( | ||
| 666 | TriangleRegion v1, TriangleRegion v2, TriangleRegion v3 | ||
| 667 | ) { | ||
| 668 | geo_debug_assert(region_dim(v1) == 0); | ||
| 669 | geo_debug_assert(region_dim(v2) == 0); | ||
| 670 | geo_debug_assert(region_dim(v3) == 0); | ||
| 671 | |||
| 672 | 562659 | const vec3& p1 = p_[v1]; | |
| 673 | 562659 | const vec3& p2 = p_[v2]; | |
| 674 | 562659 | const vec3& p3 = p_[v3]; | |
| 675 | |||
| 676 | 562659 | return PCK::triangle_normal_axis(p1,p2,p3); | |
| 677 | } | ||
| 678 | |||
| 679 | |||
| 680 | bool points_are_identical(TriangleRegion i, TriangleRegion j) { | ||
| 681 | geo_debug_assert(region_dim(i) == 0); | ||
| 682 | geo_debug_assert(region_dim(j) == 0); | ||
| 683 | 99444 | const vec3& p1 = p_[i]; | |
| 684 | 99444 | const vec3& p2 = p_[j]; | |
| 685 | return | ||
| 686 | 161080 | (p1[0] == p2[0]) && | |
| 687 |
16/24✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 5992 times.
✓ Branch 9 taken 18868 times.
✓ Branch 10 taken 2414 times.
✓ Branch 11 taken 3578 times.
✓ Branch 12 taken 24825 times.
✓ Branch 13 taken 36 times.
✓ Branch 14 taken 24803 times.
✓ Branch 15 taken 22 times.
✓ Branch 16 taken 24825 times.
✓ Branch 17 taken 36 times.
✓ Branch 18 taken 24803 times.
✓ Branch 19 taken 22 times.
✓ Branch 20 taken 5994 times.
✓ Branch 21 taken 18868 times.
✓ Branch 22 taken 2416 times.
✓ Branch 23 taken 3578 times.
|
99444 | (p1[1] == p2[1]) && |
| 688 |
8/12✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1458 times.
✓ Branch 5 taken 956 times.
✓ Branch 6 taken 24799 times.
✓ Branch 7 taken 4 times.
✓ Branch 8 taken 24799 times.
✓ Branch 9 taken 4 times.
✓ Branch 10 taken 1460 times.
✓ Branch 11 taken 956 times.
|
54436 | (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 | 1962702 | index_t triangle_dim( | |
| 698 | TriangleRegion i, TriangleRegion j, TriangleRegion k | ||
| 699 | ) { | ||
| 700 | geo_debug_assert(region_dim(i) == 0); | ||
| 701 | geo_debug_assert(region_dim(j) == 0); | ||
| 702 | geo_debug_assert(region_dim(k) == 0); | ||
| 703 | |||
| 704 | 1962702 | const vec3& p1 = p_[i]; | |
| 705 | 1962702 | const vec3& p2 = p_[j]; | |
| 706 | 1962702 | const vec3& p3 = p_[k]; | |
| 707 | |||
| 708 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1962702 times.
|
1962702 | if(!PCK::aligned_3d(p1.data(), p2.data(), p3.data())) { |
| 709 | 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 | 981351 | 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 | 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 | ); | ||
| 790 | 981351 | I.compute(); | |
| 791 | 981351 | 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 | 4854310 | coord_index_t region_dim(TriangleRegion r) { | |
| 810 | 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 | 4854310 | return trgl_rgn_dim[index_t(r)]; | |
| 815 | } | ||
| 816 | |||
| 817 | 271528 | TriangleRegion swap_T1_T2(TriangleRegion R) { | |
| 818 | TriangleRegion result=T_RGN_NB; | ||
| 819 |
14/16✓ Branch 0 taken 4376 times.
✓ Branch 1 taken 3696 times.
✓ Branch 2 taken 4669 times.
✓ Branch 3 taken 6000 times.
✓ Branch 4 taken 3688 times.
✓ Branch 5 taken 4061 times.
✓ Branch 6 taken 32379 times.
✓ Branch 7 taken 28805 times.
✓ Branch 8 taken 35697 times.
✓ Branch 9 taken 32844 times.
✓ Branch 10 taken 28576 times.
✓ Branch 11 taken 36309 times.
✓ Branch 12 taken 26142 times.
✓ Branch 13 taken 24286 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
|
271528 | switch(R) { |
| 820 | 4376 | case T1_RGN_P0: | |
| 821 | result = T2_RGN_P0; | ||
| 822 | 4376 | break; | |
| 823 | 3696 | case T1_RGN_P1: | |
| 824 | result = T2_RGN_P1; | ||
| 825 | 3696 | break; | |
| 826 | 4669 | case T1_RGN_P2: | |
| 827 | result = T2_RGN_P2; | ||
| 828 | 4669 | break; | |
| 829 | 6000 | case T2_RGN_P0: | |
| 830 | result = T1_RGN_P0; | ||
| 831 | 6000 | break; | |
| 832 | 3688 | case T2_RGN_P1: | |
| 833 | result = T1_RGN_P1; | ||
| 834 | 3688 | break; | |
| 835 | 4061 | case T2_RGN_P2: | |
| 836 | result = T1_RGN_P2; | ||
| 837 | 4061 | break; | |
| 838 | 32379 | case T1_RGN_E0: | |
| 839 | result = T2_RGN_E0; | ||
| 840 | 32379 | break; | |
| 841 | 28805 | case T1_RGN_E1: | |
| 842 | result = T2_RGN_E1; | ||
| 843 | 28805 | break; | |
| 844 | 35697 | case T1_RGN_E2: | |
| 845 | result = T2_RGN_E2; | ||
| 846 | 35697 | break; | |
| 847 | 32844 | case T2_RGN_E0: | |
| 848 | result = T1_RGN_E0; | ||
| 849 | 32844 | break; | |
| 850 | 28576 | case T2_RGN_E1: | |
| 851 | result = T1_RGN_E1; | ||
| 852 | 28576 | break; | |
| 853 | 36309 | case T2_RGN_E2: | |
| 854 | result = T1_RGN_E2; | ||
| 855 | 36309 | break; | |
| 856 | 26142 | case T1_RGN_T: | |
| 857 | result = T2_RGN_T; | ||
| 858 | 26142 | break; | |
| 859 | 24286 | case T2_RGN_T: | |
| 860 | result = T1_RGN_T; | ||
| 861 | 24286 | break; | |
| 862 | case T_RGN_NB: | ||
| 863 | ✗ | geo_assert_not_reached; | |
| 864 | } | ||
| 865 | 271528 | return result; | |
| 866 | } | ||
| 867 | |||
| 868 | 3166775 | void get_triangle_vertices( | |
| 869 | TriangleRegion T, | ||
| 870 | TriangleRegion& p0, TriangleRegion& p1, TriangleRegion& p2 | ||
| 871 | ) { | ||
| 872 | geo_debug_assert(region_dim(T) == 2); | ||
| 873 |
2/3✓ Branch 0 taken 1937925 times.
✓ Branch 1 taken 1228850 times.
✗ Branch 2 not taken.
|
3166775 | switch(T) { |
| 874 | 1937925 | case T1_RGN_T: { | |
| 875 | 1937925 | p0 = T1_RGN_P0; p1 = T1_RGN_P1; p2 = T1_RGN_P2; | |
| 876 | 1937925 | } break; | |
| 877 | 1228850 | case T2_RGN_T: { | |
| 878 | 1228850 | p0 = T2_RGN_P0; p1 = T2_RGN_P1; p2 = T2_RGN_P2; | |
| 879 | 1228850 | } break; | |
| 880 | default: | ||
| 881 | ✗ | geo_assert_not_reached; | |
| 882 | } | ||
| 883 | 3166775 | } | |
| 884 | |||
| 885 | 1711428 | void get_triangle_edges( | |
| 886 | TriangleRegion T, | ||
| 887 | TriangleRegion& e0, TriangleRegion& e1, TriangleRegion& e2 | ||
| 888 | ) { | ||
| 889 | geo_debug_assert(region_dim(T) == 2); | ||
| 890 |
2/3✓ Branch 0 taken 855714 times.
✓ Branch 1 taken 855714 times.
✗ Branch 2 not taken.
|
1711428 | switch(T) { |
| 891 | 855714 | case T1_RGN_T: { | |
| 892 | 855714 | e0 = T1_RGN_E0; e1 = T1_RGN_E1; e2 = T1_RGN_E2; | |
| 893 | 855714 | } break; | |
| 894 | 855714 | case T2_RGN_T: { | |
| 895 | 855714 | e0 = T2_RGN_E0; e1 = T2_RGN_E1; e2 = T2_RGN_E2; | |
| 896 | 855714 | } break; | |
| 897 | default: | ||
| 898 | ✗ | geo_assert_not_reached; | |
| 899 | } | ||
| 900 | 1711428 | } | |
| 901 | |||
| 902 | 5226374 | void get_edge_vertices( | |
| 903 | TriangleRegion E, TriangleRegion& q0, TriangleRegion& q1 | ||
| 904 | ) { | ||
| 905 | geo_debug_assert(region_dim(E) == 1); | ||
| 906 |
6/7✓ Branch 0 taken 880950 times.
✓ Branch 1 taken 869218 times.
✓ Branch 2 taken 871249 times.
✓ Branch 3 taken 866497 times.
✓ Branch 4 taken 872573 times.
✓ Branch 5 taken 865887 times.
✗ Branch 6 not taken.
|
5226374 | switch(E) { |
| 907 | 880950 | case T1_RGN_E0: { | |
| 908 | 880950 | q0 = T1_RGN_P1; | |
| 909 | 880950 | q1 = T1_RGN_P2; | |
| 910 | 880950 | } break; | |
| 911 | 869218 | case T1_RGN_E1: { | |
| 912 | 869218 | q0 = T1_RGN_P2; | |
| 913 | 869218 | q1 = T1_RGN_P0; | |
| 914 | 869218 | } break; | |
| 915 | 871249 | case T1_RGN_E2: { | |
| 916 | 871249 | q0 = T1_RGN_P0; | |
| 917 | 871249 | q1 = T1_RGN_P1; | |
| 918 | 871249 | } break; | |
| 919 | 866497 | case T2_RGN_E0: { | |
| 920 | 866497 | q0 = T2_RGN_P1; | |
| 921 | 866497 | q1 = T2_RGN_P2; | |
| 922 | 866497 | } break; | |
| 923 | 872573 | case T2_RGN_E1: { | |
| 924 | 872573 | q0 = T2_RGN_P2; | |
| 925 | 872573 | q1 = T2_RGN_P0; | |
| 926 | 872573 | } break; | |
| 927 | 865887 | case T2_RGN_E2: { | |
| 928 | 865887 | q0 = T2_RGN_P0; | |
| 929 | 865887 | q1 = T2_RGN_P1; | |
| 930 | 865887 | } break; | |
| 931 | default: | ||
| 932 | ✗ | geo_assert_not_reached; | |
| 933 | }; | ||
| 934 | 5226374 | } | |
| 935 | |||
| 936 | 328512 | TriangleRegion GEOGRAM_API regions_convex_hull( | |
| 937 | TriangleRegion R1, TriangleRegion R2 | ||
| 938 | ) { | ||
| 939 | geo_debug_assert(is_in_T1(R1) == is_in_T1(R2)); | ||
| 940 |
2/2✓ Branch 0 taken 206287 times.
✓ Branch 1 taken 122225 times.
|
328512 | if(R1 == R2) { |
| 941 | return R1; | ||
| 942 | } | ||
| 943 | |||
| 944 | TriangleRegion R = is_in_T1(R1) ? T1_RGN_T : T2_RGN_T; | ||
| 945 | |||
| 946 |
4/4✓ Branch 1 taken 160509 times.
✓ Branch 2 taken 45778 times.
✓ Branch 4 taken 143348 times.
✓ Branch 5 taken 17161 times.
|
206287 | if(region_dim(R1) == 1 && region_dim(R2) == 0) { |
| 947 | TriangleRegion v1,v2; | ||
| 948 | 17161 | get_edge_vertices(R1,v1,v2); | |
| 949 |
4/4✓ Branch 0 taken 9483 times.
✓ Branch 1 taken 7678 times.
✓ Branch 2 taken 7578 times.
✓ Branch 3 taken 1905 times.
|
17161 | if(R2 == v1 || R2 == v2) { |
| 950 | R = R1; | ||
| 951 | } | ||
| 952 |
4/4✓ Branch 1 taken 155161 times.
✓ Branch 2 taken 33965 times.
✓ Branch 4 taken 140522 times.
✓ Branch 5 taken 14639 times.
|
189126 | } else if(region_dim(R2) == 1 && region_dim(R1) == 0) { |
| 953 | TriangleRegion v1,v2; | ||
| 954 | 14639 | get_edge_vertices(R2,v1,v2); | |
| 955 |
4/4✓ Branch 0 taken 8346 times.
✓ Branch 1 taken 6293 times.
✓ Branch 2 taken 6395 times.
✓ Branch 3 taken 1951 times.
|
14639 | if(R1 == v1 || R1 == v2) { |
| 956 | R = R2; | ||
| 957 | } | ||
| 958 |
4/4✓ Branch 1 taken 10419 times.
✓ Branch 2 taken 164068 times.
✓ Branch 4 taken 10237 times.
✓ Branch 5 taken 182 times.
|
174487 | } else if(region_dim(R1) == 0 && region_dim(R2) == 0) { |
| 959 | 24363 | 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 0 taken 34600 times.
✗ Branch 1 not taken.
|
34600 | } |
| 963 | ) { | ||
| 964 | TriangleRegion v1,v2; | ||
| 965 | 34600 | get_edge_vertices(E,v1,v2); | |
| 966 |
8/8✓ Branch 0 taken 6742 times.
✓ Branch 1 taken 27858 times.
✓ Branch 2 taken 2336 times.
✓ Branch 3 taken 4406 times.
✓ Branch 4 taken 8929 times.
✓ Branch 5 taken 21265 times.
✓ Branch 6 taken 5831 times.
✓ Branch 7 taken 3098 times.
|
34600 | if((R1 == v1 && R2 == v2) || (R1 == v2 && R2 == v1)) { |
| 967 | R = E; | ||
| 968 | 10237 | break; | |
| 969 | } | ||
| 970 | } | ||
| 971 | } | ||
| 972 | |||
| 973 | return R; | ||
| 974 | } | ||
| 975 | |||
| 976 | } | ||
| 977 |