gmap3.cpp 20 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

			fit = phi1(fit) ;
134 135
		}
	}
136

137
	GMap2::deleteCC(d) ;
138

139
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
140
}
141

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

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

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

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

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

	return nd ;
165 166
}

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

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

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

182
		return true;
Thomas's avatar
Thomas committed
183
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
184
	return false;
Thomas's avatar
Thomas committed
185 186
}

187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
Dart GMap3::deleteEdge(Dart d)
{
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
	Dart dit = d ;
	do
	{
		Dart fit = dit ;
		Dart end = 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) ;

			fit = phi1(fit) ;
		}
		dit = alpha2(dit) ;
	} while(dit != d) ;

	GMap2::deleteCC(d) ;

	return res ;
}

228
void GMap3::splitFace(Dart d, Dart e)
Thomas's avatar
Thomas committed
229
{
230
	assert(d != e && GMap2::sameOrientedFace(d, e)) ;
Thomas's avatar
Thomas committed
231

232 233
	Dart dd = beta1(beta3(d));
	Dart ee = beta1(beta3(e));
Thomas's avatar
Thomas committed
234

Pierre Kraemer's avatar
Pierre Kraemer committed
235 236 237 238 239 240 241 242 243 244
	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
245 246
	GMap2::splitFace(d, e);
	GMap2::splitFace(dd, ee);
247 248 249 250
	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
251 252 253 254 255

	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
256 257
}

