gmap2.cpp 18.8 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
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/gmap/gmap2.h"
26
#include "Topology/generic/traversorCell.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
27 28 29 30

namespace CGoGN
{

31 32
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-G-map
Pierre Kraemer's avatar
Pierre Kraemer committed
33 34
 *************************************************************************/

35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
Dart GMap2::newFace(unsigned int nbEdges, bool withBoundary)
{
	Dart d = GMap1::newFace(nbEdges);
	if (withBoundary)
	{
		Dart e = GMap1::newFace(nbEdges);

		Dart it = d;
		do
		{
			beta2sew(it, beta0(e));
			beta2sew(beta0(it), e);
			it = phi1(it);
			e = phi_1(e);
		} while (it != d);
	}
	return d;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
54 55
void GMap2::deleteFace(Dart d)
{
56 57
	assert(!isBoundaryMarked(d)) ;
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
58 59
	do
	{
60 61 62 63 64 65 66 67 68 69 70 71 72
		if(!isBoundaryEdge(it))
			unsewFaces(it) ;
		it = phi1(it) ;
	} while(it != d) ;
	Dart dd = phi2(d) ;
	GMap1::deleteFace(d) ;
	GMap1::deleteFace(dd) ;
}

void GMap2::fillHole(Dart d)
{
	assert(isBoundaryMarked(d)) ;
	boundaryUnmarkOrbit(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
73 74 75 76 77 78 79 80
}

/*! @name Topological Operators
 *  Topological operations on 2-G-maps
 *************************************************************************/

void GMap2::splitVertex(Dart d, Dart e)
{
81
	assert(sameVertex(d, e));
Pierre Kraemer's avatar
Pierre Kraemer committed
82 83 84 85
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
	GMap1::cutEdge(dd);			// Cut the edge of dd (make a new edge)
	GMap1::cutEdge(ee);			// Cut the edge of ee (make a new edge)
86 87
	beta2sew(phi1(dd), beta0(phi1(ee)));	// Sew the two faces along the new edge
	beta2sew(phi1(ee), beta0(phi1(dd)));
Pierre Kraemer's avatar
Pierre Kraemer committed
88 89
}

90
Dart GMap2::deleteVertex(Dart d)
91 92
{
	if(isBoundaryVertex(d))
93
		return NIL ;
94

95
	Dart res = NIL ;
96 97 98
	Dart vit = d ;
	do
	{
99 100 101 102 103 104 105 106 107 108 109 110
		if(res == NIL && phi1(phi1(d)) != d)
			res = phi1(d) ;

		Dart d0 = beta0(vit) ;
		Dart d02 = beta2(d0) ;
		Dart d01 = beta1(d0) ;
		Dart d021 = beta1(d02) ;
		beta1unsew(d0) ;
		beta1unsew(d02) ;
		beta1sew(d0, d02) ;
		beta1sew(d01, d021) ;

111 112
		vit = alpha1(vit) ;
	} while(vit != d) ;
113 114
	deleteFace(d) ;
	return res ;
115 116
}

Pierre Kraemer's avatar
Pierre Kraemer committed
117 118
void GMap2::cutEdge(Dart d)
{
119 120 121 122 123 124 125 126 127 128 129 130
	Dart e = phi2(d) ;
	beta2unsew(d) ;
	beta2unsew(e) ;
	GMap1::cutEdge(d) ;
	GMap1::cutEdge(e) ;

	Dart nd = phi1(d) ;
	Dart ne = phi1(e) ;
	beta2sew(d, beta0(ne)) ;
	beta2sew(beta0(d), ne) ;
	beta2sew(e, beta0(nd)) ;
	beta2sew(beta0(e), nd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
131 132
}

133
bool GMap2::uncutEdge(Dart d)
134
{
135
	if(vertexDegree(phi1(d)) == 2)
136
	{
137
		Dart ne = phi2(d) ;
138 139
		Dart nd = phi1(d) ;
		Dart e = phi_1(ne) ;
140 141 142 143
		beta2unsew(d) ;
		beta2unsew(ne) ;
		beta2unsew(e) ;
		beta2unsew(nd) ;
144 145
		GMap1::collapseEdge(nd) ;
		GMap1::collapseEdge(ne) ;
146 147 148
		beta2sew(d, beta0(e)) ;
		beta2sew(e, beta0(d)) ;
		return true ;
149
	}
150
	return false ;
151 152 153
}

Dart GMap2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
154
{
155
	Dart resV = NIL ;
156 157

	Dart e = phi2(d);
158 159
	beta2unsew(d);	// Unlink the opposite edges
	beta2unsew(e);
160

161 162
	Dart f = phi1(e) ;
	Dart h = alpha1(e);
163

164 165
	if (h != e)
		resV = h;
166

167 168 169 170 171 172 173
	if (f != e && delDegenerateFaces)
	{
		GMap1::collapseEdge(e) ;		// Collapse edge e
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
	}
	else
		GMap1::collapseEdge(e) ;	// Just collapse edge e
174

175
	f = phi1(d) ;
176
	if(resV == NIL)
177
	{
178 179 180
		h = alpha1(d);
		if (h != d)
			resV = h;
181 182
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
183 184
	if (f != d && delDegenerateFaces)
	{
185 186
		GMap1::collapseEdge(d) ;		// Collapse edge d
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
187 188
	}
	else
189
		GMap1::collapseEdge(d) ;	// Just collapse edge d
190 191

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
192 193 194 195
}

bool GMap2::flipEdge(Dart d)
{
196
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
197
	{
198
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
199 200 201 202
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
		Dart dNext2 = phi1(dNext);
		Dart eNext2 = phi1(eNext);

		beta1unsew(d) ;
		beta1unsew(eNext) ;
		beta1unsew(e) ;
		beta1unsew(dNext) ;
		beta1unsew(dNext2) ;
		beta1unsew(eNext2) ;

		beta1sew(beta0(e), eNext2) ;
		beta1sew(d, beta0(eNext)) ;
		beta1sew(beta0(d), dNext2) ;
		beta1sew(e, beta0(dNext)) ;
		beta1sew(eNext, beta0(dPrev)) ;
		beta1sew(dNext, beta0(ePrev)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
220 221 222 223 224 225 226
		return true ;
	}
	return false ; // cannot flip a border edge
}

bool GMap2::flipBackEdge(Dart d)
{
227
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
228
	{
229
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
230 231 232 233
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250
		Dart dPrev1 = beta1(dPrev) ;
		Dart ePrev1 = beta1(ePrev) ;

		beta1unsew(d) ;
		beta1unsew(eNext) ;
		beta1unsew(e) ;
		beta1unsew(dNext) ;
		beta1unsew(dPrev) ;
		beta1unsew(ePrev) ;

		beta1sew(beta0(e), dPrev) ;
		beta1sew(d, dPrev1) ;
		beta1sew(beta0(d), ePrev) ;
		beta1sew(e, ePrev1) ;
		beta1sew(eNext, beta0(dPrev)) ;
		beta1sew(dNext, beta0(ePrev)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
251 252 253 254 255
		return true ;
	}
	return false ; // cannot flip a border edge
}

256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
//void GMap2::insertEdgeInVertex(Dart d, Dart e)
//{
//	assert(!sameVertex(d,e) && phi2(e)==phi_1(e));
//
//	phi1sew(phi_1(d),phi_1(e));
//}
//
//void GMap2::removeEdgeFromVertex(Dart d)
//{
//	assert(phi2(d)!=d);
//
//	phi1sew(phi_1(d),phi2(d));
//}

void GMap2::sewFaces(Dart d, Dart e, bool withBoundary)
271
{
272 273 274 275 276 277 278 279
	// if sewing with fixed points
	if (!withBoundary)
	{
		assert(beta2(d) == d && beta2(beta0(d)) == beta0(d) && beta2(e) == e && beta2(beta0(e)) == beta0(e)) ;
		beta2sew(d, beta0(e)) ;
		beta2sew(e, beta0(d)) ;
		return ;
	}
280

281
	assert(isBoundaryEdge(d) && isBoundaryEdge(e)) ;
282

283 284
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
285

286 287 288 289
	beta2unsew(d) ;	// unsew faces from boundary
	beta2unsew(beta0(d)) ;
	beta2unsew(e) ;
	beta2unsew(beta0(e)) ;
290

291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
	if (ee != phi_1(dd))
	{
		Dart eeN = phi1(ee) ;		// remove the boundary edge
		Dart dd1 = beta1(dd) ;
		beta1unsew(eeN) ;
		beta1unsew(dd1) ;
		beta1sew(beta0(ee), dd) ;
		beta1sew(eeN, dd1) ;
	}
	if (dd != phi_1(ee))
	{
		Dart ddN = phi1(dd) ;		// and properly close incident boundaries
		Dart ee1 = beta1(ee) ;
		beta1unsew(ddN) ;
		beta1unsew(ee1) ;
		beta1sew(beta0(dd), ee) ;
		beta1sew(ddN, ee1) ;
	}
	GMap1::deleteFace(dd) ;

	beta2sew(d, beta0(e)) ; // sew the faces
	beta2sew(e, beta0(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
313 314 315 316
}

void GMap2::unsewFaces(Dart d)
{
317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352
	assert(!isBoundaryEdge(d)) ;

	Dart dd = phi2(d);

	Dart e = newBoundaryFace(2);
	Dart ee = phi1(e) ;

	if (isBoundaryVertex(d))
	{
		Dart f = findBoundaryEdgeOfVertex(d);
		Dart f1 = beta1(f) ;
		beta1unsew(ee) ;
		beta1unsew(f) ;
		beta1sew(f, beta0(e)) ;
		beta1sew(f1, ee) ;
	}

	if (isBoundaryVertex(dd))
	{
		Dart f = findBoundaryEdgeOfVertex(dd);
		Dart f1 = beta1(f) ;
		beta1unsew(e) ;
		beta1unsew(f) ;
		beta1sew(f, beta0(ee)) ;
		beta1sew(f1, e) ;
	}

	beta2unsew(d) ;
	beta2unsew(beta0(d)) ;
	beta2unsew(dd) ;
	beta2unsew(beta0(dd)) ;

	beta2sew(d, beta0(e)) ;		// sew faces
	beta2sew(e, beta0(d)) ;
	beta2sew(dd, beta0(ee)) ;	// to the boundary
	beta2sew(ee, beta0(dd)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
353 354 355 356 357 358 359
}

bool GMap2::collapseDegeneratedFace(Dart d)
{
	Dart e = phi1(d);				// Check if the face is a loop
	if (phi1(e) == d)				// Yes: it contains one or two edge(s)
	{
360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381
		Dart d2 = phi2(d) ;			// Check opposite edges
		Dart e2 = phi2(e) ;
		beta2unsew(d) ;
		beta2unsew(beta0(d)) ;
		if(d != e)
		{
			beta2unsew(e) ;
			beta2unsew(beta0(e)) ;
			beta2sew(d2, beta0(e2)) ;
			beta2sew(e2, beta0(d2)) ;
		}
		else
		{
			Dart d21 = beta1(d2) ;
			Dart d2N = phi1(d2) ;
			beta1unsew(d2) ;
			beta1unsew(d2N) ;
			beta1sew(d21, d2N) ;
			beta1sew(d2, beta0(d2)) ;
			GMap1::deleteFace(d2) ;
		}
		GMap1::deleteFace(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
382 383 384 385 386 387 388
		return true ;
	}
	return false ;
}

void GMap2::splitFace(Dart d, Dart e)
{
389 390 391 392 393 394 395 396 397 398
	assert(d != e && sameFace(d, e)) ;

	if(!sameOrientedFace(d, e))
		e = beta1(e) ;

	GMap1::cutEdge(phi_1(d)) ;
	GMap1::cutEdge(phi_1(e)) ;
	GMap1::splitFace(phi_1(d), phi_1(e)) ;
	beta2sew(phi_1(d), beta1(e)) ;
	beta2sew(phi_1(e), beta1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
399 400 401 402
}

bool GMap2::mergeFaces(Dart d)
{
403
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
404
	{
405 406 407 408 409 410
		Dart e = phi2(d) ;
		beta2unsew(d) ;
		beta2unsew(e) ;
		GMap1::mergeFaces(d, phi1(e)) ;
		GMap1::mergeFaces(e, phi1(d)) ;
		GMap1::deleteFace(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
411 412 413 414 415 416 417 418
		return true ;
	}
	return false ;
}

void GMap2::extractTrianglePair(Dart d)
{
	Dart e = phi2(d) ;
419 420 421 422

	assert(!isBoundaryFace(d) && !isBoundaryFace(e)) ;
	assert(faceDegree(d) == 3 && faceDegree(e) == 3) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
423 424
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
425 426 427 428 429 430 431 432 433 434 435 436 437 438 439
	beta2unsew(d1) ;
	beta2unsew(beta0(d1)) ;
	beta2unsew(d2) ;
	beta2unsew(beta0(d2)) ;
	beta2sew(d1, beta0(d2)) ;
	beta2sew(d2, beta0(d1)) ;

	Dart e1 = phi2(phi1(e)) ;
	Dart e2 = phi2(phi_1(e)) ;
	beta2unsew(e1) ;
	beta2unsew(beta0(e1)) ;
	beta2unsew(e2) ;
	beta2unsew(beta0(e2)) ;
	beta2sew(e1, beta0(e2)) ;
	beta2sew(e2, beta0(e1)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
440 441 442 443 444
}

void GMap2::insertTrianglePair(Dart d, Dart v1, Dart v2)
{
	Dart e = phi2(d) ;
445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469

	assert(v1 != v2 && sameOrientedVertex(v1, v2)) ;
	assert(faceDegree(d) == 3 && faceDegree(phi2(d)) == 3) ;

	Dart vv1 = phi2(v1) ;
	beta2unsew(v1) ;
	beta2unsew(vv1) ;
	beta2sew(phi_1(d), beta0(v1)) ;
	beta2sew(beta1(d), v1) ;
	beta2sew(phi1(d), beta0(vv1)) ;
	beta2sew(beta0(phi1(d)), vv1) ;

	Dart vv2 = phi2(v2) ;
	beta2unsew(v2) ;
	beta2unsew(vv2) ;
	beta2sew(phi_1(e), beta0(v2)) ;
	beta2sew(beta1(e), v2) ;
	beta2sew(phi1(e), beta0(vv2)) ;
	beta2sew(beta0(phi1(e)), vv2) ;
}

void GMap2::unsewAroundVertex(Dart d)
{
	Dart it = d ;
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
470
	{
471 472 473 474 475 476 477 478 479 480
		Dart temp = phi1(it) ;
		Dart e_1 = phi_1(it) ;

		do
		{
			unsewFaces(temp) ;
			temp = phi1(temp) ;
		} while(temp != e_1);

		it = alpha1(it);
Pierre Kraemer's avatar
Pierre Kraemer committed
481
	}
482
	while(it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
483 484 485 486
}

bool GMap2::mergeVolumes(Dart d, Dart e)
{
487 488 489 490 491
	assert(!isBoundaryMarked(d) && !isBoundaryMarked(e)) ;

	if (isBoundaryFace(d) || isBoundaryFace(e))
		return false;

Pierre Kraemer's avatar
Pierre Kraemer committed
492
	// First traversal of both faces to check the face sizes
493 494
	// and store their edges to efficiently access them further

Pierre Kraemer's avatar
Pierre Kraemer committed
495 496
	std::vector<Dart> dDarts;
	std::vector<Dart> eDarts;
497
	dDarts.reserve(16);		// usual faces have less than 16 edges
Pierre Kraemer's avatar
Pierre Kraemer committed
498 499 500
	eDarts.reserve(16);

	Dart dFit = d ;
501
	Dart eFit = phi1(e) ;	// must take phi1 because of the use
Pierre Kraemer's avatar
Pierre Kraemer committed
502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523
	do						// of reverse iterator for sewing loop
	{
		dDarts.push_back(dFit) ;
		dFit = phi1(dFit) ;
	} while(dFit != d) ;
	do
	{
		eDarts.push_back(eFit) ;
		eFit = phi1(eFit) ;
	} while(eFit != phi1(e)) ;

	if(dDarts.size() != eDarts.size())
		return false ;

	// Make the sewing: take darts in initial order (clockwise) in first face
	// and take darts in reverse order (counter-clockwise) in the second face
	std::vector<Dart>::iterator dIt;
	std::vector<Dart>::reverse_iterator eIt;
	for (dIt = dDarts.begin(), eIt = eDarts.rbegin(); dIt != dDarts.end(); ++dIt, ++eIt)
	{
		Dart d2 = phi2(*dIt);			// Search the faces adjacent to dNext and eNext
		Dart e2 = phi2(*eIt);
524 525 526 527 528 529
		beta2unsew(d2);		// Unlink the two adjacent faces from dNext and eNext
		beta2unsew(beta0(d2));
		beta2unsew(e2);
		beta2unsew(beta0(e2));
		beta2sew(d2, beta0(e2));	// Link the two adjacent faces together
		beta2sew(e2, beta0(d2));
Pierre Kraemer's avatar
Pierre Kraemer committed
530
	}
531 532
	deleteFace(d);		// Delete the two alone faces
	deleteFace(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
533 534 535 536 537 538 539 540

	return true ;
}

/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

Thomas's avatar
Thomas committed
541 542
bool GMap2::sameOrientedVertex(Dart d, Dart e)
{
543
	Dart it = d;
Thomas's avatar
Thomas committed
544 545
	do
	{
546
		if (it == e)	// Test equality with e
Thomas's avatar
Thomas committed
547
			return true;
548 549 550
		it = alpha1(it);
	} while (it != d);
	return false;		// None is equal to e => vertices are distinct
Thomas's avatar
Thomas committed
551 552
}

553 554 555 556 557 558 559 560 561 562 563
unsigned int GMap2::vertexDegree(Dart d)
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = alpha1(it) ;
	} while (it != d) ;
	return count ;
}
Thomas's avatar
Thomas committed
564

565
bool GMap2::isBoundaryVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
566
{
567
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
568 569
	do
	{
570 571 572 573 574
		if (isBoundaryMarked(it))
			return true ;
		it = alpha1(it) ;
	} while (it != d) ;
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
575 576
}

577
Dart GMap2::findBoundaryEdgeOfVertex(Dart d)
578
{
579
	Dart it = d ;
580 581
	do
	{
582 583 584 585 586
		if (isBoundaryMarked(it))
			return it ;
		it = alpha1(it) ;
	} while (it != d) ;
	return NIL ;
587 588
}

589
bool GMap2::isBoundaryEdge(Dart d)
590
{
591 592 593 594 595 596 597
	Dart e = beta2(d);
	return isBoundaryMarked(e) || isBoundaryMarked(d);
}

bool GMap2::isBoundaryFace(Dart d)
{
	Dart it = d ;
598 599
	do
	{
600
		if (isBoundaryMarked(beta2(it)))
601
			return true ;
602 603
		it = phi1(it) ;
	} while (it != d) ;
604 605 606
	return false ;
}

Thomas's avatar
Thomas committed
607 608 609 610 611 612 613 614 615
bool GMap2::sameOrientedVolume(Dart d, Dart e)
{
	DartMarkerStore mark(*this);	// Lock a marker

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

	// For every face added to the list
616
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Thomas's avatar
Thomas committed
617
	{
618
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
Thomas's avatar
Thomas committed
619
		{
620
			Dart it = *face ;
Thomas's avatar
Thomas committed
621 622
			do
			{
623
				if(it == e)
Thomas's avatar
Thomas committed
624 625
					return true;

626 627 628
				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
				if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
Thomas's avatar
Thomas committed
629
					visitedFaces.push_back(adj);	// Add it
630 631
				it = phi1(it);
			} while(it != *face);
Thomas's avatar
Thomas committed
632 633 634 635 636
		}
	}
	return false;
}

637
unsigned int GMap2::volumeDegree(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
638
{
639 640
	unsigned int count = 0;
	DartMarkerStore mark(*this);		// Lock a marker
641

642 643 644 645
	std::vector<Dart> visitedFaces;		// Faces that are traversed
	visitedFaces.reserve(16);
	visitedFaces.push_back(d);			// Start with the face of d
	std::vector<Dart>::iterator face;
646 647

	// For every face added to the list
648
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
649
	{
650 651
		Dart df = visitedFaces[i];
		if (!isBoundaryMarked(df) && !mark.isMarked(df))		// Face has not been visited yet
652
		{
653 654
			++count;
			Dart it = df ;
655 656
			do
			{
657 658 659 660 661 662
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
				if ( !isBoundaryMarked(adj) && !mark.isMarked(adj) )
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
663 664
		}
	}
665 666 667 668 669 670 671 672 673 674 675 676 677

	return count;
}

bool GMap2::isTriangular()
{
	TraversorF<GMap2> t(*this) ;
	for(Dart d = t.begin(); d != t.end(); d = t.next())
	{
		if(faceDegree(d) != 3)
			return false ;
	}
	return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
678 679 680 681
}

bool GMap2::check()
{
682
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
683 684 685 686 687
	for(Dart d = begin(); d != end(); next(d))
	{
		Dart dd = beta0(d);
		if (beta0(dd) != d)	// beta0 involution ?
		{
688
			CGoGNout << "Check: beta0 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
689 690 691 692 693 694
			return false;
		}

		dd = beta1(d);
		if (beta1(dd) != d)	// beta1 involution ?
		{
695
			CGoGNout << "Check: beta1 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
696 697 698 699 700 701
			return false;
		}

		dd = beta2(d);
		if (beta2(dd) != d)	// beta2 involution ?
		{
702
			CGoGNout << "Check: beta2 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
703 704 705 706
			return false;
		}
	}

707
	CGoGNout << "Check: topology ok" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
708 709 710 711 712 713 714
	return true;
}

/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
715
bool GMap2::foreach_dart_of_oriented_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
716
{
717
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
718 719
	do
	{
720
		if (f(it))
Pierre Kraemer's avatar
Pierre Kraemer committed
721
			return true;
722 723
		it = alpha1(it);
 	} while (it != d);
724
 	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
725 726
}

Sylvain Thery's avatar
Sylvain Thery committed
727
bool GMap2::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
728 729 730 731
{
	if (f(d))
		return true ;
	Dart e = beta0(d) ;
732 733 734 735 736 737
	if (f(e))
		return true ;
	e = beta2(d) ;
	if (f(e))
		return true ;
	e = beta0(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
738 739 740 741 742 743
	if (f(e))
		return true ;

	return false ;
}

744 745 746 747 748 749 750 751 752 753 754 755
bool GMap2::foreach_dart_of_oriented_volume(Dart d, FunctorType& f, unsigned int thread)
{
	DartMarkerStore mark(*this,thread);	// Lock a marker
	bool found = false;				// Last functor return value

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

	// For every face added to the list
	for (face = visitedFaces.begin(); !found && face != visitedFaces.end(); ++face)
	{
756
		if (!isBoundaryMarked(*face) && !mark.isMarked(*face))		// Face has not been visited yet
757 758 759 760 761 762 763 764 765 766 767 768 769
		{
			// Apply functor to the darts of the face
			found = foreach_dart_of_oriented_face(*face, f);

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
				Dart dNext = *face ;
				do
				{
					mark.mark(dNext);					// Mark
					Dart adj = phi2(dNext);				// Get adjacent face
770
					if (!isBoundaryMarked(adj) && !mark.isMarked(adj))
771 772 773 774 775 776 777 778 779
						visitedFaces.push_back(adj);	// Add it
					dNext = phi1(dNext);
				} while(dNext != *face);
			}
		}
	}
	return found;
}

780 781 782 783 784
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/

unsigned int GMap2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
785
{
786
	assert(beta2(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
787

788 789
	Dart first = newEdge();		// First edge of the face that will fill the hole
	unsigned int countEdges = 1;
Pierre Kraemer's avatar
Pierre Kraemer committed
790

791 792
	beta2sew(d, beta0(first));	// sew the new edge to the hole
	beta2sew(first, beta0(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
793

794 795 796
	Dart dNext = d;	// Turn around the hole
	Dart dPhi1;		// to complete the face
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
797
	{
798 799 800
		dPhi1 = phi1(dNext) ;
		dNext = beta2(dPhi1) ;
		while(dNext != dPhi1)
Pierre Kraemer's avatar
Pierre Kraemer committed
801
		{
802 803
			dPhi1 = beta1(dNext) ;	// Search and put in dNext
			dNext = beta2(dPhi1) ;	// the next dart of the hole
Pierre Kraemer's avatar
Pierre Kraemer committed
804
		}
805 806

		if (dPhi1 != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
807
		{
808 809 810 811 812 813 814
			Dart next = newEdge();	// Add a new edge there and link it to the face
			++countEdges;
			Dart tmp = phi1(first) ;
			beta1sew(beta0(first), next);	// the edge is linked to the face
			beta1sew(beta0(next), tmp) ;
			beta2sew(dNext, beta0(next));	// the face is linked to the hole
			beta2sew(next, beta0(dNext));
Pierre Kraemer's avatar
Pierre Kraemer committed
815
		}
816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838
	} while (dPhi1 != d);

	if (countEdges < 3)
	{
		countEdges = 0 ;
		collapseDegeneratedFace(first); // if the closing face is 2-sided, collapse it
	}
	else
	{
		if(forboundary)
			boundaryMarkOrbit(FACE, phi2(d));
	}

	return countEdges ;
}

void GMap2::closeMap()
{
	// Search the map for topological holes (fix points of phi2)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (beta2(d) == d)
			closeHole(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
839 840 841 842
	}
}

} // namespace CGoGN