Création d'un compte pour un collaborateur extérieur au laboratoire depuis l'intranet ICube : https://intranet.icube.unistra.fr/fr/labs/member/profile

map3.cpp 19.5 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

90
91
92
//	mark.markOrbit(ORIENTED_FACE, d) ;
	mark.markOrbit(FACE2, d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
93

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

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

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

untereiner's avatar
untereiner committed
114
115
116
	Dart dd = phi3(d) ;
	Map2::deleteCC(d) ;
	Map2::deleteCC(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
117
118
}

119
120
void Map3::fillHole(Dart d)
{
121
122
123
124
125
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi3(dd) ;
	boundaryUnmarkOrbit(VOLUME, dd) ;
126
127
}

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

132
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
133
{
134
135
136
	if(isBoundaryVertex(d))
		return NIL ;

Pierre Kraemer's avatar
Pierre Kraemer committed
137
138
	// Save the darts around the vertex
	// (one dart per face should be enough)
untereiner's avatar
untereiner committed
139
	std::vector<Dart> fstoretmp;
140
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
141
142
143
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

144
	 // just one dart per face
untereiner's avatar
untereiner committed
145
	std::vector<Dart> fstore;
146
	fstore.reserve(128);
untereiner's avatar
untereiner committed
147
	DartMarker mf(*this);
148
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
149
	{
150
		if(!mf.isMarked(fstoretmp[i]))
151
		{
152
153
			mf.markOrbit(FACE, fstoretmp[i]);
			fstore.push_back(fstoretmp[i]);
untereiner's avatar
untereiner committed
154
		}
155
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
156

157
	Dart res = NIL ;
untereiner's avatar
untereiner committed
158
159
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
160
161
162
163
164
165
166
167
		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) ;
168

169
170
			if(res == NIL)
				res = d2 ;
171

172
173
174
175
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
176
177

			fit = phi1(fit) ;
178
		}
untereiner's avatar
untereiner committed
179
	}
180

181
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
182

183
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
184
185
}

David Cazier's avatar
David Cazier committed
186
Dart Map3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
187
188
189
{
	Dart prev = d;
	Dart dd = alpha2(d);
David Cazier's avatar
David Cazier committed
190
	Dart nd = Map2::cutEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
191

192
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
193
194
195
196
197
198
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

199
200
201
202
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
203
204
	}

205
206
207
208
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
209

David Cazier's avatar
David Cazier committed
210
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
211
212
}

Pierre Kraemer's avatar
Pierre Kraemer committed
213
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
214
{
Pierre Kraemer's avatar
Pierre Kraemer committed
215
216
	if(vertexDegree(phi1(d)) == 2)
	{
217
218
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
219

220
221
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
222
223
224
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
225

226
227
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
228
229
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
230
231
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
232
		return true;
untereiner's avatar
untereiner committed
233
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
234
	return false;
untereiner's avatar
untereiner committed
235
236
}

untereiner's avatar
untereiner committed
237
238
239
240
241
242
Dart Map3::deleteEdge(Dart d)
{
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
243
244
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
245
	{
246
247
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
248
249
250
251
252
253
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
254

untereiner's avatar
untereiner committed
255
256
			if(res == NIL)
				res = d2 ;
257

untereiner's avatar
untereiner committed
258
259
260
261
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
262
263

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
264
		}
265
266
267
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
268
269
270
271
272
273
274
275
276
	Map2::deleteCC(d) ;

	return res ;
}

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

277
	Dart dit = d;
untereiner's avatar
untereiner committed
278
279
280

	do
	{
281
282
		Dart e = dit;
		dit = alpha2(dit);
untereiner's avatar
untereiner committed
283

284
285
286
		//test si un seul polyedre autour de l'arete
		if(e == dit)
			resV == phi3(phi2(phi1(e)));
untereiner's avatar
untereiner committed
287

288
		if(delDegenerateVolumes)
untereiner's avatar
untereiner committed
289
		{
290
			Map2::collapseEdge(e, true);
291
			collapseDegeneretedVolume(e);
292
293
294
		}
		else
			Map2::collapseEdge(e, false);
untereiner's avatar
untereiner committed
295

296
297
		if(resV == NIL)
		{
untereiner's avatar
untereiner committed
298

299
		}
untereiner's avatar
untereiner committed
300

301
302
	}while(d != dit);

303
304
	return resV;
}
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356



//	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
357

358
359
360
361
362
bool Map3::collapseDegeneratedFace(Dart d)
{
	Dart d3 = phi3(d);

	Map3::unsewVolumes(d);
363

364
365
366
367
368
369
	std::cout << Map2::collapseDegeneratedFace(d) << std::endl;
	std::cout << Map2::collapseDegeneratedFace(d3) << std::endl;
	std::cout << std::endl;

	return true;
}
untereiner's avatar
untereiner committed
370

