Blender V5.3
meshlaplacian.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
9
10#include "MEM_guardedalloc.h"
11
12#include "DNA_mesh_types.h"
13#include "DNA_object_types.h"
14
15#include "BLI_map.hh"
16#include "BLI_math_geom_c.hh"
17#include "BLI_math_matrix_c.hh"
19#include "BLI_math_vector_c.hh"
20#include "BLI_memarena.hh"
21#include "BLI_ordered_edge.hh"
22#include "BLI_string_utf8.hh"
23
24#include "BLT_translation.hh"
25
26#include "BKE_attribute.hh"
27#include "BKE_bvhutils.hh"
28#include "BKE_mesh.hh"
29#include "BKE_mesh_wrapper.hh"
30#include "BKE_modifier.hh"
31
32#include "ED_armature.hh"
33#include "ED_mesh.hh"
34#include "ED_object_vgroup.hh"
35
36#include "eigen_capi.h"
37
38#include "meshlaplacian.h"
39
40#include <algorithm>
41
42namespace blender {
43
44/* ************* XXX *************** */
45static void waitcursor(int /*val*/) {}
46static void progress_bar(int /*dummy_val*/, const char * /*dummy*/) {}
47static void start_progress_bar() {}
48static void end_progress_bar() {}
49static void error(const char *str)
50{
51 printf("error: %s\n", str);
52}
53/* ************* XXX *************** */
54
55/************************** Laplacian System *****************************/
56
58 LinearSolver *context; /* linear solver */
59
61
62 float **verts; /* vertex coordinates */
63 float *varea; /* vertex weights for laplacian computation */
64 char *vpinned; /* vertex pinning */
65 int (*faces)[3]; /* face vertex indices */
66 float (*fweights)[3]; /* cotangent weights per face */
67
68 int areaweights; /* use area in cotangent weights? */
69 int storeweights; /* store cotangent weights in fweights */
70 bool variablesdone; /* variables set in linear system */
71
72 Map<OrderedEdge, int> edgehash; /* edge hash for construction */
73
76 Span<int> corner_verts; /* needed to find vertices by index */
79 float (*verts)[3]; /* vertex coordinates */
80 float (*vert_normals)[3]; /* vertex normals */
81
82 float (*root)[3]; /* bone root */
83 float (*tip)[3]; /* bone tip */
85
86 float *H; /* diagonal H matrix */
87 float *p; /* values from all p vectors */
88 float *mindist; /* minimum distance to a bone for all vertices */
89
90 BVHTree *bvhtree; /* ray tracing acceleration structure */
91 const int3 **vltree; /* a corner_tri that the vertex belongs to */
93};
94
95/* Laplacian matrix construction */
96
97/* Computation of these weights for the laplacian is based on:
98 * "Discrete Differential-Geometry Operators for Triangulated 2-Manifolds",
99 * Meyer et al, 2002. Section 3.5, formula (8).
100 *
101 * We do it a bit different by going over faces instead of going over each
102 * vertex and adjacent faces, since we don't store this adjacency. Also, the
103 * formulas are tweaked a bit to work for non-manifold meshes. */
104
105static void laplacian_increase_edge_count(Map<OrderedEdge, int> &edgehash, int v1, int v2)
106{
107 edgehash.add_or_modify({v1, v2}, [](int *value) { *value = 1; }, [](int *value) { (*value)++; });
108}
109
110static int laplacian_edge_count(const Map<OrderedEdge, int> &edgehash, int v1, int v2)
111{
112 return edgehash.lookup({v1, v2});
113}
114
115static void laplacian_triangle_area(LaplacianSystem *sys, int i1, int i2, int i3)
116{
117 float t1, t2, t3, len1, len2, len3, area;
118 float *varea = sys->varea, *v1, *v2, *v3;
119 int obtuse = 0;
120
121 v1 = sys->verts[i1];
122 v2 = sys->verts[i2];
123 v3 = sys->verts[i3];
124
125 t1 = cotangent_tri_weight_v3(v1, v2, v3);
126 t2 = cotangent_tri_weight_v3(v2, v3, v1);
127 t3 = cotangent_tri_weight_v3(v3, v1, v2);
128
129 if (angle_v3v3v3(v2, v1, v3) > DEG2RADF(90.0f)) {
130 obtuse = 1;
131 }
132 else if (angle_v3v3v3(v1, v2, v3) > DEG2RADF(90.0f)) {
133 obtuse = 2;
134 }
135 else if (angle_v3v3v3(v1, v3, v2) > DEG2RADF(90.0f)) {
136 obtuse = 3;
137 }
138
139 if (obtuse > 0) {
140 area = area_tri_v3(v1, v2, v3);
141
142 varea[i1] += (obtuse == 1) ? area : area * 0.5f;
143 varea[i2] += (obtuse == 2) ? area : area * 0.5f;
144 varea[i3] += (obtuse == 3) ? area : area * 0.5f;
145 }
146 else {
147 len1 = len_v3v3(v2, v3);
148 len2 = len_v3v3(v1, v3);
149 len3 = len_v3v3(v1, v2);
150
151 t1 *= len1 * len1;
152 t2 *= len2 * len2;
153 t3 *= len3 * len3;
154
155 varea[i1] += (t2 + t3) * 0.25f;
156 varea[i2] += (t1 + t3) * 0.25f;
157 varea[i3] += (t1 + t2) * 0.25f;
158 }
159}
160
161static void laplacian_triangle_weights(LaplacianSystem *sys, int f, int i1, int i2, int i3)
162{
163 float t1, t2, t3;
164 float *varea = sys->varea, *v1, *v2, *v3;
165
166 v1 = sys->verts[i1];
167 v2 = sys->verts[i2];
168 v3 = sys->verts[i3];
169
170 /* instead of *0.5 we divided by the number of faces of the edge, it still
171 * needs to be verified that this is indeed the correct thing to do! */
172 t1 = cotangent_tri_weight_v3(v1, v2, v3) / laplacian_edge_count(sys->edgehash, i2, i3);
173 t2 = cotangent_tri_weight_v3(v2, v3, v1) / laplacian_edge_count(sys->edgehash, i3, i1);
174 t3 = cotangent_tri_weight_v3(v3, v1, v2) / laplacian_edge_count(sys->edgehash, i1, i2);
175
176 EIG_linear_solver_matrix_add(sys->context, i1, i1, (t2 + t3) * varea[i1]);
177 EIG_linear_solver_matrix_add(sys->context, i2, i2, (t1 + t3) * varea[i2]);
178 EIG_linear_solver_matrix_add(sys->context, i3, i3, (t1 + t2) * varea[i3]);
179
180 EIG_linear_solver_matrix_add(sys->context, i1, i2, -t3 * varea[i1]);
181 EIG_linear_solver_matrix_add(sys->context, i2, i1, -t3 * varea[i2]);
182
183 EIG_linear_solver_matrix_add(sys->context, i2, i3, -t1 * varea[i2]);
184 EIG_linear_solver_matrix_add(sys->context, i3, i2, -t1 * varea[i3]);
185
186 EIG_linear_solver_matrix_add(sys->context, i3, i1, -t2 * varea[i3]);
187 EIG_linear_solver_matrix_add(sys->context, i1, i3, -t2 * varea[i1]);
188
189 if (sys->storeweights) {
190 sys->fweights[f][0] = t1 * varea[i1];
191 sys->fweights[f][1] = t2 * varea[i2];
192 sys->fweights[f][2] = t3 * varea[i3];
193 }
194}
195
196static LaplacianSystem *laplacian_system_construct_begin(int verts_num, int faces_num, int lsq)
197{
198 LaplacianSystem *sys;
199
200 sys = MEM_new<LaplacianSystem>(__func__);
201
202 sys->verts = MEM_new_array_zeroed<float *>(verts_num, "LaplacianSystemVerts");
203 sys->vpinned = MEM_new_array_zeroed<char>(verts_num, "LaplacianSystemVpinned");
204 sys->faces = MEM_new_array_zeroed<int[3]>(faces_num, "LaplacianSystemFaces");
205
206 sys->verts_num = 0;
207 sys->faces_num = 0;
208
209 sys->areaweights = 1;
210 sys->storeweights = 0;
211
212 /* create linear solver */
213 if (lsq) {
214 sys->context = EIG_linear_least_squares_solver_new(0, verts_num, 1);
215 }
216 else {
217 sys->context = EIG_linear_solver_new(0, verts_num, 1);
218 }
219
220 return sys;
221}
222
223void laplacian_add_vertex(LaplacianSystem *sys, float *co, int pinned)
224{
225 sys->verts[sys->verts_num] = co;
226 sys->vpinned[sys->verts_num] = pinned;
227 sys->verts_num++;
228}
229
230void laplacian_add_triangle(LaplacianSystem *sys, int v1, int v2, int v3)
231{
232 sys->faces[sys->faces_num][0] = v1;
233 sys->faces[sys->faces_num][1] = v2;
234 sys->faces[sys->faces_num][2] = v3;
235 sys->faces_num++;
236}
237
239{
240 int (*face)[3];
241 int a, verts_num = sys->verts_num, faces_num = sys->faces_num;
242
243 laplacian_begin_solve(sys, 0);
244
245 sys->varea = MEM_new_array_zeroed<float>(verts_num, "LaplacianSystemVarea");
246
247 sys->edgehash.reserve(sys->faces_num);
248 for (a = 0, face = sys->faces; a < sys->faces_num; a++, face++) {
249 laplacian_increase_edge_count(sys->edgehash, (*face)[0], (*face)[1]);
250 laplacian_increase_edge_count(sys->edgehash, (*face)[1], (*face)[2]);
251 laplacian_increase_edge_count(sys->edgehash, (*face)[2], (*face)[0]);
252 }
253
254 if (sys->areaweights) {
255 for (a = 0, face = sys->faces; a < sys->faces_num; a++, face++) {
256 laplacian_triangle_area(sys, (*face)[0], (*face)[1], (*face)[2]);
257 }
258 }
259
260 for (a = 0; a < verts_num; a++) {
261 if (sys->areaweights) {
262 if (sys->varea[a] != 0.0f) {
263 sys->varea[a] = 0.5f / sys->varea[a];
264 }
265 }
266 else {
267 sys->varea[a] = 1.0f;
268 }
269
270 /* for heat weighting */
271 if (sys->heat.H) {
272 EIG_linear_solver_matrix_add(sys->context, a, a, sys->heat.H[a]);
273 }
274 }
275
276 if (sys->storeweights) {
277 sys->fweights = MEM_new_array_zeroed<float[3]>(faces_num, "LaplacianFWeight");
278 }
279
280 for (a = 0, face = sys->faces; a < faces_num; a++, face++) {
281 laplacian_triangle_weights(sys, a, (*face)[0], (*face)[1], (*face)[2]);
282 }
283
284 MEM_delete(sys->faces);
285 sys->faces = nullptr;
286
287 MEM_SAFE_DELETE(sys->varea);
288}
289
291{
292 if (sys->verts) {
293 MEM_delete(sys->verts);
294 }
295 if (sys->varea) {
296 MEM_delete(sys->varea);
297 }
298 if (sys->vpinned) {
299 MEM_delete(sys->vpinned);
300 }
301 if (sys->faces) {
302 MEM_delete(sys->faces);
303 }
304 if (sys->fweights) {
305 MEM_delete(sys->fweights);
306 }
307
309 MEM_delete(sys);
310}
311
313{
314 int a;
315
316 if (!sys->variablesdone) {
317 if (index >= 0) {
318 for (a = 0; a < sys->verts_num; a++) {
319 if (sys->vpinned[a]) {
322 }
323 }
324 }
325
326 sys->variablesdone = true;
327 }
328}
329
331{
333}
334
336{
337 sys->variablesdone = false;
338
339 // EIG_linear_solver_print_matrix(sys->context, );
340
341 return EIG_linear_solver_solve(sys->context);
342}
343
348
349/************************* Heat Bone Weighting ******************************/
350/* From "Automatic Rigging and Animation of 3D Characters"
351 * Ilya Baran and Jovan Popovic, SIGGRAPH 2007 */
352
353#define C_WEIGHT 1.0f
354#define WEIGHT_LIMIT_START 0.05f
355#define WEIGHT_LIMIT_END 0.025f
356#define DISTANCE_EPSILON 1e-4f
357
359 float start[3];
360 float vec[3];
362};
363
364static void bvh_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
365{
366 BVHCallbackUserData *data = static_cast<BVHCallbackUserData *>(userdata);
367 const int3 &tri = data->sys->heat.corner_tris[index];
368 const Span<int> corner_verts = data->sys->heat.corner_verts;
369 float (*verts)[3] = data->sys->heat.verts;
370 const float *vtri_co[3];
371 float dist_test;
372
373 vtri_co[0] = verts[corner_verts[tri[0]]];
374 vtri_co[1] = verts[corner_verts[tri[1]]];
375 vtri_co[2] = verts[corner_verts[tri[2]]];
376
377#ifdef USE_KDOPBVH_WATERTIGHT
379 data->start, ray->isect_precalc, UNPACK3(vtri_co), &dist_test, nullptr))
380#else
381 UNUSED_VARS(ray);
382 if (isect_ray_tri_v3(data->start, data->vec, UNPACK3(vtri_co), &dist_test, nullptr))
383#endif
384 {
385 if (dist_test < hit->dist) {
386 float n[3];
387 normal_tri_v3(n, UNPACK3(vtri_co));
388 if (dot_v3v3(n, data->vec) < -1e-5f) {
389 hit->index = index;
390 hit->dist = dist_test;
391 }
392 }
393 }
394}
395
396/* Ray-tracing for vertex to bone/vertex visibility. */
398{
399 const int3 *corner_tris = sys->heat.corner_tris;
400 const Span<int> corner_verts = sys->heat.corner_verts;
401 float (*verts)[3] = sys->heat.verts;
402 int tris_num = sys->heat.tris_num;
403 int verts_num = sys->heat.verts_num;
404 int a;
405
406 sys->heat.bvhtree = BLI_bvhtree_new(tris_num, 0.0f, 4, 6);
407 sys->heat.vltree = MEM_new_array_zeroed<const int3 *>(verts_num, "HeatVFaces");
408
409 for (a = 0; a < tris_num; a++) {
410 const int3 &tri = corner_tris[a];
411 float bb[6];
412 int vtri[3];
413
414 vtri[0] = corner_verts[tri[0]];
415 vtri[1] = corner_verts[tri[1]];
416 vtri[2] = corner_verts[tri[2]];
417
418 INIT_MINMAX(bb, bb + 3);
419 minmax_v3v3_v3(bb, bb + 3, verts[vtri[0]]);
420 minmax_v3v3_v3(bb, bb + 3, verts[vtri[1]]);
421 minmax_v3v3_v3(bb, bb + 3, verts[vtri[2]]);
422
423 BLI_bvhtree_insert(sys->heat.bvhtree, a, bb, 2);
424
425 /* Setup inverse pointers to use on isect.orig */
426 sys->heat.vltree[vtri[0]] = &tri;
427 sys->heat.vltree[vtri[1]] = &tri;
428 sys->heat.vltree[vtri[2]] = &tri;
429 }
430
432}
433
434static int heat_ray_source_visible(LaplacianSystem *sys, int vertex, int source)
435{
436 BVHTreeRayHit hit;
438 const int3 *lt;
439 float end[3];
440 int visible;
441
442 lt = sys->heat.vltree[vertex];
443 if (lt == nullptr) {
444 return 1;
445 }
446
447 data.sys = sys;
448 copy_v3_v3(data.start, sys->heat.verts[vertex]);
449
450 closest_to_line_segment_v3(end, data.start, sys->heat.root[source], sys->heat.tip[source]);
451
452 sub_v3_v3v3(data.vec, end, data.start);
453 madd_v3_v3v3fl(data.start, data.start, data.vec, 1e-5);
454 mul_v3_fl(data.vec, 1.0f - 2e-5f);
455
456 /* pass normalized vec + distance to bvh */
457 hit.index = -1;
458 hit.dist = normalize_v3(data.vec);
459
460 visible = BLI_bvhtree_ray_cast(sys->heat.bvhtree,
461 data.start,
462 data.vec,
463 0.0f,
464 &hit,
466 static_cast<void *>(&data)) == -1;
467
468 return visible;
469}
470
471static float heat_source_distance(LaplacianSystem *sys, int vertex, int source)
472{
473 float closest[3], d[3], dist, cosine;
474
475 /* compute Euclidean distance */
477 closest, sys->heat.verts[vertex], sys->heat.root[source], sys->heat.tip[source]);
478
480 dist = normalize_v3(d);
481
482 /* if the vertex normal does not point along the bone, increase distance */
483 cosine = dot_v3v3(d, sys->heat.vert_normals[vertex]);
484
485 return dist / (0.5f * (cosine + 1.001f));
486}
487
488static int heat_source_closest(LaplacianSystem *sys, int vertex, int source)
489{
490 float dist;
491
492 dist = heat_source_distance(sys, vertex, source);
493
494 if (dist <= sys->heat.mindist[vertex] * (1.0f + DISTANCE_EPSILON)) {
495 if (heat_ray_source_visible(sys, vertex, source)) {
496 return 1;
497 }
498 }
499
500 return 0;
501}
502
503static void heat_set_H(LaplacianSystem *sys, int vertex)
504{
505 float dist, mindist, h;
506 int j, numclosest = 0;
507
508 mindist = 1e10;
509
510 /* compute minimum distance */
511 for (j = 0; j < sys->heat.numsource; j++) {
512 dist = heat_source_distance(sys, vertex, j);
513
514 mindist = std::min(dist, mindist);
515 }
516
517 sys->heat.mindist[vertex] = mindist;
518
519 /* count number of sources with approximately this minimum distance */
520 for (j = 0; j < sys->heat.numsource; j++) {
521 if (heat_source_closest(sys, vertex, j)) {
522 numclosest++;
523 }
524 }
525
526 sys->heat.p[vertex] = (numclosest > 0) ? 1.0f / numclosest : 0.0f;
527
528 /* compute H entry */
529 if (numclosest > 0) {
530 mindist = max_ff(mindist, 1e-4f);
531 h = numclosest * C_WEIGHT / (mindist * mindist);
532 }
533 else {
534 h = 0.0f;
535 }
536
537 sys->heat.H[vertex] = h;
538}
539
541{
542 float fnor[3];
543 int a, v1, v2, v3, (*face)[3];
544
546
547 for (a = 0, face = sys->faces; a < sys->faces_num; a++, face++) {
548 v1 = (*face)[0];
549 v2 = (*face)[1];
550 v3 = (*face)[2];
551
552 normal_tri_v3(fnor, sys->verts[v1], sys->verts[v2], sys->verts[v3]);
553
554 add_v3_v3(sys->heat.vert_normals[v1], fnor);
555 add_v3_v3(sys->heat.vert_normals[v2], fnor);
556 add_v3_v3(sys->heat.vert_normals[v3], fnor);
557 }
558
559 for (a = 0; a < sys->verts_num; a++) {
561 }
562}
563
565{
566 const int3 *corner_tris = sys->heat.corner_tris;
567 const Span<int> corner_verts = sys->heat.corner_verts;
568 int tris_num = sys->heat.tris_num;
569 int verts_num = sys->heat.verts_num;
570 int a;
571
572 /* heat specific definitions */
573 sys->heat.mindist = MEM_new_array_zeroed<float>(verts_num, "HeatMinDist");
574 sys->heat.H = MEM_new_array_zeroed<float>(verts_num, "HeatH");
575 sys->heat.p = MEM_new_array_zeroed<float>(verts_num, "HeatP");
576
577 /* add verts and faces to laplacian */
578 for (a = 0; a < verts_num; a++) {
579 laplacian_add_vertex(sys, sys->heat.verts[a], 0);
580 }
581
582 for (a = 0; a < tris_num; a++) {
583 int vtri[3];
584 vtri[0] = corner_verts[corner_tris[a][0]];
585 vtri[1] = corner_verts[corner_tris[a][1]];
586 vtri[2] = corner_verts[corner_tris[a][2]];
588 }
589
590 /* for distance computation in set_H */
592
593 for (a = 0; a < verts_num; a++) {
594 heat_set_H(sys, a);
595 }
596}
597
599{
601 MEM_delete(sys->heat.vltree);
602 MEM_delete(sys->heat.corner_tris);
603
604 MEM_delete(sys->heat.mindist);
605 MEM_delete(sys->heat.H);
606 MEM_delete(sys->heat.p);
607 MEM_delete(sys->heat.vert_normals);
608}
609
610static float heat_limit_weight(float weight)
611{
612 float t;
613
614 if (weight < WEIGHT_LIMIT_END) {
615 return 0.0f;
616 }
617 if (weight < WEIGHT_LIMIT_START) {
619 return t * WEIGHT_LIMIT_START;
620 }
621 return weight;
622}
623
625 Mesh *mesh,
626 float (*verts)[3],
627 int numbones,
628 bDeformGroup **dgrouplist,
629 bDeformGroup **dgroupflip,
630 float (*root)[3],
631 float (*tip)[3],
632 const bool *selected,
633 const char **r_error_str)
634{
635 LaplacianSystem *sys;
636 int3 *corner_tris;
637 float solution, weight;
638 int *vertsflipped = nullptr, *mask = nullptr;
639 int a, tris_num, j, bbone, firstsegment, lastsegment;
640 bool use_topology = (mesh->editflag & ME_EDIT_MIRROR_TOPO) != 0;
641
642 const Span<float3> vert_positions = mesh->vert_positions();
643 const OffsetIndices faces = mesh->faces();
644 const Span<int> corner_verts = mesh->corner_verts();
645 const bke::AttributeAccessor attributes = mesh->attributes();
646 bool use_vert_sel = (mesh->editflag & ME_EDIT_PAINT_VERT_SEL) != 0;
647 bool use_face_sel = (mesh->editflag & ME_EDIT_PAINT_FACE_SEL) != 0;
648
649 *r_error_str = nullptr;
650
651 /* bone heat needs triangulated faces */
652 tris_num = poly_to_tri_count(mesh->faces_num, mesh->corners_num);
653
654 /* count triangles and create mask */
655 if (ob->mode & OB_MODE_WEIGHT_PAINT && (use_face_sel || use_vert_sel)) {
656 mask = MEM_new_array_zeroed<int>(mesh->verts_num, "heat_bone_weighting mask");
657
658 /* (added selectedVerts content for vertex mask, they used to just equal 1) */
659 if (use_vert_sel) {
660 const VArray select_vert = *attributes.lookup_or_default<bool>(
661 ".select_vert", bke::AttrDomain::Point, false);
662 if (select_vert) {
663 for (const int i : faces.index_range()) {
664 for (const int vert : corner_verts.slice(faces[i])) {
665 mask[vert] = select_vert[vert];
666 }
667 }
668 }
669 }
670 else if (use_face_sel) {
671 const VArray select_poly = *attributes.lookup_or_default<bool>(
672 ".select_poly", bke::AttrDomain::Face, false);
673 if (select_poly) {
674 for (const int i : faces.index_range()) {
675 if (select_poly[i]) {
676 for (const int vert : corner_verts.slice(faces[i])) {
677 mask[vert] = 1;
678 }
679 }
680 }
681 }
682 }
683 }
684
685 /* create laplacian */
686 sys = laplacian_system_construct_begin(mesh->verts_num, tris_num, 1);
687
688 sys->heat.tris_num = poly_to_tri_count(mesh->faces_num, mesh->corners_num);
689 corner_tris = MEM_new_array_uninitialized<int3>(sys->heat.tris_num, __func__);
690
692 vert_positions, faces, corner_verts, {corner_tris, sys->heat.tris_num});
693
694 sys->heat.corner_tris = corner_tris;
695 sys->heat.corner_verts = corner_verts;
696 sys->heat.verts_num = mesh->verts_num;
697 sys->heat.verts = verts;
698 sys->heat.root = root;
699 sys->heat.tip = tip;
700 sys->heat.numsource = numbones;
701
704
706
707 if (dgroupflip) {
708 vertsflipped = MEM_new_array_zeroed<int>(mesh->verts_num, "vertsflipped");
709 for (a = 0; a < mesh->verts_num; a++) {
710 vertsflipped[a] = mesh_get_x_mirror_vert(ob, nullptr, a, use_topology);
711 }
712 }
713
714 /* compute weights per bone */
715 for (j = 0; j < numbones; j++) {
716 if (selected[j] == false) {
717 continue;
718 }
719
720 firstsegment = (j == 0 || dgrouplist[j - 1] != dgrouplist[j]);
721 lastsegment = (j == numbones - 1 || dgrouplist[j] != dgrouplist[j + 1]);
722 bbone = !(firstsegment && lastsegment);
723
724 /* clear weights */
725 if (bbone && firstsegment) {
726 for (a = 0; a < mesh->verts_num; a++) {
727 if (mask && !mask[a]) {
728 continue;
729 }
730
731 ed::object::vgroup_vert_remove(ob, dgrouplist[j], a);
732 if (vertsflipped && dgroupflip[j] && vertsflipped[a] >= 0) {
733 ed::object::vgroup_vert_remove(ob, dgroupflip[j], vertsflipped[a]);
734 }
735 }
736 }
737
738 /* fill right hand side */
739 laplacian_begin_solve(sys, -1);
740
741 for (a = 0; a < mesh->verts_num; a++) {
742 if (heat_source_closest(sys, a, j)) {
743 laplacian_add_right_hand_side(sys, a, sys->heat.H[a] * sys->heat.p[a]);
744 }
745 }
746
747 /* solve */
748 if (laplacian_system_solve(sys)) {
749 /* load solution into vertex groups */
750 for (a = 0; a < mesh->verts_num; a++) {
751 if (mask && !mask[a]) {
752 continue;
753 }
754
755 solution = laplacian_system_get_solution(sys, a);
756
757 if (bbone) {
758 if (solution > 0.0f) {
759 ed::object::vgroup_vert_add(ob, dgrouplist[j], a, solution, WEIGHT_ADD);
760 }
761 }
762 else {
763 weight = heat_limit_weight(solution);
764 if (weight > 0.0f) {
765 ed::object::vgroup_vert_add(ob, dgrouplist[j], a, weight, WEIGHT_REPLACE);
766 }
767 else {
768 ed::object::vgroup_vert_remove(ob, dgrouplist[j], a);
769 }
770 }
771
772 /* do same for mirror */
773 if (vertsflipped && dgroupflip[j] && vertsflipped[a] >= 0) {
774 if (bbone) {
775 if (solution > 0.0f) {
777 ob, dgroupflip[j], vertsflipped[a], solution, WEIGHT_ADD);
778 }
779 }
780 else {
781 weight = heat_limit_weight(solution);
782 if (weight > 0.0f) {
784 ob, dgroupflip[j], vertsflipped[a], weight, WEIGHT_REPLACE);
785 }
786 else {
787 ed::object::vgroup_vert_remove(ob, dgroupflip[j], vertsflipped[a]);
788 }
789 }
790 }
791 }
792 }
793 else if (*r_error_str == nullptr) {
794 *r_error_str = N_("Bone Heat Weighting: failed to find solution for one or more bones");
795 break;
796 }
797
798 /* remove too small vertex weights */
799 if (bbone && lastsegment) {
800 for (a = 0; a < mesh->verts_num; a++) {
801 if (mask && !mask[a]) {
802 continue;
803 }
804
805 weight = ed::object::vgroup_vert_weight(ob, dgrouplist[j], a);
806 weight = heat_limit_weight(weight);
807 if (weight <= 0.0f) {
808 ed::object::vgroup_vert_remove(ob, dgrouplist[j], a);
809 }
810
811 if (vertsflipped && dgroupflip[j] && vertsflipped[a] >= 0) {
812 weight = ed::object::vgroup_vert_weight(ob, dgroupflip[j], vertsflipped[a]);
813 weight = heat_limit_weight(weight);
814 if (weight <= 0.0f) {
815 ed::object::vgroup_vert_remove(ob, dgroupflip[j], vertsflipped[a]);
816 }
817 }
818 }
819 }
820 }
821
822 /* free */
823 if (vertsflipped) {
824 MEM_delete(vertsflipped);
825 }
826 if (mask) {
827 MEM_delete(mask);
828 }
829
830 heat_system_free(sys);
831
833}
834
835/************************** Harmonic Coordinates ****************************/
836/* From "Harmonic Coordinates for Character Articulation",
837 * Pushkar Joshi, Mark Meyer, Tony DeRose, Brian Green and Tom Sanocki,
838 * SIGGRAPH 2007. */
839
840#define EPSILON 0.0001f
841
842#define MESHDEFORM_TAG_UNTYPED 0
843#define MESHDEFORM_TAG_BOUNDARY 1
844#define MESHDEFORM_TAG_INTERIOR 2
845#define MESHDEFORM_TAG_EXTERIOR 3
846
848#define MESHDEFORM_LEN_THRESHOLD 1e-6f
849
850#define MESHDEFORM_MIN_INFLUENCE 0.0005f
851
852static const int MESHDEFORM_OFFSET[7][3] = {
853 {0, 0, 0},
854 {1, 0, 0},
855 {-1, 0, 0},
856 {0, 1, 0},
857 {0, -1, 0},
858 {0, 0, 1},
859 {0, 0, -1},
860};
861
863 /* intersection on the cage 'cagecos' */
864 float co[3];
865 /* non-facing intersections are considered interior */
866 bool facing;
867 /* ray-cast index aligned with polygons (ray-hit-triangle isn't needed) */
869 /* distance from 'co' to the ray-cast start (clamped to avoid zero division) */
870 float len;
871 /* weights aligned with the polygon's loop indices */
872 float poly_weights[0];
873};
874
880
882 /* grid dimensions */
883 float min[3], max[3];
884 float width[3], halfwidth[3];
886
887 /* meshes */
892
893 /* grids */
895 MDefBoundIsect *(*boundisect)[6];
897 int *tag;
898 float *phi, *totalphi;
899
900 /* mesh stuff */
901 int *inside;
902 float *weights;
904 float cagemat[4][4];
905
906 /* direct solver */
907 int *varidx;
908
911
912 /* avoid DM function calls during intersections */
920};
921
923 float start[3];
924 float vec[3];
926 float lambda;
927
928 bool isect;
929 float u, v;
930};
931
932/* ray intersection */
933
938
939static void harmonic_ray_callback(void *userdata,
940 int index,
941 const BVHTreeRay *ray,
942 BVHTreeRayHit *hit)
943{
944 MeshRayCallbackData *data = static_cast<MeshRayCallbackData *>(userdata);
945 MeshDeformBind *mdb = data->mdb;
946 const Span<int> corner_verts = mdb->cagemesh_cache.corner_verts;
947 const Span<int> tri_faces = mdb->cagemesh_cache.tri_faces;
948 const Span<float3> face_normals = mdb->cagemesh_cache.face_normals;
949 MeshDeformIsect *isec = data->isec;
950 float no[3], co[3], dist;
951 float *face[3];
952
953 const int3 &tri = mdb->cagemesh_cache.corner_tris[index];
954
955 face[0] = mdb->cagecos[corner_verts[tri[0]]];
956 face[1] = mdb->cagecos[corner_verts[tri[1]]];
957 face[2] = mdb->cagecos[corner_verts[tri[2]]];
958
959 bool isect_ray_tri = isect_ray_tri_watertight_v3(
960 ray->origin, ray->isect_precalc, UNPACK3(face), &dist, nullptr);
961
962 if (!isect_ray_tri || dist > isec->vec_length) {
963 return;
964 }
965
966 if (!face_normals.is_empty()) {
967 copy_v3_v3(no, face_normals[tri_faces[index]]);
968 }
969 else {
970 normal_tri_v3(no, UNPACK3(face));
971 }
972
973 madd_v3_v3v3fl(co, ray->origin, ray->direction, dist);
974 dist /= isec->vec_length;
975 if (dist < hit->dist) {
976 hit->index = index;
977 hit->dist = dist;
978 copy_v3_v3(hit->co, co);
979
980 isec->isect = (dot_v3v3(no, ray->direction) <= 0.0f);
981 isec->lambda = dist;
982 }
983}
984
986 const float co1[3],
987 const float co2[3])
988{
989 BVHTreeRayHit hit;
990 MeshDeformIsect isect_mdef;
992 mdb,
993 &isect_mdef,
994 };
995 float end[3], vec_normal[3];
996
997 /* happens binding when a cage has no faces */
998 if (mdb->bvhtree == nullptr) [[unlikely]] {
999 return nullptr;
1000 }
1001
1002 /* setup isec */
1003 memset(&isect_mdef, 0, sizeof(isect_mdef));
1004 isect_mdef.lambda = 1e10f;
1005
1006 copy_v3_v3(isect_mdef.start, co1);
1007 copy_v3_v3(end, co2);
1008 sub_v3_v3v3(isect_mdef.vec, end, isect_mdef.start);
1009 isect_mdef.vec_length = normalize_v3_v3(vec_normal, isect_mdef.vec);
1010
1011 hit.index = -1;
1014 isect_mdef.start,
1015 vec_normal,
1016 0.0,
1017 &hit,
1019 &data,
1021 {
1022 const Span<int> corner_verts = mdb->cagemesh_cache.corner_verts;
1023 const int face_i = mdb->cagemesh_cache.tri_faces[hit.index];
1024 const IndexRange face = mdb->cagemesh_cache.faces[face_i];
1025 const float (*cagecos)[3] = mdb->cagecos;
1026 const float len = isect_mdef.lambda;
1027 MDefBoundIsect *isect;
1028
1029 Array<float3, 64> mp_cagecos(face.size());
1030
1031 /* create MDefBoundIsect, and extra for 'poly_weights[]' */
1032 isect = static_cast<MDefBoundIsect *>(
1033 BLI_memarena_alloc(mdb->memarena, sizeof(*isect) + (sizeof(float) * face.size())));
1034
1035 /* compute intersection coordinate */
1036 madd_v3_v3v3fl(isect->co, co1, isect_mdef.vec, len);
1037
1038 isect->facing = isect_mdef.isect;
1039
1040 isect->face_index = face_i;
1041
1042 isect->len = max_ff(len_v3v3(co1, isect->co), MESHDEFORM_LEN_THRESHOLD);
1043
1044 /* compute mean value coordinates for interpolation */
1045 for (int i = 0; i < face.size(); i++) {
1046 copy_v3_v3(mp_cagecos[i], cagecos[corner_verts[face[i]]]);
1047 }
1048
1050 reinterpret_cast<float (*)[3]>(mp_cagecos.data()),
1051 face.size(),
1052 isect->co);
1053
1054 return isect;
1055 }
1056
1057 return nullptr;
1058}
1059
1060static int meshdeform_inside_cage(MeshDeformBind *mdb, float *co)
1061{
1062 MDefBoundIsect *isect;
1063 float outside[3], start[3], dir[3];
1064 int i;
1065
1066 for (i = 1; i <= 6; i++) {
1067 outside[0] = co[0] + (mdb->max[0] - mdb->min[0] + 1.0f) * MESHDEFORM_OFFSET[i][0];
1068 outside[1] = co[1] + (mdb->max[1] - mdb->min[1] + 1.0f) * MESHDEFORM_OFFSET[i][1];
1069 outside[2] = co[2] + (mdb->max[2] - mdb->min[2] + 1.0f) * MESHDEFORM_OFFSET[i][2];
1070
1071 copy_v3_v3(start, co);
1072 sub_v3_v3v3(dir, outside, start);
1073 normalize_v3(dir);
1074
1075 isect = meshdeform_ray_tree_intersect(mdb, start, outside);
1076 if (isect && !isect->facing) {
1077 return 1;
1078 }
1079 }
1080
1081 return 0;
1082}
1083
1084/* solving */
1085
1086BLI_INLINE int meshdeform_index(MeshDeformBind *mdb, int x, int y, int z, int n)
1087{
1088 int size = mdb->size;
1089
1090 x += MESHDEFORM_OFFSET[n][0];
1091 y += MESHDEFORM_OFFSET[n][1];
1092 z += MESHDEFORM_OFFSET[n][2];
1093
1094 if (x < 0 || x >= mdb->size) {
1095 return -1;
1096 }
1097 if (y < 0 || y >= mdb->size) {
1098 return -1;
1099 }
1100 if (z < 0 || z >= mdb->size) {
1101 return -1;
1102 }
1103
1104 return x + y * size + z * size * size;
1105}
1106
1108 MeshDeformBind *mdb, int x, int y, int z, int n, float *center)
1109{
1110 x += MESHDEFORM_OFFSET[n][0];
1111 y += MESHDEFORM_OFFSET[n][1];
1112 z += MESHDEFORM_OFFSET[n][2];
1113
1114 center[0] = mdb->min[0] + x * mdb->width[0] + mdb->halfwidth[0];
1115 center[1] = mdb->min[1] + y * mdb->width[1] + mdb->halfwidth[1];
1116 center[2] = mdb->min[2] + z * mdb->width[2] + mdb->halfwidth[2];
1117}
1118
1119static void meshdeform_add_intersections(MeshDeformBind *mdb, int x, int y, int z)
1120{
1121 MDefBoundIsect *isect;
1122 float center[3], ncenter[3];
1123 int i, a;
1124
1125 a = meshdeform_index(mdb, x, y, z, 0);
1126 meshdeform_cell_center(mdb, x, y, z, 0, center);
1127
1128 /* check each outgoing edge for intersection */
1129 for (i = 1; i <= 6; i++) {
1130 if (meshdeform_index(mdb, x, y, z, i) == -1) {
1131 continue;
1132 }
1133
1134 meshdeform_cell_center(mdb, x, y, z, i, ncenter);
1135
1136 isect = meshdeform_ray_tree_intersect(mdb, center, ncenter);
1137 if (isect) {
1138 mdb->boundisect[a][i - 1] = isect;
1139 mdb->tag[a] = MESHDEFORM_TAG_BOUNDARY;
1140 }
1141 }
1142}
1143
1145{
1146 int *stack, *tag = mdb->tag;
1147 int a, b, i, xyz[3], stacksize, size = mdb->size;
1148
1149 stack = MEM_new_array_zeroed<int>(mdb->size3, __func__);
1150
1151 /* we know lower left corner is EXTERIOR because of padding */
1152 tag[0] = MESHDEFORM_TAG_EXTERIOR;
1153 stack[0] = 0;
1154 stacksize = 1;
1155
1156 /* floodfill exterior tag */
1157 while (stacksize > 0) {
1158 a = stack[--stacksize];
1159
1160 xyz[2] = a / (size * size);
1161 xyz[1] = (a - xyz[2] * size * size) / size;
1162 xyz[0] = a - xyz[1] * size - xyz[2] * size * size;
1163
1164 for (i = 1; i <= 6; i++) {
1165 b = meshdeform_index(mdb, xyz[0], xyz[1], xyz[2], i);
1166
1167 if (b != -1) {
1168 if (tag[b] == MESHDEFORM_TAG_UNTYPED ||
1169 (tag[b] == MESHDEFORM_TAG_BOUNDARY && !mdb->boundisect[a][i - 1]))
1170 {
1172 stack[stacksize++] = b;
1173 }
1174 }
1175 }
1176 }
1177
1178 /* other cells are interior */
1179 for (a = 0; a < size * size * size; a++) {
1180 if (tag[a] == MESHDEFORM_TAG_UNTYPED) {
1181 tag[a] = MESHDEFORM_TAG_INTERIOR;
1182 }
1183 }
1184
1185#if 0
1186 {
1187 int tb, ti, te, ts;
1188 tb = ti = te = ts = 0;
1189 for (a = 0; a < size * size * size; a++) {
1190 if (tag[a] == MESHDEFORM_TAG_BOUNDARY) {
1191 tb++;
1192 }
1193 else if (tag[a] == MESHDEFORM_TAG_INTERIOR) {
1194 ti++;
1195 }
1196 else if (tag[a] == MESHDEFORM_TAG_EXTERIOR) {
1197 te++;
1198
1199 if (mdb->semibound[a]) {
1200 ts++;
1201 }
1202 }
1203 }
1204
1205 printf("interior %d exterior %d boundary %d semi-boundary %d\n", ti, te, tb, ts);
1206 }
1207#endif
1208
1209 MEM_delete(stack);
1210}
1211
1213 const MDefBoundIsect *isect,
1214 int cagevert)
1215{
1216 const IndexRange face = mdb->cagemesh_cache.faces[isect->face_index];
1217 const Span<int> corner_verts = mdb->cagemesh_cache.corner_verts;
1218
1219 for (int i = 0; i < face.size(); i++) {
1220 if (corner_verts[face[i]] == cagevert) {
1221 return isect->poly_weights[i];
1222 }
1223 }
1224
1225 return 0.0f;
1226}
1227
1229 const float *gridvec,
1230 float * /*vec*/,
1231 int /*cagevert*/)
1232{
1233 float dvec[3], ivec[3], result = 0.0f;
1234 float totweight = 0.0f;
1235
1236 for (int i = 0; i < 3; i++) {
1237 ivec[i] = int(gridvec[i]);
1238 dvec[i] = gridvec[i] - ivec[i];
1239 }
1240
1241 for (int i = 0; i < 8; i++) {
1242 int x, y, z;
1243 float wx, wy, wz;
1244
1245 if (i & 1) {
1246 x = ivec[0] + 1;
1247 wx = dvec[0];
1248 }
1249 else {
1250 x = ivec[0];
1251 wx = 1.0f - dvec[0];
1252 }
1253
1254 if (i & 2) {
1255 y = ivec[1] + 1;
1256 wy = dvec[1];
1257 }
1258 else {
1259 y = ivec[1];
1260 wy = 1.0f - dvec[1];
1261 }
1262
1263 if (i & 4) {
1264 z = ivec[2] + 1;
1265 wz = dvec[2];
1266 }
1267 else {
1268 z = ivec[2];
1269 wz = 1.0f - dvec[2];
1270 }
1271
1272 CLAMP(x, 0, mdb->size - 1);
1273 CLAMP(y, 0, mdb->size - 1);
1274 CLAMP(z, 0, mdb->size - 1);
1275
1276 int a = meshdeform_index(mdb, x, y, z, 0);
1277 float weight = wx * wy * wz;
1278 result += weight * mdb->phi[a];
1279 totweight += weight;
1280 }
1281
1282 if (totweight > 0.0f) {
1283 result /= totweight;
1284 }
1285
1286 return result;
1287}
1288
1289static void meshdeform_check_semibound(MeshDeformBind *mdb, int x, int y, int z)
1290{
1291 int i, a;
1292
1293 a = meshdeform_index(mdb, x, y, z, 0);
1294 if (mdb->tag[a] != MESHDEFORM_TAG_EXTERIOR) {
1295 return;
1296 }
1297
1298 for (i = 1; i <= 6; i++) {
1299 if (mdb->boundisect[a][i - 1]) {
1300 mdb->semibound[a] = 1;
1301 }
1302 }
1303}
1304
1305static float meshdeform_boundary_total_weight(MeshDeformBind *mdb, int x, int y, int z)
1306{
1307 float weight, totweight = 0.0f;
1308 int i, a;
1309
1310 a = meshdeform_index(mdb, x, y, z, 0);
1311
1312 /* count weight for neighbor cells */
1313 for (i = 1; i <= 6; i++) {
1314 if (meshdeform_index(mdb, x, y, z, i) == -1) {
1315 continue;
1316 }
1317
1318 if (mdb->boundisect[a][i - 1]) {
1319 weight = 1.0f / mdb->boundisect[a][i - 1]->len;
1320 }
1321 else if (!mdb->semibound[a]) {
1322 weight = 1.0f / mdb->width[0];
1323 }
1324 else {
1325 weight = 0.0f;
1326 }
1327
1328 totweight += weight;
1329 }
1330
1331 return totweight;
1332}
1333
1335 MeshDeformBind *mdb, LinearSolver *context, int x, int y, int z)
1336{
1337 MDefBoundIsect *isect;
1338 float weight, totweight;
1339 int i, a, acenter;
1340
1341 acenter = meshdeform_index(mdb, x, y, z, 0);
1342 if (mdb->tag[acenter] == MESHDEFORM_TAG_EXTERIOR) {
1343 return;
1344 }
1345
1346 EIG_linear_solver_matrix_add(context, mdb->varidx[acenter], mdb->varidx[acenter], 1.0f);
1347
1348 totweight = meshdeform_boundary_total_weight(mdb, x, y, z);
1349 for (i = 1; i <= 6; i++) {
1350 a = meshdeform_index(mdb, x, y, z, i);
1351 if (a == -1 || mdb->tag[a] == MESHDEFORM_TAG_EXTERIOR) {
1352 continue;
1353 }
1354
1355 isect = mdb->boundisect[acenter][i - 1];
1356 if (!isect) {
1357 weight = (1.0f / mdb->width[0]) / totweight;
1358 EIG_linear_solver_matrix_add(context, mdb->varidx[acenter], mdb->varidx[a], -weight);
1359 }
1360 }
1361}
1362
1364 MeshDeformBind *mdb, LinearSolver *context, int x, int y, int z, int cagevert)
1365{
1366 MDefBoundIsect *isect;
1367 float rhs, weight, totweight;
1368 int i, a, acenter;
1369
1370 acenter = meshdeform_index(mdb, x, y, z, 0);
1371 if (mdb->tag[acenter] == MESHDEFORM_TAG_EXTERIOR) {
1372 return;
1373 }
1374
1375 totweight = meshdeform_boundary_total_weight(mdb, x, y, z);
1376 for (i = 1; i <= 6; i++) {
1377 a = meshdeform_index(mdb, x, y, z, i);
1378 if (a == -1) {
1379 continue;
1380 }
1381
1382 isect = mdb->boundisect[acenter][i - 1];
1383
1384 if (isect) {
1385 weight = (1.0f / isect->len) / totweight;
1386 rhs = weight * meshdeform_boundary_phi(mdb, isect, cagevert);
1387 EIG_linear_solver_right_hand_side_add(context, 0, mdb->varidx[acenter], rhs);
1388 }
1389 }
1390}
1391
1393 MeshDeformBind *mdb, int x, int y, int z, int cagevert)
1394{
1395 MDefBoundIsect *isect;
1396 float rhs, weight, totweight;
1397 int i, a;
1398
1399 a = meshdeform_index(mdb, x, y, z, 0);
1400 if (!mdb->semibound[a]) {
1401 return;
1402 }
1403
1404 mdb->phi[a] = 0.0f;
1405
1406 totweight = meshdeform_boundary_total_weight(mdb, x, y, z);
1407 for (i = 1; i <= 6; i++) {
1408 isect = mdb->boundisect[a][i - 1];
1409
1410 if (isect) {
1411 weight = (1.0f / isect->len) / totweight;
1412 rhs = weight * meshdeform_boundary_phi(mdb, isect, cagevert);
1413 mdb->phi[a] += rhs;
1414 }
1415 }
1416}
1417
1419 MeshDeformBind *mdb, int x, int y, int z, int /*cagevert*/)
1420{
1421 float phi, totweight;
1422 int i, a, acenter;
1423
1424 acenter = meshdeform_index(mdb, x, y, z, 0);
1425 if (mdb->tag[acenter] != MESHDEFORM_TAG_EXTERIOR || mdb->semibound[acenter]) {
1426 return;
1427 }
1428
1429 phi = 0.0f;
1430 totweight = 0.0f;
1431 for (i = 1; i <= 6; i++) {
1432 a = meshdeform_index(mdb, x, y, z, i);
1433
1434 if (a != -1 && mdb->semibound[a]) {
1435 phi += mdb->phi[a];
1436 totweight += 1.0f;
1437 }
1438 }
1439
1440 if (totweight != 0.0f) {
1441 mdb->phi[acenter] = phi / totweight;
1442 }
1443}
1444
1446{
1447 LinearSolver *context;
1448 float vec[3], gridvec[3];
1449 int a, b, x, y, z, totvar;
1450 char message[256];
1451
1452 /* setup variable indices */
1453 mdb->varidx = MEM_new_array_zeroed<int>(mdb->size3, "MeshDeformDSvaridx");
1454 for (a = 0, totvar = 0; a < mdb->size3; a++) {
1455 mdb->varidx[a] = (mdb->tag[a] == MESHDEFORM_TAG_EXTERIOR) ? -1 : totvar++;
1456 }
1457
1458 if (totvar == 0) {
1459 MEM_delete(mdb->varidx);
1460 return;
1461 }
1462
1463 progress_bar(0, "Starting mesh deform solve");
1464
1465 /* setup linear solver */
1466 context = EIG_linear_solver_new(totvar, totvar, 1);
1467
1468 /* build matrix */
1469 for (z = 0; z < mdb->size; z++) {
1470 for (y = 0; y < mdb->size; y++) {
1471 for (x = 0; x < mdb->size; x++) {
1472 meshdeform_matrix_add_cell(mdb, context, x, y, z);
1473 }
1474 }
1475 }
1476
1477 /* solve for each cage vert */
1478 for (a = 0; a < mdb->cage_verts_num; a++) {
1479 /* fill in right hand side and solve */
1480 for (z = 0; z < mdb->size; z++) {
1481 for (y = 0; y < mdb->size; y++) {
1482 for (x = 0; x < mdb->size; x++) {
1483 meshdeform_matrix_add_rhs(mdb, context, x, y, z, a);
1484 }
1485 }
1486 }
1487
1488 if (EIG_linear_solver_solve(context)) {
1489 for (z = 0; z < mdb->size; z++) {
1490 for (y = 0; y < mdb->size; y++) {
1491 for (x = 0; x < mdb->size; x++) {
1493 }
1494 }
1495 }
1496
1497 for (z = 0; z < mdb->size; z++) {
1498 for (y = 0; y < mdb->size; y++) {
1499 for (x = 0; x < mdb->size; x++) {
1501 }
1502 }
1503 }
1504
1505 for (b = 0; b < mdb->size3; b++) {
1506 if (mdb->tag[b] != MESHDEFORM_TAG_EXTERIOR) {
1507 mdb->phi[b] = EIG_linear_solver_variable_get(context, 0, mdb->varidx[b]);
1508 }
1509 mdb->totalphi[b] += mdb->phi[b];
1510 }
1511
1512 if (mdb->weights) {
1513 /* static bind : compute weights for each vertex */
1514 for (b = 0; b < mdb->verts_num; b++) {
1515 if (mdb->inside[b]) {
1516 copy_v3_v3(vec, mdb->vertexcos[b]);
1517 gridvec[0] = (vec[0] - mdb->min[0] - mdb->halfwidth[0]) / mdb->width[0];
1518 gridvec[1] = (vec[1] - mdb->min[1] - mdb->halfwidth[1]) / mdb->width[1];
1519 gridvec[2] = (vec[2] - mdb->min[2] - mdb->halfwidth[2]) / mdb->width[2];
1520
1521 mdb->weights[b * mdb->cage_verts_num + a] = meshdeform_interp_w(mdb, gridvec, vec, a);
1522 }
1523 }
1524 }
1525 else {
1526 MDefBindInfluence *inf;
1527
1528 /* dynamic bind */
1529 for (b = 0; b < mdb->size3; b++) {
1530 if (mdb->phi[b] >= MESHDEFORM_MIN_INFLUENCE) {
1531 inf = static_cast<MDefBindInfluence *>(
1532 BLI_memarena_alloc(mdb->memarena, sizeof(*inf)));
1533 inf->vertex = a;
1534 inf->weight = mdb->phi[b];
1535 inf->next = mdb->dyngrid[b];
1536 mdb->dyngrid[b] = inf;
1537 }
1538 }
1539 }
1540 }
1541 else {
1543 mmd->object, &mmd->modifier, "Failed to find bind solution (increase precision?)");
1544 error("Mesh Deform: failed to find bind solution.");
1545 break;
1546 }
1547
1548 SNPRINTF_UTF8(message, "Mesh deform solve %d / %d |||", a + 1, mdb->cage_verts_num);
1549 progress_bar(float(a + 1) / float(mdb->cage_verts_num), message);
1550 }
1551
1552#if 0
1553 /* sanity check */
1554 for (b = 0; b < mdb->size3; b++) {
1555 if (mdb->tag[b] != MESHDEFORM_TAG_EXTERIOR) {
1556 if (fabsf(mdb->totalphi[b] - 1.0f) > 1e-4f) {
1557 printf("totalphi deficiency [%s|%d] %d: %.10f\n",
1558 (mdb->tag[b] == MESHDEFORM_TAG_INTERIOR) ? "interior" : "boundary",
1559 mdb->semibound[b],
1560 mdb->varidx[b],
1561 mdb->totalphi[b]);
1562 }
1563 }
1564 }
1565#endif
1566
1567 /* free */
1568 MEM_delete(mdb->varidx);
1569
1570 EIG_linear_solver_delete(context);
1571}
1572
1574{
1575 MDefBindInfluence *inf;
1576 MDefInfluence *mdinf;
1577 MDefCell *cell;
1578 float center[3], vec[3], maxwidth, totweight;
1579 int a, b, x, y, z, totinside, offset;
1580
1581 /* compute bounding box of the cage mesh */
1582 INIT_MINMAX(mdb->min, mdb->max);
1583
1584 for (a = 0; a < mdb->cage_verts_num; a++) {
1585 minmax_v3v3_v3(mdb->min, mdb->max, mdb->cagecos[a]);
1586 }
1587
1588 /* allocate memory */
1589 mdb->size = (2 << (mmd->gridsize - 1)) + 2;
1590 mdb->size3 = mdb->size * mdb->size * mdb->size;
1591 mdb->tag = MEM_new_array_zeroed<int>(mdb->size3, "MeshDeformBindTag");
1592 mdb->phi = MEM_new_array_zeroed<float>(mdb->size3, "MeshDeformBindPhi");
1593 mdb->totalphi = MEM_new_array_zeroed<float>(mdb->size3, "MeshDeformBindTotalPhi");
1594 mdb->boundisect = MEM_new_array_zeroed<MDefBoundIsect *[6]>(mdb->size3, "MDefBoundIsect");
1595 mdb->semibound = MEM_new_array_zeroed<int>(mdb->size3, "MDefSemiBound");
1596 mdb->bvhdata = mdb->cagemesh->bvh_corner_tris();
1597 mdb->bvhtree = mdb->bvhdata.tree;
1598 mdb->inside = MEM_new_array_zeroed<int>(mdb->verts_num, "MDefInside");
1599
1600 if (mmd->flag & MOD_MDEF_DYNAMIC_BIND) {
1601 mdb->dyngrid = MEM_new_array_zeroed<MDefBindInfluence *>(mdb->size3, "MDefDynGrid");
1602 }
1603 else {
1605 "MDefWeights");
1606 }
1607
1608 mdb->memarena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "harmonic coords arena");
1610
1611 /* Initialize data from `cagedm` for reuse. */
1612 {
1613 Mesh *mesh = mdb->cagemesh;
1614 mdb->cagemesh_cache.faces = mesh->faces();
1615 mdb->cagemesh_cache.corner_verts = mesh->corner_verts();
1616 mdb->cagemesh_cache.corner_tris = mesh->corner_tris();
1617 mdb->cagemesh_cache.tri_faces = mesh->corner_tri_faces();
1618 mdb->cagemesh_cache.face_normals = mesh->face_normals();
1619 }
1620
1621 /* make bounding box equal size in all directions, add padding, and compute
1622 * width of the cells */
1623 maxwidth = -1.0f;
1624 for (a = 0; a < 3; a++) {
1625 maxwidth = std::max(mdb->max[a] - mdb->min[a], maxwidth);
1626 }
1627
1628 for (a = 0; a < 3; a++) {
1629 center[a] = (mdb->min[a] + mdb->max[a]) * 0.5f;
1630 mdb->min[a] = center[a] - maxwidth * 0.5f;
1631 mdb->max[a] = center[a] + maxwidth * 0.5f;
1632
1633 mdb->width[a] = (mdb->max[a] - mdb->min[a]) / (mdb->size - 4);
1634 mdb->min[a] -= 2.1f * mdb->width[a];
1635 mdb->max[a] += 2.1f * mdb->width[a];
1636
1637 mdb->width[a] = (mdb->max[a] - mdb->min[a]) / mdb->size;
1638 mdb->halfwidth[a] = mdb->width[a] * 0.5f;
1639 }
1640
1641 progress_bar(0, "Setting up mesh deform system");
1642
1643 totinside = 0;
1644 for (a = 0; a < mdb->verts_num; a++) {
1645 copy_v3_v3(vec, mdb->vertexcos[a]);
1646 mdb->inside[a] = meshdeform_inside_cage(mdb, vec);
1647 if (mdb->inside[a]) {
1648 totinside++;
1649 }
1650 }
1651 (void)totinside; /* Quiet set-but-unused warning (may be removed). */
1652
1653 /* free temporary MDefBoundIsects */
1655 mdb->memarena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "harmonic coords arena");
1656
1657 /* start with all cells untyped */
1658 for (a = 0; a < mdb->size3; a++) {
1659 mdb->tag[a] = MESHDEFORM_TAG_UNTYPED;
1660 }
1661
1662 /* detect intersections and tag boundary cells */
1663 for (z = 0; z < mdb->size; z++) {
1664 for (y = 0; y < mdb->size; y++) {
1665 for (x = 0; x < mdb->size; x++) {
1667 }
1668 }
1669 }
1670
1671 /* compute exterior and interior tags */
1673
1674 for (z = 0; z < mdb->size; z++) {
1675 for (y = 0; y < mdb->size; y++) {
1676 for (x = 0; x < mdb->size; x++) {
1678 }
1679 }
1680 }
1681
1682 /* solve */
1683 meshdeform_matrix_solve(mmd, mdb);
1684
1685 /* assign results */
1686 if (mmd->flag & MOD_MDEF_DYNAMIC_BIND) {
1687 mmd->influences_num = 0;
1688 for (a = 0; a < mdb->size3; a++) {
1689 for (inf = mdb->dyngrid[a]; inf; inf = inf->next) {
1690 mmd->influences_num++;
1691 }
1692 }
1693
1694 /* convert MDefBindInfluences to smaller MDefInfluences */
1695 mmd->dyngrid = MEM_new_array<MDefCell>(mdb->size3, "MDefDynGrid");
1697 mmd->dyninfluences = MEM_new_array<MDefInfluence>(mmd->influences_num, "MDefInfluence");
1699 offset = 0;
1700 for (a = 0; a < mdb->size3; a++) {
1701 cell = &mmd->dyngrid[a];
1702 cell->offset = offset;
1703
1704 totweight = 0.0f;
1705 mdinf = mmd->dyninfluences + cell->offset;
1706 for (inf = mdb->dyngrid[a]; inf; inf = inf->next, mdinf++) {
1707 mdinf->weight = inf->weight;
1708 mdinf->vertex = inf->vertex;
1709 totweight += mdinf->weight;
1710 cell->influences_num++;
1711 }
1712
1713 if (totweight > 0.0f) {
1714 mdinf = mmd->dyninfluences + cell->offset;
1715 for (b = 0; b < cell->influences_num; b++, mdinf++) {
1716 mdinf->weight /= totweight;
1717 }
1718 }
1719
1720 offset += cell->influences_num;
1721 }
1722
1723 mmd->dynverts = mdb->inside;
1725 mmd->dyngridsize = mdb->size;
1726 copy_v3_v3(mmd->dyncellmin, mdb->min);
1727 mmd->dyncellwidth = mdb->width[0];
1728 MEM_delete(mdb->dyngrid);
1729 }
1730 else {
1731 mmd->bindweights = mdb->weights;
1732 MEM_delete(mdb->inside);
1733 }
1734
1735 MEM_delete(mdb->tag);
1736 MEM_delete(mdb->phi);
1737 MEM_delete(mdb->totalphi);
1738 MEM_delete(mdb->boundisect);
1739 MEM_delete(mdb->semibound);
1741}
1742
1745 Mesh *cagemesh,
1746 float *vertexcos,
1747 int verts_num,
1748 float cagemat[4][4])
1749{
1750 MeshDeformModifierData *mmd_orig = reinterpret_cast<MeshDeformModifierData *>(
1751 BKE_modifier_get_original(object, &mmd->modifier));
1752 MeshDeformBind mdb{};
1753 int a;
1754
1755 waitcursor(1);
1757
1758 /* No need to support other kinds of mesh data as binding is a one-off action. */
1760
1761 /* get mesh and cage mesh */
1762 mdb.vertexcos = MEM_new_array_zeroed<float[3]>(verts_num, "MeshDeformCos");
1763 mdb.verts_num = verts_num;
1764
1765 mdb.cagemesh = cagemesh;
1767 mdb.cagecos = MEM_new_array_zeroed<float[3]>(mdb.cage_verts_num, "MeshDeformBindCos");
1768 copy_m4_m4(mdb.cagemat, cagemat);
1769
1770 const Span<float3> positions = mdb.cagemesh->vert_positions();
1771 for (a = 0; a < mdb.cage_verts_num; a++) {
1772 copy_v3_v3(mdb.cagecos[a], positions[a]);
1773 }
1774 for (a = 0; a < mdb.verts_num; a++) {
1775 mul_v3_m4v3(mdb.vertexcos[a], mdb.cagemat, vertexcos + a * 3);
1776 }
1777
1778 /* solve */
1779 harmonic_coordinates_bind(mmd_orig, &mdb);
1780
1781 /* assign bind variables */
1782 mmd_orig->bindcagecos = reinterpret_cast<float *>(mdb.cagecos);
1784 mmd_orig->verts_num = mdb.verts_num;
1785 mmd_orig->cage_verts_num = mdb.cage_verts_num;
1786 copy_m4_m4(mmd_orig->bindmat, mmd_orig->object->object_to_world().ptr());
1787
1788 /* transform bindcagecos to world space */
1789 for (a = 0; a < mdb.cage_verts_num; a++) {
1790 mul_m4_v3(mmd_orig->object->object_to_world().ptr(), mmd_orig->bindcagecos + a * 3);
1791 }
1792
1793 /* free */
1794 MEM_delete(mdb.vertexcos);
1795
1796 /* compact weights */
1797 BKE_modifier_mdef_compact_influences(reinterpret_cast<ModifierData *>(mmd_orig));
1798
1800 waitcursor(0);
1801}
1802
1803} // namespace blender
#define BVH_RAYCAST_DIST_MAX
#define DEG2RADF(_deg)
#define BLI_MEMARENA_STD_BUFSIZE
#define SNPRINTF_UTF8(dst, format,...)
Object is a sort of wrapper for general info.
#define WEIGHT_REPLACE
#define WEIGHT_ADD
Read Blender memory allocation and freeing.
#define CLAMP(a, b, c)
#define INIT_MINMAX(min, max)
#define UNUSED_VARS(...)
#define BLI_INLINE
#define UNPACK3(a)
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
Definition btQuadWord.h:117
bool closest(btVector3 &v)
const T * data() const
Definition BLI_array.hh:323
constexpr int64_t size() const
const Value & lookup(const Key &key) const
Definition BLI_map.hh:545
auto add_or_modify(const Key &key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
Definition BLI_map.hh:481
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr bool is_empty() const
Definition BLI_span.hh:264
GAttributeReader lookup_or_default(StringRef name, AttrDomain domain, AttrType data_type, const void *default_value=nullptr) const
#define str(s)
#define vertex
LinearSolver * EIG_linear_solver_new(int num_rows, int num_columns, int num_right_hand_sides)
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)
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 dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
#define WEIGHT_LIMIT_END
#define WEIGHT_LIMIT_START
#define MESHDEFORM_MIN_INFLUENCE
#define MESHDEFORM_TAG_UNTYPED
#define MESHDEFORM_TAG_BOUNDARY
#define MESHDEFORM_TAG_INTERIOR
#define MESHDEFORM_LEN_THRESHOLD
#define C_WEIGHT
#define DISTANCE_EPSILON
#define MESHDEFORM_TAG_EXTERIOR
void corner_tris_calc(Span< float3 > vert_positions, OffsetIndices< int > faces, Span< int > corner_verts, MutableSpan< int3 > corner_tris)
float vgroup_vert_weight(Object *ob, bDeformGroup *dg, int vertnum)
void vgroup_vert_add(Object *ob, bDeformGroup *dg, int vertnum, float weight, int assignmode)
void vgroup_vert_remove(Object *ob, bDeformGroup *dg, int vertnum)
const ImplicitSharingInfo * info_for_mem_free(T *data)
BMesh Iterators.
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
static const int MESHDEFORM_OFFSET[7][3]
int laplacian_system_solve(LaplacianSystem *sys)
static void meshdeform_matrix_add_rhs(MeshDeformBind *mdb, LinearSolver *context, int x, int y, int z, int cagevert)
static void heat_ray_tree_create(LaplacianSystem *sys)
void BKE_modifier_set_error(const Object *ob, ModifierData *md, const char *format,...) ATTR_PRINTF_FORMAT(3
static void start_progress_bar()
void BLI_memarena_use_calloc(MemArena *ma) ATTR_NONNULL(1)
static void meshdeform_matrix_add_exterior_phi(MeshDeformBind *mdb, int x, int y, int z, int)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
static float meshdeform_boundary_phi(const MeshDeformBind *mdb, const MDefBoundIsect *isect, int cagevert)
static void laplacian_system_delete(LaplacianSystem *sys)
MINLINE void copy_v3_v3(float r[3], const float a[3])
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static float heat_limit_weight(float weight)
void minmax_v3v3_v3(float min[3], float max[3], const float vec[3])
void laplacian_begin_solve(LaplacianSystem *sys, int index)
static void meshdeform_matrix_add_semibound_phi(MeshDeformBind *mdb, int x, int y, int z, int cagevert)
bool isect_ray_tri_watertight_v3(const float ray_origin[3], const struct IsectRayPrecalc *isect_precalc, const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
void laplacian_add_right_hand_side(LaplacianSystem *sys, int v, float value)
void mul_v3_m4v3(float r[3], const float mat[4][4], const float vec[3])
static float heat_source_distance(LaplacianSystem *sys, int vertex, int source)
void BLI_bvhtree_free(BVHTree *tree)
float angle_v3v3v3(const float a[3], const float b[3], const float c[3]) ATTR_WARN_UNUSED_RESULT
static void meshdeform_add_intersections(MeshDeformBind *mdb, int x, int y, int z)
int BLI_bvhtree_ray_cast_ex(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata, int flag)
void laplacian_add_vertex(LaplacianSystem *sys, float *co, int pinned)
void BLI_bvhtree_balance(BVHTree *tree)
float closest_to_line_segment_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3])
Definition math_geom.cc:403
int mesh_get_x_mirror_vert(Object *ob, Mesh *mesh_eval, int index, bool use_topology)
Definition meshtools.cc:297
void BKE_mesh_wrapper_ensure_mdata(Mesh *mesh)
static void meshdeform_bind_floodfill(MeshDeformBind *mdb)
static int laplacian_edge_count(const Map< OrderedEdge, int > &edgehash, int v1, int v2)
static void laplacian_system_construct_end(LaplacianSystem *sys)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static float meshdeform_interp_w(MeshDeformBind *mdb, const float *gridvec, float *, int)
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
static int heat_source_closest(LaplacianSystem *sys, int vertex, int source)
int BLI_bvhtree_ray_cast(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
static void meshdeform_matrix_solve(MeshDeformModifierData *mmd, MeshDeformBind *mdb)
static void heat_calc_vnormals(LaplacianSystem *sys)
MINLINE void mul_v3_fl(float r[3], float f)
void mul_m4_v3(const float M[4][4], float r[3])
static void heat_system_free(LaplacianSystem *sys)
static void bvh_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
static LaplacianSystem * laplacian_system_construct_begin(int verts_num, int faces_num, int lsq)
static void meshdeform_check_semibound(MeshDeformBind *mdb, int x, int y, int z)
VecBase< int32_t, 3 > int3
@ ME_EDIT_PAINT_VERT_SEL
@ ME_EDIT_PAINT_FACE_SEL
@ ME_EDIT_MIRROR_TOPO
BMesh const char void * data
static void end_progress_bar()
static void error(const char *str)
static void harmonic_coordinates_bind(MeshDeformModifierData *mmd, MeshDeformBind *mdb)
static void harmonic_ray_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
static int meshdeform_inside_cage(MeshDeformBind *mdb, float *co)
static void laplacian_triangle_weights(LaplacianSystem *sys, int f, int i1, int i2, int i3)
static MDefBoundIsect * meshdeform_ray_tree_intersect(MeshDeformBind *mdb, const float co1[3], const float co2[3])
static float meshdeform_boundary_total_weight(MeshDeformBind *mdb, int x, int y, int z)
void interp_weights_poly_v3(float w[], float v[][3], int n, const float co[3])
bool isect_ray_tri_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
MINLINE int poly_to_tri_count(int poly_count, int corner_count)
@ BVH_RAYCAST_WATERTIGHT
static void waitcursor(int)
MINLINE float normalize_v3_v3(float r[3], const float a[3])
static void heat_laplacian_create(LaplacianSystem *sys)
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
MINLINE float normalize_v3(float n[3])
void ED_mesh_deform_bind_callback(Object *object, MeshDeformModifierData *mmd, Mesh *cagemesh, float *vertexcos, int verts_num, float cagemat[4][4])
void heat_bone_weighting(Object *ob, Mesh *mesh, float(*verts)[3], int numbones, bDeformGroup **dgrouplist, bDeformGroup **dgroupflip, float(*root)[3], float(*tip)[3], const bool *selected, const char **r_error_str)
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 cotangent_tri_weight_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:202
static int heat_ray_source_visible(LaplacianSystem *sys, int vertex, int source)
static void laplacian_triangle_area(LaplacianSystem *sys, int i1, int i2, int i3)
float laplacian_system_get_solution(LaplacianSystem *sys, int v)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE float max_ff(float a, float b)
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:104
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
static void heat_set_H(LaplacianSystem *sys, int vertex)
static void meshdeform_matrix_add_cell(MeshDeformBind *mdb, LinearSolver *context, int x, int y, int z)
void copy_m4_m4(float m1[4][4], const float m2[4][4])
BLI_INLINE int meshdeform_index(MeshDeformBind *mdb, int x, int y, int z, int n)
BLI_INLINE void meshdeform_cell_center(MeshDeformBind *mdb, int x, int y, int z, int n, float *center)
static void progress_bar(int, const char *)
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
static void laplacian_increase_edge_count(Map< OrderedEdge, int > &edgehash, int v1, int v2)
void laplacian_add_triangle(LaplacianSystem *sys, int v1, int v2, int v3)
ModifierData * BKE_modifier_get_original(const Object *object, ModifierData *md)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BKE_modifier_mdef_compact_influences(ModifierData *md)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
#define fabsf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
struct IsectRayPrecalc * isect_precalc
Map< OrderedEdge, int > edgehash
struct blender::LaplacianSystem::HeatWeighting heat
MDefBindInfluence * next
MDefBoundIsect *(* boundisect)[6]
MDefBindInfluence ** dyngrid
struct blender::MeshDeformBind::@216130301134331141060305204241047217364301101243 cagemesh_cache
bke::BVHTreeFromMesh bvhdata
const ImplicitSharingInfoHandle * bindcagecos_sharing_info
const ImplicitSharingInfoHandle * dyngrid_sharing_info
const ImplicitSharingInfoHandle * dynverts_sharing_info
const ImplicitSharingInfoHandle * dyninfluences_sharing_info
#define N_(msgid)