embeddedMap2.cpp 12.6 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 29 30 31 32
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include <vector>
#include <algorithm>

#include "Topology/map/embeddedMap2.h"

namespace CGoGN
{

33 34 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
Dart EmbeddedMap2::newFace(unsigned int nbEdges, bool withBoundary)
{
	Dart d = Map2::newFace(nbEdges, withBoundary);

	if(withBoundary)
	{
		if (isOrbitEmbedded<VERTEX>())
		{
			Traversor2FV<EmbeddedMap2> t(*this, d);
			for(Dart it = t.begin(); it != t.end(); it = t.next())
				initOrbitEmbeddingNewCell<VERTEX>(it) ;
		}

		if(isOrbitEmbedded<EDGE>())
		{
			Traversor2FE<EmbeddedMap2> t(*this, d);
			for(Dart it = t.begin(); it != t.end(); it = t.next())
				initOrbitEmbeddingNewCell<EDGE>(it) ;
		}

		if(isOrbitEmbedded<FACE>())
		{
			initOrbitEmbeddingNewCell<FACE>(d) ;
			initOrbitEmbeddingNewCell<FACE>(phi2(d)) ;
		}
	}
	return d ;
}

62 63 64 65 66 67 68
void EmbeddedMap2::splitVertex(Dart d, Dart e)
{
	Dart dd = phi2(d) ;
	Dart ee = phi2(e) ;

	Map2::splitVertex(d, e) ;

69
	if (isOrbitEmbedded<VERTEX>())
70
	{
71 72
		initDartEmbedding<VERTEX>(phi1(dd), getEmbedding<VERTEX>(d)) ;
		setOrbitEmbeddingOnNewCell<VERTEX>(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
73
		copyCell<VERTEX>(e, d) ;
74 75
	}

76 77 78 79 80
	if(isOrbitEmbedded<EDGE>())
	{
		initOrbitEmbeddingNewCell<EDGE>(phi1(dd)) ;
	}

81
	if(isOrbitEmbedded<FACE>())
82
	{
83 84
		initDartEmbedding<FACE>(phi1(dd), getEmbedding<FACE>(dd)) ;
		initDartEmbedding<FACE>(phi1(ee), getEmbedding<FACE>(ee)) ;
85 86 87
	}
}

88
Dart EmbeddedMap2::deleteVertex(Dart d)
89
{
90 91
	Dart f = Map2::deleteVertex(d) ;
	if(f != NIL)
92
	{
93
		if (isOrbitEmbedded<FACE>())
94
		{
95
			setOrbitEmbedding<FACE>(f, getEmbedding<FACE>(f)) ;
96 97
		}
	}
98
	return f ;
99 100
}

David Cazier's avatar
David Cazier committed
101
Dart EmbeddedMap2::cutEdge(Dart d)
102
{
David Cazier's avatar
David Cazier committed
103
	Dart nd = Map2::cutEdge(d) ;
104

105 106 107 108 109
	if(isOrbitEmbedded<VERTEX>())
	{
		initOrbitEmbeddingNewCell<VERTEX>(nd) ;
	}

110
	if (isOrbitEmbedded<EDGE>())
111
	{
112 113
		initDartEmbedding<EDGE>(phi2(d), getEmbedding<EDGE>(d)) ;
		setOrbitEmbeddingOnNewCell<EDGE>(nd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
114
		copyCell<EDGE>(nd, d) ;
115
	}
116

117
	if(isOrbitEmbedded<FACE>())
118
	{
119
		initDartEmbedding<FACE>(nd, getEmbedding<FACE>(d)) ;
120
		Dart e = phi2(nd) ;
121
		initDartEmbedding<FACE>(phi1(e), getEmbedding<FACE>(e)) ;
122
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
123

David Cazier's avatar
David Cazier committed
124
	return nd;
125 126
}

Pierre Kraemer's avatar
Pierre Kraemer committed
127
bool EmbeddedMap2::uncutEdge(Dart d)
128
{
Pierre Kraemer's avatar
Pierre Kraemer committed
129
	if(Map2::uncutEdge(d))
130
	{
131
		if(isOrbitEmbedded<EDGE>())
untereiner's avatar
untereiner committed
132
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
133
			copyDartEmbedding<EDGE>(phi2(d), d) ;
untereiner's avatar
untereiner committed
134
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
135
		return true ;
136
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
137
	return false ;
138 139 140 141 142 143 144 145 146 147 148 149 150
}

bool EmbeddedMap2::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 ;

151
	if(faceDegree(d) == 3)
152 153 154 155 156 157
	{
		if(vertexDegree(phi_1(d)) < 4)
			return false ;
	}

	Dart dd = phi2(d) ;
158
	if(faceDegree(dd) == 3)
159 160 161 162 163 164 165 166 167 168 169 170
	{
		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
	{
171
		unsigned int ve = getEmbedding<VERTEX>(phi2(vit1)) ;
172 173 174 175 176 177 178
		vu1.push_back(ve) ;
		vit1 = alpha1(vit1) ;
	} while(vit1 != end) ;
	end = phi1(d) ;
	Dart vit2 = alpha1(alpha1(dd)) ;
	do
	{
179
		unsigned int ve = getEmbedding<VERTEX>(phi2(vit2)) ;
180 181 182 183 184 185 186 187 188 189 190 191
		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 EmbeddedMap2::collapseEdge(Dart d, bool delDegenerateFaces)
{
	unsigned int vEmb = EMBNULL ;
192
	if (isOrbitEmbedded<VERTEX>())
193
	{
194
		vEmb = getEmbedding<VERTEX>(d) ;
195 196 197 198
	}

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

199
	if (isOrbitEmbedded<VERTEX>())
200
	{
201
		setOrbitEmbedding<VERTEX>(dV, vEmb) ;
202
	}
203
	
204 205 206 207 208 209 210 211 212
	return dV ;
}

bool EmbeddedMap2::flipEdge(Dart d)
{
	if(Map2::flipEdge(d))
	{
		Dart e = phi2(d) ;

213
		if (isOrbitEmbedded<VERTEX>())
214
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
215 216
			copyDartEmbedding<VERTEX>(d, phi1(e)) ;
			copyDartEmbedding<VERTEX>(e, phi1(d)) ;
217
		}
218

219
		if (isOrbitEmbedded<FACE>())
220
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
221 222
			copyDartEmbedding<FACE>(phi_1(d), d) ;
			copyDartEmbedding<FACE>(phi_1(e), e) ;
223
		}
224

225 226 227 228 229 230 231 232 233 234 235
		return true ;
	}
	return false ;
}

bool EmbeddedMap2::flipBackEdge(Dart d)
{
	if(Map2::flipBackEdge(d))
	{
		Dart e = phi2(d) ;

236
		if (isOrbitEmbedded<VERTEX>())
237
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
238 239
			copyDartEmbedding<VERTEX>(d, phi1(e)) ;
			copyDartEmbedding<VERTEX>(e, phi1(d)) ;
240
		}
241

242
		if (isOrbitEmbedded<FACE>())
243
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
244 245
			copyDartEmbedding<FACE>(phi1(d), d) ;
			copyDartEmbedding<FACE>(phi1(e), e) ;
246
		}
247

248 249 250 251 252
		return true ;
	}
	return false ;
}

untereiner's avatar
untereiner committed
253 254 255 256 257 258
void EmbeddedMap2::swapEdges(Dart d, Dart e)
{
	Dart d2 = phi2(d);
	Dart e2 = phi2(e);
	Map2::swapEdges(d,e);

259
	if(isOrbitEmbedded<VERTEX>())
untereiner's avatar
untereiner committed
260
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
261 262 263 264
		copyDartEmbedding<VERTEX>(d, phi2(phi_1(d)));
		copyDartEmbedding<VERTEX>(e, phi2(phi_1(e)));
		copyDartEmbedding<VERTEX>(d2, phi2(phi_1(d2)));
		copyDartEmbedding<VERTEX>(e2, phi2(phi_1(e2)));
untereiner's avatar
untereiner committed
265 266
	}

267
	if(isOrbitEmbedded<EDGE>())
untereiner's avatar
untereiner committed
268 269 270 271
	{

	}

272
	if(isOrbitEmbedded<VOLUME>())
273
		setOrbitEmbeddingOnNewCell<VOLUME>(d);
untereiner's avatar
untereiner committed
274 275
}

276
void EmbeddedMap2::sewFaces(Dart d, Dart e, bool withBoundary)
277
{
278 279 280 281 282
	if (!withBoundary)
	{
		Map2::sewFaces(d, e, false) ;
		return ;
	}
283

untereiner's avatar
untereiner committed
284
	Map2::sewFaces(d, e, withBoundary) ;
285

286
	if (isOrbitEmbedded<VERTEX>())
287
	{
288 289
		setOrbitEmbedding<VERTEX>(d, getEmbedding<VERTEX>(d)) ;
		setOrbitEmbedding<VERTEX>(e, getEmbedding<VERTEX>(phi1(d))) ;
290 291
	}

292
	if (isOrbitEmbedded<EDGE>())
293
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
294
		copyDartEmbedding<EDGE>(e, d) ;
295 296 297
	}
}

298
void EmbeddedMap2::unsewFaces(Dart d, bool withBoundary)
299
{
300 301 302 303 304 305
	if (!withBoundary)
	{
		Map2::unsewFaces(d, false) ;
		return ;
	}

306 307 308
	Dart e = phi2(d) ;
	Map2::unsewFaces(d) ;

309
	if (isOrbitEmbedded<VERTEX>())
310
	{
311 312
		Dart ee = phi1(e) ;
		if(!sameVertex(d, ee))
313
		{
314
			setOrbitEmbeddingOnNewCell<VERTEX>(ee);
Pierre Kraemer's avatar
Pierre Kraemer committed
315
			copyCell<VERTEX>(ee, d);
316 317
		}

318 319
		Dart dd = phi1(d) ;
		if(!sameVertex(e, dd))
320
		{
321
			setOrbitEmbeddingOnNewCell<VERTEX>(dd);
Pierre Kraemer's avatar
Pierre Kraemer committed
322
			copyCell<VERTEX>(dd, e);
323 324
		}
	}
325

326
	if (isOrbitEmbedded<EDGE>())
327
	{
328
		setOrbitEmbeddingOnNewCell<EDGE>(e);
Pierre Kraemer's avatar
Pierre Kraemer committed
329
		copyCell<EDGE>(e, d);
330 331 332 333 334 335
	}
}

bool EmbeddedMap2::collapseDegeneratedFace(Dart d)
{
	Dart e = phi2(d) ;
336 337 338
	bool updateEdgeEmb = false ;
	if(phi1(d) != d)
		updateEdgeEmb = true ;
339

340
	if(Map2::collapseDegeneratedFace(d))
341
	{
342
		if (isOrbitEmbedded<EDGE>() && updateEdgeEmb)
343
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
344
			copyDartEmbedding<EDGE>(phi2(e), e) ;
345 346 347 348 349 350 351 352 353 354
		}
		return true ;
	}
	return false ;
}

void EmbeddedMap2::splitFace(Dart d, Dart e)
{
	Map2::splitFace(d, e) ;

355
	if (isOrbitEmbedded<VERTEX>())
356
	{
357 358
		initDartEmbedding<VERTEX>(phi_1(e), getEmbedding<VERTEX>(d)) ;
		initDartEmbedding<VERTEX>(phi_1(d), getEmbedding<VERTEX>(e)) ;
359
	}
360 361 362 363 364 365

	if(isOrbitEmbedded<EDGE>())
	{
		initOrbitEmbeddingNewCell<EDGE>(phi_1(d)) ;
	}

366
	if (isOrbitEmbedded<FACE>())
367
	{
368 369
		initDartEmbedding<FACE>(phi_1(d), getEmbedding<FACE>(d)) ;
		setOrbitEmbeddingOnNewCell<FACE>(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
370
		copyCell<FACE>(e, d) ;
371 372 373 374 375 376 377 378 379
	}
}

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

	if(Map2::mergeFaces(d))
	{
380
		if (isOrbitEmbedded<FACE>())
381
		{
382
			setOrbitEmbedding<FACE>(dNext, getEmbedding<FACE>(dNext)) ;
383 384 385 386 387 388 389 390 391 392
		}
		return true ;
	}
	return false ;
}

bool EmbeddedMap2::mergeVolumes(Dart d, Dart e)
{
	std::vector<Dart> darts ;
	std::vector<unsigned int> vEmb ;
untereiner's avatar
untereiner committed
393
	vEmb.reserve(32) ;
394
	std::vector<unsigned int> eEmb ;
untereiner's avatar
untereiner committed
395
	eEmb.reserve(32) ;
396 397 398 399 400
	Dart fit = d ;
	do
	{
		darts.push_back(phi2(fit)) ;

401
		if (isOrbitEmbedded<VERTEX>())
402
		{
403
			vEmb.push_back(getEmbedding<VERTEX>(phi2(fit))) ;
404 405
		}

406
		if (isOrbitEmbedded<EDGE>())
407
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
408
			eEmb.push_back(getEmbedding<EDGE>(fit)) ;
409
		}
410
		
411 412 413 414 415 416 417
		fit = phi1(fit) ;
	} while (fit != d) ;

	if(Map2::mergeVolumes(d, e))
	{
		for(unsigned int i = 0; i < darts.size(); ++i)
		{
418
			if (isOrbitEmbedded<VERTEX>())
419
			{
420
				setOrbitEmbedding<VERTEX>(darts[i], vEmb[i]) ;
421 422
			}

423
			if (isOrbitEmbedded<EDGE>())
424
			{
425
				setOrbitEmbedding<EDGE>(darts[i], eEmb[i]) ;
426 427 428 429 430 431 432
			}
		}
		return true ;
	}
	return false ;
}

433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454
void EmbeddedMap2::splitSurface(std::vector<Dart>& vd, bool firstSideClosed, bool secondSideClosed)
{
	std::vector<Dart> darts ;
	darts.reserve(vd.size());

	// save the edge neighbors darts
	for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
	{
		darts.push_back(phi2(*it));
	}

	assert(darts.size() == vd.size());

	Map2::splitSurface(vd, firstSideClosed, secondSideClosed);

	// follow the edge path a second time to embed the vertex, edge and volume orbits
	for(unsigned int i = 0; i < vd.size(); ++i)
	{
		Dart dit = vd[i];
		Dart dit2 = darts[i];

		// embed the vertex embedded from the origin volume to the new darts
455
		if(isOrbitEmbedded<VERTEX>())
456
		{
457 458
			initDartEmbedding<VERTEX>(phi2(dit), getEmbedding<VERTEX>(phi1(dit)));
			initDartEmbedding<VERTEX>(phi2(dit2), getEmbedding<VERTEX>(phi1(dit2)));
459 460 461
		}

		// embed the edge embedded from the origin volume to the new darts
462
		if(isOrbitEmbedded<EDGE>())
463
		{
464 465 466
			initDartEmbedding<EDGE>(phi2(dit), getEmbedding<EDGE>(dit));
			setOrbitEmbeddingOnNewCell<EDGE>(phi2(dit2));
			copyCell<EDGE>(dit2, dit);
467 468 469
		}

		// embed the volume embedded from the origin volume to the new darts
470
		if(isOrbitEmbedded<VOLUME>())
471
		{
472 473
			initDartEmbedding<VOLUME>(phi2(dit), getEmbedding<VOLUME>(dit));
			initDartEmbedding<VOLUME>(phi2(dit2), getEmbedding<VOLUME>(dit2));
474 475 476 477
		}
	}
}

478
unsigned int EmbeddedMap2::closeHole(Dart d, bool forboundary)
479
{
480
	unsigned int nbE = Map2::closeHole(d, forboundary) ;
481 482 483 484
	Dart dd = phi2(d) ;
	Dart f = dd ;
	do
	{
485
		if (isOrbitEmbedded<VERTEX>())
486
		{
487
			initDartEmbedding<VERTEX>(f, getEmbedding<VERTEX>(phi1(phi2(f)))) ;
488
		}
489

490
		if (isOrbitEmbedded<EDGE>())
491
		{
492
			initDartEmbedding<EDGE>(f, getEmbedding<EDGE>(phi2(f))) ;
493
		}
494

495 496
		f = phi1(f) ;
	} while(dd != f) ;
497 498 499 500 501 502

	if(isOrbitEmbedded<FACE>())
	{
		initOrbitEmbeddingNewCell<FACE>(dd) ;
	}

503 504 505 506 507 508 509 510 511 512 513 514
	return nbE ;
}

bool EmbeddedMap2::check()
{
	bool topo = Map2::check() ;
	if (!topo)
		return false ;

	CGoGNout << "Check: embedding begin" << CGoGNendl ;
	for(Dart d = begin(); d != end(); next(d))
	{
515
		if (isOrbitEmbedded<VERTEX>())
516
		{
517
			if (getEmbedding<VERTEX>(d) != getEmbedding<VERTEX>(alpha1(d)))
518 519 520 521 522 523
			{
				CGoGNout << "Check: different embeddings on vertex" << CGoGNendl ;
				return false ;
			}
		}

524
		if (isOrbitEmbedded<EDGE>())
525
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
526
			if (getEmbedding<EDGE>(d) != getEmbedding<EDGE>(phi2(d)))
527 528 529 530 531 532
			{
				CGoGNout << "Check: different embeddings on edge" << CGoGNendl ;
				return false ;
			}
		}

533 534 535 536 537 538 539 540
//		if (isOrbitEmbedded(ORIENTED_FACE))
//		{
//			if (getEmbedding(ORIENTED_FACE, d) != getEmbedding(ORIENTED_FACE, phi1(d)))
//		{
//				CGoGNout << "Check: different embeddings on oriented face" << CGoGNendl ;
//				return false ;
//			}
//		}
untereiner's avatar
untereiner committed
541

542
		if (isOrbitEmbedded<FACE>())
543
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
544
			if (getEmbedding<FACE>(d) != getEmbedding<FACE>(phi1(d)))
545
			{
546 547 548 549 550
				CGoGNout << "Check: different embeddings on face" << CGoGNendl ;
				return false ;
			}
		}
	}
551

552
	CGoGNout << "Check: embedding ok" << CGoGNendl ;
553

Pierre Kraemer's avatar
Pierre Kraemer committed
554
    std::cout << "nb vertex orbits : " << getNbOrbits<VERTEX>() << std::endl ;
555 556
    std::cout << "nb vertex cells : " << m_attribs[VERTEX].size() << std::endl ;

Pierre Kraemer's avatar
Pierre Kraemer committed
557
    std::cout << "nb edge orbits : " << getNbOrbits<EDGE>() << std::endl ;
558 559
    std::cout << "nb edge cells : " << m_attribs[EDGE].size() << std::endl ;

Pierre Kraemer's avatar
Pierre Kraemer committed
560
    std::cout << "nb face orbits : " << getNbOrbits<FACE>() << std::endl ;
561 562
    std::cout << "nb face cells : " << m_attribs[FACE].size() << std::endl ;

563 564 565 566
	return true ;
}

} // namespace CGoGN