map3.cpp 24.1 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 87 88 89 90 91
	DartMarkerStore mark(*this);		// Lock a marker

	std::vector<Dart> visitedFaces;		// Faces that are traversed
	visitedFaces.reserve(512);
	visitedFaces.push_back(d);			// Start with the face of d

	mark.markOrbit<FACE2>(d) ;

92

93
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
94
	{
95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
		Dart e = visitedFaces[i] ;

		if(!isBoundaryFace(e))
			unsewVolumes(e) ;

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

112 113 114 115 116 117 118
//	Traversor3WF<Map3> tWF(*this,d);
//	for(Dart dit = tWF.begin() ; dit != tWF.end() ; dit = tWF.next())
//	{
//		if(!isBoundaryFace(dit))
//			unsewVolumes(dit) ;
//	}

untereiner's avatar
untereiner committed
119
	Dart dd = phi3(d) ;
120
	Map2::deleteCC(d) ; //deleting the volume
121
	Map2::deleteCC(dd) ; //deleting its border (created from the unsew operation)
Pierre Kraemer's avatar
Pierre Kraemer committed
122 123
}

124 125
void Map3::fillHole(Dart d)
{
126 127 128 129
	assert(isBoundaryFace(d)) ;
	Dart dd = d ;
	if(!isBoundaryMarked(dd))
		dd = phi3(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
130
	boundaryUnmarkOrbit<VOLUME>(dd) ;
131 132
}

Pierre Kraemer's avatar
Pierre Kraemer committed
133 134 135 136
/*! @name Topological Operators
 *  Topological operations on 3-maps
 *************************************************************************/

untereiner's avatar
untereiner committed
137
Dart Map3::splitVertex(std::vector<Dart>& vd)
untereiner's avatar
untereiner committed
138
{
139
	//assert(checkPathAroundVertex(vd)) ;
untereiner's avatar
untereiner committed
140

untereiner's avatar
untereiner committed
141
	//bool boundE = false;
untereiner's avatar
untereiner committed
142 143

	Dart prev = vd.front();	//elt 0
144 145

	Dart db1 = NIL;
146
	if(isBoundaryFace(phi2(prev)))
147 148 149 150
	{
		db1 = phi2(phi3(phi1(phi2(prev))));
	}

untereiner's avatar
untereiner committed
151 152 153 154 155 156 157 158 159 160 161 162
	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));

163 164
		Dart d1 = phi_1(phi2(phi_1(vd[i-1])));
		Dart d2 = phi1(phi2(vd[i]));
untereiner's avatar
untereiner committed
165

166
		phi3sew(d1, d2);
untereiner's avatar
untereiner committed
167 168
	}

169 170
	Dart db2 = NIL;
	if(isBoundaryFace(phi2(phi_1(prev))))
Lionel Untereiner's avatar
Lionel Untereiner committed
171
	{
172
		db2 = phi2(phi3(phi2(phi_1(prev))));
Lionel Untereiner's avatar
Lionel Untereiner committed
173 174
	}

175 176 177 178 179 180
	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))));
	}
181
	else
