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