map3.cpp 25 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

Pierre Kraemer's avatar
Pierre Kraemer committed
90
	mark.markOrbit<FACE2>(d) ;
91

Pierre Kraemer's avatar
Pierre Kraemer committed
92

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

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

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

untereiner's avatar
untereiner committed
112
	Dart dd = phi3(d) ;
113 114
	Map2::deleteCC(d) ; //deleting the volume
	Map2::deleteCC(dd) ; //deleting its border (created from the unsew operation)
Pierre Kraemer's avatar
Pierre Kraemer committed
115 116
}

117 118
void Map3::fillHole(Dart d)
{
119 120 121 122
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi3(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
123
	boundaryUnmarkOrbit<VOLUME>(dd) ;
124 125
}

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

untereiner's avatar
untereiner committed
130
Dart Map3::splitVertex(std::vector<Dart>& vd)
untereiner's avatar
untereiner committed
131
{
132
	//assert(checkPathAroundVertex(vd)) ;
untereiner's avatar
untereiner committed
133

untereiner's avatar
untereiner committed
134
	//bool boundE = false;
untereiner's avatar
untereiner committed
135 136

	Dart prev = vd.front();	//elt 0
137 138

	Dart db1 = NIL;
139
	if(isBoundaryFace(phi2(prev)))
140 141 142 143
	{
		db1 = phi2(phi3(phi1(phi2(prev))));
	}

untereiner's avatar
untereiner committed
144 145 146 147 148 149 150 151 152 153 154 155
	Dart fs = phi_1(phi2(phi_1(prev)));	//first side

	Map2::splitVertex(prev, phi2(fs));

	for(unsigned int i = 1; i < vd.size(); ++i)
	{
		prev = vd[i];

		Dart fs = phi_1(phi2(phi_1(prev)));	//first side

		Map2::splitVertex(prev, phi2(fs));

156 157
		Dart d1 = phi_1(phi2(phi_1(vd[i-1])));
		Dart d2 = phi1(phi2(vd[i]));
untereiner's avatar
untereiner committed
158

159
		phi3sew(d1, d2);
untereiner's avatar
untereiner committed
160 161
	}

162 163
	Dart db2 = NIL;
	if(isBoundaryFace(phi2(phi_1(prev))))
Lionel Untereiner's avatar
Lionel Untereiner committed
164
	{
165
		db2 = phi2(phi3(phi2(phi_1(prev))));
Lionel Untereiner's avatar
Lionel Untereiner committed
166 167
	}

168 169 170 171 172 173
	if(db1 != NIL && db2 != NIL)
	{
		Map2::splitVertex(db1, db2);
		phi3sew(phi1(phi2(db2)), phi_1(phi3(phi2(db2))));
		phi3sew(phi1(phi2(db1)), phi_1(phi3(phi2(db1))));
	}
174
	else
175 176 177 178 179
	{
		Dart dbegin = phi1(phi2(vd.front()));
		Dart dend = phi_1(phi2(phi_1(vd.back())));
		phi3sew(dbegin, dend);
	}
Lionel Untereiner's avatar
Lionel Untereiner committed
180

untereiner's avatar
untereiner committed
181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213
	return phi_1(phi2(phi_1(prev)));
}

//	//unsew the face path
//	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
//	{
//		Dart dit = *it;
//
//		Map1::cutEdge(phi_1(phi2(phi_1(dit)))); //comme un vertexSplit
//		Map1::cutEdge(phi2(phi1(phi2(dit))));
//		Map2::sewFaces(phi1(phi2(phi1(phi2(dit)))), phi_1(phi2(phi_1(dit))), false);
//
//
//
//		Dart dit3 = phi3(dit);
//		unsewVolumes(dit);

//		Dart f1 = newFace(3,false);
//		Dart f2 = newFace(3,false);
//		Dart f3 = newFace(3,false);
//		Dart f4 = newFace(3,false);
//
//		sewFaces(f1,f2,false);
//		sewFaces(phi_1(f1), f3, false);
//		sewFaces(phi1(f1), f4, false);
//		sewFaces(phi_1(f2), phi1(f4), false);
//		sewFaces(phi_1(f3), phi1(f2), false);
//		sewFaces(phi1(f3), phi_1(f4), false);
//
//		sewVolumes(dit,f3);
//		sewVolumes(dit3,f4);
//	}

Lionel Untereiner's avatar
Lionel Untereiner committed
214
/*
untereiner's avatar
untereiner committed
215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231
	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));
	}
Lionel Untereiner's avatar
Lionel Untereiner committed
232
*/
untereiner's avatar
untereiner committed
233

untereiner's avatar
untereiner committed
234

235
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
236
{
237 238 239
	if(isBoundaryVertex(d))
		return NIL ;

Pierre Kraemer's avatar
Pierre Kraemer committed
240 241
	// Save the darts around the vertex
	// (one dart per face should be enough)
untereiner's avatar
untereiner committed
242
	std::vector<Dart> fstoretmp;
243
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
244 245 246
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

247
	 // just one dart per face
untereiner's avatar
untereiner committed
248
	std::vector<Dart> fstore;
249
	fstore.reserve(128);
untereiner's avatar
untereiner committed
250
	DartMarker mf(*this);
251
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
252
	{
253
		if(!mf.isMarked(fstoretmp[i]))
254
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
255
			mf.markOrbit<FACE>(fstoretmp[i]);
256
			fstore.push_back(fstoretmp[i]);
untereiner's avatar
untereiner committed
257
		}
258
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
259

260
	Dart res = NIL ;
untereiner's avatar
untereiner committed
261 262
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
263 264 265 266 267 268 269 270
		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) ;
271

272 273
			if(res == NIL)
				res = d2 ;
274

275 276 277 278
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
279 280

			fit = phi1(fit) ;
281
		}
