Blender V5.3
uv_initializer.cpp
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "uv_initializer.h"
10
11#include <Eigen/SparseLU>
12#include <cassert>
13
14namespace slim {
15
16static double compute_angle(const Eigen::Vector3d &a, const Eigen::Vector3d &b)
17{
18 return acos(a.dot(b) / (a.norm() * b.norm()));
19}
20
22 const Eigen::MatrixXi &f,
23 const Eigen::MatrixXd &v,
24 Eigen::SparseMatrix<double> &vertex_to_face_indices)
25{
26 using t = Eigen::Triplet<double>;
27 std::vector<t> coefficients;
28
29 for (int i = 0; i < f.rows(); i++) {
30
31 int vertex_index1 = f(i, 0);
32 int vertex_index2 = f(i, 1);
33 int vertex_index3 = f(i, 2);
34
35 double angle1 = compute_angle(v.row(vertex_index2) - v.row(vertex_index1),
36 v.row(vertex_index3) - v.row(vertex_index1));
37 double angle2 = compute_angle(v.row(vertex_index3) - v.row(vertex_index2),
38 v.row(vertex_index1) - v.row(vertex_index2));
39 double angle3 = compute_angle(v.row(vertex_index1) - v.row(vertex_index3),
40 v.row(vertex_index2) - v.row(vertex_index3));
41
42 coefficients.emplace_back(vertex_index1, 2 * vertex_index2, angle3);
43 coefficients.emplace_back(vertex_index1, 2 * vertex_index3 + 1, angle2);
44
45 coefficients.emplace_back(vertex_index2, 2 * vertex_index1 + 1, angle3);
46 coefficients.emplace_back(vertex_index2, 2 * vertex_index3, angle1);
47
48 coefficients.emplace_back(vertex_index3, 2 * vertex_index1, angle2);
49 coefficients.emplace_back(vertex_index3, 2 * vertex_index2 + 1, angle1);
50 }
51
52 vertex_to_face_indices.setFromTriplets(coefficients.begin(), coefficients.end());
53}
54
56 const Eigen::MatrixXi &f,
57 const Eigen::MatrixXd &v,
58 Eigen::SparseMatrix<double> &vertex_to_face_indices)
59{
60
61 using t = Eigen::Triplet<double>;
62 std::vector<t> coefficients;
63
64 for (int i = 0; i < f.rows(); i++) {
65
66 int vertex_index1 = f(i, 0);
67 int vertex_index2 = f(i, 1);
68 int vertex_index3 = f(i, 2);
69
70 double angle1 = compute_angle(v.row(vertex_index2) - v.row(vertex_index1),
71 v.row(vertex_index3) - v.row(vertex_index1));
72 double angle2 = compute_angle(v.row(vertex_index3) - v.row(vertex_index2),
73 v.row(vertex_index1) - v.row(vertex_index2));
74 double angle3 = compute_angle(v.row(vertex_index1) - v.row(vertex_index3),
75 v.row(vertex_index2) - v.row(vertex_index3));
76
77 coefficients.emplace_back(vertex_index1, 2 * vertex_index2, angle1);
78 coefficients.emplace_back(vertex_index1, 2 * vertex_index3 + 1, angle1);
79
80 coefficients.emplace_back(vertex_index2, 2 * vertex_index1 + 1, angle2);
81 coefficients.emplace_back(vertex_index2, 2 * vertex_index3, angle2);
82
83 coefficients.emplace_back(vertex_index3, 2 * vertex_index1, angle3);
84 coefficients.emplace_back(vertex_index3, 2 * vertex_index2 + 1, angle3);
85 }
86
87 vertex_to_face_indices.setFromTriplets(coefficients.begin(), coefficients.end());
88}
89
90/* Implementation of different fixed-border parameterizations, mean value coordinates, harmonic,
91 * tutte. */
92void convex_border_parameterization(const Eigen::MatrixXi &f,
93 const Eigen::MatrixXd &v,
94 const Eigen::MatrixXi &e,
95 const Eigen::VectorXd &el,
96 const Eigen::VectorXi &bnd,
97 const Eigen::MatrixXd &bnd_uv,
98 Eigen::MatrixXd &uv,
99 Method method)
100{
101 int verts_num = uv.rows();
102 int edges_num = e.rows();
103
104 Eigen::SparseMatrix<double> vertex_to_angles(verts_num, verts_num * 2);
105
106 switch (method) {
107 case HARMONIC:
108 find_vertex_to_opposite_angles_correspondence(f, v, vertex_to_angles);
109 break;
110 case MVC:
111 find_vertex_to_its_angles_correspondence(f, v, vertex_to_angles);
112 break;
113 case TUTTE:
114 break;
115 }
116
117 int n_unknowns = verts_num - bnd.size();
118 int n_knowns = bnd.size();
119
120 Eigen::SparseMatrix<double> aint(n_unknowns, n_unknowns);
121 Eigen::SparseMatrix<double> abnd(n_unknowns, n_knowns);
122 Eigen::VectorXd z(n_knowns);
123
124 std::vector<Eigen::Triplet<double>> int_triplet_vector;
125 std::vector<Eigen::Triplet<double>> bnd_triplet_vector;
126
127 int rowindex;
128 int columnindex;
129 double edge_weight, edge_length;
130 Eigen::RowVector2i edge;
131
132 int first_vertex, second_vertex;
133
134 for (int e_idx = 0; e_idx < edges_num; e_idx++) {
135 edge = e.row(e_idx);
136 edge_length = el(e_idx);
137 first_vertex = edge(0);
138 second_vertex = edge(1);
139
140 if (first_vertex >= n_knowns) {
141 /* Into aint. */
142 rowindex = first_vertex - n_knowns;
143
144 double angle1 = vertex_to_angles.coeff(first_vertex, 2 * second_vertex);
145 double angle2 = vertex_to_angles.coeff(first_vertex, 2 * second_vertex + 1);
146
147 switch (method) {
148 case HARMONIC:
149 edge_weight = 1 / tan(angle1) + 1 / tan(angle2);
150 break;
151 case MVC:
152 edge_weight = tan(angle1 / 2) + tan(angle2 / 2);
153 edge_weight /= edge_length;
154 break;
155 case TUTTE:
156 edge_weight = 1;
157 break;
158 }
159
160 int_triplet_vector.emplace_back(rowindex, rowindex, edge_weight);
161
162 if (second_vertex >= n_knowns) {
163 /* Also an unknown point in the interior. */
164 columnindex = second_vertex - n_knowns;
165
166 int_triplet_vector.emplace_back(rowindex, columnindex, -edge_weight);
167 }
168 else {
169 /* Known point on the border. */
170 columnindex = second_vertex;
171 bnd_triplet_vector.emplace_back(rowindex, columnindex, edge_weight);
172 }
173 }
174 }
175
176 aint.setFromTriplets(int_triplet_vector.begin(), int_triplet_vector.end());
177 aint.makeCompressed();
178
179 abnd.setFromTriplets(bnd_triplet_vector.begin(), bnd_triplet_vector.end());
180 abnd.makeCompressed();
181
182 for (int i = 0; i < n_unknowns; i++) {
183 double factor = aint.coeff(i, i);
184 aint.row(i) /= factor;
185 abnd.row(i) /= factor;
186 }
187
188 Eigen::SparseLU<Eigen::SparseMatrix<double>> solver;
189 solver.compute(aint);
190
191 for (int i = 0; i < 2; i++) {
192
193 for (int zindex = 0; zindex < n_knowns; zindex++) {
194 z(zindex) = bnd_uv(bnd(zindex), i);
195 }
196
197 Eigen::VectorXd b = abnd * z;
198
199 Eigen::VectorXd uvs;
200 uvs = solver.solve(b);
201
202 Eigen::VectorXd boundary = bnd_uv.col(i);
203 Eigen::VectorXd interior = uvs;
204
205 uv.col(i) << boundary, interior;
206 }
207}
208
209void mvc(const Eigen::MatrixXi &f,
210 const Eigen::MatrixXd &v,
211 const Eigen::MatrixXi &e,
212 const Eigen::VectorXd &el,
213 const Eigen::VectorXi &bnd,
214 const Eigen::MatrixXd &bnd_uv,
215 Eigen::MatrixXd &uv)
216{
217
218 convex_border_parameterization(f, v, e, el, bnd, bnd_uv, uv, Method::MVC);
219}
220
221void harmonic(const Eigen::MatrixXi &f,
222 const Eigen::MatrixXd &v,
223 const Eigen::MatrixXi &e,
224 const Eigen::VectorXd &el,
225 const Eigen::VectorXi &bnd,
226 const Eigen::MatrixXd &bnd_uv,
227 Eigen::MatrixXd &uv)
228{
229
230 convex_border_parameterization(f, v, e, el, bnd, bnd_uv, uv, Method::HARMONIC);
231}
232
233void tutte(const Eigen::MatrixXi &f,
234 const Eigen::MatrixXd &v,
235 const Eigen::MatrixXi &e,
236 const Eigen::VectorXd &el,
237 const Eigen::VectorXi &bnd,
238 const Eigen::MatrixXd &bnd_uv,
239 Eigen::MatrixXd &uv)
240{
241
242 convex_border_parameterization(f, v, e, el, bnd, bnd_uv, uv, Method::TUTTE);
243}
244
245void map_vertices_to_convex_border(Eigen::MatrixXd &vertex_positions)
246{
247 double pi = atan(1) * 4;
248 int boundary_vertices_num = vertex_positions.rows();
249 double x, y;
250 double angle = 2 * pi / boundary_vertices_num;
251
252 for (int i = 0; i < boundary_vertices_num; i++) {
253 x = cos(angle * i);
254 y = sin(angle * i);
255 vertex_positions(i, 0) = (x * 0.5) + 0.5;
256 vertex_positions(i, 1) = (y * 0.5) + 0.5;
257 }
258}
259
260static void get_flips(const Eigen::MatrixXi &f,
261 const Eigen::MatrixXd &uv,
262 std::vector<int> &flip_idx)
263{
264 flip_idx.resize(0);
265 for (int i = 0; i < f.rows(); i++) {
266
267 Eigen::Vector2d v1_n = uv.row(f(i, 0));
268 Eigen::Vector2d v2_n = uv.row(f(i, 1));
269 Eigen::Vector2d v3_n = uv.row(f(i, 2));
270
271 Eigen::MatrixXd t2_homo(3, 3);
272 t2_homo.col(0) << v1_n(0), v1_n(1), 1;
273 t2_homo.col(1) << v2_n(0), v2_n(1), 1;
274 t2_homo.col(2) << v3_n(0), v3_n(1), 1;
275 double det = t2_homo.determinant();
276 assert(det == det);
277 if (det < 0) {
278 flip_idx.push_back(i);
279 }
280 }
281}
282
283int count_flips(const Eigen::MatrixXi &f, const Eigen::MatrixXd &uv)
284{
285
286 std::vector<int> flip_idx;
287 get_flips(f, uv, flip_idx);
288
289 return flip_idx.size();
290}
291
292} // namespace slim
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
Definition btQuadWord.h:117
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
#define assert(assertion)
#define atan
#define tan
#define sin
#define cos
#define acos
void map_vertices_to_convex_border(Eigen::MatrixXd &vertex_positions)
void tutte(const Eigen::MatrixXi &f, const Eigen::MatrixXd &v, const Eigen::MatrixXi &e, const Eigen::VectorXd &el, const Eigen::VectorXi &bnd, const Eigen::MatrixXd &bnd_uv, Eigen::MatrixXd &uv)
static void get_flips(const Eigen::MatrixXi &f, const Eigen::MatrixXd &uv, std::vector< int > &flip_idx)
int count_flips(const Eigen::MatrixXi &f, const Eigen::MatrixXd &uv)
static double compute_angle(const Eigen::Vector3d &a, const Eigen::Vector3d &b)
static void find_vertex_to_its_angles_correspondence(const Eigen::MatrixXi &f, const Eigen::MatrixXd &v, Eigen::SparseMatrix< double > &vertex_to_face_indices)
void mvc(const Eigen::MatrixXi &f, const Eigen::MatrixXd &v, const Eigen::MatrixXi &e, const Eigen::VectorXd &el, const Eigen::VectorXi &bnd, const Eigen::MatrixXd &bnd_uv, Eigen::MatrixXd &uv)
static void find_vertex_to_opposite_angles_correspondence(const Eigen::MatrixXi &f, const Eigen::MatrixXd &v, Eigen::SparseMatrix< double > &vertex_to_face_indices)
void convex_border_parameterization(const Eigen::MatrixXi &f, const Eigen::MatrixXd &v, const Eigen::MatrixXi &e, const Eigen::VectorXd &el, const Eigen::VectorXi &bnd, const Eigen::MatrixXd &bnd_uv, Eigen::MatrixXd &uv, Method method)
void harmonic(const Eigen::MatrixXi &f, const Eigen::MatrixXd &v, const Eigen::MatrixXi &e, const Eigen::VectorXd &el, const Eigen::VectorXi &bnd, const Eigen::MatrixXd &bnd_uv, Eigen::MatrixXd &uv)
Method
@ HARMONIC
@ TUTTE
@ MVC