map2MR_PrimalAdapt.hpp 18.9 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-2012, 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.unistra.fr/                                           *
Pierre Kraemer's avatar
Pierre Kraemer committed
21 22 23 24
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

untereiner's avatar
untereiner committed
25
#include "Algo/Multiresolution/Map2MR/map2MR_PrimalAdapt.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
26 27 28 29

namespace CGoGN
{

30 31 32
namespace Algo
{

33 34 35
namespace Surface
{

36 37 38 39 40 41 42 43 44 45 46 47
namespace MR
{

namespace Primal
{

namespace Adaptive
{

template <typename PFP>
Map2MR<PFP>::Map2MR(typename PFP::MAP& map) :
	m_map(map),
48 49 50 51
	shareVertexEmbeddings(true),
	vertexVertexFunctor(NULL),
	edgeVertexFunctor(NULL),
	faceVertexFunctor(NULL)
Pierre Kraemer's avatar
Pierre Kraemer committed
52
{
53

Pierre Kraemer's avatar
Pierre Kraemer committed
54 55 56 57 58
}

/***************************************************
 *               CELLS INFORMATION                 *
 ***************************************************/
59 60
template <typename PFP>
unsigned int Map2MR<PFP>::edgeLevel(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
61
{
62
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"edgeLevel : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
63

64 65
	unsigned int ld = m_map.getDartLevel(d) ;
	unsigned int ldd = m_map.getDartLevel(m_map.phi2(d)) ;	// the level of an edge is the maximum of the
Pierre Kraemer's avatar
Pierre Kraemer committed
66 67 68
	return ld > ldd ? ld : ldd ;				// insertion levels of its two darts
}

69 70
template <typename PFP>
unsigned int Map2MR<PFP>::faceLevel(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
71
{
72
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"faceLevel : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
73

74
	if(m_map.getCurrentLevel() == 0)
Pierre Kraemer's avatar
Pierre Kraemer committed
75 76 77
		return 0 ;

	Dart it = d ;
78 79 80
	unsigned int min1 = m_map.getDartLevel(it) ;		// the level of a face is the second minimum of the
	it = m_map.phi1(it) ;
	unsigned int min2 = m_map.getDartLevel(it) ;		// insertion levels of its darts
Pierre Kraemer's avatar
Pierre Kraemer committed
81 82 83 84 85 86 87 88

	if(min2 < min1)
	{
		unsigned int tmp = min1 ;
		min1 = min2 ;
		min2 = tmp ;
	}

89
	it = m_map.phi1(it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
90 91
	while(it != d)
	{
92
		unsigned int dl = m_map.getDartLevel(it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
93 94 95 96 97 98 99 100 101 102
		if(dl < min2)
		{
			if(dl < min1)
			{
				min2 = min1 ;
				min1 = dl ;
			}
			else
				min2 = dl ;
		}
103
		it = m_map.phi1(it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
104 105 106 107 108
	}

	return min2 ;
}

109 110
template <typename PFP>
Dart Map2MR<PFP>::faceOrigin(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
111
{
112
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"faceOrigin : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
113

114
	m_map.pushLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
115
	Dart p = d ;
116
	unsigned int pLevel = m_map.getDartLevel(p) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
117 118
	while(pLevel > 0)
	{
119 120 121
		p = m_map.faceOldestDart(p) ;
		pLevel = m_map.getDartLevel(p) ;
		m_map.setCurrentLevel(pLevel) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
122
	}
123
	m_map.popLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
124 125 126
	return p ;
}

127 128
template <typename PFP>
Dart Map2MR<PFP>::faceOldestDart(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
129
{
130
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"faceOldestDart : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
131 132 133

	Dart it = d ;
	Dart oldest = it ;
134
	unsigned int l_old = m_map.getDartLevel(oldest) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
135 136
	do
	{
137
		unsigned int l = m_map.getDartLevel(it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
138 139 140 141 142 143 144
		if(l == 0)
			return it ;
		if(l < l_old)
		{
			oldest = it ;
			l_old = l ;
		}
145
		it = m_map.phi1(it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
146 147 148 149
	} while(it != d) ;
	return oldest ;
}

150 151
template <typename PFP>
bool Map2MR<PFP>::edgeIsSubdivided(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
152
{
153
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"edgeIsSubdivided : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
154

155
	if(m_map.getCurrentLevel() == m_map.getMaxLevel())
Pierre Kraemer's avatar
Pierre Kraemer committed
156 157
		return false ;

158 159 160 161
	Dart d2 = m_map.phi2(d) ;
	m_map.incCurrentLevel() ;
	Dart d2_l = m_map.phi2(d) ;
	m_map.decCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
162 163 164 165 166 167
	if(d2 != d2_l)
		return true ;
	else
		return false ;
}

168 169
template <typename PFP>
bool Map2MR<PFP>::edgeCanBeCoarsened(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
170
{
171
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"edgeCanBeCoarsened : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
172 173 174 175 176 177

	if(edgeIsSubdivided(d))
	{
		bool subdOnce = true ;
		bool degree2 = false ;

178 179 180
		Dart d2 = m_map.phi2(d) ;
		m_map.incCurrentLevel() ;
		if(m_map.vertexDegree(m_map.phi1(d)) == 2)
Pierre Kraemer's avatar
Pierre Kraemer committed
181 182 183 184 185
		{
			degree2 = true ;
			if(edgeIsSubdivided(d) || edgeIsSubdivided(d2))
				subdOnce = false ;
		}
186
		m_map.decCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
187 188 189 190 191 192 193

		return degree2 && subdOnce ;
	}

	return false ;
}

194 195
template <typename PFP>
bool Map2MR<PFP>::faceIsSubdivided(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
196
{
197
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"faceIsSubdivided : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
198

199
	if(m_map.getCurrentLevel() == m_map.getMaxLevel())
Pierre Kraemer's avatar
Pierre Kraemer committed
200 201 202
		return false ;

	unsigned int fLevel = faceLevel(d) ;
203
	if(fLevel < m_map.getCurrentLevel())	// a face whose level in the current level map is lower than
Pierre Kraemer's avatar
Pierre Kraemer committed
204 205 206
		return false ;				// the current level can not be subdivided to higher levels

	bool subd = false ;
207 208
	m_map.incCurrentLevel() ;
	if(m_map.getDartLevel(m_map.phi1(m_map.phi1(d))) == m_map.getCurrentLevel())
Pierre Kraemer's avatar
Pierre Kraemer committed
209
		subd = true ;
210
	m_map.decCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
211 212 213
	return subd ;
}

214 215
template <typename PFP>
bool Map2MR<PFP>::faceIsSubdividedOnce(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
216
{
217
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"faceIsSubdividedOnce : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
218

219
	if(m_map.getCurrentLevel() == m_map.getMaxLevel())
Pierre Kraemer's avatar
Pierre Kraemer committed
220 221 222
		return false ;

	unsigned int fLevel = faceLevel(d) ;
223
	if(fLevel < m_map.getCurrentLevel())	// a face whose level in the current level map is lower than
Pierre Kraemer's avatar
Pierre Kraemer committed
224 225 226 227 228 229
		return false ;				// the current level can not be subdivided to higher levels

	unsigned int degree = 0 ;
	bool subd = false ;
	bool subdOnce = true ;

230 231
	m_map.incCurrentLevel() ;
	if(m_map.getDartLevel(m_map.phi1(m_map.phi1(d))) == m_map.getCurrentLevel())
Pierre Kraemer's avatar
Pierre Kraemer committed
232
		subd = true ;
233
	m_map.decCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
234 235 236

	if(subd)
	{
237
		m_map.incCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
238

239
		if(m_map.getCurrentLevel() == m_map.getMaxLevel())
Pierre Kraemer's avatar
Pierre Kraemer committed
240
		{
241
			m_map.decCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
242 243 244 245 246 247
			return true ;
		}

		Dart fit = d ;
		do
		{
248 249
			m_map.incCurrentLevel() ;
			if(m_map.getDartLevel(m_map.phi1(m_map.phi1(fit))) == m_map.getCurrentLevel())
Pierre Kraemer's avatar
Pierre Kraemer committed
250
				subdOnce = false ;
251
				m_map.decCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
252
			++degree ;
253
			fit = m_map.phi1(fit) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
254 255 256 257
		} while(subdOnce && fit != d) ;

		if(degree == 3 && subdOnce)
		{
258 259 260
			Dart cf = m_map.phi2(m_map.phi1(d)) ;
			m_map.incCurrentLevel() ;
			if(m_map.getDartLevel(m_map.phi1(m_map.phi1(cf))) == m_map.getCurrentLevel())
Pierre Kraemer's avatar
Pierre Kraemer committed
261
				subdOnce = false ;
262
			m_map.decCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
263 264
		}

265
		m_map.decCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
266 267 268 269 270 271 272

		return subdOnce ;
	}

	return false ;
}

273
/***************************************************
274
 *               SUBDIVISION                       *
275 276
 ***************************************************/

277
template <typename PFP>
278
Dart Map2MR<PFP>::cutEdge(Dart d)
279
{
280
	Dart dd = m_map.phi2(d) ;
untereiner's avatar
untereiner committed
281 282
	Dart d11 = m_map.phi1(d);
	Dart dd11 = m_map.phi1(dd);
283

284 285
	m_map.duplicateDart(d);
	m_map.duplicateDart(dd);
untereiner's avatar
untereiner committed
286 287
	m_map.duplicateDart(d11);
	m_map.duplicateDart(dd11);
288

289
	Dart nd = m_map.cutEdge(d) ;
290

untereiner's avatar
untereiner committed
291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
	Dart d1 = m_map.phi1(d);
	Dart dd1 = m_map.phi1(dd);

	m_map.propagateDartRelation(d, m_map.m_phi1) ;
	m_map.propagateDartRelation(d, m_map.m_phi2) ;

	m_map.propagateDartRelation(dd, m_map.m_phi1) ;
	m_map.propagateDartRelation(dd, m_map.m_phi2) ;

	m_map.propagateDartRelation(d1, m_map.m_phi1) ;
	m_map.propagateDartRelation(d1, m_map.m_phi_1) ;
	m_map.propagateDartRelation(d1, m_map.m_phi2) ;

	m_map.propagateDartRelation(dd1, m_map.m_phi1) ;
	m_map.propagateDartRelation(dd1, m_map.m_phi_1) ;
	m_map.propagateDartRelation(dd1, m_map.m_phi2) ;

	m_map.propagateDartRelation(d11, m_map.m_phi_1) ;
	m_map.propagateDartRelation(dd11, m_map.m_phi_1) ;

311
	return nd ;
312 313
}

314
template <typename PFP>
315
void Map2MR<PFP>::splitFace(Dart d, Dart e)
316
{
317 318
	Dart dprev = m_map.phi_1(d) ;
	Dart eprev = m_map.phi_1(e) ;
319

320 321 322 323
	m_map.duplicateDart(d);
	m_map.duplicateDart(e);
	m_map.duplicateDart(dprev);
	m_map.duplicateDart(eprev);
324

325
	m_map.splitFace(d, e) ;
untereiner's avatar
untereiner committed
326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
	Dart dd = m_map.phi1(dprev) ;
	Dart ee = m_map.phi1(eprev) ;

	m_map.propagateDartRelation(dd, d, dprev, m_map.m_phi_1, m_map.m_phi1) ;
	m_map.propagateDartRelation(ee, e, eprev, m_map.m_phi_1, m_map.m_phi1) ;

	m_map.propagateDartRelation(dd, m_map.m_phi1) ;
//	//m_map.propagateDartRelation(dd, m_map.m_phi_1) ;
	m_map.propagateDartRelation(dd, m_map.m_phi2) ;

	m_map.propagateDartRelation(ee, m_map.m_phi1) ;
//	//m_map.propagateDartRelation(ee, m_map.m_phi_1) ;
	m_map.propagateDartRelation(ee, m_map.m_phi2) ;

	m_map.propagateDartRelation(dprev, d, m_map.m_phi1) ;
	m_map.propagateDartRelation(eprev, e, m_map.m_phi1) ;
//	//m_map.propagateDartRelation(dprev, m_map.m_phi1) ;
//	//m_map.propagateDartRelation(eprev, m_map.m_phi1) ;

	m_map.propagateDartRelation(d, m_map.m_phi_1) ;
	m_map.propagateDartRelation(e, m_map.m_phi_1) ;

	m_map.template propagateDartEmbedding<VERTEX>(dd) ;
	m_map.template propagateDartEmbedding<VERTEX>(ee) ;

351 352
}

353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373
template <typename PFP>
void Map2MR<PFP>::flipBackEdge(Dart d)
{
	Dart dprev = m_map.phi_1(d) ;
	Dart dnext = m_map.phi_1(d) ;

	Dart d2 = m_map.phi2(d);
	Dart d2prev = m_map.phi_1(d2) ;
	Dart d2next = m_map.phi_1(d2) ;

	m_map.duplicateDart(d);
	m_map.duplicateDart(dprev);
	m_map.duplicateDart(dnext);

	m_map.duplicateDart(d2);
	m_map.duplicateDart(d2prev);
	m_map.duplicateDart(d2next);

	m_map.flipBackEdge(d) ;
}

374 375
template <typename PFP>
void Map2MR<PFP>::subdivideEdge(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
376
{
377
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"subdivideEdge : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
378 379
	assert(!edgeIsSubdivided(d) || !"Trying to subdivide an already subdivided edge") ;

380
	assert(m_map.getCurrentLevel() == edgeLevel(d) || !"Trying to subdivide an edge on a bad current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
381

382
	m_map.incCurrentLevel() ;
383

384 385
	//Dart nd = cutEdge(d) ;
	Dart nd = m_map.cutEdge(d);
386

387
	(*edgeVertexFunctor)(nd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
388

389
	m_map.decCurrentLevel() ;
390 391
}

392 393
template <typename PFP>
void Map2MR<PFP>::coarsenEdge(Dart d)
394
{
395
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"coarsenEdge : called with a dart inserted after current level") ;
396 397
	assert(edgeCanBeCoarsened(d) || !"Trying to coarsen an edge that can not be coarsened") ;

398 399 400
	m_map.incCurrentLevel() ;
	m_map.uncutEdge(d) ;
	m_map.decCurrentLevel() ;
401

402 403 404
	unsigned int maxL = m_map.getMaxLevel() ;
	if(m_map.getCurrentLevel() == maxL - 1 && m_map.getNbInsertedDarts(maxL) == 0)
		m_map.removeLevelBack() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
405 406
}

407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491
//template <typename PFP>
//unsigned int Map2MR<PFP>::subdivideFace(Dart d, bool triQuad, bool OneLevelDifference)
//{
//	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"subdivideFace : called with a dart inserted after current level") ;
//	assert(!faceIsSubdivided(d) || !"Trying to subdivide an already subdivided face") ;

//	unsigned int fLevel = faceLevel(d) ;
//	Dart old = faceOldestDart(d) ;

//	m_map.pushLevel() ;
//	m_map.setCurrentLevel(fLevel) ;		// go to the level of the face to subdivide its edges

//	if(m_map.getCurrentLevel() == m_map.getMaxLevel())
//		m_map.addLevelBack();

//	unsigned int degree = 0 ;
//	Dart it = old ;
//	do
//	{
//		++degree ;						// compute the degree of the face

//		if(OneLevelDifference)
//		{
//			Dart nf = m_map.phi2(it) ;
//			if(faceLevel(nf) == fLevel - 1)	// check if neighboring faces have to be subdivided first
//				subdivideFace(nf,triQuad) ;
//		}

//		if(!edgeIsSubdivided(it))
//			subdivideEdge(it) ;			// and cut the edges (if they are not already)
//		it = m_map.phi1(it) ;
//	} while(it != old) ;

//	m_map.setCurrentLevel(fLevel + 1) ;	// go to the next level to perform face subdivision

//	if(triQuad && degree == 3)					// if subdividing a triangle
//	{
//		Dart dd = m_map.phi1(old) ;
//		Dart e = m_map.phi1(dd) ;
//		(*vertexVertexFunctor)(e) ;
//		e = m_map.phi1(e) ;
//		splitFace(dd, e) ;

//		dd = e ;
//		e = m_map.phi1(dd) ;
//		(*vertexVertexFunctor)(e) ;
//		e = m_map.phi1(e) ;
//		splitFace(dd, e) ;

//		dd = e ;
//		e = m_map.phi1(dd) ;
//		(*vertexVertexFunctor)(e) ;
//		e = m_map.phi1(e) ;
//		splitFace(dd, e) ;
//	}
//	else							// if subdividing a polygonal face
//	{
//		Dart dd = m_map.phi1(old) ;
//		Dart next = m_map.phi1(dd) ;
//		(*vertexVertexFunctor)(next) ;
//		next = m_map.phi1(next) ;
//		splitFace(dd, next) ;			// insert a first edge
//		Dart ne = m_map.phi2(m_map.phi_1(dd)) ;

//		cutEdge(ne) ;					// cut the new edge to insert the central vertex

//		dd = m_map.phi1(next) ;
//		(*vertexVertexFunctor)(dd) ;
//		dd = m_map.phi1(dd) ;
//		while(dd != ne)					// turn around the face and insert new edges
//		{								// linked to the central vertex
//			splitFace(m_map.phi1(ne), dd) ;
//			dd = m_map.phi1(dd) ;
//			(*vertexVertexFunctor)(dd) ;
//			dd = m_map.phi1(dd) ;
//		}

//		(*faceVertexFunctor)(m_map.phi1(ne)) ;
//	}

//	m_map.popLevel() ;

//	return fLevel ;
//}

492
template <typename PFP>
493
unsigned int Map2MR<PFP>::subdivideFace(Dart d, bool triQuad, bool OneLevelDifference)
Pierre Kraemer's avatar
Pierre Kraemer committed
494
{
495
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"subdivideFace : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
496 497 498 499 500
	assert(!faceIsSubdivided(d) || !"Trying to subdivide an already subdivided face") ;

	unsigned int fLevel = faceLevel(d) ;
	Dart old = faceOldestDart(d) ;

501 502
	m_map.pushLevel() ;
	m_map.setCurrentLevel(fLevel) ;		// go to the level of the face to subdivide its edges
Pierre Kraemer's avatar
Pierre Kraemer committed
503

Pierre Kraemer's avatar
Pierre Kraemer committed
504
	unsigned int degree = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
505 506 507
	Dart it = old ;
	do
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
508
		++degree ;						// compute the degree of the face
509 510 511 512 513

		if(OneLevelDifference)
		{
			Dart nf = m_map.phi2(it) ;
			if(faceLevel(nf) == fLevel - 1)	// check if neighboring faces have to be subdivided first
untereiner's avatar
untereiner committed
514
				subdivideFace(nf,triQuad) ;
515 516
		}

517
		if(!edgeIsSubdivided(it))
Pierre Kraemer's avatar
Pierre Kraemer committed
518
			subdivideEdge(it) ;			// and cut the edges (if they are not already)
519
		it = m_map.phi1(it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
520 521
	} while(it != old) ;

522
	m_map.setCurrentLevel(fLevel + 1) ;	// go to the next level to perform face subdivision
Pierre Kraemer's avatar
Pierre Kraemer committed
523

524
	if(triQuad && degree == 3)					// if subdividing a triangle
Pierre Kraemer's avatar
Pierre Kraemer committed
525
	{
526 527
		Dart dd = m_map.phi1(old) ;
		Dart e = m_map.phi1(dd) ;
528
		(*vertexVertexFunctor)(e) ;
529
		e = m_map.phi1(e) ;
530 531
		//splitFace(dd, e) ;
		m_map.splitFace(dd, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
532 533

		dd = e ;
534
		e = m_map.phi1(dd) ;
535
		(*vertexVertexFunctor)(e) ;
536
		e = m_map.phi1(e) ;
537 538
		//splitFace(dd, e) ;
		m_map.splitFace(dd, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
539 540

		dd = e ;
541
		e = m_map.phi1(dd) ;
542
		(*vertexVertexFunctor)(e) ;
543
		e = m_map.phi1(e) ;
544 545
		//splitFace(dd, e) ;
		m_map.splitFace(dd, e) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
546 547 548
	}
	else							// if subdividing a polygonal face
	{
549
		std::cout << "wrong" << std::endl;
550 551
		Dart dd = m_map.phi1(old) ;
		Dart next = m_map.phi1(dd) ;
552
		(*vertexVertexFunctor)(next) ;
553
		next = m_map.phi1(next) ;
554
		splitFace(dd, next) ;			// insert a first edge
untereiner's avatar
untereiner committed
555
		Dart ne = m_map.phi2(m_map.phi_1(dd)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
556 557 558

		cutEdge(ne) ;					// cut the new edge to insert the central vertex

559
		dd = m_map.phi1(next) ;
560
		(*vertexVertexFunctor)(dd) ;
561
		dd = m_map.phi1(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
562 563
		while(dd != ne)					// turn around the face and insert new edges
		{								// linked to the central vertex
564 565
			splitFace(m_map.phi1(ne), dd) ;
			dd = m_map.phi1(dd) ;
566
			(*vertexVertexFunctor)(dd) ;
567
			dd = m_map.phi1(dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
568
		}
569

570
		(*faceVertexFunctor)(m_map.phi1(ne)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
571 572
	}

573 574 575 576 577
	m_map.popLevel() ;

	return fLevel ;
}

untereiner's avatar
untereiner committed
578

579 580
template <typename PFP>
void Map2MR<PFP>::coarsenFace(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
581
{
582
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"coarsenFace : called with a dart inserted after current level") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
583 584 585 586 587 588 589
	assert(faceIsSubdividedOnce(d) || !"Trying to coarsen a non-subdivided face or a more than once subdivided face") ;

	unsigned int degree = 0 ;
	Dart fit = d ;
	do
	{
		++degree ;
590
		fit = m_map.phi1(fit) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
591 592 593 594 595 596 597
	} while(fit != d) ;

	if(degree == 3)
	{
		fit = d ;
		do
		{
598 599 600 601 602 603
			m_map.incCurrentLevel() ;
			Dart innerEdge = m_map.phi1(fit) ;
			m_map.setCurrentLevel(m_map.getMaxLevel()) ;
			m_map.mergeFaces(innerEdge) ;
			m_map.decCurrentLevel() ;
			fit = m_map.phi1(fit) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
604 605 606 607
		} while(fit != d) ;
	}
	else
	{
608 609 610 611 612
		m_map.incCurrentLevel() ;
		Dart centralV = m_map.phi1(m_map.phi1(d)) ;
		m_map.setCurrentLevel(m_map.getMaxLevel()) ;
		m_map.deleteVertex(centralV) ;
		m_map.decCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
613 614 615 616 617 618 619
	}

	fit = d ;
	do
	{
		if(edgeCanBeCoarsened(fit))
			coarsenEdge(fit) ;
620
		fit = m_map.phi1(fit) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
621
	} while(fit != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
622

623 624 625
	unsigned int maxL = m_map.getMaxLevel() ;
	if(m_map.getCurrentLevel() == maxL - 1 && m_map.getNbInsertedDarts(maxL) == 0)
		m_map.removeLevelBack() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
626 627
}

628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697
template <typename PFP>
unsigned int Map2MR<PFP>::subdivideFaceSqrt3(Dart d)
{
	assert(m_map.getDartLevel(d) <= m_map.getCurrentLevel() || !"subdivideFace : called with a dart inserted after current level") ;
	//assert(!faceIsSubdivided(d) || !"Trying to subdivide an already subdivided face") ;

	unsigned int fLevel = faceLevel(d) ;
	Dart old = faceOldestDart(d) ;

	m_map.pushLevel() ;
	m_map.setCurrentLevel(fLevel) ;		// go to the level of the face to subdivide its edges

	if(m_map.getCurrentLevel() == m_map.getMaxLevel())
		m_map.addLevelBack();

	m_map.setCurrentLevel(fLevel + 1) ;	// go to the next level to perform face subdivision

	//if it is an even level (triadic refinement) and a boundary face
	if((m_map.getCurrentLevel()%2 == 0) && m_map.isBoundaryFace(d))
	{
//		//find the boundary edge
//		Dart df = m_map.findBoundaryEdgeOfFace(d);
//		//trisection of the boundary edge
//		cutEdge(df) ;
//		splitFace(m_map.phi2(df), m_map.phi1(m_map.phi1(m_map.phi2(df)))) ;
//		(*vertexVertexFunctor)(m_map.phi1(df) ;
//
//		df = m_map.phi1(df);
//		cutEdge(df) ;
//		splitFace(m_map.phi2(df), m_map.phi1(m_map.phi1(m_map.phi2(df)))) ;
//		//(*vertexVertexFunctor)(m_map.phi1(df)) ;
	}
	else
	{
		Dart d1 = m_map.phi1(old);
		(*vertexVertexFunctor)(old) ;
		splitFace(old, d1) ;
		(*vertexVertexFunctor)(d1) ;
		cutEdge(m_map.phi_1(old)) ;
		Dart x = m_map.phi2(m_map.phi_1(old)) ;
		Dart dd = m_map.phi1(m_map.phi1(m_map.phi1((x))));
		while(dd != x)
		{
			(*vertexVertexFunctor)(dd) ;
			Dart next = m_map.phi1(dd) ;
			splitFace(dd, m_map.phi1(x)) ;
			dd = next ;
		}

		Dart cd = m_map.phi2(x);
		(*faceVertexFunctor)(cd) ;

		Dart dit = cd;
		do
		{
			Dart dit12 = m_map.phi2(m_map.phi1(dit));

			dit = m_map.phi2(m_map.phi_1(dit));

			if(faceLevel(dit12) == (fLevel + 1)  && !m_map.isBoundaryEdge(dit12))
					flipBackEdge(dit12);
		}
		while(dit != cd);
	}

	m_map.popLevel() ;

	return fLevel ;
}

698 699 700 701 702 703
} // namespace Adaptive

} // namespace Primal

} // namespace MR

704 705
} // namespace Surface

706 707
} // namespace Algo

Pierre Kraemer's avatar
Pierre Kraemer committed
708
} // namespace CGoGN