embeddedMap2.hpp 10.3 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
* Copyright (C) 2009, IGG Team, LSIIT, University of Strasbourg                *
*                                                                              *
* 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.           *
*                                                                              *
* Web site: https://iggservis.u-strasbg.fr/CGoGN/                              *
* 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 39 40

	MAP2::splitVertex(d, e) ;

	if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
41 42
		MAP2::copyDartEmbedding(VERTEX_ORBIT, MAP2::phi1(dd), d) ;
		MAP2::copyDartEmbedding(VERTEX_ORBIT, MAP2::phi1(ee), e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
43 44 45
		MAP2::embedNewCell(VERTEX_ORBIT, e) ;
		MAP2::copyCell(VERTEX_ORBIT, e, d) ;
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
46 47 48 49 50 51

	if(MAP2::isOrbitEmbedded(FACE_ORBIT))
	{
		MAP2::copyDartEmbedding(FACE_ORBIT, MAP2::phi1(dd), dd) ;
		MAP2::copyDartEmbedding(FACE_ORBIT, MAP2::phi1(ee), ee) ;
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
52 53
}

Pierre Kraemer's avatar
Pierre Kraemer committed
54 55 56 57 58 59 60 61
template <typename MAP2>
bool EmbeddedMap2<MAP2>::deleteVertex(Dart d)
{
	Dart f = MAP2::phi1(d) ;
	if(MAP2::deleteVertex(d))
	{
		if (MAP2::isOrbitEmbedded(FACE_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
62
			MAP2::embedOrbit(FACE_ORBIT, f, MAP2::getEmbedding(FACE_ORBIT, 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) ;

Pierre Kraemer's avatar
Pierre Kraemer committed
76 77
	if (MAP2::isOrbitEmbedded(EDGE_ORBIT))
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
78 79 80 81 82 83 84 85 86
		MAP2::embedNewCell(EDGE_ORBIT, nd) ;
		MAP2::copyCell(EDGE_ORBIT, nd, d) ;
	}
	if(MAP2::isOrbitEmbedded(FACE_ORBIT))
	{
		MAP2::copyDartEmbedding(FACE_ORBIT, MAP2::phi1(d), d) ;
		Dart e = MAP2::phi2(nd) ;
		if(e != nd)
			MAP2::copyDartEmbedding(FACE_ORBIT, MAP2::phi1(e), e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
	}
}

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
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
125
		unsigned int ve = MAP2::getEmbedding(VERTEX_ORBIT, MAP2::phi2(vit1)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
126 127 128 129 130 131 132
		vu1.push_back(ve) ;
		vit1 = MAP2::alpha1(vit1) ;
	} while(vit1 != end) ;
	end = MAP2::phi1(d) ;
	Dart vit2 = MAP2::alpha1(MAP2::alpha1(dd)) ;
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
133
		unsigned int ve = MAP2::getEmbedding(VERTEX_ORBIT, MAP2::phi2(vit2)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
134 135 136 137 138 139 140 141 142 143
		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>
144
Dart EmbeddedMap2<MAP2>::collapseEdge(Dart d, bool delDegenerateFaces)
Pierre Kraemer's avatar
Pierre Kraemer committed
145 146 147 148
{
	unsigned int vEmb = EMBNULL ;
	if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
149
		vEmb = MAP2::getEmbedding(VERTEX_ORBIT, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
150 151
	}

152
	Dart dV = MAP2::collapseEdge(d, delDegenerateFaces);
Pierre Kraemer's avatar
Pierre Kraemer committed
153 154 155

	if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
	{
156
		MAP2::embedOrbit(VERTEX_ORBIT, dV, vEmb) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
157
	}
158 159

	return dV ;
Pierre Kraemer's avatar
Pierre Kraemer committed
160 161 162 163 164 165 166 167 168 169 170
}

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

		if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
171 172
			MAP2::setDartEmbedding(VERTEX_ORBIT, d, MAP2::getEmbedding(VERTEX_ORBIT, MAP2::phi1(e))) ;
			MAP2::setDartEmbedding(VERTEX_ORBIT, e, MAP2::getEmbedding(VERTEX_ORBIT, MAP2::phi1(d))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
173 174 175
		}
		if (MAP2::isOrbitEmbedded(FACE_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
176 177
			MAP2::setDartEmbedding(FACE_ORBIT, MAP2::phi_1(d), MAP2::getEmbedding(FACE_ORBIT, d)) ;
			MAP2::setDartEmbedding(FACE_ORBIT, MAP2::phi_1(e), MAP2::getEmbedding(FACE_ORBIT, e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
178 179 180 181 182 183 184 185 186 187 188 189 190 191 192
		}
		return true ;
	}
	return false ;
}

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

		if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
193 194
			MAP2::setDartEmbedding(VERTEX_ORBIT, d, MAP2::getEmbedding(VERTEX_ORBIT, MAP2::phi1(e))) ;
			MAP2::setDartEmbedding(VERTEX_ORBIT, e, MAP2::getEmbedding(VERTEX_ORBIT, MAP2::phi1(d))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
195 196 197
		}
		if (MAP2::isOrbitEmbedded(FACE_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
198 199
			MAP2::setDartEmbedding(FACE_ORBIT, MAP2::phi1(d), MAP2::getEmbedding(FACE_ORBIT, d)) ;
			MAP2::setDartEmbedding(FACE_ORBIT, MAP2::phi1(e), MAP2::getEmbedding(FACE_ORBIT, e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
200 201 202 203 204 205 206 207 208 209 210 211 212
		}
		return true ;
	}
	return false ;
}

template <typename MAP2>
void EmbeddedMap2<MAP2>::sewFaces(Dart d, Dart e)
{
	unsigned int vEmb1 = EMBNULL ;
	unsigned int vEmb2 = EMBNULL ;
	if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
213 214
		vEmb1 = MAP2::getEmbedding(VERTEX_ORBIT, d) ;
		vEmb2 = MAP2::getEmbedding(VERTEX_ORBIT, MAP2::phi1(d)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
	}

	MAP2::sewFaces(d, e) ;

	if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
	{
		MAP2::embedOrbit(VERTEX_ORBIT, d, vEmb1) ;
		MAP2::embedOrbit(VERTEX_ORBIT, e, vEmb2) ;
	}

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

template <typename MAP2>
void EmbeddedMap2<MAP2>::unsewFaces(Dart d)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
234 235
	bool boundaryD = false ;
	bool boundaryE = false ;
Pierre Kraemer's avatar
Pierre Kraemer committed
236 237
	if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
238
		if(MAP2::isBoundaryVertex(d))
Pierre Kraemer's avatar
Pierre Kraemer committed
239 240 241
			boundaryD = true ;
		if(MAP2::isBoundaryVertex(MAP2::phi1(d)))
			boundaryE = true ;
Pierre Kraemer's avatar
Pierre Kraemer committed
242 243 244 245 246 247 248
	}

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

	if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
249
		if(boundaryD)
Pierre Kraemer's avatar
Pierre Kraemer committed
250
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
251 252
			if(e != d)
			{
Pierre Kraemer's avatar
Pierre Kraemer committed
253 254 255
				Dart ee = MAP2::phi1(e) ;
				MAP2::embedNewCell(VERTEX_ORBIT, ee) ;
				MAP2::copyCell(VERTEX_ORBIT, ee, d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
256
			}
Pierre Kraemer's avatar
Pierre Kraemer committed
257 258
		}

Pierre Kraemer's avatar
Pierre Kraemer committed
259
		if(boundaryE)
Pierre Kraemer's avatar
Pierre Kraemer committed
260 261 262 263 264 265 266 267
		{
			if(e != d)
			{
				MAP2::embedNewCell(VERTEX_ORBIT, e) ;
				MAP2::copyCell(VERTEX_ORBIT, e, MAP2::phi1(d)) ;
			}
		}
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283
	if (MAP2::isOrbitEmbedded(EDGE_ORBIT))
	{
		MAP2::embedNewCell(EDGE_ORBIT, e) ;
		MAP2::copyCell(EDGE_ORBIT, e, d) ;
	}
}

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

	if(MAP2::collapseDegeneratedFace(d))
	{
		if (MAP2::isOrbitEmbedded(EDGE_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
284
			MAP2::setDartEmbedding(EDGE_ORBIT, MAP2::phi2(e), MAP2::getEmbedding(EDGE_ORBIT, e)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
285 286 287 288 289 290 291 292 293 294 295
		}
		return true ;
	}
	return false ;
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
296 297 298 299 300
	if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
	{
		MAP2::setDartEmbedding(VERTEX_ORBIT, MAP2::phi_1(e), MAP2::getEmbedding(VERTEX_ORBIT, d)) ;
		MAP2::setDartEmbedding(VERTEX_ORBIT, MAP2::phi_1(d), MAP2::getEmbedding(VERTEX_ORBIT, e)) ;
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316
	if (MAP2::isOrbitEmbedded(FACE_ORBIT))
	{
		MAP2::embedNewCell(FACE_ORBIT, e) ;
		MAP2::copyCell(FACE_ORBIT, e, d) ;
	}
}

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

	if(MAP2::mergeFaces(d))
	{
		if (MAP2::isOrbitEmbedded(FACE_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
317
			MAP2::embedOrbit(FACE_ORBIT, dNext, MAP2::getEmbedding(VERTEX_ORBIT, dNext)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336
		}
		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)) ;

		if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
337
			vEmb.push_back(MAP2::getEmbedding(VERTEX_ORBIT, MAP2::phi2(fit))) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
338 339 340 341
		}

		if (MAP2::isOrbitEmbedded(EDGE_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
342
			eEmb.push_back(MAP2::getEmbedding(EDGE_ORBIT, fit)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372
		}

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

	if(MAP2::mergeVolumes(d, e))
	{
		for(unsigned int i = 0; i < darts.size(); ++i)
		{
			if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
			{
				MAP2::embedOrbit(VERTEX_ORBIT, darts[i], vEmb[i]) ;
			}

			if (MAP2::isOrbitEmbedded(EDGE_ORBIT))
			{
				MAP2::embedOrbit(EDGE_ORBIT, darts[i], eEmb[i]) ;
			}
		}
		return true ;
	}
	return false ;
}

template <typename MAP2>
bool EmbeddedMap2<MAP2>::check()
{
	bool topo = MAP2::check() ;
	if (!topo)
		return false ;
373

374
	CGoGNout << "Check: embedding begin" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
375 376 377 378
	for(Dart d = MAP2::begin(); d != MAP2::end(); MAP2::next(d))
	{
		if (MAP2::isOrbitEmbedded(VERTEX_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
379
			if (MAP2::getEmbedding(VERTEX_ORBIT, d) != MAP2::getEmbedding(VERTEX_ORBIT, MAP2::alpha1(d)))
Pierre Kraemer's avatar
Pierre Kraemer committed
380
			{
381
				CGoGNout << "Check: different embeddings on vertex" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
382 383 384 385 386 387
				return false ;
			}
		}

		if (MAP2::isOrbitEmbedded(EDGE_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
388
			if (MAP2::getEmbedding(EDGE_ORBIT, d) != MAP2::getEmbedding(EDGE_ORBIT, MAP2::phi2(d)))
Pierre Kraemer's avatar
Pierre Kraemer committed
389
			{
390
				CGoGNout << "Check: different embeddings on edge" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
391 392 393 394 395 396
				return false ;
			}
		}

		if (MAP2::isOrbitEmbedded(FACE_ORBIT))
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
397
			if (MAP2::getEmbedding(FACE_ORBIT, d) != MAP2::getEmbedding(FACE_ORBIT, MAP2::phi1(d)))
Pierre Kraemer's avatar
Pierre Kraemer committed
398
		{
399
				CGoGNout << "Check: different embeddings on face" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
400 401 402 403
				return false ;
			}
		}
	}
404
	CGoGNout << "Check: embedding ok" << CGoGNendl ;
Pierre Kraemer's avatar
Pierre Kraemer committed
405 406 407 408
	return true ;
}

} // namespace CGoGN