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