map3.cpp 18.1 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1 2 3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2011, IGG Team, LSIIT, University of Strasbourg           *
Pierre Kraemer's avatar
Pierre Kraemer committed
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
20
* Web site: http://cgogn.u-strasbg.fr/                                         *
Pierre Kraemer's avatar
Pierre Kraemer committed
21 22 23 24 25 26 27 28 29 30 31 32
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/map3.h"

namespace CGoGN
{

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

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

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

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

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

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

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

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

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

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

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

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

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

106
	Dart res = NIL ;
untereiner's avatar
untereiner committed
107 108
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
109 110 111 112 113 114 115 116
		Dart fit = *it ;
		Dart end = phi_1(fit) ;
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
117

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

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

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

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

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

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

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

		Map2::cutEdge(prev);

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

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

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

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

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

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

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

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

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

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

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

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

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

	return res ;
}

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

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

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

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

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

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

248
		}
untereiner's avatar
untereiner committed
249

250 251
	}while(d != dit);

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



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

307

untereiner's avatar
untereiner committed
308

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

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

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

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

323 324 325 326 327
bool Map3::collapseDegeneretedVolume(Dart d)
{
	Dart e1 = phi2(d);
	Dart e2 = phi2(phi1(d));

328 329
	//Si les deux faces ne sont pas du bord
	if(!isBoundaryFace(e1) && !isBoundaryFace(e2))
330
	{
331 332 333
		sewVolumes(phi3(e1),phi3(e2));
		deleteVolume(d);
		return true;
334 335 336
	}
	else
	{
337 338 339
		//alors simple suppression du volume degenere
		deleteVolume(d);
		return true;
340
	}
341 342

	return false;
343 344
}

345
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
346 347 348
{
	assert(faceDegree(d) == faceDegree(e));

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
	// 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) ;
		}
380 381
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
382 383
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
384
	} while(fitD != dd) ;
385 386
	Map2::deleteCC(dd) ;

387 388
	fitD = d ;
	fitE = e ;