Pierre Kraemer's avatar
Pierre Kraemer committed
258
void GMap3::sewVolumes(Dart d, Dart e, bool withBoundary)
259 260 261
{
	assert(faceDegree(d) == faceDegree(e));

Pierre Kraemer's avatar
Pierre Kraemer committed
262 263 264
	// if sewing with fixed points
	if (!withBoundary)
	{
265
		assert(beta3(d) == d && beta3(e) == e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
266 267 268 269
		Dart fitD = d ;
		Dart fitE = e ;
		do
		{
270 271
			beta3sew(fitD, beta0(fitE)) ;
			beta3sew(beta0(fitD), fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
272 273 274 275 276 277
			fitD = phi1(fitD) ;
			fitE = phi_1(fitE) ;
		} while(fitD != d) ;
		return ;
	}

278 279
	Dart dd = beta3(d) ;
	Dart ee = beta3(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
280 281 282

	Dart fitD = dd ;
	Dart fitE = ee ;
283 284
	do
	{
285 286
		Dart fitD2 = beta2(fitD) ;
		Dart fitE2 = beta2(fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
287 288
		if(fitD2 != fitE)
		{
289 290
			beta2unsew(fitD) ;
			beta2unsew(fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
291 292
			beta2unsew(beta0(fitD)) ;
			beta2unsew(beta0(fitE)) ;
293 294 295 296
			beta2sew(fitD2, beta0(fitE2)) ;
			beta2sew(beta0(fitD2), fitE2) ;
			beta2sew(fitD, beta0(fitE)) ;
			beta2sew(beta0(fitD), fitE) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
297
		}
298 299 300 301
		beta3unsew(fitD) ;
		beta3unsew(beta0(fitD)) ;
		beta3unsew(fitE) ;
		beta3unsew(beta0(fitE)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
302 303 304
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != dd) ;
305
	GMap2::deleteCC(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
306 307 308

	fitD = d ;
	fitE = e ;
309 310
	do
	{
311 312
		beta3sew(fitD, beta0(fitE)) ;
		beta3sew(beta0(fitD), fitE) ;
313 314 315 316 317 318 319
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void GMap3::unsewVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
320 321 322 323 324 325 326 327 328 329 330 331
	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 ;
332 333
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
334 335 336 337
		Dart f = findBoundaryFaceOfEdge(fit1) ;
		if(f != NIL)
		{
			Dart f2 = phi2(f) ;
338 339 340 341 342 343
			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
344 345
		}
		else
346 347 348 349
		{
			beta2sew(fitB1, beta0(fitB2)) ;
			beta2sew(beta0(fitB1), fitB2) ;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
350

351 352 353 354 355 356
		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
357 358 359 360 361 362

		fit1 = phi1(fit1) ;
		fit2 = phi_1(fit2) ;
		fitB1 = phi_1(fitB1) ;
		fitB2 = phi1(fitB2) ;
	} while(fitB1 != b1) ;
363 364 365 366
}

bool GMap3::mergeVolumes(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
367
	if(!GMap3::isBoundaryFace(d))
368
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
369
		GMap2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
370 371 372 373 374
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
375 376 377 378 379 380 381 382 383 384 385 386 387 388 389
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
390
	GMap3::sewVolumes(beta2(e), beta2(e2), false);
Pierre Kraemer's avatar
Pierre Kraemer committed
391 392
}

393 394 395
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
396

397
bool GMap3::sameOrientedVertex(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
398
{
399 400
	DartMarkerStore mv(*this);	// Lock a marker

Pierre Kraemer's avatar
Pierre Kraemer committed
401 402 403
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
404 405
	mv.mark(d);

406
	for(unsigned int i = 0; i < darts.size(); ++i)
407
	{
408
		if(darts[i] == e)
409 410
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
411
		// add phi21 and phi23 successor if they are not marked yet
412
		Dart d2 = phi2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
413 414
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
415

Pierre Kraemer's avatar
Pierre Kraemer committed
416 417 418 419 420 421 422 423 424
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
425 426 427 428 429 430 431 432
		}
	}
	return false;
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
434 435 436
	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
437 438
	mv.mark(d);

439
	for(unsigned int i = 0; i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
440
	{
441
		if(darts[i] == e)
442 443
			return true;

444
		Dart dx = beta1(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
445 446
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
447
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
448 449
			mv.mark(dx);
		}
450
		dx = beta2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
451 452
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
453
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
454 455
			mv.mark(dx);
		}
456
		dx = beta3(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
457 458
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
459
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
460 461 462
			mv.mark(dx);
		}
	}
463
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
464 465
}

466 467
unsigned int GMap3::vertexDegree(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
468
	unsigned int count = 0;
469 470
	DartMarkerStore mv(*this);	// Lock a marker

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

476
	for(unsigned int i = 0; i < darts.size(); ++i)
477 478
	{
		//add phi21 and phi23 successor if they are not marked yet
479
		Dart d2 = phi2(darts[i]);
480 481 482 483 484
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

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

	DartMarkerStore me(*this);
Pierre Kraemer's avatar
Pierre Kraemer committed
496
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
497
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
498
		if(!me.isMarked(*it))
499 500
		{
			++count;
Pierre Kraemer's avatar
Pierre Kraemer committed
501
			me.markOrbit(EDGE, *it);
502 503 504 505 506 507 508 509
		}
	}

	return count;
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
512 513 514
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
515 516
	mv.mark(d);

517
	for(unsigned int i = 0; i < darts.size(); ++i)
518
	{
519
		if(isBoundaryMarked(darts[i]))
Pierre Kraemer's avatar
Pierre Kraemer committed
520
			return true ;
521 522

		//add phi21 and phi23 successor if they are not marked yet
523
		Dart d2 = phi2(darts[i]);
524 525 526 527 528
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
529
			darts.push_back(d21);
530 531
			mv.mark(d21);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
532
		if(!mv.isMarked(d23))
533
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
534
			darts.push_back(d23);
535 536 537
			mv.mark(d23);
		}
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
538
	return false ;
539 540
}

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

553
bool GMap3::sameEdge(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
554
{
Pierre Kraemer's avatar
Pierre Kraemer committed
555
	Dart it = d;
556 557
	do
	{
558
		if(it == e || beta0(it) == e || beta2(it) == e || phi2(it) == e)
559 560
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
561 562
		it = alpha2(it);
	} while (it != d);
563 564 565
	return false;
}

566 567 568
unsigned int GMap3::edgeDegree(Dart d)
{
	unsigned int deg = 0;
Pierre Kraemer's avatar
Pierre Kraemer committed
569
	Dart it = d;
570 571
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
572 573 574
		++deg;
		it = alpha2(it);
	} while(it != d);
575 576 577
	return deg;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
578
bool GMap3::isBoundaryEdge(Dart d)
579
{
Pierre Kraemer's avatar
Pierre Kraemer committed
580
	Dart it = d;
581 582
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
583 584 585 586
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
587 588 589
	return false;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
590
Dart GMap3::findBoundaryFaceOfEdge(Dart d)
591
{
Pierre Kraemer's avatar
Pierre Kraemer committed
592
	Dart it = d;
593 594
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
595 596 597 598 599 600
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
}
601

Pierre Kraemer's avatar
Pierre Kraemer committed
602 603 604 605 606 607
bool GMap3::sameOrientedFace(Dart d, Dart e)
{
	Dart it = d;
	do
	{
		if(it == e || phi3(it) == e)
608
			return true;
Pierre Kraemer's avatar
Pierre Kraemer committed
609 610 611 612
		it = phi1(it);
	} while (it != d);
	return false;
}
613

Pierre Kraemer's avatar
Pierre Kraemer committed
614 615 616
bool GMap3::isBoundaryVolume(Dart d)
{
	DartMarkerStore mark(*this);	// Lock a marker
617

Pierre Kraemer's avatar
Pierre Kraemer committed
618 619 620 621
	std::vector<Dart> visitedFaces ;
	visitedFaces.reserve(128) ;
	visitedFaces.push_back(d) ;
	mark.markOrbit(FACE, d) ;
622

623
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
624
	{
625
		if (isBoundaryMarked(beta3(visitedFaces[i])))
Pierre Kraemer's avatar
Pierre Kraemer committed
626 627
			return true ;

628
		Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
629 630 631 632 633 634 635 636 637
		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) ;
638
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
639
	}
640 641 642
	return false;
}

Thomas's avatar
Thomas committed
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 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717
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
718 719 720 721 722 723 724 725 726 727 728 729 730

    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
731 732 733
    return true;
}

734 735 736 737
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

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

Pierre Kraemer's avatar
Pierre Kraemer committed
743 744 745
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
746 747
	mv.mark(d);

748
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
749
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
750
		// add phi21 and phi23 successor if they are not marked yet
751
		Dart d2 = phi2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
752 753
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
754

Pierre Kraemer's avatar
Pierre Kraemer committed
755
		if(!mv.isMarked(d21))
756
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
757 758 759 760 761 762 763
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
764 765
		}

766
		found = f(darts[i]);
767 768 769 770
	}
	return found;
}

771
bool GMap3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
772
{
Pierre Kraemer's avatar
Pierre Kraemer committed
773
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
774
	bool found = false;					// Last functor return value
775

Pierre Kraemer's avatar
Pierre Kraemer committed
776 777 778
	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
779 780
	mv.mark(d);

781
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
782
	{
783
		Dart dx = beta1(darts[i]);
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);
		}
789
		dx = beta2(darts[i]);
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
			mv.mark(dx);
		}
795
		dx = beta3(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
796 797
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
798
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
799 800 801
			mv.mark(dx);
		}

802
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
803 804
	}
	return found;
805
}
Pierre Kraemer's avatar
Pierre Kraemer committed
806

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

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

Pierre Kraemer's avatar
Pierre Kraemer committed
824 825 826
	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
827 828
	mv.mark(d);

829
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
830
	{
831
		Dart dx = beta0(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
832 833
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
834
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
835 836
			mv.mark(dx);
		}
837
		dx = beta1(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
838 839
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
840
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
841 842
			mv.mark(dx);
		}
843
		dx = beta2(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
844 845
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
846
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
847 848
			mv.mark(dx);
		}
849
		dx = beta3(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
850 851
		if (!mv.isMarked(dx))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
852
			darts.push_back(dx);
Pierre Kraemer's avatar
Pierre Kraemer committed
853 854 855
			mv.mark(dx);
		}

856
		found =  f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
857 858 859 860
	}
	return found;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
861 862 863 864 865 866
/*! @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)
{
867
	assert(beta3(d) == d);		// Nothing to close
Pierre Kraemer's avatar
Pierre Kraemer committed
868 869 870 871 872
	DartMarkerStore m(*this) ;

	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
873
	m.markOrbit(FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
874 875 876 877

	unsigned int count = 0 ;

	// For every face added to the list
878
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
879
	{
880
		Dart f = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
881 882 883 884 885 886 887 888 889 890 891
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryFace(degree) ;
		++count ;

		Dart bit = b ;
		do
		{
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
892
				if(beta3(e) == e)
Pierre Kraemer's avatar
Pierre Kraemer committed
893 894 895 896 897
				{
					found = true ;
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
898
						m.markOrbit(FACE, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
899 900 901 902 903
					}
				}
				else if(isBoundaryMarked(e))
				{
					found = true ;
904 905
					beta2sew(e, bit) ;
					beta2sew(beta0(e), beta0(bit)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
906 907 908 909 910
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

911 912 913
			beta3sew(f, bit) ;
			beta3sew(beta0(f), beta0(bit)) ;
			bit = phi1(bit) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
914
			f = phi1(f);
915
		} while(f != visitedFaces[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931
	}

	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