GCC Code Coverage Report

Directory: ./
File: lib/geogram/mesh/mesh_topology.cpp
Date: 2026-09-07 02:37:58
Exec Total Coverage
Lines: 133 141 94.3%
Functions: 8 8 100.0%
Branches: 179 296 60.5%
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_topology.h>
41 #include <geogram/mesh/mesh.h>
42 #include <geogram/basic/memory.h>
43 #include <geogram/basic/logger.h>
44 #include <stack>
45
46 namespace {
47
48 using namespace GEO;
49
50 /**
51 * \brief Computes the number of surface vertices that are not isolated.
52 * \param[in] M the mesh
53 * \return the number of vertices of a mesh with at least
54 * one incident surface facet
55 */
56 153 index_t nb_non_isolated_surface_vertices(const Mesh& M) {
57 153 index_t result = 0;
58
1/2
✓ Branch 2 taken 153 times.
✗ Branch 3 not taken.
 153 std::vector<bool> visited(M.vertices.nb(), false);
59
2/2
✓ Branch 4 taken 1434285 times.
✓ Branch 5 taken 153 times.
 1434438 for(index_t c: M.facet_corners) {
60
1/2
✓ Branch 1 taken 1434285 times.
✗ Branch 2 not taken.
 1434285 visited[M.facet_corners.vertex(c)] = true;
61 }
62
2/2
✓ Branch 5 taken 320590 times.
✓ Branch 6 taken 153 times.
 320743 for(index_t v: M.vertices) {
63
2/2
✓ Branch 2 taken 319925 times.
✓ Branch 3 taken 665 times.
 320590 if(visited[v]) {
64 319925 ++result;
65 }
66 }
67 153 return result;
68 153 }
69 }
70
71 namespace GEO {
72
73 396 index_t get_connected_components(
74 const Mesh& M, vector<index_t>& component
75 ) {
76 396 index_t nb_components = 0;
77 396 component.assign(M.facets.nb(), NO_INDEX);
78
2/2
✓ Branch 5 taken 1618129 times.
✓ Branch 6 taken 396 times.
 1618525 for(index_t f: M.facets) {
79
3/4
✓ Branch 1 taken 1618129 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1346 times.
✓ Branch 4 taken 1616783 times.
 1618129 if(component[f] == NO_INDEX) {
80
1/2
✓ Branch 1 taken 1346 times.
✗ Branch 2 not taken.
 1346 std::stack<index_t> S;
81
1/2
✓ Branch 1 taken 1346 times.
✗ Branch 2 not taken.
 1346 S.push(f);
82
1/2
✓ Branch 1 taken 1346 times.
✗ Branch 2 not taken.
 1346 component[f] = nb_components;
83 do {
84
1/2
✓ Branch 1 taken 1618129 times.
✗ Branch 2 not taken.
 1618129 index_t cur_f = S.top();
85
1/2
✓ Branch 1 taken 1618129 times.
✗ Branch 2 not taken.
 1618129 S.pop();
86
6/10
✓ Branch 1 taken 1618129 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1618129 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1618129 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 5084070 times.
✗ Branch 11 not taken.
✓ Branch 14 taken 5084070 times.
✓ Branch 15 taken 1618129 times.
 6702199 for(index_t adj_f: M.facets.adjacent(cur_f)) {
87
7/8
✓ Branch 0 taken 5058732 times.
✓ Branch 1 taken 25338 times.
✓ Branch 3 taken 5058732 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1616783 times.
✓ Branch 6 taken 3441949 times.
✓ Branch 7 taken 1616783 times.
✓ Branch 8 taken 3467287 times.
 5084070 if(adj_f != NO_FACET && component[adj_f] == NO_INDEX) {
88
1/2
✓ Branch 1 taken 1616783 times.
✗ Branch 2 not taken.
 1616783 S.push(index_t(adj_f));
89
1/2
✓ Branch 1 taken 1616783 times.
✗ Branch 2 not taken.
 1616783 component[adj_f] = nb_components;
90 }
91 }
92
2/2
✓ Branch 1 taken 1616783 times.
✓ Branch 2 taken 1346 times.
 1618129 } while(!S.empty());
93 1346 nb_components++;
94 1346 }
95 }
96 396 return nb_components;
97 }
98
99 131 index_t GEOGRAM_API get_connected_components(
100 const Mesh& M, Attribute<index_t>& component
101 ) {
102 131 index_t nb_components = 0;
103
2/2
✓ Branch 4 taken 856224 times.
✓ Branch 5 taken 131 times.
 856355 for(index_t f: M.facets) {
104
1/2
✓ Branch 1 taken 856224 times.
✗ Branch 2 not taken.
 856224 component[f] = NO_INDEX;
105 }
106
2/2
✓ Branch 5 taken 856224 times.
✓ Branch 6 taken 131 times.
 856355 for(index_t f: M.facets) {
107
3/4
✓ Branch 1 taken 856224 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 9066 times.
✓ Branch 4 taken 847158 times.
 856224 if(component[f] == NO_INDEX) {
108
1/2
✓ Branch 1 taken 9066 times.
✗ Branch 2 not taken.
 9066 std::stack<index_t> S;
109
1/2
✓ Branch 1 taken 9066 times.
✗ Branch 2 not taken.
 9066 S.push(f);
110
1/2
✓ Branch 1 taken 9066 times.
✗ Branch 2 not taken.
 9066 component[f] = nb_components;
111 do {
112
1/2
✓ Branch 1 taken 856224 times.
✗ Branch 2 not taken.
 856224 index_t cur_f = S.top();
113
1/2
✓ Branch 1 taken 856224 times.
✗ Branch 2 not taken.
 856224 S.pop();
114
6/10
✓ Branch 1 taken 856224 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 856224 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 856224 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 2568672 times.
✗ Branch 11 not taken.
✓ Branch 14 taken 2568672 times.
✓ Branch 15 taken 856224 times.
 3424896 for(index_t adj_f: M.facets.adjacent(cur_f)) {
115
7/8
✓ Branch 0 taken 2404714 times.
✓ Branch 1 taken 163958 times.
✓ Branch 3 taken 2404714 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 847158 times.
✓ Branch 6 taken 1557556 times.
✓ Branch 7 taken 847158 times.
✓ Branch 8 taken 1721514 times.
 2568672 if(adj_f != NO_FACET && component[adj_f] == NO_INDEX) {
116
1/2
✓ Branch 1 taken 847158 times.
✗ Branch 2 not taken.
 847158 S.push(index_t(adj_f));
117
1/2
✓ Branch 1 taken 847158 times.
✗ Branch 2 not taken.
 847158 component[adj_f] = nb_components;
118 }
119 }
120
2/2
✓ Branch 1 taken 847158 times.
✓ Branch 2 taken 9066 times.
 856224 } while(!S.empty());
121 9066 nb_components++;
122 9066 }
123 }
124 131 return nb_components;
125 }
126
127 155 index_t mesh_nb_connected_components(const Mesh& M) {
128 155 vector<index_t> component;
129
1/2
✓ Branch 1 taken 155 times.
✗ Branch 2 not taken.
 310 return get_connected_components(M, component);
130 155 }
131
132 153 signed_index_t mesh_Xi(const Mesh& M) {
133 153 index_t nb_v = nb_non_isolated_surface_vertices(M);
134
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 152 times.
 153 if(nb_v != M.vertices.nb()) {
135
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 1 if(M.cells.nb() == 0) {
136 ✗ Logger::warn("Topology")
137 ✗ << "Surface mesh has " << M.vertices.nb() - nb_v
138 ✗ << " isolated vertices"
139 ✗ << std::endl;
140 } else {
141
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 3 Logger::out("Topology")
142
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 << "Surface mesh has " << M.vertices.nb() - nb_v
143 << " isolated vertices "
144
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 << " (but they may be attached to tetrahedra)"
145
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 << std::endl;
146 }
147 }
148 153 signed_index_t result = signed_index_t(nb_v + M.facets.nb());
149
2/2
✓ Branch 5 taken 401534 times.
✓ Branch 6 taken 153 times.
 401687 for(index_t f: M.facets) {
150
3/4
✓ Branch 1 taken 401534 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 1434285 times.
✓ Branch 9 taken 401534 times.
 1835819 for(index_t c: M.facets.corners(f)) {
151
1/2
✓ Branch 1 taken 1434285 times.
✗ Branch 2 not taken.
 1434285 index_t f2 = M.facet_corners.adjacent_facet(c);
152
4/4
✓ Branch 0 taken 1425734 times.
✓ Branch 1 taken 8551 times.
✓ Branch 2 taken 712867 times.
✓ Branch 3 taken 712867 times.
 1434285 if(f2 == NO_FACET || f > f2) {
153 721418 --result;
154 } // We count each edge once,
155 }
156 }
157 153 return result;
158 }
159
160 155 signed_index_t mesh_nb_borders(const Mesh& M) {
161 // Step 1: chain vertices around borders
162
1/2
✓ Branch 2 taken 155 times.
✗ Branch 3 not taken.
 155 std::vector<index_t> next_around_border(M.vertices.nb(),NO_VERTEX);
163
2/2
✓ Branch 5 taken 525045 times.
✓ Branch 6 taken 154 times.
 525199 for(index_t f: M.facets) {
164
3/4
✓ Branch 1 taken 525045 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 1805162 times.
✓ Branch 9 taken 525044 times.
 2330206 for(index_t c1: M.facets.corners(f)) {
165
3/4
✓ Branch 1 taken 1805162 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7723 times.
✓ Branch 4 taken 1797439 times.
 1805162 if(M.facet_corners.adjacent_facet(c1) == NO_FACET) {
166
1/2
✓ Branch 1 taken 7723 times.
✗ Branch 2 not taken.
 7723 index_t c2 = M.facets.next_corner_around_facet(f, c1);
167
1/2
✓ Branch 1 taken 7723 times.
✗ Branch 2 not taken.
 7723 index_t v1 = M.facet_corners.vertex(c1);
168
1/2
✓ Branch 1 taken 7723 times.
✗ Branch 2 not taken.
 7723 index_t v2 = M.facet_corners.vertex(c2);
169
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 7722 times.
 7723 if(next_around_border[v1] != NO_VERTEX) {
170 // If this happens, then the same vertex
171 // is incident to more than two edges on
172 // the border (non-manifold configuration,
173 // return "error value" -1)
174 1 return -1;
175 }
176 // May happen with non-manifold configuration,
177 // where several connected component of the
178 // border can touch the same vertex several
179 // times.
180 7722 next_around_border[v1] = v2;
181 }
182 }
183 }
184 // Step 2: count connected components of the borders
185 154 index_t result = 0;
186
2/2
✓ Branch 5 taken 382113 times.
✓ Branch 6 taken 154 times.
 382267 for(index_t v: M.vertices) {
187
2/2
✓ Branch 1 taken 159 times.
✓ Branch 2 taken 381954 times.
 382113 if(next_around_border[v] != NO_VERTEX) {
188 159 result++;
189 159 index_t cur = v;
190
2/2
✓ Branch 1 taken 7716 times.
✓ Branch 2 taken 159 times.
 7875 while(next_around_border[cur] != NO_VERTEX) {
191 7716 index_t next = next_around_border[cur];
192 7716 next_around_border[cur] = NO_VERTEX;
193 7716 cur = next;
194 }
195 }
196 }
197 154 return signed_index_t(result);
198 155 }
199
200 70 bool meshes_have_same_topology(
201 const Mesh& M1, const Mesh& M2, bool verbose
202 ) {
203 70 signed_index_t Xi1 = mesh_Xi(M1);
204 70 signed_index_t Xi2 = mesh_Xi(M2);
205
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 70 if(!verbose && Xi1 != Xi2) {
206 ✗ return false;
207 }
208
209 70 signed_index_t nbB1 = mesh_nb_borders(M1);
210 70 signed_index_t nbB2 = mesh_nb_borders(M2);
211
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 70 if(!verbose && nbB1 != nbB2) {
212 ✗ return false;
213 }
214
215 70 index_t nb_conn1 = mesh_nb_connected_components(M1);
216 70 index_t nb_conn2 = mesh_nb_connected_components(M2);
217
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 70 if(!verbose && nb_conn1 != nb_conn2) {
218 ✗ return false;
219 }
220
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 70 times.
 70 if(!verbose) {
221 ✗ return true;
222 }
223
224
5/6
✓ Branch 0 taken 69 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 68 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 68 times.
✗ Branch 5 not taken.
 70 bool result = (Xi1 == Xi2 && nbB1 == nbB2 && nb_conn1 == nb_conn2);
225
2/4
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 70 times.
✗ Branch 5 not taken.
 210 Logger::out("Topology")
226
3/6
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 70 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 70 times.
✗ Branch 8 not taken.
 70 << "M1: Xi=" << Xi1 << " nbB=" << nbB1
227
4/8
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 70 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 70 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 70 times.
✗ Branch 11 not taken.
 70 << " nbConn=" << nb_conn1 << std::endl;
228
229
2/4
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 70 times.
✗ Branch 5 not taken.
 210 Logger::out("Topology")
230
3/6
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 70 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 70 times.
✗ Branch 8 not taken.
 70 << "M2: Xi=" << Xi2 << " nbB=" << nbB2
231
4/8
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 70 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 70 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 70 times.
✗ Branch 11 not taken.
 70 << " nbConn=" << nb_conn2 << std::endl;
232
233
5/8
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 70 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 68 times.
✓ Branch 7 taken 2 times.
✓ Branch 9 taken 70 times.
✗ Branch 10 not taken.
 140 Logger::out("Topology") << (result ? "match." : "mismatch.")
234
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 << std::endl;
235 70 return result;
236 }
237
238 19 void reorient_connected_components(Mesh& surf) {
239 19 vector<index_t> component;
240
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 index_t nb_components = get_connected_components(surf, component);
241
242
2/4
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 19 times.
✗ Branch 5 not taken.
 19 vector<vec3> comp_G(nb_components,{0.0,0.0,0.0});
243
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 vector<index_t> comp_N(nb_components,0);
244
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 vector<double> comp_signed_V(nb_components,0.0);
245
246
2/2
✓ Branch 5 taken 48562 times.
✓ Branch 6 taken 19 times.
 48581 for(index_t f: surf.facets) {
247
1/2
✓ Branch 1 taken 48562 times.
✗ Branch 2 not taken.
 48562 index_t comp = component[f];
248
3/4
✓ Branch 1 taken 194248 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 145686 times.
✓ Branch 4 taken 48562 times.
 194248 for(index_t lv=0; lv<surf.facets.nb_vertices(f); ++lv) {
249
1/2
✓ Branch 1 taken 145686 times.
✗ Branch 2 not taken.
 145686 index_t v = surf.facets.vertex(f,lv);
250
2/4
✓ Branch 1 taken 145686 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 145686 times.
✗ Branch 5 not taken.
 145686 comp_G[comp] += surf.vertices.point(v);
251
1/2
✓ Branch 1 taken 145686 times.
✗ Branch 2 not taken.
 145686 ++comp_N[comp];
252 }
253 }
254
255
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 19 times.
 55 for(index_t comp=0; comp<nb_components; ++comp) {
256
2/4
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
 36 comp_G[comp] /= double(comp_N[comp]);
257 }
258
259
2/2
✓ Branch 5 taken 48562 times.
✓ Branch 6 taken 19 times.
 48581 for(index_t f: surf.facets) {
260
1/2
✓ Branch 1 taken 48562 times.
✗ Branch 2 not taken.
 48562 index_t comp = component[f];
261
7/12
✓ Branch 1 taken 48562 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48562 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 48562 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 48562 times.
✗ Branch 11 not taken.
✓ Branch 16 taken 97124 times.
✗ Branch 17 not taken.
✓ Branch 18 taken 48562 times.
✓ Branch 19 taken 48562 times.
 97124 for(auto [ p1, p2, p3] : surf.facets.triangle_points(f)) {
262
2/4
✓ Branch 1 taken 48562 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48562 times.
✗ Branch 5 not taken.
 48562 comp_signed_V[comp] += Geom::tetra_signed_volume(
263
2/4
✓ Branch 1 taken 48562 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48562 times.
✗ Branch 5 not taken.
 48562 comp_G[comp],p1,p2,p3
264 );
265 }
266 }
267
268
2/2
✓ Branch 5 taken 48562 times.
✓ Branch 6 taken 19 times.
 48581 for(index_t f: surf.facets) {
269
1/2
✓ Branch 1 taken 48562 times.
✗ Branch 2 not taken.
 48562 index_t comp = component[f];
270
3/4
✓ Branch 1 taken 48562 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 9776 times.
✓ Branch 4 taken 38786 times.
 48562 if(comp_signed_V[comp] < 0.0) {
271
1/2
✓ Branch 1 taken 9776 times.
✗ Branch 2 not taken.
 9776 surf.facets.flip(f);
272 }
273 }
274 19 }
275
276 }
277