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