halfEdgeSelector.hpp 29.2 KB
Newer Older
1 2 3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2013, IGG Team, ICube, University of Strasbourg           *
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/                                           *
21 22 23 24 25 26 27 28 29 30
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

namespace CGoGN
{

namespace Algo
{

31 32 33
namespace Surface
{

34 35 36
namespace Decimation
{

37 38 39
/*****************************************************************************************************************
 *                                 HALF-EDGE MEMORYLESS QEM METRIC                                               *
 *****************************************************************************************************************/
40 41 42 43 44 45

template <typename PFP>
bool HalfEdgeSelector_QEMml<PFP>::init()
{
	MAP& m = this->m_map ;

46
	if(m_positionApproximator.getApproximatedAttributeName() != m_position.name())
47 48
	{
		return false ;
49
	}
50

51
	for (Vertex v : allVerticesOf(m))
52
	{
53 54
		Utils::Quadric<REAL> q ;	// create one quadric
		m_quadric[v] = q ;				// per vertex
55 56
	}

57
	for (Face f : allFacesOf(m))
58
	{
59 60 61 62 63 64 65
		Dart d = f.dart;
		Dart d1 = m.phi1(d) ;	// for each triangle,
		Dart d_1 = m.phi_1(d) ;	// initialize the quadric of the triangle
		Utils::Quadric<REAL> q(m_position[d], m_position[d1], m_position[d_1]) ;
		m_quadric[d] += q ;		// and add the contribution of
		m_quadric[d1] += q ;		// this quadric to the ones
		m_quadric[d_1] += q ;		// of the 3 incident vertices
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
	}

	// Init multimap for each Half-edge
	halfEdges.clear() ;

	for(Dart d = m.begin(); d != m.end(); m.next(d))
	{
		initHalfEdgeInfo(d) ;	// init the edges with their optimal info
	}							// and insert them in the multimap according to their error

	cur = halfEdges.begin() ; 	// init the current edge to the first one

	return true ;
}

template <typename PFP>
82
bool HalfEdgeSelector_QEMml<PFP>::nextEdge(Dart& d) const
83 84 85 86 87 88 89 90 91 92 93 94
{
	if(cur == halfEdges.end() || halfEdges.empty())
		return false ;
	d = (*cur).second ;
	return true ;
}

template <typename PFP>
void HalfEdgeSelector_QEMml<PFP>::updateBeforeCollapse(Dart d)
{
	MAP& m = this->m_map ;

95 96 97
	HalfEdgeInfo* edgeE = &(halfEdgeInfo[d]) ;
	if(edgeE->valid)
		halfEdges.erase(edgeE->it) ;
98

99 100 101
	edgeE = &(halfEdgeInfo[m.phi1(d)]) ;
	if(edgeE->valid)						// remove all
		halfEdges.erase(edgeE->it) ;
102

103 104 105
	edgeE = &(halfEdgeInfo[m.phi_1(d)]) ;	// the halfedges that will disappear
	if(edgeE->valid)
		halfEdges.erase(edgeE->it) ;
106 107
										// from the multimap
	Dart dd = m.phi2(d) ;
108
	assert(dd != d) ;
109 110
	if(dd != d)
	{
111 112 113
		edgeE = &(halfEdgeInfo[dd]) ;
		if(edgeE->valid)
			halfEdges.erase(edgeE->it) ;
114

115 116 117
		edgeE = &(halfEdgeInfo[m.phi1(dd)]) ;
		if(edgeE->valid)
			halfEdges.erase(edgeE->it) ;
118

119 120 121
		edgeE = &(halfEdgeInfo[m.phi_1(dd)]) ;
		if(edgeE->valid)
			halfEdges.erase(edgeE->it) ;
122 123 124 125
	}
}

template <typename PFP>
126 127
void HalfEdgeSelector_QEMml<PFP>::recomputeQuadric(const Dart d, const bool recomputeNeighbors)
{
128 129 130 131 132 133 134 135
	MAP& m = this->m_map;
	Utils::Quadric<REAL>& q = m_quadric[d];
	q.zero() ;
	Traversor2VF<MAP> tf(m, d);
	for (Dart f = tf.begin() ; f != tf.end() ; f = tf.next())
	{
		q += Utils::Quadric<REAL>(m_position[f], m_position[m.phi1(f)], m_position[m.phi_1(f)]) ;
	}
136

137 138 139 140 141 142 143 144
	if (recomputeNeighbors)
	{
		Traversor2VVaE<MAP> tv(m, d);
		for (Dart v = tv.begin() ; v != tv.end() ; v = tv.next())
		{
			recomputeQuadric(v, false);
		}
	}
145 146 147
}

template <typename PFP>
Sylvain Thery's avatar
Sylvain Thery committed
148
void HalfEdgeSelector_QEMml<PFP>::updateAfterCollapse(Dart d2, Dart /*dd2*/)
149 150 151 152 153 154 155 156 157
{
	MAP& m = this->m_map ;

	recomputeQuadric(d2, true) ;

	Dart vit = d2 ;
	do
	{
		updateHalfEdgeInfo(vit, true) ;
158
		Dart d = m.phi2(vit) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
159
		if (d != vit)
160 161
			updateHalfEdgeInfo(d, true) ;

162
		updateHalfEdgeInfo(m.phi1(vit), true) ;
163
		d = m.phi2(m.phi1(vit)) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
164
		if (d != m.phi1(vit))
165
			updateHalfEdgeInfo(d, true) ;
166 167

		Dart stop = m.phi2(vit) ;
168
		assert (stop != vit) ;
169
		Dart vit2 = m.phi12(m.phi1(vit)) ;
170 171
		do {
			updateHalfEdgeInfo(vit2, true) ;
172
			d = m.phi2(vit2) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
173
			if (d != vit2)
174 175
				updateHalfEdgeInfo(d, true) ;

176
			updateHalfEdgeInfo(m.phi1(vit2), false) ;
177
			d = m.phi2(m.phi1(vit2)) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
178
			if (d != m.phi1(vit2))
179
				updateHalfEdgeInfo(d, false) ;
180

181
			vit2 = m.phi12(vit2) ;
182
		} while (stop != vit2) ;
183
		vit = m.phi2_1(vit) ;
184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237
	} while(vit != d2) ;

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

template <typename PFP>
void HalfEdgeSelector_QEMml<PFP>::initHalfEdgeInfo(Dart d)
{
	MAP& m = this->m_map ;
	HalfEdgeInfo heinfo ;
	if(m.edgeCanCollapse(d))
		computeHalfEdgeInfo(d, heinfo) ;
	else
		heinfo.valid = false ;

	halfEdgeInfo[d] = heinfo ;
}

template <typename PFP>
void HalfEdgeSelector_QEMml<PFP>::updateHalfEdgeInfo(Dart d, bool recompute)
{
	MAP& m = this->m_map ;
	HalfEdgeInfo& heinfo = halfEdgeInfo[d] ;
	if(recompute)
	{
		if(heinfo.valid)
			halfEdges.erase(heinfo.it) ;			// remove the edge from the multimap
		if(m.edgeCanCollapse(d))
			computeHalfEdgeInfo(d, heinfo) ;
		else
			heinfo.valid = false ;
	}
	else
	{
		if(m.edgeCanCollapse(d))
		{								 	// if the edge can be collapsed now
			if(!heinfo.valid)				 // but it was not before
				computeHalfEdgeInfo(d, heinfo) ;
		}
		else
		{								 // if the edge cannot be collapsed now
			if(heinfo.valid)				 // and it was before
			{
				halfEdges.erase(heinfo.it) ;
				heinfo.valid = false ;
			}
		}
	}
}

template <typename PFP>
void HalfEdgeSelector_QEMml<PFP>::computeHalfEdgeInfo(Dart d, HalfEdgeInfo& heinfo)
{
	MAP& m = this->m_map ;
238
	Dart dd = m.phi1(d) ;
239

240
	Utils::Quadric<REAL> quad ;
241 242
	quad += m_quadric[d] ;	// compute the sum of the
	quad += m_quadric[dd] ;	// two vertices quadrics
243

244
	m_positionApproximator.approximate(d) ;
245

246
	REAL err = quad(m_positionApproximator.getApprox(d)) ;
247 248 249 250
	heinfo.it = halfEdges.insert(std::make_pair(err, d)) ;
	heinfo.valid = true ;
}

251 252 253
/*****************************************************************************************************************
 *                                 HALF-EDGE QEMextColor METRIC                                                  *
 *****************************************************************************************************************/
254 255 256 257 258 259

template <typename PFP>
bool HalfEdgeSelector_QEMextColor<PFP>::init()
{
	MAP& m = this->m_map ;

260 261
	assert(m_positionApproximator.getType() == A_hQEM
		|| m_positionApproximator.getType() == A_hHalfCollapse
262
		|| !"Approximator for selector (HalfEdgeSelector_QEMextColor) must be of a half-edge approximator") ;
263

264 265
	assert(m_colorApproximator.getType() == A_hQEM
		|| m_colorApproximator.getType() == A_hHalfCollapse
266
		|| !"Approximator for selector (HalfEdgeSelector_QEMextColor) must be of a half-edge approximator") ;
267

268 269 270 271 272
	if(m_positionApproximator.getApproximatedAttributeName() != m_position.name())
	{
		return false;
	}
	if(m_colorApproximator.getApproximatedAttributeName() != m_color.name())
273
	{
274
		return false;
275 276
	}

277
	for (Vertex v : allVerticesOf(m))
278
	{
279 280
		Utils::QuadricNd<REAL,6> q ;	// create one quadric
		m_quadric[v] = q ;				// per vertex
281 282
	}

283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302
	for (Face f : allFacesOf(m))
	{
		Dart d = f.dart;
		Dart d1 = m.phi1(d) ;	// for each triangle,
		Dart d_1 = m.phi_1(d) ;	// initialize the quadric of the triangle
		VEC6 p0, p1, p2 ;
		for (unsigned int i = 0 ; i < 3 ; ++i)
		{
			p0[i] = m_position[d][i] ;
			p0[i+3] = m_color[d][i] ;
			p1[i] = m_position[d1][i] ;
			p1[i+3] = m_color[d1][i] ;
			p2[i] = m_position[d_1][i] ;
			p2[i+3] = m_color[d_1][i] ;
		}
		Utils::QuadricNd<REAL,6> q(p0, p1, p2) ;
		m_quadric[d] += q ;		// and add the contribution of
		m_quadric[d1] += q ;		// this quadric to the ones
		m_quadric[d_1] += q ;		// of the 3 incident vertices
	}
303 304 305 306 307 308 309 310 311 312 313 314 315 316 317

	// Init multimap for each Half-edge
	halfEdges.clear() ;

	for(Dart d = m.begin(); d != m.end(); m.next(d))
	{
		initHalfEdgeInfo(d) ;	// init the edges with their optimal info
	}							// and insert them in the multimap according to their error

	cur = halfEdges.begin() ; 	// init the current edge to the first one

	return true ;
}

template <typename PFP>
318
bool HalfEdgeSelector_QEMextColor<PFP>::nextEdge(Dart& d) const
319 320 321 322 323 324 325 326 327 328 329 330
{
	if(cur == halfEdges.end() || halfEdges.empty())
		return false ;
	d = (*cur).second ;
	return true ;
}

template <typename PFP>
void HalfEdgeSelector_QEMextColor<PFP>::updateBeforeCollapse(Dart d)
{
	MAP& m = this->m_map ;

331 332 333
	HalfEdgeInfo* edgeE = &(halfEdgeInfo[d]) ;
	if(edgeE->valid)
		halfEdges.erase(edgeE->it) ;
334

335 336 337
	edgeE = &(halfEdgeInfo[m.phi1(d)]) ;
	if(edgeE->valid)						// remove all
		halfEdges.erase(edgeE->it) ;
338

339 340 341
	edgeE = &(halfEdgeInfo[m.phi_1(d)]) ;	// the halfedges that will disappear
	if(edgeE->valid)
		halfEdges.erase(edgeE->it) ;
342 343 344 345 346
										// from the multimap
	Dart dd = m.phi2(d) ;
	assert(dd != d) ;
	if(dd != d)
	{
347 348 349
		edgeE = &(halfEdgeInfo[dd]) ;
		if(edgeE->valid)
			halfEdges.erase(edgeE->it) ;
350

351 352 353
		edgeE = &(halfEdgeInfo[m.phi1(dd)]) ;
		if(edgeE->valid)
			halfEdges.erase(edgeE->it) ;
354

355 356 357
		edgeE = &(halfEdgeInfo[m.phi_1(dd)]) ;
		if(edgeE->valid)
			halfEdges.erase(edgeE->it) ;
358 359 360 361
	}
}

template <typename PFP>
362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
void HalfEdgeSelector_QEMextColor<PFP>::recomputeQuadric(const Dart d, const bool recomputeNeighbors)
{
	MAP& m = this->m_map;
	Utils::QuadricNd<REAL,6>& q = m_quadric[d];
	q.zero() ;
	Traversor2VF<MAP> tf(m, d);
	for (Dart f = tf.begin() ; f != tf.end() ; f = tf.next())
	{
		Dart f1 = m.phi1(f) ;
		Dart f_1 = m.phi_1(f) ;
		VEC6 p0, p1, p2 ;
		for (unsigned int i = 0 ; i < 3 ; ++i)
		{
			p0[i] = m_position[f][i] ;
			p0[i+3] = m_color[f][i] ;
			p1[i] = m_position[f1][i] ;
			p1[i+3] = m_color[f1][i] ;
			p2[i] = m_position[f_1][i] ;
			p2[i+3] = m_color[f_1][i] ;
		}
		q += Utils::QuadricNd<REAL,6>(p0, p1, p2) ;
	}

	if (recomputeNeighbors)
	{
		Traversor2VVaE<MAP> tv(m, d);
		for (Dart v = tv.begin() ; v != tv.end() ; v = tv.next())
		{
			recomputeQuadric(v, false);
		}
	}
393 394 395
}

template <typename PFP>
Sylvain Thery's avatar
Sylvain Thery committed
396
void HalfEdgeSelector_QEMextColor<PFP>::updateAfterCollapse(Dart d2, Dart /*dd2*/)
397 398 399 400 401 402 403 404 405 406
{
	MAP& m = this->m_map ;

	recomputeQuadric(d2, true) ;

	Dart vit = d2 ;
	do
	{
		updateHalfEdgeInfo(vit, true) ;
		Dart d = m.phi2(vit) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
407
		if (d != vit)
408 409 410 411
			updateHalfEdgeInfo(d, true) ;

		updateHalfEdgeInfo(m.phi1(vit), true) ;
		d = m.phi2(m.phi1(vit)) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
412
		if (d != m.phi1(vit))
413 414 415 416 417 418 419 420
			updateHalfEdgeInfo(d, true) ;

		Dart stop = m.phi2(vit) ;
		assert (stop != vit) ;
		Dart vit2 = m.phi12(m.phi1(vit)) ;
		do {
			updateHalfEdgeInfo(vit2, true) ;
			d = m.phi2(vit2) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
421
			if (d != vit2)
422 423 424 425
				updateHalfEdgeInfo(d, true) ;

			updateHalfEdgeInfo(m.phi1(vit2), false) ;
			d = m.phi2(m.phi1(vit2)) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
426
			if (d != m.phi1(vit2))
427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485
				updateHalfEdgeInfo(d, false) ;

			vit2 = m.phi12(vit2) ;
		} while (stop != vit2) ;
		vit = m.phi2_1(vit) ;
	} while(vit != d2) ;

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

template <typename PFP>
void HalfEdgeSelector_QEMextColor<PFP>::initHalfEdgeInfo(Dart d)
{
	MAP& m = this->m_map ;
	HalfEdgeInfo heinfo ;
	if(m.edgeCanCollapse(d))
		computeHalfEdgeInfo(d, heinfo) ;
	else
		heinfo.valid = false ;

	halfEdgeInfo[d] = heinfo ;
}

template <typename PFP>
void HalfEdgeSelector_QEMextColor<PFP>::updateHalfEdgeInfo(Dart d, bool recompute)
{
	MAP& m = this->m_map ;
	HalfEdgeInfo& heinfo = halfEdgeInfo[d] ;
	if(recompute)
	{
		if(heinfo.valid)
			halfEdges.erase(heinfo.it) ;			// remove the edge from the multimap
		if(m.edgeCanCollapse(d))
			computeHalfEdgeInfo(d, heinfo) ;
		else
			heinfo.valid = false ;
	}
	else
	{
		if(m.edgeCanCollapse(d))
		{								 	// if the edge can be collapsed now
			if(!heinfo.valid)				 // but it was not before
				computeHalfEdgeInfo(d, heinfo) ;
		}
		else
		{								 // if the edge cannot be collapsed now
			if(heinfo.valid)				 // and it was before
			{
				halfEdges.erase(heinfo.it) ;
				heinfo.valid = false ;
			}
		}
	}
}

template <typename PFP>
void HalfEdgeSelector_QEMextColor<PFP>::computeHalfEdgeInfo(Dart d, HalfEdgeInfo& heinfo)
{
	MAP& m = this->m_map ;
486

487 488 489 490 491 492 493 494
	Dart dd = m.phi1(d) ;

	// New position
	Utils::QuadricNd<REAL,6> quad ;
	quad += m_quadric[d] ;	// compute the sum of the
	quad += m_quadric[dd] ;	// two vertices quadrics

	// compute all approximated attributes
495 496
	m_positionApproximator.approximate(d) ;
	m_colorApproximator.approximate(d) ;
497 498

	// get pos
499
	const VEC3& newPos = m_positionApproximator.getApprox(d) ;
500
	// get col
501
	const VEC3& newCol = m_colorApproximator.getApprox(d) ;
502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522

	// compute error
	VEC6 newEmb ;
	for (unsigned int i = 0 ; i < 3 ; ++i)
	{
		newEmb[i] = newPos[i] ;
		newEmb[i+3] = newCol[i] ;
	}

	const REAL& err = quad(newEmb) ;

	// Check if errated values appear
	if (err < -1e-6)
		heinfo.valid = false ;
	else
	{
		heinfo.it = this->halfEdges.insert(std::make_pair(std::max(err,REAL(0)), d)) ;
		heinfo.valid = true ;
	}
}

Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
523 524 525 526 527 528 529 530 531
/*****************************************************************************************************************
 *                                 HALF-EDGE QEMextColorNormal METRIC                                                  *
 *****************************************************************************************************************/

template <typename PFP>
bool HalfEdgeSelector_QEMextColorNormal<PFP>::init()
{
	MAP& m = this->m_map ;

532 533
	assert(m_positionApproximator.getType() == A_hQEM
		|| m_positionApproximator.getType() == A_hHalfCollapse
534
		|| !"Approximator for selector (HalfEdgeSelector_QEMextColor) must be of a half-edge approximator") ;
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
535

536 537
	assert(m_colorApproximator.getType() == A_hQEM
		|| m_colorApproximator.getType() == A_hHalfCollapse
538
		|| !"Approximator for selector (HalfEdgeSelector_QEMextColor) must be of a half-edge approximator") ;
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
539

540 541
	assert(m_normalApproximator.getType() == A_hQEM
		|| m_normalApproximator.getType() == A_hHalfCollapse
542
		|| !"Approximator for selector (HalfEdgeSelector_QEMextColor) must be of a half-edge approximator") ;
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
543

544 545 546 547 548 549 550 551 552
	if(m_positionApproximator.getApproximatedAttributeName() != m_position.name())
	{
		return false;
	}
	if(m_colorApproximator.getApproximatedAttributeName() != m_color.name())
	{
		return false;
	}
	if(m_normalApproximator.getApproximatedAttributeName() != m_normal.name())
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
553
	{
554
		return false;
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
555 556
	}

557
	for (Vertex v : allVerticesOf(m))
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
558
	{
559 560 561
		Utils::QuadricNd<REAL,9> q ;	// create one quadric
		m_quadric[v] = q ;				// per vertex
	}
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
562

563 564 565 566 567
	for (Face f : allFacesOf(m))
	{
		Dart d = f.dart;
		Dart d1 = m.phi1(d) ;	// for each triangle,
		Dart d_1 = m.phi_1(d) ;	// initialize the quadric of the triangle
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
568 569 570
		VEC9 p0, p1, p2 ;
		for (unsigned int i = 0 ; i < 3 ; ++i)
		{
571 572 573 574 575 576 577 578 579
			p0[i] = m_position[d][i] ;
			p0[i+3] = m_color[d][i] ;
			p0[i+6] = m_normal[d][i] ;
			p1[i] = m_position[d1][i] ;
			p1[i+3] = m_color[d1][i] ;
			p1[i+6] = m_normal[d1][i] ;
			p2[i] = m_position[d_1][i] ;
			p2[i+3] = m_color[d_1][i] ;
			p2[i+6] = m_normal[d_1][i] ;
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
580
		}
581 582 583 584
		Utils::QuadricNd<REAL,9> q(p0, p1, p2) ;
		m_quadric[d] += q ;		// and add the contribution of
		m_quadric[d1] += q ;		// this quadric to the ones
		m_quadric[d_1] += q ;		// of the 3 incident vertices
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644
	}

	// Init multimap for each Half-edge
	halfEdges.clear() ;

	for(Dart d = m.begin(); d != m.end(); m.next(d))
	{
		initHalfEdgeInfo(d) ;	// init the edges with their optimal info
	}							// and insert them in the multimap according to their error

	cur = halfEdges.begin() ; 	// init the current edge to the first one

	return true ;
}

template <typename PFP>
bool HalfEdgeSelector_QEMextColorNormal<PFP>::nextEdge(Dart& d) const
{
	if(cur == halfEdges.end() || halfEdges.empty())
		return false ;
	d = (*cur).second ;
	return true ;
}

template <typename PFP>
void HalfEdgeSelector_QEMextColorNormal<PFP>::updateBeforeCollapse(Dart d)
{
	MAP& m = this->m_map ;

	HalfEdgeInfo* edgeE = &(halfEdgeInfo[d]) ;
	if(edgeE->valid)
		halfEdges.erase(edgeE->it) ;

	edgeE = &(halfEdgeInfo[m.phi1(d)]) ;
	if(edgeE->valid)						// remove all
		halfEdges.erase(edgeE->it) ;

	edgeE = &(halfEdgeInfo[m.phi_1(d)]) ;	// the halfedges that will disappear
	if(edgeE->valid)
		halfEdges.erase(edgeE->it) ;
										// from the multimap
	Dart dd = m.phi2(d) ;
	assert(dd != d) ;
	if(dd != d)
	{
		edgeE = &(halfEdgeInfo[dd]) ;
		if(edgeE->valid)
			halfEdges.erase(edgeE->it) ;

		edgeE = &(halfEdgeInfo[m.phi1(dd)]) ;
		if(edgeE->valid)
			halfEdges.erase(edgeE->it) ;

		edgeE = &(halfEdgeInfo[m.phi_1(dd)]) ;
		if(edgeE->valid)
			halfEdges.erase(edgeE->it) ;
	}
}

template <typename PFP>
645 646 647 648 649 650 651
void HalfEdgeSelector_QEMextColorNormal<PFP>::recomputeQuadric(const Dart d, const bool recomputeNeighbors)
{
	MAP& m = this->m_map;
	Utils::QuadricNd<REAL,9>& q = m_quadric[d];
	q.zero() ;
	Traversor2VF<MAP> tf(m, d);
	for (Dart f = tf.begin() ; f != tf.end() ; f = tf.next())
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
652
	{
653 654 655 656 657 658 659 660 661 662 663 664 665 666
		Dart f1 = m.phi1(f) ;
		Dart f_1 = m.phi_1(f) ;
		VEC9 p0, p1, p2 ;
		for (unsigned int i = 0 ; i < 3 ; ++i)
		{
			p0[i] = m_position[f][i] ;
			p0[i+3] = m_color[f][i] ;
			p0[i+6] = m_normal[f][i] ;
			p1[i] = m_position[f1][i] ;
			p1[i+3] = m_color[f1][i] ;
			p1[i+6] = m_normal[f1][i] ;
			p2[i] = m_position[f_1][i] ;
			p2[i+3] = m_color[f_1][i] ;
			p2[i+6] = m_normal[f_1][i] ;
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
667
		}
668 669
		q += Utils::QuadricNd<REAL,9>(p0, p1, p2) ;
	}
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
670

671 672 673 674 675 676 677 678
	if (recomputeNeighbors)
	{
		Traversor2VVaE<MAP> tv(m, d);
		for (Dart v = tv.begin() ; v != tv.end() ; v = tv.next())
		{
			recomputeQuadric(v, false);
		}
	}
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779
}

template <typename PFP>
void HalfEdgeSelector_QEMextColorNormal<PFP>::updateAfterCollapse(Dart d2, Dart /*dd2*/)
{
	MAP& m = this->m_map ;

	recomputeQuadric(d2, true) ;

	Dart vit = d2 ;
	do
	{
		updateHalfEdgeInfo(vit, true) ;
		Dart d = m.phi2(vit) ;
		if (d != vit)
			updateHalfEdgeInfo(d, true) ;

		updateHalfEdgeInfo(m.phi1(vit), true) ;
		d = m.phi2(m.phi1(vit)) ;
		if (d != m.phi1(vit))
			updateHalfEdgeInfo(d, true) ;

		Dart stop = m.phi2(vit) ;
		assert (stop != vit) ;
		Dart vit2 = m.phi12(m.phi1(vit)) ;
		do {
			updateHalfEdgeInfo(vit2, true) ;
			d = m.phi2(vit2) ;
			if (d != vit2)
				updateHalfEdgeInfo(d, true) ;

			updateHalfEdgeInfo(m.phi1(vit2), false) ;
			d = m.phi2(m.phi1(vit2)) ;
			if (d != m.phi1(vit2))
				updateHalfEdgeInfo(d, false) ;

			vit2 = m.phi12(vit2) ;
		} while (stop != vit2) ;
		vit = m.phi2_1(vit) ;
	} while(vit != d2) ;

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

template <typename PFP>
void HalfEdgeSelector_QEMextColorNormal<PFP>::initHalfEdgeInfo(Dart d)
{
	MAP& m = this->m_map ;
	HalfEdgeInfo heinfo ;
	if(m.edgeCanCollapse(d))
		computeHalfEdgeInfo(d, heinfo) ;
	else
		heinfo.valid = false ;

	halfEdgeInfo[d] = heinfo ;
}

template <typename PFP>
void HalfEdgeSelector_QEMextColorNormal<PFP>::updateHalfEdgeInfo(Dart d, bool recompute)
{
	MAP& m = this->m_map ;
	HalfEdgeInfo& heinfo = halfEdgeInfo[d] ;
	if(recompute)
	{
		if(heinfo.valid)
			halfEdges.erase(heinfo.it) ;			// remove the edge from the multimap
		if(m.edgeCanCollapse(d))
			computeHalfEdgeInfo(d, heinfo) ;
		else
			heinfo.valid = false ;
	}
	else
	{
		if(m.edgeCanCollapse(d))
		{								 	// if the edge can be collapsed now
			if(!heinfo.valid)				 // but it was not before
				computeHalfEdgeInfo(d, heinfo) ;
		}
		else
		{								 // if the edge cannot be collapsed now
			if(heinfo.valid)				 // and it was before
			{
				halfEdges.erase(heinfo.it) ;
				heinfo.valid = false ;
			}
		}
	}
}

template <typename PFP>
void HalfEdgeSelector_QEMextColorNormal<PFP>::computeHalfEdgeInfo(Dart d, HalfEdgeInfo& heinfo)
{
	MAP& m = this->m_map ;
	Dart dd = m.phi1(d) ;

	// New position
	Utils::QuadricNd<REAL,9> quad ;
	quad += m_quadric[d] ;	// compute the sum of the
	quad += m_quadric[dd] ;	// two vertices quadrics

	// compute all approximated attributes
780 781 782
	m_positionApproximator.approximate(d) ;
	m_colorApproximator.approximate(d) ;
	m_normalApproximator.approximate(d) ;
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
783 784

	// get pos
785
	const VEC3& newPos = m_positionApproximator.getApprox(d) ;
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
786
	// get col
787
	const VEC3& newCol = m_colorApproximator.getApprox(d) ;
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
788
	// get normal
789
	const VEC3& newN = m_normalApproximator.getApprox(d) ;
Kenneth Vanhoey's avatar
up  
Kenneth Vanhoey committed
790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812

	// compute error
	VEC9 newEmb ;
	for (unsigned int i = 0 ; i < 3 ; ++i)
	{
		newEmb[i] = newPos[i] ;
		newEmb[i+3] = newCol[i] ;
		newEmb[i+6] = newN[i] ;
	}

	const REAL& err = quad(newEmb) ;

	// Check if errated values appear
	if (err < -1e-6)
		heinfo.valid = false ;
	else
	{
		heinfo.it = this->halfEdges.insert(std::make_pair(std::max(err,REAL(0)), d)) ;
		heinfo.valid = true ;
	}
}


813 814 815
/*****************************************************************************************************************
 *                                 HALF-EDGE COLOR GRADIENT ERR                                                  *
 *****************************************************************************************************************/
816 817

template <typename PFP>
818
bool HalfEdgeSelector_ColorGradient<PFP>::init()
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
819 820 821
{
	MAP& m = this->m_map ;

822 823
	assert(m_positionApproximator.getType() == A_hQEM
		|| m_positionApproximator.getType() == A_hHalfCollapse
824
		|| !"Approximator for selector (HalfEdgeSelector_QEMextColor) must be of a half-edge approximator") ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
825

826 827
	assert(m_colorApproximator.getType() == A_hQEM
		|| m_colorApproximator.getType() == A_hHalfCollapse
828
		|| !"Approximator for selector (HalfEdgeSelector_QEMextColor) must be of a half-edge approximator") ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
829

830 831 832 833 834 835 836
	if(m_positionApproximator.getApproximatedAttributeName() != m_position.name())
	{
		return false;
	}
	if(m_colorApproximator.getApproximatedAttributeName() != m_color.name())
	{
		return false;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
837 838
	}

839
	for (Vertex v : allVerticesOf(m))
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
840
	{
841 842
		Utils::Quadric<REAL> q ;	// create one quadric
		m_quadric[v] = q ;				// per vertex
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
843 844
	}

845
	for (Face f : allFacesOf(m))
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
846
	{
847 848 849 850 851 852 853
		Dart d = f.dart;
		Dart d1 = m.phi1(d) ;	// for each triangle,
		Dart d_1 = m.phi_1(d) ;	// initialize the quadric of the triangle
		Utils::Quadric<REAL> q(m_position[d], m_position[d1], m_position[d_1]) ;
		m_quadric[d] += q ;		// and add the contribution of
		m_quadric[d1] += q ;		// this quadric to the ones
		m_quadric[d_1] += q ;		// of the 3 incident vertices
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
854 855 856 857 858
	}

	// Init multimap for each Half-edge
	halfEdges.clear() ;

859
	for(Dart d = m.begin(); d != m.end(); m.next(d))
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
860
	{
861 862
		initHalfEdgeInfo(d) ;	// init the edges with their optimal info
	}							// and insert them in the multimap according to their error
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
863 864 865 866 867 868 869

	cur = halfEdges.begin() ; 	// init the current edge to the first one

	return true ;
}

template <typename PFP>
870
bool HalfEdgeSelector_ColorGradient<PFP>::nextEdge(Dart& d) const
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
871 872 873 874 875 876 877 878
{
	if(cur == halfEdges.end() || halfEdges.empty())
		return false ;
	d = (*cur).second ;
	return true ;
}

template <typename PFP>
879
void HalfEdgeSelector_ColorGradient<PFP>::updateBeforeCollapse(Dart d)
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905
{
	MAP& m = this->m_map ;

	const Dart& v0 = m.phi1(d) ;

	Traversor2VVaE<MAP> tv(m,v0) ;
	for (Dart v = tv.begin() ; v != tv.end() ; v = tv.next())
	{
		Traversor2VE<MAP> te(m,v) ;
		for (Dart he = te.begin() ; he != te.end() ; he = te.next())
		{
			HalfEdgeInfo* edgeE = &(halfEdgeInfo[he]) ;
			if(edgeE->valid)
			{
				edgeE->valid = false ;
				halfEdges.erase(edgeE->it) ;
			}
			Dart de = m.phi2(he) ;
			edgeE = &(halfEdgeInfo[de]) ;
			if(edgeE->valid)
			{
				edgeE->valid = false ;
				halfEdges.erase(edgeE->it) ;
			}
		}
	}
906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934

//	HalfEdgeInfo* edgeE = &(halfEdgeInfo[d]) ;
//	if(edgeE->valid)
//		halfEdges.erase(edgeE->it) ;
//
//	edgeE = &(halfEdgeInfo[m.phi1(d)]) ;
//	if(edgeE->valid)						// remove all
//		halfEdges.erase(edgeE->it) ;
//
//	edgeE = &(halfEdgeInfo[m.phi_1(d)]) ;	// the halfedges that will disappear
//	if(edgeE->valid)
//		halfEdges.erase(edgeE->it) ;
//										// from the multimap
//	Dart dd = m.phi2(d) ;
//	assert(dd != d) ;
//	if(dd != d)
//	{
//		edgeE = &(halfEdgeInfo[dd]) ;
//		if(edgeE->valid)
//			halfEdges.erase(edgeE->it) ;
//
//		edgeE = &(halfEdgeInfo[m.phi1(dd)]) ;
//		if(edgeE->valid)
//			halfEdges.erase(edgeE->it) ;
//
//		edgeE = &(halfEdgeInfo[m.phi_1(dd)]) ;
//		if(edgeE->valid)
//			halfEdges.erase(edgeE->it) ;
//	}
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
935 936 937
}

template <typename PFP>
938
void HalfEdgeSelector_ColorGradient<PFP>::recomputeQuadric(const Dart d)
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
939
{
940 941 942 943 944 945 946 947
	MAP& m = this->m_map;
	Utils::Quadric<REAL>& q = m_quadric[d];
	q.zero() ;
	Traversor2VF<MAP> tf(m, d);
	for (Dart f = tf.begin() ; f != tf.end() ; f = tf.next())
	{
		q += Utils::Quadric<REAL>(m_position[f], m_position[m.phi1(f)], m_position[m.phi_1(f)]) ;
	}
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
948 949 950
}

template <typename PFP>
Sylvain Thery's avatar
Sylvain Thery committed
951
void HalfEdgeSelector_ColorGradient<PFP>::updateAfterCollapse(Dart d2, Dart /*dd2*/)
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977
{
	MAP& m = this->m_map ;

	const Dart& v1 = d2 ;

	recomputeQuadric(v1) ;
	Traversor2VVaE<MAP> tv(m,v1) ;
	for (Dart v = tv.begin() ; v != tv.end() ; v = tv.next())
	{
		recomputeQuadric(v) ;
	}

	for (Dart v = tv.begin() ; v != tv.end() ; v = tv.next())
	{
		Traversor2VE<MAP> te(m,v) ;
		for (Dart e = te.begin() ; e != te.end() ; e = te.next())
		{
			updateHalfEdgeInfo(e) ;
			updateHalfEdgeInfo(m.phi2(e)) ;
		}
	}

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

template <typename PFP>
978
void HalfEdgeSelector_ColorGradient<PFP>::initHalfEdgeInfo(Dart d)
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
979 980 981 982 983 984 985 986 987 988 989 990
{
	MAP& m = this->m_map ;
	HalfEdgeInfo heinfo ;
	if(m.edgeCanCollapse(d))
		computeHalfEdgeInfo(d, heinfo) ;
	else
		heinfo.valid = false ;

	halfEdgeInfo[d] = heinfo ;
}

template <typename PFP>
991
void HalfEdgeSelector_ColorGradient<PFP>::updateHalfEdgeInfo(Dart d)
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
992 993 994 995 996 997 998 999 1000
{
	MAP& m = this->m_map ;
	HalfEdgeInfo& heinfo = halfEdgeInfo[d] ;

	if(!heinfo.valid && m.edgeCanCollapse(d))
		computeHalfEdgeInfo(d, heinfo) ;
}

template <typename PFP>
1001
void HalfEdgeSelector_ColorGradient<PFP>::computeHalfEdgeInfo(Dart d, HalfEdgeInfo& heinfo)
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1002 1003 1004 1005 1006 1007 1008 1009 1010
{
	MAP& m = this->m_map ;
	Dart dd = m.phi1(d) ;

	Utils::Quadric<REAL> quad ;
	quad += m_quadric[d] ;	// compute the sum of the
	quad += m_quadric[dd] ;	// two vertices quadrics

	// compute all approximated attributes
1011 1012
	m_positionApproximator.approximate(d) ;
	m_colorApproximator.approximate(d) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1013 1014 1015

	// Get all approximated attributes
	// New position
1016 1017 1018
	const VEC3& newPos = m_positionApproximator.getApprox(d) ;
	// New color
	const VEC3& newCol = m_colorApproximator.getApprox(d) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1019 1020 1021 1022

	const Dart& v0 = dd ;
	const Dart& v1 = d ;

1023 1024
	assert(newPos == m_position[v1]) ;
	assert(newCol == m_color[v1]) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1025 1026 1027 1028 1029 1030 1031

	// Compute errors
	// Position
	Utils::Quadric<REAL> quadGeom ;
	quadGeom += m_quadric[d] ;	// compute the sum of the
	quadGeom += m_quadric[dd] ;	// two vertices quadrics

1032 1033 1034
	//std::cout << quadGeom(newPos) / (alpha/M_PI + quadHF(newHF)) << std::endl ;
	// sum of QEM metric and color gradient metric
	const REAL t = 0.01 ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1035
	const REAL& err =
1036 1037 1038
		t * quadGeom(newPos) + // geom
		(1-t) * computeGradientColorError(v0,v1).norm()/sqrt(3) // color
	;
1039 1040 1041

	/*std::cout << quadGeom(newPos) << std::endl ;
	std::cerr << computeGradientColorError(v0,v1).norm()/sqrt(3) << std::endl ;*/
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053

	// Check if errated values appear
	if (err < -1e-6)
		heinfo.valid = false ;
	else
	{
		heinfo.it = this->halfEdges.insert(std::make_pair(std::max(err,REAL(0)), d)) ;
		heinfo.valid = true ;
	}
}

template <typename PFP>
1054 1055
typename PFP::VEC3
HalfEdgeSelector_ColorGradient<PFP>::computeGradientColorError(const Dart& v0, const Dart& v1) const
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1056 1057 1058
{
	MAP& m = this->m_map ;

1059
	Traversor2VF<MAP> tf(m, v0) ; // all faces around vertex v0
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1060

1061 1062
	const VEC3& P0 = m_position[v0] ;
	const VEC3& P1 = m_position[v1] ;
1063 1064 1065
	const VEC3& c0 = m_color[v0] ;
	const VEC3& c1 = m_color[v1] ;
	const VEC3 d = P1 - P0 ; // displacement vector
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1066

1067 1068 1069
	VEC3 count ;
	REAL areaSum = 0 ;
	for (Dart fi = tf.begin() ; fi != tf.end() ; fi = tf.next()) // foreach "blue" face
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1070
	{
1071
		// get the data
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1072 1073
		const Dart& vi = m.phi1(fi) ;
		const Dart& vj = m.phi_1(fi) ;
1074 1075
		const VEC3& Pi = m_position[vi] ;
		const VEC3& Pj = m_position[vj] ;
1076 1077
		const VEC3& ci = m_color[vi] ;
		const VEC3& cj = m_color[vj] ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1078

1079 1080 1081 1082
		// utils
		const VEC3 ei = P0 - Pj ;
		const VEC3 ej = Pi - P0 ;
		//const VEC3 e0 = Pj - Pi ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1083

1084 1085 1086 1087 1088
		const REAL areaIJ0sq = (ei ^ ej).norm2() ;
		const REAL areaIJ0 = sqrt(areaIJ0sq)/2. ;
		areaSum += areaIJ0 ;
		// per-channel treatment
		for (unsigned int c = 0 ; c < 3 ;  ++c)
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1089
		{
1090 1091 1092 1093 1094 1095 1096 1097
			// color gradient for channel i
			VEC3 grad = (ei.norm2()*(ci[c]-c1[c]) + (ei*ej)*(cj[c]-c1[c]))*ej ;
			grad -= (ej.norm2()*(cj[c]-c1[c]) + (ei*ej)*(ci[c]-c1[c]))*ei ;
			const REAL denom = areaIJ0sq ;
			if (denom < 1e-9) // case flat triangles
				grad = VEC3(0,0,0) ;
			else
				grad /= denom ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1098

1099
			// color change error for channel i
1100
			count[c] += areaIJ0 * pow(d*grad, 2) ;
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
1101 1102 1103
		}
	}

1104 1105
	const VEC3 colDiff = c1 - c0 ;
	for (unsigned int c = 0 ; c < 3 ; ++c)
1106
	{
1107
		count[c] += pow(colDiff[c],2) * areaSum ;
1108 1109
	}

1110
	return count ;
1111 1112 1113 1114 1115 1116
}

} // namespace Decimation

} // namespace Surface

1117 1118 1119
} // namespace Algo

} // namespace CGoGN