ihm.cpp 7.96 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*******************************************************************************
* 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/ihm.h"
#include <math.h>

namespace CGoGN
{

namespace Algo
{

namespace IHM
{

ImplicitHierarchicalMap::ImplicitHierarchicalMap() : m_curLevel(0), m_maxLevel(0), m_idCount(0)
{
	m_dartLevel = Map2::addAttribute<unsigned int>(DART_ORBIT, "dartLevel") ;
	m_edgeId = Map2::addAttribute<unsigned int>(DART_ORBIT, "edgeId") ;
	for(unsigned int i = 0; i < NB_ORBITS; ++i)
		m_nextLevelCell[i] = NULL ;
}

ImplicitHierarchicalMap::~ImplicitHierarchicalMap()
{
	Map2::removeAttribute(m_edgeId) ;
	Map2::removeAttribute(m_dartLevel) ;
}

void ImplicitHierarchicalMap::init()
{
	initEdgeId() ;

	for(unsigned int orbit = 0; orbit < NB_ORBITS; ++orbit)
	{
		if(m_nextLevelCell[orbit] != NULL)
		{
59
			AttributeContainer& cellCont = m_attribs[orbit] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
			for(unsigned int i = cellCont.begin(); i < cellCont.end(); cellCont.next(i))
				m_nextLevelCell[orbit]->operator[](i) = EMBNULL ;
		}
	}
}

void ImplicitHierarchicalMap::initEdgeId()
{
	m_idCount = 0 ;
	DartMarker edgeMark(*this) ;
	for(Dart d = Map2::begin(); d != Map2::end(); Map2::next(d))
	{
		if(!edgeMark.isMarked(d))
		{
			edgeMark.markOrbit(EDGE_ORBIT, d) ;
			m_edgeId[d] = m_idCount ;
			m_edgeId[Map2::phi2(d)] = m_idCount++ ;
		}
	}
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
85
86
87
	if(m_curLevel == 0)
		return 0 ;

Pierre Kraemer's avatar
Pierre Kraemer committed
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
//	unsigned int cur = m_curLevel ;
//	Dart it = d ;
//	Dart end = d ;
//	bool resetEnd = true ;
//	bool firstEdge = true ;
//	do
//	{
//		if(!resetEnd)
//			firstEdge = false ;
//
//		unsigned int eId = m_edgeId[it] ;
//		Dart next = it ;
//		do
//		{
//			unsigned int l = edgeLevel(next) ;
//			if(l < m_curLevel)
//				m_curLevel = l ;
//			else // l == curLevel
//			{
//				if(!firstEdge)
//				{
//					--m_curLevel ;
//					next = it ;
//				}
//			}
//			next = phi1(next) ;
//		} while(m_edgeId[next] == eId) ;
//		it = next ;
//
//		if(resetEnd)
//		{
//			end = it ;
//			resetEnd = false ;
//		}
//
//	} while(!firstEdge && it != end) ;
//
//	unsigned int fLevel = m_curLevel ;
//	m_curLevel = cur ;

Pierre Kraemer's avatar
Pierre Kraemer committed
128
129
	Dart it = d ;
	Dart old = it ;
130
	unsigned int l_old = m_dartLevel[old] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
131
132
133
134
	unsigned int fLevel = edgeLevel(it) ;
	do
	{
		it = phi1(it) ;
135
136
137
138
139
140
141
142
		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
Pierre Kraemer's avatar
Pierre Kraemer committed
143
144
145
146
147
148
149
150
151
152
153
154
155
	} 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) ;
156
157
158
159
160
161
162

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

Pierre Kraemer's avatar
Pierre Kraemer committed
163
164
165
166
167
	m_curLevel = cur ;