untereiner's avatar
untereiner committed
282
	}
283

284
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
285

286
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
287 288
}

David Cazier's avatar
David Cazier committed
289
Dart Map3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
290 291 292
{
	Dart prev = d;
	Dart dd = alpha2(d);
David Cazier's avatar
David Cazier committed
293
	Dart nd = Map2::cutEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
294

295
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
296 297 298 299 300 301
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

302 303 304 305
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
306 307
	}

308 309 310 311
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
312

David Cazier's avatar
David Cazier committed
313
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
314 315
}

Pierre Kraemer's avatar
Pierre Kraemer committed
316
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
317
{
Pierre Kraemer's avatar
Pierre Kraemer committed
318 319
	if(vertexDegree(phi1(d)) == 2)
	{
320 321
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
322

323 324
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
325 326 327
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
328

329 330
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
331 332
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
333 334
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
335
		return true;
untereiner's avatar
untereiner committed
336
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
337
	return false;
untereiner's avatar
untereiner committed
338 339
}

Sylvain Thery's avatar
Sylvain Thery committed
340 341 342 343 344 345 346
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
347 348
Dart Map3::deleteEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
349 350
	assert(deleteEdgePreCond(d));

untereiner's avatar
untereiner committed
351 352 353 354
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
355 356
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
357
	{
358 359
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
360 361 362 363 364 365
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
366

untereiner's avatar
untereiner committed
367 368
			if(res == NIL)
				res = d2 ;
369

untereiner's avatar
untereiner committed
370 371 372 373
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
374 375

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
376
		}
377 378 379
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
380 381 382 383 384
	Map2::deleteCC(d) ;

	return res ;
}

Sylvain Thery's avatar
Sylvain Thery committed
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
//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
418 419 420
Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
421
	Dart dit = d;
untereiner's avatar
untereiner committed
422

Sylvain Thery's avatar
Sylvain Thery committed
423
	std::vector<Dart> darts;
untereiner's avatar
untereiner committed
424 425
	do
	{
Sylvain Thery's avatar
Sylvain Thery committed
426
		darts.push_back(dit);
427
		dit = alpha2(dit);
Sylvain Thery's avatar
Sylvain Thery committed
428
	}while(dit != d);
untereiner's avatar
untereiner committed
429

Sylvain Thery's avatar
Sylvain Thery committed
430 431 432
	for (std::vector<Dart>::iterator it = darts.begin(); it != darts.end(); ++it)
	{
		Dart x = phi2(phi_1(*it));
433 434 435 436 437 438 439 440

		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
441 442
		resV = Map2::collapseEdge(*it, true);
		if (delDegenerateVolumes)
443 444
			if(collapseDegeneretedVolume(x) && resCV != NIL)
				resV = resCV;
Sylvain Thery's avatar
Sylvain Thery committed
445
	}
