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