map3.cpp 18.1 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
31
32
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/map3.h"

namespace CGoGN
{

/*! @name Generator and Deletor
 *  To generate or delete volumes in a 3-map
 *************************************************************************/
33
34

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

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

42
	mark.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
43

44
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
45
	{
46
		Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
47

48
49
		if(!isBoundaryFace(e))
			unsewVolumes(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
50
51
52
53
54
55
56

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

untereiner's avatar
untereiner committed
63
64
65
	Dart dd = phi3(d) ;
	Map2::deleteCC(d) ;
	Map2::deleteCC(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
66
67
}

68
69
void Map3::fillHole(Dart d)
{
70
71
72
73
74
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi3(dd) ;
	boundaryUnmarkOrbit(VOLUME, dd) ;
75
76
}

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

81
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
82
{
83
84
85
	if(isBoundaryVertex(d))
		return NIL ;

Pierre Kraemer's avatar
Pierre Kraemer committed
86
87
	// Save the darts around the vertex
	// (one dart per face should be enough)
untereiner's avatar
untereiner committed
88
	std::vector<Dart> fstoretmp;
89
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
90
91
92
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

Pierre Kraemer's avatar
Pierre Kraemer committed
93
	// just one dart per face
untereiner's avatar
untereiner committed
94
	std::vector<Dart> fstore;
95
	fstore.reserve(128);
untereiner's avatar
untereiner committed
96
	DartMarker mf(*this);
97
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
98
	{
99
		if(!mf.isMarked(fstoretmp[i]))
100
		{
101
102
			mf.markOrbit(FACE, fstoretmp[i]);
			fstore.push_back(fstoretmp[i]);
untereiner's avatar
untereiner committed
103
		}
104
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
105

106
	Dart res = NIL ;
untereiner's avatar
untereiner committed
107
108
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
109
110
111
112
113
114
115
116
		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) ;
117

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

121
122
123
124
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
125
126

			fit = phi1(fit) ;
127
		}
untereiner's avatar
untereiner committed
128
	}
129

130
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
131

132
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
133
134
}

David Cazier's avatar
David Cazier committed
135
Dart Map3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
136
137
138
{
	Dart prev = d;
	Dart dd = alpha2(d);
David Cazier's avatar
David Cazier committed
139
	Dart nd = Map2::cutEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
140

141
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
142
143
144
145
146
147
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

148
149
150
151
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
152
153
	}

154
155
156
157
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
158

David Cazier's avatar
David Cazier committed
159
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
160
161
}

Pierre Kraemer's avatar
Pierre Kraemer committed
162
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
163
{
Pierre Kraemer's avatar
Pierre Kraemer committed
164
165
	if(vertexDegree(phi1(d)) == 2)
	{
166
167
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
168

169
170
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
171
172
173
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
174

175
176
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
177
178
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
179
180
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
181
		return true;
untereiner's avatar
untereiner committed
182
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
183
	return false;
untereiner's avatar
untereiner committed
184
185
}

untereiner's avatar
untereiner committed
186
187
188
189
190
191
Dart Map3::deleteEdge(Dart d)
{
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
192
193
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
194
	{
195
196
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
197
198
199
200
201
202
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
203

untereiner's avatar
untereiner committed
204
205
			if(res == NIL)
				res = d2 ;
206

untereiner's avatar
untereiner committed
207
208
209
210
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
211
212

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
213
		}
214
215
216
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
217
218
219
220
221
222
223
224
225
	Map2::deleteCC(d) ;

	return res ;
}

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

226
	Dart dit = d;
untereiner's avatar
untereiner committed
227
228
229

	do
	{
230
231
		Dart e = dit;
		dit = alpha2(dit);
untereiner's avatar
untereiner committed
232

233
234
235
		//test si un seul polyedre autour de l'arete
		if(e == dit)
			resV == phi3(phi2(phi1(e)));
untereiner's avatar
untereiner committed
236

237
		if(delDegenerateVolumes)
untereiner's avatar
untereiner committed
238
		{
239
240
241
242
243
			Map2::collapseEdge(e, true);
			//collapseDegeneretedVolume(e);
		}
		else
			Map2::collapseEdge(e, false);
untereiner's avatar
untereiner committed
244

245
246
		if(resV == NIL)
		{
untereiner's avatar
untereiner committed
247

248
		}
untereiner's avatar
untereiner committed
249
250


251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
	}while(d != dit);





//	Dart e = d;
//
//	// stocke un brin par volume autour de l'arete
//	std::vector<Dart> tmp;
//	tmp.reserve(32);
//	do
//	{
//		tmp.push_back(e);
//		e = alpha2(e);
//	} while (e != d);
//
//	// contraction de la 2 carte de chaque 2-arete
//	for (std::vector<Dart>::iterator it = tmp.begin(); it != tmp.end(); ++it)
//	{
//		// un brin d'une face adjacente a l'arrete contracte
//		Dart d = phi2(phi_1(*it));
//		Map2::collapseEdge(*it, true);
//
//		// test de la degeneresence
//		// impossible d'avoir un volume de moins de 4 faces sans avoir de phi2 en points fixe donc on les vire
//		if(delDegenerateVolumes && Map2::volumeDegree(d) < 4)
//		{
//			Dart e = d;
//			// pour tous les brins de la face adjacente
//
//			do
//			{
//				Dart ee = phi3(e);
//				Dart ff = phi3(phi2(e));
//
//				// si les brins ont un voisin par phi3
//				if(ee != e)
//
//					phi3unsew(ee);
//				if(ff != phi2(e))
//					phi3unsew(ff);
//
//				// si les deux en ont un, il faut les coudres ensemble
//				if(ee != e && ff != phi2(e))
//					phi3sew(ee, ff);
//
//				// on peut supprimer les brins de cette arete
//				deleteDart(e);
//				deleteDart(phi2(e));
//				e = phi1(e);
//
//			} while (e != d);
//		}
//	}
untereiner's avatar
untereiner committed
306
307
308
309

	return resV;
}

