qem.h 8.97 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
#define CONST_VAL -5212368.54127 // random value
44

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

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

55
56
57
58
59
/*! \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
60
61
62
63
template <typename REAL>
class Quadric
{
public:
64
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
79
80
	/*!
	 * \brief Default constructor
	 *
	 * Initializes empty members
	 */
81
	Quadric() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
82

83
84
85
86
87
88
89
90
91
	//Quadric(int i) ;

	/*!
	 * \brief Constructor building a quadric given three points (defining a plane);
	 *
	 * \param p1 first point
	 * \param p2 second point
	 * \param p3 third point
	 */
92
	Quadric(VEC3& p1, VEC3& p2, VEC3& p3) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
93

94
95
96
	/*!
	 * \brief set members to zero
	 */
97
	void zero() ;
98

99
100
101
102
103
	/*!
	 * \brief affectation operator (by copy)
	 *
	 * \param q the Quadric to copy
	 */
104
	void operator= (const Quadric<REAL>& q) ;
105
106
107
108
109
110

	/*!
	 * \brief sum of Quadric operator
	 *
	 * \param q the Quadric to sum
	 */
111
	Quadric& operator+= (const Quadric<REAL>& q) ;
112
113
114
115
116
117

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

120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
	/*!
	 * \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) ;

	/*!
	 * `brief error evaluation operator
	 *
	 * \param v a point expressed in homogeneous coordinates in space
	 *
	 * \return the error
	 */
141
	REAL operator() (const VEC4& v) const ;
142
143
144
145
146
147
148
149

	/*!
	 * `brief error evaluation operator
	 *
	 * \param v a point in space
	 *
	 * \param the error
	 */
150
	REAL operator() (const VEC3& v) const ;
Pierre Kraemer's avatar
Pierre Kraemer committed
151

152
153
154
155
156
157
158
159
	/*!
	 * \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
160
161
162
163
	friend std::ostream& operator<<(std::ostream& out, const Quadric<REAL>& q)
	{
		out << q.A ;
		return out ;
164
	} ;
Pierre Kraemer's avatar
Pierre Kraemer committed
165

166
167
168
169
170
171
172
173
	/*!
	 * \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
174
175
176
177
	friend std::istream& operator>>(std::istream& in, Quadric<REAL>& q)
	{
		in >> q.A ;
		return in ;
178
	} ;
Pierre Kraemer's avatar
Pierre Kraemer committed
179

180
181
182
183
184
185
186
	/*!
	 * \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
	 */
187
	bool findOptimizedPos(VEC3& v) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
188
189

private:
190
191
192
193
194
195
196
197
198
	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
	 */
199
	REAL evaluate(const VEC4& v) const ;
Pierre Kraemer's avatar
Pierre Kraemer committed
200

201
202
203
204
205
206
207
208
	/*!
	 * \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
	 */
209
	bool optimize(VEC4& v) const ;
Pierre Kraemer's avatar
Pierre Kraemer committed
210
211
} ;

212
213
214
215
216
217
/*! \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.
 */
218
219
220
221
template <typename REAL, unsigned int N>
class QuadricNd
{
public:
222
223
224
225
	static std::string CGoGNnameOfType()
	{
		return "QuadricNd" ;
	}
226
227
228
229

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

230
	QuadricNd() ;
231

232
	QuadricNd(int i) ;
233

234
	QuadricNd(const VECN& p1_r, const VECN& p2_r, const VECN& p3_r) ;
235

236
	void zero() ;
237

238
	void operator= (const QuadricNd<REAL,N>& q) ;
239

240
	QuadricNd& operator+= (const QuadricNd<REAL,N>& q) ;
241

242
	QuadricNd& operator -= (const QuadricNd<REAL,N>& q) ;
243

244
	QuadricNd& operator *= (REAL v) ;
245

246
	QuadricNd& operator /= (REAL v) ;
247

248
	REAL operator() (const VECNp& v) const ;
249

250
	REAL operator() (const VECN& v) const ;
251
252
253

