merge with/from trunk at r35190
[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 }
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         MDeformWeight *dw;
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, "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         mul_m4_m4m4(cagemat, ob->obmat, imat);
228         mul_m4_m4m4(cmat, cagemat, mmd->bindmat);
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, "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, "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, "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         defgrp_index = defgroup_name_index(ob, mmd->defgrp_name);
286
287         if(dm && defgrp_index >= 0)
288                 dvert= dm->getVertDataArray(dm, CD_MDEFORMVERT);
289
290         /* do deformation */
291         fac= 1.0f;
292
293         for(b=0; b<totvert; b++) {
294                 if(mmd->flag & MOD_MDEF_DYNAMIC_BIND)
295                         if(!mmd->dynverts[b])
296                                 continue;
297
298                 if(dvert) {
299                         for(dw=NULL, a=0; a<dvert[b].totweight; a++) {
300                                 if(dvert[b].dw[a].def_nr == defgrp_index) {
301                                         dw = &dvert[b].dw[a];
302                                         break;
303                                 }
304                         }
305
306                         if(mmd->flag & MOD_MDEF_INVERT_VGROUP) {
307                                 if(!dw) fac= 1.0f;
308                                 else if(dw->weight == 1.0f) continue;
309                                 else fac=1.0f-dw->weight;
310                         }
311                         else {
312                                 if(!dw) continue;
313                                 else fac= dw->weight;
314                         }
315                 }
316
317                 if(mmd->flag & MOD_MDEF_DYNAMIC_BIND) {
318                         /* transform coordinate into cage's local space */
319                         mul_v3_m4v3(co, cagemat, vertexCos[b]);
320                         totweight= meshdeform_dynamic_bind(mmd, dco, co);
321                 }
322                 else {
323                         totweight= 0.0f;
324                         zero_v3(co);
325
326                         for(a=offsets[b]; a<offsets[b+1]; a++) {
327                                 weight= influences[a].weight;
328                                 madd_v3_v3fl(co, dco[influences[a].vertex], weight);
329                                 totweight += weight;
330                         }
331                 }
332
333                 if(totweight > 0.0f) {
334                         mul_v3_fl(co, fac/totweight);
335                         mul_m3_v3(icagemat, co);
336                         if(G.rt != 527)
337                                 add_v3_v3(vertexCos[b], co);
338                         else
339                                 copy_v3_v3(vertexCos[b], co);
340                 }
341         }
342
343         /* release cage derivedmesh */
344         MEM_freeN(dco);
345         MEM_freeN(cagecos);
346         cagedm->release(cagedm);
347 }
348
349 static void deformVerts(ModifierData *md, Object *ob,
350                                                 DerivedMesh *derivedData,
351                                                 float (*vertexCos)[3],
352                                                 int numVerts,
353                                                 int UNUSED(useRenderParams),
354                                                 int UNUSED(isFinalCalc))
355 {
356         DerivedMesh *dm= get_dm(ob, NULL, derivedData, NULL, 0);
357
358         modifier_vgroup_cache(md, vertexCos); /* if next modifier needs original vertices */
359         
360         meshdeformModifier_do(md, ob, dm, vertexCos, numVerts);
361
362         if(dm && dm != derivedData)
363                 dm->release(dm);
364 }
365
366 static void deformVertsEM(ModifierData *md, Object *ob,
367                                                 struct EditMesh *UNUSED(editData),
368                                                 DerivedMesh *derivedData,
369                                                 float (*vertexCos)[3],
370                                                 int numVerts)
371 {
372         DerivedMesh *dm= get_dm(ob, NULL, derivedData, NULL, 0);
373
374         meshdeformModifier_do(md, ob, dm, vertexCos, numVerts);
375
376         if(dm && dm != derivedData)
377                 dm->release(dm);
378 }
379
380 #define MESHDEFORM_MIN_INFLUENCE 0.00001
381
382 void modifier_mdef_compact_influences(ModifierData *md)
383 {
384         MeshDeformModifierData *mmd= (MeshDeformModifierData*)md;
385         float weight, *weights, totweight;
386         int totinfluence, totvert, totcagevert, a, b;
387
388         weights= mmd->bindweights;
389         if(!weights)
390                 return;
391         
392         totvert= mmd->totvert;
393         totcagevert= mmd->totcagevert;
394
395         /* count number of influences above threshold */
396         for(b=0; b<totvert; b++) {
397                 for(a=0; a<totcagevert; a++) {
398                         weight= weights[a + b*totcagevert];
399
400                         if(weight > MESHDEFORM_MIN_INFLUENCE)
401                                 mmd->totinfluence++;
402                 }
403         }
404
405         /* allocate bind influences */
406         mmd->bindinfluences= MEM_callocN(sizeof(MDefInfluence)*mmd->totinfluence, "MDefBindInfluence");
407         mmd->bindoffsets= MEM_callocN(sizeof(int)*(totvert+1), "MDefBindOffset");
408
409         /* write influences */
410         totinfluence= 0;
411
412         for(b=0; b<totvert; b++) {
413                 mmd->bindoffsets[b]= totinfluence;
414                 totweight= 0.0f;
415
416                 /* sum total weight */
417                 for(a=0; a<totcagevert; a++) {
418                         weight= weights[a + b*totcagevert];
419
420                         if(weight > MESHDEFORM_MIN_INFLUENCE)
421                                 totweight += weight;
422                 }
423
424                 /* assign weights normalized */
425                 for(a=0; a<totcagevert; a++) {
426                         weight= weights[a + b*totcagevert];
427
428                         if(weight > MESHDEFORM_MIN_INFLUENCE) {
429                                 mmd->bindinfluences[totinfluence].weight= weight/totweight;
430                                 mmd->bindinfluences[totinfluence].vertex= a;
431                                 totinfluence++;
432                         }
433                 }
434         }
435
436         mmd->bindoffsets[b]= totinfluence;
437         
438         /* free */
439         MEM_freeN(mmd->bindweights);
440         mmd->bindweights= NULL;
441 }
442
443 ModifierTypeInfo modifierType_MeshDeform = {
444         /* name */              "MeshDeform",
445         /* structName */        "MeshDeformModifierData",
446         /* structSize */        sizeof(MeshDeformModifierData),
447         /* type */              eModifierTypeType_OnlyDeform,
448         /* flags */             eModifierTypeFlag_AcceptsCVs
449                                                         | eModifierTypeFlag_SupportsEditmode,
450
451         /* copyData */          copyData,
452         /* deformVerts */       deformVerts,
453         /* deformMatrices */    0,
454         /* deformVertsEM */     deformVertsEM,
455         /* deformMatricesEM */  0,
456         /* applyModifier */     0,
457         /* applyModifierEM */   0,
458         /* initData */          initData,
459         /* requiredDataMask */  requiredDataMask,
460         /* freeData */          freeData,
461         /* isDisabled */        isDisabled,
462         /* updateDepgraph */    updateDepgraph,
463         /* dependsOnTime */     0,
464         /* dependsOnNormals */  0,
465         /* foreachObjectLink */ foreachObjectLink,
466         /* foreachIDLink */     0,
467 };