GCC Code Coverage Report

Directory: ./
File: lib/geogram/mesh/mesh_repair.cpp
Date: 2026-09-07 02:36:43
Exec Total Coverage
Lines: 437 568 76.9%
Functions: 24 31 77.4%
Branches: 439 936 46.9%
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/mesh_repair.h>
41 #include <geogram/mesh/mesh_geometry.h>
42 #include <geogram/mesh/index.h>
43 #include <geogram/mesh/mesh_halfedges.h>
44 #include <geogram/mesh/mesh_io.h>
45 #include <geogram/mesh/mesh_preprocessing.h>
46 #include <geogram/points/colocate.h>
47 #include <geogram/basic/geometry_nd.h>
48 #include <geogram/basic/stopwatch.h>
49 #include <geogram/basic/command_line.h>
50 #include <geogram/basic/argused.h>
51 #include <geogram/basic/algorithm.h>
52
53 #include <stack>
54 #include <queue>
55
56 namespace {
57
58 using namespace GEO;
59
60 /**
61 * \brief Tests whether a facet is degenerate.
62 * \param[in] M the mesh that the facet belongs to
63 * \param[in] f the index of the facet in \p M
64 * \return true if facet \p f has duplicated vertices,
65 * false otherwise
66 */
67 918622 bool facet_is_degenerate(const Mesh& M, index_t f) {
68 918622 index_t nb_vertices = M.facets.nb_vertices(f);
69
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 918622 times.
 918622 if(nb_vertices != 3) {
70 ✗ index_t* vertices = (index_t*)alloca(nb_vertices*sizeof(index_t));
71 ✗ for(index_t lv=0; lv<nb_vertices; ++lv) {
72 ✗ vertices[lv] = M.facets.vertex(f,lv);
73 }
74 ✗ std::sort(vertices, vertices + nb_vertices);
75 ✗ return std::unique(
76 ✗ vertices, vertices + nb_vertices
77 ✗ ) != vertices + nb_vertices;
78 }
79 918622 index_t c1 = M.facets.corners_begin(f);
80 918622 index_t c2 = c1 + 1;
81 918622 index_t c3 = c2 + 1;
82 918622 index_t v1 = M.facet_corners.vertex(c1);
83 918622 index_t v2 = M.facet_corners.vertex(c2);
84 918622 index_t v3 = M.facet_corners.vertex(c3);
85
5/6
✓ Branch 0 taken 918622 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 918521 times.
✓ Branch 3 taken 101 times.
✓ Branch 4 taken 79 times.
✓ Branch 5 taken 918442 times.
 918622 return v1 == v2 || v2 == v3 || v3 == v1;
86 }
87
88 /**
89 * \brief Generates a unique ordering of the vertices of
90 * a facet.
91 * \details Shifts and inverts the order of f's vertices in
92 * such a way that f's first vertex has the smallest index
93 * and it's predecessor->successor have increasing vertex
94 * indices. This ensures that the same facet has a unique
95 * representation (used to detect duplicated facets).
96 * \param[in] M the mesh that the facet belongs to
97 * \param[in] f the index of the facet in \p M
98 * \return true if the facet was flipped, false otherwise
99 */
100 832937 bool normalize_facet_vertices_order(Mesh& M, index_t f) {
101 832937 index_t d = M.facets.nb_vertices(f);
102
103 // Step 1: corner-to-vertex connections
104 // ------------------------------------
105
106 // Determine index c_min of corner with smallest vertex id
107 832937 index_t c0 = M.facets.corners_begin(f);
108 832937 index_t c_min = c0;
109
2/2
✓ Branch 1 taken 1665874 times.
✓ Branch 2 taken 832937 times.
 2498811 for(index_t c = c0 + 1; c < M.facets.corners_end(f); ++c) {
110
2/2
✓ Branch 2 taken 674860 times.
✓ Branch 3 taken 991014 times.
 1665874 if(M.facet_corners.vertex(c) < M.facet_corners.vertex(c_min)) {
111 674860 c_min = c;
112 }
113 }
114
115 // Determine whether facet should be flipped
116 832937 index_t c_prev = M.facets.prev_corner_around_facet(f, c_min);
117 832937 index_t c_next = M.facets.next_corner_around_facet(f, c_min);
118 bool direct = (
119 832937 M.facet_corners.vertex(c_next) >= M.facet_corners.vertex(c_prev)
120 832937 );
121
122 // Assign corner-to-vertex links
123 832937 index_t* f_vertex = (index_t*) alloca(sizeof(index_t) * d);
124 {
125 832937 index_t c = c_min;
126
2/2
✓ Branch 0 taken 2498811 times.
✓ Branch 1 taken 832937 times.
 3331748 for(index_t i = 0; i < d; i++) {
127 2498811 f_vertex[i] = M.facet_corners.vertex(c);
128
2/2
✓ Branch 0 taken 1254201 times.
✓ Branch 1 taken 1244610 times.
 2498811 c = direct ? M.facets.next_corner_around_facet(f, c)
129 1244610 : M.facets.prev_corner_around_facet(f, c);
130 }
131 }
132
2/2
✓ Branch 0 taken 2498811 times.
✓ Branch 1 taken 832937 times.
 3331748 for(index_t i = 0; i < d; i++) {
133 2498811 M.facet_corners.set_vertex(c0 + i, f_vertex[i]);
134 }
135
136 // Step 2: permute corner attributes, using the function
137 // that swaps attributes between two elements.
138 // -----------------------------------------------------
139
140 // Compute permutation P and inverse permutation Pinv
141 // P[i]: from where we fetch the attributes of the i-th corner
142 // P_inv[i]: where we want to put the attributes of the i-th corner
143
144 832937 index_t* P = (index_t*) alloca(sizeof(index_t) * d);
145 832937 index_t* P_inv = (index_t*) alloca(sizeof(index_t) * d);
146 {
147 832937 index_t cur = c_min - c0;
148
2/2
✓ Branch 0 taken 2498811 times.
✓ Branch 1 taken 832937 times.
 3331748 for(index_t i=0; i<d; ++i) {
149 2498811 P[i] = cur;
150
2/2
✓ Branch 0 taken 1254201 times.
✓ Branch 1 taken 1244610 times.
 2498811 if(direct) {
151
2/2
✓ Branch 0 taken 836134 times.
✓ Branch 1 taken 418067 times.
 1254201 cur = (cur == d-1) ? 0 : cur+1;
152 } else {
153
2/2
✓ Branch 0 taken 414870 times.
✓ Branch 1 taken 829740 times.
 1244610 cur = (cur == 0) ? d-1 : cur-1;
154 }
155 }
156
2/2
✓ Branch 0 taken 2498811 times.
✓ Branch 1 taken 832937 times.
 3331748 for(index_t i=0; i<d; ++i) {
157 2498811 P_inv[P[i]] = i;
158 }
159 }
160
161 // Permute attributes (and update P and P_inv accordingly)
162
2/2
✓ Branch 0 taken 1665874 times.
✓ Branch 1 taken 832937 times.
 2498811 for(index_t i=0; i<d-1; ++i) {
163 1665874 index_t j = P[i];
164 1665874 index_t j_inv = P_inv[i];
165
2/2
✓ Branch 0 taken 849458 times.
✓ Branch 1 taken 816416 times.
 1665874 if(i != j) {
166 849458 M.facet_corners.attributes().swap_items(c0+i,c0+j);
167 }
168 1665874 std::swap(P[i],P[j_inv]);
169 1665874 std::swap(P_inv[i], P_inv[j]);
170
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 1665874 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 1665874 geo_assert(P[i] == i);
171
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 1665874 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 1665874 geo_assert(P_inv[i] == i);
172 }
173
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 832937 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 832937 geo_assert(P[d-1] == d-1);
174
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 832937 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 832937 geo_assert(P_inv[d-1] == d-1);
175 832937 return !direct;
176 }
177
178 /**
179 * \brief Comparator class for sorting facets.
180 */
181 class CompareFacets {
182 public:
183 /**
184 * \brief Constructs a new CompareFacets.
185 * \param[in] M the mesh
186 */
187 246 explicit CompareFacets(const Mesh& M) :
188 246 mesh_(M) {
189 246 }
190
191 /**
192 * \brief Tests the lexicographic order of two facets by their indices.
193 * \param[in] f1 index of the first facet
194 * \param[in] f2 index of the second facet
195 * \return true if facet \p f1 is before facet \p f2 according to
196 * the lexicographic order of its vertices, false otherwise.
197 */
198 15926296 bool is_before(index_t f1, index_t f2) const {
199 15926296 index_t c1 = mesh_.facets.corners_begin(f1);
200 15926296 index_t c2 = mesh_.facets.corners_begin(f2);
201 15926296 while(
202
4/4
✓ Branch 1 taken 17451527 times.
✓ Branch 2 taken 40324 times.
✓ Branch 3 taken 17451527 times.
✓ Branch 4 taken 40324 times.
 34943378 c1 != mesh_.facets.corners_end(f1) &&
203
1/2
✓ Branch 1 taken 17451527 times.
✗ Branch 2 not taken.
 17451527 c2 != mesh_.facets.corners_end(f2)
204 ) {
205 17451527 index_t v1 = mesh_.facet_corners.vertex(c1);
206 17451527 index_t v2 = mesh_.facet_corners.vertex(c2);
207
2/2
✓ Branch 0 taken 3758469 times.
✓ Branch 1 taken 13693058 times.
 17451527 if(v1 > v2) {
208 3758469 return false;
209 }
210
2/2
✓ Branch 0 taken 12127503 times.
✓ Branch 1 taken 1565555 times.
 13693058 if(v1 < v2) {
211 12127503 return true;
212 }
213 1565555 c1++;
214 1565555 c2++;
215 }
216 return (
217
1/2
✓ Branch 1 taken 40324 times.
✗ Branch 2 not taken.
 80648 c1 == mesh_.facets.corners_end(f1) &&
218
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 40324 times.
 40324 c2 != mesh_.facets.corners_end(f2)
219 40324 ) ;
220 }
221
222 /**
223 * \brief Tests whether two facets are identical.
224 * \param[in] f1 index of the first facet
225 * \param[in] f2 index of the second facet
226 * \return true if facets \p f1 and \p f2 have the same
227 * vertices, false otherwise
228 */
229 832691 bool is_same(index_t f1, index_t f2) const {
230
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 832691 times.
 832691 if(mesh_.facets.nb_vertices(f1) != mesh_.facets.nb_vertices(f2)) {
231 ✗ return false;
232 }
233 832691 index_t c1 = mesh_.facets.corners_begin(f1);
234 832691 index_t c2 = mesh_.facets.corners_begin(f2);
235
2/2
✓ Branch 1 taken 1587314 times.
✓ Branch 2 taken 29881 times.
 1617195 while(c1 != mesh_.facets.corners_end(f1)) {
236
1/6
✗ Branch 1 not taken.
✓ Branch 2 taken 1587314 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 1587314 geo_debug_assert(c2 != mesh_.facets.corners_end(f2));
237 1587314 index_t v1 = mesh_.facet_corners.vertex(c1);
238 1587314 index_t v2 = mesh_.facet_corners.vertex(c2);
239
2/2
✓ Branch 0 taken 802810 times.
✓ Branch 1 taken 784504 times.
 1587314 if(v1 != v2) {
240 802810 return false;
241 }
242 784504 c1++;
243 784504 c2++;
244 }
245 29881 return true;
246 }
247
248 /**
249 * \brief Tests the lexicographic order of two facets by their indices.
250 * \param[in] f1 index of the first facet
251 * \param[in] f2 index of the second facet
252 * \return true if facet \p f1 is before facet \p f2 according to
253 * the lexicographic order of its vertices, false otherwise.
254 */
255 15926296 bool operator() (index_t f1, index_t f2) const {
256 15926296 return is_before(f1, f2);
257 }
258
259 private:
260 const Mesh& mesh_;
261 };
262
263
264 /**
265 * \brief Finds the non-duplicated vertices of a facet
266 * \param[in] M a const reference to a mesh
267 * \param[in] f a facet index in \p M
268 * \param[out] new_polygon on exit, where to append the
269 * non-duplicated vertices of facet \p f
270 * and a terminal NO_INDEX
271 * \retval true if the facet has three non-duplicated
272 * vertices and more
273 * \retval false otherwise
274 */
275 ✗ bool find_facet_non_duplicated_vertices(
276 const Mesh& M, index_t f, vector<index_t>& new_polygon
277 ) {
278 ✗ index_t first_corner = NO_INDEX;
279
280 // Find the first vertex that is different from
281 // its predecessor around the facet.
282 ✗ for(index_t c1: M.facets.corners(f)) {
283 ✗ index_t c2 = M.facets.next_corner_around_facet(f,c1);
284 ✗ if(M.facet_corners.vertex(c1) != M.facet_corners.vertex(c2)) {
285 ✗ first_corner = c2;
286 ✗ break;
287 }
288 }
289
290 // All the vertices may be identical (if the facet
291 // is completely degenerate).
292 ✗ if(first_corner == NO_INDEX) {
293 ✗ return false;
294 }
295
296 ✗ index_t c = first_corner;
297 ✗ index_t cur_v = NO_INDEX;
298 ✗ index_t nb = 0;
299
300 do {
301 ✗ index_t v = M.facet_corners.vertex(c);
302 ✗ if(v != cur_v) {
303 ✗ new_polygon.push_back(v);
304 ✗ cur_v = v;
305 ✗ ++nb;
306 }
307 ✗ c = M.facets.next_corner_around_facet(f,c);
308 ✗ } while(c != first_corner);
309 ✗ new_polygon.push_back(NO_INDEX);
310
311 // If there were only 2 non-duplicated vertices, then
312 // the facet is degenerate and is "rolled back" (we do
313 // not want to generate facets with two vertices only).
314 ✗ if(nb == 2) {
315 ✗ new_polygon.resize(new_polygon.size()-3);
316 ✗ return false;
317 }
318
319 ✗ return true;
320 }
321
322
323 /**
324 * \brief Detects degenerate facets in a mesh.
325 * \param[in] M the mesh
326 * \param[in] check_duplicates if true, duplicated facets are
327 * detected and all but one instance of each is marked as to be
328 * removed.
329 * \param[out] remove_f indicates for each facet whether it should be
330 * removed. If remove_f[f] != 0 if f should be removed, else f
331 * should be kept. If remove_f.size() == 0, then there is
332 * no facet to remove, else remove_f.size() == M.facets.nb().
333 * \param[out] old_polygons if non zero, on exit contains the
334 * indices of the polygonal facets that had duplicated vertices
335 * \param[out] new_polygons if non zero, on exit contains the
336 * polygonal facets to be created to replace the input polygonal
337 * facets that have duplicated vertices. Each individual facet
338 * is terminated by NO_INDEX
339 */
340 313 void detect_bad_facets(
341 Mesh& M, bool check_duplicates, vector<index_t>& remove_f,
342 vector<index_t>* old_polygons = nullptr,
343 vector<index_t>* new_polygons = nullptr,
344 bool verbose = false
345 ) {
346 313 index_t nb_duplicates = 0;
347 313 index_t nb_degenerate = 0;
348
2/2
✓ Branch 0 taken 246 times.
✓ Branch 1 taken 67 times.
 313 if(check_duplicates) {
349
1/2
✓ Branch 2 taken 246 times.
✗ Branch 3 not taken.
 246 vector<char> flipped(M.facets.nb());
350
351 // Used by boolean operations
352
1/2
✓ Branch 1 taken 246 times.
✗ Branch 2 not taken.
 246 Attribute<index_t> operand_bit;
353
1/2
✓ Branch 2 taken 246 times.
✗ Branch 3 not taken.
 246 operand_bit.bind_if_is_defined(
354
1/2
✓ Branch 1 taken 246 times.
✗ Branch 2 not taken.
 492 M.facets.attributes(),"operand_bit"
355 );
356
357 // Reorder vertices around each facet to make
358 // it easier to compare two facets, and memorize
359 // initial facet orientation.
360
361
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 246 times.
 246 if(M.facets.nb() > 65535) { // Do that in parallel if mesh is large
362 ✗ parallel_for(
363 0, M.facets.nb(),
364 ✗ [&](index_t f) {
365 ✗ flipped[f] = normalize_facet_vertices_order(M, f);
366 ✗ }
367 );
368 } else {
369
2/2
✓ Branch 4 taken 832937 times.
✓ Branch 5 taken 246 times.
 833183 for(index_t f: M.facets) {
370
2/4
✓ Branch 1 taken 832937 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 832937 times.
✗ Branch 5 not taken.
 832937 flipped[f] = normalize_facet_vertices_order(M, f);
371 }
372 }
373
374 // Indirect-sort the facets in lexicographic
375 // order.
376
1/2
✓ Branch 2 taken 246 times.
✗ Branch 3 not taken.
 246 vector<index_t> f_sort(M.facets.nb());
377
2/2
✓ Branch 4 taken 832937 times.
✓ Branch 5 taken 246 times.
 833183 for(index_t f: M.facets) {
378
1/2
✓ Branch 1 taken 832937 times.
✗ Branch 2 not taken.
 832937 f_sort[f] = f;
379 }
380 246 CompareFacets compare_facets(M);
381
1/2
✓ Branch 3 taken 246 times.
✗ Branch 4 not taken.
 246 GEO::sort(f_sort.begin(), f_sort.end(), compare_facets);
382
383 // Now f_sort[0] ... fsort[nb_facets-1] contains the indices
384 // of the sorted facets. This ensures that the indices of the
385 // facets with the same vertices (i.e. duplicated facets)
386 // appear at contiguous sequences in fsort.
387
388 // Traverse in fsort the sequences of duplicate facets.
389 // The algorithm detects the sequence of indices
390 // f_sort[if1] ... f_sort[if2-1] that contain facets
391 // with the same indices.
392 246 index_t if1 = 0;
393
2/2
✓ Branch 1 taken 803056 times.
✓ Branch 2 taken 246 times.
 803302 while(if1 < M.facets.nb()) {
394 803056 index_t if2 = if1 + 1;
395 803056 while(
396
4/4
✓ Branch 1 taken 832691 times.
✓ Branch 2 taken 246 times.
✓ Branch 3 taken 29881 times.
✓ Branch 4 taken 803056 times.
 1665628 if2 < M.facets.nb() &&
397
5/8
✓ Branch 1 taken 832691 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 832691 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 832691 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 29881 times.
✓ Branch 10 taken 802810 times.
 832691 compare_facets.is_same(f_sort[if1], f_sort[if2])
398 ) {
399 29881 nb_duplicates++;
400 // Tag all facets in f_sort[if1+1] ... f_sort[if2-1] as
401 // 'to be removed' (because they all have the same vertices
402 // as f_sort[if1]).
403
2/2
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 29855 times.
 29881 if(remove_f.size() == 0) {
404
1/2
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
 26 remove_f.resize(M.facets.nb(), 0);
405 }
406
2/4
✓ Branch 1 taken 29881 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 29881 times.
✗ Branch 5 not taken.
 29881 remove_f[f_sort[if2]] = 1;
407 // Used by boolean operations
408 // ^= instead of |= because there can be "fins" in the
409 // input of boolean operators, and ^= discards duplicated
410 // facets in fins.
411
1/2
✓ Branch 1 taken 29881 times.
✗ Branch 2 not taken.
 29881 if(operand_bit.is_bound()) {
412
4/8
✓ Branch 1 taken 29881 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 29881 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 29881 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 29881 times.
✗ Branch 11 not taken.
 29881 operand_bit[f_sort[if1]] ^= operand_bit[f_sort[if2]];
413 }
414 29881 if2++;
415 }
416 803056 if1 = if2;
417 }
418
419 // Restore initial facets orientation
420
2/2
✓ Branch 5 taken 832937 times.
✓ Branch 6 taken 246 times.
 833183 for(index_t f: M.facets) {
421
3/4
✓ Branch 1 taken 832937 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 414870 times.
✓ Branch 4 taken 418067 times.
 832937 if(flipped[f]) {
422
1/2
✓ Branch 1 taken 414870 times.
✗ Branch 2 not taken.
 414870 M.facets.flip(f);
423 }
424 }
425 246 }
426
427 // Now, we tag the degenerate facets as 'to be removed'. A
428 // facet is degenerate if it is incident to the same vertex several
429 // times.
430
2/2
✓ Branch 5 taken 948503 times.
✓ Branch 6 taken 313 times.
 948816 for(index_t f: M.facets) {
431 948503 if(
432
7/8
✓ Branch 1 taken 178915 times.
✓ Branch 2 taken 769588 times.
✓ Branch 4 taken 178915 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 149034 times.
✓ Branch 7 taken 29881 times.
✓ Branch 8 taken 180 times.
✓ Branch 9 taken 948323 times.
 1867125 (remove_f.size() == 0 || remove_f[f] == 0) &&
433
3/4
✓ Branch 1 taken 918622 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 180 times.
✓ Branch 4 taken 918442 times.
 918622 facet_is_degenerate(M, f)
434 ) {
435 180 nb_degenerate++;
436
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 177 times.
 180 if(remove_f.size() == 0) {
437
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 remove_f.resize(M.facets.nb(), 0);
438 }
439
1/2
✓ Branch 1 taken 180 times.
✗ Branch 2 not taken.
 180 remove_f[f] = 1;
440
441 // If we found a degenerate polygonal facet and
442 // we want to regenerate a valid one:
443 180 if(
444
1/2
✓ Branch 0 taken 180 times.
✗ Branch 1 not taken.
 180 old_polygons != nullptr &&
445
2/4
✓ Branch 0 taken 180 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 180 times.
 360 new_polygons != nullptr &&
446
2/4
✓ Branch 1 taken 180 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 180 times.
 180 M.facets.nb_vertices(f) > 3
447 ) {
448 ✗ if(find_facet_non_duplicated_vertices(
449 M,f,*new_polygons
450 )) {
451 ✗ old_polygons->push_back(f);
452 }
453 }
454 }
455 }
456
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 313 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 313 if(verbose && (nb_duplicates != 0 || nb_degenerate != 0)) {
457 ✗ Logger::out("Validate")
458 ✗ << "Detected " << nb_duplicates << " duplicate and "
459 ✗ << nb_degenerate << " degenerate facets"
460 ✗ << std::endl;
461 }
462 313 }
463
464 /************************************************************************/
465
466 /**
467 * \brief Connects the facets in a mesh.
468 * \details Reconstructs the corners.adjacent_facet links.
469 * Note that the Moebius law is not respected by this
470 * function (adjacent facets may have incoherent orientations).
471 * This function outputs a mesh with possibly not coherently
472 * oriented triangles. In other words, for two
473 * corners c1, c2, if we have:
474 * - v1 = facet_corners.vertex(c1)
475 * - v2 = facet_corners.vertex(
476 * c1,facets.next_corner_around_facet(c2f(c1),c1)
477 * )
478 * - w1 = facet_corners.vertex(c2)
479 * - w2 = facet_corners.vertex(
480 * c2,facets.next_corner_around_facet(c2f(c2),c2)
481 * )
482 * then c1 and c2 are adjacent if we have:
483 * - v1=w2 and v2=w1 (as usual) or:
484 * - v1=v2 and w1=w2 ('inverted' configuration)
485 * The output of this function can be then post-processed by
486 * repair_reorient_facets_anti_moebius() to recover coherent
487 * orientations.
488 * \param[in] M the mesh to repair
489 */
490 195 void repair_connect_facets(Mesh& M) {
491 195 const index_t NON_MANIFOLD=index_t(-2);
492
493 // Reset all facet-facet adjacencies.
494
2/2
✓ Branch 5 taken 2185176 times.
✓ Branch 6 taken 195 times.
 2185371 for(index_t c: M.facet_corners) {
495
1/2
✓ Branch 1 taken 2185176 times.
✗ Branch 2 not taken.
 2185176 M.facet_corners.set_adjacent_facet(c,NO_FACET);
496 }
497
498 // For each vertex v, v2c[v] gives the index of a
499 // corner incident to vertex v.
500
1/2
✓ Branch 2 taken 195 times.
✗ Branch 3 not taken.
 195 vector<index_t> v2c(M.vertices.nb(),NO_CORNER);
501
502 // For each corner c, next_c_around_v[c] is the
503 // linked list of all the corners incident to
504 // vertex v.
505
1/2
✓ Branch 2 taken 195 times.
✗ Branch 3 not taken.
 195 vector<index_t> next_c_around_v(M.facet_corners.nb(),NO_CORNER);
506
507 // For each corner c, c2f[c] is the index of
508 // the facet incident to c (or use c/3 if
509 // M is triangulated).
510 195 vector<index_t> c2f;
511
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 195 times.
 195 if(!M.facets.are_simplices()) {
512 ✗ c2f.assign(M.facet_corners.nb(), NO_FACET);
513 }
514
515 // Compute v2c and next_c_around_v
516
2/2
✓ Branch 4 taken 2185176 times.
✓ Branch 5 taken 195 times.
 2185371 for(index_t c: M.facet_corners) {
517
1/2
✓ Branch 1 taken 2185176 times.
✗ Branch 2 not taken.
 2185176 index_t v = M.facet_corners.vertex(c);
518
2/4
✓ Branch 1 taken 2185176 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2185176 times.
✗ Branch 5 not taken.
 2185176 next_c_around_v[c] = v2c[v];
519
1/2
✓ Branch 1 taken 2185176 times.
✗ Branch 2 not taken.
 2185176 v2c[v] = c;
520 }
521
522 // Compute f2c (only if M is not triangulated,
523 // because if M is triangulated, we have f2c(c) = c/3).
524
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 195 times.
 195 if(!M.facets.are_simplices()) {
525 ✗ for(index_t f: M.facets) {
526 ✗ for(index_t c: M.facets.corners(f)) {
527 ✗ c2f[c]=f;
528 }
529 }
530 }
531
532
2/2
✓ Branch 5 taken 728392 times.
✓ Branch 6 taken 195 times.
 728587 for(index_t f1: M.facets) {
533
3/4
✓ Branch 1 taken 728392 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 2185176 times.
✓ Branch 9 taken 728392 times.
 2913568 for(index_t c1: M.facets.corners(f1)) {
534
3/4
✓ Branch 1 taken 2185176 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1097680 times.
✓ Branch 4 taken 1087496 times.
 2185176 if(M.facet_corners.adjacent_facet(c1) == NO_FACET) {
535 1097680 index_t adj_corner = NO_CORNER;
536
1/2
✓ Branch 1 taken 1097680 times.
✗ Branch 2 not taken.
 1097680 index_t v1=M.facet_corners.vertex(c1);
537
2/4
✓ Branch 1 taken 1097680 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1097680 times.
✗ Branch 5 not taken.
 1097680 index_t v2=M.facet_corners.vertex(
538 M.facets.next_corner_around_facet(f1,c1)
539 );
540
541
1/2
✓ Branch 1 taken 1097680 times.
✗ Branch 2 not taken.
 1097680 index_t c2 = v2c[v1];
542
543 // Lookup candidate adjacent edges from incident
544 // edges list.
545
2/2
✓ Branch 0 taken 6859308 times.
✓ Branch 1 taken 1097680 times.
 7956988 while(c2 != NO_CORNER) {
546
2/2
✓ Branch 0 taken 5761628 times.
✓ Branch 1 taken 1097680 times.
 6859308 if(c2 != c1) {
547 index_t f2 =
548
1/4
✓ Branch 1 taken 5761628 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 5761628 M.facets.are_simplices() ? c2/3 : c2f[c2];
549 index_t c3 =
550
1/2
✓ Branch 1 taken 5761628 times.
✗ Branch 2 not taken.
 5761628 M.facets.prev_corner_around_facet(f2,c2);
551
1/2
✓ Branch 1 taken 5761628 times.
✗ Branch 2 not taken.
 5761628 index_t v3 = M.facet_corners.vertex(c3);
552 // Check with standard orientation.
553
2/2
✓ Branch 0 taken 1050173 times.
✓ Branch 1 taken 4711455 times.
 5761628 if(v3 == v2) {
554
2/2
✓ Branch 0 taken 1049928 times.
✓ Branch 1 taken 245 times.
 1050173 if(adj_corner == NO_CORNER) {
555 1049928 adj_corner = c3;
556 } else {
557 245 adj_corner = NON_MANIFOLD;
558 }
559 } else {
560 // Check with the other ("wrong") orientation
561
1/2
✓ Branch 1 taken 4711455 times.
✗ Branch 2 not taken.
 4711455 c3 = M.facets.next_corner_around_facet(f2,c2);
562
1/2
✓ Branch 1 taken 4711455 times.
✗ Branch 2 not taken.
 4711455 v3 = M.facet_corners.vertex(c3);
563
2/2
✓ Branch 0 taken 37959 times.
✓ Branch 1 taken 4673496 times.
 4711455 if(v3 == v2) {
564
2/2
✓ Branch 0 taken 37796 times.
✓ Branch 1 taken 163 times.
 37959 if(adj_corner == NO_CORNER) {
565 37796 adj_corner = c2;
566 } else {
567 163 adj_corner = NON_MANIFOLD;
568 }
569 }
570 }
571 }
572
1/2
✓ Branch 1 taken 6859308 times.
✗ Branch 2 not taken.
 6859308 c2 = next_c_around_v[c2];
573 }
574
2/2
✓ Branch 0 taken 1087724 times.
✓ Branch 1 taken 9956 times.
 1097680 if(
575
2/2
✓ Branch 0 taken 1087496 times.
✓ Branch 1 taken 228 times.
 1087724 adj_corner != NO_CORNER &&
576 adj_corner != NON_MANIFOLD
577 ) {
578
1/2
✓ Branch 1 taken 1087496 times.
✗ Branch 2 not taken.
 1087496 M.facet_corners.set_adjacent_facet(adj_corner,f1);
579
1/2
✓ Branch 1 taken 1087496 times.
✗ Branch 2 not taken.
 1087496 index_t f2 = M.facets.are_simplices() ?
580 adj_corner/3 :
581
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 1087496 c2f[adj_corner] ;
582
1/2
✓ Branch 1 taken 1087496 times.
✗ Branch 2 not taken.
 1087496 M.facet_corners.set_adjacent_facet(c1,f2);
583 }
584 }
585 }
586 }
587 195 }
588
589 /************************************************************************/
590
591 /**
592 * \brief Tests the relative orientation of two adjacent facets
593 * \param[in] M the mesh
594 * \param[in] f1 index of the first facet
595 * \param[in] c11 index of a corner in facet \p f1
596 * \param[in] f2 index of the second facet
597 * \return 1 if \p f1 and \p f2 have compatible orientations, -1 if
598 * they have incompatible orientations, 0 if they are not adjacent
599 */
600 1459923 inline signed_index_t repair_relative_orientation(
601 Mesh& M, index_t f1, index_t c11, index_t f2
602 ) {
603 1459923 index_t c12 = M.facets.next_corner_around_facet(f1, c11);
604 1459923 index_t v11 = M.facet_corners.vertex(c11);
605 1459923 index_t v12 = M.facet_corners.vertex(c12);
606
2/4
✓ Branch 1 taken 1459923 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 2892768 times.
✗ Branch 9 not taken.
 2892768 for(index_t c21: M.facets.corners(f2)) {
607
1/2
✓ Branch 1 taken 2892768 times.
✗ Branch 2 not taken.
 2892768 index_t c22 = M.facets.next_corner_around_facet(f2, c21);
608
1/2
✓ Branch 1 taken 2892768 times.
✗ Branch 2 not taken.
 2892768 index_t v21 = M.facet_corners.vertex(c21);
609
1/2
✓ Branch 1 taken 2892768 times.
✗ Branch 2 not taken.
 2892768 index_t v22 = M.facet_corners.vertex(c22);
610
4/4
✓ Branch 0 taken 541431 times.
✓ Branch 1 taken 2351337 times.
✓ Branch 2 taken 139302 times.
✓ Branch 3 taken 402129 times.
 2892768 if(v11 == v21 && v12 == v22) {
611 1459923 return -1;
612 }
613
4/4
✓ Branch 0 taken 1420007 times.
✓ Branch 1 taken 1333459 times.
✓ Branch 2 taken 1320621 times.
✓ Branch 3 taken 99386 times.
 2753466 if(v11 == v22 && v12 == v21) {
614 1320621 return 1;
615 }
616 }
617 ✗ return 0;
618 }
619
620 /**
621 * \brief Removes an adjacency connections between two facets in a mesh
622 * \param[in] M the mesh
623 * \param[in] f1 index of the first facet
624 * \param[in] f2 index of the second facet
625 */
626 ✗ void repair_dissociate(
627 Mesh& M, index_t f1, index_t f2
628 ) {
629 ✗ for(index_t c: M.facets.corners(f1)) {
630 ✗ if(M.facet_corners.adjacent_facet(c) == f2) {
631 ✗ M.facet_corners.set_adjacent_facet(c, NO_FACET);
632 }
633 }
634 ✗ for(index_t c: M.facets.corners(f2)) {
635 ✗ if(M.facet_corners.adjacent_facet(c) == f1) {
636 ✗ M.facet_corners.set_adjacent_facet(c, NO_FACET);
637 }
638 }
639 ✗ }
640
641 /**
642 * \brief Greedily propagates facet reorientation in a mesh
643 * \details Whenever a Moebius loop is encountered, the involved
644 * facets are disconnected from their neighbors.
645 * \param[in] M the mesh
646 * \param[in] f index of the current facet
647 * \param[in,out] visited a vector used to mark facets that were
648 * already traversed
649 * \param[out] moebius_count number of Moebius loops encountered
650 * \param[out] moebius_facets a pointer to a vector. On exit,
651 * *moebius_facets[f] has a non-zero value if facet f is
652 * incident to an edge that could not be consistently oriented.
653 * If nullptr, then this information is not returned.
654 */
655 977995 void repair_propagate_orientation(
656 Mesh& M, index_t f, const std::vector<bool>& visited,
657 index_t& moebius_count,
658 vector<index_t>* moebius_facets = nullptr
659 ) {
660 977995 index_t nb_plus = 0;
661 977995 index_t nb_minus = 0;
662
3/4
✓ Branch 1 taken 977995 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 2933985 times.
✓ Branch 9 taken 977995 times.
 3911980 for(index_t c: M.facets.corners(f)) {
663
1/2
✓ Branch 1 taken 2933985 times.
✗ Branch 2 not taken.
 2933985 index_t f2 = M.facet_corners.adjacent_facet(c);
664
6/6
✓ Branch 0 taken 2919335 times.
✓ Branch 1 taken 14650 times.
✓ Branch 3 taken 1459923 times.
✓ Branch 4 taken 1459412 times.
✓ Branch 5 taken 1459923 times.
✓ Branch 6 taken 1474062 times.
 2933985 if(f2 != NO_FACET && visited[index_t(f2)]) {
665 signed_index_t ori =
666
1/2
✓ Branch 1 taken 1459923 times.
✗ Branch 2 not taken.
 1459923 repair_relative_orientation(M, f, c, f2);
667
2/4
✓ Branch 0 taken 1320621 times.
✓ Branch 1 taken 139302 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 1459923 switch(ori) {
668 1320621 case 1:
669 1320621 nb_plus++;
670 1320621 break;
671 139302 case -1:
672 139302 nb_minus++;
673 139302 break;
674 ✗ case 0:
675 ✗ geo_assert_not_reached;
676 }
677 }
678 }
679
3/4
✓ Branch 0 taken 884520 times.
✓ Branch 1 taken 93475 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 884520 times.
 977995 if(nb_plus != 0 && nb_minus != 0) {
680 ✗ moebius_count++;
681 ✗ if(moebius_facets != nullptr) {
682 ✗ moebius_facets->resize(M.facets.nb(), 0);
683 ✗ (*moebius_facets)[f] = 1;
684 ✗ for(index_t c: M.facets.corners(f)) {
685 ✗ index_t f2 = M.facet_corners.adjacent_facet(c);
686 ✗ if(f2 != NO_FACET) {
687 ✗ (*moebius_facets)[f2] = 1;
688 }
689 }
690 }
691 ✗ if(nb_plus > nb_minus) {
692 ✗ nb_minus = 0;
693 ✗ for(index_t c: M.facets.corners(f)) {
694 ✗ index_t f2 = M.facet_corners.adjacent_facet(c);
695 ✗ if(
696 ✗ f2 != NO_FACET && visited[f2] &&
697 ✗ repair_relative_orientation(M, f, c, f2) < 0
698 ) {
699 ✗ repair_dissociate(M, f, f2);
700 }
701 }
702 } else {
703 ✗ nb_plus = 0;
704 ✗ for(index_t c: M.facets.corners(f)) {
705 ✗ index_t f2 = M.facet_corners.adjacent_facet(c);
706 ✗ if(
707 ✗ f2 != NO_FACET && visited[index_t(f2)] &&
708 ✗ repair_relative_orientation(M, f, c, f2) > 0
709 ) {
710 ✗ repair_dissociate(M, f, f2);
711 }
712 }
713 }
714 }
715 977995 geo_argused(nb_plus);
716
2/2
✓ Branch 0 taken 93475 times.
✓ Branch 1 taken 884520 times.
 977995 if(nb_minus != 0) {
717
1/2
✓ Branch 1 taken 93475 times.
✗ Branch 2 not taken.
 93475 M.facets.flip(f);
718 }
719 977995 }
720
721 /**
722 * \brief Tests whether a facet of a mesh is on the border.
723 * \param[in] M the mesh
724 * \param[in] f index of the facet
725 * \return true if \p f is on the border of \p M, false otherwise
726 */
727 978178 bool facet_is_on_border(Mesh& M, index_t f) {
728
3/4
✓ Branch 1 taken 978178 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 2917810 times.
✓ Branch 9 taken 963726 times.
 3881536 for(index_t c: M.facets.corners(f)) {
729
3/4
✓ Branch 1 taken 2917810 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 14452 times.
✓ Branch 4 taken 2903358 times.
 2917810 if(M.facet_corners.adjacent_facet(c) == NO_FACET) {
730 14452 return true;
731 }
732 }
733 963726 return false;
734 }
735
736 /**
737 * \brief Used to represent graph distance to border.
738 * Since values are clamped to a small number (typically 5),
739 * this fits in a single byte.
740 */
741 typedef Numeric::uint8 facet_distance_t;
742
743 /**
744 * \brief Computes for each facet its facet-graph distance to
745 * the border of the mesh, clamped to max_iter.
746 * \param[in] M the mesh
747 * \param[out] D for each facet, its graph distance to the border
748 * \param[in] max_iter maximumm number of iterations (determines the
749 * largest possible computed graph distance).
750 */
751 199 void compute_border_distance(
752 Mesh& M, vector<facet_distance_t>& D, index_t max_iter
753 ) {
754
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 199 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 199 geo_assert(max_iter < 256);
755
1/2
✓ Branch 2 taken 199 times.
✗ Branch 3 not taken.
 199 D.assign(M.facets.nb(), facet_distance_t(max_iter));
756
2/2
✓ Branch 5 taken 978178 times.
✓ Branch 6 taken 199 times.
 978377 for(index_t f: M.facets) {
757
3/4
✓ Branch 1 taken 978178 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 14452 times.
✓ Branch 4 taken 963726 times.
 978178 if(facet_is_on_border(M, f)) {
758
1/2
✓ Branch 1 taken 14452 times.
✗ Branch 2 not taken.
 14452 D[f] = facet_distance_t(0);
759 }
760 }
761
2/2
✓ Branch 0 taken 796 times.
✓ Branch 1 taken 199 times.
 995 for(signed_index_t i = 1; i < signed_index_t(max_iter); i++) {
762
2/2
✓ Branch 5 taken 3912712 times.
✓ Branch 6 taken 796 times.
 3913508 for(index_t f: M.facets) {
763
3/4
✓ Branch 1 taken 3912712 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3802738 times.
✓ Branch 4 taken 109974 times.
 3912712 if(D[f] == signed_index_t(max_iter)) {
764
3/4
✓ Branch 1 taken 3802738 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 11368946 times.
✓ Branch 9 taken 3768737 times.
 15137683 for(index_t c: M.facets.corners(f)) {
765
1/2
✓ Branch 1 taken 11368946 times.
✗ Branch 2 not taken.
 11368946 index_t g = M.facet_corners.adjacent_facet(c);
766
6/8
✓ Branch 0 taken 11368946 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 11368946 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 34001 times.
✓ Branch 6 taken 11334945 times.
✓ Branch 7 taken 34001 times.
✓ Branch 8 taken 11334945 times.
 11368946 if(g != NO_FACET && D[g] == facet_distance_t(i - 1)) {
767
1/2
✓ Branch 1 taken 34001 times.
✗ Branch 2 not taken.
 34001 D[f] = facet_distance_t(i);
768 34001 break;
769 }
770 }
771 }
772 }
773 }
774 199 }
775
776 /**
777 * \brief A priority queue specialized to
778 * the specific case where priorities can
779 * take a small number of distinct values.
780 * \details
781 * It is implemented as an array of stacks.
782 */
783 class SimplePriorityQueue {
784 public:
785 /**
786 * \param[in] D priorities
787 * \param[in] max_distance max value in D
788 */
789 199 SimplePriorityQueue(
790 const vector<facet_distance_t>& D,
791 facet_distance_t max_distance
792 199 ) :
793 199 stacks_(index_t(max_distance + 1)),
794 199 D_(D) {
795 199 }
796
797 /**
798 * \brief Pushes a facet onto the priority queue
799 * \param[in] f index of the facet to push
800 */
801 978178 void push(index_t f) {
802
1/6
✗ Branch 2 not taken.
✓ Branch 3 taken 978178 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 978178 geo_debug_assert(D_[f] < stacks_.size());
803 978178 stacks_[D_[f]].push(f);
804 978178 }
805
806 /**
807 * \brief Pops a facet from the priority queue
808 * \return the index of the popped facet
809 */
810 978178 index_t pop() {
811 158427 for(
812 978178 signed_index_t i = signed_index_t(stacks_.size()) - 1;
813
1/2
✓ Branch 0 taken 1136605 times.
✗ Branch 1 not taken.
 1136605 i >= 0; i--
814 ) {
815
2/2
✓ Branch 2 taken 978178 times.
✓ Branch 3 taken 158427 times.
 1136605 if(!stacks_[i].empty()) {
816 978178 index_t result = stacks_[i].top();
817 978178 stacks_[i].pop();
818 978178 return result;
819 }
820 }
821 ✗ geo_assert_not_reached;
822 }
823
824 /**
825 * \brief Tests whether this SimplePriorityQueue is empty
826 * \return true if this SimplePriorityQueue is empty, false
827 * otherwise
828 */
829 978361 bool empty() {
830
2/2
✓ Branch 1 taken 5045823 times.
✓ Branch 2 taken 183 times.
 5046006 for(index_t i = 0; i < stacks_.size(); i++) {
831
2/2
✓ Branch 2 taken 978178 times.
✓ Branch 3 taken 4067645 times.
 5045823 if(!stacks_[i].empty()) {
832 978178 return false;
833 }
834 }
835 183 return true;
836 }
837
838 private:
839 vector<std::stack<index_t> > stacks_;
840 const vector<facet_distance_t>& D_;
841 };
842
843 /**
844 * \brief Reorients the facets with a heuristic that reduces
845 * the impact of Moebius loops.
846 * \param[in,out] M the mesh to repair
847 * \param[out] moebius_facets a pointer to a vector. On exit,
848 * *moebius_facets[f] has a non-zero value if facet f is
849 * incident to an edge that could not be consistently oriented.
850 * If nullptr, then this information is not returned.
851 */
852 199 void repair_reorient_facets_anti_moebius(
853 Mesh& M, vector<index_t>* moebius_facets=nullptr
854 ) {
855 199 const int max_iter = 5;
856 199 vector<facet_distance_t> D;
857
1/2
✓ Branch 2 taken 199 times.
✗ Branch 3 not taken.
 199 std::vector<bool> visited(M.facets.nb(), false);
858
1/2
✓ Branch 1 taken 199 times.
✗ Branch 2 not taken.
 199 compute_border_distance(M, D, max_iter);
859
1/2
✓ Branch 1 taken 199 times.
✗ Branch 2 not taken.
 199 SimplePriorityQueue Q(D, max_iter);
860
861 199 index_t moebius_count = 0;
862 199 index_t nb_visited = 0;
863
2/2
✓ Branch 0 taken 1194 times.
✓ Branch 1 taken 199 times.
 1393 for(signed_index_t i = max_iter; i >= 0; i--) {
864
2/2
✓ Branch 5 taken 380935 times.
✓ Branch 6 taken 453 times.
 381388 for(index_t f: M.facets) {
865
7/8
✓ Branch 2 taken 8183 times.
✓ Branch 3 taken 372752 times.
✓ Branch 5 taken 8183 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 183 times.
✓ Branch 8 taken 8000 times.
✓ Branch 9 taken 183 times.
✓ Branch 10 taken 380752 times.
 380935 if(!visited[f] && D[f] == i) {
866
1/2
✓ Branch 1 taken 183 times.
✗ Branch 2 not taken.
 183 Q.push(f);
867 183 visited[f] = true;
868 183 nb_visited++;
869
3/4
✓ Branch 1 taken 978361 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 978178 times.
✓ Branch 4 taken 183 times.
 978361 while(!Q.empty()) {
870
1/2
✓ Branch 1 taken 978178 times.
✗ Branch 2 not taken.
 978178 index_t f1 = Q.pop();
871
3/4
✓ Branch 1 taken 978178 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 2934534 times.
✓ Branch 9 taken 978178 times.
 3912712 for(index_t c: M.facets.corners(f1)) {
872
1/2
✓ Branch 1 taken 2934534 times.
✗ Branch 2 not taken.
 2934534 index_t f2 = M.facet_corners.adjacent_facet(c);
873
6/6
✓ Branch 0 taken 2919846 times.
✓ Branch 1 taken 14688 times.
✓ Branch 4 taken 977995 times.
✓ Branch 5 taken 1941851 times.
✓ Branch 6 taken 977995 times.
✓ Branch 7 taken 1956539 times.
 2934534 if(f2 != NO_FACET && !visited[f2]) {
874 977995 visited[f2] = true;
875 977995 nb_visited++;
876
1/2
✓ Branch 1 taken 977995 times.
✗ Branch 2 not taken.
 977995 repair_propagate_orientation(
877 M, f2, visited,
878 moebius_count, moebius_facets
879 );
880
1/2
✓ Branch 1 taken 977995 times.
✗ Branch 2 not taken.
 977995 Q.push(f2);
881 }
882 }
883 }
884 }
885
2/2
✓ Branch 1 taken 741 times.
✓ Branch 2 taken 380194 times.
 380935 if(nb_visited == M.facets.nb()) {
886 741 break;
887 }
888 }
889 }
890
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 199 times.
 199 if(moebius_count != 0) {
891 ✗ Logger::out("Validate")
892 ✗ << "Encountered " << moebius_count
893 ✗ << " ambiguous facet orientation (Moebius)"
894 ✗ << std::endl;
895 }
896 199 }
897
898 /************************************************************************/
899
900 /**
901 * \brief Finds the corner by facet and vertex index
902 * \param[in] M the mesh
903 * \param[in] f the facet index
904 * \param[in] v the vertex index
905 * \return the index of the corner that corresponds to \p f and \p v
906 * \pre such a corner does not exist in \p M
907 */
908 1815824 inline index_t find_corner(
909 const Mesh& M, index_t f, index_t v
910 ) {
911
2/4
✓ Branch 1 taken 1815824 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 3633315 times.
✗ Branch 9 not taken.
 3633315 for(index_t c: M.facets.corners(f)) {
912
3/4
✓ Branch 1 taken 3633315 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1815824 times.
✓ Branch 4 taken 1817491 times.
 3633315 if(M.facet_corners.vertex(c) == v) {
913 1815824 return c;
914 }
915 }
916 ✗ geo_assert_not_reached;
917 }
918
919 /**
920 * \brief Splits the non-manifold vertices
921 * \param[in] M the mesh to repair
922 */
923 195 void repair_split_non_manifold_vertices(Mesh& M, bool verbose=false) {
924
1/2
✓ Branch 2 taken 195 times.
✗ Branch 3 not taken.
 195 std::vector<bool> c_is_visited(M.facet_corners.nb(), false);
925
1/2
✓ Branch 2 taken 195 times.
✗ Branch 3 not taken.
 195 std::vector<bool> v_is_used(M.vertices.nb(), false);
926 // new vertices are stored separately to avoid
927 // too large vector growth that would occur if
928 // pushed back to M.vertices_.
929 195 vector<double> new_vertices;
930 195 index_t nb_vertices = M.vertices.nb();
931
2/2
✓ Branch 5 taken 728392 times.
✓ Branch 6 taken 195 times.
 728587 for(index_t f: M.facets) {
932
3/4
✓ Branch 1 taken 728392 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 2185176 times.
✓ Branch 9 taken 728392 times.
 2913568 for(index_t c: M.facets.corners(f)) {
933
2/2
✓ Branch 2 taken 369352 times.
✓ Branch 3 taken 1815824 times.
 2185176 if(!c_is_visited[c]) {
934 369352 index_t cur_f = f;
935 369352 index_t cur_c = c;
936
1/2
✓ Branch 1 taken 369352 times.
✗ Branch 2 not taken.
 369352 index_t old_v = M.facet_corners.vertex(c);
937 369352 index_t new_v = old_v;
938
2/2
✓ Branch 2 taken 168 times.
✓ Branch 3 taken 369184 times.
 369352 if(v_is_used[old_v]) {
939 168 new_v = nb_vertices;
940 168 nb_vertices++;
941 504 for(
942
3/4
✓ Branch 1 taken 672 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 504 times.
✓ Branch 4 taken 168 times.
 672 index_t coord = 0; coord < M.vertices.dimension();
943 coord++
944 ) {
945 504 new_vertices.push_back(
946
2/4
✓ Branch 1 taken 504 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 504 times.
✗ Branch 5 not taken.
 504 M.vertices.point_ptr(old_v)[coord]
947 );
948 }
949 } else {
950 369184 v_is_used[old_v] = true;
951 }
952
953 369352 index_t count = 0;
954 for(;;) {
955 2175141 c_is_visited[cur_c] = true;
956 // cannot use corners.set_vertex
957 // since vertices are not created yet
958 // (would generate an assertion fail).
959
1/2
✓ Branch 1 taken 2175141 times.
✗ Branch 2 not taken.
 2175141 M.facet_corners.set_vertex_no_check(cur_c,new_v);
960
1/2
✓ Branch 1 taken 2175141 times.
✗ Branch 2 not taken.
 2175141 cur_f = M.facet_corners.adjacent_facet(cur_c);
961
4/4
✓ Branch 0 taken 2164957 times.
✓ Branch 1 taken 10184 times.
✓ Branch 2 taken 1805789 times.
✓ Branch 3 taken 359168 times.
 2175141 if(cur_f == NO_FACET || cur_f == f) {
962 break;
963 }
964
1/2
✓ Branch 1 taken 1805789 times.
✗ Branch 2 not taken.
 1805789 cur_c = find_corner(M, index_t(cur_f), old_v);
965 1805789 count++;
966
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 1805789 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 1805789 geo_assert(count < 10000);
967 }
968
969
2/2
✓ Branch 0 taken 10184 times.
✓ Branch 1 taken 359168 times.
 369352 if(cur_f == NO_FACET) {
970 10184 cur_f = f;
971 10184 cur_c = c;
972 10184 count = 0;
973 for(;;) {
974
1/2
✓ Branch 1 taken 20219 times.
✗ Branch 2 not taken.
 20219 cur_c = M.facets.prev_corner_around_facet(
975 index_t(cur_f), cur_c
976 );
977
1/2
✓ Branch 1 taken 20219 times.
✗ Branch 2 not taken.
 20219 cur_f = M.facet_corners.adjacent_facet(cur_c);
978
2/2
✓ Branch 0 taken 10184 times.
✓ Branch 1 taken 10035 times.
 20219 if(cur_f == NO_FACET) {
979 10184 break;
980 }
981
1/2
✓ Branch 1 taken 10035 times.
✗ Branch 2 not taken.
 10035 cur_c = find_corner(M, index_t(cur_f), old_v);
982 10035 c_is_visited[cur_c] = true;
983 // cannot use corners.set_vertex
984 // since size is not updated yet
985 // (would generate an assertion fail).
986
1/2
✓ Branch 1 taken 10035 times.
✗ Branch 2 not taken.
 10035 M.facet_corners.set_vertex_no_check(cur_c,new_v);
987 10035 count++;
988
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 10035 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 10035 geo_assert(count < 10000);
989 }
990 }
991 }
992 }
993 }
994
995
2/2
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 190 times.
 195 if(new_vertices.size() != 0) {
996
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if(verbose) {
997
2/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
 15 Logger::out("Validate")
998
2/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
 5 << "Detected non-manifold vertices" << std::endl;
999
3/6
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 5 times.
✗ Branch 8 not taken.
 15 Logger::out("Validate") << " (fixed by generating "
1000
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 << nb_vertices - M.vertices.nb()
1001
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 << " new vertices)"
1002
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 << std::endl;
1003 }
1004 15 index_t first_v = M.vertices.create_vertices(
1005
2/4
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 5 times.
✗ Branch 6 not taken.
 5 new_vertices.size() / M.vertices.dimension()
1006 );
1007
1008
2/2
✓ Branch 1 taken 504 times.
✓ Branch 2 taken 5 times.
 509 for(index_t i=0; i<new_vertices.size(); ++i) {
1009
2/4
✓ Branch 1 taken 504 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 504 times.
✗ Branch 5 not taken.
 504 M.vertices.point_ptr(first_v)[i] = new_vertices[i];
1010 }
1011 }
1012 195 }
1013 }
1014
1015 /****************************************************************************/
1016
1017 namespace GEO {
1018
1019 ✗ void mesh_connect_and_reorient_facets_no_check(
1020 Mesh& M
1021 ) {
1022 ✗ repair_connect_facets(M);
1023 ✗ repair_reorient_facets_anti_moebius(M);
1024 ✗ }
1025
1026 187 void mesh_repair(
1027 Mesh& M, MeshRepairMode mode, double colocate_epsilon
1028 ) {
1029 187 bool verbose = ((mode & MESH_REPAIR_QUIET) == 0);
1030
1031 187 index_t nb_vertices_in = M.vertices.nb();
1032 187 index_t nb_facets_in = M.facets.nb();
1033
1034
2/2
✓ Branch 0 taken 158 times.
✓ Branch 1 taken 29 times.
 187 if(mode & MESH_REPAIR_COLOCATE) {
1035 158 mesh_colocate_vertices_no_check(M, colocate_epsilon, verbose);
1036 }
1037
2/2
✓ Branch 0 taken 110 times.
✓ Branch 1 taken 77 times.
 187 if(mode & MESH_REPAIR_TRIANGULATE) {
1038 110 M.facets.triangulate();
1039 }
1040 187 mesh_remove_bad_facets_no_check(
1041 187 M, (mode & MESH_REPAIR_DUP_F) != 0
1042 );
1043
1044 187 repair_connect_facets(M);
1045 187 repair_reorient_facets_anti_moebius(M);
1046 187 repair_split_non_manifold_vertices(M,verbose);
1047
1048 187 if(
1049
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 185 times.
 187 (mode & MESH_REPAIR_RECONSTRUCT) != 0
1050 ) {
1051 2 double Marea = Geom::mesh_area(M,3);
1052
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 remove_small_connected_components(
1053 M,
1054
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 CmdLine::get_arg_percent("co3ne:min_comp_area",Marea),
1055
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 6 CmdLine::get_arg_uint("co3ne:min_comp_facets")
1056 );
1057
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 fill_holes(
1058 M,
1059
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 CmdLine::get_arg_percent("co3ne:max_hole_area",Marea),
1060
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 6 CmdLine::get_arg_uint("co3ne:max_hole_edges")
1061 );
1062 // We do that one more time, to remove the small
1063 // connected components
1064 // yielded by the detected non-manifold edges.
1065
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 remove_small_connected_components(
1066 M,
1067
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 CmdLine::get_arg_percent("co3ne:min_comp_area",Marea),
1068
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 4 CmdLine::get_arg_uint("co3ne:min_comp_facets")
1069 );
1070
1071 // We need to do that one more time after removing the
1072 // small component, to ensure that everything is correct.
1073 2 repair_connect_facets(M);
1074 2 repair_reorient_facets_anti_moebius(M);
1075 2 repair_split_non_manifold_vertices(M,verbose);
1076
1077 }
1078
1079
2/2
✓ Branch 0 taken 158 times.
✓ Branch 1 taken 29 times.
 187 if((mode & MESH_REPAIR_QUIET) == 0) {
1080 158 if(
1081
6/6
✓ Branch 1 taken 125 times.
✓ Branch 2 taken 33 times.
✓ Branch 3 taken 20 times.
✓ Branch 4 taken 105 times.
✓ Branch 5 taken 53 times.
✓ Branch 6 taken 105 times.
 283 M.vertices.nb() != nb_vertices_in ||
1082 125 M.facets.nb() != nb_facets_in
1083 ) {
1084
2/4
✓ Branch 1 taken 53 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 53 times.
✗ Branch 5 not taken.
 106 M.show_stats("Validate");
1085 }
1086 }
1087
1088
1/2
✓ Branch 1 taken 187 times.
✗ Branch 2 not taken.
 187 if(M.vertices.dimension() >= 3) {
1089 187 orient_normals(M);
1090 }
1091 187 }
1092
1093 6 void mesh_postprocess_RDT(
1094 Mesh& M, bool verbose
1095 ) {
1096
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 vector<index_t> f_is_bad(M.facets.nb(), 0);
1097
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 vector<signed_index_t> v_nb_incident(M.vertices.nb(), 0);
1098
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 detect_bad_facets(M, true, f_is_bad, nullptr, nullptr, verbose);
1099 6 bool changed = false;
1100
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 do {
1101 6 changed = false;
1102
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 v_nb_incident.assign(M.vertices.nb(), 0);
1103
2/2
✓ Branch 5 taken 59804 times.
✓ Branch 6 taken 6 times.
 59810 for(index_t f: M.facets) {
1104
2/4
✓ Branch 1 taken 59804 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 59804 times.
✗ Branch 4 not taken.
 59804 if(f_is_bad[f] == 0) {
1105
3/4
✓ Branch 1 taken 59804 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 179412 times.
✓ Branch 8 taken 59804 times.
 239216 for(index_t c: M.facets.corners(f)) {
1106
2/4
✓ Branch 1 taken 179412 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 179412 times.
✗ Branch 5 not taken.
 179412 ++v_nb_incident[M.facet_corners.vertex(c)];
1107 }
1108 }
1109 }
1110
2/2
✓ Branch 5 taken 59804 times.
✓ Branch 6 taken 6 times.
 59810 for(index_t f: M.facets) {
1111
2/4
✓ Branch 1 taken 59804 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 59804 times.
✗ Branch 4 not taken.
 59804 if(f_is_bad[f] == 0) {
1112
3/4
✓ Branch 1 taken 59804 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 179412 times.
✓ Branch 9 taken 59804 times.
 239216 for(index_t c: M.facets.corners(f)) {
1113
3/6
✓ Branch 1 taken 179412 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 179412 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 179412 times.
 179412 if(v_nb_incident[M.facet_corners.vertex(c)] == 1) {
1114 ✗ f_is_bad[f] = 1;
1115 ✗ changed = true;
1116 ✗ break;
1117 }
1118 }
1119 }
1120 }
1121 } while(changed);
1122
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 M.facets.delete_elements(f_is_bad);
1123
1124
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 repair_connect_facets(M);
1125
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 repair_reorient_facets_anti_moebius(M);
1126
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 repair_split_non_manifold_vertices(M,verbose);
1127
1128
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if(verbose) {
1129 ✗ M.show_stats("Validate");
1130 }
1131 6 }
1132
1133 4 void mesh_reorient(Mesh& M, vector<index_t>* moebius_facets) {
1134 4 repair_reorient_facets_anti_moebius(M, moebius_facets);
1135 4 }
1136
1137 ✗ void mesh_detect_colocated_vertices(
1138 const Mesh& M, vector<index_t>& v_colocated_index,
1139 double colocate_epsilon
1140 ) {
1141 ✗ Geom::colocate(
1142 M.vertices.point_ptr(0),
1143 ✗ coord_index_t(M.vertices.dimension()),
1144 M.vertices.nb(),
1145 v_colocated_index,
1146 colocate_epsilon
1147 );
1148 ✗ }
1149
1150 ✗ void mesh_detect_isolated_vertices(
1151 const Mesh& M, vector<index_t>& v_is_isolated
1152 ) {
1153 ✗ v_is_isolated.assign(M.vertices.nb(),1);
1154 ✗ for(index_t e: M.edges) {
1155 ✗ v_is_isolated[M.edges.vertex(e,0)] = 0;
1156 ✗ v_is_isolated[M.edges.vertex(e,1)] = 0;
1157 }
1158 ✗ for(index_t f: M.facets) {
1159 ✗ for(index_t lv=0; lv<M.facets.nb_vertices(f); ++lv) {
1160 ✗ v_is_isolated[M.facets.vertex(f,lv)] = 0;
1161 }
1162 }
1163 ✗ for(index_t c: M.cells) {
1164 ✗ for(index_t lv=0; lv<M.cells.nb_vertices(c); ++lv) {
1165 ✗ v_is_isolated[M.cells.vertex(c,lv)] = 0;
1166 }
1167 }
1168 ✗ }
1169
1170 ✗ void mesh_detect_degenerate_facets(
1171 const Mesh& M, vector<index_t>& f_is_degenerate
1172 ) {
1173 ✗ f_is_degenerate.resize(M.facets.nb());
1174 ✗ for(index_t f: M.facets) {
1175 ✗ f_is_degenerate[f] = facet_is_degenerate(M,f);
1176 }
1177 ✗ }
1178
1179 218 void mesh_colocate_vertices_no_check(
1180 Mesh& M, double colocate_epsilon, bool verbose
1181 ) {
1182 218 vector<index_t> old2new;
1183
1184
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 218 times.
 218 if(M.vertices.nb() == 0) {
1185 ✗ return;
1186 }
1187
1188 218 index_t nb_new_vertices = 0;
1189
2/2
✓ Branch 0 taken 177 times.
✓ Branch 1 taken 41 times.
 218 if(colocate_epsilon == 0.0) {
1190
1/2
✓ Branch 1 taken 177 times.
✗ Branch 2 not taken.
 354 nb_new_vertices = Geom::colocate_by_lexico_sort(
1191
2/4
✓ Branch 1 taken 177 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 177 times.
✗ Branch 5 not taken.
 177 M.vertices.point_ptr(0), 3, M.vertices.nb(),
1192 old2new, M.vertices.dimension()
1193 );
1194 } else {
1195
2/4
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 41 times.
✗ Branch 5 not taken.
 123 nb_new_vertices = Geom::colocate(
1196
2/4
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 41 times.
✗ Branch 5 not taken.
 41 M.vertices.point_ptr(0), 3, M.vertices.nb(),
1197 old2new, colocate_epsilon, M.vertices.dimension()
1198 );
1199 }
1200
1201
2/2
✓ Branch 1 taken 176 times.
✓ Branch 2 taken 42 times.
 218 if(nb_new_vertices == M.vertices.nb()) {
1202 176 return;
1203 }
1204
1205
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 13 times.
 42 if(verbose) {
1206
3/6
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 29 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 29 times.
✗ Branch 8 not taken.
 87 Logger::out("Validate") << "Removed "
1207
1/2
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
 29 << M.vertices.nb() - nb_new_vertices
1208
2/4
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 29 times.
✗ Branch 5 not taken.
 29 << " duplicated vertices" << std::endl;
1209 }
1210
1211 // Replace vertex indices for edges
1212
1/2
✗ Branch 5 not taken.
✓ Branch 6 taken 42 times.
 42 for(index_t e: M.edges) {
1213 ✗ M.edges.set_vertex(e, 0, old2new[M.edges.vertex(e,0)]);
1214 ✗ M.edges.set_vertex(e, 1, old2new[M.edges.vertex(e,1)]);
1215 }
1216
1217 // Replace vertex indices for facets
1218
2/2
✓ Branch 5 taken 262272 times.
✓ Branch 6 taken 42 times.
 262314 for(index_t c: M.facet_corners) {
1219
3/6
✓ Branch 1 taken 262272 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 262272 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 262272 times.
✗ Branch 8 not taken.
 262272 M.facet_corners.set_vertex(c, old2new[M.facet_corners.vertex(c)]);
1220 }
1221
1222 // Replace vertex indices for cells
1223
1/2
✗ Branch 5 not taken.
✓ Branch 6 taken 42 times.
 42 for(index_t ce: M.cells) {
1224 ✗ for(index_t c: M.cells.corners(ce)) {
1225 ✗ M.cell_corners.set_vertex(c, old2new[M.cell_corners.vertex(c)]);
1226 }
1227 }
1228
1229 // Now old2new is "recycled" for marking vertices that
1230 // need to be removed.
1231
2/2
✓ Branch 1 taken 96398 times.
✓ Branch 2 taken 42 times.
 96440 for(index_t i = 0; i < old2new.size(); i++) {
1232
3/4
✓ Branch 1 taken 96398 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 47156 times.
✓ Branch 4 taken 49242 times.
 96398 if(old2new[i] == i) {
1233
1/2
✓ Branch 1 taken 47156 times.
✗ Branch 2 not taken.
 47156 old2new[i] = 0;
1234 } else {
1235
1/2
✓ Branch 1 taken 49242 times.
✗ Branch 2 not taken.
 49242 old2new[i] = 1;
1236 }
1237 }
1238
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 M.vertices.delete_elements(old2new);
1239
2/2
✓ Branch 5 taken 262272 times.
✓ Branch 6 taken 42 times.
 262314 for(index_t c: M.facet_corners) {
1240
1/2
✓ Branch 1 taken 262272 times.
✗ Branch 2 not taken.
 262272 M.facet_corners.set_adjacent_facet(c, NO_INDEX);
1241 }
1242
2/2
✓ Branch 1 taken 42 times.
✓ Branch 2 taken 176 times.
 218 }
1243
1244 /*************************************************************************/
1245
1246 307 void mesh_remove_bad_facets_no_check(Mesh& M, bool check_duplicates) {
1247 307 vector<index_t> remove_f;
1248 307 vector<index_t> old_polygons;
1249 307 vector<index_t> new_polygons;
1250
1/2
✓ Branch 1 taken 307 times.
✗ Branch 2 not taken.
 307 detect_bad_facets(
1251 M, check_duplicates, remove_f, &old_polygons, &new_polygons
1252 );
1253 307 index_t current_old_polygon=0;
1254
2/2
✓ Branch 1 taken 29 times.
✓ Branch 2 taken 278 times.
 307 if(remove_f.size() != 0) {
1255 // Create the new facets that correspond to input polygonal
1256 // facets that had duplicated vertices.
1257 // This needs to be done before deleting the bad facets,
1258 // else some vertices will become isolated and will be
1259 // discarded.
1260 29 index_t b=0;
1261 29 index_t e=0;
1262
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 29 times.
 29 while(b < new_polygons.size()) {
1263 ✗ while(new_polygons[e] != NO_INDEX) {
1264 ✗ ++e;
1265 }
1266 ✗ index_t new_f = M.facets.create_polygon(e-b);
1267 ✗ M.facets.attributes().copy_item(
1268 ✗ new_f, old_polygons[current_old_polygon]
1269 );
1270 ✗ ++current_old_polygon;
1271 // We created a new facet that we want to keep !!
1272 ✗ remove_f.push_back(0);
1273 ✗ for(index_t lv=0; lv<e-b; ++lv) {
1274 ✗ M.facets.set_vertex(new_f,lv,new_polygons[b+lv]);
1275 }
1276 ✗ ++e;
1277 ✗ b=e;
1278 }
1279
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 M.facets.delete_elements(remove_f);
1280 }
1281
2/2
✓ Branch 5 taken 2575914 times.
✓ Branch 6 taken 307 times.
 2576221 for(index_t c: M.facet_corners) {
1282
1/2
✓ Branch 1 taken 2575914 times.
✗ Branch 2 not taken.
 2575914 M.facet_corners.set_adjacent_facet(c, NO_INDEX);
1283 }
1284 307 }
1285
1286 /*************************************************************************/
1287
1288 }
1289