subdivision.hpp 6.54 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
	unsigned int cur = map.getCurrentLevel() ;
	Dart d2 = map.phi2(d) ;
	map.setCurrentLevel(cur + 1) ;
152 153 154
	unsigned int dl = map.getDartLevel(d2) ;
	map.setDartLevel(map.phi1(d2), dl) ;
	map.collapseEdge(d2) ;
155
	map.setCurrentLevel(cur) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
156 157 158 159 160 161 162
}

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
163 164

	unsigned int cur = map.getCurrentLevel() ;
165 166
	map.setCurrentLevel(cur + 1) ;
	Dart cv = map.phi1(map.phi1(d)) ;
167
	map.setCurrentLevel(map.getMaxLevel()) ;
168
	map.deleteVertex(cv) ;
169
	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