gmap2.cpp 21.4 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
 *************************************************************************/

Thomas's avatar
Thomas committed
613 614
bool GMap2::sameOrientedVertex(Dart d, Dart e)
{
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
}

625 626 627 628 629 630 631 632 633 634 635
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
636

637
bool GMap2::isBoundaryVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
638
{
639
	Dart it = d ;
Pierre Kraemer's avatar
Pierre Kraemer committed
640 641
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
642
		if (isBoundaryMarked2(it))
643 644 645 646
			return true ;
		it = alpha1(it) ;
	} while (it != d) ;
	return false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
647 648
}

649
Dart GMap2::findBoundaryEdgeOfVertex(Dart d)
650
{
651
	Dart it = d ;
652 653
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
654
		if (isBoundaryMarked2(it))
655 656 657 658
			return it ;
		it = alpha1(it) ;
	} while (it != d) ;
	return NIL ;
659 660
}

661 662 663
bool GMap2::isBoundaryFace(Dart d)
{
	Dart it = d ;
664 665
	do
	{
Thery Sylvain's avatar
Thery Sylvain committed
666
		if (isBoundaryMarked2(beta2(it)))
667
			return true ;
668 669
		it = phi1(it) ;
	} while (it != d) ;
670 671 672
	return false ;
}

Thomas's avatar
Thomas committed
673 674 675 676 677 678 679 680 681
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
682
	for (face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Thomas's avatar
Thomas committed
683
	{
Thery Sylvain's avatar
Thery Sylvain committed
684
		if (!isBoundaryMarked2(*face) && !mark.isMarked(*face))		// Face has not been visited yet
Thomas's avatar
Thomas committed
685
		{
686
			Dart it = *face ;
Thomas's avatar
Thomas committed
687 688
			do
			{
689
				if(it == e)
Thomas's avatar
Thomas committed
690 691
					return true;

692 693
				mark.mark(it);						// Mark
				Dart adj = phi2(it);				// Get adjacent face
Thery Sylvain's avatar
Thery Sylvain committed
694
				if (!isBoundaryMarked2(adj) && !mark.isMarked(adj))
Thomas's avatar
Thomas committed
695
					visitedFaces.push_back(adj);	// Add it
696 697
				it = phi1(it);
			} while(it != *face);
Thomas's avatar
Thomas committed
698 699 700 701 702
		}
	}
	return false;
}

