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

#include "Topology/gmap/gmap3.h"
#include "Topology/generic/dartmarker.h"

namespace CGoGN
{

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

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

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

	// For every face added to the list
Pierre Kraemer's avatar
Pierre Kraemer committed
45
	for(std::vector<Dart>::iterator face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
Pierre Kraemer's avatar
Pierre Kraemer committed
46
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
47
		Dart e = *face ;
Pierre Kraemer's avatar
Pierre Kraemer committed
48

Pierre Kraemer's avatar
Pierre Kraemer committed
49 50
		if(!isBoundaryFace(e))
			unsewVolumes(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
51

Pierre Kraemer's avatar
Pierre Kraemer committed
52 53 54 55
		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
Pierre Kraemer's avatar
Pierre Kraemer committed
56
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
57 58 59 60 61
				visitedFaces.push_back(ee) ;
				mark.markOrbit(FACE, ee) ;
			}
			e = phi1(e) ;
		} while(e != *face) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
62
	}
63

Pierre Kraemer's avatar
Pierre Kraemer committed
64 65 66 67 68 69 70 71 72 73 74 75
	Dart dd = phi3(d) ;
	GMap2::deleteCC(d) ;
	GMap2::deleteCC(dd) ;
}

void GMap3::fillHole(Dart d)
{
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi3(dd) ;
	boundaryUnmarkOrbit(VOLUME, dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
76 77
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
82
Dart GMap3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
83
{
84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
	if(isBoundaryVertex(d))
		return NIL ;

	// Save the darts around the vertex
	// (one dart per face should be enough)
	std::vector<Dart> fstoretmp;
	fstoretmp.reserve(128);
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

	// just one dart per face
	std::vector<Dart> fstore;
	fstore.reserve(128);
	DartMarker mf(*this);
	for(std::vector<Dart>::iterator it = fstoretmp.begin() ; it != fstoretmp.end() ; ++it)
	{
		if(!mf.isMarked(*it))
		{
			mf.markOrbit(FACE, *it);
			fstore.push_back(*it);
		}
	}

	Dart res = NIL ;
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
		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) ;

			if(res == NIL)
				res = d2 ;

			beta2unsew(d2) ;
			beta2unsew(beta0(d2)) ;

			beta2unsew(d32) ;
			beta2unsew(beta0(d32)) ;

			beta2sew(d2, beta0(d32)) ;
			beta2sew(beta0(d2), d32) ;
			beta2sew(fit, beta0(d3)) ;
			beta2sew(beta0(fit), d3) ;
		}
	}
	GMap2::deleteCC(d) ;

	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
137 138
	return NIL ;
}
139

Pierre Kraemer's avatar
Pierre Kraemer committed
140 141 142 143 144
void GMap3::cutEdge(Dart d)
{
	Dart prev = d ;
	Dart dd = alpha2(d) ;
	GMap2::cutEdge(d) ;
145

Pierre Kraemer's avatar
Pierre Kraemer committed
146
	while(dd != d)
147
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
148 149
		prev = dd ;
		dd = alpha2(dd) ;
150

Pierre Kraemer's avatar
Pierre Kraemer committed
151
		GMap2::cutEdge(prev) ;
152

Pierre Kraemer's avatar
Pierre Kraemer committed
153 154 155
		Dart d3 = beta3(prev);
		beta3sew(beta0(prev), beta0(d3));
		beta3sew(phi1(prev), phi1(d3));
156
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
157 158 159

	Dart d3 = beta3(d);
	beta3sew(beta0(d), beta0(d3));
Pierre Kraemer's avatar
Pierre Kraemer committed
160
	beta3sew(phi1(d), phi1(d3));
Pierre Kraemer's avatar
Pierre Kraemer committed
161 162 163 164
}

