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 21.3 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
}

Sylvain Thery's avatar
Sylvain Thery committed
237
238
239
240
241
242
243
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
244
245
Dart Map3::deleteEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
246
247
	assert(deleteEdgePreCond(d));

untereiner's avatar
untereiner committed
248
249
250
251
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
252
253
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
254
	{
255
256
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
257
258
259
260
261
262
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
263

untereiner's avatar
untereiner committed
264
265
			if(res == NIL)
				res = d2 ;
266

untereiner's avatar
untereiner committed
267
268
269
270
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
271
272

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
273
		}
274
275
276
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
277
278
279
280
281
	Map2::deleteCC(d) ;

	return res ;
}

Sylvain Thery's avatar
Sylvain Thery committed
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
//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
315
316
317
Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
318
	Dart dit = d;
untereiner's avatar
untereiner committed
319

Sylvain Thery's avatar
Sylvain Thery committed
320
	std::vector<Dart> darts;
untereiner's avatar
untereiner committed
321
322
	do
	{
Sylvain Thery's avatar
Sylvain Thery committed
323
		darts.push_back(dit);
324
		dit = alpha2(dit);
Sylvain Thery's avatar
Sylvain Thery committed
325
	}while(dit != d);
untereiner's avatar
untereiner committed
326

Sylvain Thery's avatar
Sylvain Thery committed
327
328
329
330
331
332
333
	for (std::vector<Dart>::iterator it = darts.begin(); it != darts.end(); ++it)
	{
		Dart x = phi2(phi_1(*it));
		resV = Map2::collapseEdge(*it, true);
		if (delDegenerateVolumes)
			collapseDegeneretedVolume(x);
	}
334

335
336
	return resV;
}
337
338
339



Sylvain Thery's avatar
Sylvain Thery committed
340

341
342
343
344
345
346
347
348
349
350
351
352
353
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
385
386
387
388
389
//	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
390

Sylvain Thery's avatar
Sylvain Thery committed
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
418
419
420
//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)
421
{
Sylvain Thery's avatar
Sylvain Thery committed
422
	return (d != e && sameOrientedFace(d, e)) ;
423
}
untereiner's avatar
untereiner committed
424

425
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
426
{
Sylvain Thery's avatar
Sylvain Thery committed
427
428
//	assert(d != e && sameOrientedFace(d, e)) ;
	assert(splitFacePreCond(d,e));
Pierre Kraemer's avatar
Pierre Kraemer committed
429

430
431
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
432

untereiner's avatar
untereiner committed
433
	Map2::splitFace(d, e);
434
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
435

436
437
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
438
439
}

Sylvain Thery's avatar
Sylvain Thery committed
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
//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;
//}

462
463
bool Map3::collapseDegeneretedVolume(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
464
465
	Dart e1 = d;
	Dart e2 = phi2(d);
466

Sylvain Thery's avatar
Sylvain Thery committed
467
	do
468
	{
Sylvain Thery's avatar
Sylvain Thery committed
469
470
471
472
473
474
475
476
477
478
479
		if (e1 != phi2(e2))
			return false;
		e1 = phi1(e1);
		e2 = phi_1(e2);
	}while (e1 != d);

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

	// degenerated:
	do
480
	{
Sylvain Thery's avatar
Sylvain Thery committed
481
482
483
484
485
486
487
488
		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);
489

Sylvain Thery's avatar
Sylvain Thery committed
490
491
492
493
494
495
496
497
	Map2::deleteCC(d) ;
	return true;
}


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

500
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
501
{
Sylvain Thery's avatar
Sylvain Thery committed
502
	assert(sewVolumesPreCond(d,e));
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
533
534
	// 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) ;
		}
535
536
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
537
538
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
539
	} while(fitD != dd) ;
540
541
	Map2::deleteCC(dd) ;

542
543
	fitD = d ;
	fitE = e ;
