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

map3.cpp 31.9 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, bool withBoundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
83
{
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
	if(withBoundary)
	{
		DartMarkerStore mark(*this);		// Lock a marker

		std::vector<Dart> visitedFaces;		// Faces that are traversed
		visitedFaces.reserve(512);
		visitedFaces.push_back(d);			// Start with the face of d

		mark.markOrbit<FACE2>(d) ;

		for(unsigned int i = 0; i < visitedFaces.size(); ++i)
		{
			Dart e = visitedFaces[i] ;

			if(!isBoundaryFace(e))
				unsewVolumes(e) ;

			do	// add all face neighbours to the table
			{
				Dart ee = phi2(e) ;
				if(!mark.isMarked(ee)) // not already marked
				{
					visitedFaces.push_back(ee) ;
					mark.markOrbit<FACE2>(ee) ;
				}
				e = phi1(e) ;
			} while(e != visitedFaces[i]) ;
		}

		Dart dd = phi3(d) ;
		Map2::deleteCC(d) ; //deleting the volume
		Map2::deleteCC(dd) ; //deleting its border (created from the unsew operation)

		return;
	}

	//else remove the CC and create fixed points
121
122
123
124
125
126
127
128
129
	DartMarkerStore mark(*this);		// Lock a marker

	std::vector<Dart> visitedFaces;		// Faces that are traversed
	visitedFaces.reserve(512);
	visitedFaces.push_back(d);			// Start with the face of d

	mark.markOrbit<FACE2>(d) ;

	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
130
	{
131
132
		Dart e = visitedFaces[i] ;

133
134
135
136
137
138
		Dart it = e ;
		do
		{
			phi3unsew(it);
			it = phi1(it) ;
		} while(it != e) ;
139
140
141
142
143
144
145
146
147
148
149

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

152
	Map2::deleteCC(d) ; //deleting the volume
Pierre Kraemer's avatar
Pierre Kraemer committed
153
154
}

155
156
void Map3::fillHole(Dart d)
{
157
158
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
Thery Sylvain's avatar
Thery Sylvain committed
159
	if(!isBoundaryMarked3(dd))
160
		dd = phi3(dd) ;
Thery Sylvain's avatar
Thery Sylvain committed
161
	boundaryUnmarkOrbit<VOLUME,3>(dd) ;
162
163
}

164
165
166
167
168
169
void Map3::createHole(Dart d)
{
	assert(!isBoundaryFace(d)) ;
	boundaryMarkOrbit<VOLUME,3>(d) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
170
171
172
173
/*! @name Topological Operators
 *  Topological operations on 3-maps
 *************************************************************************/

untereiner's avatar
untereiner committed
174
Dart Map3::splitVertex(std::vector<Dart>& vd)
untereiner's avatar
untereiner committed
175
{
176
	//assert(checkPathAroundVertex(vd)) ;
untereiner's avatar
untereiner committed
177

untereiner's avatar
untereiner committed
178
	//bool boundE = false;
untereiner's avatar
untereiner committed
179
180

	Dart prev = vd.front();	//elt 0
181
182

	Dart db1 = NIL;
183
	if(isBoundaryFace(phi2(prev)))
184
185
186
187
	{
		db1 = phi2(phi3(phi1(phi2(prev))));
	}

untereiner's avatar
untereiner committed
188
189
190
191
192
193
194
195
196
197
198
199
	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));

200
201
		Dart d1 = phi_1(phi2(phi_1(vd[i-1])));
		Dart d2 = phi1(phi2(vd[i]));
untereiner's avatar
untereiner committed
202

203
		phi3sew(d1, d2);
untereiner's avatar
untereiner committed
204
205
	}

206
207
	Dart db2 = NIL;
	if(isBoundaryFace(phi2(phi_1(prev))))
Lionel Untereiner's avatar
Lionel Untereiner committed
208
	{
209
		db2 = phi2(phi3(phi2(phi_1(prev))));
Lionel Untereiner's avatar
Lionel Untereiner committed
210
211
	}

212
213
214
215
216
217
	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))));
	}
218
	else
