map3.cpp 23.4 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1 2 3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-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
merges  
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
merges  
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
 *************************************************************************/

untereiner's avatar
untereiner committed
132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
void Map3::splitVertex(Dart d, Dart e)
{
	assert(sameVertex(d,e));
	assert(!sameVolume(d,e));

	if(isBoundaryVertex(d))
	{
		unsewVolumes(d);
		unsewVolumes(e);

		Dart dc = phi1(phi2(d));

		//unsewVolumes(phi2(dc));
		Map2::splitVertex(d, phi1(phi2(dc)));


//		Map2::splitFace(d, phi2(dc));

//		Dart ec = phi_1(phi2(e));
//		Map2::splitVertex(e, ec);
//		//Map2::splitFace(e, phi2(ec));
	}
}

156
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
157
{
158 159 160
	if(isBoundaryVertex(d))
		return NIL ;

Pierre Kraemer's avatar
Pierre Kraemer committed
161 162
	// Save the darts around the vertex
	// (one dart per face should be enough)
untereiner's avatar
untereiner committed
163
	std::vector<Dart> fstoretmp;
164
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
165 166 167
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

168
	 // just one dart per face
untereiner's avatar
untereiner committed
169
	std::vector<Dart> fstore;
170
	fstore.reserve(128);
untereiner's avatar
untereiner committed
171
	DartMarker mf(*this);
172
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
173
	{
174
		if(!mf.isMarked(fstoretmp[i]))
175
		{
176 177
			mf.markOrbit(FACE, fstoretmp[i]);
			fstore.push_back(fstoretmp[i]);
untereiner's avatar
untereiner committed
178
		}
179
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
180

181
	Dart res = NIL ;
untereiner's avatar
untereiner committed
182 183
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
184 185 186 187 188 189 190 191
		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) ;
192

193 194
			if(res == NIL)
				res = d2 ;
195

196 197 198 199
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
200 201

			fit = phi1(fit) ;
202
		}
untereiner's avatar
untereiner committed
203
	}
204

205
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
206

207
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
208 209
}

David Cazier's avatar
David Cazier committed
210
Dart Map3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
211 212 213
{
	Dart prev = d;
	Dart dd = alpha2(d);
David Cazier's avatar
David Cazier committed
214
	Dart nd = Map2::cutEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
215

216
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
217 218 219 220 221 222
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

223 224 225 226
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
227 228
	}

229 230 231 232
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
233

David Cazier's avatar
David Cazier committed
234
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
235 236
}

Pierre Kraemer's avatar
Pierre Kraemer committed
237
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
238
{
Pierre Kraemer's avatar
Pierre Kraemer committed
239 240
	if(vertexDegree(phi1(d)) == 2)
	{
241 242
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
243

244 245
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
246 247 248
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
249

250 251
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
252 253
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
254 255
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
256
		return true;
untereiner's avatar
untereiner committed
257
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
258
	return false;
untereiner's avatar
untereiner committed
259 260
}

Sylvain Thery's avatar
Sylvain Thery committed
261 262 263 264 265 266 267
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
268 269
Dart Map3::deleteEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
270 271
	assert(deleteEdgePreCond(d));

untereiner's avatar
untereiner committed
272 273 274 275
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
276 277
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
278
	{
279 280
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
281 282 283 284 285 286
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
287

untereiner's avatar
untereiner committed
288 289
			if(res == NIL)
				res = d2 ;
290

untereiner's avatar
untereiner committed
291 292 293 294
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
295 296

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
297
		}
298 299 300
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
301 302 303 304 305
	Map2::deleteCC(d) ;

	return res ;
}

Sylvain Thery's avatar
Sylvain Thery committed
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338
//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
339 340 341
Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
342
	Dart dit = d;
untereiner's avatar
untereiner committed
343

Sylvain Thery's avatar
Sylvain Thery committed
344
	std::vector<Dart> darts;
untereiner's avatar
untereiner committed
345 346
	do
	{
Sylvain Thery's avatar
Sylvain Thery committed
347
		darts.push_back(dit);
348
		dit = alpha2(dit);
Sylvain Thery's avatar
Sylvain Thery committed
349
	}while(dit != d);
untereiner's avatar
untereiner committed
350

Sylvain Thery's avatar
Sylvain Thery committed
351 352 353
	for (std::vector<Dart>::iterator it = darts.begin(); it != darts.end(); ++it)
	{
		Dart x = phi2(phi_1(*it));
354 355 356 357 358 359 360 361

		Dart resCV = NIL;

		if(!isBoundaryFace(phi2(phi1(*it))))
			resCV = phi3(phi2(phi1(*it)));
		else if(!isBoundaryFace(phi2(phi_1(*it))))
			resCV = phi3(phi2(phi_1(*it)));

Sylvain Thery's avatar
Sylvain Thery committed
362 363
		resV = Map2::collapseEdge(*it, true);
		if (delDegenerateVolumes)
364 365
			if(collapseDegeneretedVolume(x) && resCV != NIL)
				resV = resCV;
Sylvain Thery's avatar
Sylvain Thery committed
366
	}
