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