Coupure prévue mardi 3 Août au matin pour maintenance du serveur. Nous faisons au mieux pour que celle-ci soit la plus brève possible.

gmap3.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
26
27
28
29
30
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/gmap/gmap3.h"
#include "Topology/generic/dartmarker.h"

namespace CGoGN
{

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

void GMap3::deleteVolume(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
36
{
Pierre Kraemer's avatar
Pierre Kraemer committed
37
	DartMarkerStore mark(*this);		// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
38
39

	std::vector<Dart> visitedFaces;		// Faces that are traversed
40
	visitedFaces.reserve(512);
Pierre Kraemer's avatar
Pierre Kraemer committed
41
	visitedFaces.push_back(d);			// Start with the face of d
Pierre Kraemer's avatar
Pierre Kraemer committed
42
	mark.markOrbit(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
43
44

	// For every face added to the list
45
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
46
	{
47
		Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
48

Pierre Kraemer's avatar
Pierre Kraemer committed
49
50
		if(!isBoundaryFace(e))
			unsewVolumes(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
51

Pierre Kraemer's avatar
Pierre Kraemer committed
52
53
54
55
		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
Pierre Kraemer's avatar
Pierre Kraemer committed
56
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
57
58
59
60
				visitedFaces.push_back(ee) ;
				mark.markOrbit(FACE, ee) ;
			}
			e = phi1(e) ;
61
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
62
	}
63

Pierre Kraemer's avatar
Pierre Kraemer committed
64
65
66
67
68
69
70
71
72
73
74
75
	Dart dd = phi3(d) ;
	GMap2::deleteCC(d) ;
	GMap2::deleteCC(dd) ;
}

void GMap3::fillHole(Dart d)
{
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi3(dd) ;
	boundaryUnmarkOrbit(VOLUME, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
76
77
}

78
/*! @name Topological Operators
Pierre Kraemer's avatar
Pierre Kraemer committed
79
 *  Topological operations on 3-G-maps
80
 *************************************************************************/
81

Pierre Kraemer's avatar
Pierre Kraemer committed
82
Dart GMap3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
83
{
84
85
86
87
88
89
90
91
92
93
94
95
96
97
	if(isBoundaryVertex(d))
		return NIL ;

	// Save the darts around the vertex
	// (one dart per face should be enough)
	std::vector<Dart> fstoretmp;
	fstoretmp.reserve(128);
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

	// just one dart per face
	std::vector<Dart> fstore;
	fstore.reserve(128);
	DartMarker mf(*this);
98
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
99
	{
100
		if(!mf.isMarked(fstoretmp[i]))
101
		{
102
103
			mf.markOrbit(FACE, fstoretmp[i]);
			fstore.push_back(fstoretmp[i]);
104
105
		}
	}
106

107
108
109
110
111
112
113
114
115
116
117
	Dart res = NIL ;
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
		Dart fit = *it ;
		Dart end = phi_1(fit) ;
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
118

119
120
			if(res == NIL)
				res = d2 ;
121

122
123
			beta2unsew(d2) ;
			beta2unsew(beta0(d2)) ;
124

125
126
			beta2unsew(d32) ;
			beta2unsew(beta0(d32)) ;
127

128
129
130
131
			beta2sew(d2, beta0(d32)) ;
			beta2sew(beta0(d2), d32) ;
			beta2sew(fit, beta0(d3)) ;
			beta2sew(beta0(fit), d3) ;
132
133

			fit = phi1(fit) ;
134
135
		}
	}
136

137
	GMap2::deleteCC(d) ;
138

139
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
140
}
141

142
Dart GMap3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
143
144
145
{
	Dart prev = d ;
	Dart dd = alpha2(d) ;
146
	Dart nd = GMap2::cutEdge(d) ;
147

Pierre Kraemer's avatar
Pierre Kraemer committed
148
	while(dd != d)
149
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
150
151
		prev = dd ;
		dd = alpha2(dd) ;
152

Pierre Kraemer's avatar
Pierre Kraemer committed
153
		GMap2::cutEdge(prev) ;
154

Pierre Kraemer's avatar
Pierre Kraemer committed
155
156
157
		Dart d3 = beta3(prev);
		beta3sew(beta0(prev), beta0(d3));
		beta3sew(phi1(prev), phi1(d3));
158
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
159
160
161

	Dart d3 = beta3(d);
	beta3sew(beta0(d), beta0(d3));
Pierre Kraemer's avatar
Pierre Kraemer committed
162
	beta3sew(phi1(d), phi1(d3));
163
164

	return nd ;
165
166
}

Pierre Kraemer's avatar
Pierre Kraemer committed
167
bool GMap3::uncutEdge(Dart d)
Thomas's avatar
Thomas committed
168
{
169
	if(vertexDegree(phi1(d)) == 2)
Thomas's avatar
Thomas committed
170
	{
171
172
173
174
175
176
177
		Dart prev = d ;

		Dart dd = d;
		do
		{
			prev = dd;
			dd = alpha2(dd);
Thomas's avatar
Thomas committed
178

179
180
			GMap2::uncutEdge(prev);
		} while (dd != d) ;
Thomas's avatar
Thomas committed
181

182
		return true;
Thomas's avatar
Thomas committed
183
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
184
	return false;
Thomas's avatar
Thomas committed
185
186
}

187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
Dart GMap3::deleteEdge(Dart d)
{
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
	Dart dit = d ;
	do
	{
		Dart fit = dit ;
		Dart end = fit ;
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;

			if(res == NIL)
				res = d2 ;

			beta2unsew(d2) ;
			beta2unsew(beta0(d2)) ;
			beta2unsew(d32) ;
			beta2unsew(beta0(d32)) ;

			beta2sew(d2, beta0(d32)) ;
			beta2sew(beta0(d2), d32) ;
			beta2sew(fit, beta0(d3)) ;
			beta2sew(beta0(fit), d3) ;

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

	GMap2::deleteCC(d) ;

	return res ;
}

228
void GMap3::splitFace(Dart d, Dart e)
Thomas's avatar
Thomas committed
229
{
230
	assert(d != e && GMap2::sameOrientedFace(d, e)) ;
Thomas's avatar
Thomas committed
231

232
233
	Dart dd = beta1(beta3(d));
	Dart ee = beta1(beta3(e));
Thomas's avatar
Thomas committed
234

Pierre Kraemer's avatar
Pierre Kraemer committed
235
236
237
238
239
240
241
242
243
244
	Dart dprev = phi_1(d) ;
	Dart eprev = phi_1(e) ;
	Dart ddprev = phi_1(dd) ;
	Dart eeprev = phi_1(ee) ;

	beta3unsew(beta1(d)) ;
	beta3unsew(beta1(e)) ;
	beta3unsew(beta1(dd)) ;
	beta3unsew(beta1(ee)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
245
246
	GMap2::splitFace(d, e);
	GMap2::splitFace(dd, ee);
247
248
249
250
	beta3sew(beta1(d), phi_1(ee));
	beta3sew(phi_1(d), beta1(ee));
	beta3sew(beta1(e), phi_1(dd));
	beta3sew(phi_1(e), beta1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
251
252
253
254
255

	beta3sew(beta0(dprev), beta0(beta3(dprev))) ;
	beta3sew(beta0(eprev), beta0(beta3(eprev))) ;
	beta3sew(beta0(ddprev), beta0(beta3(ddprev))) ;
	beta3sew(beta0(eeprev), beta0(beta3(eeprev))) ;
Thomas's avatar
Thomas committed
256
257
}

Pierre Kraemer's avatar
Pierre Kraemer committed
258
void GMap3::sewVolumes(Dart d, Dart e, bool withBoundary)
259
260
261
{
	assert(faceDegree(d) == faceDegree(e));

Pierre Kraemer's avatar
Pierre Kraemer committed
262
263
264
	// if sewing with fixed points
	if (!withBoundary)
	{
265
		assert(beta3(d) == d && beta3(e) == e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
266
267
268
269
		Dart fitD = d ;
		Dart fitE = e ;
		do
		{
270
271
			beta3sew(fitD, beta0(fitE)) ;
			beta3sew(beta0(fitD), fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
272
273
274
275
276
277
			fitD = phi1(fitD) ;
			fitE = phi_1(fitE) ;
		} while(fitD != d) ;
		return ;
	}

278
279
	Dart dd = beta3(d) ;
	Dart ee = beta3(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
280
281
282

	Dart fitD = dd ;
	Dart fitE = ee ;
283
284
	do
	{
285
286
		Dart fitD2 = beta2(fitD) ;
		Dart fitE2 = beta2(fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
287
288
		if(fitD2 != fitE)
		{
289
290
			beta2unsew(fitD) ;
			beta2unsew(fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
291
292
			beta2unsew(beta0(fitD)) ;
			beta2unsew(beta0(fitE)) ;
293
294
295
296
			beta2sew(fitD2, beta0(fitE2)) ;
			beta2sew(beta0(fitD2), fitE2) ;
			beta2sew(fitD, beta0(fitE)) ;
			beta2sew(beta0(fitD), fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
297
		}
298
299
300
301
		beta3unsew(fitD) ;
		beta3unsew(beta0(fitD)) ;
		beta3unsew(fitE) ;
		beta3unsew(beta0(fitE)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
302
303
304
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != dd) ;
305
	GMap2::deleteCC(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
306
307
308

	fitD = d ;
	fitE = e ;
309
310
	do
	{
311
312
		beta3sew(fitD, beta0(fitE)) ;
		beta3sew(beta0(fitD), fitE) ;
313
314
315
316
317
318
319
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void GMap3::unsewVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
320
321
322
323
324
325
326
327
328
329
330
331
	assert(!isBoundaryFace(d)) ;

	unsigned int nbE = faceDegree(d) ;
	Dart d3 = phi3(d);

	Dart b1 = newBoundaryFace(nbE) ;
	Dart b2 = newBoundaryFace(nbE) ;

	Dart fit1 = d ;
	Dart fit2 = d3 ;
	Dart fitB1 = b1 ;
	Dart fitB2 = b2 ;
332
333
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
334
335
336
337
		Dart f = findBoundaryFaceOfEdge(fit1) ;
		if(f != NIL)
		{
			Dart f2 = phi2(f) ;
338
339
340
341
342
343
			beta2unsew(f) ;
			beta2unsew(beta0(f)) ;
			beta2sew(fitB1, beta0(f)) ;
			beta2sew(beta0(fitB1), f) ;
			beta2sew(fitB2, beta0(f2)) ;
			beta2sew(beta0(fitB2), f2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
344
345
		}
		else
346
347
348
349
		{
			beta2sew(fitB1, beta0(fitB2)) ;
			beta2sew(beta0(fitB1), fitB2) ;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
350

351
352
353
354
355
356
		beta3unsew(fit1) ;
		beta3unsew(beta0(fit1)) ;
		beta3sew(fit1, beta0(fitB1)) ;
		beta3sew(beta0(fit1), fitB1) ;
		beta3sew(fit2, beta0(fitB2)) ;
		beta3sew(beta0(fit2), fitB2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
357
358
359
360
361
362

		fit1 = phi1(fit1) ;
		fit2 = phi_1(fit2) ;
		fitB1 = phi_1(fitB1) ;
		fitB2 = phi1(fitB2) ;
	} while(fitB1 != b1) ;
363
364
365
366
}

bool GMap3::mergeVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
367
	if(!GMap3::isBoundaryFace(d))
368
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
369
		GMap2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
370
371
372
373
374
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
void GMap3::splitVolume(std::vector<Dart>& vd)
{
	assert(checkSimpleOrientedPath(vd)) ;

	Dart e = vd.front();
	Dart e2 = phi2(e);

	//unsew the edge path
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
		GMap2::unsewFaces(*it);

	GMap2::fillHole(e) ;
	GMap2::fillHole(e2) ;

	//sew the two connected components
Pierre Kraemer's avatar
Pierre Kraemer committed
390
	GMap3::sewVolumes(beta2(e), beta2(e2), false);
Pierre Kraemer's avatar
Pierre Kraemer committed
391
392
}

393
394
395
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
396

397
bool GMap3::sameOrientedVertex(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
398
{
399
400
	DartMarkerStore mv(*this);	// Lock a marker

Pierre Kraemer's avatar
Pierre Kraemer committed
401
402
403
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
404
405
	mv.mark(d);

406
	for(unsigned int i = 0; i < darts.size(); ++i)
407
	{
408
		if(darts[i] == e)
409
410
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
411
		// add phi21 and phi23 successor if they are not marked yet
412
		Dart d2 = phi2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
413
414
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
415

Pierre Kraemer's avatar
Pierre Kraemer committed
416
417
418
419
420
421
422
423
424
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
425
426
427
428
429
430
431
432
		}
	}
	return false;
}

bool GMap3::sameVertex(Dart d, Dart e)
{
	DartMarkerStore mv(*this);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
433

Pierre Kraemer's avatar
Pierre Kraemer committed
434
435
436
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
Pierre Kraemer's avatar
Pierre Kraemer committed
437
438
	mv.mark(d);

439
	for(unsigned int i = 0; i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
440
	{
441
		if(darts[i] == e)
442
443
			return true;

444
		Dart dx = beta1(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
445
446
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
447
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
448
449
			mv.mark(dx);
		}
450
		dx = beta2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
451
452
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
453
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
454
455
			mv.mark(dx);
		}
456
		dx = beta3(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
457
458
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
459
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
460
461
462
			mv.mark(dx);
		}
	}
463
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
464
465
}

466
467
unsigned int GMap3::vertexDegree(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
468
	unsigned int count = 0;
469
470
	DartMarkerStore mv(*this);	// Lock a marker

Pierre Kraemer's avatar
Pierre Kraemer committed
471
472
473
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
474
475
	mv.mark(d);

476
	for(unsigned int i = 0; i < darts.size(); ++i)
477
478
	{
		//add phi21 and phi23 successor if they are not marked yet
479
		Dart d2 = phi2(darts[i]);
480
481
482
483
484
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
485
			darts.push_back(d21);
486
487
			mv.mark(d21);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
488
		if(!mv.isMarked(d23))
489
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
490
			darts.push_back(d23);
491
492
493
494
495
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
Pierre Kraemer's avatar
Pierre Kraemer committed
496
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
497
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
498
		if(!me.isMarked(*it))
499
500
		{
			++count;
Pierre Kraemer's avatar
Pierre Kraemer committed
501
			me.markOrbit(EDGE, *it);
502
503
504
505
506
507
508
509
		}
	}

	return count;
}

bool GMap3::isBoundaryVertex(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
510
	DartMarkerStore mv(*this);	// Lock a marker
511

Pierre Kraemer's avatar
Pierre Kraemer committed
512
513
514
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
515
516
	mv.mark(d);

517
	for(unsigned int i = 0; i < darts.size(); ++i)
518
	{
519
		if(isBoundaryMarked(darts[i]))
Pierre Kraemer's avatar
Pierre Kraemer committed
520
			return true ;
521
522

		//add phi21 and phi23 successor if they are not marked yet
523
		Dart d2 = phi2(darts[i]);
524
525
526
527
528
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
529
			darts.push_back(d21);
530
531
			mv.mark(d21);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
532
		if(!mv.isMarked(d23))
533
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
534
			darts.push_back(d23);
535
536
537
			mv.mark(d23);
		}
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
538
	return false ;
539
540
}

541
542
bool GMap3::sameOrientedEdge(Dart d, Dart e)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
543
	Dart it = d;
544
545
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
546
		if(it == e || phi2(it) == e)
547
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
548
549
		it = alpha2(it);
	} while (it != d);
550
551
	return false;
}
Pierre Kraemer's avatar
Pierre Kraemer committed
552

553
bool GMap3::sameEdge(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
554
{
Pierre Kraemer's avatar
Pierre Kraemer committed
555
	Dart it = d;
556
557
	do
	{
558
		if(it == e || beta0(it) == e || beta2(it) == e || phi2(it) == e)
559
560
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
561
562
		it = alpha2(it);
	} while (it != d);
563
564
565
	return false;
}

566
567
568
unsigned int GMap3::edgeDegree(Dart d)
{
	unsigned int deg = 0;
Pierre Kraemer's avatar
Pierre Kraemer committed
569
	Dart it = d;
570
571
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
572
573
574
		++deg;
		it = alpha2(it);
	} while(it != d);
575
576
577
	return deg;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
578
bool GMap3::isBoundaryEdge(Dart d)
579
{
Pierre Kraemer's avatar
Pierre Kraemer committed
580
	Dart it = d;
581
582
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
583
584
585
586
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
587
588
589
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
590
Dart GMap3::findBoundaryFaceOfEdge(Dart d)
591
{
Pierre Kraemer's avatar
Pierre Kraemer committed
592
	Dart it = d;
593
594
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
595
596
597
598
599
600
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
}
601

Pierre Kraemer's avatar
Pierre Kraemer committed
602
603
604
605
606
607
bool GMap3::sameOrientedFace(Dart d, Dart e)
{
	Dart it = d;
	do
	{
		if(it == e || phi3(it) == e)
608
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
609
610
611
612
		it = phi1(it);
	} while (it != d);
	return false;
}
613

Pierre Kraemer's avatar
Pierre Kraemer committed
614
615
616
bool GMap3::isBoundaryVolume(Dart d)
{
	DartMarkerStore mark(*this);	// Lock a marker
617

Pierre Kraemer's avatar
Pierre Kraemer committed
618
619
620
621
	std::vector<Dart> visitedFaces ;
	visitedFaces.reserve(128) ;
	visitedFaces.push_back(d) ;
	mark.markOrbit(FACE, d) ;
622

623
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
624
	{
625
		if (isBoundaryMarked(beta3(visitedFaces[i])))
Pierre Kraemer's avatar
Pierre Kraemer committed
626
627
			return true ;

628
		Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
629
630
631
632
633
634
635
636
637
		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
				mark.markOrbit(FACE, ee) ;
			}
			e = phi1(e) ;
638
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
639
	}
640
641
642
	return false;
}

Thomas's avatar
Thomas committed
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
bool GMap3::check()
{
    CGoGNout << "Check: topology begin" << CGoGNendl;
    DartMarker m(*this);
    m.unmarkAll();
    for(Dart d = this->begin(); d != this->end(); this->next(d))
    {
        Dart d0 = beta0(d);
        if (beta0(d0) != d) // beta0 involution ?
		{
             CGoGNout << "Check: beta0 is not an involution" << CGoGNendl;
            return false;
        }

        Dart d3 = beta3(d);
        if (beta3(d3) != d) // beta3 involution ?
		{
             CGoGNout << "Check: beta3 is not an involution" << CGoGNendl;
            return false;
        }

        if(d3 != d)
        {
        	if(beta1(d3) != beta3(beta1(d)))
        	{
        		CGoGNout << "Check: beta3 , faces are not entirely sewn" << CGoGNendl;
        		return false;
        	}
        }

        Dart d2 = beta2(d);
        if (beta2(d2) != d) // beta2 involution ?
		{
            CGoGNout << "Check: beta2 is not an involution" << CGoGNendl;
            return false;
        }

        Dart d1 = phi1(d);
        if (phi_1(d1) != d) // phi1 a une image correcte ?
		{
            CGoGNout << "Check: unconsistent phi_1 link" << CGoGNendl;
            return false;
        }

        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
		{
            CGoGNout << "Check: dart with two phi1 predecessors" << CGoGNendl;
            return false;
        }
        m.mark(d1);

        if (d1 == d)
            CGoGNout << "Check: (warning) face loop (one edge)" << CGoGNendl;

        if (phi1(d1) == d)
            CGoGNout << "Check: (warning) face with only two edges" << CGoGNendl;

        if (phi2(d1) == d)
            CGoGNout << "Check: (warning) dandling edge (phi2)" << CGoGNendl;

        if (phi3(d1) == d)
            CGoGNout << "Check: (warning) dandling edge (phi3)" << CGoGNendl;
    }

    for(Dart d = this->begin(); d != this->end(); this->next(d))
    {
        if (!m.isMarked(d)) // phi1 a au moins un antécédent ?
		{
        	std::cout << "dart = " << d << std::endl;
            CGoGNout << "Check: dart with no phi1 predecessor" << CGoGNendl;
            return false;
        }
    }

    CGoGNout << "Check: topology ok" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
718
719
720
721
722
723
724
725
726
727
728
729
730

    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 ;

Thomas's avatar
Thomas committed
731
732
733
    return true;
}

734
735
736
737
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

738
739
bool GMap3::foreach_dart_of_oriented_vertex(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
740
	DartMarkerStore mv(*this, thread);	// Lock a marker
741
742
	bool found = false;					// Last functor return value

Pierre Kraemer's avatar
Pierre Kraemer committed
743
744
745
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
746
747
	mv.mark(d);

748
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
749
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
750
		// add phi21 and phi23 successor if they are not marked yet
751
		Dart d2 = phi2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
752
753
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
754

Pierre Kraemer's avatar
Pierre Kraemer committed
755
		if(!mv.isMarked(d21))
756
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
757
758
759
760
761
762
763
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
764
765
		}

766
		found = f(darts[i]);
767
768
769
770
	}
	return found;
}

771
bool GMap3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
772
{
Pierre Kraemer's avatar
Pierre Kraemer committed
773
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
774
	bool found = false;					// Last functor return value
775

Pierre Kraemer's avatar
Pierre Kraemer committed
776
777
778
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
Pierre Kraemer's avatar
Pierre Kraemer committed
779
780
	mv.mark(d);

781
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
782
	{
783
		Dart dx = beta1(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
784
785
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
786
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
787
788
			mv.mark(dx);
		}
789
		dx = beta2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
790
791
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
792
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
793
794
			mv.mark(dx);
		}
795
		dx = beta3(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
796
797
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
798
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
799
800
801
			mv.mark(dx);
		}

802
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
803
804
	}
	return found;
805
}
Pierre Kraemer's avatar
Pierre Kraemer committed
806

807
808
bool GMap3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
809
810
811
812
	Dart it = d;
	do
	{
		if (GMap2::foreach_dart_of_edge(it, f, thread))
813
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
814
815
		it = alpha2(it);
	} while (it != d);
816
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
817
818
}

Sylvain Thery's avatar
Sylvain Thery committed
819
bool GMap3::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
820
{
Sylvain Thery's avatar
Sylvain Thery committed
821
	DartMarkerStore mv(*this,thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
822
823
	bool found = false;					// Last functor return value

Pierre Kraemer's avatar
Pierre Kraemer committed
824
825
826
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(1024);
	darts.push_back(d);			// Start with the dart d
Pierre Kraemer's avatar
Pierre Kraemer committed
827
828
	mv.mark(d);

829
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
830
	{
831
		Dart dx = beta0(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
832
833
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
834
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
835
836
			mv.mark(dx);
		}
837
		dx = beta1(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
838
839
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
840
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
841
842
			mv.mark(dx);
		}
843
		dx = beta2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
844
845
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
846
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
847
848
			mv.mark(dx);
		}
849
		dx = beta3(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
850
851
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
852
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
853
854
855
			mv.mark(dx);
		}

856
		found =  f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
857
858
859
860
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
861
862
863
864
865
866
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/

unsigned int GMap3::closeHole(Dart d, bool forboundary)
{
867
	assert(beta3(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
868
869
870
871
872
	DartMarkerStore m(*this) ;

	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
873
	m.markOrbit(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
874
875
876
877

	unsigned int count = 0 ;

	// For every face added to the list
878
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
879
	{
880
		Dart f = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
881
882
883
884
885
886
887
888
889
890
891
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryFace(degree) ;
		++count ;

		Dart bit = b ;
		do
		{
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
892
				if(beta3(e) == e)
Pierre Kraemer's avatar
Pierre Kraemer committed
893
894
895
896
897
				{
					found = true ;
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
898
						m.markOrbit(FACE, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
899
900
901
902
903
					}
				}
				else if(isBoundaryMarked(e))
				{
					found = true ;
904
905
					beta2sew(e, bit) ;
					beta2sew(beta0(e), beta0(bit)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
906
907
908
909
910
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

911
912
913
			beta3sew(f, bit) ;
			beta3sew(beta0(f), beta0(bit)) ;
			bit = phi1(bit) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
914
			f = phi1(f);
915
		} while(f != visitedFaces[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
	}

	return count ;
}

void GMap3::closeMap()
{
	// Search the map for topological holes (fix points of beta3)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (beta3(d) == d)
			closeHole(d);
	}
}

} // namespace CGoGN