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

	mark.markOrbit(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
44 45

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
53 54 55 56
		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
57
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
58 59 60 61 62
				visitedFaces.push_back(ee) ;
				mark.markOrbit(FACE, ee) ;
			}
			e = phi1(e) ;
		} while(e != *face) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
63
	}
64

Pierre Kraemer's avatar
Pierre Kraemer committed
65 66 67 68 69 70 71 72 73 74 75 76
	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
77 78
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
83
Dart GMap3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
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 137
	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
138 139
	return NIL ;
}
140

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

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

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

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

	}
Pierre Kraemer's avatar
Pierre Kraemer committed
159 160 161 162 163 164 165 166

	Dart d3 = beta3(d);
	beta3sew(beta0(d), beta0(d3));
	beta3sew(phi1(prev), phi1(d3));
}

bool GMap3::uncutEdge(Dart d)
{
167 168 169 170 171 172 173 174 175 176 177 178 179 180
	if(vertexDegree(phi1(d)) == 2)
	{
		Dart prev = d ;

		Dart dd = d;
		do
		{
			prev = dd;
			dd = alpha2(dd);
			GMap2::uncutEdge(prev);
		} while (dd != d) ;

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

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
191 192
	GMap2::splitFace(d, e);
	GMap2::splitFace(dd, ee);
Thomas's avatar
Thomas committed
193

194 195 196 197
	beta3sew(beta1(d), phi_1(ee));
	beta3sew(phi_1(d), beta1(ee));
	beta3sew(beta1(e), phi_1(dd));
	beta3sew(phi_1(e), beta1(dd));
Thomas's avatar
Thomas committed
198 199
}

Pierre Kraemer's avatar
Pierre Kraemer committed
200
void GMap3::sewVolumes(Dart d, Dart e, bool withBoundary)
201 202 203
{
	assert(faceDegree(d) == faceDegree(e));

Pierre Kraemer's avatar
Pierre Kraemer committed
204 205 206
	// if sewing with fixed points
	if (!withBoundary)
	{
207
		assert(beta3(d) == d && beta3(e) == e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
208 209 210 211
		Dart fitD = d ;
		Dart fitE = e ;
		do
		{
212 213
			beta3sew(fitD, beta0(fitE)) ;
			beta3sew(beta0(fitD), fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
214 215 216 217 218 219
			fitD = phi1(fitD) ;
			fitE = phi_1(fitE) ;
		} while(fitD != d) ;
		return ;
	}

220 221
	Dart dd = beta3(d) ;
	Dart ee = beta3(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
222 223 224

	Dart fitD = dd ;
	Dart fitE = ee ;
225 226
	do
	{
227 228
		Dart fitD2 = beta2(fitD) ;
		Dart fitE2 = beta2(fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
229 230
		if(fitD2 != fitE)
		{
231 232 233 234 235 236
			beta2unsew(fitD) ;
			beta2unsew(fitE) ;
			beta2sew(fitD2, beta0(fitE2)) ;
			beta2sew(beta0(fitD2), fitE2) ;
			beta2sew(fitD, beta0(fitE)) ;
			beta2sew(beta0(fitD), fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
237
		}
238 239 240 241
		beta3unsew(fitD) ;
		beta3unsew(beta0(fitD)) ;
		beta3unsew(fitE) ;
		beta3unsew(beta0(fitE)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
242 243 244
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != dd) ;
245
	GMap2::deleteCC(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
246 247 248 249 250

	fitD = d ;
	fitE = e ;
	do
	{
251 252
		beta3sew(fitD, beta0(fitE)) ;
		beta3sew(beta0(fitD), fitE) ;
253 254 255 256 257 258 259
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void GMap3::unsewVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
260 261 262 263 264 265 266 267 268 269 270 271
	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 ;
272 273
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
274 275 276 277
		Dart f = findBoundaryFaceOfEdge(fit1) ;
		if(f != NIL)
		{
			Dart f2 = phi2(f) ;
278 279 280 281 282 283
			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
284 285
		}
		else
286 287 288 289
		{
			beta2sew(fitB1, beta0(fitB2)) ;
			beta2sew(beta0(fitB1), fitB2) ;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
290

291 292 293 294 295 296
		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
297 298 299 300 301 302

		fit1 = phi1(fit1) ;
		fit2 = phi_1(fit2) ;
		fitB1 = phi_1(fitB1) ;
		fitB2 = phi1(fitB2) ;
	} while(fitB1 != b1) ;
303 304 305 306
}

bool GMap3::mergeVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
307
	if(!GMap3::isBoundaryFace(d))
308
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
309
		GMap2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
310 311 312 313 314
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332
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
	GMap3::sewVolumes(phi2(e), phi2(e2), false);
}

333 334 335
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
336

337
bool GMap3::sameOrientedVertex(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
338
{
339 340
	DartMarkerStore mv(*this);	// Lock a marker

Pierre Kraemer's avatar
Pierre Kraemer committed
341 342 343
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
344 345
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
346
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
347
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
348
		if(*it == e)
349 350
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
351 352 353 354
		// 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
355

Pierre Kraemer's avatar
Pierre Kraemer committed
356 357 358 359 360 361 362 363 364
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
365 366 367 368 369 370 371 372
		}
	}
	return false;
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
374 375 376
	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
377 378
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
379
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
380
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
381
		if(*it == e)
382 383
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
384
		Dart dx = beta1(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
385 386
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
387
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
388 389
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
390
		dx = beta2(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
391 392
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
393
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
394 395
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
396
		dx = beta3(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
397 398
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
399
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
400 401 402
			mv.mark(dx);
		}
	}
403
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
404 405
}

406 407
unsigned int GMap3::vertexDegree(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
408
	unsigned int count = 0;
409 410
	DartMarkerStore mv(*this);	// Lock a marker

Pierre Kraemer's avatar
Pierre Kraemer committed
411 412 413
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
414 415
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
416
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
417 418
	{
		//add phi21 and phi23 successor if they are not marked yet
Pierre Kraemer's avatar
Pierre Kraemer committed
419
		Dart d2 = phi2(*it);
420 421 422 423 424
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
425
			darts.push_back(d21);
426 427
			mv.mark(d21);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
428
		if(!mv.isMarked(d23))
429
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
430
			darts.push_back(d23);
431 432 433 434 435
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
Pierre Kraemer's avatar
Pierre Kraemer committed
436
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
437
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
438
		if(!me.isMarked(*it))
439 440
		{
			++count;
Pierre Kraemer's avatar
Pierre Kraemer committed
441
			me.markOrbit(EDGE, *it);
442 443 444 445 446 447 448 449
		}
	}

	return count;
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
452 453 454
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
455 456
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
457
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
458
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
459 460
		if(isBoundaryMarked(*it))
			return true ;
461 462

		//add phi21 and phi23 successor if they are not marked yet
Pierre Kraemer's avatar
Pierre Kraemer committed
463
		Dart d2 = phi2(*it);
464 465 466 467 468
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
469
			darts.push_back(d21);
470 471
			mv.mark(d21);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
472
		if(!mv.isMarked(d23))
473
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
474
			darts.push_back(d23);
475 476 477
			mv.mark(d23);
		}
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
478
	return false ;
479 480
}

481 482
bool GMap3::sameOrientedEdge(Dart d, Dart e)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
483
	Dart it = d;
484 485
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
486
		if(it == e || phi2(it) == e)
487
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
488 489
		it = alpha2(it);
	} while (it != d);
490 491
	return false;
}
Pierre Kraemer's avatar
Pierre Kraemer committed
492

493
bool GMap3::sameEdge(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
494
{
Pierre Kraemer's avatar
Pierre Kraemer committed
495
	Dart it = d;
496 497
	do
	{
498
		if(it == e || beta0(it) == e || beta2(it) == e || phi2(it) == e)
499 500
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
501 502
		it = alpha2(it);
	} while (it != d);
503 504 505
	return false;
}

506 507 508
unsigned int GMap3::edgeDegree(Dart d)
{
	unsigned int deg = 0;
Pierre Kraemer's avatar
Pierre Kraemer committed
509
	Dart it = d;
510 511
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
512 513 514
		++deg;
		it = alpha2(it);
	} while(it != d);
515 516 517
	return deg;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
518
bool GMap3::isBoundaryEdge(Dart d)
519
{
Pierre Kraemer's avatar
Pierre Kraemer committed
520
	Dart it = d;
521 522
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
523 524 525 526
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
527 528 529
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
530
Dart GMap3::findBoundaryFaceOfEdge(Dart d)
531
{
Pierre Kraemer's avatar
Pierre Kraemer committed
532
	Dart it = d;
533 534
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
535 536 537 538 539 540
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
}
541

Pierre Kraemer's avatar
Pierre Kraemer committed
542 543 544 545 546 547
bool GMap3::sameOrientedFace(Dart d, Dart e)
{
	Dart it = d;
	do
	{
		if(it == e || phi3(it) == e)
548
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
549 550 551 552
		it = phi1(it);
	} while (it != d);
	return false;
}
553

Pierre Kraemer's avatar
Pierre Kraemer committed
554 555 556 557 558 559 560 561
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) ;
562

Pierre Kraemer's avatar
Pierre Kraemer committed
563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579
	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) ;
	}
580 581 582
	return false;
}

Thomas's avatar
Thomas committed
583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 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
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
658 659 660 661 662 663 664 665 666 667 668 669 670

    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
671 672 673
    return true;
}

674 675 676 677
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

678 679
bool GMap3::foreach_dart_of_oriented_vertex(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
680
	DartMarkerStore mv(*this, thread);	// Lock a marker
681 682
	bool found = false;					// Last functor return value

Pierre Kraemer's avatar
Pierre Kraemer committed
683 684 685
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
686 687
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
688
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
689
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
690 691 692 693
		// 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
694

Pierre Kraemer's avatar
Pierre Kraemer committed
695
		if(!mv.isMarked(d21))
696
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
697 698 699 700 701 702 703
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
704 705
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
706
		found = f(*it);
707 708 709 710
	}
	return found;
}

711
bool GMap3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
712
{
Pierre Kraemer's avatar
Pierre Kraemer committed
713
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
714
	bool found = false;					// Last functor return value
715

Pierre Kraemer's avatar
Pierre Kraemer committed
716 717 718
	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
719 720
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
721
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
722
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
723
		Dart dx = beta1(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
724 725
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
726
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
727 728
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
729
		dx = beta2(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
730 731
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
732
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
733 734
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
735
		dx = beta3(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
736 737
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
738
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
739 740 741
			mv.mark(dx);
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
742
		found = f(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
743 744
	}
	return found;
745
}
Pierre Kraemer's avatar
Pierre Kraemer committed
746

747 748
bool GMap3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
749 750 751 752
	Dart it = d;
	do
	{
		if (GMap2::foreach_dart_of_edge(it, f, thread))
753
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
754 755
		it = alpha2(it);
	} while (it != d);
756
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
757 758
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
764 765 766
	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
767 768
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
769
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
770
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
771
		Dart dx = beta0(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
772 773
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
774
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
775 776
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
777
		dx = beta1(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
778 779
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
780
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
781 782
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
783
		dx = beta2(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
784 785
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
786
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
787 788
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
789
		dx = beta3(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
790 791
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
792
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
793 794 795
			mv.mark(dx);
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
796
		found =  f(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
797 798 799 800
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
801 802 803 804 805 806
/*! @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)
{
807
	assert(beta3(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
808 809 810 811 812
	DartMarkerStore m(*this) ;

	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
813
	m.markOrbit(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831

	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
			{
832
				if(beta3(e) == e)
Pierre Kraemer's avatar
Pierre Kraemer committed
833 834 835 836 837
				{
					found = true ;
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
838
						m.markOrbit(FACE, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
839 840 841 842 843
					}
				}
				else if(isBoundaryMarked(e))
				{
					found = true ;
844 845
					beta2sew(e, bit) ;
					beta2sew(beta0(e), beta0(bit)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
846 847 848 849 850
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

851 852 853
			beta3sew(f, bit) ;
			beta3sew(beta0(f), beta0(bit)) ;
			bit = phi1(bit) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871
			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