gmap3.cpp 18.6 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
{
Pierre Kraemer's avatar
Pierre Kraemer committed
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
//	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 ;
//			phi2unsew(d2) ;
//			phi2unsew(d32) ;
//			phi2sew(d2, d32) ;
//			phi2sew(fit, d3) ;
//		}
//	}
//	Map2::deleteCC(d) ;
//
//	return res ;
	return NIL ;
}
132

Pierre Kraemer's avatar
Pierre Kraemer committed
133 134 135 136 137
void GMap3::cutEdge(Dart d)
{
	Dart prev = d ;
	Dart dd = alpha2(d) ;
	GMap2::cutEdge(d) ;
138

Pierre Kraemer's avatar
Pierre Kraemer committed
139
	while(dd != d)
140
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
141 142
		prev = dd ;
		dd = alpha2(dd) ;
143

Pierre Kraemer's avatar
Pierre Kraemer committed
144
		GMap2::cutEdge(prev) ;
145

Pierre Kraemer's avatar
Pierre Kraemer committed
146 147 148
		Dart d3 = beta3(prev);
		beta3sew(beta0(prev), beta0(d3));
		beta3sew(phi1(prev), phi1(d3));
149 150

	}
Pierre Kraemer's avatar
Pierre Kraemer committed
151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178

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

bool GMap3::uncutEdge(Dart d)
{
//	if(vertexDegree(phi1(d)) == 2)
//	{
//		Dart prev = d ;
//		phi3unsew(phi1(prev)) ;
//
//		Dart dd = d;
//		do
//		{
//			prev = dd;
//			dd = alpha2(dd);
//
//			phi3unsew(phi2(prev)) ;
//			phi3unsew(phi2(phi1(prev))) ;
//			Map2::uncutEdge(prev);
//			phi3sew(dd, phi2(prev));
//		} while (dd != d) ;
//
//		return true;
//	}
	return false;
179 180
}

181
void GMap3::splitFace(Dart d, Dart e)
Thomas's avatar
Thomas committed
182
{
Pierre Kraemer's avatar
Pierre Kraemer committed
183
	assert(d != e && sameOrientedFace(d, e)) ;
Thomas's avatar
Thomas committed
184

Pierre Kraemer's avatar
Pierre Kraemer committed
185 186
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Thomas's avatar
Thomas committed
187

Pierre Kraemer's avatar
Pierre Kraemer committed
188 189
	GMap2::splitFace(d, e);
	GMap2::splitFace(dd, ee);
Thomas's avatar
Thomas committed
190

Pierre Kraemer's avatar
Pierre Kraemer committed
191 192
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Thomas's avatar
Thomas committed
193 194
}

Pierre Kraemer's avatar
Pierre Kraemer committed
195
void GMap3::sewVolumes(Dart d, Dart e, bool withBoundary)
196 197 198
{
	assert(faceDegree(d) == faceDegree(e));

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

	Dart dd = phi3(d) ;
	Dart ee = phi3(e) ;

	Dart fitD = dd ;
	Dart fitE = ee ;
219 220
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
		Dart fitD2 = phi2(fitD) ;
		Dart fitE2 = phi2(fitE) ;
		if(fitD2 != fitE)
		{
			phi2unsew(fitD) ;
			phi2unsew(fitE) ;
			phi2sew(fitD2, fitE2) ;
			phi2sew(fitD, fitE) ;
		}
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != dd) ;
	Map2::deleteCC(dd) ;

	fitD = d ;
	fitE = e ;
	do
	{
		phi3sew(fitD, fitE) ;
242 243 244 245 246 247 248
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void GMap3::unsewVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
249 250 251 252 253 254 255 256 257 258 259 260
	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 ;
261 262
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282
		Dart f = findBoundaryFaceOfEdge(fit1) ;
		if(f != NIL)
		{
			Dart f2 = phi2(f) ;
			phi2unsew(f) ;
			phi2sew(fitB1, f) ;
			phi2sew(fitB2, f2) ;
		}
		else
			phi2sew(fitB1, fitB2) ;

		phi3unsew(fit1) ;
		phi3sew(fit1, fitB1) ;
		phi3sew(fit2, fitB2) ;

		fit1 = phi1(fit1) ;
		fit2 = phi_1(fit2) ;
		fitB1 = phi_1(fitB1) ;
		fitB2 = phi1(fitB2) ;
	} while(fitB1 != b1) ;
