embeddedMap3.cpp 11.6 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
* Copyright (C) 2009-2011, IGG Team, LSIIT, University of Strasbourg           *
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
* Web site: http://cgogn.u-strasbg.fr/                                         *
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/embeddedMap3.h"

namespace CGoGN
{

Pierre Kraemer's avatar
Pierre Kraemer committed
30
Dart EmbeddedMap3::deleteVertex(Dart d)
31
{
untereiner's avatar
untereiner committed
32
33
34
35
36
37
38
39
40
	Dart v = Map3::deleteVertex(d) ;
	if(v != NIL)
	{
		if (isOrbitEmbedded(VOLUME))
		{
			embedOrbit(VOLUME, v, getEmbedding(VOLUME, v)) ;
		}
	}
	return v ;
41
42
}

David Cazier's avatar
David Cazier committed
43
Dart EmbeddedMap3::cutEdge(Dart d)
44
{
David Cazier's avatar
David Cazier committed
45
	Dart nd = Map3::cutEdge(d);
46
47
48

	if(isOrbitEmbedded(EDGE))
	{
untereiner's avatar
untereiner committed
49
50
51
		// embed the new darts created in the cut edge
		embedOrbit(EDGE, d, getEmbedding(EDGE, d)) ;
		// embed a new cell for the new edge and copy the attributes' line (c) Lionel
untereiner's avatar
untereiner committed
52
53
		embedNewCell(EDGE, nd) ;
		copyCell(EDGE, nd, d) ;
54
55
	}

untereiner's avatar
untereiner committed
56
	if(isOrbitEmbedded(ORIENTED_FACE))
57
58
59
60
	{
		Dart f = d;
		do
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
61
62
63
			Dart f1 = phi1(f) ;
			copyDartEmbedding(ORIENTED_FACE, f1, f);
			Dart e = phi3(f1);
untereiner's avatar
untereiner committed
64
65
66
67
68
69
70
71
72
73
74
75
76
			copyDartEmbedding(ORIENTED_FACE, phi1(e), e);
			f = alpha2(f);
		} while(f != d);
	}

	if(isOrbitEmbedded(FACE))
	{
		Dart f = d;
		do
		{
			unsigned int fEmb = getEmbedding(FACE, f) ;
			setDartEmbedding(FACE, phi1(f), fEmb);
			setDartEmbedding(FACE, phi3(f), fEmb);
77
78
79
80
81
82
83
84
85
			f = alpha2(f);
		} while(f != d);
	}

	if(isOrbitEmbedded(VOLUME))
	{
		Dart f = d;
		do
		{
untereiner's avatar
untereiner committed
86
87
88
			unsigned int vEmb = getEmbedding(VOLUME, f) ;
			setDartEmbedding(VOLUME, phi1(f), vEmb);
			setDartEmbedding(VOLUME, phi2(f), vEmb);
89
90
91
			f = alpha2(f);
		} while(f != d);
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
92
93

	return nd ;
94
95
}

96
bool EmbeddedMap3::uncutEdge(Dart d)
97
{
98
	if(Map3::uncutEdge(d))
untereiner's avatar
untereiner committed
99
	{
100
101
102
		//embed all darts from the old two edges to one of the two edge embedding
		if(isOrbitEmbedded(EDGE))
		{
untereiner's avatar
untereiner committed
103
			embedOrbit(EDGE, d, getEmbedding(EDGE, d)) ;
104
105
		}
		return true ;
untereiner's avatar
untereiner committed
106
	}
107
	return false ;
108
109
}

untereiner's avatar
untereiner committed
110
111
112
113
114
115
116
117
118
119
120
121
122
Dart EmbeddedMap3::deleteEdge(Dart d)
{
	Dart v = Map3::deleteVertex(d) ;
	if(v != NIL)
	{
		if(isOrbitEmbedded(VOLUME))
		{
			embedOrbit(VOLUME, v, getEmbedding(VOLUME, v)) ;
		}
	}
	return v;
}

123
124
125
126
127
128
129
130
131
bool EmbeddedMap3::edgeCanCollapse(Dart d)
{
	//Criteres sur le bord
	if(isBoundaryEdge(d))
	{
		//fusion de deux bord

		//deconnection du bord
	}
132
133

	return false;
134
135
}

untereiner's avatar
untereiner committed
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
Dart EmbeddedMap3::collapseEdge(Dart d, bool delDegenerateVolumes)
{
	unsigned int vEmb = getEmbedding(VERTEX, d) ;

	Dart resV = Map3::collapseEdge(d, delDegenerateVolumes);

	if(resV != NIL)
	{
		if(isOrbitEmbedded(VERTEX))
		{
			embedOrbit(VERTEX,resV,vEmb);
		}
	}

	return resV;
}

153
154
void EmbeddedMap3::splitFace(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
155
156
157
158
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));

	Map3::splitFace(d, e);
