Création d'un compte pour un collaborateur extérieur au laboratoire depuis l'intranet ICube : https://intranet.icube.unistra.fr/fr/labs/member/profile

ihm3.cpp 20.2 KB
Newer Older
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           *
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/                                         *
21
22
23
24
25
26
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Algo/ImplicitHierarchicalMesh/ihm3.h"
#include <math.h>
27
#include <limits>
28
29
30
31
32
33
34

namespace CGoGN
{

namespace Algo
{

untereiner's avatar
untereiner committed
35
namespace IHM
36
37
38
39
{

ImplicitHierarchicalMap3::ImplicitHierarchicalMap3() : m_curLevel(0), m_maxLevel(0), m_edgeIdCount(0), m_faceIdCount(0)
{
40
41
42
	m_dartLevel = Map3::addAttribute<unsigned int>(DART, "dartLevel") ;
	m_faceId = Map3::addAttribute<unsigned int>(DART, "faceId") ;
	m_edgeId = Map3::addAttribute<unsigned int>(DART, "edgeId") ;
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

	for(unsigned int i = 0; i < NB_ORBITS; ++i)
		m_nextLevelCell[i] = NULL ;
}

ImplicitHierarchicalMap3::~ImplicitHierarchicalMap3()
{
	Map3::removeAttribute(m_edgeId) ;
	Map3::removeAttribute(m_faceId) ;
	Map3::removeAttribute(m_dartLevel) ;
}

void ImplicitHierarchicalMap3::init()
{
	initEdgeId() ;
	initFaceId();

	for(unsigned int orbit = 0; orbit < NB_ORBITS; ++orbit)
	{
		if(m_nextLevelCell[orbit] != NULL)
		{
64
			AttributeContainer& cellCont = m_attribs[orbit] ;
65
66
67
68
69
70
			for(unsigned int i = cellCont.begin(); i < cellCont.end(); cellCont.next(i))
				m_nextLevelCell[orbit]->operator[](i) = EMBNULL ;
		}
	}
}

untereiner's avatar
untereiner committed
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

Dart ImplicitHierarchicalMap3::beginSplittingPath(Dart d, DartMarker& m)
{
	Dart dres = NIL;
	Dart dit = d;
	bool found = false;

	// Recherche d'un brin de depart du chemin d'arete
	do
	{
		Dart eit = phi1(dit);

		if(!m.isMarked(eit) && getDartLevel(eit) == getCurrentLevel())
		{
			found = true;
			dres = eit;
		}

		dit = phi2(phi_1(dit));
	}
	while(!found && dit != d);

	return dres;
}

void ImplicitHierarchicalMap3::constructSplittingPath(Dart d, std::vector<Dart>& v, DartMarker& m)
{

	//Construction du chemin d'arete
	Dart cit = d;

	v.push_back(cit);
	m.markOrbit(EDGE, cit);

	do
	{

		if(std::min(getDartLevel(phi1(cit)),getDartLevel(phi2(phi1(cit))))  == getDartLevel(d))
		{
			if(m.isMarked(phi1(cit)))
			{
				cit = phi1(phi2(phi1(cit)));
				std::cout << "1_1" << std::endl;
			}
		}
		else if(std::min(getDartLevel(phi1(cit)),getDartLevel(phi2(phi1(cit)))) < getDartLevel(d))
		{
			cit = phi1(phi2(phi1(cit)));
			std::cout << "2" << std::endl;
		}
		else
			cit = phi1(cit);

		v.push_back(cit);
		m.markOrbit(EDGE, cit);


	}
	while(cit != d);

//	do
//	{
//		v.push_back(cit);
//		m.markOrbit(EDGE, cit);
//
//		cit = phi1(cit);
//
//		//std::cout << "cit = " << cit << std::endl;
//
//		if(std::min(getDartLevel(cit), getDartLevel(phi2(cit))) == getDartLevel(d))
//		{
//			if(m.isMarked(cit))
//			{
//				cit = phi1(phi2(cit));
//				//std::cout << "1_1" << std::endl;
//			}
//		}
//		else if(std::min(getDartLevel(cit),getDartLevel(phi2(cit))) < getDartLevel(d))
//		{
//			cit = phi1(phi2(cit));
//			//std::cout << "2" << std::endl;
//		}
//
//	}while(cit != d);

}

158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
//Dart ImplicitHierarchicalMap3::cutEdge(Dart d)
//{
//        Dart resV = EmbeddedMap3::cutEdge(d);
//
//        unsigned int eId = getEdgeId(d);
//        Dart dit = d;
//        do
//        {
//        	//EdgeId
//        	m_edgeId[phi1(dit)] = eId;
//        	m_edgeId[phi3(dit)] = eId;
//
//        	//FaceId
//        	unsigned int fId = getFaceId(dit);
//        	m_faceId[phi1(dit)] = fId;
//        	m_edgeId[phi3(dit)] = fId;
//
//            dit = alpha2(dit);
//        }
//        while(dit != d);
//
//        return resV;
//}
//
//bool ImplicitHierarchicalMap3::uncutEdge(Dart d)
//{
//       return EmbeddedMap3::uncutEdge(d);
//}
//
//void ImplicitHierarchicalMap3::splitFace(Dart d, Dart e)
//{
//        EmbeddedMap3::splitFace(d,e);
//
//        unsigned int eId = getNewEdgeId();
//        unsigned int fId = getFaceId(d);
//
//        Dart ne = phi_1(d);
//        Dart ne3 = phi3(ne);
//
//        m_edgeId[ne] = eId;
//        m_edgeId[phi2(ne)] = eId;
//        m_edgeId[ne3] = eId;
//        m_edgeId[phi2(ne3)] = eId;
//
//        m_faceId[ne] = fId;
//        m_faceId[phi2(ne)] = fId;
//        m_faceId[ne3] = fId;
//        m_faceId[phi2(ne3)] = fId;
//}
//
//void ImplicitHierarchicalMap3::sewVolumes(Dart d, Dart e, bool withBoundary)
//{
//        EmbeddedMap3::sewVolumes(d,e);
//
//        unsigned int fId;
//
//        if(m_faceId[d] < m_faceId[phi3(d)])
//        	fId = m_faceId[d] ;
//        else
//        	fId = m_edgeId[phi3(d)];
//
//        Dart dit = d;
//        do
//        {
//                //EdgeId
////                if(m_edgeId[dit] < m_edgeId[phi3(dit)])
////                	m_edgeId[phi3(dit)] = m_edgeId[dit] ;
////                else
////                	m_edgeId[dit] = m_edgeId[phi3(dit)];
//
//                //FaceId
//                m_faceId[dit] = fId;
//                m_faceId[phi3(dit)] = fId;
//
//                dit = phi1(dit);
//        }
//        while(dit != d);
//}
//
//void ImplicitHierarchicalMap3::splitVolume(std::vector<Dart>& vd)
//{
//        EmbeddedMap3::splitVolume(vd);
//
//        unsigned int fId = getNewFaceId();
//
//        for(std::vector<Dart>::iterator it = vd.begin() ; it != vd.end() ; ++it)
//        {
//                Dart dit = *it;
//
//                //Edge Id
//                m_edgeId[phi2(dit)] = m_edgeId[dit];
//
//                //Face Id
//                m_faceId[phi2(dit)] = fId;
//        }
//}


256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
void ImplicitHierarchicalMap3::initEdgeId()
{
	DartMarker edgeMark(*this) ;
	for(Dart d = Map3::begin(); d != Map3::end(); Map3::next(d))
	{
		if(!edgeMark.isMarked(d))
		{
			Dart e = d;
			do
			{
				m_edgeId[e] = m_edgeIdCount;
				edgeMark.mark(e);

				m_edgeId[Map3::phi2(e)] = m_edgeIdCount ;
				edgeMark.mark(Map3::phi2(e));

				e = Map3::alpha2(e);
			} while(e != d);

			m_edgeIdCount++;
		}
	}
}

void ImplicitHierarchicalMap3::initFaceId()
{
	DartMarker faceMark(*this) ;
	for(Dart d = Map3::begin(); d != Map3::end(); Map3::next(d))
	{
		if(!faceMark.isMarked(d))
		{
			Dart e = d;
			do
			{
				m_faceId[e] = m_faceIdCount ;
				faceMark.mark(e);

293
				Dart e3 = Map3::phi3(e);
294
295
				m_faceId[e3] = m_faceIdCount ;
				faceMark.mark(e3);
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313

				e = Map3::phi1(e);
			} while(e != d);

			m_faceIdCount++;
		}
	}
}

unsigned int ImplicitHierarchicalMap3::faceLevel(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;

	if(m_curLevel == 0)
		return 0 ;

	Dart it = d ;
	Dart old = it ;
314
	unsigned int l_old = m_dartLevel[old] ;
315
316
317
318
	unsigned int fLevel = edgeLevel(it) ;
	do
	{
		it = phi1(it) ;
319
320
321
322
323
324
325
326
		unsigned int dl = m_dartLevel[it] ;
		if(dl < l_old)							// compute the oldest dart of the face
		{										// in the same time
			old = it ;
			l_old = dl ;
		}										// in a first time, the level of a face
		unsigned int l = edgeLevel(it) ;		// is the minimum of the levels
		fLevel = l < fLevel ? l : fLevel ;		// of its edges
327
328
	} while(it != d) ;

untereiner's avatar
ihm3    
untereiner committed
329

330
331
332
333
334
	unsigned int cur = m_curLevel ;
	m_curLevel = fLevel ;

	unsigned int nbSubd = 0 ;
	it = old ;
335
336
337
338
	unsigned int eId = m_edgeId[old] ;			// the particular case of a face
	do											// with all neighboring faces regularly subdivided
	{											// but not the face itself
		++nbSubd ;								// is treated here
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
		it = phi1(it) ;
	} while(m_edgeId[it] == eId) ;

	while(nbSubd > 1)
	{
		nbSubd /= 2 ;
		--fLevel ;
	}

	m_curLevel = cur ;

	return fLevel ;
}

unsigned int ImplicitHierarchicalMap3::volumeLevel(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;

	if(m_curLevel == 0)
		return 0 ;

	//First : the level of a volume is the
	//minimum of the levels of its faces

	DartMarkerStore mark(*this);		// Lock a marker

	std::vector<Dart> visitedFaces;		// Faces that are traversed
366
	visitedFaces.reserve(512);
367
368
369
370
	visitedFaces.push_back(d);			// Start with the face of d
	std::vector<Dart>::iterator face;

	Dart oldest = d ;
371
	unsigned int vLevel = std::numeric_limits<unsigned int>::max() ; //hook de ouf
372
373
374
375

	//parcours les faces du volume au niveau courant
	//on cherche le brin de niveau le plus bas de la hierarchie
	//on note le niveau le plus bas de la hierarchie
376
	mark.markOrbit(FACE, d) ;
untereiner's avatar
untereiner committed
377
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
378
	{
untereiner's avatar
untereiner committed
379
		Dart e = visitedFaces[i] ;
380
381
382
383

		// in a first time, the level of a face
		//the level of the volume is the minimum of the
		//levels of its faces
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
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

		//
		// Compute the level of this face
		// and the oldest dart
		//
		Dart it = e ;
		Dart old = it ;
		unsigned int l_old = m_dartLevel[old] ;
		unsigned int fLevel = edgeLevel(it) ;
		do
		{
			it = phi1(it) ;
			unsigned int dl = m_dartLevel[it] ;
			if(dl < l_old)							// compute the oldest dart of the face
			{										// in the same time
				old = it ;
				l_old = dl ;
			}										// in a first time, the level of a face
			unsigned int l = edgeLevel(it) ;		// is the minimum of the levels
			fLevel = l < fLevel ? l : fLevel ;		// of its edges
		} while(it != e) ;

		unsigned int cur = m_curLevel ;
		m_curLevel = fLevel ;

		unsigned int nbSubd = 0 ;
		it = old ;
		unsigned int eId = m_edgeId[old] ;			// the particular case of a face
		do											// with all neighboring faces regularly subdivided
		{											// but not the face itself
			++nbSubd ;								// is treated here
			it = phi1(it) ;
		} while(m_edgeId[it] == eId) ;

		while(nbSubd > 1)
		{
			nbSubd /= 2 ;
			--fLevel ;
		}

		m_curLevel = cur ;

		//
		// compute the minimum level of the volume
		// if the level of this face is lower than the saved volume level
		//
430
431
		vLevel = fLevel < vLevel ? fLevel : vLevel ;

432
433
434
435
		//
		// compute the oldest dart from the volume
		// if the oldest dart from this face is oldest than the oldest saved dart
		//
436
		if(m_dartLevel[old] < m_dartLevel[oldest])
437
				oldest = old ;
438

439
440
441
442
443

		//
		// add all face neighbours to the table
		//
		do
444
445
446
447
448
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
untereiner's avatar
untereiner committed
449
				mark.markOrbit(FACE, ee) ;
450
451
			}
			e = phi1(e) ;
untereiner's avatar
untereiner committed
452
		} while(e != visitedFaces[i]) ;
453
454
	}

untereiner's avatar
untereiner committed
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
	//Second : the case of all faces regularly subdivided but not the volume itself
	unsigned int cur = m_curLevel ;
	m_curLevel = vLevel ;