219
220
221
222
223
	{
		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
224

untereiner's avatar
untereiner committed
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
	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
258
/*
untereiner's avatar
untereiner committed
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
	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
276
*/
untereiner's avatar
untereiner committed
277

untereiner's avatar
untereiner committed
278

279
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
280
{
281
282
	//if(isBoundaryVertex(d))
	//	return NIL ;
283

Pierre Kraemer's avatar
Pierre Kraemer committed
284
285
	// Save the darts around the vertex
	// (one dart per face should be enough)
untereiner's avatar
untereiner committed
286
	std::vector<Dart> fstoretmp;
287
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
288
289
290
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

291
	 // just one dart per face
untereiner's avatar
untereiner committed
292
	std::vector<Dart> fstore;
293
	fstore.reserve(128);
untereiner's avatar
untereiner committed
294
	DartMarker mf(*this);
295
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
296
	{
297
		if(!mf.isMarked(fstoretmp[i]))
298
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
299
			mf.markOrbit<FACE>(fstoretmp[i]);
300
			fstore.push_back(fstoretmp[i]);
untereiner's avatar
untereiner committed
301
		}
302
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
303

304
305
	std::cout << "nb faces " << fstore.size() << std::endl;

306
	Dart res = NIL ;
untereiner's avatar
untereiner committed
307
308
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
309
310
311
		Dart fit = *it ;
		Dart end = phi_1(fit) ;
		fit = phi1(fit) ;
312
313

		if(fit == end)
314
		{
315
			std::cout << " mmmmmmmmmmmmmmmmmmmmmerrrrrrrrrrrrrrrrrde !!!!!!!!!!!! " << std::endl;
316

317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
//			Dart d2 = phi2(fit) ;
//			Dart d23 = phi3(d2) ;
//			Dart d3 = phi3(fit) ;
//			Dart d32 = phi2(d3) ;
//
//			//phi3unsew()
//			phi3sew(d3,23);
//
//			fit = phi_1(fit);
//
//			d2 = phi2(fit) ;
//			d23 = phi3(d2) ;
//			d3 = phi3(fit) ;
//			d32 = phi2(d3) ;
//			phi3sew(d3,23);
332

333
334
335
336
337
338
339
340
341
//			Map2::deleteCC(fit);
		}
		else
		{
			while(fit != end)
			{
				Dart d2 = phi2(fit) ;
				Dart d3 = phi3(fit) ;
				Dart d32 = phi2(d3) ;
342

343
344
345
346
347
348
349
350
351
352
				if(res == NIL)
					res = d2 ;

				phi2unsew(d2) ;
				phi2unsew(d32) ;
				phi2sew(d2, d32) ;
				phi2sew(fit, d3) ;

				fit = phi1(fit) ;
			}
353
		}
untereiner's avatar
untereiner committed
354
	}
355

356
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
357

358
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
359
360
}

David Cazier's avatar
David Cazier committed
361
Dart Map3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
362
363
364
{
	Dart prev = d;
	Dart dd = alpha2(d);
David Cazier's avatar
David Cazier committed
365
	Dart nd = Map2::cutEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
366

367
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
368
369
370
371
372
373
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

374
375
376
377
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
378
379
	}

380
381
382
383
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
384

David Cazier's avatar
David Cazier committed
385
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
386
387
}

Pierre Kraemer's avatar
Pierre Kraemer committed
388
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
389
{
Pierre Kraemer's avatar
Pierre Kraemer committed
390
391
	if(vertexDegree(phi1(d)) == 2)
	{
392
393
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
394

395
396
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
397
398
399
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
400

401
402
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
403
404
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
405
406
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
407
		return true;
untereiner's avatar
untereiner committed
408
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
409
	return false;
untereiner's avatar
untereiner committed
410
411
}

Sylvain Thery's avatar
Sylvain Thery committed
412
413
414
415
416
417
418
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
419
420
Dart Map3::deleteEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
421
422
	assert(deleteEdgePreCond(d));

untereiner's avatar
untereiner committed
423
424
425
426
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
427
428
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
429
	{
430
431
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
432
433
434
435
436
437
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
438

untereiner's avatar
untereiner committed
439
440
			if(res == NIL)
				res = d2 ;
441

untereiner's avatar
untereiner committed
442
443
444
445
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
446
447

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
448
		}
449
450
451
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
452
453
454
455
456
	Map2::deleteCC(d) ;

	return res ;
}

