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