map3.cpp 18.7 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 31 32
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/map3.h"

namespace CGoGN
{

/*! @name Generator and Deletor
 *  To generate or delete volumes in a 3-map
 *************************************************************************/
33 34

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

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

42
	mark.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
43

44
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
45
	{
46
		Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
47

48 49
		if(!isBoundaryFace(e))
			unsewVolumes(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
50 51 52 53 54 55 56

		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
57
				mark.markOrbit(ORIENTED_FACE, ee) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
58 59
			}
			e = phi1(e) ;
60
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
61 62
	}

untereiner's avatar
untereiner committed
63 64 65
	Dart dd = phi3(d) ;
	Map2::deleteCC(d) ;
	Map2::deleteCC(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
66 67
}

68 69
void Map3::fillHole(Dart d)
{
70 71 72 73 74
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi3(dd) ;
	boundaryUnmarkOrbit(VOLUME, dd) ;
75 76
}

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

81
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
82
{
83 84 85
	if(isBoundaryVertex(d))
		return NIL ;

Pierre Kraemer's avatar
Pierre Kraemer committed
86 87
	// Save the darts around the vertex
	// (one dart per face should be enough)
untereiner's avatar
untereiner committed
88
	std::vector<Dart> fstoretmp;
89
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
90 91 92
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

Pierre Kraemer's avatar
Pierre Kraemer committed
93
	// just one dart per face
untereiner's avatar
untereiner committed
94
	std::vector<Dart> fstore;
95
	fstore.reserve(128);
untereiner's avatar
untereiner committed
96
	DartMarker mf(*this);
97
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
98
	{
99
		if(!mf.isMarked(fstoretmp[i]))
100
		{
101 102
			mf.markOrbit(FACE, fstoretmp[i]);
			fstore.push_back(fstoretmp[i]);
untereiner's avatar
untereiner committed
103
		}
104
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
105

106
	Dart res = NIL ;
untereiner's avatar
untereiner committed
107 108
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
109 110 111 112 113 114 115 116
		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) ;
117

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

121 122 123 124
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
125 126

			fit = phi1(fit) ;
127
		}
untereiner's avatar
untereiner committed
128
	}
129

130
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
131

132
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
133 134
}

David Cazier's avatar
David Cazier committed
135
Dart Map3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
136 137 138
{
	Dart prev = d;
	Dart dd = alpha2(d);
David Cazier's avatar
David Cazier committed
139
	Dart nd = Map2::cutEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
140

141
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
142 143 144 145 146 147
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

148 149 150 151
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
152 153
	}

154 155 156 157
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
158

David Cazier's avatar
David Cazier committed
159
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
160 161
}

Pierre Kraemer's avatar
Pierre Kraemer committed
162
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
163
{
Pierre Kraemer's avatar
Pierre Kraemer committed
164 165
	if(vertexDegree(phi1(d)) == 2)
	{
166 167
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
168

169 170
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
171 172 173
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
174

175 176
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
177 178
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
179 180
		} while (dd != d) ;

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

untereiner's avatar
untereiner committed
186 187 188 189 190 191
Dart Map3::deleteEdge(Dart d)
{
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
192 193
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
194
	{
195 196
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
197 198 199 200 201 202
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
203

untereiner's avatar
untereiner committed
204 205
			if(res == NIL)
				res = d2 ;
206

untereiner's avatar
untereiner committed
207 208 209 210
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
211 212

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
213
		}
214 215 216
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
217 218 219 220 221 222 223 224 225
	Map2::deleteCC(d) ;

	return res ;
}

Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;

226
	Dart dit = d;
untereiner's avatar
untereiner committed
227 228 229

	do
	{
230 231
		Dart e = dit;
		dit = alpha2(dit);
untereiner's avatar
untereiner committed
232

233 234 235
		//test si un seul polyedre autour de l'arete
		if(e == dit)
			resV == phi3(phi2(phi1(e)));
untereiner's avatar
untereiner committed
236

237
		if(delDegenerateVolumes)
untereiner's avatar
untereiner committed
238
		{
239 240 241 242 243
			Map2::collapseEdge(e, true);
			//collapseDegeneretedVolume(e);
		}
		else
			Map2::collapseEdge(e, false);
untereiner's avatar
untereiner committed
244

245 246
		if(resV == NIL)
		{
untereiner's avatar
untereiner committed
247

248
		}
untereiner's avatar
untereiner committed
249 250


251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305
	}while(d != dit);





//	Dart e = d;
//
//	// stocke un brin par volume autour de l'arete
//	std::vector<Dart> tmp;
//	tmp.reserve(32);
//	do
//	{
//		tmp.push_back(e);
//		e = alpha2(e);
//	} while (e != d);
//
//	// contraction de la 2 carte de chaque 2-arete
//	for (std::vector<Dart>::iterator it = tmp.begin(); it != tmp.end(); ++it)
//	{
//		// un brin d'une face adjacente a l'arrete contracte
//		Dart d = phi2(phi_1(*it));
//		Map2::collapseEdge(*it, true);
//
//		// test de la degeneresence
//		// impossible d'avoir un volume de moins de 4 faces sans avoir de phi2 en points fixe donc on les vire
//		if(delDegenerateVolumes && Map2::volumeDegree(d) < 4)
//		{
//			Dart e = d;
//			// pour tous les brins de la face adjacente
//
//			do
//			{
//				Dart ee = phi3(e);
//				Dart ff = phi3(phi2(e));
//
//				// si les brins ont un voisin par phi3
//				if(ee != e)
//
//					phi3unsew(ee);
//				if(ff != phi2(e))
//					phi3unsew(ff);
//
//				// si les deux en ont un, il faut les coudres ensemble
//				if(ee != e && ff != phi2(e))
//					phi3sew(ee, ff);
//
//				// on peut supprimer les brins de cette arete
//				deleteDart(e);
//				deleteDart(phi2(e));
//				e = phi1(e);
//
//			} while (e != d);
//		}
//	}
untereiner's avatar
untereiner committed
306 307 308 309

	return resV;
}