Sylvain Thery's avatar
Sylvain Thery committed
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
//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
490
491
492
Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
493
	Dart dit = d;
untereiner's avatar
untereiner committed
494

Sylvain Thery's avatar
Sylvain Thery committed
495
	std::vector<Dart> darts;
untereiner's avatar
untereiner committed
496
497
	do
	{
Sylvain Thery's avatar
Sylvain Thery committed
498
		darts.push_back(dit);
499
		dit = alpha2(dit);
Sylvain Thery's avatar
Sylvain Thery committed
500
	}while(dit != d);
untereiner's avatar
untereiner committed
501

Sylvain Thery's avatar
Sylvain Thery committed
502
503
504
	for (std::vector<Dart>::iterator it = darts.begin(); it != darts.end(); ++it)
	{
		Dart x = phi2(phi_1(*it));
505
506
507
508
509
510
511
512

		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
513
514
		resV = Map2::collapseEdge(*it, true);
		if (delDegenerateVolumes)
515
516
			if(collapseDegeneretedVolume(x) && resCV != NIL)
				resV = resCV;
Sylvain Thery's avatar
Sylvain Thery committed
517
	}
518

519
520
	return resV;
}
521
522


Sylvain Thery's avatar
Sylvain Thery committed
523
bool Map3::splitFacePreCond(Dart d, Dart e)
524
{
Sylvain Thery's avatar
Sylvain Thery committed
525
	return (d != e && sameOrientedFace(d, e)) ;
526
}
untereiner's avatar
untereiner committed
527

528
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
529
{
Sylvain Thery's avatar
Sylvain Thery committed
530
531
//	assert(d != e && sameOrientedFace(d, e)) ;
	assert(splitFacePreCond(d,e));
Pierre Kraemer's avatar
Pierre Kraemer committed
532

533
534
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
535

untereiner's avatar
untereiner committed
536
	Map2::splitFace(d, e);
537
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
538

539
540
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
541
542
}

Thomas's avatar
Thomas committed
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
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;
}

570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
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
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
//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;
//}

613
614
bool Map3::collapseDegeneretedVolume(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
615
616
	Dart e1 = d;
	Dart e2 = phi2(d);
617

Sylvain Thery's avatar
Sylvain Thery committed
618
	do
619
	{
Sylvain Thery's avatar
Sylvain Thery committed
620
621
622
623
624
625
626
627
628
629
630
		if (e1 != phi2(e2))
			return false;
		e1 = phi1(e1);
		e2 = phi_1(e2);
	}while (e1 != d);

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

	// degenerated:
	do
631
	{
Sylvain Thery's avatar
Sylvain Thery committed
632
633
634
635
636
637
638
639
		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);
640

Sylvain Thery's avatar
Sylvain Thery committed
641
642
643
644
645
646
647
648
	Map2::deleteCC(d) ;
	return true;
}


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

651
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
652
{
Sylvain Thery's avatar
Sylvain Thery committed
653
	assert(sewVolumesPreCond(d,e));
654

655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
	// 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) ;
		}
686
687
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
688
689
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
690
	} while(fitD != dd) ;
691
692
	Map2::deleteCC(dd) ;

693
694
	fitD = d ;
	fitE = e ;