446

447 448
	return resV;
}
449 450 451



Sylvain Thery's avatar
Sylvain Thery committed
452

453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501
//	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
502

Sylvain Thery's avatar
Sylvain Thery committed
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
//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)
533
{
Sylvain Thery's avatar
Sylvain Thery committed
534
	return (d != e && sameOrientedFace(d, e)) ;
535
}
untereiner's avatar
untereiner committed
536

537
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
538
{
Sylvain Thery's avatar
Sylvain Thery committed
539 540
//	assert(d != e && sameOrientedFace(d, e)) ;
	assert(splitFacePreCond(d,e));
Pierre Kraemer's avatar
Pierre Kraemer committed
541

542 543
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
544

untereiner's avatar
untereiner committed
545
	Map2::splitFace(d, e);
546
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
547

548 549
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
550 551
}

Thomas's avatar
Thomas committed
552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578
bool Map3::mergeFaces(Dart d)
{
	assert(edgeDegree(d)==2);

	Dart dd = phi3(d);

	phi3unsew(d);
	phi3unsew(dd);

	//use code of mergesFaces to override the if(isBoundaryEdge)
	//we have to merge the faces if the face is linked to a border also
//	Map2::mergeFaces(d);
	Dart e = phi2(d) ;
	phi2unsew(d) ;
	Map1::mergeCycles(d, phi1(e)) ;
	Map1::splitCycle(e, phi1(d)) ;
	Map1::deleteCycle(d) ;
//	Map2::mergeFaces(dd);
	e = phi2(dd) ;
	phi2unsew(dd) ;
	Map1::mergeCycles(dd, phi1(e)) ;
	Map1::splitCycle(e, phi1(dd)) ;
	Map1::deleteCycle(dd);

	return true;
}

579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599
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
600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621
//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;
//}

622 623
bool Map3::collapseDegeneretedVolume(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
624 625
	Dart e1 = d;
	Dart e2 = phi2(d);
626

Sylvain Thery's avatar
Sylvain Thery committed
627
	do
628
	{
Sylvain Thery's avatar
Sylvain Thery committed
629 630 631 632 633 634 635 636 637 638 639
		if (e1 != phi2(e2))
			return false;
		e1 = phi1(e1);
		e2 = phi_1(e2);
	}while (e1 != d);

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

	// degenerated:
	do
640
	{
Sylvain Thery's avatar
Sylvain Thery committed
641 642 643 644 645 646 647 648
		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);
649

Sylvain Thery's avatar
Sylvain Thery committed
650 651 652 653 654 655 656 657
	Map2::deleteCC(d) ;
	return true;
}


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

660
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
661
{
Sylvain Thery's avatar
Sylvain Thery committed
662
	assert(sewVolumesPreCond(d,e));
663

664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694
	// 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) ;
		}
695 696
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
697 698
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
699
	} while(fitD != dd) ;
700 701
	Map2::deleteCC(dd) ;

702 703
	fitD = d ;
	fitE = e ;
