subdivision.hppxx 8.42 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 25 26 27 28 29 30
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

namespace CGoGN
{

namespace Algo
{

31 32 33
namespace Surface
{

Pierre Kraemer's avatar
Pierre Kraemer committed
34 35 36 37
namespace IHM
{

template <typename PFP>
38
void subdivideEdge(typename PFP::MAP& map, Dart d, VertexAttribute<typename PFP::VEC3>& position)
Pierre Kraemer's avatar
Pierre Kraemer committed
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
{
	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>
untereiner's avatar
untereiner committed
64
void subdivideFace(typename PFP::MAP& map, Dart d, VertexAttribute<typename PFP::VEC3>& position, bool forceTri)
Pierre Kraemer's avatar
Pierre Kraemer committed
65 66 67 68 69 70 71 72 73 74
{
	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

75 76
	std::cout << "subdiv" << std::endl;

Pierre Kraemer's avatar
Pierre Kraemer committed
77 78 79 80 81 82 83 84
	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)
85
			IHM::subdivideEdge<PFP>(map, it, position) ;	// and compute the degree of the face
Pierre Kraemer's avatar
Pierre Kraemer committed
86 87 88 89 90 91
		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

untereiner's avatar
untereiner committed
92
	if(degree == 3 && forceTri)								// if subdividing a triangle
Pierre Kraemer's avatar
Pierre Kraemer committed
93 94 95 96
	{
		Dart dd = map.phi1(old) ;
		Dart e = map.phi1(map.phi1(dd)) ;
		map.splitFace(dd, e) ;					// insert a new edge
untereiner's avatar
untereiner committed
97 98 99
        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
Pierre Kraemer's avatar
Pierre Kraemer committed
100 101 102 103

		dd = e ;
		e = map.phi1(map.phi1(dd)) ;
		map.splitFace(dd, e) ;
untereiner's avatar
untereiner committed
104 105 106
        id = map.getNewEdgeId() ;
        map.setEdgeId(map.phi_1(dd), id) ;
        map.setEdgeId(map.phi_1(e), id) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
107 108 109 110

		dd = e ;
		e = map.phi1(map.phi1(dd)) ;
		map.splitFace(dd, e) ;
untereiner's avatar
untereiner committed
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
        id = map.getNewEdgeId() ;
        map.setEdgeId(map.phi_1(dd), id) ;
        map.setEdgeId(map.phi_1(e), id) ;


//		Dart stop = map.phi2(map.phi1(old));
//		Dart dit = stop;
//		do
//		{
//			unsigned int dId = map.getEdgeId(map.phi_1(map.phi2(dit)));
//			unsigned int eId = map.getEdgeId(map.phi1(map.phi2(dit)));

//			unsigned int t = dId + eId;

//			if(t == 0)
//			{
//				map.setEdgeId(dit, 1);
//				map.setEdgeId(map.phi2(dit), 1);
//			}
//			else if(t == 1)
//			{
//				map.setEdgeId(dit, 2);
//				map.setEdgeId(map.phi2(dit), 2);
//			}
//			else if(t == 2)
//			{
//				if(dId == eId)
//				{
//					map.setEdgeId(dit, 0);
//					map.setEdgeId(map.phi2(dit), 0);
//				}
//				else
//				{
//					map.setEdgeId(dit, 1);
//					map.setEdgeId(map.phi2(dit), 1);
//				}
//			}
//			else if(t == 3)
//			{
//				map.setEdgeId(dit, 0);
//				map.setEdgeId(map.phi2(dit), 0);
//			}

//			dit = map.phi1(dit);
//		}while(dit != stop);
156

Pierre Kraemer's avatar
Pierre Kraemer committed
157 158 159 160 161 162
	}
	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) ;
untereiner's avatar
untereiner committed
163
        Dart ne2 = map.phi2(ne) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
164 165