159
160
161

	if(isOrbitEmbedded(VERTEX))
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
162
163
164
165
166
167
		unsigned int vEmb1 = getEmbedding(VERTEX, d) ;
		unsigned int vEmb2 = getEmbedding(VERTEX, e) ;
		setDartEmbedding(VERTEX, phi_1(e), vEmb1);
		setDartEmbedding(VERTEX, phi_1(ee), vEmb1);
		setDartEmbedding(VERTEX, phi_1(d), vEmb2);
		setDartEmbedding(VERTEX, phi_1(dd), vEmb2);
untereiner's avatar
untereiner committed
168
	}
169

untereiner's avatar
untereiner committed
170
171
172
173
174
	if(isOrbitEmbedded(ORIENTED_FACE))
	{
		copyDartEmbedding(ORIENTED_FACE, phi_1(d), d) ;
		embedNewCell(ORIENTED_FACE, e) ;
		copyCell(ORIENTED_FACE, e, d) ;
175

untereiner's avatar
untereiner committed
176
177
178
		copyDartEmbedding(ORIENTED_FACE, phi_1(dd), dd) ;
		embedNewCell(ORIENTED_FACE, ee) ;
		copyCell(ORIENTED_FACE, ee, dd) ;
179
180
181
182
	}

	if(isOrbitEmbedded(FACE))
	{
untereiner's avatar
untereiner committed
183
184
		unsigned int fEmb = getEmbedding(FACE, d) ;
		setDartEmbedding(FACE, phi_1(d), fEmb) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
185
		setDartEmbedding(FACE, phi_1(ee), fEmb) ;
untereiner's avatar
untereiner committed
186
187
		embedNewCell(FACE, e);
		copyCell(FACE, e, d);
188
189
190
191
	}

	if(isOrbitEmbedded(VOLUME))
	{
untereiner's avatar
untereiner committed
192
193
194
		unsigned int vEmb1 = getEmbedding(VOLUME, d) ;
		setDartEmbedding(VOLUME, phi_1(d),  vEmb1);
		setDartEmbedding(VOLUME, phi_1(e),  vEmb1);
195

untereiner's avatar
untereiner committed
196
197
198
		unsigned int vEmb2 = getEmbedding(VOLUME, dd) ;
		setDartEmbedding(VOLUME, phi_1(dd),  vEmb2);
		setDartEmbedding(VOLUME, phi_1(ee),  vEmb2);
199
200
201
	}
}

untereiner's avatar
untereiner committed
202
void EmbeddedMap3::sewVolumes(Dart d, Dart e, bool withBoundary)
203
{
204
205
206
207
208
209
	if (!withBoundary)
	{
		Map3::sewVolumes(d, e, false) ;
		return ;
	}

untereiner's avatar
untereiner committed
210
	Map3::sewVolumes(d, e, withBoundary);
211

Pierre Kraemer's avatar
Pierre Kraemer committed
212
213
	// embed the vertex orbits from the oriented face with dart e
	// with vertex orbits value from oriented face with dart d
214
215
	if (isOrbitEmbedded(VERTEX))
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
216
		Dart it = d ;
untereiner's avatar
untereiner committed
217
218
		do
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
219
220
221
			embedOrbit(VERTEX, it, getEmbedding(VERTEX, it)) ;
			it = phi1(it) ;
		} while(it != d) ;