182 183 184 185 186
	{
		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
187

untereiner's avatar
untereiner committed
188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
	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
221
/*
untereiner's avatar
untereiner committed
222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238
	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
239
*/
untereiner's avatar
untereiner committed
240

untereiner's avatar
untereiner committed
241

242
Dart Map3::deleteVertex(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
243
{
244 245 246
	if(isBoundaryVertex(d))
		return NIL ;

Pierre Kraemer's avatar
Pierre Kraemer committed
247 248
	// Save the darts around the vertex
	// (one dart per face should be enough)
untereiner's avatar
untereiner committed
249
	std::vector<Dart> fstoretmp;
250
	fstoretmp.reserve(128);
untereiner's avatar
untereiner committed
251 252 253
	FunctorStore fs(fstoretmp);
	foreach_dart_of_vertex(d, fs);

254
	 // just one dart per face
untereiner's avatar
untereiner committed
255
	std::vector<Dart> fstore;
256
	fstore.reserve(128);
untereiner's avatar
untereiner committed
257
	DartMarker mf(*this);
258
	for(unsigned int i = 0; i < fstoretmp.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
259
	{
260
		if(!mf.isMarked(fstoretmp[i]))
261
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
262
			mf.markOrbit<FACE>(fstoretmp[i]);
263
			fstore.push_back(fstoretmp[i]);
untereiner's avatar
untereiner committed
264
		}
265
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
266

267
	Dart res = NIL ;
untereiner's avatar
untereiner committed
268 269
	for(std::vector<Dart>::iterator it = fstore.begin() ; it != fstore.end() ; ++it)
	{
270 271 272 273 274 275 276 277
		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) ;
278

279 280
			if(res == NIL)
				res = d2 ;
281

282 283 284 285
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
286 287

			fit = phi1(fit) ;
288
		}
untereiner's avatar
untereiner committed
289
	}
290

291
	Map2::deleteCC(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
292

293
	return res ;
Pierre Kraemer's avatar
Pierre Kraemer committed
294 295
}

David Cazier's avatar
David Cazier committed
296
Dart Map3::cutEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
297 298 299
{
	Dart prev = d;
	Dart dd = alpha2(d);
David Cazier's avatar
David Cazier committed
300
	Dart nd = Map2::cutEdge(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
301

302
	while (dd != d)
Pierre Kraemer's avatar
Pierre Kraemer committed
303 304 305 306 307 308
	{
		prev = dd;
		dd = alpha2(dd);

		Map2::cutEdge(prev);

309 310 311 312
		Dart d3 = phi3(prev);
		phi3unsew(prev);
		phi3sew(prev, phi1(d3));
		phi3sew(d3, phi1(prev));
Pierre Kraemer's avatar
Pierre Kraemer committed
313 314
	}

315 316 317 318
	Dart d3 = phi3(d);
	phi3unsew(d);
	phi3sew(d, phi1(d3));
	phi3sew(d3, phi1(d));
Pierre Kraemer's avatar
Pierre Kraemer committed
319

David Cazier's avatar
David Cazier committed
320
	return nd;
Pierre Kraemer's avatar
Pierre Kraemer committed
321 322
}

Pierre Kraemer's avatar
Pierre Kraemer committed
323
bool Map3::uncutEdge(Dart d)
untereiner's avatar
untereiner committed
324
{
Pierre Kraemer's avatar
Pierre Kraemer committed
325 326
	if(vertexDegree(phi1(d)) == 2)
	{
327 328
		Dart prev = d ;
		phi3unsew(phi1(prev)) ;
untereiner's avatar
untereiner committed
329

330 331
		Dart dd = d;
		do
Pierre Kraemer's avatar
Pierre Kraemer committed
332 333 334
		{
			prev = dd;
			dd = alpha2(dd);
untereiner's avatar
untereiner committed
335

336 337
			phi3unsew(phi2(prev)) ;
			phi3unsew(phi2(phi1(prev))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
338 339
			Map2::uncutEdge(prev);
			phi3sew(dd, phi2(prev));
340 341
		} while (dd != d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
342
		return true;
untereiner's avatar
untereiner committed
343
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
344
	return false;
untereiner's avatar
untereiner committed
345 346
}

Sylvain Thery's avatar
Sylvain Thery committed
347 348 349 350 351 352 353
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
354 355
Dart Map3::deleteEdge(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
356 357
	assert(deleteEdgePreCond(d));

untereiner's avatar
untereiner committed
358 359 360 361
	if(isBoundaryEdge(d))
		return NIL ;

	Dart res = NIL ;
362 363
	Dart dit = d ;
	do
untereiner's avatar
untereiner committed
364
	{
365 366
		Dart fit = dit ;
		Dart end = fit ;
untereiner's avatar
untereiner committed
367 368 369 370 371 372
		fit = phi1(fit) ;
		while(fit != end)
		{
			Dart d2 = phi2(fit) ;
			Dart d3 = phi3(fit) ;
			Dart d32 = phi2(d3) ;
373

untereiner's avatar
untereiner committed
374 375
			if(res == NIL)
				res = d2 ;
376

untereiner's avatar
untereiner committed
377 378 379 380
			phi2unsew(d2) ;
			phi2unsew(d32) ;
			phi2sew(d2, d32) ;
			phi2sew(fit, d3) ;
381 382

			fit = phi1(fit) ;
untereiner's avatar
untereiner committed
383
		}
384 385 386
		dit = alpha2(dit) ;
	} while(dit != d) ;

untereiner's avatar
untereiner committed
387 388 389 390 391
	Map2::deleteCC(d) ;

	return res ;
}

Sylvain Thery's avatar
Sylvain Thery committed
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 423 424
//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
425 426 427
Dart Map3::collapseEdge(Dart d, bool delDegenerateVolumes)
{
	Dart resV = NIL;
428
	Dart dit = d;
untereiner's avatar
untereiner committed
429

Sylvain Thery's avatar
Sylvain Thery committed
430
	std::vector<Dart> darts;
untereiner's avatar
untereiner committed
431 432
	do
	{
Sylvain Thery's avatar
Sylvain Thery committed
433
		darts.push_back(dit);
434
		dit = alpha2(dit);
Sylvain Thery's avatar
Sylvain Thery committed
435
	}while(dit != d);
untereiner's avatar
untereiner committed
436

Sylvain Thery's avatar
Sylvain Thery committed
437 438 439
	for (std::vector<Dart>::iterator it = darts.begin(); it != darts.end(); ++it)
	{
		Dart x = phi2(phi_1(*it));
440 441 442 443 444 445 446 447

		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
448 449
		resV = Map2::collapseEdge(*it, true);
		if (delDegenerateVolumes)
450 451
			if(collapseDegeneretedVolume(x) && resCV != NIL)
				resV = resCV;
Sylvain Thery's avatar
Sylvain Thery committed
452
	}
453

454 455
	return resV;
}
456 457


Sylvain Thery's avatar
Sylvain Thery committed
458
bool Map3::splitFacePreCond(Dart d, Dart e)
459
{
Sylvain Thery's avatar
Sylvain Thery committed
460
	return (d != e && sameOrientedFace(d, e)) ;
461
}
untereiner's avatar
untereiner committed
462

463
void Map3::splitFace(Dart d, Dart e)
Pierre Kraemer's avatar
Pierre Kraemer committed
464
{
Sylvain Thery's avatar
Sylvain Thery committed
465 466
//	assert(d != e && sameOrientedFace(d, e)) ;
	assert(splitFacePreCond(d,e));
Pierre Kraemer's avatar
Pierre Kraemer committed
467

468 469
	Dart dd = phi1(phi3(d));
	Dart ee = phi1(phi3(e));
Pierre Kraemer's avatar
Pierre Kraemer committed
470

untereiner's avatar
untereiner committed
471
	Map2::splitFace(d, e);
472
	Map2::splitFace(dd, ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
473

474 475
	phi3sew(phi_1(d), phi_1(ee));
	phi3sew(phi_1(e), phi_1(dd));
Pierre Kraemer's avatar
Pierre Kraemer committed
476 477
}

Thomas's avatar
Thomas committed
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504
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;
}

505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525
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
526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547
//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;
//}

548 549
bool Map3::collapseDegeneretedVolume(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
550 551
	Dart e1 = d;
	Dart e2 = phi2(d);
552

Sylvain Thery's avatar
Sylvain Thery committed
553
	do
554
	{
Sylvain Thery's avatar
Sylvain Thery committed
555 556 557 558 559 560 561 562 563 564 565
		if (e1 != phi2(e2))
			return false;
		e1 = phi1(e1);
		e2 = phi_1(e2);
	}while (e1 != d);

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

	// degenerated:
	do
566
	{
Sylvain Thery's avatar
Sylvain Thery committed
567 568 569 570 571 572 573 574
		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);
575

Sylvain Thery's avatar
Sylvain Thery committed
576 577 578 579 580 581 582 583
	Map2::deleteCC(d) ;
	return true;
}


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

586
void Map3::sewVolumes(Dart d, Dart e, bool withBoundary)
587
{
Sylvain Thery's avatar
Sylvain Thery committed
588
	assert(sewVolumesPreCond(d,e));
589

590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620
	// 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) ;
		}
621 622
		phi3unsew(fitD) ;
		phi3unsew(fitE) ;
623 624
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
625
	} while(fitD != dd) ;
626 627
	Map2::deleteCC(dd) ;

628 629
	fitD = d ;
	fitE = e ;
630 631
	do
	{
632
		phi3sew(fitD, fitE) ;
633 634 635 636 637
		fitD = phi1(fitD) ;
		fitE = phi_1(fitE) ;
	} while(fitD != d) ;
}

Sylvain Thery's avatar
Sylvain Thery committed
638 639 640 641 642 643
bool Map3::unsewVolumesPreCond(Dart d)
{
	return (!isBoundaryFace(d)) ;
}


644 645
void Map3::unsewVolumes(Dart d)
{
Sylvain Thery's avatar
Sylvain Thery committed
646
	assert(unsewVolumesPreCond(d)) ;
untereiner's avatar
untereiner committed
647 648 649 650 651 652 653 654 655 656 657

	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 ;
658 659
	do
	{
untereiner's avatar
untereiner committed
660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679
		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) ;
680 681 682 683
}

bool Map3::mergeVolumes(Dart d)
{
untereiner's avatar
untereiner committed
684
	if(!Map3::isBoundaryFace(d))
685
	{
untereiner's avatar
untereiner committed
686
		Map2::mergeVolumes(d, phi3(d)); // merge the two volumes along common face
687 688 689 690 691
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
692 693
void Map3::splitVolume(std::vector<Dart>& vd)
{
694
	//assert(checkSimpleOrientedPath(vd)) ;
untereiner's avatar
untereiner committed
695

untereiner's avatar
untereiner committed
696 697 698
	Dart e = vd.front();
	Dart e2 = phi2(e);

699
	Map2::splitSurface(vd,true,true);
untereiner's avatar
untereiner committed
700

untereiner's avatar
untereiner committed
701
	//sew the two connected components
untereiner's avatar
untereiner committed
702
	Map3::sewVolumes(phi2(e), phi2(e2), false);
untereiner's avatar
untereiner committed
703 704
}

705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727
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;
}

728 729 730 731
/*! @name Topological Queries
 *  Return or set various topological information
 *************************************************************************/

732
bool Map3::sameVertex(Dart d, Dart e)
733 734 735
{
	DartMarkerStore mv(*this);	// Lock a marker

untereiner's avatar
untereiner committed
736 737 738
	std::vector<Dart> darts;	// Darts that are traversed
	darts.reserve(256);
	darts.push_back(d);			// Start with the dart d
739 740
	mv.mark(d);

741
	for(unsigned int i = 0; i < darts.size(); ++i)
742
	{
743
		if(darts[i] == e)
744 745
			return true;

Pierre Kraemer's avatar
Pierre Kraemer committed
746
		// add phi21 and phi23 successor if they are not marked yet
747
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
748 749
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
750

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

untereiner's avatar
untereiner committed
765 766
unsigned int Map3::vertexDegree(Dart d)
{
untereiner's avatar
untereiner committed
767
	unsigned int count = 0;
untereiner's avatar
untereiner committed
768

769 770
	Traversor3VE<Map3> trav3VE(*this, d);
	for(Dart dit = trav3VE.begin() ; dit != trav3VE.end() ; dit = trav3VE.next())
untereiner's avatar
untereiner committed
771
	{
772
		++count;
untereiner's avatar
untereiner committed
773 774 775 776 777
	}

	return count;
}

778 779 780 781 782 783 784
unsigned int Map3::vertexDegreeOnBoundary(Dart d)
{
	assert(Map3::isBoundaryVertex(d));

	return Map2::vertexDegree(d);
}

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

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

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

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

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

untereiner's avatar
untereiner committed
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 848 849 850
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 ;
}

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

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

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

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

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

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

untereiner's avatar
untereiner committed
920 921 922
	return false;
}

923
bool Map3::check()
924
{
925
    std::cout << "Check: topology begin" << std::endl;
926
    DartMarkerStore m(*this);
927 928 929 930 931 932 933 934
    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;
        }
935

untereiner's avatar
untereiner committed
936 937
		if(phi1(d3) != phi3(phi_1(d)))
		{
938
			if(isBoundaryMarked(d))
939 940 941
				std::cout << "Boundary case - ";

			std::cout << "Check: phi3 , faces are not entirely sewn" << std::endl;
942
			return false;
untereiner's avatar
untereiner committed
943
		}
944

945 946 947
        Dart d2 = phi2(d);
        if (phi2(d2) != d) // phi2 involution ?
		{
948 949 950 951
        	if(isBoundaryMarked(d))
        		std::cout << "Boundary case - ";

        	std::cout << "Check: phi2 is not an involution" << std::endl;
952 953
            return false;
        }
954

955 956 957
        Dart d1 = phi1(d);
        if (phi_1(d1) != d) // phi1 a une image correcte ?
		{
958 959 960
        	if(isBoundaryMarked(d))
        		std::cout << "Boundary case - ";

961 962 963
            std::cout << "Check: unconsistent phi_1 link" << std::endl;
            return false;
        }
964

965
        if (m.isMarked(d1)) // phi1 a un seul antécédent ?
966
		{
967 968 969
        	if(isBoundaryMarked(d))
        		std::cout << "Boundary case - ";

970 971 972 973
            std::cout << "Check: dart with two phi1 predecessors" << std::endl;
            return false;
        }
        m.mark(d1);
974

975
        if (d1 == d)
976 977 978 979
        {
        	if(isBoundaryMarked(d))
        		std::cout << "Boundary case - ";

980
            std::cout << "Check: (warning) face loop (one edge)" << std::endl;
981
        }
982 983

        if (phi1(d1) == d)
984 985 986 987
        {
        	if(isBoundaryMarked(d))
        		std::cout << "Boundary case - ";

988
            std::cout << "Check: (warning) face with only two edges" << std::endl;
989
        }
990 991

        if (phi2(d1) == d)
992 993 994 995 996 997
        {
        	if(isBoundaryMarked(d))
        		std::cout << "Boundary case - ";

        	std::cout << "Check: (warning) dandling edge (phi2)" << std::endl;
        }
998 999

        if (phi3(d1) == d)
1000 1001 1002 1003
        {
        	if(isBoundaryMarked(d))
        		std::cout << "Boundary case - ";

1004
            std::cout << "Check: (warning) dandling edge (phi3)" << std::endl;
1005
        }
1006 1007 1008 1009 1010
    }

    for(Dart d = this->begin(); d != this->end(); this->next(d))
    {
        if (!m.isMarked(d)) // phi1 a au moins un antécédent ?
1011
		{
1012 1013 1014
        	if(isBoundaryMarked(d))
        		std::cout << "Boundary case - ";

1015 1016 1017 1018
            std::cout << "Check: dart with no phi1 predecessor" << std::endl;
            return false;
        }
    }
1019

1020
    std::cout << "Check: topology ok" << std::endl;
1021

1022
    return true;
1023 1024
}

Pierre Kraemer's avatar
Pierre Kraemer committed
1025 1026 1027 1028
/*! @name Cell Functors
 *  Apply functors to all darts of a cell
 *************************************************************************/

untereiner's avatar
untereiner committed
1029
bool Map3::foreach_dart_of_vertex(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
1030
{
untereiner's avatar
untereiner committed
1031
	DartMarkerStore mv(*this, thread);	// Lock a marker
Pierre Kraemer's avatar
Pierre Kraemer committed
1032 1033
	bool found = false;					// Last functor return value

untereiner's avatar
untereiner committed
1034 1035 1036
	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
1037 1038
	mv.mark(d);

1039
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
1040
	{
1041
		// add phi21 and phi23 successor if they are not marked yet
1042
		Dart d2 = phi2(darts[i]);
untereiner's avatar
untereiner committed
1043 1044
		Dart d21 = phi1(d2); // turn in volume
		Dart d23 = phi3(d2); // change volume
untereiner's avatar
untereiner committed
1045

untereiner's avatar
untereiner committed
1046 1047 1048 1049 1050 1051 1052 1053 1054
		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
1055 1056
		}

1057
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
1058 1059 1060 1061
	}
	return found;
}

Sylvain Thery's avatar
Sylvain Thery committed
1062
bool Map3::foreach_dart_of_edge(Dart d, FunctorType& f, unsigned int thread)
Pierre Kraemer's avatar
Pierre Kraemer committed
1063
{
untereiner's avatar
untereiner committed
1064
	Dart it = d;
Pierre Kraemer's avatar
Pierre Kraemer committed
1065 1066
	do
	{
untereiner's avatar
untereiner committed
1067
		if (Map2::foreach_dart_of_edge(it, f, thread))
Pierre Kraemer's avatar
Pierre Kraemer committed
1068
			return true;
untereiner's avatar
untereiner committed
1069 1070
		it = alpha2(it);
	} while (it != d);
Pierre Kraemer's avatar
Pierre Kraemer committed
1071 1072 1073
	return false;
}

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

untereiner's avatar
untereiner committed
1079 1080 1081
	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
1082 1083
	mv.mark(d);

1084
	for(unsigned int i = 0; !found && i < darts.size(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
1085
	{
untereiner's avatar
untereiner committed
1086
		// add all successors if they are not marked yet
1087 1088 1089
		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
1090

untereiner's avatar
untereiner committed
1091 1092 1093 1094 1095
		if (!mv.isMarked(d2))
		{
			darts.push_back(d2);
			mv.mark(d2);
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
1096 1097
		if (!mv.isMarked(d3))
		{
untereiner's avatar
untereiner committed
1098 1099
			darts.push_back(d2);
			mv.mark(d2);
Pierre Kraemer's avatar
Pierre Kraemer committed
1100 1101 1102
		}
		if (!mv.isMarked(d4))
		{
untereiner's avatar
untereiner committed
1103
			darts.push_back(d4);
Pierre Kraemer's avatar
Pierre Kraemer committed
1104 1105 1106
			mv.mark(d4);
		}

1107
		found = f(darts[i]);
Pierre Kraemer's avatar
Pierre Kraemer committed
1108 1109 1110 1111
	}
	return found;
}

untereiner's avatar
untereiner committed
1112 1113 1114
/*! @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
1115