	return fLevel ;
}

168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
Dart ImplicitHierarchicalMap::faceOrigin(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;
	unsigned int cur = m_curLevel ;
	Dart p = d ;
	unsigned int pLevel = m_dartLevel[p] ;
	while(pLevel > 0)
	{
		p = faceOldestDart(p) ;
		pLevel = m_dartLevel[p] ;
		m_curLevel = pLevel ;
	}
	m_curLevel = cur ;
	return p ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
184
185
186
187
188
Dart ImplicitHierarchicalMap::faceOldestDart(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;
	Dart it = d ;
	Dart oldest = it ;
189
	unsigned int l_old = m_dartLevel[oldest] ;
Pierre Kraemer's avatar
Pierre Kraemer committed
190
191
	do
	{
192
		unsigned int l = m_dartLevel[it] ;
193
194
195
196
		if(l == 0)
			return it ;
		if(l < l_old)
//		if(l < l_old || (l == l_old && it < oldest))
197
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
198
			oldest = it ;
199
200
201
			l_old = l ;
		}
		it = phi1(it) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
202
203
204
205
206
207
208
209
210
211
	} while(it != d) ;
	return oldest ;
}

bool ImplicitHierarchicalMap::edgeIsSubdivided(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;
//	Dart d2 = phi2(d) ;
	Dart d1 = phi1(d) ;
	++m_curLevel ;
212
//	Dart d2_l = phi2(d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
213
214
215
216
217
218
219
220
	Dart d1_l = phi1(d) ;
	--m_curLevel ;
	if(d1 != d1_l)
		return true ;
	else
		return false ;
}

221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
bool ImplicitHierarchicalMap::edgeCanBeCoarsened(Dart d)
{
	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 ;
		if(vertexDegree(phi1(d)) == 2)
		{
			degree2 = true ;
			if(edgeIsSubdivided(d) || edgeIsSubdivided(d2))
				subdOnce = false ;
		}
		--m_curLevel ;
	}
	return subd && degree2 && subdOnce ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
bool ImplicitHierarchicalMap::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 ImplicitHierarchicalMap::faceIsSubdividedOnce(Dart d)
{
	assert(m_dartLevel[d] <= m_curLevel || !"Access to a dart introduced after current level") ;
	unsigned int fLevel = faceLevel(d) ;
262
263
	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
Pierre Kraemer's avatar
Pierre Kraemer committed
264
265
266
267
268
269
270
271

	unsigned int degree = 0 ;
	bool subd = false ;
	bool subdOnce = true ;
	Dart fit = d ;
	do
	{
		++m_curLevel ;
Pierre Kraemer's avatar
Pierre Kraemer committed
272
		if(m_dartLevel[phi1(fit)] == m_curLevel && m_edgeId[phi1(fit)] != m_edgeId[fit])
Pierre Kraemer's avatar
Pierre Kraemer committed
273
274
275
		{
			subd = true ;
			++m_curLevel ;
Pierre Kraemer's avatar
Pierre Kraemer committed
276
			if(m_dartLevel[phi1(fit)] == m_curLevel && m_edgeId[phi1(fit)] != m_edgeId[fit])
Pierre Kraemer's avatar
Pierre Kraemer committed
277
278
279
280
281
282
283
284
285
286
287
288
289
				subdOnce = false ;
			--m_curLevel ;
		}
		--m_curLevel ;
		++degree ;
		fit = phi1(fit) ;
	} while(subd && subdOnce && fit != d) ;

	if(degree == 3 && subd)
	{
		++m_curLevel ;
		Dart cf = phi2(phi1(d)) ;
		++m_curLevel ;
290
		if(m_dartLevel[phi1(cf)] == m_curLevel && m_edgeId[phi1(cf)] != m_edgeId[cf])
Pierre Kraemer's avatar
Pierre Kraemer committed
291
292
293
294
295
296
297
298
299
300
301
302
303
			subdOnce = false ;
		--m_curLevel ;
		--m_curLevel ;
	}

	return subd && subdOnce ;
}

} //namespace IHM

} //namespace Algo

} //namespace CGoGN