qem.h 16.2 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
 * 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                                        *
 *                                                                              *
 *******************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
24

25
/*! \file qem.h
26 27 28
* Header file for Quadric Error Metric classes.
*/

Pierre Kraemer's avatar
Pierre Kraemer committed
29 30 31
#ifndef __QEM__
#define __QEM__

32
#include "Utils/os_spec.h" // allow compilation under windows
33
#include <cmath>
34

Pierre Kraemer's avatar
Pierre Kraemer committed
35 36
#include "Geometry/vector_gen.h"
#include "Geometry/matrix.h"
37
#include "Geometry/tensor.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
38 39
#include "Geometry/plane_3d.h"

40 41
// Eigen includes
#include <Eigen/Dense>
42

43 44 45
/*! \namespace CGoGN
 * \brief namespace for all elements composing the CGoGN library
 */
46 47
namespace CGoGN {

48 49 50
/*! \namespace Utils
 * \brief namespace for tool classes used by CGoGN and its applications
 */
51
namespace Utils {
52

53 54 55 56 57
/*! \class Quadric
 *
 * \brief Quadric for computing the quadric error metric (QEM)
 * introduced by Garland and Heckbert in 1997.
 */
Pierre Kraemer's avatar
Pierre Kraemer committed
58 59 60 61
template <typename REAL>
class Quadric
{
public:
62
	/**
63 64
	 * \brief get CGoGN name of current type
	 *
65 66 67 68 69 70
	 * \return name of the CGoGN type
	 */
	static std::string CGoGNnameOfType()
	{
		return "Quadric" ;
	}
Pierre Kraemer's avatar
Pierre Kraemer committed
71

72 73 74
	typedef Geom::Vector<3,REAL> VEC3 ;
	typedef Geom::Vector<4,REAL> VEC4 ;
	typedef Geom::Matrix<4,4,double> MATRIX44 ; // double is crucial here !
Pierre Kraemer's avatar
Pierre Kraemer committed
75

76 77 78
	/*!
	 * \brief Default constructor
	 *
79
	 * Initializes empty members.
80
	 */
81
	Quadric() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
82

83 84 85 86 87 88
	/*!
	 * \brief Constructor
	 *
	 * Initializes empty members (idem. default constructor).
	 * Exists for compatibility reasons.
	 */
89
	Quadric(int i) ;
90 91

	/*!
92
	 * \brief Constructor building a quadric given three points (defining a plane);.
93 94 95 96 97
	 *
	 * \param p1 first point
	 * \param p2 second point
	 * \param p3 third point
	 */
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
98
	Quadric(const VEC3& p1, const VEC3& p2, const VEC3& p3) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
99

100 101 102 103 104 105

	/*!
	 * \brief destructor
	 */
	~Quadric() {} ;

106 107 108
	/*!
	 * \brief set members to zero
	 */
109
	void zero() ;
110

111 112 113 114 115
	/*!
	 * \brief affectation operator (by copy)
	 *
	 * \param q the Quadric to copy
	 */
116
	void operator= (const Quadric<REAL>& q) ;
117 118 119 120 121 122

	/*!
	 * \brief sum of Quadric operator
	 *
	 * \param q the Quadric to sum
	 */
123
	Quadric& operator+= (const Quadric<REAL>& q) ;
124 125 126 127 128 129

	/*!
	 * \brief substract of Quadric operator
	 *
	 * \param q the Quadric to substract
	 */
130
	Quadric& operator -= (const Quadric<REAL>& q) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
131

132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
	/*!
	 * \brief scalar product operator
	 *
	 * \param v the scalar to multiply the Quadric with
	 */
	Quadric& operator *= (const REAL& v) ;

	/*!
	 * \brief scalar division operator
	 *
	 * \param v the scalar to divide the Quadric with
	 */
	Quadric& operator /= (const REAL& v) ;

	/*!
147
	 * \brief error evaluation operator
148 149 150 151 152
	 *
	 * \param v a point expressed in homogeneous coordinates in space
	 *
	 * \return the error
	 */
153
	REAL operator() (const VEC4& v) const ;
154 155