371
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
372
{
untereiner's avatar
untereiner committed
373
	assert(d != e && sameOrientedFace(d, e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
374

375
376
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
377

untereiner's avatar
untereiner committed
378
	Map2::splitFace(d, e);
379
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
380

381
382
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
383
384
}

385
386
387
388
389
bool Map3::collapseDegeneretedVolume(Dart d)
{
	Dart e1 = phi2(d);
	Dart e2 = phi2(phi1(d));

390
391
	//Si les deux faces ne sont pas du bord
	if(!isBoundaryFace(e1) && !isBoundaryFace(e2))
392
	{
393
394
395
		sewVolumes(phi3(e1),phi3(e2));
		deleteVolume(d);
		return true;
396
397
398
	}
	else
	{
399
400
401
		//alors simple suppression du volume degenere
		deleteVolume(d);
		return true;
402
	}
403
404

	return false;
405
406
}

407
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
408
409
410
{
	assert(faceDegree(d) == faceDegree(e));

411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
	// 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) ;
		}
442
443
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
444
445
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
446
	} while(fitD != dd) ;
447
448
	Map2::deleteCC(dd) ;

449
450
	fitD = d ;
	fitE = e ;
451
452
	do
	{
453
		phi3sew(fitD, fitE) ;
454
455
456
457
458
459
460
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void Map3::unsewVolumes(Dart d)
{
untereiner's avatar
untereiner committed
461
462
463
464
465
466
467
468
469
470
471
472
	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 ;
473
474
	do
	{
untereiner's avatar
untereiner committed
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
		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) ;
495
496
497
498
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
499
	if(!Map3::isBoundaryFace(d))
500
	{
untereiner's avatar
untereiner committed
501
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
502
503
504
505
506
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
507
508
void Map3::splitVolume(std::vector<Dart>& vd)
{
509
	//assert(checkSimpleOrientedPath(vd)) ;
untereiner's avatar
untereiner committed
510

untereiner's avatar
untereiner committed
511
512
513
	Dart e = vd.front();
	Dart e2 = phi2(e);

514
515
516
517
518
519
//	//unsew the edge path
//	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
//		Map2::unsewFaces(*it);
//
//	Map2::fillHole(e) ;
//	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
520

521
	Map2::splitSurface(vd,true,true);
untereiner's avatar
untereiner committed
522

untereiner's avatar
untereiner committed
523
	//sew the two connected components
untereiner's avatar
untereiner committed
524
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
525
526
}

527
528
529
530
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

531
bool Map3::sameVertex(Dart d, Dart e)
532
533
534
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
535
536
537
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
538
539
	mv.mark(d);

540
	for(unsigned int i = 0; i < darts.size(); ++i)
541
	{
542
		if(darts[i] == e)
543
544
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
545
		// add phi21 and phi23 successor if they are not marked yet
546
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
547
548
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
549

untereiner's avatar
untereiner committed
550
551
552
553
554
555
556
557
558
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
559
560
561
562
563
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
564
565
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
566
	unsigned int count = 0;
untereiner's avatar
untereiner committed
567
568
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
569
570
571
	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
572
573
	mv.mark(d);

574
	for(unsigned int i = 0; i < darts.size(); ++i)
untereiner's avatar
untereiner committed
575
576
	{
		//add phi21 and phi23 successor if they are not marked yet
577
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
578
579
580
581
582
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
583
			darts.push_back(d21);
untereiner's avatar
untereiner committed
584
585
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
586
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
587
		{
untereiner's avatar
untereiner committed
588
			darts.push_back(d23);
untereiner's avatar
untereiner committed
589
590
591
592
593
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
untereiner's avatar
untereiner committed
594
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
595
	{
untereiner's avatar
untereiner committed
596
		if(!me.isMarked(*it))
untereiner's avatar
untereiner committed
597
598
		{
			++count;
untereiner's avatar
untereiner committed
599
			me.markOrbit(EDGE, *it);
untereiner's avatar
untereiner committed
600
601
602
603
604
605
		}
	}

	return count;
}

606
607
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
608
	DartMarkerStore mv(*this);	// Lock a marker
609

untereiner's avatar
untereiner committed
610
611
612
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
613
614
	mv.mark(d);

615
	for(unsigned int i = 0; i < darts.size(); ++i)
616
	{
617
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
618
			return true ;
619
620

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

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
627
			darts.push_back(d21);
628
629
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
630
		if(!mv.isMarked(d23))
631
		{
untereiner's avatar
untereiner committed
632
			darts.push_back(d23);
633
634
635
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
636
	return false ;
637
638
639
640
}

bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
641
	Dart it = d;
642
643
	do
	{
untereiner's avatar
untereiner committed
644
		if(it == e)
645
			return true;
untereiner's avatar
untereiner committed
646
647
		it = alpha2(it);
	} while (it != d);
648
649
650
	return false;
}

untereiner's avatar
untereiner committed
651
unsigned int Map3::edgeDegree(Dart d)
652
{
untereiner's avatar
untereiner committed
653
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
654
	Dart it = d;
655
656
	do
	{
untereiner's avatar
untereiner committed
657
658
659
		++deg;
		it = alpha2(it);
	} while(it != d);
660
661
662
	return deg;
}

untereiner's avatar
untereiner committed
663
bool Map3::isBoundaryEdge(Dart d)
664
{
untereiner's avatar
untereiner committed
665
666
667
668
669
670
671
672
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
673
674
}

untereiner's avatar
untereiner committed
675
Dart Map3::findBoundaryFaceOfEdge(Dart d)
676
{
untereiner's avatar
untereiner committed
677
678
679
680
681
682
683
684
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
685
686
}

Pierre Kraemer's avatar
Pierre Kraemer committed
687
688
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
689
690
	Traversor3WF<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
691
	{
untereiner's avatar
untereiner committed
692
		if(isBoundaryMarked(phi3(dit)))
untereiner's avatar
untereiner committed
693
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
694
	}
untereiner's avatar
untereiner committed
695
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
696
697
}

untereiner's avatar
untereiner committed
698
699
bool Map3::hasBoundaryEdge(Dart d)
{
untereiner's avatar
untereiner committed
700
701
	Traversor3WE<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
untereiner's avatar
untereiner committed
702
	{
untereiner's avatar
untereiner committed
703
704
		if(isBoundaryEdge(dit))
			return true;
untereiner's avatar
untereiner committed
705
	}
untereiner's avatar
untereiner committed
706

untereiner's avatar
untereiner committed
707
708
709
	return false;
}

710
bool Map3::check()
711
{
712
713
714
715
716
717
718
719
720
721
    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;
        }
722

untereiner's avatar
untereiner committed
723
724
725
726
727
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
			return false;
		}
728

729
730
731
732
733
734
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
735

736
737
738
739
740
741
        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;
        }
742

743
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
744
		{
745
746
747
748
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
749

750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
        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 ?
766
		{
767
768
769
770
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
771

772
    std::cout << "Check: topology ok" << std::endl;
773

774
    return true;
775
776
}

Pierre Kraemer's avatar
Pierre Kraemer committed
777
778
779
780
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
781
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
782
{
untereiner's avatar
untereiner committed
783
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
784
785
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
786
787
788
	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
789
790
	mv.mark(d);

791
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
792
	{
793
		// add phi21 and phi23 successor if they are not marked yet
794
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
795
796
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
797

untereiner's avatar
untereiner committed
798
799
800
801
802
803
804
805
806
		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
807
808
		}

809
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
810
811
812
813
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
814
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
815
{
untereiner's avatar
untereiner committed
816
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
817
818
	do
	{
untereiner's avatar
untereiner committed
819
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
820
			return true;
untereiner's avatar
untereiner committed
821
822
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
823
824
825
	return false;
}

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

untereiner's avatar
untereiner committed
831
832
833
	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
834
835
	mv.mark(d);

836
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
837
	{
untereiner's avatar
untereiner committed
838
		// add all successors if they are not marked yet
839
840
841
		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
842

untereiner's avatar
untereiner committed
843
844
845
846
847
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
848
849
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
850
851
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
852
853
854
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
855
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
856
857
858
			mv.mark(d4);
		}

859
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
860
861
862
863
	}
	return found;
}

untereiner's avatar
untereiner committed
864
865
866
/*! @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
867

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

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

untereiner's avatar
untereiner committed
879
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
880

untereiner's avatar
untereiner committed
881
	// For every face added to the list
882
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
883
	{
884
885
886
		Dart it = visitedFaces[i] ;
		Dart f = it ;

untereiner's avatar
untereiner committed
887
888
889
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
890

untereiner's avatar
untereiner committed
891
892
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
893
		{
untereiner's avatar
untereiner committed
894
895
896
897
898
899
900
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
				if(phi3(e) == e)
				{
					found = true ;
901
902
903
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
904
						m.markOrbit(FACE2, e) ;
905
					}
untereiner's avatar
untereiner committed
906
				}
907
				else if(isBoundaryMarked(e))
untereiner's avatar
untereiner committed
908
909
				{
					found = true ;
910
					phi2sew(e, bit) ;
untereiner's avatar
untereiner committed
911
912
913
914
915
916
917
918
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
919
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
920
921
	}

untereiner's avatar
untereiner committed
922
923
924
	return count ;
}

925
unsigned int Map3::closeMap()
untereiner's avatar
untereiner committed
926
927
{
	// Search the map for topological holes (fix points of phi3)
928
	unsigned int nb = 0 ;
untereiner's avatar
untereiner committed
929
930
931
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi3(d) == d)
932
933
		{
			++nb ;
untereiner's avatar
untereiner committed
934
			closeHole(d);
935
		}
untereiner's avatar
untereiner committed
936
	}
937
	return nb ;
Pierre Kraemer's avatar
Pierre Kraemer committed
938
939
940
}

} // namespace CGoGN