283 284 285 286
}

bool GMap3::mergeVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
287
	if(!GMap3::isBoundaryFace(d))
288
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
289
		GMap2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
290 291 292 293 294
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
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);
}

313 314 315
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
316

317
bool GMap3::sameOrientedVertex(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
318
{
319 320
	DartMarkerStore mv(*this);	// Lock a marker

Pierre Kraemer's avatar
Pierre Kraemer committed
321 322 323
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
324 325
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
326
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
327
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
328
		if(*it == e)
329 330
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
331 332 333 334
		// 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
335

Pierre Kraemer's avatar
Pierre Kraemer committed
336 337 338 339 340 341 342 343 344
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
345 346 347 348 349 350 351 352
		}
	}
	return false;
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
354 355 356
	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
357 358
	mv.mark(d);

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

Pierre Kraemer's avatar
Pierre Kraemer committed
364
		Dart dx = beta1(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
365 366
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
367
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
368 369
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
370
		dx = beta2(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
371 372
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
373
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
374 375
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
376
		dx = beta3(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
377 378
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
379
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
380 381 382
			mv.mark(dx);
		}
	}
383
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
384 385
}

386 387
unsigned int GMap3::vertexDegree(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
388
	unsigned int count = 0;
389 390
	DartMarkerStore mv(*this);	// Lock a marker

Pierre Kraemer's avatar
Pierre Kraemer committed
391 392 393
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
394 395
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
396
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
397 398
	{
		//add phi21 and phi23 successor if they are not marked yet
Pierre Kraemer's avatar
Pierre Kraemer committed
399
		Dart d2 = phi2(*it);
400 401 402 403 404
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
405
			darts.push_back(d21);
406 407
			mv.mark(d21);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
408
		if(!mv.isMarked(d23))
409
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
410
			darts.push_back(d23);
411 412 413 414 415
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
Pierre Kraemer's avatar
Pierre Kraemer committed
416
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
417
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
418
		if(!me.isMarked(*it))
419 420
		{
			++count;
Pierre Kraemer's avatar
Pierre Kraemer committed
421
			me.markOrbit(EDGE, *it);
422 423 424 425 426 427 428 429
		}
	}

	return count;
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
432 433 434
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
435 436
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
437
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
438
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
439 440
		if(isBoundaryMarked(*it))
			return true ;
441 442

		//add phi21 and phi23 successor if they are not marked yet
Pierre Kraemer's avatar
Pierre Kraemer committed
443
		Dart d2 = phi2(*it);
444 445 446 447 448
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
449
			darts.push_back(d21);
450 451
			mv.mark(d21);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
452
		if(!mv.isMarked(d23))
453
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
454
			darts.push_back(d23);
455 456 457
			mv.mark(d23);
		}
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
458
	return false ;
459 460
}

461 462
bool GMap3::sameOrientedEdge(Dart d, Dart e)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
463
	Dart it = d;
464 465
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
466
		if(it == e || phi2(it) == e)
467
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
468 469
		it = alpha2(it);
	} while (it != d);
470 471
	return false;
}
Pierre Kraemer's avatar
Pierre Kraemer committed
472

