afee0e2c79e2ea180af153935f1bb8533eac3ae4
[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
39 #include "BLI_math.h"
40 #include "BLI_utildefines.h"
41
42 #include "BLF_translation.h"
43
44 #include "BKE_cdderivedmesh.h"
45 #include "BKE_global.h"
46 #include "BKE_mesh.h"
47 #include "BKE_modifier.h"
48 #include "BKE_deform.h"
49 #include "BKE_tessmesh.h"
50
51 #include "depsgraph_private.h"
52
53 #include "MEM_guardedalloc.h"
54
55 #include "MOD_util.h"
56
57
58 static void initData(ModifierData *md)
59 {
60         MeshDeformModifierData *mmd = (MeshDeformModifierData*) md;
61
62         mmd->gridsize= 5;
63 }
64
65 static void freeData(ModifierData *md)
66 {
67         MeshDeformModifierData *mmd = (MeshDeformModifierData*) md;
68
69         if(mmd->bindinfluences) MEM_freeN(mmd->bindinfluences);
70         if(mmd->bindoffsets) MEM_freeN(mmd->bindoffsets);
71         if(mmd->bindcagecos) MEM_freeN(mmd->bindcagecos);
72         if(mmd->dyngrid) MEM_freeN(mmd->dyngrid);
73         if(mmd->dyninfluences) MEM_freeN(mmd->dyninfluences);
74         if(mmd->dynverts) MEM_freeN(mmd->dynverts);
75         if(mmd->bindweights) MEM_freeN(mmd->bindweights); /* deprecated */
76         if(mmd->bindcos) MEM_freeN(mmd->bindcos); /* deprecated */
77 }
78
79 static void copyData(ModifierData *md, ModifierData *target)
80 {
81         MeshDeformModifierData *mmd = (MeshDeformModifierData*) md;
82         MeshDeformModifierData *tmmd = (MeshDeformModifierData*) target;
83
84         tmmd->gridsize = mmd->gridsize;
85         tmmd->object = mmd->object;
86 }
87
88 static CustomDataMask requiredDataMask(Object *UNUSED(ob), ModifierData *md)
89 {       
90         MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
91         CustomDataMask dataMask = 0;
92
93         /* ask for vertexgroups if we need them */
94         if(mmd->defgrp_name[0]) dataMask |= CD_MASK_MDEFORMVERT;
95
96         return dataMask;
97 }
98
99 static int isDisabled(ModifierData *md, int UNUSED(useRenderParams))
100 {
101         MeshDeformModifierData *mmd = (MeshDeformModifierData*) md;
102
103         return !mmd->object;
104 }
105
106 static void foreachObjectLink(
107                 ModifierData *md, Object *ob,
108   void (*walk)(void *userData, Object *ob, Object **obpoin),
109          void *userData)
110 {
111         MeshDeformModifierData *mmd = (MeshDeformModifierData*) md;
112
113         walk(userData, ob, &mmd->object);
114 }
115
116 static void updateDepgraph(ModifierData *md, DagForest *forest,
117                                                 struct Scene *UNUSED(scene),
118                                                 Object *UNUSED(ob),
119                                                 DagNode *obNode)
120 {
121         MeshDeformModifierData *mmd = (MeshDeformModifierData*) md;
122
123         if (mmd->object) {
124                 DagNode *curNode = dag_get_node(forest, mmd->object);
125
126                 dag_add_relation(forest, curNode, obNode,
127                                  DAG_RL_DATA_DATA|DAG_RL_OB_DATA|DAG_RL_DATA_OB|DAG_RL_OB_OB,
128                                  "Mesh Deform Modifier");
129         }
130 }
131
132 static float meshdeform_dynamic_bind(MeshDeformModifierData *mmd, float (*dco)[3], float *vec)
133 {
134         MDefCell *cell;
135         MDefInfluence *inf;
136         float gridvec[3], dvec[3], ivec[3], co[3], wx, wy, wz;
137         float weight, cageweight, totweight, *cageco;
138         int i, j, a, x, y, z, size;
139
140         zero_v3(co);
141         totweight= 0.0f;
142         size= mmd->dyngridsize;
143
144         for(i=0; i<3; i++) {
145                 gridvec[i]= (vec[i] - mmd->dyncellmin[i] - mmd->dyncellwidth*0.5f)/mmd->dyncellwidth;
146                 ivec[i]= (int)gridvec[i];
147                 dvec[i]= gridvec[i] - ivec[i];
148         }
149
150         for(i=0; i<8; i++) {
151                 if(i & 1) { x= ivec[0]+1; wx= dvec[0]; }
152                 else { x= ivec[0]; wx= 1.0f-dvec[0]; } 
153
154                 if(i & 2) { y= ivec[1]+1; wy= dvec[1]; }
155                 else { y= ivec[1]; wy= 1.0f-dvec[1]; } 
156
157                 if(i & 4) { z= ivec[2]+1; wz= dvec[2]; }
158                 else { z= ivec[2]; wz= 1.0f-dvec[2]; } 
159
160                 CLAMP(x, 0, size-1);
161                 CLAMP(y, 0, size-1);
162                 CLAMP(z, 0, size-1);
163
164                 a= x + y*size + z*size*size;
165                 weight= wx*wy*wz;
166
167                 cell= &mmd->dyngrid[a];
168                 inf= mmd->dyninfluences + cell->offset;
169                 for(j=0; j<cell->totinfluence; j++, inf++) {
170                         cageco= dco[inf->vertex];
171                         cageweight= weight*inf->weight;
172                         co[0] += cageweight*cageco[0];
173                         co[1] += cageweight*cageco[1];
174                         co[2] += cageweight*cageco[2];
175                         totweight += cageweight;
176                 }
177         }
178
179         copy_v3_v3(vec, co);
180
181         return totweight;
182 }
183
184 static void meshdeformModifier_do(
185           ModifierData *md, Object *ob, DerivedMesh *dm,
186           float (*vertexCos)[3], int numVerts)
187 {
188         MeshDeformModifierData *mmd = (MeshDeformModifierData*) md;
189         struct Mesh *me= (mmd->object)? mmd->object->data: NULL;
190         BMEditMesh *em = me ? me->edit_btmesh : NULL;
191         DerivedMesh *tmpdm, *cagedm;
192         MDeformVert *dvert = NULL;
193         MDefInfluence *influences;
194         int *offsets;
195         float imat[4][4], cagemat[4][4], iobmat[4][4], icagemat[3][3], cmat[4][4];
196         float weight, totweight, fac, co[3], (*dco)[3], (*bindcagecos)[3];
197         int a, b, totvert, totcagevert, defgrp_index;
198         float (*cagecos)[3];
199
200         if(!mmd->object || (!mmd->bindcagecos && !mmd->bindfunc))
201                 return;
202         
203         /* get cage derivedmesh */
204         if(em) {
205                 tmpdm= editbmesh_get_derived_cage_and_final(md->scene, ob, em, &cagedm, 0);
206                 if(tmpdm)
207                         tmpdm->release(tmpdm);
208         }
209         else
210                 cagedm= mmd->object->derivedFinal;
211
212         /* if we don't have one computed, use derivedmesh from data
213          * without any modifiers */
214         if(!cagedm) {
215                 cagedm= get_dm(mmd->object, NULL, NULL, NULL, 0);
216                 if(cagedm)
217                         cagedm->needsFree= 1;
218         }
219         
220         if(!cagedm) {
221                 modifier_setError(md, TIP_("Can't get mesh from cage object."));
222                 return;
223         }
224
225         /* compute matrices to go in and out of cage object space */
226         invert_m4_m4(imat, mmd->object->obmat);
227         mult_m4_m4m4(cagemat, imat, ob->obmat);
228         mult_m4_m4m4(cmat, mmd->bindmat, cagemat);
229         invert_m4_m4(iobmat, cmat);
230         copy_m3_m4(icagemat, iobmat);
231
232         /* bind weights if needed */
233         if(!mmd->bindcagecos) {
234                 static int recursive = 0;
235
236                 /* progress bar redraw can make this recursive .. */
237                 if(!recursive) {
238                         recursive = 1;
239                         mmd->bindfunc(md->scene, mmd, (float*)vertexCos, numVerts, cagemat);
240                         recursive = 0;
241                 }
242         }
243
244         /* verify we have compatible weights */
245         totvert= numVerts;
246         totcagevert= cagedm->getNumVerts(cagedm);
247
248         if(mmd->totvert != totvert) {
249                 modifier_setError(md, TIP_("Verts changed from %d to %d."), mmd->totvert, totvert);
250                 cagedm->release(cagedm);
251                 return;
252         }
253         else if (mmd->totcagevert != totcagevert) {
254                 modifier_setError(md, TIP_("Cage verts changed from %d to %d."), mmd->totcagevert, totcagevert);
255                 cagedm->release(cagedm);
256                 return;
257         } else if (mmd->bindcagecos == NULL) {
258                 modifier_setError(md, TIP_("Bind data missing."));
259                 cagedm->release(cagedm);
260                 return;
261         }
262
263         cagecos= MEM_callocN(sizeof(*cagecos)*totcagevert, "meshdeformModifier vertCos");
264
265         /* setup deformation data */
266         cagedm->getVertCos(cagedm, cagecos);
267         influences= mmd->bindinfluences;
268         offsets= mmd->bindoffsets;
269         bindcagecos= (float(*)[3])mmd->bindcagecos;
270
271         dco= MEM_callocN(sizeof(*dco)*totcagevert, "MDefDco");
272         for(a=0; a<totcagevert; a++) {
273                 /* get cage vertex in world space with binding transform */
274                 copy_v3_v3(co, cagecos[a]);
275
276                 if(G.rt != 527) {
277                         mul_m4_v3(mmd->bindmat, co);
278                         /* compute difference with world space bind coord */
279                         sub_v3_v3v3(dco[a], co, bindcagecos[a]);
280                 }
281                 else
282                         copy_v3_v3(dco[a], co);
283         }
284
285         modifier_get_vgroup(ob, dm, mmd->defgrp_name, &dvert, &defgrp_index);
286
287         /* do deformation */
288         fac= 1.0f;
289
290         for(b=0; b<totvert; b++) {
291                 if(mmd->flag & MOD_MDEF_DYNAMIC_BIND)
292                         if(!mmd->dynverts[b])
293                                 continue;
294
295                 if(dvert) {
296                         fac= defvert_find_weight(&dvert[b], defgrp_index);
297
298                         if (mmd->flag & MOD_MDEF_INVERT_VGROUP) {
299                                 fac= 1.0f - fac;
300                         }
301
302                         if (fac <= 0.0f) {
303                                 continue;
304                         }
305                 }
306
307                 if(mmd->flag & MOD_MDEF_DYNAMIC_BIND) {
308                         /* transform coordinate into cage's local space */
309                         mul_v3_m4v3(co, cagemat, vertexCos[b]);
310                         totweight= meshdeform_dynamic_bind(mmd, dco, co);
311                 }
312                 else {
313                         totweight= 0.0f;
314                         zero_v3(co);
315
316                         for(a=offsets[b]; a<offsets[b+1]; a++) {
317                                 weight= influences[a].weight;
318                                 madd_v3_v3fl(co, dco[influences[a].vertex], weight);
319                                 totweight += weight;
320                         }
321                 }
322
323                 if(totweight > 0.0f) {
324                         mul_v3_fl(co, fac/totweight);
325                         mul_m3_v3(icagemat, co);
326                         if(G.rt != 527)
327                                 add_v3_v3(vertexCos[b], co);
328                         else
329                                 copy_v3_v3(vertexCos[b], co);
330                 }
331         }
332
333         /* release cage derivedmesh */
334         MEM_freeN(dco);
335         MEM_freeN(cagecos);
336         cagedm->release(cagedm);
337 }
338
339 static void deformVerts(ModifierData *md, Object *ob,
340                                                 DerivedMesh *derivedData,
341                                                 float (*vertexCos)[3],
342                                                 int numVerts,
343                                                 int UNUSED(useRenderParams),
344                                                 int UNUSED(isFinalCalc))
345 {
346         DerivedMesh *dm= get_dm(ob, NULL, derivedData, NULL, 0);
347
348         modifier_vgroup_cache(md, vertexCos); /* if next modifier needs original vertices */
349         
350         meshdeformModifier_do(md, ob, dm, vertexCos, numVerts);
351
352         if(dm && dm != derivedData)
353                 dm->release(dm);
354 }
355
356 static void deformVertsEM(ModifierData *md, Object *ob,
357                                                 struct BMEditMesh *UNUSED(editData),
358                                                 DerivedMesh *derivedData,
359                                                 float (*vertexCos)[3],
360                                                 int numVerts)
361 {
362         DerivedMesh *dm= get_dm(ob, NULL, derivedData, NULL, 0);
363
364         meshdeformModifier_do(md, ob, dm, vertexCos, numVerts);
365
366         if(dm && dm != derivedData)
367                 dm->release(dm);
368 }
369
370 #define MESHDEFORM_MIN_INFLUENCE 0.00001f
371
372 void modifier_mdef_compact_influences(ModifierData *md)
373 {
374         MeshDeformModifierData *mmd= (MeshDeformModifierData*)md;
375         float weight, *weights, totweight;
376         int totinfluence, totvert, totcagevert, a, b;
377
378         weights= mmd->bindweights;
379         if(!weights)
380                 return;
381         
382         totvert= mmd->totvert;
383         totcagevert= mmd->totcagevert;
384
385         /* count number of influences above threshold */
386         for(b=0; b<totvert; b++) {
387                 for(a=0; a<totcagevert; a++) {
388                         weight= weights[a + b*totcagevert];
389
390                         if(weight > MESHDEFORM_MIN_INFLUENCE)
391                                 mmd->totinfluence++;
392                 }
393         }
394
395         /* allocate bind influences */
396         mmd->bindinfluences= MEM_callocN(sizeof(MDefInfluence)*mmd->totinfluence, "MDefBindInfluence");
397         mmd->bindoffsets= MEM_callocN(sizeof(int)*(totvert+1), "MDefBindOffset");
398
399         /* write influences */
400         totinfluence= 0;
401
402         for(b=0; b<totvert; b++) {
403                 mmd->bindoffsets[b]= totinfluence;
404                 totweight= 0.0f;
405
406                 /* sum total weight */
407                 for(a=0; a<totcagevert; a++) {
408                         weight= weights[a + b*totcagevert];
409
410                         if(weight > MESHDEFORM_MIN_INFLUENCE)
411                                 totweight += weight;
412                 }
413
414                 /* assign weights normalized */
415                 for(a=0; a<totcagevert; a++) {
416                         weight= weights[a + b*totcagevert];
417
418                         if(weight > MESHDEFORM_MIN_INFLUENCE) {
419                                 mmd->bindinfluences[totinfluence].weight= weight/totweight;
420                                 mmd->bindinfluences[totinfluence].vertex= a;
421                                 totinfluence++;
422                         }
423                 }
424         }
425
426         mmd->bindoffsets[b]= totinfluence;
427         
428         /* free */
429         MEM_freeN(mmd->bindweights);
430         mmd->bindweights= NULL;
431 }
432
433 ModifierTypeInfo modifierType_MeshDeform = {
434         /* name */              "MeshDeform",
435         /* structName */        "MeshDeformModifierData",
436         /* structSize */        sizeof(MeshDeformModifierData),
437         /* type */              eModifierTypeType_OnlyDeform,
438         /* flags */             eModifierTypeFlag_AcceptsCVs
439                                                         | eModifierTypeFlag_SupportsEditmode,
440
441         /* copyData */          copyData,
442         /* deformVerts */       deformVerts,
443         /* deformMatrices */    NULL,
444         /* deformVertsEM */     deformVertsEM,
445         /* deformMatricesEM */  NULL,
446         /* applyModifier */     NULL,
447         /* applyModifierEM */   NULL,
448         /* initData */          initData,
449         /* requiredDataMask */  requiredDataMask,
450         /* freeData */          freeData,
451         /* isDisabled */        isDisabled,
452         /* updateDepgraph */    updateDepgraph,
453         /* dependsOnTime */     NULL,
454         /* dependsOnNormals */  NULL,
455         /* foreachObjectLink */ foreachObjectLink,
456         /* foreachIDLink */     NULL,
457         /* foreachTexLink */    NULL,
458 };