embeddedGMap2.cpp 14.5 KB
Newer Older
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           *
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/                                           *
21 22 23 24 25 26 27 28
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include <vector>
#include <algorithm>

#include "Topology/gmap/embeddedGMap2.h"
29
#include "Topology/generic/traversor/traversor2.h"
30 31 32 33

namespace CGoGN
{

Thery Sylvain's avatar
Thery Sylvain committed
34 35 36 37 38 39 40 41 42 43
Dart EmbeddedGMap2::newFace(unsigned int nbEdges, bool withBoundary)
{
	Dart d = GMap2::newFace(nbEdges, withBoundary);

	if(withBoundary)
	{
		if (isOrbitEmbedded<VERTEX>())
		{
			Traversor2FV<EmbeddedGMap2> t(*this, d);
			for(Dart it = t.begin(); it != t.end(); it = t.next())
44
				Algo::Topo::initOrbitEmbeddingOnNewCell<VERTEX>(*this, it) ;
Thery Sylvain's avatar
Thery Sylvain committed
45 46 47 48 49 50
		}

		if(isOrbitEmbedded<EDGE>())
		{
			Traversor2FE<EmbeddedGMap2> t(*this, d);
			for(Dart it = t.begin(); it != t.end(); it = t.next())
51
				Algo::Topo::initOrbitEmbeddingOnNewCell<EDGE>(*this, it) ;
Thery Sylvain's avatar
Thery Sylvain committed
52 53 54 55
		}

		if(isOrbitEmbedded<FACE>())
		{
56 57
			Algo::Topo::initOrbitEmbeddingOnNewCell<FACE>(*this, d) ;
			Algo::Topo::initOrbitEmbeddingOnNewCell<FACE>(*this, phi2(d)) ;
Thery Sylvain's avatar
Thery Sylvain committed
58 59 60
		}
	}

61 62 63 64 65 66 67 68
//	else
//	{
//		if (isOrbitEmbedded<VERTEX>())
//		{
//			Traversor2FV<EmbeddedGMap2> t(*this, d);
//			for(Dart it = t.begin(); it != t.end(); it = t.next())
//				initOrbitEmbeddingNewCell<VERTEX>(it) ;
//		}
Thery Sylvain's avatar
Thery Sylvain committed
69

70 71 72 73
//		if(isOrbitEmbedded<FACE>())
//			initOrbitEmbeddingNewCell<FACE>(d) ;

//	}
Thery Sylvain's avatar
Thery Sylvain committed
74 75 76 77
	return d ;
}


78 79 80 81 82 83 84
void EmbeddedGMap2::splitVertex(Dart d, Dart e)
{
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;

	GMap2::splitVertex(d, e) ;

85
	if (isOrbitEmbedded<VERTEX>())
86
	{
87 88 89 90
		unsigned int vEmb = getEmbedding<VERTEX>(d) ;
		setDartEmbedding<VERTEX>(phi1(dd), vEmb) ;
		setDartEmbedding<VERTEX>(beta2(phi1(dd)), vEmb) ;
		setDartEmbedding<VERTEX>(beta0(dd), vEmb) ;
91

92 93
		Algo::Topo::setOrbitEmbeddingOnNewCell<VERTEX>(*this, e) ;
		Algo::Topo::copyCellAttributes<VERTEX>(*this, e, d) ;
94 95
	}

96 97
	if(isOrbitEmbedded<EDGE>())
	{
98
		Algo::Topo::initOrbitEmbeddingOnNewCell<EDGE>(*this, phi1(dd)) ;
99 100
	}

101
	if(isOrbitEmbedded<FACE>())
102
	{
103
		unsigned int f1Emb = getEmbedding<FACE>(dd) ;
104 105
		setDartEmbedding<FACE>(phi1(dd), f1Emb) ;
		setDartEmbedding<FACE>(beta0(phi1(dd)), f1Emb) ;
106
		unsigned int f2Emb = getEmbedding<FACE>(ee) ;
107 108
		setDartEmbedding<FACE>(phi1(ee), f2Emb) ;
		setDartEmbedding<FACE>(beta0(phi1(ee)), f2Emb) ;
109 110 111
	}
}

112
Dart EmbeddedGMap2::deleteVertex(Dart d)
113
{
114 115
	Dart f = GMap2::deleteVertex(d) ;
	if(f != NIL)
116
	{
117
		if (isOrbitEmbedded<FACE>())
118
		{
119
			Algo::Topo::setOrbitEmbedding<FACE>(*this, f, getEmbedding<FACE>(f)) ;
120
		}
121
	}
122
	return f ;
123
}
124

125
Dart EmbeddedGMap2::cutEdge(Dart d)
126
{
127
	Dart nd = GMap2::cutEdge(d) ;
128

129 130
	if(isOrbitEmbedded<VERTEX>())
	{
131
		Algo::Topo::initOrbitEmbeddingOnNewCell<VERTEX>(*this, nd) ;
132 133
	}

134
	if (isOrbitEmbedded<EDGE>())
135
	{
136 137 138
		unsigned int eEmb = getEmbedding<EDGE>(d) ;
		setDartEmbedding<EDGE>(phi2(d), eEmb) ;
		setDartEmbedding<EDGE>(beta0(d), eEmb) ;
139 140
		Algo::Topo::setOrbitEmbeddingOnNewCell<EDGE>(*this, nd) ;
		Algo::Topo::copyCellAttributes<EDGE>(*this, nd, d) ;
141
	}
Thomas's avatar
Thomas committed
142

143
	if(isOrbitEmbedded<FACE>())
144
	{
145 146 147
		unsigned int f1Emb = getEmbedding<FACE>(d) ;
		setDartEmbedding<FACE>(phi1(d), f1Emb) ;
		setDartEmbedding<FACE>(beta0(d), f1Emb) ;
148
		Dart e = phi2(nd) ;
149 150 151
		unsigned int f2Emb = getEmbedding<FACE>(d) ;
		setDartEmbedding<FACE>(phi1(e), f2Emb) ;
		setDartEmbedding<FACE>(beta0(e), f2Emb) ;
152
	}
153 154

	return nd ;
155 156
}

157
bool EmbeddedGMap2::uncutEdge(Dart d)
158
{
159 160
	if(GMap2::uncutEdge(d))
	{
161
		if(isOrbitEmbedded<EDGE>())
162
		{
163 164 165
			unsigned int eEmb = getEmbedding<EDGE>(d) ;
			setDartEmbedding<EDGE>(phi2(d), eEmb) ;
			setDartEmbedding<EDGE>(beta0(d), eEmb) ;
166 167 168 169
		}
		return true ;
	}
	return false ;
170
}
171 172 173 174 175 176 177 178 179 180 181 182

bool EmbeddedGMap2::edgeCanCollapse(Dart d)
{
	if(isBoundaryVertex(d) || isBoundaryVertex(phi1(d)))
		return false ;

	unsigned int val_v1 = vertexDegree(d) ;
	unsigned int val_v2 = vertexDegree(phi1(d)) ;

	if(val_v1 + val_v2 < 8 || val_v1 + val_v2 > 14)
		return false ;

183
	if(faceDegree(d) == 3)
184 185 186 187 188 189
	{
		if(vertexDegree(phi_1(d)) < 4)
			return false ;
	}

	Dart dd = phi2(d) ;
190
	if(faceDegree(dd) == 3)
191 192 193 194 195 196 197 198 199 200 201 202
	{
		if(vertexDegree(phi_1(dd)) < 4)
			return false ;
	}

	// Check vertex sharing condition
	std::vector<unsigned int> vu1 ;
	vu1.reserve(32) ;
	Dart vit1 = alpha1(alpha1(d)) ;
	Dart end = phi1(dd) ;
	do
	{
203
		unsigned int ve = getEmbedding<VERTEX>(phi2(vit1)) ;
204 205 206 207 208 209 210
		vu1.push_back(ve) ;
		vit1 = alpha1(vit1) ;
	} while(vit1 != end) ;
	end = phi1(d) ;
	Dart vit2 = alpha1(alpha1(dd)) ;
	do
	{
211
		unsigned int ve = getEmbedding<VERTEX>(phi2(vit2)) ;
212 213 214 215 216 217 218 219 220 221 222 223
		std::vector<unsigned int>::iterator it = std::find(vu1.begin(), vu1.end(), ve) ;
		if(it != vu1.end())
			return false ;
		vit2 = alpha1(vit2) ;
	} while(vit2 != end) ;

	return true ;
}

Dart EmbeddedGMap2::collapseEdge(Dart d, bool delDegenerateFaces)
{
	unsigned int vEmb = EMBNULL ;
224
	if (isOrbitEmbedded<VERTEX>())
225
	{
226
		vEmb = getEmbedding<VERTEX>(d) ;
227 228 229 230
	}

	Dart dV = GMap2::collapseEdge(d, delDegenerateFaces);

231
	if (isOrbitEmbedded<VERTEX>())
232
	{
233
		Algo::Topo::setOrbitEmbedding<VERTEX>(*this, dV, vEmb) ;
234 235 236 237 238 239 240 241 242 243 244
	}

	return dV ;
}

bool EmbeddedGMap2::flipEdge(Dart d)
{
	if(GMap2::flipEdge(d))
	{
		Dart e = phi2(d) ;

245
		if (isOrbitEmbedded<VERTEX>())
246
		{
247 248 249 250 251 252
			unsigned int v1Emb = getEmbedding<VERTEX>(beta1(d)) ;
			setDartEmbedding<VERTEX>(d, v1Emb) ;
			setDartEmbedding<VERTEX>(beta2(d), v1Emb) ;
			unsigned int v2Emb = getEmbedding<VERTEX>(beta1(e)) ;
			setDartEmbedding<VERTEX>(e, v2Emb) ;
			setDartEmbedding<VERTEX>(beta2(e), v2Emb) ;
253
		}
254
		if (isOrbitEmbedded<FACE>())
255
		{
256 257 258 259 260 261
			unsigned int f1Emb = getEmbedding<FACE>(d) ;
			setDartEmbedding<FACE>(phi_1(d), f1Emb) ;
			setDartEmbedding<FACE>(beta1(d), f1Emb) ;
			unsigned int f2Emb = getEmbedding<FACE>(e) ;
			setDartEmbedding<FACE>(phi_1(e), f2Emb) ;
			setDartEmbedding<FACE>(beta1(e), f2Emb) ;
262 263 264 265 266 267 268 269 270 271 272 273
		}
		return true ;
	}
	return false ;
}

bool EmbeddedGMap2::flipBackEdge(Dart d)
{
	if(GMap2::flipBackEdge(d))
	{
		Dart e = phi2(d) ;

274
		if (isOrbitEmbedded<VERTEX>())
275
		{
276 277 278 279 280 281
			unsigned int v1Emb = getEmbedding<VERTEX>(beta1(d)) ;
			setDartEmbedding<VERTEX>(d, v1Emb) ;
			setDartEmbedding<VERTEX>(beta2(d), v1Emb) ;
			unsigned int v2Emb = getEmbedding<VERTEX>(beta1(e)) ;
			setDartEmbedding<VERTEX>(e, v2Emb) ;
			setDartEmbedding<VERTEX>(beta2(e), v2Emb) ;
282
		}
Thomas's avatar
Thomas committed
283

284
		if (isOrbitEmbedded<FACE>())
285
		{
286 287 288 289 290 291
			unsigned int f1Emb = getEmbedding<FACE>(d) ;
			setDartEmbedding<FACE>(phi1(d), f1Emb) ;
			setDartEmbedding<FACE>(beta0(phi1(d)), f1Emb) ;
			unsigned int f2Emb = getEmbedding<FACE>(e) ;
			setDartEmbedding<FACE>(phi1(e), f2Emb) ;
			setDartEmbedding<FACE>(beta0(phi1(e)), f2Emb) ;
292 293 294 295 296 297
		}
		return true ;
	}
	return false ;
}

298 299 300 301
//void EmbeddedGMap2::insertEdgeInVertex(Dart d, Dart e)
//{
//	GMap2::insertEdgeInVertex(d, e);
//
302
//	if (isOrbitEmbedded<VERTEX>())
303
//	{
304 305
//		copyDartEmbedding<VERTEX>(e, d) ;
//		copyDartEmbedding<VERTEX>(beta2(e), d) ;
306 307
//	}
//
308
//	if (isOrbitEmbedded<FACE>())
309 310 311
//	{
//		if(!sameFace(d,e))
//		{
312
//			setOrbitEmbeddingOnNewCell<FACE>(e);
313
//			copyCell<FACE>(e, d) ;
314 315 316
//		}
//		else
//		{
317
//			setOrbitEmbedding<FACE>(d, getEmbedding<FACE>(d)) ;
318 319 320 321 322 323 324 325 326 327
//		}
//	}
//}
//
//void EmbeddedGMap2::removeEdgeFromVertex(Dart d)
//{
//	Dart dPrev = alpha_1(d);
//
//	GMap2::removeEdgeFromVertex(d);
//
328
//	if (isOrbitEmbedded<VERTEX>())
329
//	{
330
//		setOrbitEmbeddingOnNewCell<VERTEX>(d);
331
//		copyCell<VERTEX>(d, dPrev);
332 333
//	}
//
334
//	if (isOrbitEmbedded<FACE>())
335 336 337
//	{
//		if(!sameFace(d, dPrev))
//		{
338
//			setOrbitEmbeddingOnNewCell<FACE>(d);
339
//			copyCell<FACE>(d, dPrev) ;
340 341 342
//		}
//		else
//		{
343
//			setOrbitEmbedding<FACE>(d, getEmbedding<FACE>(d)) ;
344 345 346
//		}
//	}
//}
347

348
void EmbeddedGMap2::sewFaces(Dart d, Dart e, bool withBoundary)
349
{
350 351
	// for fixed point construction (import & primitives)
	if (!withBoundary)
352
	{
353
		GMap2::sewFaces(d, e, false) ;
Thery Sylvain's avatar
Thery Sylvain committed
354 355
		if(isOrbitEmbedded<EDGE>())
		{
356
			Algo::Topo::initOrbitEmbeddingOnNewCell<EDGE>(*this, d) ;
Thery Sylvain's avatar
Thery Sylvain committed
357
		}
358
		return ;
359 360
	}

361
	GMap2::sewFaces(d, e, true) ;
362

363
	if (isOrbitEmbedded<VERTEX>())
364
	{
365 366
		Algo::Topo::setOrbitEmbedding<VERTEX>(*this, d, getEmbedding<VERTEX>(d)) ;
		Algo::Topo::setOrbitEmbedding<VERTEX>(*this, e, getEmbedding<VERTEX>(beta0(d))) ;
367 368
	}

369
	if (isOrbitEmbedded<EDGE>())
370
	{
371
		Algo::Topo::setOrbitEmbedding<EDGE>(*this, e, getEmbedding<EDGE>(d)) ;
372 373 374 375 376
	}
}

void EmbeddedGMap2::unsewFaces(Dart d)
{
377 378
	Dart e = beta2(d);
	GMap2::unsewFaces(d);
379

380
	if (isOrbitEmbedded<VERTEX>())
381
	{
382
		if(!sameVertex(d,e))
383
		{
384 385
			Algo::Topo::setOrbitEmbeddingOnNewCell<VERTEX>(*this, e);
			Algo::Topo::copyCellAttributes<VERTEX>(*this, e, d);
386 387
		}

388 389 390 391
		d = beta0(d);
		e = beta0(e);

		if(!sameVertex(d,e))
392
		{
393 394
			Algo::Topo::setOrbitEmbeddingOnNewCell<VERTEX>(*this, e);
			Algo::Topo::copyCellAttributes<VERTEX>(*this, e, d);
395 396
		}
	}
397

398
	if (isOrbitEmbedded<EDGE>())
399
	{
400 401
		Algo::Topo::setOrbitEmbeddingOnNewCell<EDGE>(*this, e);
		Algo::Topo::copyCellAttributes<EDGE>(*this, e, d);
402 403 404 405 406
	}
}

bool EmbeddedGMap2::collapseDegeneratedFace(Dart d)
{
407 408 409 410
	Dart e = beta2(d) ;
	bool updateEdgeEmb = false ;
	if(phi1(d) != d)
		updateEdgeEmb = true ;
411 412 413

	if(GMap2::collapseDegeneratedFace(d))
	{
414
		if (isOrbitEmbedded<EDGE>() && updateEdgeEmb)
415
		{
416 417 418
			unsigned int eEmb = getEmbedding<EDGE>(e) ;
			setDartEmbedding<EDGE>(beta2(e), eEmb) ;
			setDartEmbedding<EDGE>(phi2(e), eEmb) ;
419 420 421 422 423 424 425 426 427 428
		}
		return true ;
	}
	return false ;
}

void EmbeddedGMap2::splitFace(Dart d, Dart e)
{
	GMap2::splitFace(d, e) ;

429
	if (isOrbitEmbedded<VERTEX>())
430
	{
431 432 433 434 435 436 437 438
		unsigned int v1Emb = getEmbedding<VERTEX>(d) ;
		setDartEmbedding<VERTEX>(phi_1(e), v1Emb) ;
		setDartEmbedding<VERTEX>(beta1(d), v1Emb) ;
		setDartEmbedding<VERTEX>(beta1(phi_1(e)), v1Emb) ;
		unsigned int v2Emb = getEmbedding<VERTEX>(e) ;
		setDartEmbedding<VERTEX>(phi_1(d), v2Emb) ;
		setDartEmbedding<VERTEX>(beta1(e), v2Emb) ;
		setDartEmbedding<VERTEX>(beta1(phi_1(d)), v2Emb) ;
439
	}
440 441 442

	if(isOrbitEmbedded<EDGE>())
	{
443
		Algo::Topo::initOrbitEmbeddingOnNewCell<EDGE>(*this, beta1(d)) ;
444 445
	}

446
	if (isOrbitEmbedded<FACE>())
447
	{
448 449 450
		unsigned int fEmb = getEmbedding<FACE>(d) ;
		setDartEmbedding<FACE>(phi_1(d), fEmb) ;
		setDartEmbedding<FACE>(beta1(phi_1(d)), fEmb) ;
451 452
		Algo::Topo::setOrbitEmbeddingOnNewCell<FACE>(*this, e) ;
		Algo::Topo::copyCellAttributes<FACE>(*this, e, d) ;
453 454 455 456 457 458 459 460 461
	}
}

bool EmbeddedGMap2::mergeFaces(Dart d)
{
	Dart dNext = phi1(d) ;

	if(GMap2::mergeFaces(d))
	{
462
		if (isOrbitEmbedded<FACE>())
463
		{
464
			Algo::Topo::setOrbitEmbedding<FACE>(*this, dNext, getEmbedding<FACE>(dNext)) ;
465 466 467 468 469 470 471 472 473 474 475
		}
		return true ;
	}
	return false ;
}

bool EmbeddedGMap2::mergeVolumes(Dart d, Dart e)
{
	std::vector<Dart> darts ;
	std::vector<unsigned int> vEmb ;
	std::vector<unsigned int> eEmb ;
476 477 478 479
	darts.reserve(32) ;
	vEmb.reserve(32) ;
	eEmb.reserve(32) ;

480 481 482 483 484
	Dart fit = d ;
	do
	{
		darts.push_back(phi2(fit)) ;

485
		if (isOrbitEmbedded<VERTEX>())
486
		{
487
			vEmb.push_back(getEmbedding<VERTEX>(phi2(fit))) ;
488 489
		}

490
		if (isOrbitEmbedded<EDGE>())
491
		{
492
			eEmb.push_back(getEmbedding<EDGE>(fit)) ;
493 494 495 496 497 498 499 500 501
		}

		fit = phi1(fit) ;
	} while (fit != d) ;

	if(GMap2::mergeVolumes(d, e))
	{
		for(unsigned int i = 0; i < darts.size(); ++i)
		{
502
			if (isOrbitEmbedded<VERTEX>())
503
			{
504
				Algo::Topo::setOrbitEmbedding<VERTEX>(*this, darts[i], vEmb[i]) ;
505 506
			}

507
			if (isOrbitEmbedded<EDGE>())
508
			{
509
				Algo::Topo::setOrbitEmbedding<EDGE>(*this, darts[i], eEmb[i]) ;
510 511 512 513 514 515 516
			}
		}
		return true ;
	}
	return false ;
}

517
unsigned int EmbeddedGMap2::closeHole(Dart d, bool forboundary)
518
{
519
	unsigned int nbE = GMap2::closeHole(d, forboundary) ;
520
	Dart dd = phi2(d) ;
521
	Dart it = dd ;
522 523
	do
	{
524
		if (isOrbitEmbedded<VERTEX>())
525
		{
526 527
			copyDartEmbedding<VERTEX>(it, beta2(it)) ;
			copyDartEmbedding<VERTEX>(beta0(it), phi2(it)) ;
528
		}
529
		if (isOrbitEmbedded<EDGE>())
530
		{
531 532 533
			unsigned int eEmb = getEmbedding<EDGE>(beta2(it)) ;
			setDartEmbedding<EDGE>(it, eEmb) ;
			setDartEmbedding<EDGE>(beta0(it), eEmb) ;
534
		}
535 536
		it = phi1(it) ;
	} while(it != dd) ;
537 538 539

	if(isOrbitEmbedded<FACE>())
	{
540
		Algo::Topo::initOrbitEmbeddingOnNewCell<FACE>(*this, dd) ;
541 542
	}

543 544 545 546 547 548 549 550 551 552 553 554
	return nbE ;
}

bool EmbeddedGMap2::check()
{
	bool topo = GMap2::check() ;
	if (!topo)
		return false ;

	CGoGNout << "Check: embedding begin" << CGoGNendl ;
	for(Dart d = begin(); d != end(); next(d))
	{
555
		if (isOrbitEmbedded<VERTEX>())
556
		{
557
			if (getEmbedding<VERTEX>(d) != getEmbedding<VERTEX>(alpha1(d)))
558 559 560 561 562 563
			{
				CGoGNout << "Check: different embeddings on vertex" << CGoGNendl ;
				return false ;
			}
		}

564
		if (isOrbitEmbedded<EDGE>())
565
		{
566
			if (getEmbedding<EDGE>(d) != getEmbedding<EDGE>(phi2(d)))
567 568 569 570 571 572
			{
				CGoGNout << "Check: different embeddings on edge" << CGoGNendl ;
				return false ;
			}
		}

573
		if (isOrbitEmbedded<FACE>())
574
		{
575
			if (getEmbedding<FACE>(d) != getEmbedding<FACE>(phi1(d)))
576 577 578 579 580 581
		{
				CGoGNout << "Check: different embeddings on face" << CGoGNendl ;
				return false ;
			}
		}
	}
582

583
	CGoGNout << "Check: embedding ok" << CGoGNendl ;
584

585
	std::cout << "nb vertex orbits : " << Algo::Topo::getNbOrbits<VERTEX>(*this) << std::endl ;
586 587
    std::cout << "nb vertex cells : " << m_attribs[VERTEX].size() << std::endl ;

588
	std::cout << "nb edge orbits : " << Algo::Topo::getNbOrbits<EDGE>(*this) << std::endl ;
589 590
    std::cout << "nb edge cells : " << m_attribs[EDGE].size() << std::endl ;

591
	std::cout << "nb face orbits : " << Algo::Topo::getNbOrbits<FACE>(*this) << std::endl ;
592 593
    std::cout << "nb face cells : " << m_attribs[FACE].size() << std::endl ;

594 595 596 597
	return true ;
}

} // namespace CGoGN