473
bool GMap3::sameEdge(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
474
{
Pierre Kraemer's avatar
Pierre Kraemer committed
475
	Dart it = d;
476 477
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
478
		if(it == e || beta0(it) == e || beta2(it) == e || phi2(it) == e)
479 480
			return true;

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

486 487 488
unsigned int GMap3::edgeDegree(Dart d)
{
	unsigned int deg = 0;
Pierre Kraemer's avatar
Pierre Kraemer committed
489
	Dart it = d;
490 491
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
492 493 494
		++deg;
		it = alpha2(it);
	} while(it != d);
495 496 497
	return deg;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
498
bool GMap3::isBoundaryEdge(Dart d)
499
{
Pierre Kraemer's avatar
Pierre Kraemer committed
500
	Dart it = d;
501 502
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
503 504 505 506
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
507 508 509
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
510
Dart GMap3::findBoundaryFaceOfEdge(Dart d)
511
{
Pierre Kraemer's avatar
Pierre Kraemer committed
512
	Dart it = d;
513 514
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
515 516 517 518 519 520
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
}
521

Pierre Kraemer's avatar
Pierre Kraemer committed
522 523 524 525 526 527
bool GMap3::sameOrientedFace(Dart d, Dart e)
{
	Dart it = d;
	do
	{
		if(it == e || phi3(it) == e)
528
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
529 530 531 532
		it = phi1(it);
	} while (it != d);
	return false;
}
533

Pierre Kraemer's avatar
Pierre Kraemer committed
534 535 536 537 538 539 540 541
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) ;
542

Pierre Kraemer's avatar
Pierre Kraemer committed
543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559
	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) ;
	}
560 561 562
	return false;
}

Thomas's avatar
Thomas committed
563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 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
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
638 639 640 641 642 643 644 645 646 647 648 649 650

    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
651 652 653
    return true;
}

654 655 656 657
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

658 659
bool GMap3::foreach_dart_of_oriented_vertex(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
660
	DartMarkerStore mv(*this, thread);	// Lock a marker
661 662
	bool found = false;					// Last functor return value

Pierre Kraemer's avatar
Pierre Kraemer committed
663 664 665
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
666 667
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
668
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
669
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
670 671 672 673
		// 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
674

Pierre Kraemer's avatar
Pierre Kraemer committed
675
		if(!mv.isMarked(d21))
676
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
677 678 679 680 681 682 683
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
684 685
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
686
		found = f(*it);
687 688 689 690
	}
	return found;
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
696 697 698
	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
699 700
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
701
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
702
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
703
		Dart dx = beta1(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
704 705
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
706
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
707 708
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
709
		dx = beta2(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
710 711
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
712
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
713 714
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
715
		dx = beta3(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
716 717
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
718
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
719 720 721
			mv.mark(dx);
		}

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

727 728
bool GMap3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
729 730 731 732
	Dart it = d;
	do
	{
		if (GMap2::foreach_dart_of_edge(it, f, thread))
733
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
734 735
		it = alpha2(it);
	} while (it != d);
736
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
737 738
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
744 745 746
	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
747 748
	mv.mark(d);

Pierre Kraemer's avatar
Pierre Kraemer committed
749
	for(std::vector<Dart>::iterator it = darts.begin(); !found && it != darts.end() ; ++it)
Pierre Kraemer's avatar
Pierre Kraemer committed
750
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
751
		Dart dx = beta0(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
752 753
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
754
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
755 756
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
757
		dx = beta1(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
758 759
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
760
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
761 762
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
763
		dx = beta2(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
764 765
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
766
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
767 768
			mv.mark(dx);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
769
		dx = beta3(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
770 771
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
772
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
773 774 775
			mv.mark(dx);
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
776
		found =  f(*it);
Pierre Kraemer's avatar
Pierre Kraemer committed
777 778 779 780
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849
/*! @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)
{
	assert(phi3(d) == d);		// Nothing to close
	DartMarkerStore m(*this) ;

	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
	m.markOrbit(ORIENTED_FACE, d) ;

	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
			{
				if(phi3(e) == e)
				{
					found = true ;
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
						m.markOrbit(ORIENTED_FACE, e) ;
					}
				}
				else if(isBoundaryMarked(e))
				{
					found = true ;
					phi2sew(e, bit) ;
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			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