703
unsigned int GMap2::volumeDegree(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
704
{
705 706
	unsigned int count = 0;
	DartMarkerStore mark(*this);		// Lock a marker
707

708 709 710 711
	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;
712 713

	// For every face added to the list
714
	for (unsigned int i = 0; i != visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
715
	{
716
		Dart df = visitedFaces[i];
Thery Sylvain's avatar
Thery Sylvain committed
717
		if (!isBoundaryMarked2(df) && !mark.isMarked(df))		// Face has not been visited yet
718
		{
719 720
			++count;
			Dart it = df ;
721 722
			do
			{
723 724
				mark.mark(it);					// Mark
				Dart adj = phi2(it);			// Get adjacent face
Thery Sylvain's avatar
Thery Sylvain committed
725
				if ( !isBoundaryMarked2(adj) && !mark.isMarked(adj) )
726 727 728
					visitedFaces.push_back(adj);// Add it
				it = phi1(it);
			} while(it != df);
729 730
		}
	}
731 732 733 734 735 736 737 738 739 740 741 742 743

	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
744 745 746 747
}

bool GMap2::check()
{
748
	CGoGNout << "Check: topology begin" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
749 750 751 752 753
	for(Dart d = begin(); d != end(); next(d))
	{
		Dart dd = beta0(d);
		if (beta0(dd) != d)	// beta0 involution ?
		{
754
			CGoGNout << "Check: beta0 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
755 756 757 758 759 760
			return false;
		}

		dd = beta1(d);
		if (beta1(dd) != d)	// beta1 involution ?
		{
761
			CGoGNout << "Check: beta1 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
762 763 764 765 766 767
			return false;
		}

		dd = beta2(d);
		if (beta2(dd) != d)	// beta2 involution ?
		{
768
			CGoGNout << "Check: beta2 is not an involution" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
769 770
			return false;
		}
771 772
		if(dd == d)
			CGoGNout << "Check (warning): beta2 has fix points" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
773 774
	}

775
	CGoGNout << "Check: topology ok" << CGoGNendl;
776

Pierre Kraemer's avatar
Pierre Kraemer committed
777 778 779
	return true;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
780 781 782 783 784 785 786
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
787
		
788
		dm.markOrbit<VERTEX>(*it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
789 790 791 792 793 794 795 796 797 798 799 800 801

		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
802 803 804 805
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

Sylvain Thery's avatar
Sylvain Thery committed
806
bool GMap2::foreach_dart_of_oriented_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
807
{
808
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
809 810
	do
	{
811
		if (f(it))
Pierre Kraemer's avatar
Pierre Kraemer committed
812
			return true;
813 814
		it = alpha1(it);
 	} while (it != d);
815
 	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
816 817
}

818 819 820 821 822 823 824 825 826 827 828
bool GMap2::foreach_dart_of_oriented_edge(Dart d, FunctorType& f, unsigned int thread)
{
	if (f(d))
		return true ;
	Dart e = beta2(beta0(d)) ;
	if (f(e))
		return true ;

	return false ;
}

Sylvain Thery's avatar
Sylvain Thery committed
829
bool GMap2::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
830 831 832 833
{
	if (f(d))
		return true ;
	Dart e = beta0(d) ;
834 835 836 837 838 839
	if (f(e))
		return true ;
	e = beta2(d) ;
	if (f(e))
		return true ;
	e = beta0(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
840 841 842 843 844 845
	if (f(e))
		return true ;

	return false ;
}

846
bool GMap2::foreach_dart_of_oriented_cc(Dart d, FunctorType& f, unsigned int thread)
847
{
Pierre Kraemer's avatar
Pierre Kraemer committed
848
	DartMarkerStore mark(*this, thread);	// Lock a marker
849 850
	bool found = false;				// Last functor return value

Pierre Kraemer's avatar
Pierre Kraemer committed
851 852
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
853 854 855
	visitedFaces.push_back(d);		// Start with the face of d

	// For every face added to the list
856
	for(unsigned int i = 0; !found && i < visitedFaces.size(); ++i)
857
	{
858
		if (!mark.isMarked(visitedFaces[i]))		// Face has not been visited yet
859 860
		{
			// Apply functor to the darts of the face
861
			found = foreach_dart_of_oriented_face(visitedFaces[i], f);
862 863 864 865 866

			// If functor returns false then mark visited darts (current face)
			// and add non visited adjacent faces to the list of face
			if (!found)
			{
867
				Dart e = visitedFaces[i] ;
868 869
				do
				{
Pierre Kraemer's avatar
Pierre Kraemer committed
870 871
					mark.mark(e);					// Mark
					Dart adj = phi2(e);				// Get adjacent face
Pierre Kraemer's avatar
Pierre Kraemer committed
872
					if (!mark.isMarked(adj))
873
						visitedFaces.push_back(adj);	// Add it
Pierre Kraemer's avatar
Pierre Kraemer committed
874
					e = phi1(e);
875
				} while(e != visitedFaces[i]);
876 877 878 879 880 881
			}
		}
	}
	return found;
}

882 883 884 885
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/

886 887 888 889 890 891 892
Dart GMap2::newBoundaryCycle(unsigned int nbE)
{
	Dart d = GMap1::newCycle(nbE);
	boundaryMarkOrbit<FACE,2>(d);
	return d;
}

893
unsigned int GMap2::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
894
{
895
	assert(beta2(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
896

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

900 901
	beta2sew(d, beta0(first));	// sew the new edge to the hole
	beta2sew(first, beta0(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
902

903
	Dart prev = first ;
904 905 906
	Dart dNext = d;	// Turn around the hole
	Dart dPhi1;		// to complete the face
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
907
	{
908 909
		dPhi1 = phi1(dNext) ;
		dNext = beta2(dPhi1) ;
910
		while(dNext != dPhi1 && dPhi1 != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
911
		{
912 913
			dPhi1 = beta1(dNext) ;	// Search and put in dNext
			dNext = beta2(dPhi1) ;	// the next dart of the hole
Pierre Kraemer's avatar
Pierre Kraemer committed
914
		}
915 916

		if (dPhi1 != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
917
		{
918 919
			Dart next = newEdge();	// Add a new edge there and link it to the face
			++countEdges;
920 921
			beta1sew(beta0(next), prev);	// the edge is linked to the face
			prev = next ;
922 923
			beta2sew(dNext, beta0(next));	// the face is linked to the hole
			beta2sew(next, beta0(dNext));
Pierre Kraemer's avatar
Pierre Kraemer committed
924
		}
925 926
	} while (dPhi1 != d);

927 928
	beta1sew(prev, beta0(first)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
929
	if(forboundary)
Thery Sylvain's avatar
Thery Sylvain committed
930
		boundaryMarkOrbit<FACE,2>(phi2(d));
931 932 933 934

	return countEdges ;
}

935
unsigned int GMap2::closeMap()
936 937
{
	// Search the map for topological holes (fix points of phi2)
938
	unsigned int nb = 0 ;
939 940 941
	for (Dart d = begin(); d != end(); next(d))
	{
		if (beta2(d) == d)
942 943
		{
			++nb ;
944
			closeHole(d);
945
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
946
	}
947
	return nb ;
Pierre Kraemer's avatar
Pierre Kraemer committed
948 949
}

950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965
/*! @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
966
} // namespace CGoGN