310
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
311
{
312
	assert(d != e && Map2::sameOrientedFace(d, e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
313

314 315
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
316

untereiner's avatar
untereiner committed
317
	Map2::splitFace(d, e);
318
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
319

320 321
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
322 323
}

324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347
bool Map3::collapseDegeneretedVolume(Dart d)
{
	Dart e1 = phi2(d);
	Dart e2 = phi2(phi1(d));

	//Si l'une des faces est du bord
	if(isBoundaryFace(e1) || isBoundaryFace(e2))
	{
		//alors simple suppression du volume degenere
	}
	else
	{
		Dart e13 = e1;
		Dart e23 = e2;
		if(!isBoundaryFace(e1))
			e13 = phi3(e1);

		if(!isBoundaryFace(e2))
			e23 = phi3(e2);

		//if(faceDegree(e1) < faceDegree)
	}
}

348
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
349 350 351
{
	assert(faceDegree(d) == faceDegree(e));

352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382
	// 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 ;
	do
	{
		Dart fitD2 = phi2(fitD) ;
		Dart fitE2 = phi2(fitE) ;
		if(fitD2 != fitE)
		{
			phi2unsew(fitD) ;
			phi2unsew(fitE) ;
			phi2sew(fitD2, fitE2) ;
			phi2sew(fitD, fitE) ;
		}
383 384
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
385 386
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
387
	} while(fitD != dd) ;
388 389
	Map2::deleteCC(dd) ;

390 391
	fitD = d ;
	fitE = e ;
392 393
	do
	{
394
		phi3sew(fitD, fitE) ;
395 396 397 398 399 400 401
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

void Map3::unsewVolumes(Dart d)
{
untereiner's avatar
untereiner committed
402 403 404 405 406 407 408 409 410 411 412 413
	assert(!isBoundaryFace(d)) ;

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

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

	Dart fit1 = d ;
	Dart fit2 = d3 ;
	Dart fitB1 = b1 ;
	Dart fitB2 = b2 ;
414 415
	do
	{
untereiner's avatar
untereiner committed
416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435
		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) ;
436 437 438 439
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
440
	if(!Map3::isBoundaryFace(d))
441
	{
untereiner's avatar
untereiner committed
442
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
443 444 445 446 447
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
448 449
void Map3::splitVolume(std::vector<Dart>& vd)
{
untereiner's avatar
untereiner committed
450 451
	assert(checkSimpleOrientedPath(vd)) ;

untereiner's avatar
untereiner committed
452 453 454 455 456 457 458
	Dart e = vd.front();
	Dart e2 = phi2(e);

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

untereiner's avatar
untereiner committed
459 460
	Map2::fillHole(e) ;
	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
461

untereiner's avatar
untereiner committed
462 463
	//sew the two connected components
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
464 465
}

466 467 468 469
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

470
bool Map3::sameVertex(Dart d, Dart e)
471 472 473
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
474 475 476
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
477 478
	mv.mark(d);

479
	for(unsigned int i = 0; i < darts.size(); ++i)
480
	{
481
		if(darts[i] == e)
482 483
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
484
		// add phi21 and phi23 successor if they are not marked yet
485
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
486 487
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
488

untereiner's avatar
untereiner committed
489 490 491 492 493 494 495 496 497
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
498 499 500 501 502
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
503 504
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
505
	unsigned int count = 0;
untereiner's avatar
untereiner committed
506 507
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
508 509 510
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
untereiner's avatar
untereiner committed
511 512
	mv.mark(d);

513
	for(unsigned int i = 0; i < darts.size(); ++i)
untereiner's avatar
untereiner committed
514 515
	{
		//add phi21 and phi23 successor if they are not marked yet
516
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
517 518 519 520 521
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
522
			darts.push_back(d21);
untereiner's avatar
untereiner committed
523 524
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
525
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
526
		{
untereiner's avatar
untereiner committed
527
			darts.push_back(d23);
untereiner's avatar
untereiner committed
528 529 530 531 532
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
untereiner's avatar
untereiner committed
533
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
534
	{
untereiner's avatar
untereiner committed
535
		if(!me.isMarked(*it))
untereiner's avatar
untereiner committed
536 537
		{
			++count;
untereiner's avatar
untereiner committed
538
			me.markOrbit(EDGE, *it);
untereiner's avatar
untereiner committed
539 540 541 542 543 544
		}
	}

	return count;
}

545 546
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
547
	DartMarkerStore mv(*this);	// Lock a marker
548

untereiner's avatar
untereiner committed
549 550 551
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
552 553
	mv.mark(d);

554
	for(unsigned int i = 0; i < darts.size(); ++i)
555
	{
556
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
557
			return true ;
558 559

		//add phi21 and phi23 successor if they are not marked yet
560
		Dart d2 = phi2(darts[i]);
561 562 563 564 565
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
566
			darts.push_back(d21);
567 568
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
569
		if(!mv.isMarked(d23))
570
		{
untereiner's avatar
untereiner committed
571
			darts.push_back(d23);
572 573 574
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
575
	return false ;
576 577 578 579
}

bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
580
	Dart it = d;
581 582
	do
	{
untereiner's avatar
untereiner committed
583
		if(it == e)
584
			return true;
untereiner's avatar
untereiner committed
585 586
		it = alpha2(it);
	} while (it != d);
587 588 589
	return false;
}

untereiner's avatar
untereiner committed
590
unsigned int Map3::edgeDegree(Dart d)
591
{
untereiner's avatar
untereiner committed
592
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
593
	Dart it = d;
594 595
	do
	{
untereiner's avatar
untereiner committed
596 597 598
		++deg;
		it = alpha2(it);
	} while(it != d);
599 600 601
	return deg;
}

untereiner's avatar
untereiner committed
602
bool Map3::isBoundaryEdge(Dart d)
603
{
untereiner's avatar
untereiner committed
604 605 606 607 608 609 610 611
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
612 613
}

untereiner's avatar
untereiner committed
614
Dart Map3::findBoundaryFaceOfEdge(Dart d)
615
{
untereiner's avatar
untereiner committed
616 617 618 619 620 621 622 623
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
624 625
}

Pierre Kraemer's avatar
Pierre Kraemer committed
626 627
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
628
	DartMarkerStore mark(*this);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
629 630

	std::vector<Dart> visitedFaces ;
untereiner's avatar
untereiner committed
631
	visitedFaces.reserve(128) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
632
	visitedFaces.push_back(d) ;
untereiner's avatar
untereiner committed
633
	mark.markOrbit(ORIENTED_FACE, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
634

635
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
636
	{
637
		if (isBoundaryMarked(phi3(visitedFaces[i])))
untereiner's avatar
untereiner committed
638
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
639

640
		Dart e = visitedFaces[i] ;
untereiner's avatar
untereiner committed
641
		do	// add all face neighbours to the table
Pierre Kraemer's avatar
Pierre Kraemer committed
642
		{
untereiner's avatar
untereiner committed
643 644
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
Pierre Kraemer's avatar
Pierre Kraemer committed
645
			{
untereiner's avatar
untereiner committed
646 647 648 649
				visitedFaces.push_back(ee) ;
				mark.markOrbit(ORIENTED_FACE, ee) ;
			}
			e = phi1(e) ;
650
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
651
	}
untereiner's avatar
untereiner committed
652
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
653 654
}

655
bool Map3::check()
656
{
657 658 659 660 661 662 663 664 665 666
    std::cout << "Check: topology begin" << std::endl;
    DartMarker m(*this);
    for(Dart d = Map3::begin(); d != Map3::end(); Map3::next(d))
    {
        Dart d3 = phi3(d);
        if (phi3(d3) != d) // phi3 involution ?
		{
            std::cout << "Check: phi3 is not an involution" << std::endl;
            return false;
        }
667

untereiner's avatar
untereiner committed
668 669 670 671 672
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
			return false;
		}
673

674 675 676 677 678 679
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
680

681 682 683 684 685 686
        Dart d1 = phi1(d);
        if (phi_1(d1) != d) // phi1 a une image correcte ?
		{
            std::cout << "Check: unconsistent phi_1 link" << std::endl;
            return false;
        }
687

688
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
689
		{
690 691 692 693
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
694

695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710
        if (d1 == d)
            std::cout << "Check: (warning) face loop (one edge)" << std::endl;

        if (phi1(d1) == d)
            std::cout << "Check: (warning) face with only two edges" << std::endl;

        if (phi2(d1) == d)
            std::cout << "Check: (warning) dandling edge (phi2)" << std::endl;

        if (phi3(d1) == d)
            std::cout << "Check: (warning) dandling edge (phi3)" << std::endl;
    }

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

717
    std::cout << "Check: topology ok" << std::endl;
718

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

untereiner's avatar
untereiner committed
722 723 724 725 726 727 728 729 730
    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 ;

731
    return true;
732 733
}

Pierre Kraemer's avatar
Pierre Kraemer committed
734 735 736 737
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

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

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

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

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

766
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
767 768 769 770
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
771
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
772
{
untereiner's avatar
untereiner committed
773
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
774 775
	do
	{
untereiner's avatar
untereiner committed
776
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
777
			return true;
untereiner's avatar
untereiner committed
778 779
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
780 781 782
	return false;
}

untereiner's avatar
untereiner committed
783
bool Map3::foreach_dart_of_cc(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
784
{
Sylvain Thery's avatar
Sylvain Thery committed
785
	DartMarkerStore mv(*this,thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
786 787
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
788 789 790
	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
791 792
	mv.mark(d);

793
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
794
	{
untereiner's avatar
untereiner committed
795
		// add all successors if they are not marked yet
796 797 798
		Dart d2 = phi1(darts[i]); // turn in face
		Dart d3 = phi2(darts[i]); // change face
		Dart d4 = phi3(darts[i]); // change volume
Pierre Kraemer's avatar
Pierre Kraemer committed
799

untereiner's avatar
untereiner committed
800 801 802 803 804
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
805 806
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
807 808
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
809 810 811
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
812
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
813 814 815
			mv.mark(d4);
		}

816
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
817 818 819 820
	}
	return found;
}

untereiner's avatar
untereiner committed
821 822 823
/*! @name Close map after import or creation
 *  These functions must be used with care, generally only by import/creation algorithms
 *************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
824

untereiner's avatar
untereiner committed
825
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
826
{
untereiner's avatar
untereiner committed
827
	assert(phi3(d) == d);		// Nothing to close
828
	DartMarkerStore m(*this) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
829

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

untereiner's avatar
untereiner committed
835
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
836

untereiner's avatar
untereiner committed
837
	// For every face added to the list
838
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
839
	{
840 841 842
		Dart it = visitedFaces[i] ;
		Dart f = it ;

untereiner's avatar
untereiner committed
843 844 845
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
846

untereiner's avatar
untereiner committed
847 848
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
849
		{
untereiner's avatar
untereiner committed
850 851 852 853 854 855 856
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
				if(phi3(e) == e)
				{
					found = true ;
857 858 859 860 861
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
						m.markOrbit(ORIENTED_FACE, e) ;
					}
untereiner's avatar
untereiner committed
862
				}
863
				else if(isBoundaryMarked(e))
untereiner's avatar
untereiner committed
864 865
				{
					found = true ;
866
					phi2sew(e, bit) ;
untereiner's avatar
untereiner committed
867 868 869 870 871 872 873 874
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
875
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
876 877
	}

untereiner's avatar
untereiner committed
878 879 880 881 882 883 884 885 886 887 888
	return count ;
}

void Map3::closeMap()
{
	// Search the map for topological holes (fix points of phi3)
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi3(d) == d)
			closeHole(d);
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
889 890 891
}

} // namespace CGoGN