	/*!
156
	 * \brief error evaluation operator
157 158 159 160 161
	 *
	 * \param v a point in space
	 *
	 * \param the error
	 */
162
	REAL operator() (const VEC3& v) const ;
Pierre Kraemer's avatar
Pierre Kraemer committed
163

164 165 166 167 168 169 170 171
	/*!
	 * \brief Write to stream operator
	 *
	 * \param out the stream to write to
	 * \param q the Quadric to write in the stream
	 *
	 * \return the stream reference
	 */
Pierre Kraemer's avatar
Pierre Kraemer committed
172 173 174 175
	friend std::ostream& operator<<(std::ostream& out, const Quadric<REAL>& q)
	{
		out << q.A ;
		return out ;
176
	} ;
Pierre Kraemer's avatar
Pierre Kraemer committed
177

178 179 180 181 182 183 184 185
	/*!
	 * \brief Read from stream operator
	 *
	 * \param int the stream to read from
	 * \param q the Quadric to write the data that has been read in
	 *
	 * \return the stream reference
	 */
Pierre Kraemer's avatar
Pierre Kraemer committed
186 187 188 189
	friend std::istream& operator>>(std::istream& in, Quadric<REAL>& q)
	{
		in >> q.A ;
		return in ;
190
	} ;
Pierre Kraemer's avatar
Pierre Kraemer committed
191

192 193 194 195 196 197 198
	/*!
	 * \brief Method to deduce a position in space that minimizes the error
	 *
	 * \param v the ideal position (if it can be computed)
	 *
	 * \return true if the ideal position has been computed correctly
	 */
199
	bool findOptimizedPos(VEC3& v) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
200 201

private:
202 203 204 205 206 207 208 209 210
	MATRIX44 A ; /*!< The Quadric matrix */

	/*!
	 * \brief method to evaluate the error at a given point in space (homogeneous coordinates)
	 *
	 * \param v the given point
	 *
	 * \return the error
	 */
211
	REAL evaluate(const VEC4& v) const ;
Pierre Kraemer's avatar
Pierre Kraemer committed
212

213 214 215 216 217 218 219 220
	/*!
	 * \brief method to deduce an optimal position in space (homogeneous coordinates)
	 * w.r.t. the current Quadric.
	 *
	 * \param v will contain the optimal position (if it can be computed)
	 *
	 * \return true if an optimal position was correctly computed
	 */
221
	bool optimize(VEC4& v) const ;
Pierre Kraemer's avatar
Pierre Kraemer committed
222 223
} ;

224 225 226 227 228 229
/*! \class QuadricNd
 * \brief extension of Quadric (which is 3D) to nD points.
 * This was published by Garland and Heckbert in 1998 and is meant to define a quadric
 * for a nD-space which contains geometry (3D) + other attributes like color (3D),
 * normals (3D) or texture coordinates (2D) for instance.
 */
230 231 232 233
template <typename REAL, unsigned int N>
class QuadricNd
{
public:
234 235 236 237 238
	/**
	 * \brief get CGoGN name of current type
	 *
	 * \return name of the CGoGN type
	 */
239 240 241 242
	static std::string CGoGNnameOfType()
	{
		return "QuadricNd" ;
	}
243 244 245 246

	typedef Geom::Vector<N,REAL> VECN ;
	typedef Geom::Vector<N+1,REAL> VECNp ;

247 248 249 250 251
	/*!
	 * \brief Default constructor
	 *
	 * Initializes empty members.
	 */
252
	QuadricNd() ;
253

254 255 256 257 258 259
	/*!
	 * \brief Constructor
	 *
	 * Initializes empty members (idem. default constructor).
	 * Exists for compatibility reasons.
	 */
260
	QuadricNd(int i) ;
261

262 263 264 265 266 267 268
	/*!
	 * \brief Constructor building a quadricNd given three points (defining a plane);
	 *
	 * \param p1 first point
	 * \param p2 second point
	 * \param p3 third point
	 */
269
	QuadricNd(const VECN& p1_r, const VECN& p2_r, const VECN& p3_r) ;
270

271 272 273 274 275 276 277 278
	/*!
	 * \brief destructor
	 */
	~QuadricNd() {} ;