	unsigned int nbSubd = 0 ;
	Dart it = oldest ;
	unsigned int eId = m_edgeId[oldest] ;

	do
	{
		++nbSubd ;
		it = phi1(it) ;
	} while(m_edgeId[it] == eId) ;


	while(nbSubd > 1)
	{
		nbSubd /= 2 ;
	    --vLevel ;
	}

	m_curLevel = cur ;

	return vLevel;
}

482

483
484
485
Dart ImplicitHierarchicalMap3::faceOldestDart(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;
486
487
488
	Dart it = d ;
	Dart oldest = it ;
	unsigned int l_old = m_dartLevel[oldest] ;
489
490
	do
	{
491
492
493
494
495
496
497
498
499
		unsigned int l = m_dartLevel[it] ;
		if(l < l_old || (l == l_old && it < oldest))
		{
			oldest = it ;
			l_old = l ;
		}
		it = phi1(it) ;
	} while(it != d) ;
	return oldest ;
500
501
502
503
504
505
506
507
508
}

Dart ImplicitHierarchicalMap3::volumeOldestDart(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;

	Dart oldest = d;
	DartMarkerStore mark(*this);	// Lock a marker

untereiner's avatar
untereiner committed
509
510
	std::vector<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.reserve(512);
511
512
513
514
	visitedFaces.push_back(d);		// Start with the face of d

	// For every face added to the list
	//the oldest dart from a volume is the oldest dart from all faces of this volume
untereiner's avatar
untereiner committed
515
	mark.markOrbit(FACE, d) ;
516

untereiner's avatar
untereiner committed
517
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
518
	{
untereiner's avatar
untereiner committed
519
		Dart e = visitedFaces[i] ;
520
521

		//for every dart in this face
522
		Dart old = faceOldestDart(e);
523
524
525
526
527
528
529
530
531
		if(m_dartLevel[old] < m_dartLevel[oldest])
			oldest = old;

		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
untereiner's avatar
untereiner committed
532
				mark.markOrbit(FACE, ee) ;
533
534
			}
			e = phi1(e) ;
untereiner's avatar
untereiner committed
535
		} while(e != visitedFaces[i]) ;
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
	}

	return oldest;
}

