gmap3.cpp 19.4 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1 2 3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-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
45
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
46
	{
47
		Dart e = visitedFaces[i] ;
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
				visitedFaces.push_back(ee) ;
				mark.markOrbit(FACE, ee) ;
			}
			e = phi1(e) ;
61
		} while(e != visitedFaces[i]) ;
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
	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);
98
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
99
	{
100
		if(!mf.isMarked(fstoretmp[i]))
101
		{
102 103
			mf.markOrbit(FACE, fstoretmp[i]);
			fstore.push_back(fstoretmp[i]);
104 105
		}
	}
106

107 108 109 110 111 112 113 114 115 116 117
	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) ;
118

119 120
			if(res == NIL)
				res = d2 ;
121

122 123
			beta2unsew(d2) ;
			beta2unsew(beta0(d2)) ;
124

125 126
			beta2unsew(d32) ;
			beta2unsew(beta0(d32)) ;
127

128 129 130 131
			beta2sew(d2, beta0(d32)) ;
			beta2sew(beta0(d2), d32) ;
			beta2sew(fit, beta0(d3)) ;
			beta2sew(beta0(fit), d3) ;
132 133
		}
	}
134
	GMap2::deleteCC(d) ;
135

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

140
Dart GMap3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
141 142 143
{
	Dart prev = d ;
	Dart dd = alpha2(d) ;
144
	Dart nd = 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));
161 162

	return nd ;
163 164
}

Pierre Kraemer's avatar
Pierre Kraemer committed
165
bool GMap3::uncutEdge(Dart d)
Thomas's avatar
Thomas committed
166
{
167
	if(vertexDegree(phi1(d)) == 2)
Thomas's avatar
Thomas committed
168
	{
169 170 171 172 173 174 175
		Dart prev = d ;

		Dart dd = d;
		do
		{
			prev = dd;
			dd = alpha2(dd);
Thomas's avatar
Thomas committed
176

177 178
			GMap2::uncutEdge(prev);
		} while (dd != d) ;
Thomas's avatar
Thomas committed
179

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

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
192 193 194 195 196 197 198 199 200 201
	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
202 203
	GMap2::splitFace(d, e);
	GMap2::splitFace(dd, ee);
204 205 206 207
	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
208 209 210 211 212

	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
213 214
}

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

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

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

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

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

void GMap3::unsewVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
277 278 279 280 281 282 283 284 285 286 287 288
	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 ;
289 290
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
291 292 293 294
		Dart f = findBoundaryFaceOfEdge(fit1) ;
		if(f != NIL)
		{
			Dart f2 = phi2(f) ;
295 296 297 298 299 300
			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
301 302
		}
		else
303 304 305 306
		{
			beta2sew(fitB1, beta0(fitB2)) ;
			beta2sew(beta0(fitB1), fitB2) ;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
307

308 309 310 311 312 313
		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
314 315 316 317 318 319

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
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
347
	GMap3::sewVolumes(beta2(e), beta2(e2), false);
Pierre Kraemer's avatar
Pierre Kraemer committed
348 349
}

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

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

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

363
	for(unsigned int i = 0; i < darts.size(); ++i)
364
	{
365
		if(darts[i] == e)
366 367
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
368
		// add phi21 and phi23 successor if they are not marked yet
369
		Dart d2 = phi2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
370 371
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
372

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

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

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
Pierre Kraemer's avatar
Pierre Kraemer committed
394 395
	mv.mark(d);

396
	for(unsigned int i = 0; i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
397
	{
398
		if(darts[i] == e)
399 400
			return true;

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

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

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

433
	for(unsigned int i = 0; i < darts.size(); ++i)
434 435
	{
		//add phi21 and phi23 successor if they are not marked yet
436
		Dart d2 = phi2(darts[i]);
437 438 439 440 441
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

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

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

	return count;
}

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

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

474
	for(unsigned int i = 0; i < darts.size(); ++i)
475
	{
476
		if(isBoundaryMarked(darts[i]))
Pierre Kraemer's avatar
Pierre Kraemer committed
477
			return true ;
478 479

		//add phi21 and phi23 successor if they are not marked yet
480
		Dart d2 = phi2(darts[i]);
481 482 483 484 485
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

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

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

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

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

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

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

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

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
575 576 577 578
	std::vector<Dart> visitedFaces ;
	visitedFaces.reserve(128) ;
	visitedFaces.push_back(d) ;
	mark.markOrbit(FACE, d) ;
579

580
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
581
	{
582
		if (isBoundaryMarked(beta3(visitedFaces[i])))
Pierre Kraemer's avatar
Pierre Kraemer committed
583 584
			return true ;

585
		Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
586 587 588 589 590 591 592 593 594
		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) ;
595
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
596
	}
597 598 599
	return false;
}

Thomas's avatar
Thomas committed
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 673 674
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
675 676 677 678 679 680 681 682 683 684 685 686 687

    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
688 689 690
    return true;
}

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

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

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

705
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
706
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
707
		// add phi21 and phi23 successor if they are not marked yet
708
		Dart d2 = phi2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
709 710
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
711

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

723
		found = f(darts[i]);
724 725 726 727
	}
	return found;
}

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

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

738
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
739
	{
740
		Dart dx = beta1(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
741 742
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
743
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
744 745
			mv.mark(dx);
		}
746
		dx = beta2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
747 748
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
749
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
750 751
			mv.mark(dx);
		}
752
		dx = beta3(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
753 754
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
755
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
756 757 758
			mv.mark(dx);
		}

759
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
760 761
	}
	return found;
762
}
Pierre Kraemer's avatar
Pierre Kraemer committed
763

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

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

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

786
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
787
	{
788
		Dart dx = beta0(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
789 790
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
791
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
792 793
			mv.mark(dx);
		}
794
		dx = beta1(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
795 796
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
797
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
798 799
			mv.mark(dx);
		}
800
		dx = beta2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
801 802
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
803
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
804 805
			mv.mark(dx);
		}
806
		dx = beta3(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
807 808
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
809
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
810 811 812
			mv.mark(dx);
		}

813
		found =  f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
814 815 816 817
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
818 819 820 821 822 823
/*! @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)
{
824
	assert(beta3(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
825 826 827 828 829
	DartMarkerStore m(*this) ;

	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
830
	m.markOrbit(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
831 832 833 834

	unsigned int count = 0 ;

	// For every face added to the list
835
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
836
	{
837
		Dart f = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
838 839 840 841 842 843 844 845 846 847 848
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryFace(degree) ;
		++count ;

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

868 869 870
			beta3sew(f, bit) ;
			beta3sew(beta0(f), beta0(bit)) ;
			bit = phi1(bit) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
871
			f = phi1(f);
872
		} while(f != visitedFaces[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888
	}

	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