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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
// Copyright (c) 2005 INRIA (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.2-branch/Surface_mesh_parameterization/include/CGAL/Discrete_conformal_map_parameterizer_3.h $
// $Id: Discrete_conformal_map_parameterizer_3.h 29623 2006-03-20 11:22:05Z lsaboret $
//
//
// Author(s) : Laurent Saboret, Pierre Alliez, Bruno Levy
#ifndef CGAL_DISCRETE_CONFORMAL_MAP_PARAMETERIZER_3_H
#define CGAL_DISCRETE_CONFORMAL_MAP_PARAMETERIZER_3_H
#include <CGAL/Fixed_border_parameterizer_3.h>
#include <CGAL/surface_mesh_parameterization_assertions.h>
CGAL_BEGIN_NAMESPACE
/// The class Discrete_conformal_map_parameterizer_3
/// implements the Discrete Conformal Map (DCM) parameterization [EDD+95].
/// This algorithm is also called "Discrete Conformal Parameterization (DCP)",
/// "Discrete Harmonic Map" or "Fixed Conformal Parameterization" by other authors.
///
/// This is a conformal parameterization, i.e. it attempts to preserve angles.
///
/// One-to-one mapping is guaranteed if surface's border is mapped onto a convex polygon.
///
/// This class is a Strategy [GHJV95] called by the main
/// parameterization algorithm Fixed_border_parameterizer_3::parameterize().
/// Discrete_conformal_map_parameterizer_3:
/// - provides default BorderParameterizer_3 and SparseLinearAlgebraTraits_d template
/// parameters that make sense.
/// - implements compute_w_ij() to compute w_ij = (i, j) coefficient of matrix A
/// for j neighbor vertex of i based on Discrete Conformal Map method.
///
/// Concept: Model of the ParameterizerTraits_3 concept.
///
/// Design Pattern:
/// Discrete_conformal_map_parameterizer_3<ParameterizationMesh_3, ...> class is a
/// Strategy [GHJV95]: it implements a strategy of surface parameterization
/// for models of ParameterizationMesh_3.
///
/// Template parameters:
/// @param ParameterizationMesh_3 3D surface mesh.
/// @param BorderParameterizer_3 Strategy to parameterize the surface border.
/// @param SparseLinearAlgebraTraits_d Traits class to solve a sparse linear system.
/// Note: the system is NOT symmetric because Fixed_border_parameterizer_3
/// does not remove (yet) border vertices from the system.
template
<
class ParameterizationMesh_3,
class BorderParameterizer_3
= Circular_border_arc_length_parameterizer_3<ParameterizationMesh_3>,
class SparseLinearAlgebraTraits_d
= OpenNL::DefaultLinearSolverTraits<typename ParameterizationMesh_3::NT>
>
class Discrete_conformal_map_parameterizer_3
: public Fixed_border_parameterizer_3<ParameterizationMesh_3,
BorderParameterizer_3,
SparseLinearAlgebraTraits_d>
{
// Private types
private:
// Superclass
typedef Fixed_border_parameterizer_3<ParameterizationMesh_3,
BorderParameterizer_3,
SparseLinearAlgebraTraits_d>
Base;
// Public types
public:
// We have to repeat the types exported by superclass
/// @cond SKIP_IN_MANUAL
typedef typename Base::Error_code Error_code;
typedef ParameterizationMesh_3 Adaptor;
typedef BorderParameterizer_3 Border_param;
typedef SparseLinearAlgebraTraits_d Sparse_LA;
/// @endcond
// Private types
private:
// Mesh_Adaptor_3 subtypes:
typedef typename Adaptor::NT NT;
typedef typename Adaptor::Point_2 Point_2;
typedef typename Adaptor::Point_3 Point_3;
typedef typename Adaptor::Vector_2 Vector_2;
typedef typename Adaptor::Vector_3 Vector_3;
typedef typename Adaptor::Facet Facet;
typedef typename Adaptor::Facet_handle Facet_handle;
typedef typename Adaptor::Facet_const_handle
Facet_const_handle;
typedef typename Adaptor::Facet_iterator Facet_iterator;
typedef typename Adaptor::Facet_const_iterator
Facet_const_iterator;
typedef typename Adaptor::Vertex Vertex;
typedef typename Adaptor::Vertex_handle Vertex_handle;
typedef typename Adaptor::Vertex_const_handle
Vertex_const_handle;
typedef typename Adaptor::Vertex_iterator Vertex_iterator;
typedef typename Adaptor::Vertex_const_iterator
Vertex_const_iterator;
typedef typename Adaptor::Border_vertex_iterator
Border_vertex_iterator;
typedef typename Adaptor::Border_vertex_const_iterator
Border_vertex_const_iterator;
typedef typename Adaptor::Vertex_around_facet_circulator
Vertex_around_facet_circulator;
typedef typename Adaptor::Vertex_around_facet_const_circulator
Vertex_around_facet_const_circulator;
typedef typename Adaptor::Vertex_around_vertex_circulator
Vertex_around_vertex_circulator;
typedef typename Adaptor::Vertex_around_vertex_const_circulator
Vertex_around_vertex_const_circulator;
// SparseLinearAlgebraTraits_d subtypes:
typedef typename Sparse_LA::Vector Vector;
typedef typename Sparse_LA::Matrix Matrix;
// Public operations
public:
/// Constructor
Discrete_conformal_map_parameterizer_3(Border_param border_param = Border_param(),
///< Object that maps the surface's border to 2D space.
Sparse_LA sparse_la = Sparse_LA())
///< Traits object to access a sparse linear system.
: Fixed_border_parameterizer_3<Adaptor,
Border_param,
Sparse_LA>(border_param, sparse_la)
{}
// Default copy constructor and operator =() are fine
// Protected operations
protected:
/// Compute w_ij = (i,j) coefficient of matrix A for j neighbor vertex of i.
virtual NT compute_w_ij(const Adaptor& mesh,
Vertex_const_handle main_vertex_v_i,
Vertex_around_vertex_const_circulator neighbor_vertex_v_j)
{
Point_3 position_v_i = mesh.get_vertex_position(main_vertex_v_i);
Point_3 position_v_j = mesh.get_vertex_position(neighbor_vertex_v_j);
// Compute cotangent of (v_i,v_k,v_j) corner (ie cotan of v_k corner)
// if v_k is the vertex before v_j when circulating around v_i
Vertex_around_vertex_const_circulator previous_vertex_v_k = neighbor_vertex_v_j;
previous_vertex_v_k --;
Point_3 position_v_k = mesh.get_vertex_position(previous_vertex_v_k);
double cotg_beta_ij = cotangent(position_v_i, position_v_k, position_v_j);
// Compute cotangent of (v_j,v_l,v_i) corner (ie cotan of v_l corner)
// if v_l is the vertex after v_j when circulating around v_i
Vertex_around_vertex_const_circulator next_vertex_v_l = neighbor_vertex_v_j;
next_vertex_v_l ++;
Point_3 position_v_l = mesh.get_vertex_position(next_vertex_v_l);
double cotg_alpha_ij = cotangent(position_v_j, position_v_l, position_v_i);
double weight = cotg_beta_ij+cotg_alpha_ij;
return weight;
}
};
CGAL_END_NAMESPACE
#endif //CGAL_DISCRETE_CONFORMAL_MAP_PARAMETERIZER_3_H
|
