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