map3.cpp 25.6 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-2012, 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.unistra.fr/                                           *
Pierre Kraemer's avatar
Pierre Kraemer committed
21
22
23
24
25
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/map3.h"
untereiner's avatar
untereiner committed
26
#include "Topology/generic/traversor3.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
27
28
29
30

namespace CGoGN
{

Pierre Kraemer's avatar
merges    
Pierre Kraemer committed
31
32
33
34
void Map3::compactTopoRelations(const std::vector<unsigned int>& oldnew)
{
	for (unsigned int i = m_attribs[DART].begin(); i != m_attribs[DART].end(); m_attribs[DART].next(i))
	{
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
		unsigned int d_index = dartIndex(m_phi1->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi1->operator[](i) = Dart(oldnew[d_index]);

		d_index = dartIndex(m_phi_1->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi_1->operator[](i) = Dart(oldnew[d_index]);

		d_index = dartIndex(m_phi2->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi2->operator[](i) = Dart(oldnew[d_index]);

		d_index = dartIndex(m_phi3->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi3->operator[](i) = Dart(oldnew[d_index]);
//
//		{
//			Dart& d = m_phi1->operator [](i);
//			Dart e = Dart(oldnew[d.index]);
//			if (d != e)
//				d = e;
//		}
//		{
//			Dart& d = m_phi_1->operator [](i);
//			Dart e = Dart(oldnew[d.index]);
//			if (d != e)
//				d = e;
//		}
//		{
//			Dart& d = m_phi2->operator [](i);
//			Dart e = Dart(oldnew[d.index]);
//			if (d != e)
//				d = e;
//		}
//		{
//			Dart& d = m_phi3->operator [](i);
//			Dart e = Dart(oldnew[d.index]);
//			if (d != e)
//				d = e;
//		}
Pierre Kraemer's avatar
merges    
Pierre Kraemer committed
75
76
77
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
78
79
80
/*! @name Generator and Deletor
 *  To generate or delete volumes in a 3-map
 *************************************************************************/
81
82

void Map3::deleteVolume(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
83
84
85
86
{
	DartMarkerStore mark(*this);		// Lock a marker

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

Pierre Kraemer's avatar
Pierre Kraemer committed
90
	mark.markOrbit<FACE2>(d) ;
91

Pierre Kraemer's avatar
Pierre Kraemer committed
92

93
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
94
	{
95
		Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
96

97
98
		if(!isBoundaryFace(e))
			unsewVolumes(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
99
100
101
102
103
104
105

		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
106
				mark.markOrbit<FACE2>(ee) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
107
108
			}
			e = phi1(e) ;
109
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
110
111
	}

untereiner's avatar
untereiner committed
112
	Dart dd = phi3(d) ;
113
114
	Map2::deleteCC(d) ; //deleting the volume
	Map2::deleteCC(dd) ; //deleting its border (created from the unsew operation)
Pierre Kraemer's avatar
Pierre Kraemer committed
115
116
}

117
118
void Map3::fillHole(Dart d)
{
119
120
121
122
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi3(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
123
	boundaryUnmarkOrbit<VOLUME>(dd) ;
124
125
}

Pierre Kraemer's avatar
Pierre Kraemer committed
126
127
128
129
/*! @name Topological Operators
 *  Topological operations on 3-maps
 *************************************************************************/

untereiner's avatar
untereiner committed
130
Dart Map3::splitVertex(std::vector<Dart>& vd)
untereiner's avatar
untereiner committed
131
{
132
	//assert(checkPathAroundVertex(vd)) ;
untereiner's avatar
untereiner committed
133

134
	bool boundE = false;
untereiner's avatar
untereiner committed
135
136

	Dart prev = vd.front();	//elt 0
137
138

	Dart db1 = NIL;
139
	if(isBoundaryFace(phi2(prev)))
140
141
142
143
	{
		db1 = phi2(phi3(phi1(phi2(prev))));
	}

untereiner's avatar
untereiner committed
144
145
146
147
148
149
150
151
152
153
154
155
	Dart fs = phi_1(phi2(phi_1(prev)));	//first side

	Map2::splitVertex(prev, phi2(fs));

	for(unsigned int i = 1; i < vd.size(); ++i)
	{
		prev = vd[i];

		Dart fs = phi_1(phi2(phi_1(prev)));	//first side

		Map2::splitVertex(prev, phi2(fs));

156
157
		Dart d1 = phi_1(phi2(phi_1(vd[i-1])));
		Dart d2 = phi1(phi2(vd[i]));
untereiner's avatar
untereiner committed
158

159
		phi3sew(d1, d2);
untereiner's avatar
untereiner committed
160
161
	}

162
163
	Dart db2 = NIL;
	if(isBoundaryFace(phi2(phi_1(prev))))
Lionel Untereiner's avatar
Lionel Untereiner committed
164
	{
165
		db2 = phi2(phi3(phi2(phi_1(prev))));
Lionel Untereiner's avatar
Lionel Untereiner committed
166
167
	}

168
169
170
171
172
173
	if(db1 != NIL && db2 != NIL)
	{
		Map2::splitVertex(db1, db2);
		phi3sew(phi1(phi2(db2)), phi_1(phi3(phi2(db2))));
		phi3sew(phi1(phi2(db1)), phi_1(phi3(phi2(db1))));
	}
174
	else
175
176
177
178
179
	{
		Dart dbegin = phi1(phi2(vd.front()));
		Dart dend = phi_1(phi2(phi_1(vd.back())));
		phi3sew(dbegin, dend);
	}
Lionel Untereiner's avatar
Lionel Untereiner committed
180

untereiner's avatar
untereiner committed
181
182
183
184
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
	return phi_1(phi2(phi_1(prev)));
}

//	//unsew the face path
//	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
//	{
//		Dart dit = *it;
//
//		Map1::cutEdge(phi_1(phi2(phi_1(dit)))); //comme un vertexSplit
//		Map1::cutEdge(phi2(phi1(phi2(dit))));
//		Map2::sewFaces(phi1(phi2(phi1(phi2(dit)))), phi_1(phi2(phi_1(dit))), false);
//
//
//
//		Dart dit3 = phi3(dit);
//		unsewVolumes(dit);

//		Dart f1 = newFace(3,false);
//		Dart f2 = newFace(3,false);
//		Dart f3 = newFace(3,false);
//		Dart f4 = newFace(3,false);
//
//		sewFaces(f1,f2,false);
//		sewFaces(phi_1(f1), f3, false);
//		sewFaces(phi1(f1), f4, false);
//		sewFaces(phi_1(f2), phi1(f4), false);
//		sewFaces(phi_1(f3), phi1(f2), false);
//		sewFaces(phi1(f3), phi_1(f4), false);
//
//		sewVolumes(dit,f3);
//		sewVolumes(dit3,f4);
//	}

Lionel Untereiner's avatar
Lionel Untereiner committed
214
/*
untereiner's avatar
untereiner committed
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
	if(isBoundaryVertex(d))
	{
		unsewVolumes(d);
		unsewVolumes(e);

		Dart dc = phi1(phi2(d));

		//unsewVolumes(phi2(dc));
		Map2::splitVertex(d, phi1(phi2(dc)));


//		Map2::splitFace(d, phi2(dc));

//		Dart ec = phi_1(phi2(e));
//		Map2::splitVertex(e, ec);
//		//Map2::splitFace(e, phi2(ec));
	}
Lionel Untereiner's avatar
Lionel Untereiner committed
232
*/
untereiner's avatar
untereiner committed
233

untereiner's avatar
untereiner committed
234

235
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
236
{
237
238
239
	if(isBoundaryVertex(d))
		return NIL ;

Pierre Kraemer's avatar
Pierre Kraemer committed
240
241
	// Save the darts around the vertex
	// (one dart per face should be enough)
untereiner's avatar
untereiner committed
242
	std::vector<Dart> fstoretmp;
243
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
244
245
246
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

247
	 // just one dart per face
untereiner's avatar
untereiner committed
248
	std::vector<Dart> fstore;
249
	fstore.reserve(128);
untereiner's avatar
untereiner committed
250
	DartMarker mf(*this);
251
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
252
	{
253
		if(!mf.isMarked(fstoretmp[i]))
254
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
255
			mf.markOrbit<FACE>(fstoretmp[i]);
256
			fstore.push_back(fstoretmp[i]);
untereiner's avatar
untereiner committed
257
		}
258
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
259

260
	Dart res = NIL ;
untereiner's avatar
untereiner committed
261
262
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
263
264
265
266
267
268
269
270
		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) ;
271

272
273
			if(res == NIL)
				res = d2 ;
274

275
276
277
278
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
279
280

			fit = phi1(fit) ;
281
		}
untereiner's avatar
untereiner committed
282
	}
283

284
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
285

286
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
287
288
}

David Cazier's avatar
David Cazier committed
289
Dart Map3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
290
291
292
{
	Dart prev = d;
	Dart dd = alpha2(d);
David Cazier's avatar
David Cazier committed
293
	Dart nd = Map2::cutEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
294

295
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
296
297
298
299
300
301
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

302
303
304
305
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
306
307
	}

308
309
310
311
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
312

David Cazier's avatar
David Cazier committed
313
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
314
315
}

Pierre Kraemer's avatar
Pierre Kraemer committed
316
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
317
{
Pierre Kraemer's avatar
Pierre Kraemer committed
318
319
	if(vertexDegree(phi1(d)) == 2)
	{
320
321
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
322

323
324
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
325
326
327
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
328

329
330
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
331
332
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
333
334
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
335
		return true;
untereiner's avatar
untereiner committed
336
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
337
	return false;
untereiner's avatar
untereiner committed
338
339
}

Sylvain Thery's avatar
Sylvain Thery committed
340
341
342
343
344
345
346
bool Map3::deleteEdgePreCond(Dart d)
{
	unsigned int nb1 = vertexDegree(d);
	unsigned int nb2 = vertexDegree(phi1(d));
	return (nb1!=2) && (nb2!=2);
}

untereiner's avatar
untereiner committed
347
348
Dart Map3::deleteEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
349
350
	assert(deleteEdgePreCond(d));

untereiner's avatar
untereiner committed
351
352
353
354
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
355
356
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
357
	{
358
359
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
360
361
362
363
364
365
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
366

untereiner's avatar
untereiner committed
367
368
			if(res == NIL)
				res = d2 ;
369

untereiner's avatar
untereiner committed
370
371
372
373
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
374
375

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
376
		}
377
378
379
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
380
381
382
383
384
	Map2::deleteCC(d) ;

	return res ;
}

Sylvain Thery's avatar
Sylvain Thery committed
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
//Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
//{
//	Dart resV = NIL;
//
//	Dart dit = d;
//
//	do
//	{
//		Dart e = dit;
//		dit = alpha2(dit);
//
//		//test si un seul polyedre autour de l'arete
//		if(e == dit)
//			resV == phi3(phi2(phi1(e)));
//
//		if(delDegenerateVolumes)
//		{
//			Map2::collapseEdge(e, true);
//			collapseDegeneretedVolume(e);
//		}
//		else
//			Map2::collapseEdge(e, false);
//
//		if(resV == NIL)
//		{
//
//		}
//
//	}while(d != dit);
//
//	return resV;
//}

untereiner's avatar
untereiner committed
418
419
420
Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
421
	Dart dit = d;
untereiner's avatar
untereiner committed
422

Sylvain Thery's avatar
Sylvain Thery committed
423
	std::vector<Dart> darts;
untereiner's avatar
untereiner committed
424
425
	do
	{
Sylvain Thery's avatar
Sylvain Thery committed
426
		darts.push_back(dit);
427
		dit = alpha2(dit);
Sylvain Thery's avatar
Sylvain Thery committed
428
	}while(dit != d);
untereiner's avatar
untereiner committed
429

Sylvain Thery's avatar
Sylvain Thery committed
430
431
432
	for (std::vector<Dart>::iterator it = darts.begin(); it != darts.end(); ++it)
	{
		Dart x = phi2(phi_1(*it));
433
434
435
436
437
438
439
440

		Dart resCV = NIL;

		if(!isBoundaryFace(phi2(phi1(*it))))
			resCV = phi3(phi2(phi1(*it)));
		else if(!isBoundaryFace(phi2(phi_1(*it))))
			resCV = phi3(phi2(phi_1(*it)));

Sylvain Thery's avatar
Sylvain Thery committed
441
442
		resV = Map2::collapseEdge(*it, true);
		if (delDegenerateVolumes)
443
444
			if(collapseDegeneretedVolume(x) && resCV != NIL)
				resV = resCV;
Sylvain Thery's avatar
Sylvain Thery committed
445
	}
446

447
448
	return resV;
}
449
450
451



Sylvain Thery's avatar
Sylvain Thery committed
452

453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
//	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
502

Sylvain Thery's avatar
Sylvain Thery committed
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
//bool Map3::collapseDegeneratedFace(Dart d)
//{
//	Dart d3 = phi3(d);
//
//	std::cout << "Map3::collapseDegeneratedFace"<< std::endl;
//
//	if (!isDartValid(d))
//		Map2::collapseDegeneratedFace(d);
//	else
//		std::cout << "Warning Coll1 invalid"<< std::endl;
//
//
//	if (isDartValid(d3))
//		Map2::collapseDegeneratedFace(d3);
//	else
//		std::cout << "Warning coll2 invalid"<< std::endl;
//
//
//
///*
//	Map3::unsewVolumes(d);
//
//	std::cout << Map2::collapseDegeneratedFace(d) << std::endl;
//	std::cout << Map2::collapseDegeneratedFace(d3) << std::endl;
//	std::cout << std::endl;
//*/
//	return true;
//}

bool Map3::splitFacePreCond(Dart d, Dart e)
533
{
Sylvain Thery's avatar
Sylvain Thery committed
534
	return (d != e && sameOrientedFace(d, e)) ;
535
}
untereiner's avatar
untereiner committed
536

537
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
538
{
Sylvain Thery's avatar
Sylvain Thery committed
539
540
//	assert(d != e && sameOrientedFace(d, e)) ;
	assert(splitFacePreCond(d,e));
Pierre Kraemer's avatar
Pierre Kraemer committed
541

542
543
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
544

untereiner's avatar
untereiner committed
545
	Map2::splitFace(d, e);
546
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
547

548
549
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
550
551
}

Thomas's avatar
Thomas committed
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
bool Map3::mergeFaces(Dart d)
{
	assert(edgeDegree(d)==2);

	Dart dd = phi3(d);

	phi3unsew(d);
	phi3unsew(dd);

	//use code of mergesFaces to override the if(isBoundaryEdge)
	//we have to merge the faces if the face is linked to a border also
//	Map2::mergeFaces(d);
	Dart e = phi2(d) ;
	phi2unsew(d) ;
	Map1::mergeCycles(d, phi1(e)) ;
	Map1::splitCycle(e, phi1(d)) ;
	Map1::deleteCycle(d) ;
//	Map2::mergeFaces(dd);
	e = phi2(dd) ;
	phi2unsew(dd) ;
	Map1::mergeCycles(dd, phi1(e)) ;
	Map1::splitCycle(e, phi1(dd)) ;
	Map1::deleteCycle(dd);

	return true;
}

579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
Dart Map3::collapseFace(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
	Dart stop = phi_1(d);
	Dart dit = d;
	std::vector<Dart> vd;
	vd.reserve(32);

	do
	{
		vd.push_back(alpha2(dit));
		dit = phi1(dit);
	}
	while(dit != stop);

	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
		resV = Map3::collapseEdge(*it, delDegenerateVolumes);

	return resV;
}

Sylvain Thery's avatar
Sylvain Thery committed
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
//bool Map3::collapseDegeneretedVolume(Dart d)
//{
//	Dart e1 = phi2(d);
//	Dart e2 = phi2(phi1(d));
//
//	//Si les deux faces ne sont pas du bord
//	if(!isBoundaryFace(e1) && !isBoundaryFace(e2))
//	{
//		sewVolumes(phi3(e1),phi3(e2));
//		deleteVolume(d);
//		return true;
//	}
//	else
//	{
//		//alors simple suppression du volume degenere
//		deleteVolume(d);
//		return true;
//	}
//
//	return false;
//}

622
623
bool Map3::collapseDegeneretedVolume(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
624
625
	Dart e1 = d;
	Dart e2 = phi2(d);
626

Sylvain Thery's avatar
Sylvain Thery committed
627
	do
628
	{
Sylvain Thery's avatar
Sylvain Thery committed
629
630
631
632
633
634
635
636
637
638
639
		if (e1 != phi2(e2))
			return false;
		e1 = phi1(e1);
		e2 = phi_1(e2);
	}while (e1 != d);

	if (e2 != phi2(d))
		return false;

	// degenerated:
	do
640
	{
Sylvain Thery's avatar
Sylvain Thery committed
641
642
643
644
645
646
647
648
		Dart f1 = phi3(e1);
		Dart f2 = phi3(e2);
		phi3unsew(e1);
		phi3unsew(e2);
		phi3sew(f1,f2);
		e1 = phi1(e1);
		e2 = phi_1(e2);
	}while (e1 != d);
649

Sylvain Thery's avatar
Sylvain Thery committed
650
651
652
653
654
655
656
657
	Map2::deleteCC(d) ;
	return true;
}


bool Map3::sewVolumesPreCond(Dart d, Dart e)
{
	return (faceDegree(d) == faceDegree(e));
658
659
}

660
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
661
{
Sylvain Thery's avatar
Sylvain Thery committed
662
	assert(sewVolumesPreCond(d,e));
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
	// 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) ;
		}
695
696
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
697
698
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
699
	} while(fitD != dd) ;
700
701
	Map2::deleteCC(dd) ;

702
703
	fitD = d ;
	fitE = e ;
704
705
	do
	{
706
		phi3sew(fitD, fitE) ;
707
708
709
710
711
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

Sylvain Thery's avatar
Sylvain Thery committed
712
713
714
715
716
717
bool Map3::unsewVolumesPreCond(Dart d)
{
	return (!isBoundaryFace(d)) ;
}


718
719
void Map3::unsewVolumes(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
720
	assert(unsewVolumesPreCond(d)) ;
untereiner's avatar
untereiner committed
721
722
723
724
725
726
727
728
729
730
731

	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 ;
732
733
	do
	{
untereiner's avatar
untereiner committed
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
		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) ;
754
755
756
757
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
758
	if(!Map3::isBoundaryFace(d))
759
	{
untereiner's avatar
untereiner committed
760
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
761
762
763
764
765
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
766
767
void Map3::splitVolume(std::vector<Dart>& vd)
{
768
	//assert(checkSimpleOrientedPath(vd)) ;
untereiner's avatar
untereiner committed
769

untereiner's avatar
untereiner committed
770
771
772
	Dart e = vd.front();
	Dart e2 = phi2(e);

773
	Map2::splitSurface(vd,true,true);
untereiner's avatar
untereiner committed
774

untereiner's avatar
untereiner committed
775
	//sew the two connected components
untereiner's avatar
untereiner committed
776
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
777
778
}

779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
Dart Map3::collapseVolume(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
	std::vector<Dart> vd;
	vd.reserve(32);

	vd.push_back(d);
	vd.push_back(alpha2(phi1(d)));
	vd.push_back(alpha2(phi_1(phi2(phi1(d)))));

//	Traversor3WF<Map3> tra(*this, phi1(d));
//	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
//	{
//		vd.push_back(alpha2(dit));
//	}
//	vd.pop_back();

	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
		resV = Map3::collapseEdge(*it, delDegenerateVolumes);

	return resV;
}

802
803
804
805
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

806
bool Map3::sameVertex(Dart d, Dart e)
807
808
809
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
810
811
812
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
813
814
	mv.mark(d);

815
	for(unsigned int i = 0; i < darts.size(); ++i)
816
	{
817
		if(darts[i] == e)
818
819
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
820
		// add phi21 and phi23 successor if they are not marked yet
821
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
822
823
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
824

untereiner's avatar
untereiner committed
825
826
827
828
829
830
831
832
833
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
834
835
836
837
838
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
839
840
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
841
	unsigned int count = 0;
untereiner's avatar
untereiner committed
842
843
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
844
845
846
	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
847
848
	mv.mark(d);

849
	for(unsigned int i = 0; i < darts.size(); ++i)
untereiner's avatar
untereiner committed
850
851
	{
		//add phi21 and phi23 successor if they are not marked yet
852
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
853
854
855
856
857
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
858
			darts.push_back(d21);
untereiner's avatar
untereiner committed
859
860
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
861
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
862
		{
untereiner's avatar
untereiner committed
863
			darts.push_back(d23);
untereiner's avatar
untereiner committed
864
865
866
867
868
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
untereiner's avatar
untereiner committed
869
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
870
	{
untereiner's avatar
untereiner committed
871
		if(!me.isMarked(*it))
untereiner's avatar
untereiner committed
872
873
		{
			++count;
Pierre Kraemer's avatar
Pierre Kraemer committed
874
			me.markOrbit<EDGE>(*it);
untereiner's avatar
untereiner committed
875
876
877
878
879
880
		}
	}

	return count;
}

881
882
883
884
885
886
887
unsigned int Map3::vertexDegreeOnBoundary(Dart d)
{
	assert(Map3::isBoundaryVertex(d));

	return Map2::vertexDegree(d);
}

888
889
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
890
	DartMarkerStore mv(*this);	// Lock a marker
891

untereiner's avatar
untereiner committed
892
893
894
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
895
896
	mv.mark(d);

897
	for(unsigned int i = 0; i < darts.size(); ++i)
898
	{
899
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
900
			return true ;
901
902

		//add phi21 and phi23 successor if they are not marked yet
903
		Dart d2 = phi2(darts[i]);
904
905
906
907
908
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
909
			darts.push_back(d21);
910
911
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
912
		if(!mv.isMarked(d23))
913
		{
untereiner's avatar
untereiner committed
914
			darts.push_back(d23);
915
916
917
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
918
	return false ;
919
920
}

untereiner's avatar
untereiner committed
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
Dart Map3::findBoundaryFaceOfVertex(Dart d)
{
	DartMarkerStore mv(*this);	// Lock a marker

	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
	mv.mark(d);

	for(unsigned int i = 0; i < darts.size(); ++i)
	{
		if(isBoundaryMarked(darts[i]))
			return darts[i];

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

		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
		}
	}
	return NIL ;
}

954
955
bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
956
	Dart it = d;
957
958
	do
	{
untereiner's avatar
untereiner committed
959
		if(it == e)
960
			return true;
untereiner's avatar
untereiner committed
961
962
		it = alpha2(it);
	} while (it != d);
963
964
965
	return false;
}

untereiner's avatar
untereiner committed
966
unsigned int Map3::edgeDegree(Dart d)
967
{
untereiner's avatar
untereiner committed
968
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
969
	Dart it = d;
970
971
	do
	{
untereiner's avatar
untereiner committed
972
973
974
		++deg;
		it = alpha2(it);
	} while(it != d);
975
976
977
	return deg;
}

untereiner's avatar
untereiner committed
978
bool Map3::isBoundaryEdge(Dart d)
979
{
untereiner's avatar
untereiner committed
980
981
982
983
984
985
986
987
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
988
989
}

untereiner's avatar
untereiner committed
990
Dart Map3::findBoundaryFaceOfEdge(Dart d)
991
{
untereiner's avatar
untereiner committed
992
993
994
995
996
997
998
999
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
1000
1001
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1002
1003
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
1004
1005
	Traversor3WF<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
1006
	{
untereiner's avatar
untereiner committed
1007
		if(isBoundaryMarked(phi3(dit)))
untereiner's avatar
untereiner committed
1008
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1009
	}
untereiner's avatar
untereiner committed
1010
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
1011
1012
}

untereiner's avatar
untereiner committed
1013
1014
bool Map3::hasBoundaryEdge(Dart d)
{
untereiner's avatar
untereiner committed
1015
1016
	Traversor3WE<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
untereiner's avatar
untereiner committed
1017
	{
untereiner's avatar
untereiner committed
1018
1019
		if(isBoundaryEdge(dit))
			return true;
untereiner's avatar
untereiner committed
1020
	}
untereiner's avatar
untereiner committed
1021

untereiner's avatar
untereiner committed
1022
1023
1024
	return false;
}

1025
bool Map3::check()
1026
{
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
    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;
        }
1037

untereiner's avatar
untereiner committed
1038
1039
1040
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
1041
			//return false;
untereiner's avatar
untereiner committed
1042
		}
1043

1044
1045
1046
1047
1048
1049
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
1050

1051
1052
1053
1054
1055
1056
        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;
        }
1057

1058
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
1059
		{
1060
1061
1062
1063
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
1064

1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
        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 ?
1081
		{
1082
1083
1084
1085
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
1086

1087
    std::cout << "Check: topology ok" << std::endl;
1088

1089
    return true;
1090
1091
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1092
1093
1094
1095
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
1096
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
1097
{
untereiner's avatar
untereiner committed
1098
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
1099
1100
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
1101
1102
1103
	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
1104
1105
	mv.mark(d);

1106
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
1107
	{
1108
		// add phi21 and phi23 successor if they are not marked yet
1109
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
1110
1111
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
1112

untereiner's avatar
untereiner committed
1113
1114
1115
1116
1117
1118
1119
1120
1121
		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
1122
1123
		}

1124
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
1125
1126
1127
1128
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
1129
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
1130
{
untereiner's avatar
untereiner committed
1131
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
1132
1133
	do
	{
untereiner's avatar
untereiner committed
1134
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
1135
			return true;
untereiner's avatar
untereiner committed
1136
1137
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
1138
1139
1140
	return false;
}

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

untereiner's avatar
untereiner committed
1146
1147
1148
	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
1149
1150
	mv.mark(d);

1151
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
1152
	{
untereiner's avatar
untereiner committed
1153
		// add all successors if they are not marked yet
1154
1155
1156
		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
1157

untereiner's avatar
untereiner committed
1158
1159
1160
1161
1162
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
1163
1164
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
1165
1166
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
1167
1168
1169
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
1170
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
1171
1172
1173
			mv.mark(d4);
		}

1174
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
1175
1176
1177
1178
	}
	return found;
}

untereiner's avatar
untereiner committed
1179
1180
1181
/*! @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
1182

untereiner's avatar
untereiner committed
1183
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
1184
{
untereiner's avatar
untereiner committed
1185
	assert(phi3(d) == d);		// Nothing to close
1186
	DartMarkerStore m(*this) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1187

untereiner's avatar
untereiner committed
1188
1189
1190
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
Pierre Kraemer's avatar
Pierre Kraemer committed
1191
	m.markOrbit<FACE2>(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1192

untereiner's avatar
untereiner committed
1193
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1194

untereiner's avatar
untereiner committed
1195
	// For every face added to the list
1196
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
1197
	{
1198
1199
1200
		Dart it = visitedFaces[i] ;
		Dart f = it ;

untereiner's avatar
untereiner committed
1201
1202
1203
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1204

untereiner's avatar
untereiner committed
1205
1206
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
1207
		{
untereiner's avatar
untereiner committed
1208
1209
1210
1211
1212
1213
1214
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
				if(phi3(e) == e)
				{
					found = true ;
1215
1216
1217
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1218
						m.markOrbit<FACE2>(e) ;
1219
					}
untereiner's avatar
untereiner committed
1220
				}
1221
				else if(isBoundaryMarked(e))
untereiner's avatar
untereiner committed
1222
1223
				{
					found = true ;
1224
					phi2sew(e, bit) ;
untereiner's avatar
untereiner committed
1225
1226
1227
1228
1229
1230
1231
1232
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
1233
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1234
1235
	}

untereiner's avatar
untereiner committed
1236
1237
1238
	return count ;
}

1239
unsigned int Map3::closeMap()
untereiner's avatar
untereiner committed
1240
1241
{
	// Search the map for topological holes (fix points of phi3)
1242
	unsigned int nb = 0 ;
untereiner's avatar
untereiner committed
1243
1244
1245
	for (Dart d = begin(); d != end(); nex