695
696
	do
	{
697
		phi3sew(fitD, fitE) ;
698
699
700
701
702
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

Sylvain Thery's avatar
Sylvain Thery committed
703
704
705
706
707
708
bool Map3::unsewVolumesPreCond(Dart d)
{
	return (!isBoundaryFace(d)) ;
}


709
710
void Map3::unsewVolumes(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
711
	assert(unsewVolumesPreCond(d)) ;
untereiner's avatar
untereiner committed
712
713
714
715
716
717
718
719
720
721
722

	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 ;
723
724
	do
	{
untereiner's avatar
untereiner committed
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
		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) ;
745
746
747
748
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
749
	if(!Map3::isBoundaryFace(d))
750
	{
untereiner's avatar
untereiner committed
751
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
752
753
754
755
756
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
757
758
void Map3::splitVolume(std::vector<Dart>& vd)
{
759
	//assert(checkSimpleOrientedPath(vd)) ;
untereiner's avatar
untereiner committed
760

untereiner's avatar
untereiner committed
761
762
763
	Dart e = vd.front();
	Dart e2 = phi2(e);

764
	Map2::splitSurface(vd,true,true);
untereiner's avatar
untereiner committed
765

untereiner's avatar
untereiner committed
766
	//sew the two connected components
untereiner's avatar
untereiner committed
767
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
768
769
}

770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
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;
}

793
794
795
796
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

797
bool Map3::sameVertex(Dart d, Dart e)
798
799
800
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
801
802
803
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
804
805
	mv.mark(d);

806
	for(unsigned int i = 0; i < darts.size(); ++i)
807
	{
808
		if(darts[i] == e)
809
810
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
811
		// add phi21 and phi23 successor if they are not marked yet
812
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
813
814
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
815

untereiner's avatar
untereiner committed
816
817
818
819
820
821
822
823
824
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
825
826
827
828
829
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
830
831
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
832
	unsigned int count = 0;
untereiner's avatar
untereiner committed
833

834
835
	Traversor3VE<Map3> trav3VE(*this, d);
	for(Dart dit = trav3VE.begin() ; dit != trav3VE.end() ; dit = trav3VE.next())
untereiner's avatar
untereiner committed
836
	{
837
		++count;
untereiner's avatar
untereiner committed
838
839
840
841
842
	}

	return count;
}

843
844
845
846
847
848
849
unsigned int Map3::vertexDegreeOnBoundary(Dart d)
{
	assert(Map3::isBoundaryVertex(d));

	return Map2::vertexDegree(d);
}

850
851
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
852
	DartMarkerStore mv(*this);	// Lock a marker
853

untereiner's avatar
untereiner committed
854
855
856
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
857
858
	mv.mark(d);

859
	for(unsigned int i = 0; i < darts.size(); ++i)
860
	{
Thery Sylvain's avatar
Thery Sylvain committed
861
		if(isBoundaryMarked3(darts[i]))
untereiner's avatar
untereiner committed
862
			return true ;
863
864

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

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
871
			darts.push_back(d21);
872
873
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
874
		if(!mv.isMarked(d23))
875
		{
untereiner's avatar
untereiner committed
876
			darts.push_back(d23);
877
878
879
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
880
	return false ;
881
882
}

untereiner's avatar
untereiner committed
883
884
885
886
887
888
889
890
891
892
893
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)
	{
Thery Sylvain's avatar
Thery Sylvain committed
894
		if(isBoundaryMarked3(darts[i]))
untereiner's avatar
untereiner committed
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
			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 ;
}

916
917
bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
918
	Dart it = d;
919
920
	do
	{
untereiner's avatar
untereiner committed
921
		if(it == e)
922
			return true;
untereiner's avatar
untereiner committed
923
924
		it = alpha2(it);
	} while (it != d);
925
926
927
	return false;
}

untereiner's avatar
untereiner committed
928
unsigned int Map3::edgeDegree(Dart d)
929
{
untereiner's avatar
untereiner committed
930
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
931
	Dart it = d;
932
933
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
934
		if(!isBoundaryMarked3(it))
935
			++deg;
untereiner's avatar
untereiner committed
936
937
		it = alpha2(it);
	} while(it != d);
938
939
940
	return deg;
}

untereiner's avatar
untereiner committed
941
bool Map3::isBoundaryEdge(Dart d)
942
{
untereiner's avatar
untereiner committed
943
944
945
	Dart it = d;
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
946
		if(isBoundaryMarked3(it))
untereiner's avatar
untereiner committed
947
948
949
950
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
951
952
}

untereiner's avatar
untereiner committed
953
Dart Map3::findBoundaryFaceOfEdge(Dart d)
954
{
untereiner's avatar
untereiner committed
955
956
957
	Dart it = d;
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
958
		if (isBoundaryMarked3(it))
untereiner's avatar
untereiner committed
959
960
961
962
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
963
964
}

Pierre Kraemer's avatar
Pierre Kraemer committed
965
966
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
967
968
	Traversor3WF<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
