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_local_operations.h>
41			#include <geogram/mesh/mesh_halfedges.h>
42			#include <geogram/mesh/mesh.h>
43
44			namespace {
45
46			using namespace GEO;
47
48			/**
49			* \brief Finds the corner of a facet that is adjacent to a given facet.
50			* \param[in] M a const reference to a Mesh
51			* \param[in] f a facet index in \p M
52			* \param[in] f_adj a facet index in \p M
53			* \return the corner of facet \p f that is adjacent to facet \p f_adj
54			* or NO_FACET if no such corner exists
55			*/
56		✗	index_t find_corner_by_adjacent_facet(
57			const Mesh& M, index_t f, index_t f_adj
58			) {
59		✗	for(index_t c: M.facets.corners(f)) {
60		✗	if(M.facet_corners.adjacent_facet(c) == f_adj) {
61			return c;
62			}
63			}
64			return NO_CORNER;
65			}
66
67			/**
68			* \brief Copies a mesh vertex.
69			* \details It is not correct to use:
70			* \code
71			* M.vertices.create_vertex(M.vertices.point_ptr(v));
72			* \endcode
73			* because Mesh::create_vertex() may realloc the points coordinates
74			* vector, thus invalidating M.vertices.point_ptr(v).
75			* \param[in] M a reference to the mesh
76			* \param[in] v the index of the vertex to be copied
77			* \return the index of the new vertex
78			*/
79		✗	index_t copy_vertex(Mesh& M, index_t v) {
80			index_t result = M.vertices.create_vertex();
81			double* to = M.vertices.point_ptr(result);
82			const double* from = M.vertices.point_ptr(v);
83		✗	for(index_t c=0; c<M.vertices.dimension(); ++c) {
84		✗	to[c] = from[c];
85			}
86		✗	return result;
87			}
88			}
89
90
91			/****************************************************************************/
92
93			namespace GEO {
94
95		✗	void glue_edges(
96			Mesh& M,
97			index_t f1, index_t c1,
98			index_t f2, index_t c2
99			) {
100		✗	geo_assert(M.facet_corners.adjacent_facet(c1) == NO_FACET);
101		✗	geo_assert(M.facet_corners.adjacent_facet(c2) == NO_FACET);
102			geo_debug_assert(c1 >= M.facets.corners_begin(f1));
103			geo_debug_assert(c1 < M.facets.corners_end(f1));
104			geo_debug_assert(c2 >= M.facets.corners_begin(f2));
105			geo_debug_assert(c2 < M.facets.corners_end(f2));
106
107
108			// Glue geometry
109			{
110			index_t v1 = M.facet_corners.vertex(c1);
111			index_t v2 = M.facet_corners.vertex(
112			M.facets.next_corner_around_facet(f1,c1)
113			);
114
115			double* p1 = M.vertices.point_ptr(v1);
116			double* p2 = M.vertices.point_ptr(v2);
117
118			index_t w1 = M.facet_corners.vertex(c2);
119			index_t w2 = M.facet_corners.vertex(
120			M.facets.next_corner_around_facet(f2,c2)
121			);
122
123			double* q1 = M.vertices.point_ptr(w1);
124			double* q2 = M.vertices.point_ptr(w2);
125
126		✗	for(index_t c=0; c<M.vertices.dimension(); ++c) {
127		✗	p1[c] = 0.5*(p1[c] + q2[c]);
128		✗	q1[c] = 0.5*(q1[c] + p2[c]);
129			}
130			}
131
132
133			index_t f[2];
134		✗	f[0] = f1;
135		✗	f[1] = f2;
136			index_t c[2];
137		✗	c[0] = c1;
138		✗	c[1] = c2;
139
140		✗	vector<index_t> delete_vertex(M.vertices.nb(),0);
141
142			// We need to keep the corners to update in a temporary
143			// vector, since updating them during the traversal would
144			// break the traversal (don't saw the branch you are sitting
145			// on !!)
146
147		✗	for(index_t k=0; k<2; ++k) {
148		✗	index_t v = M.facet_corners.vertex(c[k]);
149			vector<index_t> corners_to_update;
150			MeshHalfedges MH(M);
151			{
152		✗	MeshHalfedges::Halfedge H(f[k],c[k]);
153			do {
154		✗	index_t w = M.facet_corners.vertex(H.corner);
155		✗	if(w != v) {
156		✗	delete_vertex[w] = 1;
157			corners_to_update.push_back(H.corner);
158			}
159		✗	} while(MH.move_to_prev_around_vertex(H));
160			}
161			{
162		✗	MeshHalfedges::Halfedge H(f[1-k], c[1-k]);
163		✗	MH.move_to_next_around_border(H);
164			do {
165		✗	index_t w = M.facet_corners.vertex(H.corner);
166		✗	if(w != v) {
167		✗	delete_vertex[w] = 1;
168			corners_to_update.push_back(H.corner);
169			}
170		✗	} while(MH.move_to_prev_around_vertex(H));
171
172			}
173		✗	for(index_t i=0; i<corners_to_update.size(); ++i) {
174		✗	M.facet_corners.set_vertex(
175			corners_to_update[i],v
176			);
177			}
178			}
179
180			M.facet_corners.set_adjacent_facet(c[0],f[1]);
181			M.facet_corners.set_adjacent_facet(c[1],f[0]);
182
183
184
185		✗	M.vertices.delete_elements(delete_vertex);
186		✗	}
187
188		✗	void unglue_edges(
189			Mesh& M,
190			index_t f1, index_t c1
191			) {
192			geo_debug_assert(c1 >= M.facets.corners_begin(f1));
193			geo_debug_assert(c1 < M.facets.corners_end(f1));
194			index_t f2 = M.facet_corners.adjacent_facet(c1);
195		✗	geo_assert(f2 != NO_FACET);
196		✗	index_t c2 = find_corner_by_adjacent_facet(M,f2,f1);
197		✗	geo_assert(c2 != NO_CORNER);
198
199			M.facet_corners.set_adjacent_facet(c1,NO_FACET);
200			M.facet_corners.set_adjacent_facet(c2,NO_FACET);
201
202			// Now, we need to determine whether edge extremities were dissociated.
203
204			MeshHalfedges MH(M);
205
206			MeshHalfedges::Halfedge H1(f1,c1);
207			MeshHalfedges::Halfedge H2(f2,c2);
208
209		✗	MeshHalfedges::Halfedge H1_prev(H1);
210		✗	MH.move_to_prev_around_border(H1_prev);
211		✗	MeshHalfedges::Halfedge H1_next(H1);
212		✗	MH.move_to_next_around_border(H1_next);
213
214			// If the predecessor of H1 around the border is not H2, then
215			// H1's origin was splitted into two vertices. Thus we
216			// create the new vertex and assign it to H1's origin (c1).
217			if(H1_prev != H2) {
218			vector<index_t> corners_to_update;
219			index_t v = M.facet_corners.vertex(c1);
220		✗	index_t new_v = copy_vertex(M,v);
221
222			// Note: we cannot set the corner vertices while we
223			// are traversing, since traversal relies on corner-vertex
224			// relations (do not saw the branch you are sitting on...),
225			// thus we store the corners to be updated in a temporary
226			// vector (a bit ugly, but not a big drama).
227		✗	MeshHalfedges::Halfedge H(H1);
228			do {
229			corners_to_update.push_back(H.corner);
230		✗	} while(MH.move_to_prev_around_vertex(H));
231		✗	for(index_t i=0; i<corners_to_update.size(); ++i) {
232		✗	M.facet_corners.set_vertex(
233			corners_to_update[i],new_v
234			);
235			}
236			}
237
238			// If the successor of H1 around the border is not H2, then
239			// H2's origin was splitted into two vertices. Thus we
240			// create the new vertex and assign it to H2's origin (c2).
241			if(H1_next != H2) {
242			vector<index_t> corners_to_update;
243			index_t v = M.facet_corners.vertex(c2);
244		✗	index_t new_v = copy_vertex(M,v);
245			// Note: we cannot set the corner vertices while we
246			// are traversing, since traversal relies on corner-vertex
247			// relations (do not saw the branch you are sitting on...),
248			// thus we store the corners to be updated in a temporary
249			// vector (a bit ugly, but not a big drama).
250		✗	MeshHalfedges::Halfedge H(H2);
251			do {
252			corners_to_update.push_back(H.corner);
253		✗	} while(MH.move_to_prev_around_vertex(H));
254		✗	for(index_t i=0; i<corners_to_update.size(); ++i) {
255		✗	M.facet_corners.set_vertex(
256			corners_to_update[i],new_v
257			);
258			}
259			}
260		✗	}
261
262		✗	bool flip_edge(Mesh& M, index_t t1, index_t e) {
263		✗	geo_assert(M.facets.are_simplices());
264			index_t c11 = e;
265			index_t t2 = M.facets.adjacent(t1,c11);
266		✗	if(t2 == NO_INDEX) {
267			return false;
268			}
269		✗	index_t c21 = M.facets.find_adjacent(t2,t1);
270		✗	geo_assert(c21 != NO_INDEX);
271
272		✗	index_t c12 = (c11+1)%3;
273			index_t t12 = M.facets.adjacent(t1,c12);
274		✗	index_t c12_back = (t12 == NO_INDEX) ? NO_INDEX
275		✗	: M.facets.find_adjacent(t12,t1);
276
277		✗	index_t c13 = (c12+1)%3;
278			index_t t13 = M.facets.adjacent(t1,c13);
279		✗	index_t c13_back = (t13 == NO_INDEX) ? NO_INDEX
280		✗	: M.facets.find_adjacent(t13,t1);
281
282		✗	index_t c22 = (c21+1)%3;
283			index_t t22 = M.facets.adjacent(t2,c22);
284		✗	index_t c22_back = (t22 == NO_INDEX) ? NO_INDEX
285		✗	: M.facets.find_adjacent(t22,t2);
286
287		✗	index_t c23 = (c22+1)%3;
288			index_t t23 = M.facets.adjacent(t2,c23);
289		✗	index_t c23_back = (t23 == NO_INDEX) ? NO_INDEX
290		✗	: M.facets.find_adjacent(t23,t2);
291
292			index_t v0 = M.facets.vertex(t1,c11);
293			index_t v1 = M.facets.vertex(t1,c12);
294			index_t v2 = M.facets.vertex(t1,c13);
295			index_t v3 = M.facets.vertex(t2,c23);
296
297			M.facets.set_vertex(t1,0,v2);
298			M.facets.set_vertex(t1,1,v3);
299			M.facets.set_vertex(t1,2,v1);
300
301			M.facets.set_vertex(t2,0,v3);
302			M.facets.set_vertex(t2,1,v2);
303			M.facets.set_vertex(t2,2,v0);
304
305			M.facets.set_adjacent(t1,0,t2);
306			M.facets.set_adjacent(t1,1,t23);
307			M.facets.set_adjacent(t1,2,t12);
308
309			M.facets.set_adjacent(t2,0,t1);
310			M.facets.set_adjacent(t2,1,t13);
311			M.facets.set_adjacent(t2,2,t22);
312
313		✗	if(t12 != NO_INDEX) {
314			M.facets.set_adjacent(t12, c12_back, t1);
315			}
316		✗	if(t23 != NO_INDEX) {
317			M.facets.set_adjacent(t23, c23_back, t1);
318			}
319
320		✗	if(t13 != NO_INDEX) {
321			M.facets.set_adjacent(t13, c13_back, t2);
322			}
323
324		✗	if(t22 != NO_INDEX) {
325			M.facets.set_adjacent(t22, c22_back, t2);
326			}
327
328			return true;
329			}
330			}
331