map3.cpp 21.3 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-2012, 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.unistra.fr/                                           *
Pierre Kraemer's avatar
Pierre Kraemer committed
21 22 23 24 25
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Topology/map/map3.h"
untereiner's avatar
untereiner committed
26
#include "Topology/generic/traversor3.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
27 28 29 30

namespace CGoGN
{

Pierre Kraemer's avatar
Pierre Kraemer committed
31 32 33 34
void Map3::compactTopoRelations(const std::vector<unsigned int>& oldnew)
{
	for (unsigned int i = m_attribs[DART].begin(); i != m_attribs[DART].end(); m_attribs[DART].next(i))
	{
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
		unsigned int d_index = dartIndex(m_phi1->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi1->operator[](i) = Dart(oldnew[d_index]);

		d_index = dartIndex(m_phi_1->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi_1->operator[](i) = Dart(oldnew[d_index]);

		d_index = dartIndex(m_phi2->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi2->operator[](i) = Dart(oldnew[d_index]);

		d_index = dartIndex(m_phi3->operator[](i));
		if (d_index != oldnew[d_index])
			m_phi3->operator[](i) = Dart(oldnew[d_index]);
//
//		{
//			Dart& d = m_phi1->operator [](i);
//			Dart e = Dart(oldnew[d.index]);
//			if (d != e)
//				d = e;
//		}
//		{
//			Dart& d = m_phi_1->operator [](i);
//			Dart e = Dart(oldnew[d.index]);
//			if (d != e)
//				d = e;
//		}
//		{
//			Dart& d = m_phi2->operator [](i);
//			Dart e = Dart(oldnew[d.index]);
//			if (d != e)
//				d = e;
//		}
//		{
//			Dart& d = m_phi3->operator [](i);
//			Dart e = Dart(oldnew[d.index]);
//			if (d != e)
//				d = e;
//		}
Pierre Kraemer's avatar
Pierre Kraemer committed
75 76 77
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
78 79 80
/*! @name Generator and Deletor
 *  To generate or delete volumes in a 3-map
 *************************************************************************/
81 82

void Map3::deleteVolume(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
83 84 85 86
{
	DartMarkerStore mark(*this);		// Lock a marker

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

90 91 92
//	mark.markOrbit(ORIENTED_FACE, d) ;
	mark.markOrbit(FACE2, d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
93

94
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
95
	{
96
		Dart e = visitedFaces[i] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
97

98 99
		if(!isBoundaryFace(e))
			unsewVolumes(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
100 101 102 103 104 105 106

		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
107 108
//				mark.markOrbit(ORIENTED_FACE, ee) ;
				mark.markOrbit(FACE2, ee) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
109 110
			}
			e = phi1(e) ;
111
		} while(e != visitedFaces[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
112 113
	}

untereiner's avatar
untereiner committed
114 115 116
	Dart dd = phi3(d) ;
	Map2::deleteCC(d) ;
	Map2::deleteCC(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
117 118
}

119 120
void Map3::fillHole(Dart d)
{
121 122 123 124 125
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi3(dd) ;
	boundaryUnmarkOrbit(VOLUME, dd) ;
126 127
}

Pierre Kraemer's avatar
Pierre Kraemer committed
128 129 130 131
/*! @name Topological Operators
 *  Topological operations on 3-maps
 *************************************************************************/

132
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
133
{
134 135 136
	if(isBoundaryVertex(d))
		return NIL ;

Pierre Kraemer's avatar
Pierre Kraemer committed
137 138
	// Save the darts around the vertex
	// (one dart per face should be enough)
untereiner's avatar
untereiner committed
139
	std::vector<Dart> fstoretmp;
140
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
141 142 143
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

144
	 // just one dart per face
untereiner's avatar
untereiner committed
145
	std::vector<Dart> fstore;
146
	fstore.reserve(128);
untereiner's avatar
untereiner committed
147
	DartMarker mf(*this);
148
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
149
	{
150
		if(!mf.isMarked(fstoretmp[i]))
151
		{
152 153
			mf.markOrbit(FACE, fstoretmp[i]);
			fstore.push_back(fstoretmp[i]);
untereiner's avatar
untereiner committed
154
		}
155
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
156

157
	Dart res = NIL ;
untereiner's avatar
untereiner committed
158 159
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
160 161 162 163 164 165 166 167
		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) ;
168

169 170
			if(res == NIL)
				res = d2 ;
171

172 173 174 175
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
176 177

			fit = phi1(fit) ;
178
		}
untereiner's avatar
untereiner committed
179
	}
180

181
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
182

183
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
184 185
}

David Cazier's avatar
David Cazier committed
186
Dart Map3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
187 188 189
{
	Dart prev = d;
	Dart dd = alpha2(d);
David Cazier's avatar
David Cazier committed
190
	Dart nd = Map2::cutEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
191

192
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
193 194 195 196 197 198
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

199 200 201 202
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
203 204
	}

205 206 207 208
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
209

David Cazier's avatar
David Cazier committed
210
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
211 212
}

Pierre Kraemer's avatar
Pierre Kraemer committed
213
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
214
{
Pierre Kraemer's avatar
Pierre Kraemer committed
215 216
	if(vertexDegree(phi1(d)) == 2)
	{
217 218
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
219

220 221
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
222 223 224
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
225

226 227
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
228 229
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
230 231
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
232
		return true;
untereiner's avatar
untereiner committed
233
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
234
	return false;
untereiner's avatar
untereiner committed
235 236
}

237 238 239 240 241 242 243
bool Map3::deleteEdgePreCond(Dart d)
{
	unsigned int nb1 = vertexDegree(d);
	unsigned int nb2 = vertexDegree(phi1(d));
	return (nb1!=2) && (nb2!=2);
}

untereiner's avatar
untereiner committed
244 245
Dart Map3::deleteEdge(Dart d)
{
246 247
	assert(deleteEdgePreCond(d));

untereiner's avatar
untereiner committed
248 249 250 251
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
252 253
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
254
	{
255 256
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
257 258 259 260 261 262
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
263

untereiner's avatar
untereiner committed
264 265
			if(res == NIL)
				res = d2 ;
266

untereiner's avatar
untereiner committed
267 268 269 270
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
271 272

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
273
		}
274 275 276
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
277 278 279 280 281
	Map2::deleteCC(d) ;

	return res ;
}

282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314
//Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
//{
//	Dart resV = NIL;
//
//	Dart dit = d;
//
//	do
//	{
//		Dart e = dit;
//		dit = alpha2(dit);
//
//		//test si un seul polyedre autour de l'arete
//		if(e == dit)
//			resV == phi3(phi2(phi1(e)));
//
//		if(delDegenerateVolumes)
//		{
//			Map2::collapseEdge(e, true);
//			collapseDegeneretedVolume(e);
//		}
//		else
//			Map2::collapseEdge(e, false);
//
//		if(resV == NIL)
//		{
//
//		}
//
//	}while(d != dit);
//
//	return resV;
//}

untereiner's avatar
untereiner committed
315 316 317
Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
318
	Dart dit = d;
untereiner's avatar
untereiner committed
319

320
	std::vector<Dart> darts;
untereiner's avatar
untereiner committed
321 322
	do
	{
323
		darts.push_back(dit);
324
		dit = alpha2(dit);
325
	}while(dit != d);
untereiner's avatar
untereiner committed
326

327 328 329 330 331 332 333
	for (std::vector<Dart>::iterator it = darts.begin(); it != darts.end(); ++it)
	{
		Dart x = phi2(phi_1(*it));
		resV = Map2::collapseEdge(*it, true);
		if (delDegenerateVolumes)
			collapseDegeneretedVolume(x);
	}
334

335 336
	return resV;
}
337 338 339



340

341 342 343 344 345 346 347 348 349 350 351 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 383 384 385 386 387 388 389
//	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
390

391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420
//bool Map3::collapseDegeneratedFace(Dart d)
//{
//	Dart d3 = phi3(d);
//
//	std::cout << "Map3::collapseDegeneratedFace"<< std::endl;
//
//	if (!isDartValid(d))
//		Map2::collapseDegeneratedFace(d);
//	else
//		std::cout << "Warning Coll1 invalid"<< std::endl;
//
//
//	if (isDartValid(d3))
//		Map2::collapseDegeneratedFace(d3);
//	else
//		std::cout << "Warning coll2 invalid"<< std::endl;
//
//
//
///*
//	Map3::unsewVolumes(d);
//
//	std::cout << Map2::collapseDegeneratedFace(d) << std::endl;
//	std::cout << Map2::collapseDegeneratedFace(d3) << std::endl;
//	std::cout << std::endl;
//*/
//	return true;
//}

bool Map3::splitFacePreCond(Dart d, Dart e)
421
{
422
	return (d != e && sameOrientedFace(d, e)) ;
423
}
untereiner's avatar
untereiner committed
424

425
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
426
{
427 428
//	assert(d != e && sameOrientedFace(d, e)) ;
	assert(splitFacePreCond(d,e));
Pierre Kraemer's avatar
Pierre Kraemer committed
429

430 431
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
432

untereiner's avatar
untereiner committed
433
	Map2::splitFace(d, e);
434
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
435

436 437
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
438 439
}

440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461
//bool Map3::collapseDegeneretedVolume(Dart d)
//{
//	Dart e1 = phi2(d);
//	Dart e2 = phi2(phi1(d));
//
//	//Si les deux faces ne sont pas du bord
//	if(!isBoundaryFace(e1) && !isBoundaryFace(e2))
//	{
//		sewVolumes(phi3(e1),phi3(e2));
//		deleteVolume(d);
//		return true;
//	}
//	else
//	{
//		//alors simple suppression du volume degenere
//		deleteVolume(d);
//		return true;
//	}
//
//	return false;
//}

462 463
bool Map3::collapseDegeneretedVolume(Dart d)
{
464 465
	Dart e1 = d;
	Dart e2 = phi2(d);
466

467
	do
468
	{
469 470 471 472 473 474 475 476 477 478 479
		if (e1 != phi2(e2))
			return false;
		e1 = phi1(e1);
		e2 = phi_1(e2);
	}while (e1 != d);

	if (e2 != phi2(d))
		return false;

	// degenerated:
	do
480
	{
481 482 483 484 485 486 487 488
		Dart f1 = phi3(e1);
		Dart f2 = phi3(e2);
		phi3unsew(e1);
		phi3unsew(e2);
		phi3sew(f1,f2);
		e1 = phi1(e1);
		e2 = phi_1(e2);
	}while (e1 != d);
489

490 491 492 493 494 495 496 497
	Map2::deleteCC(d) ;
	return true;
}


bool Map3::sewVolumesPreCond(Dart d, Dart e)
{
	return (faceDegree(d) == faceDegree(e));
498 499
}

500
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
501
{
502
	assert(sewVolumesPreCond(d,e));
503

504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534
	// 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) ;
		}
535 536
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
537 538
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
539
	} while(fitD != dd) ;
540 541
	Map2::deleteCC(dd) ;

542 543
	fitD = d ;
	fitE = e ;
544 545
	do
	{
546
		phi3sew(fitD, fitE) ;
547 548 549 550 551
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

552 553 554 555 556 557
bool Map3::unsewVolumesPreCond(Dart d)
{
	return (!isBoundaryFace(d)) ;
}


558 559
void Map3::unsewVolumes(Dart d)
{
560
	assert(unsewVolumesPreCond(d)) ;
untereiner's avatar
untereiner committed
561 562 563 564 565 566 567 568 569 570 571

	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 ;
572 573
	do
	{
untereiner's avatar
untereiner committed
574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593
		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) ;
594 595 596 597
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
598
	if(!Map3::isBoundaryFace(d))
599
	{
untereiner's avatar
untereiner committed
600
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
601 602 603 604 605
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
606 607
void Map3::splitVolume(std::vector<Dart>& vd)
{
608
	//assert(checkSimpleOrientedPath(vd)) ;
untereiner's avatar
untereiner committed
609

untereiner's avatar
untereiner committed
610 611 612
	Dart e = vd.front();
	Dart e2 = phi2(e);

613 614 615 616 617 618
//	//unsew the edge path
//	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
//		Map2::unsewFaces(*it);
//
//	Map2::fillHole(e) ;
//	Map2::fillHole(e2) ;
untereiner's avatar
untereiner committed
619

620
	Map2::splitSurface(vd,true,true);
untereiner's avatar
untereiner committed
621

untereiner's avatar
untereiner committed
622
	//sew the two connected components
untereiner's avatar
untereiner committed
623
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
624 625
}

626 627 628 629
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

630
bool Map3::sameVertex(Dart d, Dart e)
631 632 633
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
634 635 636
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
637 638
	mv.mark(d);

639
	for(unsigned int i = 0; i < darts.size(); ++i)
640
	{
641
		if(darts[i] == e)
642 643
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
644
		// add phi21 and phi23 successor if they are not marked yet
645
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
646 647
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
648

untereiner's avatar
untereiner committed
649 650 651 652 653 654 655 656 657
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
658 659 660 661 662
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
663 664
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
665
	unsigned int count = 0;
untereiner's avatar
untereiner committed
666 667
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
668 669 670
	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
671 672
	mv.mark(d);

673
	for(unsigned int i = 0; i < darts.size(); ++i)
untereiner's avatar
untereiner committed
674 675
	{
		//add phi21 and phi23 successor if they are not marked yet
676
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
677 678 679 680 681
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
682
			darts.push_back(d21);
untereiner's avatar
untereiner committed
683 684
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
685
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
686
		{
untereiner's avatar
untereiner committed
687
			darts.push_back(d23);
untereiner's avatar
untereiner committed
688 689 690 691 692
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
untereiner's avatar
untereiner committed
693
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
694
	{
untereiner's avatar
untereiner committed
695
		if(!me.isMarked(*it))
untereiner's avatar
untereiner committed
696 697
		{
			++count;
untereiner's avatar
untereiner committed
698
			me.markOrbit(EDGE, *it);
untereiner's avatar
untereiner committed
699 700 701 702 703 704
		}
	}

	return count;
}

705 706
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
707
	DartMarkerStore mv(*this);	// Lock a marker
708

untereiner's avatar
untereiner committed
709 710 711
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
712 713
	mv.mark(d);

714
	for(unsigned int i = 0; i < darts.size(); ++i)
715
	{
716
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
717
			return true ;
718 719

		//add phi21 and phi23 successor if they are not marked yet
720
		Dart d2 = phi2(darts[i]);
721 722 723 724 725
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
726
			darts.push_back(d21);
727 728
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
729
		if(!mv.isMarked(d23))
730
		{
untereiner's avatar
untereiner committed
731
			darts.push_back(d23);
732 733 734
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
735
	return false ;
736 737 738 739
}

bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
740
	Dart it = d;
741 742
	do
	{
untereiner's avatar
untereiner committed
743
		if(it == e)
744
			return true;
untereiner's avatar
untereiner committed
745 746
		it = alpha2(it);
	} while (it != d);
747 748 749
	return false;
}

untereiner's avatar
untereiner committed
750
unsigned int Map3::edgeDegree(Dart d)
751
{
untereiner's avatar
untereiner committed
752
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
753
	Dart it = d;
754 755
	do
	{
untereiner's avatar
untereiner committed
756 757 758
		++deg;
		it = alpha2(it);
	} while(it != d);
759 760 761
	return deg;
}

untereiner's avatar
untereiner committed
762
bool Map3::isBoundaryEdge(Dart d)
763
{
untereiner's avatar
untereiner committed
764 765 766 767 768 769 770 771
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
772 773
}

untereiner's avatar
untereiner committed
774
Dart Map3::findBoundaryFaceOfEdge(Dart d)
775
{
untereiner's avatar
untereiner committed
776 777 778 779 780 781 782 783
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
784 785
}

Pierre Kraemer's avatar
Pierre Kraemer committed
786 787
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
788 789
	Traversor3WF<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
790
	{
untereiner's avatar
untereiner committed
791
		if(isBoundaryMarked(phi3(dit)))
untereiner's avatar
untereiner committed
792
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
793
	}
untereiner's avatar
untereiner committed
794
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
795 796
}

797 798
bool Map3::hasBoundaryEdge(Dart d)
{
untereiner's avatar
untereiner committed
799 800
	Traversor3WE<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
801
	{
untereiner's avatar
untereiner committed
802 803
		if(isBoundaryEdge(dit))
			return true;
804
	}
untereiner's avatar
untereiner committed
805

806 807 808
	return false;
}

809
bool Map3::check()
810
{
811 812 813 814 815 816 817 818 819 820
    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;
        }
821

untereiner's avatar
untereiner committed
822 823 824 825 826
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
			return false;
		}
827

828 829 830 831 832 833
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
834

835 836 837 838 839 840
        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;
        }
841

842
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
843
		{
844 845 846 847
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
848

849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864
        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 ?
865
		{
866 867 868 869
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
870

871
    std::cout << "Check: topology ok" << std::endl;
872

873
    return true;
874 875
}

Pierre Kraemer's avatar
Pierre Kraemer committed
876 877 878 879
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
880
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
881
{
untereiner's avatar
untereiner committed
882
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
883 884
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
885 886 887
	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
888 889
	mv.mark(d);

890
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
891
	{
892
		// add phi21 and phi23 successor if they are not marked yet
893
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
894 895
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
896

untereiner's avatar
untereiner committed
897 898 899 900 901 902 903 904 905
		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
906 907
		}

908
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
909 910 911 912
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
913
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
914
{
untereiner's avatar
untereiner committed
915
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
916 917
	do
	{
untereiner's avatar
untereiner committed
918
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
919
			return true;
untereiner's avatar
untereiner committed
920 921
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
922 923 924
	return false;
}

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

untereiner's avatar
untereiner committed
930 931 932
	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
933 934
	mv.mark(d);

935
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
936
	{
untereiner's avatar
untereiner committed
937
		// add all successors if they are not marked yet
938 939 940
		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
941

untereiner's avatar
untereiner committed
942 943 944 945 946
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
947 948
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
949 950
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
951 952 953
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
954
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
955 956 957
			mv.mark(d4);
		}

958
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
959 960 961 962
	}
	return found;
}

untereiner's avatar
untereiner committed
963 964 965
/*! @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
966

untereiner's avatar
untereiner committed
967
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
968
{
untereiner's avatar
untereiner committed
969
	assert(phi3(d) == d);		// Nothing to close
970
	DartMarkerStore m(*this) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
971

untereiner's avatar
untereiner committed
972 973 974
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
975 976
//	m.markOrbit(ORIENTED_FACE, d) ;
	m.markOrbit(FACE2, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
977

untereiner's avatar
untereiner committed
978
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
979

untereiner's avatar
untereiner committed
980
	// For every face added to the list
981
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
982
	{
983 984 985
		Dart it = visitedFaces[i] ;
		Dart f = it ;

untereiner's avatar
untereiner committed
986 987 988
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
989

untereiner's avatar
untereiner committed
990 991
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
992
		{
untereiner's avatar
untereiner committed
993 994 995 996 997 998 999
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
				if(phi3(e) == e)
				{
					found = true ;
1000 1001 1002
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
1003
						m.markOrbit(FACE2, e) ;
1004
					}
untereiner's avatar
untereiner committed
1005
				}
1006
				else if(isBoundaryMarked(e))
untereiner's avatar
untereiner committed
1007 1008
				{
					found = true ;
1009
					phi2sew(e, bit) ;
untereiner's avatar
untereiner committed
1010 1011 1012 1013 1014 1015 1016 1017
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
1018
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1019 1020
	}

untereiner's avatar
untereiner committed
1021 1022 1023
	return count ;
}

1024
unsigned int Map3::closeMap()
untereiner's avatar
untereiner committed
1025 1026
{
	// Search the map for topological holes (fix points of phi3)
1027
	unsigned int nb = 0 ;
untereiner's avatar
untereiner committed
1028 1029 1030
	for (Dart d = begin(); d != end(); next(d))
	{
		if (phi3(d) == d)
1031 1032
		{
			++nb ;
untereiner's avatar
untereiner committed
1033
			closeHole(d);
1034
		}
untereiner's avatar
untereiner committed
1035
	}
1036
	return nb ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1037 1038 1039
}

} // namespace CGoGN