	/*!
	 * \brief set members to zero
	 */
279
	void zero() ;
280

281 282 283
	/*!
	 * \brief affectation operator (by copy)
	 *
284
	 * \param q the QuadricNd to copy
285
	 */
286
	void operator= (const QuadricNd<REAL,N>& q) ;
287

288
	/*!
289
	 * \brief sum of QuadricNd operator
290
	 *
291
	 * \param q the QuadricNd to sum
292
	 */
293
	QuadricNd& operator+= (const QuadricNd<REAL,N>& q) ;
294

295
	/*!
296
	 * \brief substract of QuadricNd operator
297
	 *
298
	 * \param q the QuadricNd to substract
299
	 */
300
	QuadricNd& operator -= (const QuadricNd<REAL,N>& q) ;
301

302 303 304
	/*!
	 * \brief scalar product operator
	 *
305
	 * \param v the scalar to multiply the QuadricNd with
306
	 */
307
	QuadricNd& operator *= (REAL v) ;
308

309 310 311 312 313
	/*!
	 * \brief scalar division operator
	 *
	 * \param v the scalar to divide the QuadricNd with
	 */
314
	QuadricNd& operator /= (REAL v) ;
315

316 317 318 319 320 321 322
	/*!
	 * \brief error evaluation operator
	 *
	 * \param v a point expressed in homogeneous coordinates in nD space
	 *
	 * \return the error
	 */
323
	REAL operator() (const VECNp& v) const ;
324

325 326 327 328 329 330 331
	/*!
	 * \brief error evaluation operator
	 *
	 * \param v a point in nD space
	 *
	 * \param the error
	 */
332
	REAL operator() (const VECN& v) const ;
333

334 335 336 337 338 339 340 341
	/*!
	 * \brief Write to stream operator
	 *
	 * \param out the stream to write to
	 * \param q the QuadricNd to write in the stream
	 *
	 * \return the stream reference
	 */
342 343
	friend std::ostream& operator<<(std::ostream& out, const QuadricNd<REAL,N>& q)
	{
344
		out << "(" << q.A << ", " << q.b << ", " << q.c << ")" ;
345
		return out ;
346
	} ;
347

348 349 350 351 352 353 354 355
	/*!
	 * \brief Read from stream operator
	 *
	 * \param int the stream to read from
	 * \param q the QuadricNd to write the data that has been read in
	 *
	 * \return the stream reference
	 */
356 357
	friend std::istream& operator>>(std::istream& in, QuadricNd<REAL,N>& q)
	{
358 359 360
		in >> q.A ;
		in >> q.b ;
		in >> q.c ;
361
		return in ;
362
	} ;
363

364 365 366 367 368 369 370
	/*!
	 * \brief Method to deduce a position in space that minimizes the error
	 *
	 * \param v the ideal position (if it can be computed)
	 *
	 * \return true if the ideal position has been computed correctly
	 */
371
	bool findOptimizedVec(VECN& v) ;
372 373

private:
374
	// Double computation is crucial for stability
375 376 377
	Geom::Matrix<N,N,double> A ; /*!< The first QuadricNd member matrix A */
	Geom::Vector<N,double> b ; /*!< The second QuadricNd member vector b */
	double c ;/*!< The third QuadricNd member scalar c */
378

379 380 381 382 383 384 385
	/*!
	 * \brief method to evaluate the error at a given nD point in space (homogeneous coordinates)
	 *
	 * \param v the given point
	 *
	 * \return the error
	 */
386
	REAL evaluate(const VECN& v) const ;
387

388 389 390 391 392 393 394 395
	/*!
	 * \brief method to deduce an optimal position in space (homogeneous coordinates)
	 * w.r.t. the current QuadricNd.
	 *
	 * \param v will contain the optimal position (if it can be computed)
	 *
	 * \return true if an optimal position was correctly computed
	 */
396
	bool optimize(VECN& v) const ;
397 398
} ;

399
/*! \class QuadricHF
400
 * \brief quadric used for measuring a lightfield metric.
401 402 403
 * This was defined by Vanhoey, Sauvage and Dischler in 2012.
 * This implementation works only for polynomial basis functions.
 */
404 405 406 407
template <typename REAL>
class QuadricHF
{
public:
408 409 410 411 412
	/**
	 * \brief get CGoGN name of current type
	 *
	 * \return name of the CGoGN type
	 */
413 414
	static std::string CGoGNnameOfType() { return "QuadricHF" ; }

415
	typedef Geom::Vector<3,REAL> VEC3 ;
416

417 418 419 420 421
	/*!
	 * \brief Constructor
	 *
	 * Initializes empty members
	 */
422
	QuadricHF() ;
423

424 425 426 427 428 429
	/*!
	 * \brief Constructor
	 *
	 * Initializes empty members (idem. default constructor)
	 * Exists for compatibility reasons
	 */
430
	QuadricHF(int i) ;
431

432
	/*!
433
	 * \brief Constructor building a QuadricHF given a lightfield function and the two angles gamma and alpha
434 435 436 437 438
	 *
	 * \param v the lightfield function
	 * \param gamma
	 * \param alpha
	 */
439
	QuadricHF(const std::vector<VEC3>& v, const REAL& gamma, const REAL& alpha) ;
440

441
	/*!
442
	 * \brief Constructor building a QuadricHF given a lightfield function and the two angles gamma and alpha
443 444 445 446 447
	 *
	 * \param v the lightfield function expressed as a Geom::Tensor
	 * \param gamma
	 * \param alpha
	 */
448
	QuadricHF(const Geom::Tensor3d* T, const REAL& gamma, const REAL& alpha) ;
449

450 451 452
	/*!
	 * Destructor
	 */
453
	~QuadricHF() ;
454

455 456 457
	/*!
	 * \brief set members to zero
	 */
458 459
	void zero() ;

460 461 462 463 464
	/*!
	 * \brief affectation operator (by copy)
	 *
	 * \param q the QuadricHF to copy
	 */
465 466
	QuadricHF& operator= (const QuadricHF<REAL>& q) ;

467 468 469 470 471
	/*!
	 * \brief sum of QuadricHF operator
	 *
	 * \param q the QuadricHF to sum
	 */
472
	QuadricHF& operator+= (const QuadricHF<REAL>& q) ;
473 474

