ihm3.cpp 12.8 KB
Newer Older
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
/*******************************************************************************
* 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 "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
40
41
{

ImplicitHierarchicalMap3::ImplicitHierarchicalMap3() : m_curLevel(0), m_maxLevel(0), m_edgeIdCount(0), m_faceIdCount(0)
{
	m_dartLevel = Map3::addAttribute<unsigned int>(DART_ORBIT, "dartLevel") ;
	m_faceId = Map3::addAttribute<unsigned int>(DART_ORBIT, "faceId") ;
42
	m_edgeId = Map3::addAttribute<unsigned int>(DART_ORBIT, "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
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
			for(unsigned int i = cellCont.begin(); i < cellCont.end(); cellCont.next(i))
				m_nextLevelCell[orbit]->operator[](i) = EMBNULL ;
		}
	}
}

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);

108
109
				Dart e3 = Map3::phi3(e);
				if(e3 != e)
110
				{
111
112
					m_faceId[e3] = m_faceIdCount ;
					faceMark.mark(e3);
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
				}

				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 ;
132
	unsigned int l_old = m_dartLevel[old] ;
133
134
135
136
	unsigned int fLevel = edgeLevel(it) ;
	do
	{
		it = phi1(it) ;
137
138
139
140
141
142
143
144
		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
145
146
147
148
149
150
151
	} while(it != d) ;

	unsigned int cur = m_curLevel ;
	m_curLevel = fLevel ;

	unsigned int nbSubd = 0 ;
	it = old ;
152
153
154
155
	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
156
157
158
159
160
161
162
163
164
165
166
167
168
		it = phi1(it) ;
	} while(m_edgeId[it] == eId) ;

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

	m_curLevel = cur ;

	return fLevel ;
}
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
//	Dart it = d ;
//	Dart old = it ;
//	unsigned int fLevel = edgeLevel(it) ;
//	do
//	{
//		it = phi1(it) ;
//		if(m_dartLevel[it] < m_dartLevel[old])  	// in a first time, the level of a face
//			old = it ;                      		// is the minimum of the levels
//		unsigned int l = edgeLevel(it) ;        	// of its edges
//		fLevel = l < fLevel ? l : fLevel ;
//	} while(it != d) ;
//
//	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 ;
//
//	return fLevel ;

203
204
205
206
207

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

untereiner's avatar
untereiner committed
208
209
//std::cout << "volumeLevel" << std::endl;

210
211
212
213
214
215
216
217
218
219
220
221
222
223
	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
	visitedFaces.reserve(16);
	visitedFaces.push_back(d);			// Start with the face of d
	std::vector<Dart>::iterator face;

	Dart oldest = d ;
224
	unsigned int vLevel = std::numeric_limits<unsigned int>::max() ; //hook de ouf
225
226
227
228
229
230
231
232
233

	//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
	mark.markOrbit(FACE_ORBIT, d) ;
	for(face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
	{
		Dart e = *face ;

untereiner's avatar
untereiner committed
234
235
//std::cout << "dart from face = " << e << std::endl;

236
237
238
		// in a first time, the level of a face
		//the level of the volume is the minimum of the
		//levels of its faces
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
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

		//
		// 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
		//
285
286
		vLevel = fLevel < vLevel ? fLevel : vLevel ;

287
288
289
290
		//
		// compute the oldest dart from the volume
		// if the oldest dart from this face is oldest than the oldest saved dart
		//
291
		if(m_dartLevel[old] < m_dartLevel[oldest])
292
				oldest = old ;
293

294
295
296
297
298

		//
		// add all face neighbours to the table
		//
		do
299
300
		{
			Dart ee = phi2(e) ;
untereiner's avatar
untereiner committed
301
//std::cout << "\t face a cote =" << ee << std::endl;
302
303
304
305
306
307
308
309
310
			if(!mark.isMarked(ee)) // not already marked
			{
				visitedFaces.push_back(ee) ;
				mark.markOrbit(FACE_ORBIT, ee) ;
			}
			e = phi1(e) ;
		} while(e != *face) ;
	}

untereiner's avatar
untereiner committed
311
312
//std::cout << "fin" << std::endl << std::endl;

313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
	//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;
}

339
340
341
342
343
344
345
346
347
348
349
//		unsigned int fLevel = faceLevel(e) ;
//		vLevel = fLevel < vLevel ? fLevel : vLevel ;
//
//		Dart old = faceOldestDart(e);
//		if(m_dartLevel[old] < m_dartLevel[oldest])
//			oldest = old ;





350
351
352
Dart ImplicitHierarchicalMap3::faceOldestDart(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;
353
354
355
	Dart it = d ;
	Dart oldest = it ;
	unsigned int l_old = m_dartLevel[oldest] ;
356
357
	do
	{
358
359
360
361
362
363
364
365
366
		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 ;
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
}

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

	std::list<Dart> visitedFaces;	// Faces that are traversed
	visitedFaces.push_back(d);		// Start with the face of d
	std::list<Dart>::iterator face;

	// For every face added to the list
	//the oldest dart from a volume is the oldest dart from all faces of this volume
	mark.markOrbit(FACE_ORBIT, d) ;

	for(face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
	{
		Dart e = *face ;

		//for every dart in this face
389
		Dart old = faceOldestDart(e);
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
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
492
493
494
495
496
497
		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) ;
				mark.markOrbit(FACE_ORBIT, ee) ;
			}
			e = phi1(e) ;
		} while(e != *face) ;
	}

	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 ;
	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
	visitedFaces.reserve(16);
	visitedFaces.push_back(d);			// Start with the face of d
	std::vector<Dart>::iterator face;


	Dart old = d ;
	bool facesAreSubdivided = false;

	//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
	mark.markOrbit(FACE_ORBIT, d) ;
	for(face = visitedFaces.begin(); face != visitedFaces.end(); ++face)
	{
		Dart e = *face ;

		// 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) ;
				mark.markOrbit(FACE_ORBIT, ee) ;
			}
			e = phi1(e) ;
		} while(e != *face) ;
	}

	//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;
}

} //namespace IHM

} //namespace Algo

} //namespace CGoGN