bool GMap3::uncutEdge(Dart d)
{
165 166 167 168 169 170 171 172 173
	if(vertexDegree(phi1(d)) == 2)
	{
		Dart prev = d ;

		Dart dd = d;
		do
		{
			prev = dd;
			dd = alpha2(dd);
Pierre Kraemer's avatar
Pierre Kraemer committed
174

175 176 177 178 179
			GMap2::uncutEdge(prev);
		} while (dd != d) ;

		return true;
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
180
	return false;
181 182
}

183
void GMap3::splitFace(Dart d, Dart e)
Thomas's avatar
Thomas committed
184
{
185
	assert(d != e && GMap2::sameOrientedFace(d, e)) ;
Thomas's avatar
Thomas committed
186

187 188
	Dart dd = beta1(beta3(d));
	Dart ee = beta1(beta3(e));
Thomas's avatar
Thomas committed
189

Pierre Kraemer's avatar
Pierre Kraemer committed
190 191 192 193 194 195 196 197 198 199
	Dart dprev = phi_1(d) ;
	Dart eprev = phi_1(e) ;
	Dart ddprev = phi_1(dd) ;
	Dart eeprev = phi_1(ee) ;

	beta3unsew(beta1(d)) ;
	beta3unsew(beta1(e)) ;
	beta3unsew(beta1(dd)) ;
	beta3unsew(beta1(ee)) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
200 201
	GMap2::splitFace(d, e);
	GMap2::splitFace(dd, ee);
202 203 204 205
	beta3sew(beta1(d), phi_1(ee));
	beta3sew(phi_1(d), beta1(ee));
	beta3sew(beta1(e), phi_1(dd));
	beta3sew(phi_1(e), beta1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
206 207 208 209 210

	beta3sew(beta0(dprev), beta0(beta3(dprev))) ;
	beta3sew(beta0(eprev), beta0(beta3(eprev))) ;
	beta3sew(beta0(ddprev), beta0(beta3(ddprev))) ;
	beta3sew(beta0(eeprev), beta0(beta3(eeprev))) ;
Thomas's avatar
Thomas committed
211 212
}

Pierre Kraemer's avatar
Pierre Kraemer committed
213
void GMap3::sewVolumes(Dart d, Dart e, bool withBoundary)
214 215 216
{
	assert(faceDegree(d) == faceDegree(e));

Pierre Kraemer's avatar
Pierre Kraemer committed
217 218 219
	// if sewing with fixed points
	if (!withBoundary)
	{
220
		assert(beta3(d) == d && beta3(e) == e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
221 222 223 224
		Dart fitD = d ;
		Dart fitE = e ;
		do
		{
225 226
			beta3sew(fitD, beta0(fitE)) ;
			beta3sew(beta0(fitD), fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
227 228 229 230 231 232
			fitD = phi1(fitD) ;
			fitE = phi_1(fitE) ;
		} while(fitD != d) ;
		return ;
	}

233 234
	Dart dd = beta3(d) ;
	Dart ee = beta3(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
235 236 237

	Dart fitD = dd ;
	Dart fitE = ee ;
238 239
	do
	{
240 241
		Dart fitD2 = beta2(fitD) ;
		Dart fitE2 = beta2(fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
242 243
		if(fitD2 != fitE)
		{
244 245
			beta2unsew(fitD) ;
			beta2unsew(fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
246 247
			beta2unsew(beta0(fitD)) ;
			beta2unsew(beta0(fitE)) ;
248 249 250 251
			beta2sew(fitD2, beta0(fitE2)) ;
			beta2sew(beta0(fitD2), fitE2) ;
			beta2sew(fitD, beta0(fitE)) ;
			beta2sew(beta0(fitD), fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
252
		}
253 254 255 256
		beta3unsew(fitD) ;
		beta3unsew(beta0(fitD)) ;
		beta3unsew(fitE) ;
		beta3unsew(beta0(fitE)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
257 258 259
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != dd) ;
260
	GMap2::deleteCC(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
261 262 263 264 265

	fitD = d ;
	fitE = e ;
	do
	{
266 267
		beta3sew(fitD, beta0(fitE)) ;
		beta3sew(beta0(fitD), fitE) ;
268 269 270 271 272 273 274
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void GMap3::unsewVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
275 276 277 278 279 280 281 282 283 284 285 286
	assert(!isBoundaryFace(d)) ;

	unsigned int nbE = faceDegree(d) ;
	Dart d3 = phi3(d);

	Dart b1 = newBoundaryFace(nbE) ;
	Dart b2 = newBoundaryFace(nbE) ;

	Dart fit1 = d ;
	Dart fit2 = d3 ;
	Dart fitB1 = b1 ;
	Dart fitB2 = b2 ;
287 288
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
289 290 291 292
		Dart f = findBoundaryFaceOfEdge(fit1) ;
		if(f != NIL)
		{
			Dart f2 = phi2(f) ;
293 294 295 296 297 298
			beta2unsew(f) ;
			beta2unsew(beta0(f)) ;
			beta2sew(fitB1, beta0(f)) ;
			beta2sew(beta0(fitB1), f) ;
			beta2sew(fitB2, beta0(f2)) ;
			beta2sew(beta0(fitB2), f2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
299 300
		}
		else
301 302 303 304
		{
			beta2sew(fitB1, beta0(fitB2)) ;
			beta2sew(beta0(fitB1), fitB2) ;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
305

306 307 308 309 310 311
		beta3unsew(fit1) ;
		beta3unsew(beta0(fit1)) ;
		beta3sew(fit1, beta0(fitB1)) ;
		beta3sew(beta0(fit1), fitB1) ;
		beta3sew(fit2, beta0(fitB2)) ;
		beta3sew(beta0(fit2), fitB2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
312 313 314 315 316 317

		fit1 = phi1(fit1) ;
		fit2 = phi_1(fit2) ;
		fitB1 = phi_1(fitB1) ;
		fitB2 = phi1(fitB2) ;
	} while(fitB1 != b1) ;
318 319 320 321
}

bool GMap3::mergeVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
322
	if(!GMap3::isBoundaryFace(d))
323
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
324
		GMap2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
325 326 327 328 329
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
330 331 332 333 334 335 336 337 338 339 340 341 342 343 344
void GMap3::splitVolume(std::vector<Dart>& vd)
{
	assert(checkSimpleOrientedPath(vd)) ;

	Dart e = vd.front();
	Dart e2 = phi2(e);

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

	GMap2::fillHole(e) ;
	GMap2::fillHole(e2) ;

	//sew the two connected components
Pierre Kraemer's avatar
Pierre Kraemer committed
345
	GMap3::sewVolumes(beta2(e), beta2(e2), false);
Pierre Kraemer's avatar
Pierre Kraemer committed
346 347
}

348 349 350
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
351

352
bool GMap3::sameOrientedVertex(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
353
{
354 355
	DartMarkerStore mv(*this);	// Lock a marker

Pierre Kraemer's avatar
Pierre Kraemer committed
356 357 358
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
359 360
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
361
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
362
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
363
		if(*it == e)
364 365
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
366 367 368 369
		// add phi21 and phi23 successor if they are not marked yet
		Dart d2 = phi2(*it);
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
370

Pierre Kraemer's avatar
Pierre Kraemer committed
371 372 373 374 375 376 377 378 379
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
380 381 382 383 384 385 386 387
		}
	}
	return false;
}

bool GMap3::sameVertex(Dart d, Dart e)
{
	DartMarkerStore mv(*this);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
388

Pierre Kraemer's avatar
Pierre Kraemer committed
389 390 391
	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
392 393
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
394
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
395
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
396
		if(*it == e)
397 398
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
399
		Dart dx = beta1(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
400 401
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
402
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
403 404
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
405
		dx = beta2(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
406 407
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
408
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
409 410
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
411
		dx = beta3(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
412 413
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
414
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
415 416 417
			mv.mark(dx);
		}
	}
418
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
419 420
}

421 422
unsigned int GMap3::vertexDegree(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
423
	unsigned int count = 0;
424 425
	DartMarkerStore mv(*this);	// Lock a marker

Pierre Kraemer's avatar
Pierre Kraemer committed
426 427 428
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
429 430
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
431
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
432 433
	{
		//add phi21 and phi23 successor if they are not marked yet
Pierre Kraemer's avatar
Pierre Kraemer committed
434
		Dart d2 = phi2(*it);
435 436 437 438 439
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
440
			darts.push_back(d21);
441 442
			mv.mark(d21);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
443
		if(!mv.isMarked(d23))
444
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
445
			darts.push_back(d23);
446 447 448 449 450
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
Pierre Kraemer's avatar
Pierre Kraemer committed
451
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
452
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
453
		if(!me.isMarked(*it))
454 455
		{
			++count;
Pierre Kraemer's avatar
Pierre Kraemer committed
456
			me.markOrbit(EDGE, *it);
457 458 459 460 461 462 463 464
		}
	}

	return count;
}

bool GMap3::isBoundaryVertex(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
465
	DartMarkerStore mv(*this);	// Lock a marker
466

Pierre Kraemer's avatar
Pierre Kraemer committed
467 468 469
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
470 471
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
472
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
473
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
474 475
		if(isBoundaryMarked(*it))
			return true ;
476 477

		//add phi21 and phi23 successor if they are not marked yet
Pierre Kraemer's avatar
Pierre Kraemer committed
478
		Dart d2 = phi2(*it);
479 480 481 482 483
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
484
			darts.push_back(d21);
485 486
			mv.mark(d21);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
487
		if(!mv.isMarked(d23))
488
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
489
			darts.push_back(d23);
490 491 492
			mv.mark(d23);
		}
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
493
	return false ;
494 495
}

496 497
bool GMap3::sameOrientedEdge(Dart d, Dart e)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
498
	Dart it = d;
499 500
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
501
		if(it == e || phi2(it) == e)
502
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
503 504
		it = alpha2(it);
	} while (it != d);
505 506
	return false;
}
Pierre Kraemer's avatar
Pierre Kraemer committed
507

508
bool GMap3::sameEdge(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
509
{
Pierre Kraemer's avatar
Pierre Kraemer committed
510
	Dart it = d;
511 512
	do
	{
513
		if(it == e || beta0(it) == e || beta2(it) == e || phi2(it) == e)
514 515
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
516 517
		it = alpha2(it);
	} while (it != d);
518 519 520
	return false;
}

521 522 523
unsigned int GMap3::edgeDegree(Dart d)
{
	unsigned int deg = 0;
Pierre Kraemer's avatar
Pierre Kraemer committed
524
	Dart it = d;
525 526
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
527 528 529
		++deg;
		it = alpha2(it);
	} while(it != d);
530 531 532
	return deg;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
533
bool GMap3::isBoundaryEdge(Dart d)
534
{
Pierre Kraemer's avatar
Pierre Kraemer committed
535
	Dart it = d;
536 537
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
538 539 540 541
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
542 543 544
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
545
Dart GMap3::findBoundaryFaceOfEdge(Dart d)
546
{
Pierre Kraemer's avatar
Pierre Kraemer committed
547
	Dart it = d;
548 549
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
550 551 552 553 554 555
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
}
556

Pierre Kraemer's avatar
Pierre Kraemer committed
557 558 559 560 561 562
bool GMap3::sameOrientedFace(Dart d, Dart e)
{
	Dart it = d;
	do
	{
		if(it == e || phi3(it) == e)
563
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
564 565 566 567
		it = phi1(it);
	} while (it != d);
	return false;
}
568

Pierre Kraemer's avatar
Pierre Kraemer committed
569 570 571 572 573 574 575 576
bool GMap3::isBoundaryVolume(Dart d)
{
	DartMarkerStore mark(*this);	// Lock a marker

	std::vector<Dart> visitedFaces ;
	visitedFaces.reserve(128) ;
	visitedFaces.push_back(d) ;
	mark.markOrbit(FACE, d) ;
577

Pierre Kraemer's avatar
Pierre Kraemer committed
578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594
	for(std::vector<Dart>::iterator it = visitedFaces.begin(); it != visitedFaces.end(); ++it)
	{
		if (isBoundaryMarked(beta3(*it)))
			return true ;

		Dart e = *it ;
		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
				mark.markOrbit(FACE, ee) ;
			}
			e = phi1(e) ;
		} while(e != *it) ;
	}
595 596 597
	return false;
}

Thomas's avatar
Thomas committed
598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672
bool GMap3::check()
{
    CGoGNout << "Check: topology begin" << CGoGNendl;
    DartMarker m(*this);
    m.unmarkAll();
    for(Dart d = this->begin(); d != this->end(); this->next(d))
    {
        Dart d0 = beta0(d);
        if (beta0(d0) != d) // beta0 involution ?
		{
             CGoGNout << "Check: beta0 is not an involution" << CGoGNendl;
            return false;
        }

        Dart d3 = beta3(d);
        if (beta3(d3) != d) // beta3 involution ?
		{
             CGoGNout << "Check: beta3 is not an involution" << CGoGNendl;
            return false;
        }

        if(d3 != d)
        {
        	if(beta1(d3) != beta3(beta1(d)))
        	{
        		CGoGNout << "Check: beta3 , faces are not entirely sewn" << CGoGNendl;
        		return false;
        	}
        }

        Dart d2 = beta2(d);
        if (beta2(d2) != d) // beta2 involution ?
		{
            CGoGNout << "Check: beta2 is not an involution" << CGoGNendl;
            return false;
        }

        Dart d1 = phi1(d);
        if (phi_1(d1) != d) // phi1 a une image correcte ?
		{
            CGoGNout << "Check: unconsistent phi_1 link" << CGoGNendl;
            return false;
        }

        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
		{
            CGoGNout << "Check: dart with two phi1 predecessors" << CGoGNendl;
            return false;
        }
        m.mark(d1);

        if (d1 == d)
            CGoGNout << "Check: (warning) face loop (one edge)" << CGoGNendl;

        if (phi1(d1) == d)
            CGoGNout << "Check: (warning) face with only two edges" << CGoGNendl;

        if (phi2(d1) == d)
            CGoGNout << "Check: (warning) dandling edge (phi2)" << CGoGNendl;

        if (phi3(d1) == d)
            CGoGNout << "Check: (warning) dandling edge (phi3)" << CGoGNendl;
    }

    for(Dart d = this->begin(); d != this->end(); this->next(d))
    {
        if (!m.isMarked(d)) // phi1 a au moins un antécédent ?
		{
        	std::cout << "dart = " << d << std::endl;
            CGoGNout << "Check: dart with no phi1 predecessor" << CGoGNendl;
            return false;
        }
    }

    CGoGNout << "Check: topology ok" << CGoGNendl;
Pierre Kraemer's avatar
Pierre Kraemer committed
673 674 675 676 677 678 679 680 681 682 683 684 685

    std::cout << "nb vertex orbits" << getNbOrbits(VERTEX) << std::endl ;
    std::cout << "nb vertex cells" << m_attribs[VERTEX].size() << std::endl ;

    std::cout << "nb edge orbits" << getNbOrbits(EDGE) << std::endl ;
    std::cout << "nb edge cells" << m_attribs[EDGE].size() << std::endl ;

    std::cout << "nb face orbits" << getNbOrbits(FACE) << std::endl ;
    std::cout << "nb face cells" << m_attribs[FACE].size() << std::endl ;

    std::cout << "nb volume orbits" << getNbOrbits(VOLUME) << std::endl ;
    std::cout << "nb volume cells" << m_attribs[VOLUME].size() << std::endl ;

Thomas's avatar
Thomas committed
686 687 688
    return true;
}

689 690 691 692
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

693 694
bool GMap3::foreach_dart_of_oriented_vertex(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
695
	DartMarkerStore mv(*this, thread);	// Lock a marker
696 697
	bool found = false;					// Last functor return value

Pierre Kraemer's avatar
Pierre Kraemer committed
698 699 700
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
701 702
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
703
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
704
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
705 706 707 708
		// add phi21 and phi23 successor if they are not marked yet
		Dart d2 = phi2(*it);
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
709

Pierre Kraemer's avatar
Pierre Kraemer committed
710
		if(!mv.isMarked(d21))
711
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
712 713 714 715 716 717 718
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
719 720
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
721
		found = f(*it);
722 723 724 725
	}
	return found;
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
731 732 733
	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
734 735
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
736
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
737
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
738
		Dart dx = beta1(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
739 740
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
741
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
742 743
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
744
		dx = beta2(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
745 746
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
747
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
748 749
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
750
		dx = beta3(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
751 752
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
753
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
754 755 756
			mv.mark(dx);
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
757
		found = f(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
758 759
	}
	return found;
760
}
Pierre Kraemer's avatar
Pierre Kraemer committed
761

762 763
bool GMap3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
764 765 766 767
	Dart it = d;
	do
	{
		if (GMap2::foreach_dart_of_edge(it, f, thread))
768
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
769 770
		it = alpha2(it);
	} while (it != d);
771
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
772 773
}

Sylvain Thery's avatar
Sylvain Thery committed
774
bool GMap3::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
775
{
Sylvain Thery's avatar
Sylvain Thery committed
776
	DartMarkerStore mv(*this,thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
777 778
	bool found = false;					// Last functor return value

Pierre Kraemer's avatar
Pierre Kraemer committed
779 780 781
	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
782 783
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
784
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
785
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
786
		Dart dx = beta0(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
787 788
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
789
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
790 791
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
792
		dx = beta1(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
793 794
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
795
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
796 797
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
798
		dx = beta2(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
799 800
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
801
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
802 803
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
804
		dx = beta3(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
805 806
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
807
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
808 809 810
			mv.mark(dx);
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
811
		found =  f(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
812 813 814 815
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
816 817 818 819 820 821
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/

unsigned int GMap3::closeHole(Dart d, bool forboundary)
{
822
	assert(beta3(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
823 824 825 826 827
	DartMarkerStore m(*this) ;

	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
828
	m.markOrbit(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846

	unsigned int count = 0 ;

	// For every face added to the list
	for (std::vector<Dart>::iterator it = visitedFaces.begin(); it != visitedFaces.end(); ++it)
	{
		Dart f = *it ;
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryFace(degree) ;
		++count ;

		Dart bit = b ;
		do
		{
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
847
				if(beta3(e) == e)
Pierre Kraemer's avatar
Pierre Kraemer committed
848 849 850 851 852
				{
					found = true ;
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
853
						m.markOrbit(FACE, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
854 855 856 857 858
					}
				}
				else if(isBoundaryMarked(e))
				{
					found = true ;
859 860
					beta2sew(e, bit) ;
					beta2sew(beta0(e), beta0(bit)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
861 862 863 864 865
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

866 867 868
			beta3sew(f, bit) ;
			beta3sew(beta0(f), beta0(bit)) ;
			bit = phi1(bit) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886
			f = phi1(f);
		} while(f != *it);
	}

	return count ;
}

void GMap3::closeMap()
{
	// Search the map for topological holes (fix points of beta3)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (beta3(d) == d)
			closeHole(d);
	}
}

} // namespace CGoGN