969
	{
Thery Sylvain's avatar
Thery Sylvain committed
970
		if(isBoundaryMarked3(phi3(dit)))
untereiner's avatar
untereiner committed
971
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
972
	}
untereiner's avatar
untereiner committed
973
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
974
975
}

untereiner's avatar
untereiner committed
976
977
bool Map3::hasBoundaryEdge(Dart d)
{
untereiner's avatar
untereiner committed
978
979
	Traversor3WE<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
untereiner's avatar
untereiner committed
980
	{
untereiner's avatar
untereiner committed
981
982
		if(isBoundaryEdge(dit))
			return true;
untereiner's avatar
untereiner committed
983
	}
untereiner's avatar
untereiner committed
984

untereiner's avatar
untereiner committed
985
986
987
	return false;
}

988
bool Map3::check()
989
{
990
    std::cout << "Check: topology begin" << std::endl;
991
    DartMarkerStore m(*this);
992
993
994
995
996
997
998
999
    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;
        }
1000

untereiner's avatar
untereiner committed
1001
1002
		if(phi1(d3) != phi3(phi_1(d)))
		{
Thery Sylvain's avatar
Thery Sylvain committed
1003
			if(isBoundaryMarked3(d))
1004
1005
1006
1007
				std::cout << "Boundary case - Check: phi3 , faces are not entirely sewn" << std::endl;
			else
				std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
			return false;
untereiner's avatar
untereiner committed
1008
		}
1009

1010
1011
1012
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
untereiner's avatar
untereiner committed
1013
        	if(isBoundaryMarked3(d))
1014
1015
1016
        		std::cout << "Boundary case - ";

        	std::cout << "Check: phi2 is not an involution" << std::endl;
1017
1018
            return false;
        }
1019

1020
1021
1022
        Dart d1 = phi1(d);
        if (phi_1(d1) != d) // phi1 a une image correcte ?
		{
untereiner's avatar
untereiner committed
1023
        	if(isBoundaryMarked3(d))
1024
1025
        		std::cout << "Boundary case - ";

1026
1027
1028
            std::cout << "Check: unconsistent phi_1 link" << std::endl;
            return false;
        }
1029

1030
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
1031
		{
untereiner's avatar
untereiner committed
1032
        	if(isBoundaryMarked3(d))
1033
1034
        		std::cout << "Boundary case - ";

1035
1036
1037
1038
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
1039

1040
        if (d1 == d)
1041
        {
untereiner's avatar
untereiner committed
1042
        	if(isBoundaryMarked3(d))
1043
1044
        		std::cout << "Boundary case - ";

1045
            std::cout << "Check: (warning) face loop (one edge)" << std::endl;
1046
        }
1047
1048

        if (phi1(d1) == d)
1049
        {
untereiner's avatar
untereiner committed
1050
        	if(isBoundaryMarked3(d))
1051
1052
        		std::cout << "Boundary case - ";

1053
            std::cout << "Check: (warning) face with only two edges" << std::endl;
1054
        }
1055
1056

        if (phi2(d1) == d)
1057
        {
untereiner's avatar
untereiner committed
1058
        	if(isBoundaryMarked3(d))
1059
1060
1061
1062
        		std::cout << "Boundary case - ";

        	std::cout << "Check: (warning) dandling edge (phi2)" << std::endl;
        }
1063
1064

        if (phi3(d1) == d)
1065
        {
untereiner's avatar
untereiner committed
1066
        	if(isBoundaryMarked3(d))
1067
1068
        		std::cout << "Boundary case - ";

1069
            std::cout << "Check: (warning) dandling edge (phi3)" << std::endl;
1070
        }
1071
1072
1073
1074
1075
    }

    for(Dart d = this->begin(); d != this->end(); this->next(d))
    {
        if (!m.isMarked(d)) // phi1 a au moins un antécédent ?
1076
		{
untereiner's avatar
untereiner committed
1077
        	if(isBoundaryMarked3(d))
1078
1079
        		std::cout << "Boundary case - ";

1080
1081
1082
1083
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
1084

1085
    std::cout << "Check: topology ok" << std::endl;
1086

1087
    return true;
1088
1089
}

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

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

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

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

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

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

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

untereiner's avatar
untereiner committed
1139