GCC Code Coverage Report

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_decimate.h>
41			#include <geogram/mesh/mesh_repair.h>
42			#include <geogram/mesh/mesh_geometry.h>
43			#include <geogram/mesh/mesh_degree3_vertices.h>
44			#include <geogram/points/colocate.h>
45			#include <geogram/basic/stopwatch.h>
46			#include <geogram/basic/algorithm.h>
47
48			namespace GEO {
49
50		✗	void mesh_decimate_vertex_clustering(
51			Mesh& M, index_t nb_bins, MeshDecimateMode mode,
52			geo_index_t* vertices_flags
53			) {
54		✗	Stopwatch W("Decimate");
55			double xyz_min[3];
56			double xyz_max[3];
57		✗	get_bbox(M, xyz_min, xyz_max);
58		✗	double R = ::sqrt(
59		✗	geo_sqr(xyz_max[0] - xyz_min[0]) +
60		✗	geo_sqr(xyz_max[1] - xyz_min[1]) +
61		✗	geo_sqr(xyz_max[2] - xyz_min[2])
62			);
63		✗	double h = R / double(nb_bins);
64
65			std::vector<bool> is_required;
66		✗	if(mode & MESH_DECIMATE_KEEP_B) {
67		✗	is_required.assign(M.vertices.nb(), false);
68		✗	for(index_t f : M.facets) {
69		✗	for(index_t c : M.facets.corners(f)) {
70		✗	if(M.facet_corners.adjacent_facet(c) == NO_FACET) {
71		✗	is_required[M.facet_corners.vertex(c)] = true;
72			}
73			}
74			}
75			}
76
77		✗	if(vertices_flags != nullptr) {
78		✗	for(index_t v: M.vertices) {
79		✗	if(vertices_flags[v] != 0) {
80			is_required[v] = true;
81			}
82			}
83			}
84
85		✗	vector<double> new_points(M.vertices.nb() * 3);
86		✗	for(index_t v: M.vertices) {
87		✗	if(is_required.size() != 0 && is_required[v]) {
88			double* p = M.vertices.point_ptr(v);
89		✗	for(coord_index_t c = 0; c < 3; ++c) {
90		✗	new_points[M.vertices.dimension() * v + c] = p[c];
91			}
92			} else {
93			double* p = M.vertices.point_ptr(v);
94		✗	for(coord_index_t c = 0; c < 3; ++c) {
95		✗	double d = p[c] - xyz_min[c];
96		✗	d = double(index_t(d / h)) * h;
97		✗	new_points[M.vertices.dimension() * v + c] = xyz_min[c] + d;
98			}
99			}
100			}
101
102			vector<index_t> old2new;
103		✗	index_t nb_new_vertices = Geom::colocate_by_lexico_sort(
104			new_points.data(), 3, M.vertices.nb(), old2new, 3
105			);
106
107		✗	if(nb_new_vertices == M.vertices.nb()) {
108		✗	Logger::warn("Decimate") << "Did not remove any vertex"
109			<< std::endl;
110			return;
111			}
112
113		✗	Logger::out("Decimate") << "Removed "
114		✗	<< M.vertices.nb() - nb_new_vertices
115			<< " vertices" << std::endl;
116
117		✗	for(index_t c: M.facet_corners) {
118		✗	M.facet_corners.set_vertex(c, old2new[M.facet_corners.vertex(c)]);
119			}
120
121			// Determine new vertices positions
122		✗	new_points.assign(M.vertices.dimension() * M.vertices.nb(), 0.0);
123		✗	vector<index_t> new_points_count(M.vertices.nb(), 0);
124
125		✗	for(index_t v: M.vertices) {
126		✗	index_t w = old2new[v];
127		✗	for(coord_index_t c = 0; c < M.vertices.dimension(); ++c) {
128		✗	new_points[w * M.vertices.dimension() + c] +=
129		✗	M.vertices.point_ptr(v)[c];
130			}
131		✗	new_points_count[w]++;
132			}
133
134		✗	for(index_t w: M.vertices) {
135		✗	double s = double(new_points_count[w]);
136		✗	if(s != 0.0) {
137		✗	s = 1.0 / s;
138			}
139		✗	for(coord_index_t c = 0; c < M.vertices.dimension(); ++c) {
140		✗	new_points[w * M.vertices.dimension() + c] *= s;
141			}
142			}
143
144		✗	M.vertices.assign_points(new_points, M.vertices.dimension(), true);
145
146			// Now old2new is "recycled" for marking vertices that
147			// need to be removed.
148		✗	for(index_t i = 0; i < old2new.size(); i++) {
149		✗	if(old2new[i] == i) {
150		✗	old2new[i] = 0;
151			} else {
152		✗	old2new[i] = 1;
153			}
154			}
155
156		✗	M.vertices.delete_elements(old2new);
157		✗	if(mode & MESH_DECIMATE_DUP_F) {
158		✗	mesh_repair(M, MESH_REPAIR_DUP_F);
159			} else {
160			// Only remove facets with duplicated vertices.
161		✗	mesh_repair(M, MeshRepairMode(0));
162			}
163
164		✗	if(mode & MESH_DECIMATE_DEG_3) {
165		✗	double max_dist = 0.001 * R;
166		✗	while(remove_degree3_vertices(M, max_dist) != 0) {}
167			}
168		✗	}
169			}
170