embeddedMap2.cpp 13.5 KB
Newer Older
1
2
3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2012, IGG Team, LSIIT, University of Strasbourg           *
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
*                                                                              *
* 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.           *
*                                                                              *
20
* Web site: http://cgogn.unistra.fr/                                           *
21
22
23
24
25
26
27
28
29
30
31
32
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include <vector>
#include <algorithm>

#include "Topology/map/embeddedMap2.h"

namespace CGoGN
{

33
34
35
36
37
38
39
40
Dart EmbeddedMap2::newFace(unsigned int nbEdges, bool withBoundary)
{
	Dart d = Map2::newFace(nbEdges, withBoundary);

	if(withBoundary)
	{
		if (isOrbitEmbedded<VERTEX>())
		{
41
/*
42
43
44
			Traversor2FV<EmbeddedMap2> t(*this, d);
			for(Dart it = t.begin(); it != t.end(); it = t.next())
				initOrbitEmbeddingNewCell<VERTEX>(it) ;
45
46
47
48
49
50
51
*/
			Dart e = d;
			do
			{
				initOrbitEmbeddingNewCell<VERTEX>(e) ;
				e = this->phi1(e);
			} while (d!=e);
52
53
54
55
		}

		if(isOrbitEmbedded<EDGE>())
		{
56
/*
57
58
59
			Traversor2FE<EmbeddedMap2> t(*this, d);
			for(Dart it = t.begin(); it != t.end(); it = t.next())
				initOrbitEmbeddingNewCell<EDGE>(it) ;
60
61
62
63
64
65
66
*/
			Dart e = d;
			do
			{
				initOrbitEmbeddingNewCell<EDGE>(e) ;
				e = this->phi1(e);
			} while (d!=e);
67
68
69
70
71
72
73
74
		}

		if(isOrbitEmbedded<FACE>())
		{
			initOrbitEmbeddingNewCell<FACE>(d) ;
			initOrbitEmbeddingNewCell<FACE>(phi2(d)) ;
		}
	}
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
	else
	{
		if (isOrbitEmbedded<VERTEX>())
		{
/*
			Traversor2FV<EmbeddedMap2> t(*this, d);
			for(Dart it = t.begin(); it != t.end(); it = t.next())
				initOrbitEmbeddingNewCell<VERTEX>(it) ;
*/
			Dart e = d;
			do
			{
				initDartEmbedding<VERTEX>(e,newCell<VERTEX>());
				e = this->phi1(e);
			} while (d!=e);
		}

		if(isOrbitEmbedded<FACE>())
			initOrbitEmbeddingNewCell<FACE>(d) ;

	}
96
97
98
	return d ;
}

99
100
101
102
103
104
105
void EmbeddedMap2::splitVertex(Dart d, Dart e)
{
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;

	Map2::splitVertex(d, e) ;

106
	if (isOrbitEmbedded<VERTEX>())
107
	{
108
109
		initDartEmbedding<VERTEX>(phi1(dd), getEmbedding<VERTEX>(d)) ;
		setOrbitEmbeddingOnNewCell<VERTEX>(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
110
		copyCell<VERTEX>(e, d) ;
111
112
	}

113
114
115
116
117
	if(isOrbitEmbedded<EDGE>())
	{
		initOrbitEmbeddingNewCell<EDGE>(phi1(dd)) ;
	}

118
	if(isOrbitEmbedded<FACE>())
119
	{
120
121
		initDartEmbedding<FACE>(phi1(dd), getEmbedding<FACE>(dd)) ;
		initDartEmbedding<FACE>(phi1(ee), getEmbedding<FACE>(ee)) ;
122
123
124
	}
}

125
Dart EmbeddedMap2::deleteVertex(Dart d)
126
{
127
128
	Dart f = Map2::deleteVertex(d) ;
	if(f != NIL)
129
	{
130
		if (isOrbitEmbedded<FACE>())
131
		{
132
			setOrbitEmbedding<FACE>(f, getEmbedding<FACE>(f)) ;
133
134
		}
	}
135
	return f ;
136
137
}

David Cazier's avatar
David Cazier committed
138
Dart EmbeddedMap2::cutEdge(Dart d)
139
{
David Cazier's avatar
David Cazier committed
140
	Dart nd = Map2::cutEdge(d) ;
141

142
143
144
145
146
	if(isOrbitEmbedded<VERTEX>())
	{
		initOrbitEmbeddingNewCell<VERTEX>(nd) ;
	}

147
	if (isOrbitEmbedded<EDGE>())
148
	{
149
150
		initDartEmbedding<EDGE>(phi2(d), getEmbedding<EDGE>(d)) ;
		setOrbitEmbeddingOnNewCell<EDGE>(nd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
151
		copyCell<EDGE>(nd, d) ;
152
	}
153

154
	if(isOrbitEmbedded<FACE>())
155
	{
156
		initDartEmbedding<FACE>(nd, getEmbedding<FACE>(d)) ;
157
		Dart e = phi2(nd) ;
158
		initDartEmbedding<FACE>(phi1(e), getEmbedding<FACE>(e)) ;
159
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
160

David Cazier's avatar
David Cazier committed
161
	return nd;
162
163
}

Pierre Kraemer's avatar
Pierre Kraemer committed
164
bool EmbeddedMap2::uncutEdge(Dart d)
165
{
Pierre Kraemer's avatar
Pierre Kraemer committed
166
	if(Map2::uncutEdge(d))
167
	{
168
		if(isOrbitEmbedded<EDGE>())
untereiner's avatar
untereiner committed
169
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
170
			copyDartEmbedding<EDGE>(phi2(d), d) ;
untereiner's avatar
untereiner committed
171
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
172
		return true ;
173
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
174
	return false ;
175
176
177
178
179
180
181
182
183
184
185
186
187
}

bool EmbeddedMap2::edgeCanCollapse(Dart d)
{
	if(isBoundaryVertex(d) || isBoundaryVertex(phi1(d)))
		return false ;

	unsigned int val_v1 = vertexDegree(d) ;
	unsigned int val_v2 = vertexDegree(phi1(d)) ;

	if(val_v1 + val_v2 < 8 || val_v1 + val_v2 > 14)
		return false ;

188
	if(faceDegree(d) == 3)
189
190
191
192
193
194
	{
		if(vertexDegree(phi_1(d)) < 4)
			return false ;
	}

	Dart dd = phi2(d) ;
195
	if(faceDegree(dd) == 3)
196
197
198
199
200
201
202
203
204
205
206
207
	{
		if(vertexDegree(phi_1(dd)) < 4)
			return false ;
	}

	// Check vertex sharing condition
	std::vector<unsigned int> vu1 ;
	vu1.reserve(32) ;
	Dart vit1 = alpha1(alpha1(d)) ;
	Dart end = phi1(dd) ;
	do
	{
208
		unsigned int ve = getEmbedding<VERTEX>(phi2(vit1)) ;
209
210
211
212
213
214
215
		vu1.push_back(ve) ;
		vit1 = alpha1(vit1) ;
	} while(vit1 != end) ;
	end = phi1(d) ;
	Dart vit2 = alpha1(alpha1(dd)) ;
	do
	{
216
		unsigned int ve = getEmbedding<VERTEX>(phi2(vit2)) ;
217
218
219
220
221
222
223
224
225
226
227
228
		std::vector<unsigned int>::iterator it = std::find(vu1.begin(), vu1.end(), ve) ;
		if(it != vu1.end())
			return false ;
		vit2 = alpha1(vit2) ;
	} while(vit2 != end) ;

	return true ;
}

Dart EmbeddedMap2::collapseEdge(Dart d, bool delDegenerateFaces)
{
	unsigned int vEmb = EMBNULL ;
229
	if (isOrbitEmbedded<VERTEX>())
230
	{
231
		vEmb = getEmbedding<VERTEX>(d) ;
232
233
234
235
	}

	Dart dV = Map2::collapseEdge(d, delDegenerateFaces);

236
	if (isOrbitEmbedded<VERTEX>())
237
	{
238
		setOrbitEmbedding<VERTEX>(dV, vEmb) ;
239
	}
240
	
241
242
243
244
245
246
247
248
249
	return dV ;
}

bool EmbeddedMap2::flipEdge(Dart d)
{
	if(Map2::flipEdge(d))
	{
		Dart e = phi2(d) ;

250
		if (isOrbitEmbedded<VERTEX>())
251
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
252
253
			copyDartEmbedding<VERTEX>(d, phi1(e)) ;
			copyDartEmbedding<VERTEX>(e, phi1(d)) ;
254
		}
255

256
		if (isOrbitEmbedded<FACE>())
257
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
258
259
			copyDartEmbedding<FACE>(phi_1(d), d) ;
			copyDartEmbedding<FACE>(phi_1(e), e) ;
260
		}
261

262
263
264
265
266
267
268
269
270
271
272
		return true ;
	}
	return false ;
}

bool EmbeddedMap2::flipBackEdge(Dart d)
{
	if(Map2::flipBackEdge(d))
	{
		Dart e = phi2(d) ;

273
		if (isOrbitEmbedded<VERTEX>())
274
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
275
276
			copyDartEmbedding<VERTEX>(d, phi1(e)) ;
			copyDartEmbedding<VERTEX>(e, phi1(d)) ;
277
		}
278

279
		if (isOrbitEmbedded<FACE>())
280
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
281
282
			copyDartEmbedding<FACE>(phi1(d), d) ;
			copyDartEmbedding<FACE>(phi1(e), e) ;
283
		}
284

285
286
287
288
289
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
290
291
292
293
294
295
void EmbeddedMap2::swapEdges(Dart d, Dart e)
{
	Dart d2 = phi2(d);
	Dart e2 = phi2(e);
	Map2::swapEdges(d,e);

296
	if(isOrbitEmbedded<VERTEX>())
untereiner's avatar
untereiner committed
297
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
298
299
300
301
		copyDartEmbedding<VERTEX>(d, phi2(phi_1(d)));
		copyDartEmbedding<VERTEX>(e, phi2(phi_1(e)));
		copyDartEmbedding<VERTEX>(d2, phi2(phi_1(d2)));
		copyDartEmbedding<VERTEX>(e2, phi2(phi_1(e2)));
untereiner's avatar
untereiner committed
302
303
	}

304
	if(isOrbitEmbedded<EDGE>())
untereiner's avatar
untereiner committed
305
306
307
308
	{

	}

309
	if(isOrbitEmbedded<VOLUME>())
310
		setOrbitEmbeddingOnNewCell<VOLUME>(d);
untereiner's avatar
untereiner committed
311
312
}

313
void EmbeddedMap2::sewFaces(Dart d, Dart e, bool withBoundary)
314
{
315
316
317
	if (!withBoundary)
	{
		Map2::sewFaces(d, e, false) ;
318
319
320
321
322
323
324
325
326
327
328
329
330

		if(isOrbitEmbedded<EDGE>())
		{
/*
			Traversor2FE<EmbeddedMap2> t(*this, d);
			for(Dart it = t.begin(); it != t.end(); it = t.next())
				initOrbitEmbeddingNewCell<EDGE>(it) ;
*/
			unsigned int emb = newCell<EDGE>();
			initDartEmbedding<EDGE>(d,emb);
			initDartEmbedding<EDGE>(e,emb);
		}

331
332
		return ;
	}
333

untereiner's avatar
untereiner committed
334
	Map2::sewFaces(d, e, withBoundary) ;
335

336
	if (isOrbitEmbedded<VERTEX>())
337
	{
338
339
		setOrbitEmbedding<VERTEX>(d, getEmbedding<VERTEX>(d)) ;
		setOrbitEmbedding<VERTEX>(e, getEmbedding<VERTEX>(phi1(d))) ;
340
341
	}

342
	if (isOrbitEmbedded<EDGE>())
343
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
344
		copyDartEmbedding<EDGE>(e, d) ;
345
346
347
	}
}

348
void EmbeddedMap2::unsewFaces(Dart d, bool withBoundary)
349
{
350
351
352
353
354
355
	if (!withBoundary)
	{
		Map2::unsewFaces(d, false) ;
		return ;
	}

356
357
358
	Dart e = phi2(d) ;
	Map2::unsewFaces(d) ;

359
	if (isOrbitEmbedded<VERTEX>())
360
	{
361
362
		Dart ee = phi1(e) ;
		if(!sameVertex(d, ee))
363
		{
364
			setOrbitEmbeddingOnNewCell<VERTEX>(ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
365
			copyCell<VERTEX>(ee, d);
366
367
		}

368
369
		Dart dd = phi1(d) ;
		if(!sameVertex(e, dd))
370
		{
371
			setOrbitEmbeddingOnNewCell<VERTEX>(dd);
Pierre Kraemer's avatar
Pierre Kraemer committed
372
			copyCell<VERTEX>(dd, e);
373
374
		}
	}
375

376
	if (isOrbitEmbedded<EDGE>())
377
	{
378
		setOrbitEmbeddingOnNewCell<EDGE>(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
379
		copyCell<EDGE>(e, d);
380
381
382
383
384
385
	}
}

bool EmbeddedMap2::collapseDegeneratedFace(Dart d)
{
	Dart e = phi2(d) ;
386
387
388
	bool updateEdgeEmb = false ;
	if(phi1(d) != d)
		updateEdgeEmb = true ;
389

390
	if(Map2::collapseDegeneratedFace(d))
391
	{
392
		if (isOrbitEmbedded<EDGE>() && updateEdgeEmb)
393
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
394
			copyDartEmbedding<EDGE>(phi2(e), e) ;
395
396
397
398
399
400
401
402
403
404
		}
		return true ;
	}
	return false ;
}

void EmbeddedMap2::splitFace(Dart d, Dart e)
{
	Map2::splitFace(d, e) ;

405
	if (isOrbitEmbedded<VERTEX>())
406
	{
407
408
		initDartEmbedding<VERTEX>(phi_1(e), getEmbedding<VERTEX>(d)) ;
		initDartEmbedding<VERTEX>(phi_1(d), getEmbedding<VERTEX>(e)) ;
409
	}
410
411
412
413
414
415

	if(isOrbitEmbedded<EDGE>())
	{
		initOrbitEmbeddingNewCell<EDGE>(phi_1(d)) ;
	}

416
	if (isOrbitEmbedded<FACE>())
417
	{
418
419
		initDartEmbedding<FACE>(phi_1(d), getEmbedding<FACE>(d)) ;
		setOrbitEmbeddingOnNewCell<FACE>(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
420
		copyCell<FACE>(e, d) ;
421
422
423
424
425
426
427
428
429
	}
}

bool EmbeddedMap2::mergeFaces(Dart d)
{
	Dart dNext = phi1(d) ;

	if(Map2::mergeFaces(d))
	{
430
		if (isOrbitEmbedded<FACE>())
431
		{
432
			setOrbitEmbedding<FACE>(dNext, getEmbedding<FACE>(dNext)) ;
433
434
435
436
437
438
439
440
441
442
		}
		return true ;
	}
	return false ;
}

bool EmbeddedMap2::mergeVolumes(Dart d, Dart e)
{
	std::vector<Dart> darts ;
	std::vector<unsigned int> vEmb ;
untereiner's avatar
untereiner committed
443
	vEmb.reserve(32) ;
444
	std::vector<unsigned int> eEmb ;
untereiner's avatar
untereiner committed
445
	eEmb.reserve(32) ;
446
447
448
449
450
	Dart fit = d ;
	do
	{
		darts.push_back(phi2(fit)) ;

451
		if (isOrbitEmbedded<VERTEX>())
452
		{
453
			vEmb.push_back(getEmbedding<VERTEX>(phi2(fit))) ;
454
455
		}

456
		if (isOrbitEmbedded<EDGE>())
457
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
458
			eEmb.push_back(getEmbedding<EDGE>(fit)) ;
459
		}
460
		
461
462
463
464
465
466
467
		fit = phi1(fit) ;
	} while (fit != d) ;

	if(Map2::mergeVolumes(d, e))
	{
		for(unsigned int i = 0; i < darts.size(); ++i)
		{
468
			if (isOrbitEmbedded<VERTEX>())
469
			{
470
				setOrbitEmbedding<VERTEX>(darts[i], vEmb[i]) ;
471
472
			}

473
			if (isOrbitEmbedded<EDGE>())
474
			{
475
				setOrbitEmbedding<EDGE>(darts[i], eEmb[i]) ;
476
477
478
479
480
481
482
			}
		}
		return true ;
	}
	return false ;
}

483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
void EmbeddedMap2::splitSurface(std::vector<Dart>& vd, bool firstSideClosed, bool secondSideClosed)
{
	std::vector<Dart> darts ;
	darts.reserve(vd.size());

	// save the edge neighbors darts
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
		darts.push_back(phi2(*it));
	}

	assert(darts.size() == vd.size());

	Map2::splitSurface(vd, firstSideClosed, secondSideClosed);

	// follow the edge path a second time to embed the vertex, edge and volume orbits
	for(unsigned int i = 0; i < vd.size(); ++i)
	{
		Dart dit = vd[i];
		Dart dit2 = darts[i];

		// embed the vertex embedded from the origin volume to the new darts
505
		if(isOrbitEmbedded<VERTEX>())
506
		{
507
508
			initDartEmbedding<VERTEX>(phi2(dit), getEmbedding<VERTEX>(phi1(dit)));
			initDartEmbedding<VERTEX>(phi2(dit2), getEmbedding<VERTEX>(phi1(dit2)));
509
510
511
		}

		// embed the edge embedded from the origin volume to the new darts
512
		if(isOrbitEmbedded<EDGE>())
513
		{
514
515
516
			initDartEmbedding<EDGE>(phi2(dit), getEmbedding<EDGE>(dit));
			setOrbitEmbeddingOnNewCell<EDGE>(phi2(dit2));
			copyCell<EDGE>(dit2, dit);
517
518
519
		}

		// embed the volume embedded from the origin volume to the new darts
520
		if(isOrbitEmbedded<VOLUME>())
521
		{
522
523
			initDartEmbedding<VOLUME>(phi2(dit), getEmbedding<VOLUME>(dit));
			initDartEmbedding<VOLUME>(phi2(dit2), getEmbedding<VOLUME>(dit2));
524
525
526
527
		}
	}
}

528
unsigned int EmbeddedMap2::closeHole(Dart d, bool forboundary)
529
{
530
	unsigned int nbE = Map2::closeHole(d, forboundary) ;
531
532
533
534
	Dart dd = phi2(d) ;
	Dart f = dd ;
	do
	{
535
		if (isOrbitEmbedded<VERTEX>())
536
		{
537
			initDartEmbedding<VERTEX>(f, getEmbedding<VERTEX>(phi1(phi2(f)))) ;
538
		}
539

540
		if (isOrbitEmbedded<EDGE>())
541
		{
542
			initDartEmbedding<EDGE>(f, getEmbedding<EDGE>(phi2(f))) ;
543
		}
544

545
546
		f = phi1(f) ;
	} while(dd != f) ;
547
548
549
550
551
552

	if(isOrbitEmbedded<FACE>())
	{
		initOrbitEmbeddingNewCell<FACE>(dd) ;
	}

553
554
555
556
557
558
559
560
561
562
563
564
	return nbE ;
}

bool EmbeddedMap2::check()
{
	bool topo = Map2::check() ;
	if (!topo)
		return false ;

	CGoGNout << "Check: embedding begin" << CGoGNendl ;
	for(Dart d = begin(); d != end(); next(d))
	{
565
		if (isOrbitEmbedded<VERTEX>())
566
		{
567
			if (getEmbedding<VERTEX>(d) != getEmbedding<VERTEX>(alpha1(d)))
568
569
570
571
572
573
			{
				CGoGNout << "Check: different embeddings on vertex" << CGoGNendl ;
				return false ;
			}
		}

574
		if (isOrbitEmbedded<EDGE>())
575
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
576
			if (getEmbedding<EDGE>(d) != getEmbedding<EDGE>(phi2(d)))
577
578
579
580
581
582
			{
				CGoGNout << "Check: different embeddings on edge" << CGoGNendl ;
				return false ;
			}
		}

583
584
585
586
587
588
589
590
//		if (isOrbitEmbedded(ORIENTED_FACE))
//		{
//			if (getEmbedding(ORIENTED_FACE, d) != getEmbedding(ORIENTED_FACE, phi1(d)))
//		{
//				CGoGNout << "Check: different embeddings on oriented face" << CGoGNendl ;
//				return false ;
//			}
//		}
untereiner's avatar
untereiner committed
591

592
		if (isOrbitEmbedded<FACE>())
593
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
594
			if (getEmbedding<FACE>(d) != getEmbedding<FACE>(phi1(d)))
595
			{
596
597
598
599
600
				CGoGNout << "Check: different embeddings on face" << CGoGNendl ;
				return false ;
			}
		}
	}
601

602
	CGoGNout << "Check: embedding ok" << CGoGNendl ;
603

Pierre Kraemer's avatar
Pierre Kraemer committed
604
    std::cout << "nb vertex orbits : " << getNbOrbits<VERTEX>() << std::endl ;
605
606
    std::cout << "nb vertex cells : " << m_attribs[VERTEX].size() << std::endl ;

Pierre Kraemer's avatar
Pierre Kraemer committed
607
    std::cout << "nb edge orbits : " << getNbOrbits<EDGE>() << std::endl ;
608
609
    std::cout << "nb edge cells : " << m_attribs[EDGE].size() << std::endl ;

Pierre Kraemer's avatar
Pierre Kraemer committed
610
    std::cout << "nb face orbits : " << getNbOrbits<FACE>() << std::endl ;
611
612
    std::cout << "nb face cells : " << m_attribs[FACE].size() << std::endl ;

613
614
615
616
	return true ;
}

} // namespace CGoGN