367

368 369
	return resV;
}
370 371 372



Sylvain Thery's avatar
Sylvain Thery committed
373

374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 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 421 422
//	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
423

Sylvain Thery's avatar
Sylvain Thery committed
424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453
//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)
454
{
Sylvain Thery's avatar
Sylvain Thery committed
455
	return (d != e && sameOrientedFace(d, e)) ;
456
}
untereiner's avatar
untereiner committed
457

458
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
459
{
Sylvain Thery's avatar
Sylvain Thery committed
460 461
//	assert(d != e && sameOrientedFace(d, e)) ;
	assert(splitFacePreCond(d,e));
Pierre Kraemer's avatar
Pierre Kraemer committed
462

463 464
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
465

untereiner's avatar
untereiner committed
466
	Map2::splitFace(d, e);
467
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
468

469 470
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
471 472
}

473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493
Dart Map3::collapseFace(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
	Dart stop = phi_1(d);
	Dart dit = d;
	std::vector<Dart> vd;
	vd.reserve(32);

	do
	{
		vd.push_back(alpha2(dit));
		dit = phi1(dit);
	}
	while(dit != stop);

	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
		resV = Map3::collapseEdge(*it, delDegenerateVolumes);

	return resV;
}

Sylvain Thery's avatar
Sylvain Thery committed
494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515
//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;
//}

516 517
bool Map3::collapseDegeneretedVolume(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
518 519
	Dart e1 = d;
	Dart e2 = phi2(d);
520

Sylvain Thery's avatar
Sylvain Thery committed
521
	do
522
	{
Sylvain Thery's avatar
Sylvain Thery committed
523 524 525 526 527 528 529 530 531 532 533
		if (e1 != phi2(e2))
			return false;
		e1 = phi1(e1);
		e2 = phi_1(e2);
	}while (e1 != d);

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

	// degenerated:
	do
534
	{
Sylvain Thery's avatar
Sylvain Thery committed
535 536 537 538 539 540 541 542
		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);
543

Sylvain Thery's avatar
Sylvain Thery committed
544 545 546 547 548 549 550 551
	Map2::deleteCC(d) ;
	return true;
}


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

554
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
555
{
Sylvain Thery's avatar
Sylvain Thery committed
556
	assert(sewVolumesPreCond(d,e));
557

558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588
	// 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) ;
		}
589 590
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
591 592
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
593
	} while(fitD != dd) ;
594 595
	Map2::deleteCC(dd) ;

596 597
	fitD = d ;
	fitE = e ;
