subdivision.hpp 6.51 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
59
60
61
62
63
64
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/*******************************************************************************
* 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                                        *
*                                                                              *
*******************************************************************************/

namespace CGoGN
{

namespace Algo
{

namespace IHM
{

template <typename PFP>
void subdivideEdge(typename PFP::MAP& map, Dart d, typename PFP::TVEC3& position)
{
	assert(map.getDartLevel(d) <= map.getCurrentLevel() || !"Access to a dart introduced after current level") ;
	assert(!map.edgeIsSubdivided(d) || !"Trying to subdivide an already subdivided edge") ;

	unsigned int eLevel = map.edgeLevel(d) ;

	unsigned int cur = map.getCurrentLevel() ;
	map.setCurrentLevel(eLevel) ;

	Dart dd = map.phi2(d) ;
	typename PFP::VEC3 p1 = position[d] ;
	typename PFP::VEC3 p2 = position[map.phi1(d)] ;

	map.setCurrentLevel(eLevel + 1) ;

	map.cutEdge(d) ;
	unsigned int eId = map.getEdgeId(d) ;
	map.setEdgeId(map.phi1(d), eId) ;
	map.setEdgeId(map.phi1(dd), eId) ;
	position[map.phi1(d)] = (p1 + p2) * typename PFP::REAL(0.5) ;

	map.setCurrentLevel(cur) ;
}

template <typename PFP>
void subdivideFace(typename PFP::MAP& map, Dart d, typename PFP::TVEC3& position)
{
	assert(map.getDartLevel(d) <= map.getCurrentLevel() || !"Access to a dart introduced after current level") ;
	assert(!map.faceIsSubdivided(d) || !"Trying to subdivide an already subdivided face") ;

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

	unsigned int cur = map.getCurrentLevel() ;
	map.setCurrentLevel(fLevel) ;		// go to the level of the face to subdivide its edges

	unsigned int degree = 0 ;
	typename PFP::VEC3 p ;
	Dart it = old ;
	do
	{
		++degree ;
		p += position[it] ;
		if(!map.edgeIsSubdivided(it))							// first cut the edges (if they are not already)
			Algo::IHM::subdivideEdge<PFP>(map, it, position) ;	// and compute the degree of the face
		it = map.phi1(it) ;
	} while(it != old) ;
	p /= typename PFP::REAL(degree) ;

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

	if(degree == 3)								// if subdividing a triangle
	{
		Dart dd = map.phi1(old) ;
		Dart e = map.phi1(map.phi1(dd)) ;
		map.splitFace(dd, e) ;					// insert a new edge
		unsigned int id = map.getNewEdgeId() ;
		map.setEdgeId(map.phi_1(dd), id) ;		// set the edge id of the inserted
		map.setEdgeId(map.phi_1(e), id) ;		// edge to the next available id

		dd = e ;
		e = map.phi1(map.phi1(dd)) ;
		map.splitFace(dd, e) ;
		id = map.getNewEdgeId() ;
		map.setEdgeId(map.phi_1(dd), id) ;
		map.setEdgeId(map.phi_1(e), id) ;

		dd = e ;
		e = map.phi1(map.phi1(dd)) ;
		map.splitFace(dd, e) ;
		id = map.getNewEdgeId() ;
		map.setEdgeId(map.phi_1(dd), id) ;
		map.setEdgeId(map.phi_1(e), id) ;
	}
	else											// if subdividing a polygonal face
	{
		Dart dd = map.phi1(old) ;
		map.splitFace(dd, map.phi1(map.phi1(dd))) ;	// insert a first edge
		Dart ne = map.alpha1(dd) ;
		Dart ne2 = map.phi2(ne) ;

		map.cutEdge(ne) ;							// cut the new edge to insert the central vertex
		unsigned int id = map.getNewEdgeId() ;
		map.setEdgeId(ne, id) ;
		map.setEdgeId(map.phi2(ne), id) ;			// set the edge id of the inserted
		id = map.getNewEdgeId() ;
		map.setEdgeId(ne2, id) ;					// edges to the next available ids
		map.setEdgeId(map.phi2(ne2), id) ;

		position[map.phi2(ne)] = p ;

		dd = map.phi1(map.phi1(map.phi1(map.phi1(ne)))) ;
		while(dd != ne)								// turn around the face and insert new edges
		{											// linked to the central vertex
			Dart next = map.phi1(map.phi1(dd)) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
131
			map.splitFace(map.phi1(ne), dd) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
			Dart nne = map.alpha1(dd) ;
			id = map.getNewEdgeId() ;
			map.setEdgeId(nne, id) ;
			map.setEdgeId(map.phi2(nne), id) ;
			dd = next ;
		}
	}

	map.setCurrentLevel(cur) ;
}

template <typename PFP>
void coarsenEdge(typename PFP::MAP& map, Dart d, typename PFP::TVEC3& position)
{
	assert(map.getDartLevel(d) <= map.getCurrentLevel() || !"Access to a dart introduced after current level") ;
147
148
	assert(map.edgeCanBeCoarsened(d) || !"Trying to coarsen an edge that can not be coarsened") ;

149
150
151
152
153
154
155
156
157
	unsigned int cur = map.getCurrentLevel() ;
	Dart d2 = map.phi2(d) ;
	map.setCurrentLevel(cur + 1) ;
	map.unsewFaces(d) ;
	map.unsewFaces(d2) ;
	map.collapseEdge(map.phi1(d)) ;
	map.collapseEdge(map.phi1(d2)) ;
	map.sewFaces(d, d2) ;
	map.setCurrentLevel(cur) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
158
159
160
161
162
163
164
}

template <typename PFP>
void coarsenFace(typename PFP::MAP& map, Dart d, typename PFP::TVEC3& position)
{
	assert(map.getDartLevel(d) <= map.getCurrentLevel() || !"Access to a dart introduced after current level") ;
	assert(map.faceIsSubdividedOnce(d) || !"Trying to coarsen a non-subdivided face or a more than once subdivided face") ;
Pierre Kraemer's avatar
Pierre Kraemer committed
165
166

	unsigned int cur = map.getCurrentLevel() ;
167
168
169
	map.setCurrentLevel(cur + 1) ;
	map.deleteVertex(map.phi1(map.phi1(d))) ;
	map.setCurrentLevel(cur) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
170
171
172
	Dart fit = d ;
	do
	{
173
174
		if(map.edgeCanBeCoarsened(fit))
			coarsenEdge<PFP>(map, fit, position) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
175
176
		fit = map.phi1(fit) ;
	} while(fit != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
177
178
179
180
181
182
183
}

} //namespace IHM

} //namespace Algo

} //namespace CGoGN