222
223
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
224
225
	// embed the new edge orbit with the old edge orbit value
	// for all the face
226
227
	if (isOrbitEmbedded(EDGE))
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
228
		Dart it = d ;
untereiner's avatar
untereiner committed
229
230
		do
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
231
232
233
			embedOrbit(EDGE, it, getEmbedding(EDGE, it)) ;
			it = phi1(it) ;
		} while(it != d) ;
234
235
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
236
	// embed the face orbit from the volume sewn
237
	if (isOrbitEmbedded(FACE))
238
	{
untereiner's avatar
untereiner committed
239
		embedOrbit(FACE, e, getEmbedding(FACE, d)) ;
240
	}
241
242
243
244
}

void EmbeddedMap3::unsewVolumes(Dart d)
{
245
246
	Dart dd = alpha1(d);

untereiner's avatar
untereiner committed
247
248
249
250
	unsigned int fEmb = EMBNULL ;
	if(isOrbitEmbedded(FACE))
		fEmb = getEmbedding(FACE, d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
251
252
	Map3::unsewVolumes(d);

untereiner's avatar
untereiner committed
253
254
255
256
257
	Dart dit = d;
	do
	{
		// embed the unsewn vertex orbit with the vertex embedding if it is deconnected
		if(isOrbitEmbedded(VERTEX))
Thomas's avatar
Thomas committed
258
		{
untereiner's avatar
untereiner committed
259
			if(!sameVertex(dit, dd))
Thomas's avatar
Thomas committed
260
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
261
				embedOrbit(VERTEX, dit, getEmbedding(VERTEX, dit)) ;
untereiner's avatar
untereiner committed
262
263
				embedNewCell(VERTEX, dd);
				copyCell(VERTEX, dd, dit);
264
265
266
			}
			else
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
267
				embedOrbit(VERTEX, dit, getEmbedding(VERTEX, dit)) ;
Thomas's avatar
Thomas committed
268
			}
untereiner's avatar
untereiner committed
269
		}
Thomas's avatar
Thomas committed
270

untereiner's avatar
untereiner committed
271
		dd = phi_1(dd);
Thomas's avatar
Thomas committed
272

untereiner's avatar
untereiner committed
273
274
275
276
		// embed the unsewn edge with the edge embedding if it is deconnected
		if(isOrbitEmbedded(EDGE))
		{
			if(!sameEdge(dit, dd))
Thomas's avatar
Thomas committed
277
			{
untereiner's avatar
untereiner committed
278
279
				embedNewCell(EDGE, dd);
				copyCell(EDGE, dd, dit);
280
281
282
283
284
285
286
				copyDartEmbedding(EDGE, phi3(dit), dit) ;
			}
			else
			{
				unsigned int eEmb = getEmbedding(EDGE, dit) ;
				setDartEmbedding(EDGE, phi3(dit), eEmb) ;
				setDartEmbedding(EDGE, alpha_2(dit), eEmb) ;
Thomas's avatar
Thomas committed
287
			}
untereiner's avatar
untereiner committed
288
		}
Thomas's avatar
Thomas committed
289

untereiner's avatar
untereiner committed
290
		if(isOrbitEmbedded(FACE))
Thomas's avatar
Thomas committed
291
		{
untereiner's avatar
untereiner committed
292
			setDartEmbedding(FACE, phi3(dit), fEmb) ;
Thomas's avatar
Thomas committed
293
		}
untereiner's avatar
untereiner committed
294
295
296
297
298
299
300
301
302

		dit = phi1(dit);
	} while(dit != d);

	// embed the unsewn face with the face embedding
	if (isOrbitEmbedded(FACE))
	{
		embedNewCell(FACE, dd);
		copyCell(FACE, dd, d);
Thomas's avatar
Thomas committed
303
	}