	friend std::ostream& operator<<(std::ostream& out, const QuadricNd<REAL,N>& q)
	{
254
		out << "(" << q.A << ", " << q.b << ", " << q.c << ")" ;
255
		return out ;
256
	} ;
257
258
259

	friend std::istream& operator>>(std::istream& in, QuadricNd<REAL,N>& q)
	{
260
261
262
		in >> q.A ;
		in >> q.b ;
		in >> q.c ;
263
		return in ;
264
	} ;
265

266
	bool findOptimizedVec(VECN& v) ;
267
268

private:
269
270
271
272
	// Double computation is crucial for stability
	Geom::Matrix<N,N,double> A ;
	Geom::Vector<N,double> b ;
	double c ;
273

274
	REAL evaluate(const VECN& v) const ;
275

276
	bool optimize(VECN& v) const ;
277
278
} ;

279
280
281
282
283
284
template <typename REAL>
class QuadricHF
{
public:
	static std::string CGoGNnameOfType() { return "QuadricHF" ; }

285
	typedef Geom::Vector<3,REAL> VEC3 ;
286

287
	QuadricHF() ;
288

289
	QuadricHF(int i) ;
290

291
	QuadricHF(const std::vector<VEC3>& v, const REAL& gamma, const REAL& alpha) ;
292

293
	QuadricHF(const Geom::Tensor3d* T, const REAL& gamma, const REAL& alpha) ;
294

295
	~QuadricHF() ;
296

297
298
299
300
301
302
303
304
305
306
307
308
309
310
	void zero() ;

	QuadricHF& operator= (const QuadricHF<REAL>& q) ;

	QuadricHF& operator+= (const QuadricHF<REAL>& q) ;
	QuadricHF& operator -= (const QuadricHF<REAL>& q) ;

	QuadricHF& operator *= (const REAL& v) ;

	QuadricHF& operator /= (const REAL& v) ;

	//	REAL operator() (const VECNp& v) const ;

	REAL operator() (const std::vector<VEC3>& coefs) const ;
311
312
313

	friend std::ostream& operator<<(std::ostream& out, const QuadricHF<REAL>& q)
	{
314
		// TODO out << "(" << q.m_A << ", " << q.m_b << ", " << q.m_c << ")" ;
315
		return out ;
316
	} ;
317
318
319

	friend std::istream& operator>>(std::istream& in, QuadricHF<REAL>& q)
	{
320
		// TODO
321
322
323
		//		in >> q.A ;
		//		in >> q.b ;
		//		in >> q.c ;
324
		return in ;
325
	} ;
326

327
	bool findOptimizedCoefs(std::vector<VEC3>& coefs) ;
328
329
330

private:
	// Double computation is crucial for stability
331
	Eigen::MatrixXd m_A ;
332
333
	Eigen::VectorXd m_b[3] ;
	double m_c[3] ;
334

335
	REAL evaluate(const std::vector<VEC3>& coefs) const ;
336

337
	bool optimize(std::vector<VEC3>& coefs) const ;
338

339
	Geom::Matrix33d rotateMatrix(const REAL& gamma) ;
340

341
	Geom::Tensor3d rotate(const Geom::Tensor3d& T, const Geom::Matrix33d& R) ;
342

343
344
	Eigen::MatrixXd buildIntegralMatrix_A(const REAL& alpha, unsigned int size) ;
	Eigen::MatrixXd buildIntegralMatrix_B(const REAL& alpha, unsigned int size) ;
345

346
	Eigen::MatrixXd buildIntegralMatrix_C(const REAL& alpha, unsigned int size) ;
347

348
	void fillTensor(Geom::Tensor3d& T) ;
349

350
351
352
	Geom::Tensor3d* tensorsFromCoefs(const std::vector<VEC3>& coefs) ;

	std::vector<VEC3> coefsFromTensors(Geom::Tensor3d* A) ;
353
354
} ;

355
} // Utils
356
357
358

} // CGOGN

359
360
#include "qem.hpp"

Pierre Kraemer's avatar
Pierre Kraemer committed
361
#endif