GCC Code Coverage Report

Directory: ./
File: lib/geogram/mesh/mesh_preprocessing.cpp
Date: 2026-09-07 02:37:58
Exec Total Coverage
Lines: 52 101 51.5%
Functions: 5 7 71.4%
Branches: 73 230 31.7%
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_preprocessing.h>
41 #include <geogram/mesh/mesh_topology.h>
42 #include <geogram/mesh/mesh_geometry.h>
43 #include <geogram/mesh/index.h>
44 #include <geogram/mesh/mesh_halfedges.h>
45 #include <geogram/basic/geometry_nd.h>
46 #include <geogram/basic/stopwatch.h>
47
48 #include <stack>
49
50 namespace {
51
52 using namespace GEO;
53
54 /**
55 * \brief
56 * Compute the signed volume of the pyramid that connects
57 * the origin to facet f.
58 * \details Summing all the signed volumes
59 * of the facets of a closed surface results in the signed
60 * volume of the interior of the surface (volumes outside
61 * the surface cancel-out).
62 * \param[in] M the mesh
63 * \param[in] f index of the facet
64 * \return the signed volume of the pyramid that connects facet \p f to
65 * the origin
66 */
67 745895 double signed_volume(const Mesh& M, index_t f) {
68 745895 double result = 0;
69
7/12
✓ Branch 1 taken 745895 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 745895 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 745895 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 745895 times.
✗ Branch 11 not taken.
✓ Branch 16 taken 1491790 times.
✗ Branch 17 not taken.
✓ Branch 18 taken 745895 times.
✓ Branch 19 taken 745895 times.
 1491790 for(auto [ p1, p2, p3] : M.facets.triangle_points(f)) {
70
1/2
✓ Branch 3 taken 745895 times.
✗ Branch 4 not taken.
 745895 result += dot(p1,cross(p2, p3)) / 6.0;
71 }
72 745895 return result;
73 }
74 }
75
76 /****************************************************************************/
77
78 namespace GEO {
79
80 2 void expand_border(Mesh& M, double epsilon) {
81
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 if(epsilon == 0.0) {
82 ✗ return;
83 }
84 2 vector<vec3> border_normal;
85
1/2
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
 2 border_normal.assign(M.vertices.nb(), vec3(0.0, 0.0, 0.0));
86
2/2
✓ Branch 5 taken 458 times.
✓ Branch 6 taken 2 times.
 460 for(index_t f: M.facets) {
87
1/2
✓ Branch 1 taken 458 times.
✗ Branch 2 not taken.
 458 vec3 N = Geom::mesh_facet_normal(M, f);
88
3/4
✓ Branch 1 taken 458 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 1374 times.
✓ Branch 9 taken 458 times.
 1832 for(index_t c1: M.facets.corners(f)) {
89
2/4
✓ Branch 1 taken 1374 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1374 times.
 1374 if(M.facet_corners.adjacent_facet(c1) == NO_FACET) {
90 ✗ index_t c2 = M.facets.next_corner_around_facet(f, c1);
91 ✗ index_t v1 = M.facet_corners.vertex(c1);
92 ✗ index_t v2 = M.facet_corners.vertex(c2);
93 ✗ const vec3& p1 = M.vertices.point(v1);
94 ✗ const vec3& p2 = M.vertices.point(v2);
95 ✗ vec3 Ne = cross(p2 - p1, N);
96 ✗ border_normal[v1] += Ne;
97 ✗ border_normal[v2] += Ne;
98 }
99 }
100 }
101
2/2
✓ Branch 5 taken 229 times.
✓ Branch 6 taken 2 times.
 231 for(index_t v: M.vertices) {
102
2/4
✓ Branch 1 taken 229 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 229 times.
✗ Branch 5 not taken.
 229 double s = length(border_normal[v]);
103
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 229 times.
 229 if(s > 0.0) {
104 ✗ M.vertices.point(v) +=
105 ✗ epsilon * (1.0 / s) * border_normal[v];
106 }
107 }
108 2 }
109
110 // == connected components and small facets ================================
111
112 6 void remove_small_facets(Mesh& M, double min_facet_area) {
113
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 vector<index_t> remove_f(M.facets.nb(), 0);
114
2/2
✓ Branch 5 taken 7798 times.
✓ Branch 6 taken 6 times.
 7804 for(index_t f: M.facets) {
115
2/4
✓ Branch 1 taken 7798 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 7798 times.
 7798 if(Geom::mesh_facet_area(M, f, 3) < min_facet_area) {
116 ✗ remove_f[f] = 1;
117 }
118 }
119
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 M.facets.delete_elements(remove_f);
120 6 }
121
122 14 void remove_small_connected_components(
123 Mesh& M, double min_area, index_t min_facets
124 ) {
125 14 vector<index_t> component;
126
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 index_t nb_components = get_connected_components(M, component);
127
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 vector<double> comp_area(nb_components, 0.0);
128
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 vector<index_t> comp_facets(nb_components, 0);
129
2/2
✓ Branch 4 taken 297151 times.
✓ Branch 5 taken 14 times.
 297165 for(index_t f: M.facets) {
130
3/6
✓ Branch 1 taken 297151 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 297151 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 297151 times.
✗ Branch 8 not taken.
 297151 comp_area[component[f]] += Geom::mesh_facet_area(M, f, 3);
131
2/4
✓ Branch 1 taken 297151 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 297151 times.
✗ Branch 5 not taken.
 297151 ++comp_facets[component[f]];
132 }
133
134
2/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
 28 Logger::out("Components")
135
3/6
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 14 times.
✗ Branch 9 not taken.
 14 << "Nb connected components=" << comp_area.size() << std::endl;
136 14 index_t nb_remove = 0;
137
2/2
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 14 times.
 28 for(index_t c = 0; c < comp_area.size(); c++) {
138
5/10
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 14 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 14 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 14 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 14 times.
 14 if(comp_area[c] < min_area || comp_facets[c] < min_facets) {
139 ✗ nb_remove++;
140 }
141 }
142
143
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 if(nb_remove == 0) {
144
2/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
 28 Logger::out("Components")
145
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 << "Mesh does not have small connected component (good)"
146
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 << std::endl;
147 14 return;
148 }
149
150 ✗ index_t nb_f_remove = 0;
151 ✗ vector<index_t> remove_f(M.facets.nb(), 0);
152 ✗ for(index_t f: M.facets) {
153 ✗ if(
154 ✗ comp_area[component[f]] < min_area ||
155 ✗ comp_facets[component[f]] < min_facets
156 ) {
157 ✗ remove_f[f] = 1;
158 ✗ nb_f_remove++;
159 }
160 }
161 ✗ M.facets.delete_elements(remove_f);
162
163 ✗ Logger::out("Components")
164 ✗ << "Removed " << nb_remove << " connected components"
165 ✗ << "(" << nb_f_remove << " facets)"
166 ✗ << std::endl;
167
3/6
✗ Branch 2 not taken.
✓ Branch 3 taken 14 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 14 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 14 times.
 42 }
168
169 // ============== orient_normals ========================================
170
171 208 void orient_normals(Mesh& M) {
172 208 vector<index_t> component;
173
1/2
✓ Branch 1 taken 208 times.
✗ Branch 2 not taken.
 208 index_t nb_components = get_connected_components(M, component);
174
1/2
✓ Branch 1 taken 208 times.
✗ Branch 2 not taken.
 208 vector<double> comp_signed_volume(nb_components, 0.0);
175
2/2
✓ Branch 4 taken 745895 times.
✓ Branch 5 taken 208 times.
 746103 for(index_t f: M.facets) {
176
3/6
✓ Branch 1 taken 745895 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 745895 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 745895 times.
✗ Branch 8 not taken.
 745895 comp_signed_volume[component[f]] += signed_volume(M, f);
177 }
178
2/2
✓ Branch 5 taken 745895 times.
✓ Branch 6 taken 208 times.
 746103 for(index_t f: M.facets) {
179
4/6
✓ Branch 1 taken 745895 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 745895 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 187973 times.
✓ Branch 7 taken 557922 times.
 745895 if(comp_signed_volume[component[f]] < 0.0) {
180
1/2
✓ Branch 1 taken 187973 times.
✗ Branch 2 not taken.
 187973 M.facets.flip(f);
181 }
182 }
183 208 }
184
185 ✗ void invert_normals(Mesh& M) {
186 ✗ for(index_t f: M.facets) {
187 ✗ M.facets.flip(f);
188 }
189 ✗ }
190
191 /************************************************************************/
192
193 ✗ void remove_degree2_vertices(Mesh& M) {
194 ✗ std::set<index_t> to_dissociate;
195 ✗ for(index_t f: M.facets) {
196 ✗ for(index_t i1: M.facets.corners(f)) {
197 ✗ index_t i2 = M.facets.next_corner_around_facet(f,i1);
198 ✗ index_t f1 = M.facet_corners.adjacent_facet(i1);
199 ✗ index_t f2 = M.facet_corners.adjacent_facet(i2);
200 ✗ if(f1 != NO_FACET && f1 == f2) {
201 ✗ to_dissociate.insert(f);
202 ✗ to_dissociate.insert(f1);
203 }
204 }
205 }
206 ✗ if(!to_dissociate.empty()) {
207 ✗ GEO::Logger::warn("Mesh")
208 ✗ << to_dissociate.size()
209 ✗ << " facets with degree 2 vertices (fixed)"
210 ✗ << std::endl;
211 }
212 ✗ for(auto f : to_dissociate) {
213 ✗ for(index_t c: M.facets.corners(f)) {
214 ✗ M.facet_corners.set_adjacent_facet(c,NO_FACET);
215 }
216 }
217 ✗ }
218
219 /************************************************************************/
220 }
221