704 705
	do
	{
706
		phi3sew(fitD, fitE) ;
707 708 709 710 711
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

Sylvain Thery's avatar
Sylvain Thery committed
712 713 714 715 716 717
bool Map3::unsewVolumesPreCond(Dart d)
{
	return (!isBoundaryFace(d)) ;
}


718 719
void Map3::unsewVolumes(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
720
	assert(unsewVolumesPreCond(d)) ;
untereiner's avatar
untereiner committed
721 722 723 724 725 726 727 728 729 730 731

	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 ;
732 733
	do
	{
untereiner's avatar
untereiner committed
734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753
		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) ;
754 755 756 757
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
758
	if(!Map3::isBoundaryFace(d))
759
	{
untereiner's avatar
untereiner committed
760
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
761 762 763 764 765
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
766 767
void Map3::splitVolume(std::vector<Dart>& vd)
{
768
	//assert(checkSimpleOrientedPath(vd)) ;
untereiner's avatar
untereiner committed
769

untereiner's avatar
untereiner committed
770 771 772
	Dart e = vd.front();
	Dart e2 = phi2(e);

773
	Map2::splitSurface(vd,true,true);
untereiner's avatar
untereiner committed
774

untereiner's avatar
untereiner committed
775
	//sew the two connected components
untereiner's avatar
untereiner committed
776
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
777 778
}

779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801
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;
}

802 803 804 805
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

806
bool Map3::sameVertex(Dart d, Dart e)
807 808 809
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
810 811 812
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
813 814
	mv.mark(d);

815
	for(unsigned int i = 0; i < darts.size(); ++i)
816
	{
817
		if(darts[i] == e)
818 819
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
820
		// add phi21 and phi23 successor if they are not marked yet
821
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
822 823
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
824

untereiner's avatar
untereiner committed
825 826 827 828 829 830 831 832 833
		if(!mv.isMarked(d21))
		{
			darts.push_back(d21);
			mv.mark(d21);
		}
		if(!mv.isMarked(d23))
		{
			darts.push_back(d23);
			mv.mark(d23);
834 835 836 837 838
		}
	}
	return false;
}

untereiner's avatar
untereiner committed
839 840
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
841
	unsigned int count = 0;
untereiner's avatar
untereiner committed
842

843 844
	Traversor3VE<Map3> trav3VE(*this, d);
	for(Dart dit = trav3VE.begin() ; dit != trav3VE.end() ; dit = trav3VE.next())
untereiner's avatar
untereiner committed
845
	{
846
		++count;
untereiner's avatar
untereiner committed
847 848 849 850 851
	}

	return count;
}

852 853 854 855 856 857 858
unsigned int Map3::vertexDegreeOnBoundary(Dart d)
{
	assert(Map3::isBoundaryVertex(d));

	return Map2::vertexDegree(d);
}

859 860
bool Map3::isBoundaryVertex(Dart d)
{
untereiner's avatar
untereiner committed
861
	DartMarkerStore mv(*this);	// Lock a marker
862

untereiner's avatar
untereiner committed
863 864 865
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
866 867
	mv.mark(d);

868
	for(unsigned int i = 0; i < darts.size(); ++i)
869
	{
870
		if(isBoundaryMarked(darts[i]))
untereiner's avatar
untereiner committed
871
			return true ;
872 873

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

		if(!mv.isMarked(d21))
		{
untereiner's avatar
untereiner committed
880
			darts.push_back(d21);
881 882
			mv.mark(d21);
		}
untereiner's avatar
untereiner committed
883
		if(!mv.isMarked(d23))
884
		{
untereiner's avatar
untereiner committed
885
			darts.push_back(d23);
886 887 888
			mv.mark(d23);
		}
	}
untereiner's avatar
untereiner committed
889
	return false ;
890 891
}

untereiner's avatar
untereiner committed
892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924
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 ;
}

925 926
bool Map3::sameOrientedEdge(Dart d, Dart e)
{
untereiner's avatar
untereiner committed
927
	Dart it = d;
928 929
	do
	{
untereiner's avatar
untereiner committed
930
		if(it == e)
931
			return true;
untereiner's avatar
untereiner committed
932 933
		it = alpha2(it);
	} while (it != d);
934 935 936
	return false;
}

untereiner's avatar
untereiner committed
937
unsigned int Map3::edgeDegree(Dart d)
938
{
untereiner's avatar
untereiner committed
939
	unsigned int deg = 0;
untereiner's avatar
untereiner committed
940
	Dart it = d;
941 942
	do
	{
untereiner's avatar
untereiner committed
943 944 945
		++deg;
		it = alpha2(it);
	} while(it != d);
946 947 948
	return deg;
}

untereiner's avatar
untereiner committed
949
bool Map3::isBoundaryEdge(Dart d)
950
{
untereiner's avatar
untereiner committed
951 952 953 954 955 956 957 958
	Dart it = d;
	do
	{
		if(isBoundaryMarked(it))
			return true ;
		it = alpha2(it);
	} while(it != d);
	return false;
959 960
}

untereiner's avatar
untereiner committed
961
Dart Map3::findBoundaryFaceOfEdge(Dart d)
962
{
untereiner's avatar
untereiner committed
963 964 965 966 967 968 969 970
	Dart it = d;
	do
	{
		if (isBoundaryMarked(it))
			return it ;
		it = alpha2(it);
	} while(it != d);
	return NIL ;
971 972
}

