Blender V5.3
mesh_fair.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include "BLI_map.hh"
12#include "BLI_math_geom_c.hh"
13#include "BLI_math_vector_c.hh"
14#include "BLI_vector.hh"
15
16#include "BKE_mesh.hh"
17#include "BKE_mesh_fair.hh"
18
19#include "eigen_capi.h"
20
21namespace blender {
22
23using std::array;
24
26 public:
27 virtual float weight_at_index(const int index) const = 0;
28 virtual ~VertexWeight() = default;
29};
30
32 public:
33 virtual float weight_at_index(const int index) const = 0;
34 virtual ~LoopWeight() = default;
35};
36
38 public:
39 /* Get coordinates of vertices which are adjacent to the loop with specified index. */
40 virtual void adjacents_coords_from_loop(const int loop,
41 float r_adj_next[3],
42 float r_adj_prev[3]) = 0;
43
44 /* Get the other vertex index for a loop. */
45 virtual int other_vertex_index_from_loop(const int loop, const int v) = 0;
46
48 {
49 return totvert_;
50 }
51
53 {
54 return totvert_;
55 }
56
58 {
59 return vlmap_[v];
60 }
61
62 float *vertex_deformation_co_get(const int v)
63 {
64 return co_[v];
65 }
66
67 virtual ~FairingContext() = default;
68
69 void fair_verts(const bool affected_verts[],
70 const eMeshFairingDepth depth,
71 const VertexWeight &vertex_weight,
72 const LoopWeight &loop_weight)
73 {
74 fair_verts_ex(affected_verts, int(depth), vertex_weight, loop_weight);
75 }
76
77 protected:
79
82
84
85 private:
86 void fair_setup_fairing(const int v,
87 const int i,
88 LinearSolver *solver,
89 float multiplier,
90 const int depth,
91 Map<int, int> &vert_col_map,
92 const VertexWeight &vertex_weight,
93 const LoopWeight &loop_weight)
94 {
95 if (depth == 0) {
96 if (vert_col_map.contains(v)) {
97 const int j = vert_col_map.lookup(v);
98 EIG_linear_solver_matrix_add(solver, i, j, -multiplier);
99 return;
100 }
101 for (int j = 0; j < 3; j++) {
102 EIG_linear_solver_right_hand_side_add(solver, j, i, multiplier * co_[v][j]);
103 }
104 return;
105 }
106
107 float w_ij_sum = 0;
108 const float w_i = vertex_weight.weight_at_index(v);
109 const Span<int> vlmap_elem = vlmap_[v];
110 for (const int l : vlmap_elem.index_range()) {
111 const int l_index = vlmap_elem[l];
112 const int other_vert = other_vertex_index_from_loop(l_index, v);
113 const float w_ij = loop_weight.weight_at_index(l_index);
114 w_ij_sum += w_ij;
115 fair_setup_fairing(other_vert,
116 i,
117 solver,
118 w_i * w_ij * multiplier,
119 depth - 1,
120 vert_col_map,
121 vertex_weight,
122 loop_weight);
123 }
124 fair_setup_fairing(v,
125 i,
126 solver,
127 -1 * w_i * w_ij_sum * multiplier,
128 depth - 1,
129 vert_col_map,
130 vertex_weight,
131 loop_weight);
132 }
133
134 void fair_verts_ex(const bool affected_verts[],
135 const int order,
136 const VertexWeight &vertex_weight,
137 const LoopWeight &loop_weight)
138 {
139 Map<int, int> vert_col_map;
140 int affected_verts_num = 0;
141 for (int i = 0; i < totvert_; i++) {
142 if (!affected_verts[i]) {
143 continue;
144 }
145 vert_col_map.add(i, affected_verts_num);
146 affected_verts_num++;
147 }
148
149 /* Early return, nothing to do. */
150 if (ELEM(affected_verts_num, 0, totvert_)) {
151 return;
152 }
153
154 /* Setup fairing matrices */
155 LinearSolver *solver = EIG_linear_solver_new(affected_verts_num, affected_verts_num, 3);
156 for (auto item : vert_col_map.items()) {
157 const int v = item.key;
158 const int col = item.value;
159 fair_setup_fairing(v, col, solver, 1.0f, order, vert_col_map, vertex_weight, loop_weight);
160 }
161
162 /* Solve linear system */
164
165 /* Copy the result back to the mesh */
166 for (auto item : vert_col_map.items()) {
167 const int v = item.key;
168 const int col = item.value;
169 for (int j = 0; j < 3; j++) {
170 co_[v][j] = EIG_linear_solver_variable_get(solver, j, col);
171 }
172 }
173
174 /* Free solver data */
176 }
177};
178
180 public:
182 {
183 totvert_ = mesh->verts_num;
184 totloop_ = mesh->corners_num;
185
186 MutableSpan<float3> positions = mesh->vert_positions_for_write();
187 edges_ = mesh->edges();
188 faces = mesh->faces();
189 corner_verts_ = mesh->corner_verts();
190 corner_edges_ = mesh->corner_edges();
191 vlmap_ = mesh->vert_to_corner_map();
192
193 /* Deformation coords. */
194 co_.resize(mesh->verts_num);
195 if (!deform_positions.is_empty()) {
196 for (int i = 0; i < mesh->verts_num; i++) {
197 co_[i] = deform_positions[i];
198 }
199 }
200 else {
201 for (int i = 0; i < mesh->verts_num; i++) {
202 co_[i] = positions[i];
203 }
204 }
205
206 loop_to_face_map_ = mesh->corner_to_face_map();
207 }
208
209 void adjacents_coords_from_loop(const int loop,
210 float r_adj_next[3],
211 float r_adj_prev[3]) override
212 {
213 const int vert = corner_verts_[loop];
214 const IndexRange face = faces[loop_to_face_map_[loop]];
215 const int2 adjacent_verts = bke::mesh::face_find_adjacent_verts(face, corner_verts_, vert);
216 copy_v3_v3(r_adj_next, co_[adjacent_verts[0]]);
217 copy_v3_v3(r_adj_prev, co_[adjacent_verts[1]]);
218 }
219
220 int other_vertex_index_from_loop(const int loop, const int v) override
221 {
222 const int2 &edge = edges_[corner_edges_[loop]];
223 return bke::mesh::edge_other_vert(edge, v);
224 }
225
226 protected:
233};
234
236 public:
238 {
239 const int totvert = fairing_context.vertex_count_get();
240 vertex_weights_.resize(totvert);
241 for (int i = 0; i < totvert; i++) {
242 const int tot_loop = fairing_context.vertex_loop_map_get(i).size();
243 if (tot_loop != 0) {
244 vertex_weights_[i] = 1.0f / tot_loop;
245 }
246 else {
247 vertex_weights_[i] = FLT_MAX;
248 }
249 }
250 }
251
252 float weight_at_index(const int index) const override
253 {
254 return vertex_weights_[index];
255 }
256
257 private:
258 Vector<float> vertex_weights_;
259};
260
262
263 public:
265 {
266
267 const int totvert = fairing_context.vertex_count_get();
268 vertex_weights_.resize(totvert);
269 for (int i = 0; i < totvert; i++) {
270
271 float area = 0.0f;
272 float a[3];
273 copy_v3_v3(a, fairing_context.vertex_deformation_co_get(i));
274 const float acute_threshold = M_PI_2;
275
276 const Span<int> vlmap_elem = fairing_context.vertex_loop_map_get(i);
277 for (const int l : vlmap_elem.index_range()) {
278 const int l_index = vlmap_elem[l];
279
280 float b[3], c[3], d[3];
281 fairing_context.adjacents_coords_from_loop(l_index, b, c);
282
283 if (angle_v3v3v3(c, fairing_context.vertex_deformation_co_get(i), b) < acute_threshold) {
284 calc_circumcenter(d, a, b, c);
285 }
286 else {
287 add_v3_v3v3(d, b, c);
288 mul_v3_fl(d, 0.5f);
289 }
290
291 float t[3];
292 add_v3_v3v3(t, a, b);
293 mul_v3_fl(t, 0.5f);
294 area += area_tri_v3(a, t, d);
295
296 add_v3_v3v3(t, a, c);
297 mul_v3_fl(t, 0.5f);
298 area += area_tri_v3(a, d, t);
299 }
300
301 vertex_weights_[i] = area != 0.0f ? 1.0f / area : 1e12;
302 }
303 }
304
305 float weight_at_index(const int index) const override
306 {
307 return vertex_weights_[index];
308 }
309
310 private:
311 Vector<float> vertex_weights_;
312
313 void calc_circumcenter(float r[3], const float a[3], const float b[3], const float c[3])
314 {
315 float ab[3];
316 sub_v3_v3v3(ab, b, a);
317
318 float ac[3];
319 sub_v3_v3v3(ac, c, a);
320
321 float ab_cross_ac[3];
322 cross_v3_v3v3(ab_cross_ac, ab, ac);
323
324 if (len_squared_v3(ab_cross_ac) > 0.0f) {
325 float d[3];
326 cross_v3_v3v3(d, ab_cross_ac, ab);
328
329 float t[3];
330 cross_v3_v3v3(t, ac, ab_cross_ac);
332
333 add_v3_v3(d, t);
334
335 mul_v3_fl(d, 1.0f / (2.0f * len_squared_v3(ab_cross_ac)));
336
337 add_v3_v3v3(r, a, d);
338 return;
339 }
340 copy_v3_v3(r, a);
341 }
342};
343
345 public:
346 float weight_at_index(const int /*index*/) const override
347 {
348 return 1.0f;
349 }
350};
351
352static void prefair_and_fair_verts(FairingContext &fairing_context,
353 const bool affected_verts[],
354 const eMeshFairingDepth depth)
355{
356 /* Pre-fair. */
357 UniformVertexWeight uniform_vertex_weights(fairing_context);
358 UniformLoopWeight uniform_loop_weights;
359 fairing_context.fair_verts(affected_verts, depth, uniform_vertex_weights, uniform_loop_weights);
360
361 /* Fair. */
362 VoronoiVertexWeight voronoi_vertex_weights(fairing_context);
363 /* TODO: Implement cotangent loop weights. */
364 fairing_context.fair_verts(affected_verts, depth, voronoi_vertex_weights, uniform_loop_weights);
365}
366
368 MutableSpan<float3> deform_vert_positions,
369 const bool affected_verts[],
370 const eMeshFairingDepth depth)
371{
372 MutableSpan<float3> deform_positions_span;
373 if (!deform_vert_positions.is_empty()) {
374 deform_positions_span = deform_vert_positions;
375 }
376 MeshFairingContext fairing_context(mesh, deform_positions_span);
377 prefair_and_fair_verts(fairing_context, affected_verts, depth);
378}
379
380} // namespace blender
#define M_PI_2
#define ELEM(...)
Span< int > vertex_loop_map_get(const int v)
Definition mesh_fair.cc:57
virtual int other_vertex_index_from_loop(const int loop, const int v)=0
virtual void adjacents_coords_from_loop(const int loop, float r_adj_next[3], float r_adj_prev[3])=0
float * vertex_deformation_co_get(const int v)
Definition mesh_fair.cc:62
GroupedSpan< int > vlmap_
Definition mesh_fair.cc:83
Vector< float * > co_
Definition mesh_fair.cc:78
void fair_verts(const bool affected_verts[], const eMeshFairingDepth depth, const VertexWeight &vertex_weight, const LoopWeight &loop_weight)
Definition mesh_fair.cc:69
virtual ~FairingContext()=default
virtual ~LoopWeight()=default
virtual float weight_at_index(const int index) const =0
bool add(const Key &key, const Value &value)
Definition BLI_map.hh:295
const Value & lookup(const Key &key) const
Definition BLI_map.hh:545
bool contains(const Key &key) const
Definition BLI_map.hh:353
ItemIterator items() const &
Definition BLI_map.hh:902
MeshFairingContext(Mesh *mesh, MutableSpan< float3 > deform_positions)
Definition mesh_fair.cc:181
int other_vertex_index_from_loop(const int loop, const int v) override
Definition mesh_fair.cc:220
void adjacents_coords_from_loop(const int loop, float r_adj_next[3], float r_adj_prev[3]) override
Definition mesh_fair.cc:209
OffsetIndices< int > faces
Definition mesh_fair.cc:230
constexpr bool is_empty() const
Definition BLI_span.hh:515
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
float weight_at_index(const int) const override
Definition mesh_fair.cc:346
UniformVertexWeight(FairingContext &fairing_context)
Definition mesh_fair.cc:237
float weight_at_index(const int index) const override
Definition mesh_fair.cc:252
void resize(const int64_t new_size)
virtual float weight_at_index(const int index) const =0
virtual ~VertexWeight()=default
VoronoiVertexWeight(FairingContext &fairing_context)
Definition mesh_fair.cc:264
float weight_at_index(const int index) const override
Definition mesh_fair.cc:305
#define FLT_MAX
LinearSolver * EIG_linear_solver_new(int num_rows, int num_columns, int num_right_hand_sides)
void EIG_linear_solver_right_hand_side_add(LinearSolver *solver, int rhs, int index, double value)
void EIG_linear_solver_delete(LinearSolver *solver)
double EIG_linear_solver_variable_get(LinearSolver *solver, int rhs, int index)
void EIG_linear_solver_matrix_add(LinearSolver *solver, int row, int col, double value)
bool EIG_linear_solver_solve(LinearSolver *solver)
ccl_device_inline void copy_v3_v3(ccl_private float *r, const float3 val)
int edge_other_vert(const int2 edge, const int vert)
Definition BKE_mesh.hh:370
int2 face_find_adjacent_verts(const IndexRange face, const Span< int > corner_verts, const int vert)
Definition BKE_mesh.hh:338
BMesh Iterators.
void BKE_mesh_prefair_and_fair_verts(Mesh *mesh, MutableSpan< float3 > deform_vert_positions, const bool affected_verts[], eMeshFairingDepth depth)
Definition mesh_fair.cc:367
MINLINE void copy_v3_v3(float r[3], const float a[3])
ATTR_WARN_UNUSED_RESULT const BMLoop * l
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
float angle_v3v3v3(const float a[3], const float b[3], const float c[3]) ATTR_WARN_UNUSED_RESULT
ATTR_WARN_UNUSED_RESULT const BMVert * v
MINLINE void mul_v3_fl(float r[3], float f)
VecBase< int32_t, 2 > int2
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
static void prefair_and_fair_verts(FairingContext &fairing_context, const bool affected_verts[], const eMeshFairingDepth depth)
Definition mesh_fair.cc:352
MINLINE void add_v3_v3(float r[3], const float a[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:104
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT