embeddedMap2.hpp 10.6 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-2011, 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.u-strasbg.fr/                                         *
Pierre Kraemer's avatar
Pierre Kraemer committed
21 22 23 24 25 26 27 28 29 30 31 32 33
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include <vector>
#include <algorithm>

namespace CGoGN
{

template <typename MAP2>
void EmbeddedMap2<MAP2>::splitVertex(Dart d, Dart e)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
34 35
	Dart dd = MAP2::phi2(d) ;
	Dart ee = MAP2::phi2(e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
36 37 38

	MAP2::splitVertex(d, e) ;

39
	if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
40
	{
41 42 43 44
		MAP2::copyDartEmbedding(VERTEX, MAP2::phi1(dd), d) ;
		MAP2::copyDartEmbedding(VERTEX, MAP2::phi1(ee), e) ;
		MAP2::embedNewCell(VERTEX, e) ;
		MAP2::copyCell(VERTEX, e, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
45
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
46

47
	if(MAP2::isOrbitEmbedded(FACE))
Pierre Kraemer's avatar
Pierre Kraemer committed
48
	{
49 50
		MAP2::copyDartEmbedding(FACE, MAP2::phi1(dd), dd) ;
		MAP2::copyDartEmbedding(FACE, MAP2::phi1(ee), ee) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
51
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
52 53
}

Pierre Kraemer's avatar
Pierre Kraemer committed
54 55 56 57 58 59
template <typename MAP2>
bool EmbeddedMap2<MAP2>::deleteVertex(Dart d)
{
	Dart f = MAP2::phi1(d) ;
	if(MAP2::deleteVertex(d))
	{
60
		if (MAP2::isOrbitEmbedded(FACE))
Pierre Kraemer's avatar
Pierre Kraemer committed
61
		{
62
			MAP2::embedOrbit(FACE, f, MAP2::getEmbedding(FACE, f)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
63 64 65 66 67 68
		}
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
69 70 71 72 73
template <typename MAP2>
void EmbeddedMap2<MAP2>::cutEdge(Dart d)
{
	MAP2::cutEdge(d) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
74 75
	Dart nd = MAP2::phi1(d) ;

76
	if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
77
	{
78
		MAP2::embedNewCell(EDGE, nd) ;
79
		MAP2::copyDartEmbedding(EDGE, MAP2::phi2(d), d) ;
80
		MAP2::copyCell(EDGE, nd, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
81
	}
82
	if(MAP2::isOrbitEmbedded(FACE))
Pierre Kraemer's avatar
Pierre Kraemer committed
83
	{
84
		MAP2::copyDartEmbedding(FACE, MAP2::phi1(d), d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
85 86
		Dart e = MAP2::phi2(nd) ;
		if(e != nd)
87
			MAP2::copyDartEmbedding(FACE, MAP2::phi1(e), e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
88 89 90
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
91 92 93 94 95 96 97 98 99
template <typename MAP2>
void EmbeddedMap2<MAP2>::uncutEdge(Dart d)
{
	bool doSomethg = (d != MAP2::phi2(d)) ;

	MAP2::uncutEdge(d) ;

	if(doSomethg)
	{
100 101
		if(MAP2::isOrbitEmbedded(EDGE))
			MAP2::copyDartEmbedding(EDGE, MAP2::phi2(d), d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
102 103 104
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
template <typename MAP2>
bool EmbeddedMap2<MAP2>::edgeCanCollapse(Dart d)
{
	if(MAP2::phi2(d) == d)
		return false ;

	if(MAP2::isBoundaryVertex(d) || MAP2::isBoundaryVertex(MAP2::phi1(d)))
		return false ;

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

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

	if(MAP2::isFaceTriangle(d))
	{
		if(MAP2::vertexDegree(MAP2::phi_1(d)) < 4)
			return false ;
	}

	Dart dd = MAP2::phi2(d) ;
	if(MAP2::isFaceTriangle(dd))
	{
		if(MAP2::vertexDegree(MAP2::phi_1(dd)) < 4)
			return false ;
	}

	// Check vertex sharing condition
	std::vector<unsigned int> vu1 ;
	vu1.reserve(32) ;
	Dart vit1 = MAP2::alpha1(MAP2::alpha1(d)) ;
	Dart end = MAP2::phi1(dd) ;
	do
	{
140
		unsigned int ve = MAP2::getEmbedding(VERTEX, MAP2::phi2(vit1)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
141 142 143 144 145 146 147
		vu1.push_back(ve) ;
		vit1 = MAP2::alpha1(vit1) ;
	} while(vit1 != end) ;
	end = MAP2::phi1(d) ;
	Dart vit2 = MAP2::alpha1(MAP2::alpha1(dd)) ;
	do
	{
148
		unsigned int ve = MAP2::getEmbedding(VERTEX, MAP2::phi2(vit2)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
149 150 151 152 153 154 155 156 157 158
		std::vector<unsigned int>::iterator it = std::find(vu1.begin(), vu1.end(), ve) ;
		if(it != vu1.end())
			return false ;
		vit2 = MAP2::alpha1(vit2) ;
	} while(vit2 != end) ;

	return true ;
}

template <typename MAP2>
159
Dart EmbeddedMap2<MAP2>::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
160 161
{
	unsigned int vEmb = EMBNULL ;
162
	if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
163
	{
164
		vEmb = MAP2::getEmbedding(VERTEX, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
165 166
	}

167
	Dart dV = MAP2::collapseEdge(d, delDegenerateFaces);
Pierre Kraemer's avatar
Pierre Kraemer committed
168

169
	if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
170
	{
171
		MAP2::embedOrbit(VERTEX, dV, vEmb) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
172
	}
173 174

	return dV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
175 176 177 178 179 180 181 182 183
}

template <typename MAP2>
bool EmbeddedMap2<MAP2>::flipEdge(Dart d)
{
	if(MAP2::flipEdge(d))
	{
		Dart e = MAP2::phi2(d) ;

184
		if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
185
		{
186 187
			MAP2::copyDartEmbedding(VERTEX, d, MAP2::phi1(e)) ;
			MAP2::copyDartEmbedding(VERTEX, e, MAP2::phi1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
188
		}
189
		if (MAP2::isOrbitEmbedded(FACE))
Pierre Kraemer's avatar
Pierre Kraemer committed
190
		{
191 192
			MAP2::copyDartEmbedding(FACE, MAP2::phi_1(d), d) ;
			MAP2::copyDartEmbedding(FACE, MAP2::phi_1(e), e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
193 194 195 196 197 198 199 200 201 202 203 204 205
		}
		return true ;
	}
	return false ;
}

template <typename MAP2>
bool EmbeddedMap2<MAP2>::flipBackEdge(Dart d)
{
	if(MAP2::flipBackEdge(d))
	{
		Dart e = MAP2::phi2(d) ;

206
		if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
207
		{
208 209
			MAP2::copyDartEmbedding(VERTEX, d, MAP2::phi1(e)) ;
			MAP2::copyDartEmbedding(VERTEX, e, MAP2::phi1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
210
		}
211
		if (MAP2::isOrbitEmbedded(FACE))
Pierre Kraemer's avatar
Pierre Kraemer committed
212
		{
213 214
			MAP2::copyDartEmbedding(FACE, MAP2::phi1(d), d) ;
			MAP2::copyDartEmbedding(FACE, MAP2::phi1(e), e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
215 216 217 218 219 220 221 222 223 224 225
		}
		return true ;
	}
	return false ;
}

template <typename MAP2>
void EmbeddedMap2<MAP2>::sewFaces(Dart d, Dart e)
{
	unsigned int vEmb1 = EMBNULL ;
	unsigned int vEmb2 = EMBNULL ;
226
	if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
227
	{
228 229
		vEmb1 = MAP2::getEmbedding(VERTEX, d) ;
		vEmb2 = MAP2::getEmbedding(VERTEX, MAP2::phi1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
230 231 232 233
	}

	MAP2::sewFaces(d, e) ;

234
	if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
235
	{
236 237
		MAP2::embedOrbit(VERTEX, d, vEmb1) ;
		MAP2::embedOrbit(VERTEX, e, vEmb2) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
238 239
	}

240
	if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
241
	{
242
		MAP2::copyDartEmbedding(EDGE, e, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
243 244 245 246 247 248
	}
}

template <typename MAP2>
void EmbeddedMap2<MAP2>::unsewFaces(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
249 250
	bool boundaryD = false ;
	bool boundaryE = false ;
251
	if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
252
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
253
		if(MAP2::isBoundaryVertex(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
254 255 256
			boundaryD = true ;
		if(MAP2::isBoundaryVertex(MAP2::phi1(d)))
			boundaryE = true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
257 258 259 260 261
	}

	Dart e = MAP2::phi2(d) ;
	MAP2::unsewFaces(d) ;

262
	if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
263
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
264
		if(boundaryD)
Pierre Kraemer's avatar
Pierre Kraemer committed
265
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
266 267
			if(e != d)
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
268
				Dart ee = MAP2::phi1(e) ;
269 270
				MAP2::embedNewCell(VERTEX, ee) ;
				MAP2::copyCell(VERTEX, ee, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
271
			}
Pierre Kraemer's avatar
Pierre Kraemer committed
272 273
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
274
		if(boundaryE)
Pierre Kraemer's avatar
Pierre Kraemer committed
275 276 277
		{
			if(e != d)
			{
278 279
				MAP2::embedNewCell(VERTEX, e) ;
				MAP2::copyCell(VERTEX, e, MAP2::phi1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
280 281 282
			}
		}
	}
283
	if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
284
	{
285 286
		MAP2::embedNewCell(EDGE, e) ;
		MAP2::copyCell(EDGE, e, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
287 288 289 290 291 292 293 294 295 296
	}
}

template <typename MAP2>
bool EmbeddedMap2<MAP2>::collapseDegeneratedFace(Dart d)
{
	Dart e = MAP2::phi2(d) ;

	if(MAP2::collapseDegeneratedFace(d))
	{
297
		if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
298
		{
299
			MAP2::copyDartEmbedding(EDGE, MAP2::phi2(e), e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
300 301 302 303 304 305 306 307 308 309 310
		}
		return true ;
	}
	return false ;
}

template <typename MAP2>
void EmbeddedMap2<MAP2>::splitFace(Dart d, Dart e)
{
	MAP2::splitFace(d, e) ;

311
	if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
312
	{
313 314
		MAP2::copyDartEmbedding(VERTEX, MAP2::phi_1(e), d) ;
		MAP2::copyDartEmbedding(VERTEX, MAP2::phi_1(d), e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
315
	}
316
	if (MAP2::isOrbitEmbedded(FACE))
Pierre Kraemer's avatar
Pierre Kraemer committed
317
	{
318 319
		MAP2::embedNewCell(FACE, e) ;
		MAP2::copyCell(FACE, e, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
320 321 322
	}
}

Thomas's avatar
Thomas committed
323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341
template <typename MAP2>
void EmbeddedMap2<MAP2>::linkVertices(Dart d, Dart e)
{
	Dart dNext = MAP2::phi1(d) ;

	MAP2::linkVertices(d,e);

	if (MAP2::isOrbitEmbedded(VERTEX))
	{
		MAP2::copyDartEmbedding(VERTEX, MAP2::phi_1(e), d) ;
		MAP2::copyDartEmbedding(VERTEX, MAP2::phi_1(d), e) ;
	}

	if (MAP2::isOrbitEmbedded(FACE))
	{
		MAP2::embedOrbit(FACE, dNext, MAP2::getEmbedding(FACE, dNext)) ;
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
342 343 344 345 346 347 348
template <typename MAP2>
bool EmbeddedMap2<MAP2>::mergeFaces(Dart d)
{
	Dart dNext = MAP2::phi1(d) ;

	if(MAP2::mergeFaces(d))
	{
349
		if (MAP2::isOrbitEmbedded(FACE))
Pierre Kraemer's avatar
Pierre Kraemer committed
350
		{
351
			MAP2::embedOrbit(FACE, dNext, MAP2::getEmbedding(FACE, dNext)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368
		}
		return true ;
	}
	return false ;
}

template <typename MAP2>
bool EmbeddedMap2<MAP2>::mergeVolumes(Dart d, Dart e)
{
	std::vector<Dart> darts ;
	std::vector<unsigned int> vEmb ;
	std::vector<unsigned int> eEmb ;
	Dart fit = d ;
	do
	{
		darts.push_back(MAP2::phi2(fit)) ;

369
		if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
370
		{
371
			vEmb.push_back(MAP2::getEmbedding(VERTEX, MAP2::phi2(fit))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
372 373
		}

374
		if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
375
		{
376
			eEmb.push_back(MAP2::getEmbedding(EDGE, fit)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
377 378 379 380 381 382 383 384 385
		}

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

	if(MAP2::mergeVolumes(d, e))
	{
		for(unsigned int i = 0; i < darts.size(); ++i)
		{
386
			if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
387
			{
388
				MAP2::embedOrbit(VERTEX, darts[i], vEmb[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
389 390
			}

391
			if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
392
			{
393
				MAP2::embedOrbit(EDGE, darts[i], eEmb[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
394 395 396 397 398 399 400
			}
		}
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
401 402 403 404 405 406 407 408
template <typename MAP2>
unsigned int EmbeddedMap2<MAP2>::closeHole(Dart d)
{
	unsigned int nbE = MAP2::closeHole(d) ;
	Dart dd = MAP2::phi2(d) ;
	Dart f = dd ;
	do
	{
409
		if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
410
		{
411
			MAP2::copyDartEmbedding(VERTEX, f, MAP2::alpha1(f)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
412
		}
413
		if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
414
		{
415
			MAP2::copyDartEmbedding(EDGE, f, MAP2::phi2(f)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
416 417 418 419 420 421
		}
		f = MAP2::phi1(f) ;
	} while(dd != f) ;
	return nbE ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
422 423 424 425 426 427
template <typename MAP2>
bool EmbeddedMap2<MAP2>::check()
{
	bool topo = MAP2::check() ;
	if (!topo)
		return false ;
428

429
	CGoGNout << "Check: embedding begin" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
430 431
	for(Dart d = MAP2::begin(); d != MAP2::end(); MAP2::next(d))
	{
432
		if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
433
		{
434
			if (MAP2::getEmbedding(VERTEX, d) != MAP2::getEmbedding(VERTEX, MAP2::alpha1(d)))
Pierre Kraemer's avatar
Pierre Kraemer committed
435
			{
436
				CGoGNout << "Check: different embeddings on vertex" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
437 438 439 440
				return false ;
			}
		}

441
		if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
442
		{
443
			if (MAP2::getEmbedding(EDGE, d) != MAP2::getEmbedding(EDGE, MAP2::phi2(d)))
Pierre Kraemer's avatar
Pierre Kraemer committed
444
			{
445
				CGoGNout << "Check: different embeddings on edge" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
446 447 448 449
				return false ;
			}
		}

450
		if (MAP2::isOrbitEmbedded(FACE))
Pierre Kraemer's avatar
Pierre Kraemer committed
451
		{
452
			if (MAP2::getEmbedding(FACE, d) != MAP2::getEmbedding(FACE, MAP2::phi1(d)))
Pierre Kraemer's avatar
Pierre Kraemer committed
453
		{
454
				CGoGNout << "Check: different embeddings on face" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
455 456 457 458
				return false ;
			}
		}
	}
459
	CGoGNout << "Check: embedding ok" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
460 461 462 463
	return true ;
}

} // namespace CGoGN