bool ImplicitHierarchicalMap3::edgeIsSubdivided(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;

	Dart d2 = phi2(d) ;
	++m_curLevel ;
	Dart d2_l = phi2(d) ;
	--m_curLevel ;
	if(d2 != d2_l)
		return true ;
	else
		return false ;
}

bool ImplicitHierarchicalMap3::faceIsSubdivided(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;
	unsigned int fLevel = faceLevel(d) ;
	if(fLevel < m_curLevel)
		return false ;

	bool subd = false ;
	++m_curLevel ;
	if(m_dartLevel[phi1(d)] == m_curLevel && m_edgeId[phi1(d)] != m_edgeId[d])
		subd = true ;
	--m_curLevel ;
567

568
569
570
571
572
573
574
575
576
577
578
579
580
581
	return subd ;
}

bool ImplicitHierarchicalMap3::volumeIsSubdivided(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;
	unsigned int vLevel = volumeLevel(d);
	if(vLevel < m_curLevel)
		return false;

	//test si toutes les faces sont subdivisee
	DartMarkerStore mark(*this);		// Lock a marker

	std::vector<Dart> visitedFaces;		// Faces that are traversed
582
	visitedFaces.reserve(512);
583
584
585
586
	visitedFaces.push_back(d);			// Start with the face of d
	std::vector<Dart>::iterator face;


587
//	Dart old = d ;
588
	bool facesAreSubdivided = faceIsSubdivided(d) ;
589
590
591
592

	//parcours les faces du volume au niveau courant
	//on cherche le brin de niveau le plus bas de la hierarchie
	//on note le niveau le plus bas de la hierarchie
593
	mark.markOrbit(FACE, d) ;
untereiner's avatar
untereiner committed
594
	for(unsigned int i = 0; i < visitedFaces.size(); ++i)
595
	{
untereiner's avatar
untereiner committed
596
		Dart e = visitedFaces[i] ;
597
598
599
600
601
602
603
604
605
606
607
608
609

		// in a first time, the level of a face
		//the level of the volume is the minimum of the
		//levels of its faces

		facesAreSubdivided &= faceIsSubdivided(e) ;

		do	// add all face neighbours to the table
		{
			Dart ee = phi2(e) ;
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
untereiner's avatar
untereiner committed
610
				mark.markOrbit(FACE, ee) ;
611
612
			}
			e = phi1(e) ;
untereiner's avatar
untereiner committed
613
		} while(e != visitedFaces[i]) ;
614
615
616
617
618
619
620
621
622
623
624
	}

	//mais pas le volume lui-meme
	bool subd = false;
	++m_curLevel;
	if(facesAreSubdivided && m_dartLevel[phi2(phi1(phi1(d)))] == m_curLevel && m_faceId[phi2(phi1(phi1(d)))] != m_faceId[d])
		subd = true;
	--m_curLevel;
	return subd;
}