389 390
	do
	{
391
		phi3sew(fitD, fitE) ;
392 393 394 395 396 397 398
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void Map3::unsewVolumes(Dart d)
{
untereiner's avatar
untereiner committed
399 400 401 402 403 404 405 406 407 408 409 410
	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 ;
411 412
	do
	{
untereiner's avatar
untereiner committed
413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432
		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) ;
433 434 435 436
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
437
	if(!Map3::isBoundaryFace(d))
438
	{
untereiner's avatar
untereiner committed
439
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
440 441 442 443 444
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
445 446
void Map3::splitVolume(std::vector<Dart>& vd)
{
untereiner's avatar
untereiner committed
447 448
	assert(checkSimpleOrientedPath(vd)) ;

untereiner's avatar
untereiner committed
449 450 451 452 453 454 455
	Dart e = vd.front();
	Dart e2 = phi2(e);

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

untereiner's avatar
untereiner committed
456 457
	Map2::fillHole(e) ;
	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
458

untereiner's avatar
untereiner committed
459 460
	//sew the two connected components
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
461 462
}

463 464 465 466
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

467
bool Map3::sameVertex(Dart d, Dart e)
468 469 470
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
471 472 473
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
474 475
	mv.mark(d);

476
	for(unsigned int i = 0; i < darts.size(); ++i)
477
	{
478
		if(darts[i] == e)
479 480
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
481
		// add phi21 and phi23 successor if they are not marked yet
482
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
483 484
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
485

untereiner's avatar
untereiner committed
486 487 488 489 490 491 492 493 494
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
495 496 497 498 499
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
500 501
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
502
	unsigned int count = 0;
untereiner's avatar
untereiner committed
503 504
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
505 506 507
	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
508 509
	mv.mark(d);

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

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
519
			darts.push_back(d21);
untereiner's avatar
untereiner committed
520 521
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
522
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
523
		{
untereiner's avatar
untereiner committed
524
			darts.push_back(d23);
untereiner's avatar
untereiner committed
525 526 527 528 529
			mv.mark(d23);
		}
	}

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

	return count;
}

542 543
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
544
	DartMarkerStore mv(*this);	// Lock a marker
545

untereiner's avatar
untereiner committed
546 547 548
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
549 550
	mv.mark(d);

551
	for(unsigned int i = 0; i < darts.size(); ++i)
552
	{
553
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
554
			return true ;
555 556

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

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
563
			darts.push_back(d21);
564 565
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
566
		if(!mv.isMarked(d23))
567
		{
untereiner's avatar
untereiner committed
568
			darts.push_back(d23);
569 570 571
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
572
	return false ;
573 574 575 576
}

bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
577
	Dart it = d;
578 579
	do
	{
untereiner's avatar
untereiner committed
580
		if(it == e)
581
			return true;
untereiner's avatar
untereiner committed
582 583
		it = alpha2(it);
	} while (it != d);
584 585 586
	return false;
}

untereiner's avatar
untereiner committed
587
unsigned int Map3::edgeDegree(Dart d)
588
{
untereiner's avatar
untereiner committed
589
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
590
	Dart it = d;
591 592
	do
	{
untereiner's avatar
untereiner committed
593 594 595
		++deg;
		it = alpha2(it);
	} while(it != d);
596 597 598
	return deg;
}

untereiner's avatar
untereiner committed
599
bool Map3::isBoundaryEdge(Dart d)
600
{
untereiner's avatar
untereiner committed
601 602 603 604 605 606 607 608
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
609 610
}

untereiner's avatar
untereiner committed
611
Dart Map3::findBoundaryFaceOfEdge(Dart d)
612
{
untereiner's avatar
untereiner committed
613 614 615 616 617 618 619 620
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
621 622
}

Pierre Kraemer's avatar
Pierre Kraemer committed
623 624
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
625
	DartMarkerStore mark(*this);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
626 627

	std::vector<Dart> visitedFaces ;
untereiner's avatar
untereiner committed
628
	visitedFaces.reserve(128) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
629
	visitedFaces.push_back(d) ;
untereiner's avatar
untereiner committed
630
	mark.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
631

632
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
633
	{
634
		if (isBoundaryMarked(phi3(visitedFaces[i])))
untereiner's avatar
untereiner committed
635
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
636

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

652
bool Map3::check()
653
{
654 655 656 657 658 659 660 661 662 663
    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;
        }
664

untereiner's avatar
untereiner committed
665 666 667 668 669
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
			return false;
		}
670

671 672 673 674 675 676
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
677

678 679 680 681 682 683
        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;
        }
684

685
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
686
		{
687 688 689 690
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
691

692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707
        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 ?
708
		{
709 710 711 712
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
713

714
    std::cout << "Check: topology ok" << std::endl;
715

716
    return true;
717 718
}

Pierre Kraemer's avatar
Pierre Kraemer committed
719 720 721 722
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
723
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
724
{
untereiner's avatar
untereiner committed
725
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
726 727
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
728 729 730
	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
731 732
	mv.mark(d);

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

untereiner's avatar
untereiner committed
740 741 742 743 744 745 746 747 748
		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
749 750
		}

751
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
752 753 754 755
	}
	return found;
}

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

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

untereiner's avatar
untereiner committed
773 774 775
	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
776 777
	mv.mark(d);

778
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
779
	{
untereiner's avatar
untereiner committed
780
		// add all successors if they are not marked yet
781 782 783
		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
784

untereiner's avatar
untereiner committed
785 786 787 788 789
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
790 791
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
792 793
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
794 795 796
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
797
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
798 799 800
			mv.mark(d4);
		}

801
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
802 803 804 805
	}
	return found;
}

untereiner's avatar
untereiner committed
806 807 808
/*! @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
809

untereiner's avatar
untereiner committed
810
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
811
{
untereiner's avatar
untereiner committed
812
	assert(phi3(d) == d);		// Nothing to close
813
	DartMarkerStore m(*this) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
814

untereiner's avatar
untereiner committed
815 816 817
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
818
	m.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
819

untereiner's avatar
untereiner committed
820
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
821

untereiner's avatar
untereiner committed
822
	// For every face added to the list
823
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
824
	{
825 826 827
		Dart it = visitedFaces[i] ;
		Dart f = it ;

untereiner's avatar
untereiner committed
828 829 830
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
831

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

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
860
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
861 862
	}

untereiner's avatar
untereiner committed
863 864 865 866 867 868 869 870 871 872 873
	return count ;
}

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

} // namespace CGoGN