304
305
306
307
308
309
310
311
312
313
}

bool EmbeddedMap3::mergeVolumes(Dart d)
{
	Dart d2 = phi2(d);

	if(Map3::mergeVolumes(d))
	{
		if (isOrbitEmbedded(VOLUME))
		{
untereiner's avatar
untereiner committed
314
			embedOrbit(VOLUME, d2, getEmbedding(VOLUME, d2)) ;
315
316
317
318
319
320
		}
		return true;
	}
	return false;
}

untereiner's avatar
untereiner committed
321
322
323
324
void EmbeddedMap3::splitVolume(std::vector<Dart>& vd)
{
	Map3::splitVolume(vd);

untereiner's avatar
untereiner committed
325
	// follow the edge path a second time to embed the vertex, edge and volume orbits
untereiner's avatar
untereiner committed
326
327
328
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
		Dart dit = *it;
untereiner's avatar
untereiner committed
329
		Dart dit23 = alpha2(dit);
untereiner's avatar
untereiner committed
330

untereiner's avatar
untereiner committed
331
		// embed the vertex embedded from the origin volume to the new darts
untereiner's avatar
untereiner committed
332
333
		if(isOrbitEmbedded(VERTEX))
		{
untereiner's avatar
untereiner committed
334
335
			copyDartEmbedding(VERTEX, dit23, dit);
			copyDartEmbedding(VERTEX, phi2(dit), phi1(dit));
untereiner's avatar
untereiner committed
336
337
		}

untereiner's avatar
untereiner committed
338
		// embed the edge embedded from the origin volume to the new darts
untereiner's avatar
untereiner committed
339
340
		if(isOrbitEmbedded(EDGE))
		{
untereiner's avatar
untereiner committed
341
342
343
			unsigned int eEmb = getEmbedding(EDGE, dit) ;
			setDartEmbedding(EDGE, dit23, eEmb);
			setDartEmbedding(EDGE, phi2(dit), eEmb);
untereiner's avatar
untereiner committed
344
345
		}

untereiner's avatar
untereiner committed
346
		// embed the volume embedded from the origin volume to the new darts
untereiner's avatar
untereiner committed
347
348
		if(isOrbitEmbedded(VOLUME))
		{
untereiner's avatar
untereiner committed
349
			copyDartEmbedding(VOLUME, phi2(dit), dit);
untereiner's avatar
untereiner committed
350
351
		}
	}
untereiner's avatar
untereiner committed
352
353
354

	if(isOrbitEmbedded(VOLUME))
	{
355
		Dart v = vd.front() ;
untereiner's avatar
untereiner committed
356
357
358
359
360
361
362
363
364
365
366
367
368
369
		Dart v23 = alpha2(v) ;
		embedNewCell(VOLUME, v23) ;
		copyCell(VOLUME, v23, v) ;
	}
}

unsigned int EmbeddedMap3::closeHole(Dart d, bool forboundary)
{
	unsigned int nbF = Map3::closeHole(d, forboundary) ;

	DartMarkerStore mark(*this);	// Lock a marker

	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
370
371
	visitedFaces.push_back(phi3(d));// Start with the face of d
	mark.markOrbit(ORIENTED_FACE, phi3(d)) ;
untereiner's avatar
untereiner committed
372
373

	// For every face added to the list
374
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
untereiner's avatar
untereiner committed
375
	{
376
377
		Dart it = visitedFaces[i] ;
		Dart f = it ;
378
		do
untereiner's avatar
untereiner committed
379
		{
380
			if(isOrbitEmbedded(VERTEX))
untereiner's avatar
untereiner committed
381
			{
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
				copyDartEmbedding(VERTEX, f, alpha1(f)) ;
			}
			if(isOrbitEmbedded(EDGE))
			{
				copyDartEmbedding(EDGE, f, phi3(f)) ;
			}
			if(isOrbitEmbedded(FACE))
			{
				copyDartEmbedding(FACE, f, phi3(f)) ;
			}

			Dart adj = phi2(f);	// Get adjacent face
			if (!mark.isMarked(adj))
			{
				visitedFaces.push_back(adj);	// Add it
				mark.markOrbit(ORIENTED_FACE, adj) ;
			}

			f = phi1(f) ;
401
		} while(f != it) ;
untereiner's avatar
untereiner committed
402
403
404
	}

	return nbF ;
untereiner's avatar
untereiner committed
405
406
}

