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 <exploragram/hexdom/quad_dominant.h>
41			#include <exploragram/hexdom/meshcomesh.h>
42			#include <exploragram/hexdom/PGP.h>
43			#include <exploragram/hexdom/basic.h>
44			#include <exploragram/hexdom/extra_connectivity.h>
45			#include <geogram/numerics/matrix_util.h>
46			#include <geogram/basic/permutation.h>
47			#include <algorithm>
48			#include <geogram/mesh/triangle_intersection.h>
49
50			#include <geogram/mesh/mesh_tetrahedralize.h>
51			#include <geogram/delaunay/delaunay.h>
52
53			#include <geogram/points/nn_search.h>
54			#include <geogram/points/colocate.h>
55			#include <queue>
56
57			#include <exploragram/hexdom/mesh_inspector.h>
58			#include <exploragram/hexdom/intersect_tools.h>
59			#include <exploragram/hexdom/polygon.h>
60
61			namespace GEO {
62
63		✗	bool find_self_intersections(Mesh* facets_with_quads_and_tri_only, vector<index_t> &intersections) {
64		✗	intersections.resize(0);
65		✗	Mesh* m = facets_with_quads_and_tri_only;
66		✗	vector<BBox> inboxes(m->facets.nb());
67		✗	FOR(f, m->facets.nb()) {
68		✗	index_t nbv = m->facets.nb_vertices(f);
69		✗	geo_assert(4 == nbv || 3 == nbv);
70		✗	FOR(fv, nbv) {
71		✗	inboxes[f].add(X(m)[m->facets.vertex(f, fv)]);
72			}
73			}
74		✗	HBoxes hb(inboxes);
75
76		✗	bool conflict_detected = false;
77		✗	FOR(f, m->facets.nb()) {
78		✗	vector<index_t> primitives;
79		✗	hb.intersect(inboxes[f], primitives);
80		✗	FOR(i, primitives.size()) {
81		✗	index_t opp_f = primitives[i];
82		✗	if (f==opp_f) continue;
83		✗	vector<vec3> P;
84		✗	FOR(fv, m->facets.nb_vertices(f)) {
85		✗	P.push_back(X(m)[m->facets.vertex(f, fv)]);
86			}
87		✗	vector<vec3> Q;
88		✗	FOR(fv, m->facets.nb_vertices(opp_f)) {
89		✗	Q.push_back(X(m)[m->facets.vertex(opp_f, fv)]);
90			}
91
92		✗	bool conflict = false;
93		✗	FOR(trP, 4) {
94		✗	FOR(trQ, 4) {
95		✗	if (trP > 0 && P.size() == 3) continue;
96		✗	if (trQ > 0 && Q.size() == 3) continue;
97		✗	TriangleIsects trash;
98		✗	conflict = conflict || triangles_intersections(
99		✗	P[quad_split[trP][0]], P[quad_split[trP][1]], P[quad_split[trP][2]],
100		✗	Q[quad_split[trQ][0]], Q[quad_split[trQ][1]], Q[quad_split[trQ][2]],
101			trash
102			);
103			}
104			}
105
106		✗	if (conflict) {
107		✗	intersections.push_back(f);
108		✗	intersections.push_back(opp_f);
109			}
110		✗	conflict_detected = conflict_detected || conflict;
111		✗	}
112		✗	}
113		✗	sort( intersections.begin(), intersections.end() );
114		✗	intersections.erase( unique( intersections.begin(), intersections.end() ), intersections.end() );
115		✗	geo_assert((conflict_detected && intersections.size()) || (!conflict_detected && !intersections.size()));
116		✗	return conflict_detected;
117		✗	}
118
119
120			/*
121			// test for self-intersection
122			// input : a surface with only triangles and quads allowed
123			// output : push_back into regions_to_lock BBoxes of self-intersections
124			bool lock_self_intersecting_regions(Mesh* mesh, Attribute<bool> &verts_to_remove, Attribute<index_t> &undo) {
125			vector<index_t> intersections;
126			bool conflict = find_self_intersections(mesh, intersections);
127			FOR(f, intersections.size()) {
128			if (undo[intersections[f]]!=NOT_AN_ID) verts_to_remove[undo[intersections[f]]] = false;
129			}
130			geo_assert(!conflict || intersections.size()>0);
131			return intersections.size()>0;
132			}
133
134			bool lock_self_intersecting_regions(Mesh* mesh, vector<BBox>& regions_to_lock) {
135			Attribute<bool> conflict(mesh->facets.attributes(), "conflict");
136			vector<index_t> intersections;
137			find_self_intersections(mesh, intersections);
138			// sort( intersections.begin(), intersections.end() );
139			// intersections.erase( unique( intersections.begin(), intersections.end() ), intersections.end() );
140
141			FOR(f, intersections.size()) {
142			BBox inbox;
143			index_t nbv = mesh->facets.nb_vertices(intersections[f]);
144			geo_assert(4 == nbv || 3 == nbv);
145			FOR(fv, nbv) {
146			inbox.add(X(mesh)[mesh->facets.vertex(intersections[f], fv)]);
147			}
148			regions_to_lock.push_back(inbox);
149			conflict[intersections[f]] = true;
150			}
151			std::cerr << "[CONFLICTING FACETS] " << intersections.size() << "\n";
152			return intersections.size()>0;
153			}
154			*/
155			// compute light connectivity (vertex to facets)
156		✗	vector<vector<index_t> > generate_v2f(Mesh *m) {
157		✗	vector<vector<index_t> > v2f(m->vertices.nb());
158		✗	FOR(f, m->facets.nb()) {
159		✗	geo_assert(m->facets.nb_vertices(f) == 3);
160		✗	FOR(lc, m->facets.nb_corners(f)) {
161		✗	v2f[m->facets.vertex(f, lc)].push_back(f);
162			}
163			}
164		✗	return v2f;
165		✗	}
166
167		✗	static void fan_asserts(Mesh *m, vector<vector<index_t> > &v2f, Attribute<index_t> &chart) {
168		✗	std::cerr << "sanity check: triangulated surface with 3 distinct vertid for each triangle...";
169		✗	FOR(f, m->facets.nb()) {
170		✗	geo_assert(3 == m->facets.nb_corners(f));
171		✗	FOR(c1, m->facets.nb_corners(f)) {
172		✗	FOR(c2, m->facets.nb_corners(f)) {
173		✗	if (c1 == c2) continue;
174		✗	geo_assert(m->facets.vertex(f, c1) != m->facets.vertex(f, c2));
175			}
176			}
177			}
178		✗	std::cerr << "ok\n";
179
180		✗	std::cerr << "sanity check: all fans are correct and for complete fans valency >= 3...";
181		✗	geo_assert(v2f.size()==m->vertices.nb());
182		✗	FOR(v, m->vertices.nb()) {
183		✗	if (!v2f[v].size()) continue;
184		✗	TrFan fan = TrFan(v, m, v2f, chart);
185		✗	geo_assert(fan.incomplete_ || v2f[v].size() >= 3);
186
187		✗	}
188		✗	std::cerr << "ok\n";
189		✗	}
190
191		✗	bool try_simplify(Mesh* m, Attribute<index_t> &chart, Attribute<bool> &verts_to_remove, Attribute<index_t> &undo) {
192			// std::cerr << "NVERTS= " << m->vertices.nb() << "\n";
193		✗	vector<index_t> to_kill(m->facets.nb(), false);
194		✗	vector<vector<index_t> > v2f = generate_v2f(m);
195		✗	bool mesh_is_modified = false;
196
197		✗	fan_asserts(m, v2f, chart);
198
199		✗	FOR(v, m->vertices.nb()) {
200		✗	if (!verts_to_remove[v] || !v2f[v].size()) continue;
201		✗	TrFan fan = TrFan(v, m, v2f, chart);
202
203		✗	fan.triangulate();
204			// if (!fan.triangulate()) continue;
205
206			{ // block of geometrical and topological sanity checks, allows to reject the triangulation
207		✗	bool non_manifold_edge = false;
208		✗	FOR(ichart, fan.ncharts()) {
209		✗	vector<index_t> &tri = fan.triangles[ichart];
210		✗	FOR(t, tri.size()/3) {
211		✗	FOR(iv, 3) {
212		✗	index_t a = tri[3*t + iv];
213		✗	index_t b = tri[3*t + (iv+1) % 3];
214
215			// (a,b) is an edge in new triangulation, let us check whether it is on the boundary of the chart
216		✗	bool fan_boundary = false;
217		✗	FOR(i, fan.nb_fan_triangles()) {
218		✗	fan_boundary = fan_boundary || (a == fan[i].org && b == fan[i].dest);
219			}
220		✗	if (fan_boundary) continue;
221
222			// here we know that (a,b) is an interior edge
223		✗	FOR(f, v2f[a].size()) {
224		✗	FOR(c, m->facets.nb_corners(v2f[a][f])) {
225		✗	non_manifold_edge = non_manifold_edge || (b == m->facets.vertex(v2f[a][f], c));
226			}
227			}
228			}
229			}
230			}
231		✗	if (non_manifold_edge) {
232		✗	error("this triangulation would introduce a non manifold edge, rejecting");
233		✗	continue;
234			}
235			}
236
237		✗	mesh_is_modified = true;
238
239		✗	FOR(ichart, fan.ncharts()) {
240		✗	vector<index_t> &tri = fan.triangles[ichart];
241		✗	FOR(t, tri.size() / 3) {
242		✗	index_t new_f = m->facets.create_triangle(tri[3*t + 0], tri[3*t + 1], tri[3*t + 2]);
243		✗	m->facets.attributes().copy_item(new_f, fan[fan.chart_offset[ichart]].f);
244		✗	undo[new_f] = v;
245		✗	to_kill.push_back(false);
246
247		✗	FOR(lc, 3) {
248		✗	v2f[m->facets.vertex(new_f, lc)].push_back(new_f);
249			}
250			}
251			}
252
253			// update light connection info
254		✗	FOR(i, v2f[fan.v_].size()) {
255		✗	to_kill[v2f[fan.v_][i]] = true;
256			}
257		✗	v2f[fan.v_].clear();
258
259		✗	FOR(i, fan.nb_fan_triangles()) {
260		✗	index_t f = fan[i].f;
261		✗	index_t org = fan[i].org;
262		✗	index_t dest = fan[i].dest;
263
264		✗	index_t vopp[2] = { org, dest };
265
266		✗	FOR(j, 2) {
267		✗	FOR(fi, v2f[vopp[j]].size()) {
268		✗	if (v2f[vopp[j]][fi] != f) continue;
269		✗	v2f[vopp[j]][fi] = v2f[vopp[j]].back();
270		✗	v2f[vopp[j]].pop_back();
271		✗	break;
272			}
273			}
274			}
275		✗	}
276
277		✗	fan_asserts(m, v2f, chart);
278
279			// std::cerr << "NVERTS= " << m->vertices.nb() << "\n";
280		✗	m->facets.delete_elements(to_kill, false);
281			// kill_isolated_vertices(m);
282			// std::cerr << "NVERTS= " << m->vertices.nb() << "\n";
283			// std::cerr << "modified " << mesh_is_modified << "\n";
284		✗	return mesh_is_modified;
285		✗	}
286
287			}
288