Merge branch 'blender-v2.81-release'
[blender.git] / source / blender / modifiers / intern / MOD_meshdeform.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software  Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2005 by the Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup modifiers
22  */
23
24 #include "BLI_utildefines.h"
25
26 #include "BLI_math.h"
27 #include "BLI_task.h"
28
29 #include "DNA_mesh_types.h"
30 #include "DNA_meshdata_types.h"
31 #include "DNA_object_types.h"
32 #include "DNA_scene_types.h"
33
34 #include "BKE_global.h"
35 #include "BKE_library.h"
36 #include "BKE_library_query.h"
37 #include "BKE_mesh.h"
38 #include "BKE_mesh_runtime.h"
39 #include "BKE_modifier.h"
40 #include "BKE_deform.h"
41 #include "BKE_editmesh.h"
42
43 #include "MEM_guardedalloc.h"
44
45 #include "DEG_depsgraph.h"
46 #include "DEG_depsgraph_query.h"
47
48 #include "MOD_util.h"
49
50 #ifdef __SSE2__
51 #  include <emmintrin.h>
52 #endif
53
54 static void initData(ModifierData *md)
55 {
56   MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
57
58   mmd->gridsize = 5;
59 }
60
61 static void freeData(ModifierData *md)
62 {
63   MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
64
65   if (mmd->bindinfluences) {
66     MEM_freeN(mmd->bindinfluences);
67   }
68   if (mmd->bindoffsets) {
69     MEM_freeN(mmd->bindoffsets);
70   }
71   if (mmd->bindcagecos) {
72     MEM_freeN(mmd->bindcagecos);
73   }
74   if (mmd->dyngrid) {
75     MEM_freeN(mmd->dyngrid);
76   }
77   if (mmd->dyninfluences) {
78     MEM_freeN(mmd->dyninfluences);
79   }
80   if (mmd->dynverts) {
81     MEM_freeN(mmd->dynverts);
82   }
83   if (mmd->bindweights) {
84     MEM_freeN(mmd->bindweights); /* deprecated */
85   }
86   if (mmd->bindcos) {
87     MEM_freeN(mmd->bindcos); /* deprecated */
88   }
89 }
90
91 static void copyData(const ModifierData *md, ModifierData *target, const int flag)
92 {
93   const MeshDeformModifierData *mmd = (const MeshDeformModifierData *)md;
94   MeshDeformModifierData *tmmd = (MeshDeformModifierData *)target;
95
96   modifier_copyData_generic(md, target, flag);
97
98   if (mmd->bindinfluences) {
99     tmmd->bindinfluences = MEM_dupallocN(mmd->bindinfluences);
100   }
101   if (mmd->bindoffsets) {
102     tmmd->bindoffsets = MEM_dupallocN(mmd->bindoffsets);
103   }
104   if (mmd->bindcagecos) {
105     tmmd->bindcagecos = MEM_dupallocN(mmd->bindcagecos);
106   }
107   if (mmd->dyngrid) {
108     tmmd->dyngrid = MEM_dupallocN(mmd->dyngrid);
109   }
110   if (mmd->dyninfluences) {
111     tmmd->dyninfluences = MEM_dupallocN(mmd->dyninfluences);
112   }
113   if (mmd->dynverts) {
114     tmmd->dynverts = MEM_dupallocN(mmd->dynverts);
115   }
116   if (mmd->bindweights) {
117     tmmd->bindweights = MEM_dupallocN(mmd->bindweights); /* deprecated */
118   }
119   if (mmd->bindcos) {
120     tmmd->bindcos = MEM_dupallocN(mmd->bindcos); /* deprecated */
121   }
122 }
123
124 static void requiredDataMask(Object *UNUSED(ob),
125                              ModifierData *md,
126                              CustomData_MeshMasks *r_cddata_masks)
127 {
128   MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
129
130   /* ask for vertexgroups if we need them */
131   if (mmd->defgrp_name[0] != '\0') {
132     r_cddata_masks->vmask |= CD_MASK_MDEFORMVERT;
133   }
134 }
135
136 static bool isDisabled(const struct Scene *UNUSED(scene),
137                        ModifierData *md,
138                        bool UNUSED(useRenderParams))
139 {
140   MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
141
142   /* The object type check is only needed here in case we have a placeholder
143    * object assigned (because the library containing the mesh is missing).
144    *
145    * In other cases it should be impossible to have a type mismatch.
146    */
147   return !mmd->object || mmd->object->type != OB_MESH;
148 }
149
150 static void foreachObjectLink(ModifierData *md, Object *ob, ObjectWalkFunc walk, void *userData)
151 {
152   MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
153
154   walk(userData, ob, &mmd->object, IDWALK_CB_NOP);
155 }
156
157 static void updateDepsgraph(ModifierData *md, const ModifierUpdateDepsgraphContext *ctx)
158 {
159   MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
160   if (mmd->object != NULL) {
161     /* TODO(sergey): Do we need transform component here? */
162     DEG_add_object_relation(ctx->node, mmd->object, DEG_OB_COMP_GEOMETRY, "Mesh Deform Modifier");
163   }
164 }
165
166 static float meshdeform_dynamic_bind(MeshDeformModifierData *mmd, float (*dco)[3], float vec[3])
167 {
168   MDefCell *cell;
169   MDefInfluence *inf;
170   float gridvec[3], dvec[3], ivec[3], wx, wy, wz;
171   float weight, cageweight, totweight, *cageco;
172   int i, j, a, x, y, z, size;
173 #ifdef __SSE2__
174   __m128 co = _mm_setzero_ps();
175 #else
176   float co[3] = {0.0f, 0.0f, 0.0f};
177 #endif
178
179   totweight = 0.0f;
180   size = mmd->dyngridsize;
181
182   for (i = 0; i < 3; i++) {
183     gridvec[i] = (vec[i] - mmd->dyncellmin[i] - mmd->dyncellwidth * 0.5f) / mmd->dyncellwidth;
184     ivec[i] = (int)gridvec[i];
185     dvec[i] = gridvec[i] - ivec[i];
186   }
187
188   for (i = 0; i < 8; i++) {
189     if (i & 1) {
190       x = ivec[0] + 1;
191       wx = dvec[0];
192     }
193     else {
194       x = ivec[0];
195       wx = 1.0f - dvec[0];
196     }
197
198     if (i & 2) {
199       y = ivec[1] + 1;
200       wy = dvec[1];
201     }
202     else {
203       y = ivec[1];
204       wy = 1.0f - dvec[1];
205     }
206
207     if (i & 4) {
208       z = ivec[2] + 1;
209       wz = dvec[2];
210     }
211     else {
212       z = ivec[2];
213       wz = 1.0f - dvec[2];
214     }
215
216     CLAMP(x, 0, size - 1);
217     CLAMP(y, 0, size - 1);
218     CLAMP(z, 0, size - 1);
219
220     a = x + y * size + z * size * size;
221     weight = wx * wy * wz;
222
223     cell = &mmd->dyngrid[a];
224     inf = mmd->dyninfluences + cell->offset;
225     for (j = 0; j < cell->totinfluence; j++, inf++) {
226       cageco = dco[inf->vertex];
227       cageweight = weight * inf->weight;
228 #ifdef __SSE2__
229       {
230         __m128 cageweight_r = _mm_set1_ps(cageweight);
231         /* This will load one extra element, this is ok because
232          * we ignore that part of register anyway.
233          */
234         __m128 cageco_r = _mm_loadu_ps(cageco);
235         co = _mm_add_ps(co, _mm_mul_ps(cageco_r, cageweight_r));
236       }
237 #else
238       co[0] += cageweight * cageco[0];
239       co[1] += cageweight * cageco[1];
240       co[2] += cageweight * cageco[2];
241 #endif
242       totweight += cageweight;
243     }
244   }
245
246 #ifdef __SSE2__
247   copy_v3_v3(vec, (float *)&co);
248 #else
249   copy_v3_v3(vec, co);
250 #endif
251
252   return totweight;
253 }
254
255 typedef struct MeshdeformUserdata {
256   /*const*/ MeshDeformModifierData *mmd;
257   const MDeformVert *dvert;
258   /*const*/ float (*dco)[3];
259   int defgrp_index;
260   float (*vertexCos)[3];
261   float (*cagemat)[4];
262   float (*icagemat)[3];
263 } MeshdeformUserdata;
264
265 static void meshdeform_vert_task(void *__restrict userdata,
266                                  const int iter,
267                                  const TaskParallelTLS *__restrict UNUSED(tls))
268 {
269   MeshdeformUserdata *data = userdata;
270   /*const*/ MeshDeformModifierData *mmd = data->mmd;
271   const MDeformVert *dvert = data->dvert;
272   const int defgrp_index = data->defgrp_index;
273   const int *offsets = mmd->bindoffsets;
274   const MDefInfluence *__restrict influences = mmd->bindinfluences;
275   /*const*/ float(*__restrict dco)[3] = data->dco;
276   float(*vertexCos)[3] = data->vertexCos;
277   float co[3];
278   float weight, totweight, fac = 1.0f;
279
280   if (mmd->flag & MOD_MDEF_DYNAMIC_BIND) {
281     if (!mmd->dynverts[iter]) {
282       return;
283     }
284   }
285
286   if (dvert) {
287     fac = defvert_find_weight(&dvert[iter], defgrp_index);
288
289     if (mmd->flag & MOD_MDEF_INVERT_VGROUP) {
290       fac = 1.0f - fac;
291     }
292
293     if (fac <= 0.0f) {
294       return;
295     }
296   }
297
298   if (mmd->flag & MOD_MDEF_DYNAMIC_BIND) {
299     /* transform coordinate into cage's local space */
300     mul_v3_m4v3(co, data->cagemat, vertexCos[iter]);
301     totweight = meshdeform_dynamic_bind(mmd, dco, co);
302   }
303   else {
304     totweight = 0.0f;
305     zero_v3(co);
306     int start = offsets[iter];
307     int end = offsets[iter + 1];
308
309     for (int a = start; a < end; a++) {
310       weight = influences[a].weight;
311       madd_v3_v3fl(co, dco[influences[a].vertex], weight);
312       totweight += weight;
313     }
314   }
315
316   if (totweight > 0.0f) {
317     mul_v3_fl(co, fac / totweight);
318     mul_m3_v3(data->icagemat, co);
319     if (G.debug_value != 527) {
320       add_v3_v3(vertexCos[iter], co);
321     }
322     else {
323       copy_v3_v3(vertexCos[iter], co);
324     }
325   }
326 }
327
328 static void meshdeformModifier_do(ModifierData *md,
329                                   const ModifierEvalContext *ctx,
330                                   Mesh *mesh,
331                                   float (*vertexCos)[3],
332                                   int numVerts)
333 {
334   MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
335   Object *ob = ctx->object;
336
337   Mesh *cagemesh;
338   MDeformVert *dvert = NULL;
339   float imat[4][4], cagemat[4][4], iobmat[4][4], icagemat[3][3], cmat[4][4];
340   float co[3], (*dco)[3] = NULL, (*bindcagecos)[3];
341   int a, totvert, totcagevert, defgrp_index;
342   float(*cagecos)[3] = NULL;
343   MeshdeformUserdata data;
344
345   static int recursive_bind_sentinel = 0;
346
347   if (mmd->object == NULL || (mmd->bindcagecos == NULL && mmd->bindfunc == NULL)) {
348     return;
349   }
350
351   /* Get cage mesh.
352    *
353    * Only do this is the target object is in edit mode by itself, meaning
354    * we don't allow linked edit meshes here.
355    * This is because editbmesh_get_mesh_cage_and_final() might easily
356    * conflict with the thread which evaluates object which is in the edit
357    * mode for this mesh.
358    *
359    * We'll support this case once granular dependency graph is landed.
360    */
361   Object *ob_target = mmd->object;
362   cagemesh = BKE_modifier_get_evaluated_mesh_from_evaluated_object(ob_target, false);
363   if (cagemesh == NULL) {
364     modifier_setError(md, "Cannot get mesh from cage object");
365     return;
366   }
367
368   /* compute matrices to go in and out of cage object space */
369   invert_m4_m4(imat, ob_target->obmat);
370   mul_m4_m4m4(cagemat, imat, ob->obmat);
371   mul_m4_m4m4(cmat, mmd->bindmat, cagemat);
372   invert_m4_m4(iobmat, cmat);
373   copy_m3_m4(icagemat, iobmat);
374
375   /* bind weights if needed */
376   if (!mmd->bindcagecos) {
377     /* progress bar redraw can make this recursive .. */
378     if (!DEG_is_active(ctx->depsgraph)) {
379       modifier_setError(md, "Attempt to bind from inactive dependency graph");
380       goto finally;
381     }
382     if (!recursive_bind_sentinel) {
383       recursive_bind_sentinel = 1;
384       mmd->bindfunc(mmd, cagemesh, (float *)vertexCos, numVerts, cagemat);
385       recursive_bind_sentinel = 0;
386     }
387
388     goto finally;
389   }
390
391   /* verify we have compatible weights */
392   totvert = numVerts;
393   totcagevert = cagemesh->totvert;
394
395   if (mmd->totvert != totvert) {
396     modifier_setError(md, "Verts changed from %d to %d", mmd->totvert, totvert);
397     goto finally;
398   }
399   else if (mmd->totcagevert != totcagevert) {
400     modifier_setError(md, "Cage verts changed from %d to %d", mmd->totcagevert, totcagevert);
401     goto finally;
402   }
403   else if (mmd->bindcagecos == NULL) {
404     modifier_setError(md, "Bind data missing");
405     goto finally;
406   }
407
408   /* setup deformation data */
409   cagecos = BKE_mesh_vert_coords_alloc(cagemesh, NULL);
410   bindcagecos = (float(*)[3])mmd->bindcagecos;
411
412   /* We allocate 1 element extra to make it possible to
413    * load the values to SSE registers, which are float4.
414    */
415   dco = MEM_calloc_arrayN((totcagevert + 1), sizeof(*dco), "MDefDco");
416   zero_v3(dco[totcagevert]);
417   for (a = 0; a < totcagevert; a++) {
418     /* get cage vertex in world space with binding transform */
419     copy_v3_v3(co, cagecos[a]);
420
421     if (G.debug_value != 527) {
422       mul_m4_v3(mmd->bindmat, co);
423       /* compute difference with world space bind coord */
424       sub_v3_v3v3(dco[a], co, bindcagecos[a]);
425     }
426     else {
427       copy_v3_v3(dco[a], co);
428     }
429   }
430
431   MOD_get_vgroup(ob, mesh, mmd->defgrp_name, &dvert, &defgrp_index);
432
433   /* Initialize data to be pass to the for body function. */
434   data.mmd = mmd;
435   data.dvert = dvert;
436   data.dco = dco;
437   data.defgrp_index = defgrp_index;
438   data.vertexCos = vertexCos;
439   data.cagemat = cagemat;
440   data.icagemat = icagemat;
441
442   /* Do deformation. */
443   TaskParallelSettings settings;
444   BLI_parallel_range_settings_defaults(&settings);
445   settings.min_iter_per_thread = 16;
446   BLI_task_parallel_range(0, totvert, &data, meshdeform_vert_task, &settings);
447
448 finally:
449   MEM_SAFE_FREE(dco);
450   MEM_SAFE_FREE(cagecos);
451 }
452
453 static void deformVerts(ModifierData *md,
454                         const ModifierEvalContext *ctx,
455                         Mesh *mesh,
456                         float (*vertexCos)[3],
457                         int numVerts)
458 {
459   Mesh *mesh_src = MOD_deform_mesh_eval_get(ctx->object, NULL, mesh, NULL, numVerts, false, false);
460
461   MOD_previous_vcos_store(md, vertexCos); /* if next modifier needs original vertices */
462
463   meshdeformModifier_do(md, ctx, mesh_src, vertexCos, numVerts);
464
465   if (!ELEM(mesh_src, NULL, mesh)) {
466     BKE_id_free(NULL, mesh_src);
467   }
468 }
469
470 static void deformVertsEM(ModifierData *md,
471                           const ModifierEvalContext *ctx,
472                           struct BMEditMesh *editData,
473                           Mesh *mesh,
474                           float (*vertexCos)[3],
475                           int numVerts)
476 {
477   Mesh *mesh_src = MOD_deform_mesh_eval_get(
478       ctx->object, editData, mesh, NULL, numVerts, false, false);
479
480   meshdeformModifier_do(md, ctx, mesh_src, vertexCos, numVerts);
481
482   if (!ELEM(mesh_src, NULL, mesh)) {
483     BKE_id_free(NULL, mesh_src);
484   }
485 }
486
487 #define MESHDEFORM_MIN_INFLUENCE 0.00001f
488
489 void modifier_mdef_compact_influences(ModifierData *md)
490 {
491   MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
492   float weight, *weights, totweight;
493   int totinfluence, totvert, totcagevert, a, b;
494
495   weights = mmd->bindweights;
496   if (!weights) {
497     return;
498   }
499
500   totvert = mmd->totvert;
501   totcagevert = mmd->totcagevert;
502
503   /* count number of influences above threshold */
504   for (b = 0; b < totvert; b++) {
505     for (a = 0; a < totcagevert; a++) {
506       weight = weights[a + b * totcagevert];
507
508       if (weight > MESHDEFORM_MIN_INFLUENCE) {
509         mmd->totinfluence++;
510       }
511     }
512   }
513
514   /* allocate bind influences */
515   mmd->bindinfluences = MEM_calloc_arrayN(
516       mmd->totinfluence, sizeof(MDefInfluence), "MDefBindInfluence");
517   mmd->bindoffsets = MEM_calloc_arrayN((totvert + 1), sizeof(int), "MDefBindOffset");
518
519   /* write influences */
520   totinfluence = 0;
521
522   for (b = 0; b < totvert; b++) {
523     mmd->bindoffsets[b] = totinfluence;
524     totweight = 0.0f;
525
526     /* sum total weight */
527     for (a = 0; a < totcagevert; a++) {
528       weight = weights[a + b * totcagevert];
529
530       if (weight > MESHDEFORM_MIN_INFLUENCE) {
531         totweight += weight;
532       }
533     }
534
535     /* assign weights normalized */
536     for (a = 0; a < totcagevert; a++) {
537       weight = weights[a + b * totcagevert];
538
539       if (weight > MESHDEFORM_MIN_INFLUENCE) {
540         mmd->bindinfluences[totinfluence].weight = weight / totweight;
541         mmd->bindinfluences[totinfluence].vertex = a;
542         totinfluence++;
543       }
544     }
545   }
546
547   mmd->bindoffsets[b] = totinfluence;
548
549   /* free */
550   MEM_freeN(mmd->bindweights);
551   mmd->bindweights = NULL;
552 }
553
554 ModifierTypeInfo modifierType_MeshDeform = {
555     /* name */ "MeshDeform",
556     /* structName */ "MeshDeformModifierData",
557     /* structSize */ sizeof(MeshDeformModifierData),
558     /* type */ eModifierTypeType_OnlyDeform,
559     /* flags */ eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_AcceptsLattice |
560         eModifierTypeFlag_SupportsEditmode,
561
562     /* copyData */ copyData,
563
564     /* deformVerts */ deformVerts,
565     /* deformMatrices */ NULL,
566     /* deformVertsEM */ deformVertsEM,
567     /* deformMatricesEM */ NULL,
568     /* applyModifier */ NULL,
569
570     /* initData */ initData,
571     /* requiredDataMask */ requiredDataMask,
572     /* freeData */ freeData,
573     /* isDisabled */ isDisabled,
574     /* updateDepsgraph */ updateDepsgraph,
575     /* dependsOnTime */ NULL,
576     /* dependsOnNormals */ NULL,
577     /* foreachObjectLink */ foreachObjectLink,
578     /* foreachIDLink */ NULL,
579     /* foreachTexLink */ NULL,
580     /* freeRuntimeData */ NULL,
581 };