		map.cutEdge(ne) ;							// cut the new edge to insert the central vertex
untereiner's avatar
untereiner committed
166 167 168 169 170 171
        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) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
172 173 174 175 176 177 178

		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
179
			map.splitFace(map.phi1(ne), dd) ;
untereiner's avatar
untereiner committed
180 181 182 183
            Dart nne = map.alpha1(dd) ;
            id = map.getNewEdgeId() ;
            map.setEdgeId(nne, id) ;
            map.setEdgeId(map.phi2(nne), id) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
184 185
			dd = next ;
		}
186

untereiner's avatar
untereiner committed
187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203
//		Dart dit = map.phi2(ne);
//		do
//		{
//			unsigned int eId = map.getEdgeId(map.phi1(dit));
//			if(eId == 0)
//			{
//				map.setEdgeId(dit, 1);
//				map.setEdgeId(map.phi2(dit), 1);
//			}
//			else if(eId == 1)
//			{
//				map.setEdgeId(dit, 0);
//				map.setEdgeId(map.phi2(dit), 0);
//			}
//			dit = map.phi2(map.phi_1(dit));
//		}
//		while(dit != map.phi2(ne));
Pierre Kraemer's avatar
Pierre Kraemer committed
204 205 206 207 208 209
	}

	map.setCurrentLevel(cur) ;
}

template <typename PFP>
210
void coarsenEdge(typename PFP::MAP& map, Dart d, VertexAttribute<typename PFP::VEC3>& position)
Pierre Kraemer's avatar
Pierre Kraemer committed
211 212
{
	assert(map.getDartLevel(d) <= map.getCurrentLevel() || !"Access to a dart introduced after current level") ;
213 214
	assert(map.edgeCanBeCoarsened(d) || !"Trying to coarsen an edge that can not be coarsened") ;

215
	unsigned int cur = map.getCurrentLevel() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
216
//	Dart e = map.phi2(d) ;
217
	map.setCurrentLevel(cur + 1) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
218 219 220 221
//	unsigned int dl = map.getDartLevel(e) ;
//	map.setDartLevel(map.phi1(e), dl) ;
//	map.collapseEdge(e) ;
	map.uncutEdge(d) ;
222
	map.setCurrentLevel(cur) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
223 224 225
}

template <typename PFP>
226
void coarsenFace(typename PFP::MAP& map, Dart d, VertexAttribute<typename PFP::VEC3>& position)
Pierre Kraemer's avatar
Pierre Kraemer committed
227 228 229
{
	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
230 231

	unsigned int cur = map.getCurrentLevel() ;
232 233

	unsigned int degree = 0 ;
Pierre Kraemer's avatar
Pierre Kraemer committed
234 235
	Dart fit = d ;
	do
236 237 238 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
	{
		++degree ;
		fit = map.phi1(fit) ;
	} while(fit != d) ;

	if(degree == 3)
	{
		fit = d ;
		do
		{
			map.setCurrentLevel(cur + 1) ;
			Dart innerEdge = map.phi1(fit) ;
			map.setCurrentLevel(map.getMaxLevel()) ;
			map.mergeFaces(innerEdge) ;
			map.setCurrentLevel(cur) ;
			fit = map.phi1(fit) ;
		} while(fit != d) ;
	}
	else
	{
		map.setCurrentLevel(cur + 1) ;
		Dart centralV = map.phi1(map.phi1(d)) ;
		map.setCurrentLevel(map.getMaxLevel()) ;
		map.deleteVertex(centralV) ;
		map.setCurrentLevel(cur) ;
	}

	fit = d ;
	do
Pierre Kraemer's avatar
Pierre Kraemer committed
265
	{
266 267
		if(map.edgeCanBeCoarsened(fit))
			coarsenEdge<PFP>(map, fit, position) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
268 269
		fit = map.phi1(fit) ;
	} while(fit != d) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
270 271 272
}

} //namespace IHM
273
} // Surface
Pierre Kraemer's avatar
Pierre Kraemer committed
274 275
} //namespace Algo
} //namespace CGoGN