310
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
311
{
312
	assert(d != e && Map2::sameOrientedFace(d, e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
313

314
315
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
316

untereiner's avatar
untereiner committed
317
	Map2::splitFace(d, e);
318
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
319

320
321
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
322
323
}

324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
bool Map3::collapseDegeneretedVolume(Dart d)
{
	Dart e1 = phi2(d);
	Dart e2 = phi2(phi1(d));

	//Si l'une des faces est du bord
	if(isBoundaryFace(e1) || isBoundaryFace(e2))
	{
		//alors simple suppression du volume degenere
	}
	else
	{
		Dart e13 = e1;
		Dart e23 = e2;
		if(!isBoundaryFace(e1))
			e13 = phi3(e1);

		if(!isBoundaryFace(e2))
			e23 = phi3(e2);

		//if(faceDegree(e1) < faceDegree)
	}
346
347

	return false;
348
349
}

350
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
351
352
353
{
	assert(faceDegree(d) == faceDegree(e));

354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
	// if sewing with fixed points
	if (!withBoundary)
	{
		assert(phi3(d) == d && phi3(e) == e) ;
		Dart fitD = d ;
		Dart fitE = e ;
		do
		{
			phi3sew(fitD, fitE) ;
			fitD = phi1(fitD) ;
			fitE = phi_1(fitE) ;
		} while(fitD != d) ;
		return ;
	}

	Dart dd = phi3(d) ;
	Dart ee = phi3(e) ;

	Dart fitD = dd ;
	Dart fitE = ee ;
	do
	{
		Dart fitD2 = phi2(fitD) ;
		Dart fitE2 = phi2(fitE) ;
		if(fitD2 != fitE)
		{
			phi2unsew(fitD) ;
			phi2unsew(fitE) ;
			phi2sew(fitD2, fitE2) ;
			phi2sew(fitD, fitE) ;
		}
385
386
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
387
388
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
389
	} while(fitD != dd) ;
390
391
	Map2::deleteCC(dd) ;

392
393
	fitD = d ;
	fitE = e ;
394
395
	do
	{
396
		phi3sew(fitD, fitE) ;
397
398
399
400
401
402
403
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void Map3::unsewVolumes(Dart d)
{
untereiner's avatar
untereiner committed
404
405
406
407
408
409
410
411
412
413
414
415
	assert(!isBoundaryFace(d)) ;

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

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

	Dart fit1 = d ;
	Dart fit2 = d3 ;
	Dart fitB1 = b1 ;
	Dart fitB2 = b2 ;
416
417
	do
	{
untereiner's avatar
untereiner committed
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
		Dart f = findBoundaryFaceOfEdge(fit1) ;
		if(f != NIL)
		{
			Dart f2 = phi2(f) ;
			phi2unsew(f) ;
			phi2sew(fitB1, f) ;
			phi2sew(fitB2, f2) ;
		}
		else
			phi2sew(fitB1, fitB2) ;

		phi3unsew(fit1) ;
		phi3sew(fit1, fitB1) ;
		phi3sew(fit2, fitB2) ;

		fit1 = phi1(fit1) ;
		fit2 = phi_1(fit2) ;
		fitB1 = phi_1(fitB1) ;
		fitB2 = phi1(fitB2) ;
	} while(fitB1 != b1) ;
438
439
440
441
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
442
	if(!Map3::isBoundaryFace(d))
443
	{
untereiner's avatar
untereiner committed
444
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
445
446
447
448
449
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
450
451
void Map3::splitVolume(std::vector<Dart>& vd)
{
untereiner's avatar
untereiner committed
452
453
	assert(checkSimpleOrientedPath(vd)) ;

untereiner's avatar
untereiner committed
454
455
456
457
458
459
460
	Dart e = vd.front();
	Dart e2 = phi2(e);

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

untereiner's avatar
untereiner committed
461
462
	Map2::fillHole(e) ;
	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
463

untereiner's avatar
untereiner committed
464
465
	//sew the two connected components
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
466
467
}

468
469
470
471
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

472
bool Map3::sameVertex(Dart d, Dart e)
473
474
475
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
476
477
478
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
479
480
	mv.mark(d);

481
	for(unsigned int i = 0; i < darts.size(); ++i)
482
	{
483
		if(darts[i] == e)
484
485
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
486
		// add phi21 and phi23 successor if they are not marked yet
487
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
488
489
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
490

untereiner's avatar
untereiner committed
491
492
493
494
495
496
497
498
499
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
500
501
502
503
504
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
505
506
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
507
	unsigned int count = 0;
untereiner's avatar
untereiner committed
508
509
	DartMarkerStore mv(*this);	// Lock a marker

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

515
	for(unsigned int i = 0; i < darts.size(); ++i)
untereiner's avatar
untereiner committed
516
517
	{
		//add phi21 and phi23 successor if they are not marked yet
518
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
519
520
521
522
523
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
524
			darts.push_back(d21);
untereiner's avatar
untereiner committed
525
526
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
527
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
528
		{
untereiner's avatar
untereiner committed
529
			darts.push_back(d23);
untereiner's avatar
untereiner committed
530
531
532
533
534
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
untereiner's avatar
untereiner committed
535
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
536
	{
untereiner's avatar
untereiner committed
537
		if(!me.isMarked(*it))
untereiner's avatar
untereiner committed
538
539
		{
			++count;
untereiner's avatar
untereiner committed
540
			me.markOrbit(EDGE, *it);
untereiner's avatar
untereiner committed
541
542
543
544
545
546
		}
	}

	return count;
}

547
548
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
549
	DartMarkerStore mv(*this);	// Lock a marker
550

untereiner's avatar
untereiner committed
551
552
553
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
554
555
	mv.mark(d);

556
	for(unsigned int i = 0; i < darts.size(); ++i)
557
	{
558
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
559
			return true ;
560
561

		//add phi21 and phi23 successor if they are not marked yet
562
		Dart d2 = phi2(darts[i]);
563
564
565
566
567
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
568
			darts.push_back(d21);
569
570
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
571
		if(!mv.isMarked(d23))
572
		{
untereiner's avatar
untereiner committed
573
			darts.push_back(d23);
574
575
576
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
577
	return false ;
578
579
580
581
}

bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
582
	Dart it = d;
583
584
	do
	{
untereiner's avatar
untereiner committed
585
		if(it == e)
586
			return true;
untereiner's avatar
untereiner committed
587
588
		it = alpha2(it);
	} while (it != d);
589
590
591
	return false;
}

untereiner's avatar
untereiner committed
592
unsigned int Map3::edgeDegree(Dart d)
593
{
untereiner's avatar
untereiner committed
594
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
595
	Dart it = d;
596
597
	do
	{
untereiner's avatar
untereiner committed
598
599
600
		++deg;
		it = alpha2(it);
	} while(it != d);
601
602
603
	return deg;
}

untereiner's avatar
untereiner committed
604
bool Map3::isBoundaryEdge(Dart d)
605
{
untereiner's avatar
untereiner committed
606
607
608
609
610
611
612
613
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
614
615
}

untereiner's avatar
untereiner committed
616
Dart Map3::findBoundaryFaceOfEdge(Dart d)
617
{
untereiner's avatar
untereiner committed
618
619
620
621
622
623
624
625
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
626
627
}

Pierre Kraemer's avatar
Pierre Kraemer committed
628
629
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
630
	DartMarkerStore mark(*this);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
631
632

	std::vector<Dart> visitedFaces ;
untereiner's avatar
untereiner committed
633
	visitedFaces.reserve(128) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
634
	visitedFaces.push_back(d) ;
untereiner's avatar
untereiner committed
635
	mark.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
636

637
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
638
	{
639
		if (isBoundaryMarked(phi3(visitedFaces[i])))
untereiner's avatar
untereiner committed
640
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
641

642
		Dart e = visitedFaces[i] ;
untereiner's avatar
untereiner committed
643
		do	// add all face neighbours to the table
Pierre Kraemer's avatar
Pierre Kraemer committed
644
		{
untereiner's avatar
untereiner committed
645
646
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
Pierre Kraemer's avatar
Pierre Kraemer committed
647
			{
untereiner's avatar
untereiner committed
648
649
650
651
				visitedFaces.push_back(ee) ;
				mark.markOrbit(ORIENTED_FACE, ee) ;
			}
			e = phi1(e) ;
652
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
653
	}
untereiner's avatar
untereiner committed
654
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
655
656
}

657
bool Map3::check()
658
{
659
660
661
662
663
664
665
666
667
668
    std::cout << "Check: topology begin" << std::endl;
    DartMarker m(*this);
    for(Dart d = Map3::begin(); d != Map3::end(); Map3::next(d))
    {
        Dart d3 = phi3(d);
        if (phi3(d3) != d) // phi3 involution ?
		{
            std::cout << "Check: phi3 is not an involution" << std::endl;
            return false;
        }
669

untereiner's avatar
untereiner committed
670
671
672
673
674
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
			return false;
		}
675

676
677
678
679
680
681
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
682

683
684
685
686
687
688
        Dart d1 = phi1(d);
        if (phi_1(d1) != d) // phi1 a une image correcte ?
		{
            std::cout << "Check: unconsistent phi_1 link" << std::endl;
            return false;
        }
689

690
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
691
		{
692
693
694
695
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
696

697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
        if (d1 == d)
            std::cout << "Check: (warning) face loop (one edge)" << std::endl;

        if (phi1(d1) == d)
            std::cout << "Check: (warning) face with only two edges" << std::endl;

        if (phi2(d1) == d)
            std::cout << "Check: (warning) dandling edge (phi2)" << std::endl;

        if (phi3(d1) == d)
            std::cout << "Check: (warning) dandling edge (phi3)" << std::endl;
    }

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

719
    std::cout << "Check: topology ok" << std::endl;
720

721
    return true;
722
723
}

Pierre Kraemer's avatar
Pierre Kraemer committed
724
725
726
727
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
728
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
729
{
untereiner's avatar
untereiner committed
730
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
731
732
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
733
734
735
	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
736
737
	mv.mark(d);

738
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
739
	{
740
		// add phi21 and phi23 successor if they are not marked yet
741
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
742
743
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
744

untereiner's avatar
untereiner committed
745
746
747
748
749
750
751
752
753
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
Pierre Kraemer's avatar
Pierre Kraemer committed
754
755
		}

756
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
757
758
759
760
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
761
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
762
{
untereiner's avatar
untereiner committed
763
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
764
765
	do
	{
untereiner's avatar
untereiner committed
766
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
767
			return true;
untereiner's avatar
untereiner committed
768
769
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
770
771
772
	return false;
}

untereiner's avatar
untereiner committed
773
bool Map3::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
774
{
Sylvain Thery's avatar
Sylvain Thery committed
775
	DartMarkerStore mv(*this,thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
776
777
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
778
779
780
	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
781
782
	mv.mark(d);

783
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
784
	{
untereiner's avatar
untereiner committed
785
		// add all successors if they are not marked yet
786
787
788
		Dart d2 = phi1(darts[i]); // turn in face
		Dart d3 = phi2(darts[i]); // change face
		Dart d4 = phi3(darts[i]); // change volume
Pierre Kraemer's avatar
Pierre Kraemer committed
789

untereiner's avatar
untereiner committed
790
791
792
793
794
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
795
796
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
797
798
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
799
800
801
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
802
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
803
804
805
			mv.mark(d4);
		}

806
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
807
808
809
810
	}
	return found;
}

untereiner's avatar
untereiner committed
811
812
813
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
814

untereiner's avatar
untereiner committed
815
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
816
{
untereiner's avatar
untereiner committed
817
	assert(phi3(d) == d);		// Nothing to close
818
	DartMarkerStore m(*this) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
819

untereiner's avatar
untereiner committed
820
821
822
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
823
	m.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
824

untereiner's avatar
untereiner committed
825
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
826

untereiner's avatar
untereiner committed
827
	// For every face added to the list
828
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
829
	{
830
831
832
		Dart it = visitedFaces[i] ;
		Dart f = it ;

untereiner's avatar
untereiner committed
833
834
835
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
836

untereiner's avatar
untereiner committed
837
838
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
839
		{
untereiner's avatar
untereiner committed
840
841
842
843
844
845
846
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
				if(phi3(e) == e)
				{
					found = true ;
847
848
849
850
851
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
						m.markOrbit(ORIENTED_FACE, e) ;
					}
untereiner's avatar
untereiner committed
852
				}
853
				else if(isBoundaryMarked(e))
untereiner's avatar
untereiner committed
854
855
				{
					found = true ;
856
					phi2sew(e, bit) ;
untereiner's avatar
untereiner committed
857
858
859
860
861
862
863
864
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
865
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
866
867
	}

untereiner's avatar
untereiner committed
868
869
870
871
872
873
874
875
876
877
878
	return count ;
}

void Map3::closeMap()
{
	// Search the map for topological holes (fix points of phi3)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi3(d) == d)
			closeHole(d);
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
879
880
881
}

} // namespace CGoGN