598 599
	do
	{
600
		phi3sew(fitD, fitE) ;
601 602 603 604 605
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

Sylvain Thery's avatar
Sylvain Thery committed
606 607 608 609 610 611
bool Map3::unsewVolumesPreCond(Dart d)
{
	return (!isBoundaryFace(d)) ;
}


612 613
void Map3::unsewVolumes(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
614
	assert(unsewVolumesPreCond(d)) ;
untereiner's avatar
untereiner committed
615 616 617 618 619 620 621 622 623 624 625

	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 ;
626 627
	do
	{
untereiner's avatar
untereiner committed
628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647
		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) ;
648 649 650 651
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
652
	if(!Map3::isBoundaryFace(d))
653
	{
untereiner's avatar
untereiner committed
654
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
655 656 657 658 659
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
660 661
void Map3::splitVolume(std::vector<Dart>& vd)
{
662
	//assert(checkSimpleOrientedPath(vd)) ;
untereiner's avatar
untereiner committed
663

untereiner's avatar
untereiner committed
664 665 666
	Dart e = vd.front();
	Dart e2 = phi2(e);

667
	Map2::splitSurface(vd,true,true);
untereiner's avatar
untereiner committed
668

untereiner's avatar
untereiner committed
669
	//sew the two connected components
untereiner's avatar
untereiner committed
670
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
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
Dart Map3::collapseVolume(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
	std::vector<Dart> vd;
	vd.reserve(32);

	vd.push_back(d);
	vd.push_back(alpha2(phi1(d)));
	vd.push_back(alpha2(phi_1(phi2(phi1(d)))));

//	Traversor3WF<Map3> tra(*this, phi1(d));
//	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
//	{
//		vd.push_back(alpha2(dit));
//	}
//	vd.pop_back();

	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
		resV = Map3::collapseEdge(*it, delDegenerateVolumes);

	return resV;
}

696 697 698 699
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

700
bool Map3::sameVertex(Dart d, Dart e)
701 702 703
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
704 705 706
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
707 708
	mv.mark(d);

709
	for(unsigned int i = 0; i < darts.size(); ++i)
710
	{
711
		if(darts[i] == e)
712 713
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
714
		// add phi21 and phi23 successor if they are not marked yet
715
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
716 717
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
718

untereiner's avatar
untereiner committed
719 720 721 722 723 724 725 726 727
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
728 729 730 731 732
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
733 734
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
735
	unsigned int count = 0;
untereiner's avatar
untereiner committed
736 737
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
738 739 740
	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
741 742
	mv.mark(d);

743
	for(unsigned int i = 0; i < darts.size(); ++i)
untereiner's avatar
untereiner committed
744 745
	{
		//add phi21 and phi23 successor if they are not marked yet
746
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
747 748 749 750 751
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
752
			darts.push_back(d21);
untereiner's avatar
untereiner committed
753 754
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
755
		if(!mv.isMarked(d23))
untereiner's avatar
untereiner committed
756
		{
untereiner's avatar
untereiner committed
757
			darts.push_back(d23);
untereiner's avatar
untereiner committed
758 759 760 761 762
			mv.mark(d23);
		}
	}

	DartMarkerStore me(*this);
untereiner's avatar
untereiner committed
763
	for(std::vector<Dart>::iterator it = darts.begin(); it != darts.end() ; ++it)
untereiner's avatar
untereiner committed
764
	{
untereiner's avatar
untereiner committed
765
		if(!me.isMarked(*it))
untereiner's avatar
untereiner committed
766 767
		{
			++count;
untereiner's avatar
untereiner committed
768
			me.markOrbit(EDGE, *it);
untereiner's avatar
untereiner committed
769 770 771 772 773 774
		}
	}

	return count;
}

775 776 777 778 779 780 781
unsigned int Map3::vertexDegreeOnBoundary(Dart d)
{
	assert(Map3::isBoundaryVertex(d));

	return Map2::vertexDegree(d);
}

782 783
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
784
	DartMarkerStore mv(*this);	// Lock a marker
785

untereiner's avatar
untereiner committed
786 787 788
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
789 790
	mv.mark(d);

791
	for(unsigned int i = 0; i < darts.size(); ++i)
792
	{
793
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
794
			return true ;
795 796

		//add phi21 and phi23 successor if they are not marked yet
797
		Dart d2 = phi2(darts[i]);
798 799 800 801 802
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
803
			darts.push_back(d21);
804 805
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
806
		if(!mv.isMarked(d23))
807
		{
untereiner's avatar
untereiner committed
808
			darts.push_back(d23);
809 810 811
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
812
	return false ;
813 814
}

untereiner's avatar
untereiner committed
815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847
Dart Map3::findBoundaryFaceOfVertex(Dart d)
{
	DartMarkerStore mv(*this);	// Lock a marker

	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
	mv.mark(d);

	for(unsigned int i = 0; i < darts.size(); ++i)
	{
		if(isBoundaryMarked(darts[i]))
			return darts[i];

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

		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
		}
	}
	return NIL ;
}

848 849
bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
850
	Dart it = d;
851 852
	do
	{
untereiner's avatar
untereiner committed
853
		if(it == e)
854
			return true;
untereiner's avatar
untereiner committed
855 856
		it = alpha2(it);
	} while (it != d);
857 858 859
	return false;
}

untereiner's avatar
untereiner committed
860
unsigned int Map3::edgeDegree(Dart d)
861
{
untereiner's avatar
untereiner committed
862
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
863
	Dart it = d;
864 865
	do
	{
untereiner's avatar
untereiner committed
866 867 868
		++deg;
		it = alpha2(it);
	} while(it != d);
869 870 871
	return deg;
}

untereiner's avatar
untereiner committed
872
bool Map3::isBoundaryEdge(Dart d)
873
{
untereiner's avatar
untereiner committed
874 875 876 877 878 879 880 881
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
882 883
}

untereiner's avatar
untereiner committed
884
Dart Map3::findBoundaryFaceOfEdge(Dart d)
885
{
untereiner's avatar
untereiner committed
886 887 888 889 890 891 892 893
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
894 895
}

Pierre Kraemer's avatar
Pierre Kraemer committed
896 897
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
898 899
	Traversor3WF<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
900
	{
untereiner's avatar
untereiner committed
901
		if(isBoundaryMarked(phi3(dit)))
untereiner's avatar
untereiner committed
902
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
903
	}
untereiner's avatar
untereiner committed
904
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
905 906
}

untereiner's avatar
untereiner committed
907 908
bool Map3::hasBoundaryEdge(Dart d)
{
untereiner's avatar
untereiner committed
909 910
	Traversor3WE<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
untereiner's avatar
untereiner committed
911
	{
untereiner's avatar
untereiner committed
912 913
		if(isBoundaryEdge(dit))
			return true;
untereiner's avatar
untereiner committed
914
	}
untereiner's avatar
untereiner committed
915

untereiner's avatar
untereiner committed
916 917 918
	return false;
}

919
bool Map3::check()
920
{
921 922 923 924 925 926 927 928 929 930
    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;
        }
931

untereiner's avatar
untereiner committed
932 933 934
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
935
			//return false;
untereiner's avatar
untereiner committed
936
		}
937

938 939 940 941 942 943
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
944

945 946 947 948 949 950
        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;
        }