untereiner's avatar
untereiner committed
625

626
bool ImplicitHierarchicalMap3::edgeCanBeCoarsened(Dart d)
untereiner's avatar
untereiner committed
627
628
629
630
631
632
633
634
635
636
637
638
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;

	bool subd = false ;
	bool subdOnce = true ;
	bool degree2 = false ;

	if(edgeIsSubdivided(d))
	{
		subd = true ;
		Dart d2 = phi2(d) ;
		++m_curLevel ;
untereiner's avatar
untereiner committed
639

640
641
		std::cout << "vertex degree = " << vertexDegree(phi1(d)) << std::endl;

untereiner's avatar
untereiner committed
642
643
644
645
646
647
648
649
650
651
652
		if(vertexDegree(phi1(d)) == 2)
		{
			degree2 = true ;
			if(edgeIsSubdivided(d) || edgeIsSubdivided(d2))
				subdOnce = false ;
		}
		--m_curLevel ;
	}
	return subd && degree2 && subdOnce ;
}

653
654
655
656
657
658
659
660
661
662
663
664
665
bool ImplicitHierarchicalMap3::faceCanBeCoarsened(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;

	bool subd = false;
	bool subdOnce = true;
	bool subdNeighborhood = false; //deux volumes voisins de la face ne sont pas subdivise

	if(faceIsSubdivided(d))
	{
		subd = true;
		Dart d3 = phi3(d);

untereiner's avatar
untereiner committed
666
667
668
669
//		std::cout << "d3 = " << d3 << std::endl;
//		std::cout << "d = " << d << std::endl;
//		std::cout << "curLevel = " << m_curLevel << std::endl;
//		std::cout << "volSubd(d3) = " << volumeIsSubdivided(d3) << std::endl;
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690

		//tester si le volume voisin est subdivise
		if(d3 != d && volumeIsSubdivided(d3))
			subdNeighborhood = true;

		++m_curLevel;
		//tester si la face subdivise a des faces subdivise
		Dart cf = phi1(d);

		do
		{
			if(faceIsSubdivided(cf))
				subdOnce = false;

			cf = phi2(phi1(cf));
		}
		while(subdOnce && cf != phi1(d));

		--m_curLevel;
	}

untereiner's avatar
untereiner committed
691
692
//	std::cout << "subdNeighborhood = " << subdNeighborhood << std::endl;
// 	std::cout << "faceCanBeCoarsened ? " << (subd && !subdNeighborhood && subdOnce) << std::endl;
693
694
695
696

	return subd && !subdNeighborhood && subdOnce;
}

