embeddedMap2.hpp 10.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-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 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 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 79
		MAP2::embedNewCell(EDGE, nd) ;
		MAP2::copyCell(EDGE, nd, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
80
	}
81
	if(MAP2::isOrbitEmbedded(FACE))
Pierre Kraemer's avatar
Pierre Kraemer committed
82
	{
83
		MAP2::copyDartEmbedding(FACE, MAP2::phi1(d), d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
84 85
		Dart e = MAP2::phi2(nd) ;
		if(e != nd)
86
			MAP2::copyDartEmbedding(FACE, MAP2::phi1(e), e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
87 88 89
	}
}

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

	MAP2::uncutEdge(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
96

Pierre Kraemer's avatar
Pierre Kraemer committed
97
	if(doSomethg)
Pierre Kraemer's avatar
Pierre Kraemer committed
98
	{
99 100
		if(MAP2::isOrbitEmbedded(EDGE))
			MAP2::copyDartEmbedding(EDGE, MAP2::phi2(d), d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
101 102 103 104 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
	}
}

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
	{
139
		unsigned int ve = MAP2::getEmbedding(VERTEX, MAP2::phi2(vit1)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
140 141 142 143 144 145 146
		vu1.push_back(ve) ;
		vit1 = MAP2::alpha1(vit1) ;
	} while(vit1 != end) ;
	end = MAP2::phi1(d) ;
	Dart vit2 = MAP2::alpha1(MAP2::alpha1(dd)) ;
	do
	{
147
		unsigned int ve = MAP2::getEmbedding(VERTEX, MAP2::phi2(vit2)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
148 149 150 151 152 153 154 155 156 157
		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>
158
Dart EmbeddedMap2<MAP2>::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
159 160
{
	unsigned int vEmb = EMBNULL ;
161
	if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
162
	{
163
		vEmb = MAP2::getEmbedding(VERTEX, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
164 165
	}

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

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

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

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

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

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

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

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

	MAP2::sewFaces(d, e) ;

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

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

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

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

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

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

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

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

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

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

template <typename MAP2>
bool EmbeddedMap2<MAP2>::mergeFaces(Dart d)
{
	Dart dNext = MAP2::phi1(d) ;

	if(MAP2::mergeFaces(d))
	{
329
		if (MAP2::isOrbitEmbedded(FACE))
330
		{
331
			MAP2::embedOrbit(FACE, dNext, MAP2::getEmbedding(FACE, dNext)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348
		}
		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)) ;

349
		if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
350
		{
351
			vEmb.push_back(MAP2::getEmbedding(VERTEX, MAP2::phi2(fit))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
352 353
		}

354
		if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
355
		{
356
			eEmb.push_back(MAP2::getEmbedding(EDGE, fit)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
357 358 359 360 361 362 363 364 365
		}

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

	if(MAP2::mergeVolumes(d, e))
	{
		for(unsigned int i = 0; i < darts.size(); ++i)
		{
366
			if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
367
			{
368
				MAP2::embedOrbit(VERTEX, darts[i], vEmb[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
369 370
			}

371
			if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
372
			{
373
				MAP2::embedOrbit(EDGE, darts[i], eEmb[i]) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
374 375 376 377 378 379 380
			}
		}
		return true ;
	}
	return false ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
381 382 383 384 385 386 387 388
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
	{
389
		if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
390
		{
391
			MAP2::copyDartEmbedding(VERTEX, f, MAP2::alpha1(f)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
392
		}
393
		if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
394
		{
395
			MAP2::copyDartEmbedding(EDGE, f, MAP2::phi2(f)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
396 397 398 399 400 401
		}
		f = MAP2::phi1(f) ;
	} while(dd != f) ;
	return nbE ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
402 403 404 405 406 407
template <typename MAP2>
bool EmbeddedMap2<MAP2>::check()
{
	bool topo = MAP2::check() ;
	if (!topo)
		return false ;
408

409
	CGoGNout << "Check: embedding begin" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
410 411
	for(Dart d = MAP2::begin(); d != MAP2::end(); MAP2::next(d))
	{
412
		if (MAP2::isOrbitEmbedded(VERTEX))
Pierre Kraemer's avatar
Pierre Kraemer committed
413
		{
414
			if (MAP2::getEmbedding(VERTEX, d) != MAP2::getEmbedding(VERTEX, MAP2::alpha1(d)))
Pierre Kraemer's avatar
Pierre Kraemer committed
415
			{
416
				CGoGNout << "Check: different embeddings on vertex" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
417 418 419 420
				return false ;
			}
		}

421
		if (MAP2::isOrbitEmbedded(EDGE))
Pierre Kraemer's avatar
Pierre Kraemer committed
422
		{
423
			if (MAP2::getEmbedding(EDGE, d) != MAP2::getEmbedding(EDGE, MAP2::phi2(d)))
Pierre Kraemer's avatar
Pierre Kraemer committed
424
			{
425
				CGoGNout << "Check: different embeddings on edge" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
426 427 428 429
				return false ;
			}
		}

430
		if (MAP2::isOrbitEmbedded(FACE))
Pierre Kraemer's avatar
Pierre Kraemer committed
431
		{
432
			if (MAP2::getEmbedding(FACE, d) != MAP2::getEmbedding(FACE, MAP2::phi1(d)))
Pierre Kraemer's avatar
Pierre Kraemer committed
433
		{
434
				CGoGNout << "Check: different embeddings on face" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
435 436 437 438
				return false ;
			}
		}
	}
439
	CGoGNout << "Check: embedding ok" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
440 441 442 443
	return true ;
}

} // namespace CGoGN