544
545
	do
	{
546
		phi3sew(fitD, fitE) ;
547
548
549
550
551
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

Sylvain Thery's avatar
Sylvain Thery committed
552
553
554
555
556
557
bool Map3::unsewVolumesPreCond(Dart d)
{
	return (!isBoundaryFace(d)) ;
}


558
559
void Map3::unsewVolumes(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
560
	assert(unsewVolumesPreCond(d)) ;
untereiner's avatar
untereiner committed
561
562
563
564
565
566
567
568
569
570
571

	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 ;
572
573
	do
	{
untereiner's avatar
untereiner committed
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
		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) ;
594
595
596
597
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
598
	if(!Map3::isBoundaryFace(d))
599
	{
untereiner's avatar
untereiner committed
600
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
601
602
603
604
605
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
606
607
void Map3::splitVolume(std::vector<Dart>& vd)
{
608
	//assert(checkSimpleOrientedPath(vd)) ;
untereiner's avatar
untereiner committed
609

untereiner's avatar
untereiner committed
610
611
612
	Dart e = vd.front();
	Dart e2 = phi2(e);

613
614
615
616
617
618
//	//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
619

620
	Map2::splitSurface(vd,true,true);
untereiner's avatar
untereiner committed
621

untereiner's avatar
untereiner committed
622
	//sew the two connected components
untereiner's avatar
untereiner committed
623
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
624
625
}

626
627
628
629
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

630
bool Map3::sameVertex(Dart d, Dart e)
631
632
633
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
634
635
636
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
637
638
	mv.mark(d);

639
	for(unsigned int i = 0; i < darts.size(); ++i)
640
	{
641
		if(darts[i] == e)
642
643
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
644
		// add phi21 and phi23 successor if they are not marked yet
645
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
646
647
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
648

untereiner's avatar
untereiner committed
649
650
651
652
653
654
655
656
657
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
658
659
660
661
662
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
663
664
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
665
	unsigned int count = 0;
untereiner's avatar
untereiner committed
666
667
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
668
669
670
	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
671
672
	mv.mark(d);

673
	for(unsigned int i = 0; i < darts.size(); ++i)
untereiner's avatar
untereiner committed
674
675
	{
		//add phi21 and phi23 successor if they are not marked yet
676
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
677
678
679
680
681
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
682
			darts.push_back(d21);
untereiner's avatar
untereiner committed
683
684
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
685
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
686
		{
untereiner's avatar
untereiner committed
687
			darts.push_back(d23);
untereiner's avatar
untereiner committed
688
689
690
691
692
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
untereiner's avatar
untereiner committed
693
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
694
	{
untereiner's avatar
untereiner committed
695
		if(!me.isMarked(*it))
untereiner's avatar
untereiner committed
696
697
		{
			++count;
untereiner's avatar
untereiner committed
698
			me.markOrbit(EDGE, *it);
untereiner's avatar
untereiner committed
699
700
701
702
703
704
		}
	}

	return count;
}

705
706
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
707
	DartMarkerStore mv(*this);	// Lock a marker
708

untereiner's avatar
untereiner committed
709
710
711
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
712
713
	mv.mark(d);

714
	for(unsigned int i = 0; i < darts.size(); ++i)
715
	{
716
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
717
			return true ;
718
719

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

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
726
			darts.push_back(d21);
727
728
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
729
		if(!mv.isMarked(d23))
730
		{
untereiner's avatar
untereiner committed
731
			darts.push_back(d23);
732
733
734
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
735
	return false ;
736
737
738
739
}

bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
740
	Dart it = d;
741
742
	do
	{
untereiner's avatar
untereiner committed
743
		if(it == e)
744
			return true;
untereiner's avatar
untereiner committed
745
746
		it = alpha2(it);
	} while (it != d);
747
748
749
	return false;
}

untereiner's avatar
untereiner committed
750
unsigned int Map3::edgeDegree(Dart d)
751
{
untereiner's avatar
untereiner committed
752
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
753
	Dart it = d;
754
755
	do
	{
untereiner's avatar
untereiner committed
756
757
758
		++deg;
		it = alpha2(it);
	} while(it != d);
759
760
761
	return deg;
}

untereiner's avatar
untereiner committed
762
bool Map3::isBoundaryEdge(Dart d)
763
{
untereiner's avatar
untereiner committed
764
765
766
767
768
769
770
771
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
772
773
}

untereiner's avatar
untereiner committed
774
Dart Map3::findBoundaryFaceOfEdge(Dart d)
775
{
untereiner's avatar
untereiner committed
776
777
778
779
780
781
782
783
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
784
785
}

Pierre Kraemer's avatar
Pierre Kraemer committed
786
787
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
788
789
	Traversor3WF<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
790
	{
untereiner's avatar
untereiner committed
791
		if(isBoundaryMarked(phi3(dit)))
untereiner's avatar
untereiner committed
792
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
793
	}
untereiner's avatar
untereiner committed
794
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
795
796
}

untereiner's avatar
untereiner committed
797
798
bool Map3::hasBoundaryEdge(Dart d)
{
untereiner's avatar
untereiner committed
799
800
	Traversor3WE<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
untereiner's avatar
untereiner committed
801
	{
untereiner's avatar
untereiner committed
802
803
		if(isBoundaryEdge(dit))
			return true;
untereiner's avatar
untereiner committed
804
	}
untereiner's avatar
untereiner committed
805

untereiner's avatar
untereiner committed
806
807
808
	return false;
}

809
bool Map3::check()
810
{
811
812
813
814
815
816
817
818
819
820
    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;
        }
821

untereiner's avatar
untereiner committed
822
823
824
825
826
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
			return false;
		}
827

828
829
830
831
832
833
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
834

835
836
837
838
839
840
        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;
        }
841

842
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
843
		{
844
845
846
847
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
848

849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
        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 ?
865
		{
866
867
868
869
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
870

871
    std::cout << "Check: topology ok" << std::endl;
872

873
    return true;
874
875
}

Pierre Kraemer's avatar
Pierre Kraemer committed
876
877
878
879
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
880
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
881
{
untereiner's avatar
untereiner committed
882
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
883
884
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
885
886
887
	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
888
889
	mv.mark(d);

890
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
891
	{
892
		// add phi21 and phi23 successor if they are not marked yet
893
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
894
895
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
896

untereiner's avatar
untereiner committed
897
898
899
900
901
902
903
904
905
		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
906
907
		}

908
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
909
910
911
912
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
913
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
914
{
untereiner's avatar
untereiner committed
915
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
916
917
	do
	{
untereiner's avatar
untereiner committed
918
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
919
			return true;
untereiner's avatar
untereiner committed
920
921
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
922
923
924
	return false;
}

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

untereiner's avatar
untereiner committed
930
931
932
	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
933
934
	mv.mark(d);

935
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
936
	{
untereiner's avatar
untereiner committed
937
		// add all successors if they are not marked yet
938
939
940
		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
941

untereiner's avatar
untereiner committed
942
943
944
945
946
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
947
948
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
949
950
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
951
952
953
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
954
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
955
956
957
			mv.mark(d4);
		}

958
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
959
960
961
962
	}
	return found;
}

untereiner's avatar
untereiner committed
963
964
965
/*! @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
966

untereiner's avatar
untereiner committed
967
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
968
{
untereiner's avatar
untereiner committed
969
	assert(phi3(d) == d);		// Nothing to close
970
	DartMarkerStore m(*this) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
971

untereiner's avatar
untereiner committed
972
973
974
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
975
976
//	m.markOrbit(ORIENTED_FACE, d) ;
	m.markOrbit(FACE2, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
977

untereiner's avatar
untereiner committed
978
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
979

untereiner's avatar
untereiner committed
980
	// For every face added to the list
981
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
982
	{
983
984
985
		Dart it = visitedFaces[i] ;
		Dart f = it ;

untereiner's avatar
untereiner committed
986
987
988
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
989

untereiner's avatar
untereiner committed
990
991
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
992
		{
untereiner's avatar
untereiner committed
993
994
995
996
997
998
999
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
				if(phi3(e) == e)
				{
					found = true ;
1000
1001
1002
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
1003
						m.markOrbit(FACE2, e) ;
1004
					}
untereiner's avatar
untereiner committed
1005
				}
1006
				else if(isBoundaryMarked(e))
untereiner's avatar
untereiner committed
1007
1008
				{
					found = true ;
1009
					phi2sew(e, bit) ;
untereiner's avatar
untereiner committed
1010
1011
1012
1013
1014
1015
1016
1017
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
1018
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1019
1020
	}

untereiner's avatar
untereiner committed
1021
1022
1023
	return count ;
}

1024
unsigned int Map3::closeMap()
untereiner's avatar
untereiner committed
1025
1026
{
	// Search the map for topological holes (fix points of phi3)
1027
	unsigned int nb = 0 ;
untereiner's avatar
untereiner committed
1028
1029
1030
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi3(d) == d)
1031
1032
		{
			++nb ;
untereiner's avatar
untereiner committed
1033
			closeHole(d);
1034
		}
untereiner's avatar
untereiner committed
1035
	}
1036
	return nb ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1037
1038
1039
}

} // namespace CGoGN