Pierre Kraemer's avatar
Pierre Kraemer committed
973 974
bool Map3::isBoundaryVolume(Dart d)
{
untereiner's avatar
untereiner committed
975 976
	Traversor3WF<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
Pierre Kraemer's avatar
Pierre Kraemer committed
977
	{
untereiner's avatar
untereiner committed
978
		if(isBoundaryMarked(phi3(dit)))
untereiner's avatar
untereiner committed
979
			return true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
980
	}
untereiner's avatar
untereiner committed
981
	return false;
Pierre Kraemer's avatar
Pierre Kraemer committed
982 983
}

untereiner's avatar
untereiner committed
984 985
bool Map3::hasBoundaryEdge(Dart d)
{
untereiner's avatar
untereiner committed
986 987
	Traversor3WE<Map3> tra(*this, d);
	for(Dart dit = tra.begin() ; dit != tra.end() ; dit = tra.next())
untereiner's avatar
untereiner committed
988
	{
untereiner's avatar
untereiner committed
989 990
		if(isBoundaryEdge(dit))
			return true;
untereiner's avatar
untereiner committed
991
	}
untereiner's avatar
untereiner committed
992

untereiner's avatar
untereiner committed
993 994 995
	return false;
}

996
bool Map3::check()
997
{
998 999 1000 1001 1002 1003 1004 1005 1006 1007
    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;
        }
1008

untereiner's avatar
untereiner committed
1009 1010 1011
		if(phi1(d3) != phi3(phi_1(d)))
		{
			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
1012
			//return false;
untereiner's avatar
untereiner committed
1013
		}
1014

1015 1016 1017 1018 1019 1020
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
            std::cout << "Check: phi2 is not an involution" << std::endl;
            return false;
        }
1021

1022 1023 1024 1025 1026 1027
        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;
        }
1028

1029
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
1030
		{
1031 1032 1033 1034
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
1035

1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051
        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 ?
1052
		{
1053 1054 1055 1056
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
1057

1058
    std::cout << "Check: topology ok" << std::endl;
1059

1060
    return true;
1061 1062
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1063 1064 1065 1066
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
1067
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
1068
{
untereiner's avatar
untereiner committed
1069
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
1070 1071
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
1072 1073 1074
	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
1075 1076
	mv.mark(d);

1077
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
1078
	{
1079
		// add phi21 and phi23 successor if they are not marked yet
1080
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
1081 1082
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
1083

untereiner's avatar
untereiner committed
1084 1085 1086 1087 1088 1089 1090 1091 1092
		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
1093 1094
		}

1095
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
1096 1097 1098 1099
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
1100
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
1101
{
untereiner's avatar
untereiner committed
1102
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
1103 1104
	do
	{
untereiner's avatar
untereiner committed
1105
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
1106
			return true;
untereiner's avatar
untereiner committed
1107 1108
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
1109 1110 1111
	return false;
}

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

untereiner's avatar
untereiner committed
1117 1118 1119
	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
1120 1121
	mv.mark(d);

1122
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
1123
	{
untereiner's avatar
untereiner committed
1124
		// add all successors if they are not marked yet
1125 1126 1127
		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
1128

untereiner's avatar
untereiner committed
1129 1130 1131 1132 1133
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
1134 1135
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
1136 1137
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
1138 1139 1140
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
1141
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
1142 1143 1144
			mv.mark(d4);
		}

1145
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
1146 1147 1148 1149
	}
	return found;
}

untereiner's avatar
untereiner committed
1150 1151 1152
/*! @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
1153

untereiner's avatar
untereiner committed
1154
unsigned int Map3::closeHole(Dart d, bool forboundary)
Pierre Kraemer's avatar
Pierre Kraemer committed
1155
{
untereiner's avatar
untereiner committed
1156
	assert(phi3(d) == d);		// Nothing to close
1157
	DartMarkerStore m(*this) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
1158

untereiner's avatar
untereiner committed
1159 1160 1161
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(1024) ;
	visitedFaces.push_back(d);		// Start with the face of d
Pierre Kraemer's avatar
Pierre Kraemer committed
1162
	m.markOrbit<FACE2>(d) ;