edgeSelector.hpp 7.19 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 27 28 29 30 31 32 33 34 35
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
* Copyright (C) 2009-2012, 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: http://cgogn.unistra.fr/                                           *
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#include "Algo/DecimationVolumes/geometryApproximator.h"
#include <time.h>

namespace CGoGN
{

namespace Algo
{

namespace DecimationVolumes
{
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
/************************************************************************************
 *                                  MAP ORDER                                       *
 ************************************************************************************/

template <typename PFP>
bool EdgeSelector_MapOrder<PFP>::init()
{
	MAP& m = this->m_map ;
	cur = m.begin() ;
	while(!this->m_select(cur) || !m.edgeCanCollapse(cur))
	{
		m.next(cur) ;
		if(cur == m.end())
			return false;
	}
	return true ;
}

template <typename PFP>
bool EdgeSelector_MapOrder<PFP>::nextEdge(Dart& d)
{
	MAP& m = this->m_map ;
	if(cur == m.end())
		return false ;
	d = cur ;
	return true ;
}

template <typename PFP>
void EdgeSelector_MapOrder<PFP>::updateAfterCollapse(Dart d2, Dart dd2)
{
	MAP& m = this->m_map ;
	cur = m.begin() ;
	while(!this->m_select(cur) || !m.edgeCanCollapse(cur))
	{
		m.next(cur) ;
		if(cur == m.end())
			break ;
	}
}
76 77

/************************************************************************************
78
 *	                                  RANDOM                                    	*
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
template <typename PFP>
bool EdgeSelector_Random<PFP>::init()
{
	MAP& m = this->m_map ;

	darts.reserve(m.getNbDarts()) ;
	darts.clear() ;

	for(Dart d = m.begin(); d != m.end(); m.next(d))
		darts.push_back(d) ;

	srand(time(NULL)) ;
	int remains = darts.size() ;
	for(unsigned int i = 0; i < darts.size()-1; ++i) // generate the random permutation
	{
		int r = (rand() % remains) + i ;
		// swap ith and rth elements
		Dart tmp = darts[i] ;
		darts[i] = darts[r] ;
		darts[r] = tmp ;
		--remains ;
	}

	cur = 0 ;
	allSkipped = true ;

	return true ;
}
108 109

template <typename PFP>
110 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
bool EdgeSelector_Random<PFP>::nextEdge(Dart& d)
{
	if(cur == darts.size() && allSkipped)
		return false ;
	d = darts[cur] ;
	return true ;
}


template <typename PFP>
void EdgeSelector_Random<PFP>::updateAfterCollapse(Dart d2, Dart dd2)
{
	MAP& m = this->m_map ;
	allSkipped = false ;
	do
	{
		++cur ;
		if(cur == darts.size())
		{
			cur = 0 ;
			allSkipped = true ;
		}
	} while(!this->m_select(cur) || !m.edgeCanCollapse(darts[cur])) ;
}

/************************************************************************************
 *                                 		SG98                                     	*
 ************************************************************************************/
template <typename PFP>
bool EdgeSelector_SG98<PFP>::init()
140
{
141 142 143 144
	MAP& m = this->m_map ;

	bool ok = false ;
	for(typename std::vector<ApproximatorGen<PFP>*>::iterator it = this->m_approximators.begin();
145 146
		it != this->m_approximators.end() && !ok;
		++it)
147 148 149 150 151 152 153 154 155 156 157
	{
		if((*it)->getApproximatedAttributeName() == "position")
		{
			m_positionApproximator = reinterpret_cast<Approximator<PFP, VEC3>* >(*it) ;
			ok = true ;
		}
	}

	if(!ok)
		return false ;

158
	edges.clear() ;
159

160 161
	TraversorE<typename PFP::MAP> tE(m);
	for(Dart dit = tE.begin() ; dit != tE.end() ; dit = tE.next())
162 163 164
	{
		initEdgeInfo(dit);
	}
165

166
	cur = edges.begin();
untereiner's avatar
untereiner committed
167 168

	return true;
169 170 171
}

template <typename PFP>
172
bool EdgeSelector_SG98<PFP>::nextEdge(Dart& d)
173
{
174 175 176 177
	if(cur == edges.end() || edges.empty())
		return false ;
	d = (*cur).second ;
	return true ;
178 179 180
}

template <typename PFP>
181
void EdgeSelector_SG98<PFP>::updateBeforeCollapse(Dart d)
182 183 184
{
	MAP& m = this->m_map ;

185 186 187
	// remove all
	// the concerned edges
	// from the multimap
188 189 190

}

191
template <typename PFP>
192
void EdgeSelector_SG98<PFP>::updateAfterCollapse(Dart d2, Dart dd2)
193 194 195 196
{
	MAP& m = this->m_map ;


197
	// must recompute some edge infos in the
198

199 200 201 202 203
	// various optimizations are applied here by
	// treating differently :
	// - edges for which the criteria must be recomputed
	// - edges that must be re-embedded
	// - edges for which only the collapsibility must be re-tested
204 205 206 207 208

	cur = edges.begin() ; // set the current edge to the first one
}

template <typename PFP>
209
void EdgeSelector_SG98<PFP>::initEdgeInfo(Dart d)
210 211 212 213 214 215 216 217 218 219 220
{
	MAP& m = this->m_map ;
	EdgeInfo einfo ;
	if(m.edgeCanCollapse(d))
		computeEdgeInfo(d, einfo) ;
	else
		einfo.valid = false ;
	edgeInfo[d] = einfo ;
}

template <typename PFP>
221
void EdgeSelector_SG98<PFP>::updateEdgeInfo(Dart d, bool recompute)
222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252
{
	MAP& m = this->m_map ;
	EdgeInfo& einfo = edgeInfo[d] ;
	if(recompute)
	{
		if(einfo.valid)
			edges.erase(einfo.it) ;		// remove the edge from the multimap
		if(m.edgeCanCollapse(d))
			computeEdgeInfo(d, einfo) ;
		else
			einfo.valid = false ;
	}
	else
	{
		if(m.edgeCanCollapse(d))
		{								 	// if the edge can be collapsed now
			if(!einfo.valid)				// but it was not before
				computeEdgeInfo(d, einfo) ;
		}
		else
		{								 // if the edge cannot be collapsed now
			if(einfo.valid)				 // and it was before
			{
				edges.erase(einfo.it) ;
				einfo.valid = false ;
			}
		}
	}
}

template <typename PFP>
253
void EdgeSelector_SG98<PFP>::computeEdgeInfo(Dart d, EdgeInfo& einfo)
254 255 256 257
{
	MAP& m = this->m_map ;
	Dart dd = m.phi2(d) ;

258 259 260 261 262 263 264 265 266 267
//	Quadric<REAL> quad ;
//	quad += quadric[d] ;	// compute the sum of the
//	quad += quadric[dd] ;	// two vertices quadrics
//
//	m_positionApproximator->approximate(d) ;
//
//	REAL err = quad(m_positionApproximator->getApprox(d)) ;
//
//	einfo.it = edges.insert(std::make_pair(err, d)) ;
//	einfo.valid = true ;
268 269
}

270 271 272
} //end namespace DecimationVolumique
} //end namespace Algo
} //end namespace CGoGN