untereiner's avatar
untereiner committed
697
bool ImplicitHierarchicalMap3::faceIsSubdividedOnce(Dart d)
untereiner's avatar
untereiner committed
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;
	unsigned int fLevel = faceLevel(d) ;
	if(fLevel < m_curLevel)		// a face whose level in the current level map is lower than
		return false ;			// the current level can not be subdivided to higher levels

	unsigned int degree = 0 ;
	bool subd = false ;
	bool subdOnce = true ;
	Dart fit = d ;
	do
	{
		++m_curLevel ;
		if(m_dartLevel[phi1(fit)] == m_curLevel && m_edgeId[phi1(fit)] != m_edgeId[fit])
		{
			subd = true ;
			++m_curLevel ;
			if(m_dartLevel[phi1(fit)] == m_curLevel && m_edgeId[phi1(fit)] != m_edgeId[fit])
				subdOnce = false ;
			--m_curLevel ;
		}
		--m_curLevel ;
		++degree ;
		fit = phi1(fit) ;
untereiner's avatar
untereiner committed
722

untereiner's avatar
untereiner committed
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
	} while(subd && subdOnce && fit != d) ;

	if(degree == 3 && subd)
	{
		++m_curLevel ;
		Dart cf = phi2(phi1(d)) ;
		++m_curLevel ;
		if(m_dartLevel[phi1(cf)] == m_curLevel && m_edgeId[phi1(cf)] != m_edgeId[cf])
			subdOnce = false ;
		--m_curLevel ;
		--m_curLevel ;
	}

	return subd && subdOnce ;
}

