gmap2.cpp 20 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1
2
3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2011, IGG Team, LSIIT, University of Strasbourg           *
Pierre Kraemer's avatar
Pierre Kraemer committed
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.u-strasbg.fr/                                         *
Pierre Kraemer's avatar
Pierre Kraemer committed
21
22
23
24
25
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/gmap/gmap2.h"
26
#include "Topology/generic/traversorCell.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
27
28
29
30

namespace CGoGN
{

31
32
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-G-map
Pierre Kraemer's avatar
Pierre Kraemer committed
33
34
 *************************************************************************/

35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
Dart GMap2::newFace(unsigned int nbEdges, bool withBoundary)
{
	Dart d = GMap1::newFace(nbEdges);
	if (withBoundary)
	{
		Dart e = GMap1::newFace(nbEdges);

		Dart it = d;
		do
		{
			beta2sew(it, beta0(e));
			beta2sew(beta0(it), e);
			it = phi1(it);
			e = phi_1(e);
		} while (it != d);
	}
	return d;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
54
55
void GMap2::deleteFace(Dart d)
{
56
57
	assert(!isBoundaryMarked(d)) ;
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
58
59
	do
	{
60
61
62
63
64
65
66
67
68
		if(!isBoundaryEdge(it))
			unsewFaces(it) ;
		it = phi1(it) ;
	} while(it != d) ;
	Dart dd = phi2(d) ;
	GMap1::deleteFace(d) ;
	GMap1::deleteFace(dd) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
void GMap2::deleteCC(Dart d)
{
	DartMarkerStore mark(*this);

	std::vector<Dart> visited;
	visited.reserve(1024) ;
	visited.push_back(d);
	mark.mark(d) ;

	for (std::vector<Dart>::iterator it = visited.begin(); it != visited.end(); ++it)
	{
		Dart d0 = beta0(*it) ;
		if(!mark.isMarked(d0))
		{
			visited.push_back(d0) ;
			mark.mark(d0);
		}
		Dart d1 = beta1(*it) ;
		if(!mark.isMarked(d1))
		{
			visited.push_back(d1) ;
			mark.mark(d1);
		}
		Dart d2 = beta2(*it) ;
		if(!mark.isMarked(d2))
		{
			visited.push_back(d2) ;
			mark.mark(d2);
		}
	}

	for(std::vector<Dart>::iterator it = visited.begin(); it != visited.end(); ++it)
		deleteDart(*it) ;
}

104
105
void GMap2::fillHole(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
106
107
108
109
110
	assert(isBoundaryEdge(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi2(dd) ;
	boundaryUnmarkOrbit(FACE, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
111
112
113
114
115
116
117
118
}

/*! @name Topological Operators
 *  Topological operations on 2-G-maps
 *************************************************************************/

void GMap2::splitVertex(Dart d, Dart e)
{
119
	assert(sameVertex(d, e));
Pierre Kraemer's avatar
Pierre Kraemer committed
120
121
122
123
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
	GMap1::cutEdge(dd);			// Cut the edge of dd (make a new edge)
	GMap1::cutEdge(ee);			// Cut the edge of ee (make a new edge)
124
125
	beta2sew(phi1(dd), beta0(phi1(ee)));	// Sew the two faces along the new edge
	beta2sew(phi1(ee), beta0(phi1(dd)));
Pierre Kraemer's avatar
Pierre Kraemer committed
126
127
}

128
Dart GMap2::deleteVertex(Dart d)
129
130
{
	if(isBoundaryVertex(d))
131
		return NIL ;
132

133
	Dart res = NIL ;
134
135
136
	Dart vit = d ;
	do
	{
137
138
139
140
141
142
143
144
145
146
147
148
		if(res == NIL && phi1(phi1(d)) != d)
			res = phi1(d) ;

		Dart d0 = beta0(vit) ;
		Dart d02 = beta2(d0) ;
		Dart d01 = beta1(d0) ;
		Dart d021 = beta1(d02) ;
		beta1unsew(d0) ;
		beta1unsew(d02) ;
		beta1sew(d0, d02) ;
		beta1sew(d01, d021) ;

149
150
		vit = alpha1(vit) ;
	} while(vit != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
151
	GMap1::deleteFace(d) ;
152
	return res ;
153
154
}

Pierre Kraemer's avatar
Pierre Kraemer committed
155
156
void GMap2::cutEdge(Dart d)
{
157
158
159
160
161
162
163
164
165
166
167
168
	Dart e = phi2(d) ;
	beta2unsew(d) ;
	beta2unsew(e) ;
	GMap1::cutEdge(d) ;
	GMap1::cutEdge(e) ;

	Dart nd = phi1(d) ;
	Dart ne = phi1(e) ;
	beta2sew(d, beta0(ne)) ;
	beta2sew(beta0(d), ne) ;
	beta2sew(e, beta0(nd)) ;
	beta2sew(beta0(e), nd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
169
170
}

171
bool GMap2::uncutEdge(Dart d)
172
{
173
	if(vertexDegree(phi1(d)) == 2)
174
	{
175
		Dart ne = phi2(d) ;
176
177
		Dart nd = phi1(d) ;
		Dart e = phi_1(ne) ;
178
179
180
181
		beta2unsew(d) ;
		beta2unsew(ne) ;
		beta2unsew(e) ;
		beta2unsew(nd) ;
182
183
		GMap1::collapseEdge(nd) ;
		GMap1::collapseEdge(ne) ;
184
185
186
		beta2sew(d, beta0(e)) ;
		beta2sew(e, beta0(d)) ;
		return true ;
187
	}
188
	return false ;
189
190
191
}

Dart GMap2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
192
{
193
	Dart resV = NIL ;
194
195

	Dart e = phi2(d);
196
197
	beta2unsew(d);	// Unlink the opposite edges
	beta2unsew(e);
198

199
200
	Dart f = phi1(e) ;
	Dart h = alpha1(e);
201

202
203
	if (h != e)
		resV = h;
204

205
206
207
208
209
210
211
	if (f != e && delDegenerateFaces)
	{
		GMap1::collapseEdge(e) ;		// Collapse edge e
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
	}
	else
		GMap1::collapseEdge(e) ;	// Just collapse edge e
212

213
	f = phi1(d) ;
214
	if(resV == NIL)
215
	{
216
217
218
		h = alpha1(d);
		if (h != d)
			resV = h;
219
220
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
221
222
	if (f != d && delDegenerateFaces)
	{
223
224
		GMap1::collapseEdge(d) ;		// Collapse edge d
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
225
226
	}
	else
227
		GMap1::collapseEdge(d) ;	// Just collapse edge d
228
229

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
230
231
232
233
}

bool GMap2::flipEdge(Dart d)
{
234
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
235
	{
236
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
237
238
239
240
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
		Dart dNext2 = phi1(dNext);
		Dart eNext2 = phi1(eNext);

		beta1unsew(d) ;
		beta1unsew(eNext) ;
		beta1unsew(e) ;
		beta1unsew(dNext) ;
		beta1unsew(dNext2) ;
		beta1unsew(eNext2) ;

		beta1sew(beta0(e), eNext2) ;
		beta1sew(d, beta0(eNext)) ;
		beta1sew(beta0(d), dNext2) ;
		beta1sew(e, beta0(dNext)) ;
		beta1sew(eNext, beta0(dPrev)) ;
		beta1sew(dNext, beta0(ePrev)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
258
259
260
261
262
263
264
		return true ;
	}
	return false ; // cannot flip a border edge
}

bool GMap2::flipBackEdge(Dart d)
{
265
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
266
	{
267
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
268
269
270
271
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
		Dart dPrev1 = beta1(dPrev) ;
		Dart ePrev1 = beta1(ePrev) ;

		beta1unsew(d) ;
		beta1unsew(eNext) ;
		beta1unsew(e) ;
		beta1unsew(dNext) ;
		beta1unsew(dPrev) ;
		beta1unsew(ePrev) ;

		beta1sew(beta0(e), dPrev) ;
		beta1sew(d, dPrev1) ;
		beta1sew(beta0(d), ePrev) ;
		beta1sew(e, ePrev1) ;
		beta1sew(eNext, beta0(dPrev)) ;
		beta1sew(dNext, beta0(ePrev)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
289
290
291
292
293
		return true ;
	}
	return false ; // cannot flip a border edge
}

294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
//void GMap2::insertEdgeInVertex(Dart d, Dart e)
//{
//	assert(!sameVertex(d,e) && phi2(e)==phi_1(e));
//
//	phi1sew(phi_1(d),phi_1(e));
//}
//
//void GMap2::removeEdgeFromVertex(Dart d)
//{
//	assert(phi2(d)!=d);
//
//	phi1sew(phi_1(d),phi2(d));
//}

void GMap2::sewFaces(Dart d, Dart e, bool withBoundary)
309
{
310
311
312
313
314
315
316
317
	// if sewing with fixed points
	if (!withBoundary)
	{
		assert(beta2(d) == d && beta2(beta0(d)) == beta0(d) && beta2(e) == e && beta2(beta0(e)) == beta0(e)) ;
		beta2sew(d, beta0(e)) ;
		beta2sew(e, beta0(d)) ;
		return ;
	}
318

319
	assert(isBoundaryEdge(d) && isBoundaryEdge(e)) ;
320

321
322
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
323

324
325
326
327
	beta2unsew(d) ;	// unsew faces from boundary
	beta2unsew(beta0(d)) ;
	beta2unsew(e) ;
	beta2unsew(beta0(e)) ;
328

329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
	if (ee != phi_1(dd))
	{
		Dart eeN = phi1(ee) ;		// remove the boundary edge
		Dart dd1 = beta1(dd) ;
		beta1unsew(eeN) ;
		beta1unsew(dd1) ;
		beta1sew(beta0(ee), dd) ;
		beta1sew(eeN, dd1) ;
	}
	if (dd != phi_1(ee))
	{
		Dart ddN = phi1(dd) ;		// and properly close incident boundaries
		Dart ee1 = beta1(ee) ;
		beta1unsew(ddN) ;
		beta1unsew(ee1) ;
		beta1sew(beta0(dd), ee) ;
		beta1sew(ddN, ee1) ;
	}
	GMap1::deleteFace(dd) ;

	beta2sew(d, beta0(e)) ; // sew the faces
	beta2sew(e, beta0(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
351
352
353
354
}

void GMap2::unsewFaces(Dart d)
{
355
356
357
358
359
360
361
	assert(!isBoundaryEdge(d)) ;

	Dart dd = phi2(d);

	Dart e = newBoundaryFace(2);
	Dart ee = phi1(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
362
363
	Dart f = findBoundaryEdgeOfVertex(d) ;
	if (f != NIL)
364
365
366
367
368
369
370
371
	{
		Dart f1 = beta1(f) ;
		beta1unsew(ee) ;
		beta1unsew(f) ;
		beta1sew(f, beta0(e)) ;
		beta1sew(f1, ee) ;
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
372
373
	f = findBoundaryEdgeOfVertex(dd) ;
	if (f != NIL)
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
	{
		Dart f1 = beta1(f) ;
		beta1unsew(e) ;
		beta1unsew(f) ;
		beta1sew(f, beta0(ee)) ;
		beta1sew(f1, e) ;
	}

	beta2unsew(d) ;
	beta2unsew(beta0(d)) ;
	beta2unsew(dd) ;
	beta2unsew(beta0(dd)) ;

	beta2sew(d, beta0(e)) ;		// sew faces
	beta2sew(e, beta0(d)) ;
	beta2sew(dd, beta0(ee)) ;	// to the boundary
	beta2sew(ee, beta0(dd)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
391
392
393
394
395
396
397
}

bool GMap2::collapseDegeneratedFace(Dart d)
{
	Dart e = phi1(d);				// Check if the face is a loop
	if (phi1(e) == d)				// Yes: it contains one or two edge(s)
	{
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
		Dart d2 = phi2(d) ;			// Check opposite edges
		Dart e2 = phi2(e) ;
		beta2unsew(d) ;
		beta2unsew(beta0(d)) ;
		if(d != e)
		{
			beta2unsew(e) ;
			beta2unsew(beta0(e)) ;
			beta2sew(d2, beta0(e2)) ;
			beta2sew(e2, beta0(d2)) ;
		}
		else
		{
			Dart d21 = beta1(d2) ;
			Dart d2N = phi1(d2) ;
			beta1unsew(d2) ;
			beta1unsew(d2N) ;
			beta1sew(d21, d2N) ;
			beta1sew(d2, beta0(d2)) ;
			GMap1::deleteFace(d2) ;
		}
		GMap1::deleteFace(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
420
421
422
423
424
425
426
		return true ;
	}
	return false ;
}

void GMap2::splitFace(Dart d, Dart e)
{
427
428
429
430
431
432
433
434
435
436
	assert(d != e && sameFace(d, e)) ;

	if(!sameOrientedFace(d, e))
		e = beta1(e) ;

	GMap1::cutEdge(phi_1(d)) ;
	GMap1::cutEdge(phi_1(e)) ;
	GMap1::splitFace(phi_1(d), phi_1(e)) ;
	beta2sew(phi_1(d), beta1(e)) ;
	beta2sew(phi_1(e), beta1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
437
438
439
440
}

bool GMap2::mergeFaces(Dart d)
{
441
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
442
	{
443
444
445
446
447
448
		Dart e = phi2(d) ;
		beta2unsew(d) ;
		beta2unsew(e) ;
		GMap1::mergeFaces(d, phi1(e)) ;
		GMap1::mergeFaces(e, phi1(d)) ;
		GMap1::deleteFace(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
449
450
451
452
453
454
455
456
		return true ;
	}
	return false ;
}

void GMap2::extractTrianglePair(Dart d)
{
	Dart e = phi2(d) ;
457
458
459
460

	assert(!isBoundaryFace(d) && !isBoundaryFace(e)) ;
	assert(faceDegree(d) == 3 && faceDegree(e) == 3) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
461
462
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
	beta2unsew(d1) ;
	beta2unsew(beta0(d1)) ;
	beta2unsew(d2) ;
	beta2unsew(beta0(d2)) ;
	beta2sew(d1, beta0(d2)) ;
	beta2sew(d2, beta0(d1)) ;

	Dart e1 = phi2(phi1(e)) ;
	Dart e2 = phi2(phi_1(e)) ;
	beta2unsew(e1) ;
	beta2unsew(beta0(e1)) ;
	beta2unsew(e2) ;
	beta2unsew(beta0(e2)) ;
	beta2sew(e1, beta0(e2)) ;
	beta2sew(e2, beta0(e1)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
478
479
480
481
482
}

void GMap2::insertTrianglePair(Dart d, Dart v1, Dart v2)
{
	Dart e = phi2(d) ;
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507

	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;

	Dart vv1 = phi2(v1) ;
	beta2unsew(v1) ;
	beta2unsew(vv1) ;
	beta2sew(phi_1(d), beta0(v1)) ;
	beta2sew(beta1(d), v1) ;
	beta2sew(phi1(d), beta0(vv1)) ;
	beta2sew(beta0(phi1(d)), vv1) ;

	Dart vv2 = phi2(v2) ;
	beta2unsew(v2) ;
	beta2unsew(vv2) ;
	beta2sew(phi_1(e), beta0(v2)) ;
	beta2sew(beta1(e), v2) ;
	beta2sew(phi1(e), beta0(vv2)) ;
	beta2sew(beta0(phi1(e)), vv2) ;
}

void GMap2::unsewAroundVertex(Dart d)
{
	Dart it = d ;
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
508
	{
509
510
511
512
513
514
515
516
517
518
		Dart temp = phi1(it) ;
		Dart e_1 = phi_1(it) ;

		do
		{
			unsewFaces(temp) ;
			temp = phi1(temp) ;
		} while(temp != e_1);

		it = alpha1(it);
Pierre Kraemer's avatar
Pierre Kraemer committed
519
	}
520
	while(it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
521
522
523
524
}

bool GMap2::mergeVolumes(Dart d, Dart e)
{
525
526
	assert(!isBoundaryMarked(d) && !isBoundaryMarked(e)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
527
	if (GMap2::isBoundaryFace(d) || GMap2::isBoundaryFace(e))
528
529
		return false;

Pierre Kraemer's avatar
Pierre Kraemer committed
530
	// First traversal of both faces to check the face sizes
531
532
	// and store their edges to efficiently access them further

Pierre Kraemer's avatar
Pierre Kraemer committed
533
534
	std::vector<Dart> dDarts;
	std::vector<Dart> eDarts;
535
	dDarts.reserve(16);		// usual faces have less than 16 edges
Pierre Kraemer's avatar
Pierre Kraemer committed
536
537
538
	eDarts.reserve(16);

	Dart dFit = d ;
539
	Dart eFit = phi1(e) ;	// must take phi1 because of the use
Pierre Kraemer's avatar
Pierre Kraemer committed
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
	do						// of reverse iterator for sewing loop
	{
		dDarts.push_back(dFit) ;
		dFit = phi1(dFit) ;
	} while(dFit != d) ;
	do
	{
		eDarts.push_back(eFit) ;
		eFit = phi1(eFit) ;
	} while(eFit != phi1(e)) ;

	if(dDarts.size() != eDarts.size())
		return false ;

	// Make the sewing: take darts in initial order (clockwise) in first face
	// and take darts in reverse order (counter-clockwise) in the second face
	std::vector<Dart>::iterator dIt;
	std::vector<Dart>::reverse_iterator eIt;
	for (dIt = dDarts.begin(), eIt = eDarts.rbegin(); dIt != dDarts.end(); ++dIt, ++eIt)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
560
		Dart d2 = phi2(*dIt);	// Search the faces adjacent to dNext and eNext
Pierre Kraemer's avatar
Pierre Kraemer committed
561
		Dart e2 = phi2(*eIt);
562
563
564
565
566
567
		beta2unsew(d2);		// Unlink the two adjacent faces from dNext and eNext
		beta2unsew(beta0(d2));
		beta2unsew(e2);
		beta2unsew(beta0(e2));
		beta2sew(d2, beta0(e2));	// Link the two adjacent faces together
		beta2sew(e2, beta0(d2));
Pierre Kraemer's avatar
Pierre Kraemer committed
568
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
569
570
	GMap1::deleteFace(d);		// Delete the two alone faces
	GMap1::deleteFace(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
571
572
573
574
575
576
577
578

	return true ;
}

/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

Thomas's avatar
Thomas committed
579
580
bool GMap2::sameOrientedVertex(Dart d, Dart e)
{
581
	Dart it = d;
Thomas's avatar
Thomas committed
582
583
	do
	{
584
		if (it == e)	// Test equality with e
Thomas's avatar
Thomas committed
585
			return true;
586
587
588
		it = alpha1(it);
	} while (it != d);
	return false;		// None is equal to e => vertices are distinct
Thomas's avatar
Thomas committed
589
590
}

591
592
593
594
595
596
597
598
599
600
601
unsigned int GMap2::vertexDegree(Dart d)
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = alpha1(it) ;
	} while (it != d) ;
	return count ;
}
Thomas's avatar
Thomas committed
602

603
bool GMap2::isBoundaryVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
604
{
605
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
606
607
	do
	{
608
609
610
611
612
		if (isBoundaryMarked(it))
			return true ;
		it = alpha1(it) ;
	} while (it != d) ;
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
613
614
}

615
Dart GMap2::findBoundaryEdgeOfVertex(Dart d)
616
{
617
	Dart it = d ;
618
619
	do
	{
620
621
622
623
624
		if (isBoundaryMarked(it))
			return it ;
		it = alpha1(it) ;
	} while (it != d) ;
	return NIL ;
625
626
}

627
628
629
bool GMap2::isBoundaryFace(Dart d)
{
	Dart it = d ;
630
631
	do
	{
632
		if (isBoundaryMarked(beta2(it)))
633
			return true ;
634
635
		it = phi1(it) ;
	} while (it != d) ;
636
637
638
	return false ;
}

Thomas's avatar
Thomas committed
639
640
641
642
643
644
645
646
647
bool GMap2::sameOrientedVolume(Dart d, Dart e)
{
	DartMarkerStore mark(*this);	// Lock a marker

	std::list<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.push_back(d);		// Start with the face of d
	std::list<Dart>::iterator face;

	// For every face added to the list
648
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Thomas's avatar
Thomas committed
649
	{
650
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
Thomas's avatar
Thomas committed
651
		{
652
			Dart it = *face ;
Thomas's avatar
Thomas committed
653
654
			do
			{
655
				if(it == e)
Thomas's avatar
Thomas committed
656
657
					return true;

658
659
660
				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
				if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
Thomas's avatar
Thomas committed
661
					visitedFaces.push_back(adj);	// Add it
662
663
				it = phi1(it);
			} while(it != *face);
Thomas's avatar
Thomas committed
664
665
666
667
668
		}
	}
	return false;
}

669
unsigned int GMap2::volumeDegree(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
670
{
671
672
	unsigned int count = 0;
	DartMarkerStore mark(*this);		// Lock a marker
673

674
675
676
677
	std::vector<Dart> visitedFaces;		// Faces that are traversed
	visitedFaces.reserve(16);
	visitedFaces.push_back(d);			// Start with the face of d
	std::vector<Dart>::iterator face;
678
679

	// For every face added to the list
680
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
681
	{
682
683
		Dart df = visitedFaces[i];
		if (!isBoundaryMarked(df) && !mark.isMarked(df))		// Face has not been visited yet
684
		{
685
686
			++count;
			Dart it = df ;
687
688
			do
			{
689
690
691
692
693
694
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
				if ( !isBoundaryMarked(adj) && !mark.isMarked(adj) )
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
695
696
		}
	}
697
698
699
700
701
702
703
704
705
706
707
708
709

	return count;
}

bool GMap2::isTriangular()
{
	TraversorF<GMap2> t(*this) ;
	for(Dart d = t.begin(); d != t.end(); d = t.next())
	{
		if(faceDegree(d) != 3)
			return false ;
	}
	return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
710
711
712
713
}

bool GMap2::check()
{
714
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
715
716
717
718
719
	for(Dart d = begin(); d != end(); next(d))
	{
		Dart dd = beta0(d);
		if (beta0(dd) != d)	// beta0 involution ?
		{
720
			CGoGNout << "Check: beta0 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
721
722
723
724
725
726
			return false;
		}

		dd = beta1(d);
		if (beta1(dd) != d)	// beta1 involution ?
		{
727
			CGoGNout << "Check: beta1 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
728
729
730
731
732
733
			return false;
		}

		dd = beta2(d);
		if (beta2(dd) != d)	// beta2 involution ?
		{
734
			CGoGNout << "Check: beta2 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
735
736
737
738
			return false;
		}
	}

739
	CGoGNout << "Check: topology ok" << CGoGNendl;
740
741
742
743
744
745
746
747
748
749

    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 ;

Pierre Kraemer's avatar
Pierre Kraemer committed
750
751
752
	return true;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
bool GMap2::checkSimpleOrientedPath(std::vector<Dart>& vd)
{
	DartMarkerStore dm(*this) ;
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
		if(dm.isMarked(*it))
			return false ;
		dm.markOrbit(VERTEX, *it) ;

		std::vector<Dart>::iterator prev ;
		if(it == vd.begin())
			prev = vd.end() - 1 ;
		else
			prev = it - 1 ;

		if(!sameVertex(*it, phi1(*prev)))
			return false ;
	}
	return true ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
774
775
776
777
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
778
bool GMap2::foreach_dart_of_oriented_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
779
{
780
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
781
782
	do
	{
783
		if (f(it))
Pierre Kraemer's avatar
Pierre Kraemer committed
784
			return true;
785
786
		it = alpha1(it);
 	} while (it != d);
787
 	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
788
789
}

Sylvain Thery's avatar
Sylvain Thery committed
790
bool GMap2::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
791
792
793
794
{
	if (f(d))
		return true ;
	Dart e = beta0(d) ;
795
796
797
798
799
800
	if (f(e))
		return true ;
	e = beta2(d) ;
	if (f(e))
		return true ;
	e = beta0(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
801
802
803
804
805
806
	if (f(e))
		return true ;

	return false ;
}

807
808
bool GMap2::foreach_dart_of_oriented_volume(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
809
	DartMarkerStore mark(*this, thread);	// Lock a marker
810
811
	bool found = false;				// Last functor return value

Pierre Kraemer's avatar
Pierre Kraemer committed
812
813
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
814
815
816
	visitedFaces.push_back(d);		// Start with the face of d

	// For every face added to the list
Pierre Kraemer's avatar
Pierre Kraemer committed
817
	for (std::vector<Dart>::iterator it = visitedFaces.begin(); !found && it != visitedFaces.end(); ++it)
818
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
819
		if (!mark.isMarked(*it))		// Face has not been visited yet
820
821
		{
			// Apply functor to the darts of the face
Pierre Kraemer's avatar
Pierre Kraemer committed
822
			found = foreach_dart_of_oriented_face(*it, f);
823
824
825
826
827

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
828
				Dart e = *it ;
829
830
				do
				{
Pierre Kraemer's avatar
Pierre Kraemer committed
831
832
833
					mark.mark(e);					// Mark
					Dart adj = phi2(e);				// Get adjacent face
					if (!mark.isMarked(e))
834
						visitedFaces.push_back(adj);	// Add it
Pierre Kraemer's avatar
Pierre Kraemer committed
835
836
					e = phi1(e);
				} while(e != *it);
837
838
839
840
841
842
			}
		}
	}
	return found;
}

843
844
845
846
847
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/

unsigned int GMap2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
848
{
849
	assert(beta2(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
850

851
852
	Dart first = newEdge();		// First edge of the face that will fill the hole
	unsigned int countEdges = 1;
Pierre Kraemer's avatar
Pierre Kraemer committed
853

854
855
	beta2sew(d, beta0(first));	// sew the new edge to the hole
	beta2sew(first, beta0(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
856

857
858
859
	Dart dNext = d;	// Turn around the hole
	Dart dPhi1;		// to complete the face
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
860
	{
861
862
863
		dPhi1 = phi1(dNext) ;
		dNext = beta2(dPhi1) ;
		while(dNext != dPhi1)
Pierre Kraemer's avatar
Pierre Kraemer committed
864
		{
865
866
			dPhi1 = beta1(dNext) ;	// Search and put in dNext
			dNext = beta2(dPhi1) ;	// the next dart of the hole
Pierre Kraemer's avatar
Pierre Kraemer committed
867
		}
868
869

		if (dPhi1 != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
870
		{
871
872
873
874
875
876
877
			Dart next = newEdge();	// Add a new edge there and link it to the face
			++countEdges;
			Dart tmp = phi1(first) ;
			beta1sew(beta0(first), next);	// the edge is linked to the face
			beta1sew(beta0(next), tmp) ;
			beta2sew(dNext, beta0(next));	// the face is linked to the hole
			beta2sew(next, beta0(dNext));
Pierre Kraemer's avatar
Pierre Kraemer committed
878
		}
879
880
	} while (dPhi1 != d);

Pierre Kraemer's avatar
Pierre Kraemer committed
881
882
	if(forboundary)
		boundaryMarkOrbit(FACE, phi2(d));
883
884
885
886
887
888
889
890
891
892
893

	return countEdges ;
}

void GMap2::closeMap()
{
	// Search the map for topological holes (fix points of phi2)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (beta2(d) == d)
			closeHole(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
894
895
896
897
	}
}

} // namespace CGoGN