951

952
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
953
		{
954 955 956 957
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
958

959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974
        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 ?
975
		{
976 977 978 979
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
980

981
    std::cout << "Check: topology ok" << std::endl;
982

983
    return true;
984 985
}

Pierre Kraemer's avatar
Pierre Kraemer committed
986 987 988 989
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
990
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
991
{
untereiner's avatar
untereiner committed
992
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
993 994
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
995 996 997
	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
998 999
	mv.mark(d);

1000
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
1001
	{
1002
		// add phi21 and phi23 successor if they are not marked yet
1003
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
1004 1005
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
1006

untereiner's avatar
untereiner committed
1007 1008 1009 1010 1011 1012 1013 1014 1015
		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
1016 1017
		}

1018
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
1019 1020 1021 1022
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
1023
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
1024
{
untereiner's avatar
untereiner committed
1025
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
1026 1027
	do
	{
untereiner's avatar
untereiner committed
1028
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
1029
			return true;
untereiner's avatar
untereiner committed
1030 1031
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
1032 1033 1034
	return false;
}

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

untereiner's avatar
untereiner committed
1040 1041 1042
	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
1043 1044
	mv.mark(d);

1045
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
1046
	{
untereiner's avatar
untereiner committed
1047
		// add all successors if they are not marked yet
1048 1049 1050
		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
1051

untereiner's avatar
untereiner committed
1052 1053 1054 1055 1056
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
1057 1058
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
1059 1060
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
1061 1062 1063
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
1064
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
1065 1066 1067
			mv.mark(d4);
		}

1068
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
1069 1070 1071 1072
	}
	return found;
}

untereiner's avatar
untereiner committed
1073 1074 1075
/*! @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
1076

untereiner's avatar
untereiner committed
1077
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
1078
{
untereiner's avatar
untereiner committed
1079
	assert(phi3(d) == d);		// Nothing to close
1080
	DartMarkerStore m(*this) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1081

untereiner's avatar
untereiner committed
1082 1083 1084
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
1085 1086
//	m.markOrbit(ORIENTED_FACE, d) ;
	m.markOrbit(FACE2, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1087

untereiner's avatar
untereiner committed
1088
	unsigned int count = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1089

untereiner's avatar
untereiner committed
1090
	// For every face added to the list
1091
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
1092
	{
1093 1094 1095
		Dart it = visitedFaces[i] ;
		Dart f = it ;

untereiner's avatar
untereiner committed
1096 1097 1098
		unsigned int degree = faceDegree(f) ;
		Dart b = newBoundaryCycle(degree) ;
		++count ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1099

untereiner's avatar
untereiner committed
1100 1101
		Dart bit = b ;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
1102
		{
untereiner's avatar
untereiner committed
1103 1104 1105 1106 1107 1108 1109
			Dart e = alpha2(f) ;
			bool found = false ;
			do
			{
				if(phi3(e) == e)
				{
					found = true ;
1110 1111 1112
					if(!m.isMarked(e))
					{
						visitedFaces.push_back(e) ;
1113
						m.markOrbit(FACE2, e) ;
1114
					}
untereiner's avatar
untereiner committed
1115
				}
1116
				else if(isBoundaryMarked(e))
untereiner's avatar
untereiner committed
1117 1118
				{
					found = true ;
1119
					phi2sew(e, bit) ;
untereiner's avatar
untereiner committed
1120 1121 1122 1123 1124 1125 1126 1127
				}
				else
					e = alpha2(e) ;
			} while(!found) ;

			phi3sew(f, bit) ;
			bit = phi_1(bit) ;
			f = phi1(f);
1128
		} while(f != it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1129 1130
	}

untereiner's avatar
untereiner committed
1131 1132 1133
	return count ;
}

1134
unsigned int Map3::closeMap()
untereiner's avatar
untereiner committed
1135 1136
{
	// Search the map for topological holes (fix points of phi3)
1137
	unsigned int nb = 0 ;