bool ImplicitHierarchicalMap3:: volumeIsSubdividedOnce(Dart d)
{
741
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;
untereiner's avatar
untereiner committed
742
743
744
745

	return true;
}

746
747
748
749
750
751
bool ImplicitHierarchicalMap3::neighborhoodLevelDiffersByOne(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;

	bool found = false;

752
	unsigned int vLevel = volumeLevel(d);// + 1;
753
754
755
756
757
758
759

	Dart old = volumeOldestDart(d);

	DartMarkerStore mf(*this);		// Lock a face marker to save one dart per face

	//Store faces that are traversed and start with the face of d
	std::vector<Dart> visitedFaces;
760
	visitedFaces.reserve(512);
761
762
763
764
	visitedFaces.push_back(old);

	mf.markOrbit(FACE, old) ;

765
	for(unsigned int i = 0; !found && i < visitedFaces.size(); ++i)
766
	{
767
		Dart e = visitedFaces[i] ;
768
769
770
771
		do
		{
			// add all face neighbours to the table

772
			if(phi3(e) != e)
773
			{
774
				Dart old = volumeOldestDart(phi3(e));
775
776
				//if((abs(volumeLevel(old) - vLevel) > 1))
				if(volumeLevel(old) < vLevel)
777
					found = true;
778
779
780
781
782
783
			}

			Dart ee = phi2(e) ;
			if(!mf.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
untereiner's avatar
untereiner committed
784
				mf.markOrbit(FACE, ee) ;
785
786
787
			}

			e = phi1(e) ;
788
		} while(e != visitedFaces[i]) ;
789
790
791
792
793
	}

	return found;
}

794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
bool ImplicitHierarchicalMap3::coarsenNeighborhoodLevelDiffersByOne(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;

	bool found = false;

	//unsigned int vLevel = volumeLevel(d);

	Dart old = volumeOldestDart(d);

	DartMarkerStore mf(*this);		// Lock a face marker to save one dart per face

	//Store faces that are traversed and start with the face of d
	std::vector<Dart> visitedFaces;
	visitedFaces.reserve(512);
	visitedFaces.push_back(old);

	mf.markOrbit(FACE, old) ;

813
	for(unsigned int i = 0; !found && i < visitedFaces.size(); ++i)
814
	{
815
		Dart e = visitedFaces[i] ;
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
		do
		{
			// add all face neighbours to the table

			if(faceIsSubdivided(e))
			{
				++m_curLevel;

				if(faceIsSubdividedOnce(e))
					found = true;

				--m_curLevel;
			}
			Dart ee = phi2(e) ;
			if(!mf.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
				mf.markOrbit(FACE, ee) ;
			}

			e = phi1(e) ;
837
		} while(e != visitedFaces[i]) ;
838
839
840
841
842
	}

	return found;
}

843
844
845
846
847
848
} //namespace IHM

} //namespace Algo

} //namespace CGoGN