407
bool EmbeddedMap3::check()
408
{
409
410
411
	bool topo = Map3::check() ;
	if (!topo)
		return false ;
412

413
	std::cout << "Check: embedding begin" << std::endl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
414

415
	for(Dart d = begin(); d != end(); next(d))
416
	{
417
		if(isOrbitEmbedded(VERTEX))
418
		{
untereiner's avatar
untereiner committed
419
420
			if( getEmbedding(VERTEX, d) != getEmbedding(VERTEX, alpha1(d)) ||
					getEmbedding(VERTEX, d) != getEmbedding(VERTEX, alpha2(d)) )
421
			{
untereiner's avatar
untereiner committed
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
				std::cout << "Embedding Check : different embeddings on vertex" << std::endl ;
				return false ;
			}
		}

		if(isOrbitEmbedded(EDGE))
		{
			if( getEmbedding(EDGE, d) != getEmbedding(EDGE, phi2(d)) ||
					getEmbedding(EDGE, d) != getEmbedding(EDGE, phi3(d)) )
			{
				std::cout << "Embedding Check : different embeddings on edge" << std::endl ;
				return false ;
			}
		}

		if (isOrbitEmbedded(ORIENTED_FACE))
		{
			if (getEmbedding(ORIENTED_FACE, d) != getEmbedding(ORIENTED_FACE, phi1(d)))
			{
				CGoGNout << "Check: different embeddings on oriented face" << CGoGNendl ;
				return false ;
443
			}
444
		}
445

untereiner's avatar
untereiner committed
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
		if (isOrbitEmbedded(FACE))
		{
			if( getEmbedding(FACE, d) != getEmbedding(FACE, phi1(d)) ||
					getEmbedding(FACE, d) != getEmbedding(FACE, phi3(d)) )
			{
				CGoGNout << "Check: different embeddings on face" << CGoGNendl ;
				return false ;
			}
		}

		if (isOrbitEmbedded(VOLUME))
		{
			if( getEmbedding(VOLUME, d) != getEmbedding(VOLUME, phi1(d)) ||
					getEmbedding(VOLUME, d) != getEmbedding(VOLUME, phi2(d)) )
			{
				CGoGNout << "Check: different embeddings on volume" << CGoGNendl ;
				return false ;
			}
		}
465
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
466

467
	std::cout << "Check: embedding ok" << std::endl ;
468
469
470
471
472
473
474
475
476
477
478
479
480

    std::cout << "nb vertex orbits : " << getNbOrbits(VERTEX) << std::endl ;
    std::cout << "nb vertex cells : " << m_attribs[VERTEX].size() << std::endl ;

    std::cout << "nb edge orbits : " << getNbOrbits(EDGE) << std::endl ;
    std::cout << "nb edge cells : " << m_attribs[EDGE].size() << std::endl ;

    std::cout << "nb face orbits : " << getNbOrbits(FACE) << std::endl ;
    std::cout << "nb face cells : " << m_attribs[FACE].size() << std::endl ;

    std::cout << "nb volume orbits : " << getNbOrbits(VOLUME) << std::endl ;
    std::cout << "nb volume cells : " << m_attribs[VOLUME].size() << std::endl ;

481
	return true ;
482
483
484
}

} // namespace CGoGN