Blender V5.3
bmo_smooth_laplacian.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 "MEM_guardedalloc.h"
12
13#include "BLI_math_geom_c.hh"
14#include "BLI_math_vector_c.hh"
15
16#include "eigen_capi.h"
17
18#include "bmesh.hh"
19
20#include "intern/bmesh_operators_private.hh" /* own include */
21
22namespace blender {
23
24// #define SMOOTH_LAPLACIAN_AREA_FACTOR 4.0f /* UNUSED */
25// #define SMOOTH_LAPLACIAN_EDGE_FACTOR 2.0f /* UNUSED */
26#define SMOOTH_LAPLACIAN_MAX_EDGE_PERCENTAGE 1.8f
27#define SMOOTH_LAPLACIAN_MIN_EDGE_PERCENTAGE 0.15f
28
30 float *eweights; /* Length weights per Edge. */
31 float (*fweights)[3]; /* Cotangent weights per loop. */
32 float *ring_areas; /* Total area per ring. */
33 float *vlengths; /* Total sum of lengths(edges) per vertex. */
34 float *vweights; /* Total sum of weights per vertex. */
35 int numEdges; /* Number of edges. */
36 int numLoops; /* Number of loops. */
37 int numVerts; /* Number of verts. */
38 bool *zerola; /* Is zero area or length. */
39
40 /* Pointers to data. */
44
45 /* Data. */
46 float min_area;
47};
49
50static bool vert_is_boundary(BMVert *v);
51static LaplacianSystem *init_laplacian_system(int a_numEdges, int a_numLoops, int a_numVerts);
54static void delete_void_pointer(void *data);
56static void memset_laplacian_system(LaplacianSystem *sys, int val);
57static void validate_solution(
58 LaplacianSystem *sys, int usex, int usey, int usez, int preserve_volume);
59static void volume_preservation(
60 BMOperator *op, float vini, float vend, int usex, int usey, int usez);
61
62static void delete_void_pointer(void *data)
63{
64 if (data) {
66 }
67}
68
70{
71 delete_void_pointer(sys->eweights);
73 delete_void_pointer(sys->ring_areas);
74 delete_void_pointer(sys->vlengths);
75 delete_void_pointer(sys->vweights);
76 delete_void_pointer(sys->zerola);
77 if (sys->context) {
79 }
80 sys->bm = nullptr;
81 sys->op = nullptr;
82 MEM_delete(sys);
83}
84
85static void memset_laplacian_system(LaplacianSystem *sys, int val)
86{
87 memset(sys->eweights, val, sizeof(float) * sys->numEdges);
88 memset(sys->fweights, val, sizeof(float[3]) * sys->numLoops);
89 memset(sys->ring_areas, val, sizeof(float) * sys->numVerts);
90 memset(sys->vlengths, val, sizeof(float) * sys->numVerts);
91 memset(sys->vweights, val, sizeof(float) * sys->numVerts);
92 memset(sys->zerola, val, sizeof(bool) * sys->numVerts);
93}
94
95static LaplacianSystem *init_laplacian_system(int a_numEdges, int a_numLoops, int a_numVerts)
96{
97 LaplacianSystem *sys;
98 sys = MEM_new_zeroed<LaplacianSystem>("ModLaplSmoothSystem");
99 sys->numEdges = a_numEdges;
100 sys->numLoops = a_numLoops;
101 sys->numVerts = a_numVerts;
102
103 sys->eweights = MEM_new_array_zeroed<float>(sys->numEdges, "ModLaplSmoothEWeight");
104 if (!sys->eweights) {
106 return nullptr;
107 }
108
109 sys->fweights = MEM_new_array_zeroed<float[3]>(sys->numLoops, "ModLaplSmoothFWeight");
110 if (!sys->fweights) {
112 return nullptr;
113 }
114
115 sys->ring_areas = MEM_new_array_zeroed<float>(sys->numVerts, "ModLaplSmoothRingAreas");
116 if (!sys->ring_areas) {
118 return nullptr;
119 }
120
121 sys->vlengths = MEM_new_array_zeroed<float>(sys->numVerts, "ModLaplSmoothVlengths");
122 if (!sys->vlengths) {
124 return nullptr;
125 }
126
127 sys->vweights = MEM_new_array_zeroed<float>(sys->numVerts, "ModLaplSmoothVweights");
128 if (!sys->vweights) {
130 return nullptr;
131 }
132
133 sys->zerola = MEM_new_array_zeroed<bool>(sys->numVerts, "ModLaplSmoothZeloa");
134 if (!sys->zerola) {
136 return nullptr;
137 }
138
139 return sys;
140}
141
157
159{
160 BMEdge *e;
161 BMFace *f;
162 BMIter eiter;
163 BMIter fiter;
164 uint i;
165
166 BM_ITER_MESH_INDEX (e, &eiter, sys->bm, BM_EDGES_OF_MESH, i) {
168 continue;
169 }
170
171 const float *v1 = e->v1->co;
172 const float *v2 = e->v2->co;
173 const int idv1 = BM_elem_index_get(e->v1);
174 const int idv2 = BM_elem_index_get(e->v2);
175
176 float w1 = len_v3v3(v1, v2);
177 if (w1 > sys->min_area) {
178 w1 = 1.0f / w1;
179 sys->eweights[i] = w1;
180 sys->vlengths[idv1] += w1;
181 sys->vlengths[idv2] += w1;
182 }
183 else {
184 sys->zerola[idv1] = true;
185 sys->zerola[idv2] = true;
186 }
187 }
188
189 uint l_curr_index = 0;
190
191 BM_ITER_MESH (f, &fiter, sys->bm, BM_FACES_OF_MESH) {
193 l_curr_index += f->len;
194 continue;
195 }
196
197 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
198 BMLoop *l_iter;
199
200 l_iter = l_first;
201 do {
202 const int vi_prev = BM_elem_index_get(l_iter->prev->v);
203 const int vi_curr = BM_elem_index_get(l_iter->v);
204 const int vi_next = BM_elem_index_get(l_iter->next->v);
205
206 const float *co_prev = l_iter->prev->v->co;
207 const float *co_curr = l_iter->v->co;
208 const float *co_next = l_iter->next->v->co;
209
210 const float areaf = area_tri_v3(co_prev, co_curr, co_next);
211
212 if (areaf < sys->min_area) {
213 sys->zerola[vi_curr] = true;
214 }
215
216 sys->ring_areas[vi_prev] += areaf;
217 sys->ring_areas[vi_curr] += areaf;
218 sys->ring_areas[vi_next] += areaf;
219
220 const float w1 = cotangent_tri_weight_v3(co_curr, co_next, co_prev) / 2.0f;
221 const float w2 = cotangent_tri_weight_v3(co_next, co_prev, co_curr) / 2.0f;
222 const float w3 = cotangent_tri_weight_v3(co_prev, co_curr, co_next) / 2.0f;
223
224 sys->fweights[l_curr_index][0] += w1;
225 sys->fweights[l_curr_index][1] += w2;
226 sys->fweights[l_curr_index][2] += w3;
227
228 sys->vweights[vi_prev] += w1 + w2;
229 sys->vweights[vi_curr] += w2 + w3;
230 sys->vweights[vi_next] += w1 + w3;
231 } while ((void)(l_curr_index += 1), (l_iter = l_iter->next) != l_first);
232 }
233}
234
236{
237 BMEdge *e;
238 BMFace *f;
239 BMIter eiter;
240 BMIter fiter;
241 int i;
242
243 uint l_curr_index = 0;
244
245 BM_ITER_MESH (f, &fiter, sys->bm, BM_FACES_OF_MESH) {
247 l_curr_index += f->len;
248 continue;
249 }
250
251 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
252 BMLoop *l_iter = l_first;
253
254 int vi_prev = BM_elem_index_get(l_iter->prev->v);
255 int vi_curr = BM_elem_index_get(l_iter->v);
256
257 bool ok_prev = (sys->zerola[vi_prev] == false) && !vert_is_boundary(l_iter->prev->v);
258 bool ok_curr = (sys->zerola[vi_curr] == false) && !vert_is_boundary(l_iter->v);
259
260 do {
261 const int vi_next = BM_elem_index_get(l_iter->next->v);
262 const bool ok_next = (sys->zerola[vi_next] == false) && !vert_is_boundary(l_iter->next->v);
263
264 if (ok_prev) {
266 vi_prev,
267 vi_curr,
268 sys->fweights[l_curr_index][1] * sys->vweights[vi_prev]);
270 vi_prev,
271 vi_next,
272 sys->fweights[l_curr_index][0] * sys->vweights[vi_prev]);
273 }
274 if (ok_curr) {
276 vi_curr,
277 vi_next,
278 sys->fweights[l_curr_index][2] * sys->vweights[vi_curr]);
280 vi_curr,
281 vi_prev,
282 sys->fweights[l_curr_index][1] * sys->vweights[vi_curr]);
283 }
284 if (ok_next) {
286 vi_next,
287 vi_curr,
288 sys->fweights[l_curr_index][2] * sys->vweights[vi_next]);
290 vi_next,
291 vi_prev,
292 sys->fweights[l_curr_index][0] * sys->vweights[vi_next]);
293 }
294
295 vi_prev = vi_curr;
296 vi_curr = vi_next;
297
298 ok_prev = ok_curr;
299 ok_curr = ok_next;
300
301 } while ((void)(l_curr_index += 1), (l_iter = l_iter->next) != l_first);
302 }
303 BM_ITER_MESH_INDEX (e, &eiter, sys->bm, BM_EDGES_OF_MESH, i) {
305 continue;
306 }
307 const uint idv1 = BM_elem_index_get(e->v1);
308 const uint idv2 = BM_elem_index_get(e->v2);
309 if (sys->zerola[idv1] == false && sys->zerola[idv2] == false) {
311 sys->context, idv1, idv2, sys->eweights[i] * sys->vlengths[idv1]);
313 sys->context, idv2, idv1, sys->eweights[i] * sys->vlengths[idv2]);
314 }
315 }
316}
317
319{
320 BMEdge *ed;
321 BMFace *f;
322 BMIter ei;
323 BMIter fi;
325 if (BM_edge_is_boundary(ed)) {
326 return true;
327 }
328 }
329 BM_ITER_ELEM (f, &fi, v, BM_FACES_OF_VERT) {
331 return true;
332 }
333 }
334 return false;
335}
336
338 BMOperator *op, float vini, float vend, int usex, int usey, int usez)
339{
340 float beta;
341 BMOIter siter;
342 BMVert *v;
343
344 if (vend != 0.0f) {
345 beta = pow(vini / vend, 1.0f / 3.0f);
346 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
347 if (usex) {
348 v->co[0] *= beta;
349 }
350 if (usey) {
351 v->co[1] *= beta;
352 }
353 if (usez) {
354 v->co[2] *= beta;
355 }
356 }
357 }
358}
359
361 LaplacianSystem *sys, int usex, int usey, int usez, int preserve_volume)
362{
363 int m_vertex_id;
364 float leni, lene;
365 float vini, vend;
366 float *vi1, *vi2, ve1[3], ve2[3];
367 uint idv1, idv2;
368 BMOIter siter;
369 BMVert *v;
370 BMEdge *e;
371 BMIter eiter;
372
373 BM_ITER_MESH (e, &eiter, sys->bm, BM_EDGES_OF_MESH) {
374 idv1 = BM_elem_index_get(e->v1);
375 idv2 = BM_elem_index_get(e->v2);
376 vi1 = e->v1->co;
377 vi2 = e->v2->co;
378 ve1[0] = EIG_linear_solver_variable_get(sys->context, 0, idv1);
379 ve1[1] = EIG_linear_solver_variable_get(sys->context, 1, idv1);
380 ve1[2] = EIG_linear_solver_variable_get(sys->context, 2, idv1);
381 ve2[0] = EIG_linear_solver_variable_get(sys->context, 0, idv2);
382 ve2[1] = EIG_linear_solver_variable_get(sys->context, 1, idv2);
383 ve2[2] = EIG_linear_solver_variable_get(sys->context, 2, idv2);
384 leni = len_v3v3(vi1, vi2);
385 lene = len_v3v3(ve1, ve2);
386 if (lene > leni * SMOOTH_LAPLACIAN_MAX_EDGE_PERCENTAGE ||
388 {
389 sys->zerola[idv1] = true;
390 sys->zerola[idv2] = true;
391 }
392 }
393
394 if (preserve_volume) {
395 vini = BM_mesh_calc_volume(sys->bm, false);
396 }
397 BMO_ITER (v, &siter, sys->op->slots_in, "verts", BM_VERT) {
398 m_vertex_id = BM_elem_index_get(v);
399 if (sys->zerola[m_vertex_id] == false) {
400 if (usex) {
401 v->co[0] = EIG_linear_solver_variable_get(sys->context, 0, m_vertex_id);
402 }
403 if (usey) {
404 v->co[1] = EIG_linear_solver_variable_get(sys->context, 1, m_vertex_id);
405 }
406 if (usez) {
407 v->co[2] = EIG_linear_solver_variable_get(sys->context, 2, m_vertex_id);
408 }
409 }
410 }
411 if (preserve_volume) {
412 vend = BM_mesh_calc_volume(sys->bm, false);
413 volume_preservation(sys->op, vini, vend, usex, usey, usez);
414 }
415}
416
418{
419 int i;
420 int m_vertex_id;
421 bool usex, usey, usez, preserve_volume;
422 float lambda_factor, lambda_border;
423 float w;
424 BMOIter siter;
425 BMVert *v;
426 LaplacianSystem *sys;
427
428 if (bm->totface == 0) {
429 return;
430 }
432 if (!sys) {
433 return;
434 }
435 sys->bm = bm;
436 sys->op = op;
437
439
441 lambda_factor = BMO_slot_float_get(op->slots_in, "lambda_factor");
442 lambda_border = BMO_slot_float_get(op->slots_in, "lambda_border");
443 sys->min_area = 0.00001f;
444 usex = BMO_slot_bool_get(op->slots_in, "use_x");
445 usey = BMO_slot_bool_get(op->slots_in, "use_y");
446 usez = BMO_slot_bool_get(op->slots_in, "use_z");
447 preserve_volume = BMO_slot_bool_get(op->slots_in, "preserve_volume");
448
450
451 for (i = 0; i < bm->totvert; i++) {
453 }
454 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
455 m_vertex_id = BM_elem_index_get(v);
457 EIG_linear_solver_variable_set(sys->context, 0, m_vertex_id, v->co[0]);
458 EIG_linear_solver_variable_set(sys->context, 1, m_vertex_id, v->co[1]);
459 EIG_linear_solver_variable_set(sys->context, 2, m_vertex_id, v->co[2]);
460 }
461
463 BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
464 m_vertex_id = BM_elem_index_get(v);
465 EIG_linear_solver_right_hand_side_add(sys->context, 0, m_vertex_id, v->co[0]);
466 EIG_linear_solver_right_hand_side_add(sys->context, 1, m_vertex_id, v->co[1]);
467 EIG_linear_solver_right_hand_side_add(sys->context, 2, m_vertex_id, v->co[2]);
468 i = m_vertex_id;
469 if ((sys->zerola[i] == false) &&
470 /* Non zero check is to account for vertices that aren't connected to a selected face.
471 * Without this wire edges become `nan`, see #89214. */
472 (sys->ring_areas[i] != 0.0f))
473 {
474 w = sys->vweights[i] * sys->ring_areas[i];
475 sys->vweights[i] = (w == 0.0f) ? 0.0f : -lambda_factor / (4.0f * w);
476 w = sys->vlengths[i];
477 sys->vlengths[i] = (w == 0.0f) ? 0.0f : -lambda_border * 2.0f / w;
478
479 if (!vert_is_boundary(v)) {
481 sys->context, i, i, 1.0f + lambda_factor / (4.0f * sys->ring_areas[i]));
482 }
483 else {
484 EIG_linear_solver_matrix_add(sys->context, i, i, 1.0f + lambda_border * 2.0f);
485 }
486 }
487 else {
488 EIG_linear_solver_matrix_add(sys->context, i, i, 1.0f);
489 }
490 }
492
494 validate_solution(sys, usex, usey, usez, preserve_volume);
495 }
496
498}
499
500} // namespace blender
Read Blender memory allocation and freeing.
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_index_get(ele)
#define BM_elem_flag_test(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
#define SMOOTH_LAPLACIAN_MAX_EDGE_PERCENTAGE
#define SMOOTH_LAPLACIAN_MIN_EDGE_PERCENTAGE
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
#define pow
void EIG_linear_solver_variable_set(LinearSolver *solver, int rhs, int index, double value)
void EIG_linear_solver_right_hand_side_add(LinearSolver *solver, int rhs, int index, double value)
void EIG_linear_solver_variable_unlock(LinearSolver *solver, int index)
LinearSolver * EIG_linear_least_squares_solver_new(int num_rows, int num_columns, int num_right_hand_sides)
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)
void EIG_linear_solver_variable_lock(LinearSolver *solver, int index)
ccl_device_inline float beta(const float x, const float y)
Definition math_base.h:708
BMesh Iterators.
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
unsigned int uint
Definition BKE_text.h:55
static void memset_laplacian_system(LaplacianSystem *sys, int val)
float BMO_slot_float_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
static void init_laplacian_matrix(LaplacianSystem *sys)
static LaplacianSystem * init_laplacian_system(int a_numEdges, int a_numLoops, int a_numVerts)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static void volume_preservation(BMOperator *op, float vini, float vend, int usex, int usey, int usez)
void MEM_delete_void(void *vmemh)
static void delete_laplacian_system(LaplacianSystem *sys)
double BM_mesh_calc_volume(BMesh *bm, bool is_signed)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BMesh const char void * data
void bmo_smooth_laplacian_vert_exec(BMesh *bm, BMOperator *op)
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void delete_void_pointer(void *data)
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
float cotangent_tri_weight_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:202
ATTR_WARN_UNUSED_RESULT const BMVert * v2
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:104
static void fill_laplacian_matrix(LaplacianSystem *sys)
static bool vert_is_boundary(BMVert *v)
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
static void validate_solution(LaplacianSystem *sys, int usex, int usey, int usez, int preserve_volume)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
struct BMLoop * next
struct BMLoop * prev
struct BMVert * v
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]