	/*!
475
	 * \brief substract of QuadricHF operator
476 477 478
	 *
	 * \param q the QuadricHF to substract
	 */
479 480
	QuadricHF& operator -= (const QuadricHF<REAL>& q) ;

481 482 483 484 485
	/*!
	 * \brief scalar product operator
	 *
	 * \param v the scalar to multiply the QuadricHF with
	 */
486 487
	QuadricHF& operator *= (const REAL& v) ;

488 489 490 491 492
	/*!
	 * \brief scalar division operator
	 *
	 * \param v the scalar to divide the QuadricHF with
	 */
493 494
	QuadricHF& operator /= (const REAL& v) ;

495 496 497 498 499 500 501
	/*!
	 * \brief error evaluation operator
	 *
	 * \param coefs a lightfield function
	 *
	 * \param the error
	 */
502
	REAL operator() (const std::vector<VEC3>& coefs) const ;
503

504 505 506 507 508 509 510 511 512 513

	/*!
	 * \brief method to evaluate the error for a given lightfield function
	 *
	 * \param coefs the given function
	 *
	 * \return the squared error per color channel
	 */
	VEC3 evalR3(const std::vector<VEC3>& coefs) const ;

514 515 516 517
	/*!
	 * \brief Write to stream operator
	 *
	 * \param out the stream to write to
518
	 * \param q the QuadricHF to write in the stream
519 520 521
	 *
	 * \return the stream reference
	 */
522 523
	friend std::ostream& operator<<(std::ostream& out, const QuadricHF<REAL>& q)
	{
524
        out << "(" << q.m_A << ", " << q.m_b << ", " << q.m_c << ")" ;
525
		return out ;
526
    }
527

528 529 530 531 532 533 534 535
	/*!
	 * \brief Read from stream operator
	 *
	 * \param int the stream to read from
	 * \param q the QuadricHF to write the data that has been read in
	 *
	 * \return the stream reference
	 */
536 537
	friend std::istream& operator>>(std::istream& in, QuadricHF<REAL>& q)
	{
538
		// TODO
539 540 541
		//		in >> q.A ;
		//		in >> q.b ;
		//		in >> q.c ;
542
		return in ;
543
	} ;
544

545 546 547 548 549 550 551
	/*!
	 * \brief Method to deduce a position in space that minimizes the error
	 *
	 * \param v the ideal position (if it can be computed)
	 *
	 * \return true if the ideal position has been computed correctly
	 */
552
	bool findOptimizedCoefs(std::vector<VEC3>& coefs) ;
553

554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570
	/*!
	 * \brief method to convert a lightfield in tensor format to a coefficient vector format
	 *
	 * \param coefs vector of coefficients representing a lightfield function
	 *
	 * \return a tensor representing the same lightfield function
	 *
	 */
	static Geom::Tensor3d* tensorsFromCoefs(const std::vector<VEC3>& coefs) ;

	/*!
	 * \brief method to convert a lightfield in coefficient vector format to a tensor format
	 *
	 * \param T the tensor to convert
	 *
	 * \return a vector of coefficients representing the same lightfield function
	 */
571
	static std::vector<VEC3> coefsFromTensors(Geom::Tensor3d* T) ;
572 573

	/*!
574 575
	 * \brief method to complete a symmetric matrix that was
	 * only filled in its first half (line >= column)
576
	 *
577
	 * \param M the matrix to fill
578
	 */
579 580 581 582 583 584 585 586 587 588 589
	static void fillSymmetricMatrix(Eigen::MatrixXd& M) ;

	/*!
	 * \brief method to rotate a tensor representing a polynomial light field
	 *
	 * \param T the tensor representing a polynomial light field
	 * \param R the 3x3 matrix representing a rotation in (u,v,1)-space
	 *
	 * \return a new rotated tensor representing a polynomial light field.
	 */
	static Geom::Tensor3d rotate(const Geom::Tensor3d& T, const Geom::Matrix33d& R) ;
590

591 592
private:
	// Double computation is crucial for stability
593 594 595
	Eigen::MatrixXd m_A ; /*!< The first QuadricHF member matrix A */
	Eigen::VectorXd m_b[3] ; /*!< The second QuadricHF member vector b */
	double m_c[3] ; /*!< The third QuadricHF member scalar c */
Kenneth Vanhoey's avatar
Kenneth Vanhoey committed
596 597
	std::vector<VEC3> m_coefs ; /*!< The coefficients in cas optim fails */
	bool m_noAlphaRot ; /*!< If alpha = 0 then optim will fail */
598

599 600 601 602 603
	/*!
	 * \brief method to evaluate the error for a given lightfield function
	 *
	 * \param coefs the given function
	 *
604
	 * \return the norm of the squared error per color channel
605
	 */
606
	REAL evaluate(const std::vector<VEC3>& coefs) const ;
607

608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626
	/*!
	 * \brief method to build a rotate matrix (rotation in tangent plane)
	 * given angle gamma
	 *
	 * \param gamma the rotation angle
	 *
	 * \return the rotation matrix
	 */
	Geom::Matrix33d buildRotateMatrix(const REAL& gamma) ;

	/*!
	 * \brief method to build the first integral matrix A
	 * given angle alpha
	 *
	 * \param alpha angle
	 * \param size the amount of monomes in a function
	 *
	 * \return the integral of product of monomes
	 */
627
	Eigen::MatrixXd buildIntegralMatrix_A(const REAL& alpha, unsigned int size) ;
628 629 630 631 632 633 634 635 636 637

	/*!
	 * \brief method to build the first integral matrix B
	 * given angle alpha
	 *
	 * \param alpha angle
	 * * \param size the amount of monomes in a function
	 *
	 * \return the integral of product of monomes
	 */
638
	Eigen::MatrixXd buildIntegralMatrix_B(const REAL& alpha, unsigned int size) ;
639

640 641 642 643 644 645 646 647 648
	/*!
	 * \brief method to build the third integral matrix C
	 * given angle alpha
	 *
	 * \param alpha angle
	 * \param size the amount of monomes in a function
	 *
	 * \return the integral of product of monomes
	 */
649
	Eigen::MatrixXd buildIntegralMatrix_C(const REAL& alpha, unsigned int size) ;
650 651 652

	Eigen::MatrixXd buildLowerLeftIntegralMatrix_A(const REAL& alpha, unsigned int size) ;
	Eigen::MatrixXd buildLowerLeftIntegralMatrix_C(const REAL& alpha, unsigned int size) ;
653 654
} ;

655
} // Utils
656 657 658

} // CGOGN

659 660
#include "qem.hpp"

Pierre Kraemer's avatar
Pierre Kraemer committed
661
#endif