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

#include "Topology/gmap/gmap2.h"
26
#include "Topology/generic/traversorCell.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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
void GMap2::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))
	{
		{
			Dart& d = m_beta0->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
		{
			Dart& d = m_beta1->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
		{
			Dart& d = m_beta2->operator [](i);
			Dart e = Dart(oldnew[d.index]);
			if (d != e)
				d = e;
		}
	}
}

56 57
/*! @name Generator and Deletor
 *  To generate or delete faces in a 2-G-map
Pierre Kraemer's avatar
Pierre Kraemer committed
58 59
 *************************************************************************/

60 61
Dart GMap2::newFace(unsigned int nbEdges, bool withBoundary)
{
62
	Dart d = GMap1::newCycle(nbEdges);
63 64
	if (withBoundary)
	{
65
		Dart e = newBoundaryCycle(nbEdges);
66 67 68 69 70 71 72 73 74 75 76 77 78

		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
79 80
void GMap2::deleteFace(Dart d)
{
Thery Sylvain's avatar
Thery Sylvain committed
81
	assert(!isBoundaryMarked2(d)) ;
82
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
83 84
	do
	{
85 86 87 88 89
		if(!isBoundaryEdge(it))
			unsewFaces(it) ;
		it = phi1(it) ;
	} while(it != d) ;
	Dart dd = phi2(d) ;
90 91
	GMap1::deleteCycle(d) ;
	GMap1::deleteCycle(dd) ;
92 93
}

Pierre Kraemer's avatar
Pierre Kraemer committed
94 95 96 97 98 99 100 101 102
void GMap2::deleteCC(Dart d)
{
	DartMarkerStore mark(*this);

	std::vector<Dart> visited;
	visited.reserve(1024) ;
	visited.push_back(d);
	mark.mark(d) ;

103
	for(unsigned int i = 0; i < visited.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
104
	{
105
		Dart d0 = beta0(visited[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
106 107 108 109 110
		if(!mark.isMarked(d0))
		{
			visited.push_back(d0) ;
			mark.mark(d0);
		}
111
		Dart d1 = beta1(visited[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
112 113 114 115 116
		if(!mark.isMarked(d1))
		{
			visited.push_back(d1) ;
			mark.mark(d1);
		}
117
		Dart d2 = beta2(visited[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
118 119 120 121 122 123 124 125 126 127 128
		if(!mark.isMarked(d2))
		{
			visited.push_back(d2) ;
			mark.mark(d2);
		}
	}

	for(std::vector<Dart>::iterator it = visited.begin(); it != visited.end(); ++it)
		deleteDart(*it) ;
}

129 130
void GMap2::fillHole(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
131 132
	assert(isBoundaryEdge(d)) ;
	Dart dd = d ;
Thery Sylvain's avatar
Thery Sylvain committed
133
	if(!isBoundaryMarked2(dd))
Pierre Kraemer's avatar
Pierre Kraemer committed
134
		dd = phi2(dd) ;
Thery Sylvain's avatar
Thery Sylvain committed
135
	boundaryUnmarkOrbit<FACE,2>(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
136 137 138 139 140 141 142 143
}

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

void GMap2::splitVertex(Dart d, Dart e)
{
144
	assert(sameVertex(d, e));
Pierre Kraemer's avatar
Pierre Kraemer committed
145 146 147 148

	if(!sameOrientedVertex(d, e))
		e = beta2(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
149 150
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
151 152 153
	beta2unsew(d) ;
	beta2unsew(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
154 155
	GMap1::cutEdge(dd);			// Cut the edge of dd (make a new edge)
	GMap1::cutEdge(ee);			// Cut the edge of ee (make a new edge)
Pierre Kraemer's avatar
Pierre Kraemer committed
156

157 158
	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
159 160
	beta2sew(d, beta0(dd)) ;
	beta2sew(e, beta0(ee)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
161 162
}

163
Dart GMap2::deleteVertex(Dart d)
164 165
{
	if(isBoundaryVertex(d))
166
		return NIL ;
167

168
	Dart res = NIL ;
169 170 171
	Dart vit = d ;
	do
	{
172 173 174 175 176 177 178 179 180 181 182 183
		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) ;

184 185
		vit = alpha1(vit) ;
	} while(vit != d) ;
186
	GMap1::deleteCycle(d) ;
187
	return res ;
188 189
}

190
Dart GMap2::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
191
{
192
	Dart e = phi2(d) ;
193 194
	Dart nd = GMap1::cutEdge(d) ;
	Dart ne = GMap1::cutEdge(e) ;
195

196 197
	beta2sew(nd, beta1(ne)) ;
	beta2sew(ne, beta1(nd)) ;
198 199

	return nd ;
Pierre Kraemer's avatar
Pierre Kraemer committed
200 201
}

202
bool GMap2::uncutEdge(Dart d)
203
{
204
	if(vertexDegree(phi1(d)) == 2)
205
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
206 207
		GMap1::uncutEdge(d) ;
		GMap1::uncutEdge(beta2(d)) ;
208
		return true ;
209
	}
210
	return false ;
211 212 213
}

Dart GMap2::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
214
{
215
	Dart resV = NIL ;
216 217

	Dart e = phi2(d);
218 219
	beta2unsew(d);	// Unlink the opposite edges
	beta2unsew(e);
220

221 222
	Dart f = phi1(e) ;
	Dart h = alpha1(e);
223

224 225
	if (h != e)
		resV = h;
226

227 228 229 230 231 232 233
	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
234

235
	f = phi1(d) ;
236
	if(resV == NIL)
237
	{
238 239 240
		h = alpha1(d);
		if (h != d)
			resV = h;
241 242
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
243 244
	if (f != d && delDegenerateFaces)
	{
245 246
		GMap1::collapseEdge(d) ;		// Collapse edge d
		collapseDegeneratedFace(f) ;	// and collapse its face if degenerated
Pierre Kraemer's avatar
Pierre Kraemer committed
247 248
	}
	else
249
		GMap1::collapseEdge(d) ;	// Just collapse edge d
250 251

	return resV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
252 253 254 255
}

bool GMap2::flipEdge(Dart d)
{
256
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
257
	{
258
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
259 260 261 262
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279
		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
280 281 282 283 284 285 286
		return true ;
	}
	return false ; // cannot flip a border edge
}

bool GMap2::flipBackEdge(Dart d)
{
287
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
288
	{
289
		Dart e = phi2(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
290 291 292 293
		Dart dNext = phi1(d);
		Dart eNext = phi1(e);
		Dart dPrev = phi_1(d);
		Dart ePrev = phi_1(e);
294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
		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
311 312 313 314 315
		return true ;
	}
	return false ; // cannot flip a border edge
}

316 317 318 319 320 321 322 323 324 325 326 327 328 329 330
//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)
331
{
332 333 334 335 336 337 338 339
	// 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 ;
	}
340

341
	assert(isBoundaryEdge(d) && isBoundaryEdge(e)) ;
342

343 344
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;
345

346 347 348 349
	beta2unsew(d) ;	// unsew faces from boundary
	beta2unsew(beta0(d)) ;
	beta2unsew(e) ;
	beta2unsew(beta0(e)) ;
350

351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368
	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) ;
	}
369
	GMap1::deleteCycle(dd) ;
370 371 372

	beta2sew(d, beta0(e)) ; // sew the faces
	beta2sew(e, beta0(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
373 374 375 376
}

void GMap2::unsewFaces(Dart d)
{
377 378 379 380
	assert(!isBoundaryEdge(d)) ;

	Dart dd = phi2(d);

381
	Dart e = newBoundaryCycle(2);
382 383
	Dart ee = phi1(e) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
384 385
	Dart f = findBoundaryEdgeOfVertex(d) ;
	if (f != NIL)
386 387 388 389 390 391 392 393
	{
		Dart f1 = beta1(f) ;
		beta1unsew(ee) ;
		beta1unsew(f) ;
		beta1sew(f, beta0(e)) ;
		beta1sew(f1, ee) ;
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
394 395
	f = findBoundaryEdgeOfVertex(dd) ;
	if (f != NIL)
396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412
	{
		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
413 414 415 416 417 418 419
}

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)
	{
420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438
		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)) ;
439
			GMap1::deleteCycle(d2) ;
440
		}
441
		GMap1::deleteCycle(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
442 443 444 445 446 447 448
		return true ;
	}
	return false ;
}

void GMap2::splitFace(Dart d, Dart e)
{
449 450 451 452 453
	assert(d != e && sameFace(d, e)) ;

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

Pierre Kraemer's avatar
Pierre Kraemer committed
454 455 456
	Dart dprev = phi_1(d) ;
	Dart eprev = phi_1(e) ;

457 458
	//required to unsew and resew because we use GMap1 cutEdge
	//which insert new darts within the cut edge
Pierre Kraemer's avatar
Pierre Kraemer committed
459 460 461
	beta2unsew(beta1(d)) ;
	beta2unsew(beta1(e)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
462 463
	Dart dd = GMap1::cutEdge(phi_1(d)) ;
	Dart ee = GMap1::cutEdge(phi_1(e)) ;
464
	GMap1::splitCycle(dd, ee) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
465 466
	beta2sew(dd, beta1(e)) ;
	beta2sew(ee, beta1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
467 468 469

	beta2sew(beta0(dprev), beta0(beta2(dprev))) ;
	beta2sew(beta0(eprev), beta0(beta2(eprev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
470 471 472 473
}

bool GMap2::mergeFaces(Dart d)
{
474
	if (!isBoundaryEdge(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
475
	{
476 477 478
		Dart e = phi2(d) ;
		beta2unsew(d) ;
		beta2unsew(e) ;
479
		GMap1::mergeCycles(d, phi1(e)) ;
480
		GMap1::splitCycle(e, phi1(d)) ;
481
		GMap1::deleteCycle(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
482 483 484 485 486 487 488 489
		return true ;
	}
	return false ;
}

void GMap2::extractTrianglePair(Dart d)
{
	Dart e = phi2(d) ;
490 491 492 493

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

Pierre Kraemer's avatar
Pierre Kraemer committed
494 495
	Dart d1 = phi2(phi1(d)) ;
	Dart d2 = phi2(phi_1(d)) ;
496 497 498 499 500 501 502 503 504 505 506 507 508 509 510
	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
511 512 513 514 515
}

void GMap2::insertTrianglePair(Dart d, Dart v1, Dart v2)
{
	Dart e = phi2(d) ;
516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536

	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) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
537 538
bool GMap2::mergeVolumes(Dart d, Dart e)
{
Thery Sylvain's avatar
Thery Sylvain committed
539
	assert(!isBoundaryMarked2(d) && !isBoundaryMarked2(e)) ;
540

Pierre Kraemer's avatar
Pierre Kraemer committed
541
	if (GMap2::isBoundaryFace(d) || GMap2::isBoundaryFace(e))
542 543
		return false;

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

Pierre Kraemer's avatar
Pierre Kraemer committed
547 548
	std::vector<Dart> dDarts;
	std::vector<Dart> eDarts;
549
	dDarts.reserve(16);		// usual faces have less than 16 edges
Pierre Kraemer's avatar
Pierre Kraemer committed
550 551 552
	eDarts.reserve(16);

	Dart dFit = d ;
553
	Dart eFit = phi1(e) ;	// must take phi1 because of the use
Pierre Kraemer's avatar
Pierre Kraemer committed
554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573
	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)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
574
		Dart d2 = phi2(*dIt);	// Search the faces adjacent to dNext and eNext
Pierre Kraemer's avatar
Pierre Kraemer committed
575
		Dart e2 = phi2(*eIt);
576 577 578 579 580 581
		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
582
	}
583 584
	GMap1::deleteCycle(d);		// Delete the two alone faces
	GMap1::deleteCycle(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
585 586 587 588

	return true ;
}

589
void GMap2::splitSurface(std::vector<Dart>& vd, bool firstSideClosed, bool secondSideClosed)
untereiner's avatar
untereiner committed
590 591
{
	//assert(checkSimpleOrientedPath(vd)) ;
592 593 594 595 596 597 598 599 600 601 602 603 604 605 606
	Dart e = vd.front() ;
	Dart e2 = phi2(e) ;

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

	if(firstSideClosed)
		GMap2::fillHole(e) ;

	if(secondSideClosed)
		GMap2::fillHole(e2) ;
untereiner's avatar
untereiner committed
607 608
}

Pierre Kraemer's avatar
Pierre Kraemer committed
609 610 611 612
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
613
bool GMap2::sameOrientedVertex(Dart d, Dart e) const
Thomas's avatar
Thomas committed
614
{
615
	Dart it = d;
Thomas's avatar
Thomas committed
616 617
	do
	{
618
		if (it == e)	// Test equality with e
Thomas's avatar
Thomas committed
619
			return true;
620 621 622
		it = alpha1(it);
	} while (it != d);
	return false;		// None is equal to e => vertices are distinct
Thomas's avatar
Thomas committed
623 624
}

Sylvain Thery's avatar
Sylvain Thery committed
625
unsigned int GMap2::vertexDegree(Dart d) const
626 627 628 629 630 631 632 633 634 635
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = alpha1(it) ;
	} while (it != d) ;
	return count ;
}
Thomas's avatar
Thomas committed
636

Sylvain Thery's avatar
Sylvain Thery committed
637
int GMap2::checkVertexDegree(Dart d, unsigned int vd) const
638 639 640 641 642 643 644 645 646 647 648 649 650
{
	unsigned int count = 0 ;
	Dart it = d ;
	do
	{
		++count ;
		it = alpha1(it) ;
	} while ((count<=vd) && (it != d)) ;

	return count-vd;
}


Sylvain Thery's avatar
Sylvain Thery committed
651
bool GMap2::isBoundaryVertex(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
652
{
653
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
654 655
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
656
		if (isBoundaryMarked2(it))
657 658 659 660
			return true ;
		it = alpha1(it) ;
	} while (it != d) ;
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
661 662
}

Sylvain Thery's avatar
Sylvain Thery committed
663
Dart GMap2::findBoundaryEdgeOfVertex(Dart d) const
664
{
665
	Dart it = d ;
666 667
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
668
		if (isBoundaryMarked2(it))
669 670 671 672
			return it ;
		it = alpha1(it) ;
	} while (it != d) ;
	return NIL ;
673 674
}

Sylvain Thery's avatar
Sylvain Thery committed
675
bool GMap2::isBoundaryFace(Dart d) const
676 677
{
	Dart it = d ;
678 679
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
680
		if (isBoundaryMarked2(beta2(it)))
681
			return true ;
682 683
		it = phi1(it) ;
	} while (it != d) ;
684 685 686
	return false ;
}

Sylvain Thery's avatar
Sylvain Thery committed
687
bool GMap2::sameOrientedVolume(Dart d, Dart e) const
Thomas's avatar
Thomas committed
688 689 690 691 692 693 694 695
{
	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
696
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Thomas's avatar
Thomas committed
697
	{
Thery Sylvain's avatar
Thery Sylvain committed
698
		if (!isBoundaryMarked2(*face) && !mark.isMarked(*face))		// Face has not been visited yet
Thomas's avatar
Thomas committed
699
		{
700
			Dart it = *face ;
Thomas's avatar
Thomas committed
701 702
			do
			{
703
				if(it == e)
Thomas's avatar
Thomas committed
704 705
					return true;

706 707
				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
Thery Sylvain's avatar
Thery Sylvain committed
708
				if (!isBoundaryMarked2(adj) && !mark.isMarked(adj))
Thomas's avatar
Thomas committed
709
					visitedFaces.push_back(adj);	// Add it
710 711
				it = phi1(it);
			} while(it != *face);
Thomas's avatar
Thomas committed
712 713 714 715 716
		}
	}
	return false;
}

Sylvain Thery's avatar
Sylvain Thery committed
717
unsigned int GMap2::volumeDegree(Dart d) const
Pierre Kraemer's avatar
Pierre Kraemer committed
718
{
719 720
	unsigned int count = 0;
	DartMarkerStore mark(*this);		// Lock a marker
721

722 723 724 725
	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;
726 727

	// For every face added to the list
728
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
729
	{
730
		Dart df = visitedFaces[i];
Thery Sylvain's avatar
Thery Sylvain committed
731
		if (!isBoundaryMarked2(df) && !mark.isMarked(df))		// Face has not been visited yet
732
		{
733 734
			++count;
			Dart it = df ;
735 736
			do
			{
737 738
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
Thery Sylvain's avatar
Thery Sylvain committed
739
				if ( !isBoundaryMarked2(adj) && !mark.isMarked(adj) )
740 741 742
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
743 744
		}
	}
745 746 747 748

	return count;
}

749

Sylvain Thery's avatar
Sylvain Thery committed
750
int GMap2::checkVolumeDegree(Dart d, unsigned int volDeg) const
751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785
{
	unsigned int count = 0;
	DartMarkerStore mark(*this);		// Lock a marker

	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;

	// For every face added to the list
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
	{
		Dart df = visitedFaces[i];
		if (!isBoundaryMarked2(df) && !mark.isMarked(df))		// Face has not been visited yet
		{
			++count;
			Dart it = df ;
			do
			{
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
				if ( !isBoundaryMarked2(adj) && !mark.isMarked(adj) )
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
		}
		if (count > volDeg)
			break;
	}

	return count - volDeg;
}



Sylvain Thery's avatar
Sylvain Thery committed
786
bool GMap2::isTriangular() const
787 788 789 790 791 792 793 794
{
	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
795 796
}

Sylvain Thery's avatar
Sylvain Thery committed
797
bool GMap2::check() const
Pierre Kraemer's avatar
Pierre Kraemer committed
798
{
799
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
800 801 802 803 804
	for(Dart d = begin(); d != end(); next(d))
	{
		Dart dd = beta0(d);
		if (beta0(dd) != d)	// beta0 involution ?
		{
805
			CGoGNout << "Check: beta0 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
806 807 808 809 810 811
			return false;
		}

		dd = beta1(d);
		if (beta1(dd) != d)	// beta1 involution ?
		{
812
			CGoGNout << "Check: beta1 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
813 814 815 816 817 818
			return false;
		}

		dd = beta2(d);
		if (beta2(dd) != d)	// beta2 involution ?
		{
819
			CGoGNout << "Check: beta2 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
820 821
			return false;
		}
822 823
		if(dd == d)
			CGoGNout << "Check (warning): beta2 has fix points" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
824 825
	}

826
	CGoGNout << "Check: topology ok" << CGoGNendl;
827

Pierre Kraemer's avatar
Pierre Kraemer committed
828 829 830
	return true;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
831 832 833 834 835 836 837
bool GMap2::checkSimpleOrientedPath(std::vector<Dart>& vd)
{
	DartMarkerStore dm(*this) ;
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
		if(dm.isMarked(*it))
			return false ;
Thomas's avatar
Thomas committed
838
		
839
		dm.markOrbit<VERTEX>(*it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
840 841 842 843 844 845 846 847 848 849 850 851 852

		std::vector<Dart>::iterator prev ;
		if(it == vd.begin())
			prev = vd.end() - 1 ;
		else
			prev = it - 1 ;

		if(!sameVertex(*it, phi1(*prev)))
			return false ;
	}
	return true ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
853 854 855 856
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
857
bool GMap2::foreach_dart_of_oriented_vertex(Dart d, FunctorType& f, unsigned int /*thread*/) const
Pierre Kraemer's avatar
Pierre Kraemer committed
858
{
859
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
860 861
	do
	{
862
		if (f(it))
Pierre Kraemer's avatar
Pierre Kraemer committed
863
			return true;
864 865
		it = alpha1(it);
 	} while (it != d);
866
 	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
867 868
}

Sylvain Thery's avatar
Sylvain Thery committed
869
bool GMap2::foreach_dart_of_oriented_edge(Dart d, FunctorType& f, unsigned int /*thread*/) const
870 871 872 873 874 875 876 877 878 879
{
	if (f(d))
		return true ;
	Dart e = beta2(beta0(d)) ;
	if (f(e))
		return true ;

	return false ;
}

Sylvain Thery's avatar
Sylvain Thery committed
880
bool GMap2::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int /*thread*/) const
Pierre Kraemer's avatar
Pierre Kraemer committed
881 882 883 884
{
	if (f(d))
		return true ;
	Dart e = beta0(d) ;
885 886 887 888 889 890
	if (f(e))
		return true ;
	e = beta2(d) ;
	if (f(e))
		return true ;
	e = beta0(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
891 892 893 894 895 896
	if (f(e))
		return true ;

	return false ;
}

Sylvain Thery's avatar
Sylvain Thery committed
897
bool GMap2::foreach_dart_of_oriented_cc(Dart d, FunctorType& f, unsigned int thread) const
898
{
Pierre Kraemer's avatar
Pierre Kraemer committed
899
	DartMarkerStore mark(*this, thread);	// Lock a marker
900 901
	bool found = false;				// Last functor return value

Pierre Kraemer's avatar
Pierre Kraemer committed
902 903
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
904 905 906
	visitedFaces.push_back(d);		// Start with the face of d

	// For every face added to the list
907
	for(unsigned int i = 0; !found && i < visitedFaces.size(); ++i)
908
	{
909
		if (!mark.isMarked(visitedFaces[i]))		// Face has not been visited yet
910 911
		{
			// Apply functor to the darts of the face
912
			found = foreach_dart_of_oriented_face(visitedFaces[i], f);
913 914 915 916 917

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
918
				Dart e = visitedFaces[i] ;
919 920
				do
				{
Pierre Kraemer's avatar
Pierre Kraemer committed
921 922
					mark.mark(e);					// Mark
					Dart adj = phi2(e);				// Get adjacent face
Pierre Kraemer's avatar
Pierre Kraemer committed
923
					if (!mark.isMarked(adj))
924
						visitedFaces.push_back(adj);	// Add it
Pierre Kraemer's avatar
Pierre Kraemer committed
925
					e = phi1(e);
926
				} while(e != visitedFaces[i]);
927 928 929 930 931 932
			}
		}
	}
	return found;
}

933 934 935 936
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/

937 938 939 940 941 942 943
Dart GMap2::newBoundaryCycle(unsigned int nbE)
{
	Dart d = GMap1::newCycle(nbE);
	boundaryMarkOrbit<FACE,2>(d);
	return d;
}

944
unsigned int GMap2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
945
{
946
	assert(beta2(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
947

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

951 952
	beta2sew(d, beta0(first));	// sew the new edge to the hole
	beta2sew(first, beta0(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
953

954
	Dart prev = first ;
955 956 957
	Dart dNext = d;	// Turn around the hole
	Dart dPhi1;		// to complete the face
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
958
	{
959 960
		dPhi1 = phi1(dNext) ;
		dNext = beta2(dPhi1) ;
961
		while(dNext != dPhi1 && dPhi1 != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
962
		{
963 964
			dPhi1 = beta1(dNext) ;	// Search and put in dNext
			dNext = beta2(dPhi1) ;	// the next dart of the hole
Pierre Kraemer's avatar
Pierre Kraemer committed
965
		}
966 967

		if (dPhi1 != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
968
		{
969 970
			Dart next = newEdge();	// Add a new edge there and link it to the face
			++countEdges;
971 972
			beta1sew(beta0(next), prev);	// the edge is linked to the face
			prev = next ;
973 974
			beta2sew(dNext, beta0(next));	// the face is linked to the hole
			beta2sew(next, beta0(dNext));
Pierre Kraemer's avatar
Pierre Kraemer committed
975
		}
976 977
	} while (dPhi1 != d);

978 979
	beta1sew(prev, beta0(first)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
980
	if(forboundary)
Thery Sylvain's avatar
Thery Sylvain committed
981
		boundaryMarkOrbit<FACE,2>(phi2(d));
982 983 984 985

	return countEdges ;
}

986
unsigned int GMap2::closeMap()
987 988
{
	// Search the map for topological holes (fix points of phi2)
989
	unsigned int nb = 0 ;
990 991 992
	for (Dart d = begin(); d != end(); next(d))
	{
		if (beta2(d) == d)
993 994
		{
			++nb ;
995
			closeHole(d);
996
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
997
	}
998
	return nb ;
Pierre Kraemer's avatar
Pierre Kraemer committed
999 1000
}

1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016
/*! @name Compute dual
 * These functions compute the dual mesh
 *************************************************************************/

void GMap2::computeDual()
{
//	DartAttribute<Dart> old_beta0 = this->getAttribute<Dart, DART>("beta0");
//	DartAttribute<Dart> old_beta2 = this->getAttribute<Dart, DART>("beta2") ;
//
//	swapAttributes<Dart>(old_beta0, old_beta2) ;
//
//	swapEmbeddingContainers(VERTEX, FACE) ;
//
//	//boundary management ?
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1017
} // namespace CGoGN