5e01a20d93b70334477769ed6e5109b3ee3a5d01
[blender-staging.git] / source / blender / modifiers / intern / MOD_mask.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_mask.c
32  *  \ingroup modifiers
33  */
34
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BLI_utildefines.h"
39 #include "BLI_listbase.h"
40 #include "BLI_ghash.h"
41
42 #include "DNA_armature_types.h"
43 #include "DNA_meshdata_types.h"
44 #include "DNA_modifier_types.h"
45 #include "DNA_object_types.h"
46
47 #include "BKE_action.h" /* BKE_pose_channel_find_name */
48 #include "BKE_cdderivedmesh.h"
49 #include "BKE_library_query.h"
50 #include "BKE_modifier.h"
51 #include "BKE_deform.h"
52
53 #include "depsgraph_private.h"
54 #include "DEG_depsgraph_build.h"
55
56 #include "BLI_strict_flags.h"
57
58 static void copyData(ModifierData *md, ModifierData *target)
59 {
60 #if 0
61         MaskModifierData *mmd = (MaskModifierData *) md;
62         MaskModifierData *tmmd = (MaskModifierData *) target;
63 #endif
64         modifier_copyData_generic(md, target);
65 }
66
67 static CustomDataMask requiredDataMask(Object *UNUSED(ob), ModifierData *UNUSED(md))
68 {
69         return CD_MASK_MDEFORMVERT;
70 }
71
72 static void foreachObjectLink(
73         ModifierData *md, Object *ob,
74         ObjectWalkFunc walk, void *userData)
75 {
76         MaskModifierData *mmd = (MaskModifierData *)md;
77         walk(userData, ob, &mmd->ob_arm, IDWALK_NOP);
78 }
79
80 static void updateDepgraph(ModifierData *md, DagForest *forest,
81                            struct Main *UNUSED(bmain),
82                            struct Scene *UNUSED(scene),
83                            Object *UNUSED(ob),
84                            DagNode *obNode)
85 {
86         MaskModifierData *mmd = (MaskModifierData *)md;
87
88         if (mmd->ob_arm) {
89                 bArmature *arm = (bArmature *)mmd->ob_arm->data;
90                 DagNode *armNode = dag_get_node(forest, mmd->ob_arm);
91                 
92                 /* tag relationship in depsgraph, but also on the armature */
93                 dag_add_relation(forest, armNode, obNode, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Mask Modifier");
94                 arm->flag |= ARM_HAS_VIZ_DEPS;
95         }
96 }
97
98 static void updateDepsgraph(ModifierData *md,
99                             struct Main *UNUSED(bmain),
100                             struct Scene *UNUSED(scene),
101                             Object *UNUSED(ob),
102                             struct DepsNodeHandle *node)
103 {
104         MaskModifierData *mmd = (MaskModifierData *)md;
105         if (mmd->ob_arm) {
106                 bArmature *arm = (bArmature *)mmd->ob_arm->data;
107                 /* Tag relationship in depsgraph, but also on the armature. */
108                 /* TODO(sergey): Is it a proper relation here? */
109                 DEG_add_object_relation(node, mmd->ob_arm, DEG_OB_COMP_TRANSFORM, "Mask Modifier");
110                 arm->flag |= ARM_HAS_VIZ_DEPS;
111         }
112 }
113
114 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
115                                   DerivedMesh *dm,
116                                   ModifierApplyFlag UNUSED(flag))
117 {
118         MaskModifierData *mmd = (MaskModifierData *)md;
119         const bool found_test = (mmd->flag & MOD_MASK_INV) == 0;
120         DerivedMesh *result = NULL;
121         GHash *vertHash = NULL, *edgeHash, *polyHash;
122         GHashIterator gh_iter;
123         MDeformVert *dvert, *dv;
124         int numPolys = 0, numLoops = 0, numEdges = 0, numVerts = 0;
125         int maxVerts, maxEdges, maxPolys;
126         int i;
127
128         const MVert *mvert_src;
129         const MEdge *medge_src;
130         const MPoly *mpoly_src;
131         const MLoop *mloop_src;
132
133         MPoly *mpoly_dst;
134         MLoop *mloop_dst;
135         MEdge *medge_dst;
136         MVert *mvert_dst;
137
138         int *loop_mapping;
139
140         dvert = dm->getVertDataArray(dm, CD_MDEFORMVERT);
141         if (dvert == NULL) {
142                 return found_test ? CDDM_from_template(dm, 0, 0, 0, 0, 0) : dm;
143         }
144
145         /* Overview of Method:
146          *      1. Get the vertices that are in the vertexgroup of interest 
147          *      2. Filter out unwanted geometry (i.e. not in vertexgroup), by populating mappings with new vs old indices
148          *      3. Make a new mesh containing only the mapping data
149          */
150         
151         /* get original number of verts, edges, and faces */
152         maxVerts = dm->getNumVerts(dm);
153         maxEdges = dm->getNumEdges(dm);
154         maxPolys = dm->getNumPolys(dm);
155         
156         /* check if we can just return the original mesh 
157          *      - must have verts and therefore verts assigned to vgroups to do anything useful
158          */
159         if (!(ELEM(mmd->mode, MOD_MASK_MODE_ARM, MOD_MASK_MODE_VGROUP)) ||
160             (maxVerts == 0) || BLI_listbase_is_empty(&ob->defbase))
161         {
162                 return dm;
163         }
164         
165         /* if mode is to use selected armature bones, aggregate the bone groups */
166         if (mmd->mode == MOD_MASK_MODE_ARM) { /* --- using selected bones --- */
167                 Object *oba = mmd->ob_arm;
168                 bPoseChannel *pchan;
169                 bDeformGroup *def;
170                 bool *bone_select_array;
171                 int bone_select_tot = 0;
172                 const int defbase_tot = BLI_listbase_count(&ob->defbase);
173                 
174                 /* check that there is armature object with bones to use, otherwise return original mesh */
175                 if (ELEM(NULL, oba, oba->pose, ob->defbase.first))
176                         return dm;
177                 
178                 /* determine whether each vertexgroup is associated with a selected bone or not 
179                  * - each cell is a boolean saying whether bone corresponding to the ith group is selected
180                  * - groups that don't match a bone are treated as not existing (along with the corresponding ungrouped verts)
181                  */
182                 bone_select_array = MEM_mallocN((size_t)defbase_tot * sizeof(char), "mask array");
183                 
184                 for (i = 0, def = ob->defbase.first; def; def = def->next, i++) {
185                         pchan = BKE_pose_channel_find_name(oba->pose, def->name);
186                         if (pchan && pchan->bone && (pchan->bone->flag & BONE_SELECTED)) {
187                                 bone_select_array[i] = true;
188                                 bone_select_tot++;
189                         }
190                         else {
191                                 bone_select_array[i] = false;
192                         }
193                 }
194
195                 /* verthash gives mapping from original vertex indices to the new indices (including selected matches only)
196                  * key = oldindex, value = newindex
197                  */
198                 vertHash = BLI_ghash_int_new_ex("mask vert gh", (unsigned int)maxVerts);
199                 
200                 /* add vertices which exist in vertexgroups into vertHash for filtering 
201                  * - dv = for each vertex, what vertexgroups does it belong to
202                  * - dw = weight that vertex was assigned to a vertexgroup it belongs to
203                  */
204                 for (i = 0, dv = dvert; i < maxVerts; i++, dv++) {
205                         MDeformWeight *dw = dv->dw;
206                         bool found = false;
207                         int j;
208                         
209                         /* check the groups that vertex is assigned to, and see if it was any use */
210                         for (j = 0; j < dv->totweight; j++, dw++) {
211                                 if (dw->def_nr < defbase_tot) {
212                                         if (bone_select_array[dw->def_nr]) {
213                                                 if (dw->weight != 0.0f) {
214                                                         found = true;
215                                                         break;
216                                                 }
217                                         }
218                                 }
219                         }
220                         
221                         if (found_test != found) {
222                                 continue;
223                         }
224                         
225                         /* add to ghash for verts (numVerts acts as counter for mapping) */
226                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numVerts));
227                         numVerts++;
228                 }
229                 
230                 /* free temp hashes */
231                 MEM_freeN(bone_select_array);
232         }
233         else {  /* --- Using Nominated VertexGroup only --- */
234                 int defgrp_index = defgroup_name_index(ob, mmd->vgroup);
235
236                 /* if no vgroup (i.e. dverts) found, return the initial mesh */
237                 if (defgrp_index == -1)
238                         return dm;
239                         
240                 /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
241                 vertHash = BLI_ghash_int_new_ex("mask vert2 bh", (unsigned int)maxVerts);
242                 
243                 /* add vertices which exist in vertexgroup into ghash for filtering */
244                 for (i = 0, dv = dvert; i < maxVerts; i++, dv++) {
245                         const bool found = defvert_find_weight(dv, defgrp_index) != 0.0f;
246                         if (found_test != found) {
247                                 continue;
248                         }
249
250                         /* add to ghash for verts (numVerts acts as counter for mapping) */
251                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numVerts));
252                         numVerts++;
253                 }
254         }
255
256         /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
257         edgeHash = BLI_ghash_int_new_ex("mask ed2 gh", (unsigned int)maxEdges);
258         polyHash = BLI_ghash_int_new_ex("mask fa2 gh", (unsigned int)maxPolys);
259
260         mvert_src = dm->getVertArray(dm);
261         medge_src = dm->getEdgeArray(dm);
262         mpoly_src = dm->getPolyArray(dm);
263         mloop_src = dm->getLoopArray(dm);
264
265         /* overalloc, assume all polys are seen */
266         loop_mapping = MEM_mallocN(sizeof(int) * (size_t)maxPolys, "mask loopmap");
267
268         /* loop over edges and faces, and do the same thing to 
269          * ensure that they only reference existing verts 
270          */
271         for (i = 0; i < maxEdges; i++) {
272                 const MEdge *me = &medge_src[i];
273                 
274                 /* only add if both verts will be in new mesh */
275                 if (BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v1)) &&
276                     BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v2)))
277                 {
278                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numEdges));
279                         numEdges++;
280                 }
281         }
282         for (i = 0; i < maxPolys; i++) {
283                 const MPoly *mp_src = &mpoly_src[i];
284                 const MLoop *ml_src = &mloop_src[mp_src->loopstart];
285                 bool ok = true;
286                 int j;
287                 
288                 for (j = 0; j < mp_src->totloop; j++, ml_src++) {
289                         if (!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(ml_src->v))) {
290                                 ok = false;
291                                 break;
292                         }
293                 }
294                 
295                 /* all verts must be available */
296                 if (ok) {
297                         BLI_ghash_insert(polyHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numPolys));
298                         loop_mapping[numPolys] = numLoops;
299                         numPolys++;
300                         numLoops += mp_src->totloop;
301                 }
302         }
303         
304         
305         /* now we know the number of verts, edges and faces, 
306          * we can create the new (reduced) mesh
307          */
308         result = CDDM_from_template(dm, numVerts, numEdges, 0, numLoops, numPolys);
309         
310         mpoly_dst = CDDM_get_polys(result);
311         mloop_dst = CDDM_get_loops(result);
312         medge_dst = CDDM_get_edges(result);
313         mvert_dst = CDDM_get_verts(result);
314
315         /* using ghash-iterators, map data into new mesh */
316         /* vertices */
317         GHASH_ITER (gh_iter, vertHash) {
318                 const MVert *v_src;
319                 MVert *v_dst;
320                 const int i_src = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(&gh_iter));
321                 const int i_dst = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(&gh_iter));
322                 
323                 v_src = &mvert_src[i_src];
324                 v_dst = &mvert_dst[i_dst];
325
326                 *v_dst = *v_src;
327                 DM_copy_vert_data(dm, result, i_src, i_dst, 1);
328         }
329                 
330         /* edges */
331         GHASH_ITER (gh_iter, edgeHash) {
332                 const MEdge *e_src;
333                 MEdge *e_dst;
334                 const int i_src = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(&gh_iter));
335                 const int i_dst = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(&gh_iter));
336                 
337                 e_src = &medge_src[i_src];
338                 e_dst = &medge_dst[i_dst];
339
340                 DM_copy_edge_data(dm, result, i_src, i_dst, 1);
341                 *e_dst = *e_src;
342                 e_dst->v1 = GET_UINT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_UINT_IN_POINTER(e_src->v1)));
343                 e_dst->v2 = GET_UINT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_UINT_IN_POINTER(e_src->v2)));
344         }
345         
346         /* faces */
347         GHASH_ITER (gh_iter, polyHash) {
348                 const int i_src = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(&gh_iter));
349                 const int i_dst = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(&gh_iter));
350                 const MPoly *mp_src = &mpoly_src[i_src];
351                 MPoly *mp_dst = &mpoly_dst[i_dst];
352                 const int i_ml_src = mp_src->loopstart;
353                 const int i_ml_dst = loop_mapping[i_dst];
354                 const MLoop *ml_src = &mloop_src[i_ml_src];
355                 MLoop *ml_dst = &mloop_dst[i_ml_dst];
356                 
357                 DM_copy_poly_data(dm, result, i_src, i_dst, 1);
358                 DM_copy_loop_data(dm, result, i_ml_src, i_ml_dst, mp_src->totloop);
359
360                 *mp_dst = *mp_src;
361                 mp_dst->loopstart = i_ml_dst;
362                 for (i = 0; i < mp_src->totloop; i++) {
363                         ml_dst[i].v = GET_UINT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_UINT_IN_POINTER(ml_src[i].v)));
364                         ml_dst[i].e = GET_UINT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_UINT_IN_POINTER(ml_src[i].e)));
365                 }
366         }
367
368         MEM_freeN(loop_mapping);
369
370         /* why is this needed? - campbell */
371         /* recalculate normals */
372         result->dirty |= DM_DIRTY_NORMALS;
373         
374         /* free hashes */
375         BLI_ghash_free(vertHash, NULL, NULL);
376         BLI_ghash_free(edgeHash, NULL, NULL);
377         BLI_ghash_free(polyHash, NULL, NULL);
378
379         /* return the new mesh */
380         return result;
381 }
382
383
384 ModifierTypeInfo modifierType_Mask = {
385         /* name */              "Mask",
386         /* structName */        "MaskModifierData",
387         /* structSize */        sizeof(MaskModifierData),
388         /* type */              eModifierTypeType_Nonconstructive,
389         /* flags */             eModifierTypeFlag_AcceptsMesh |
390                                 eModifierTypeFlag_SupportsMapping |
391                                 eModifierTypeFlag_SupportsEditmode,
392
393         /* copyData */          copyData,
394         /* deformVerts */       NULL,
395         /* deformMatrices */    NULL,
396         /* deformVertsEM */     NULL,
397         /* deformMatricesEM */  NULL,
398         /* applyModifier */     applyModifier,
399         /* applyModifierEM */   NULL,
400         /* initData */          NULL,
401         /* requiredDataMask */  requiredDataMask,
402         /* freeData */          NULL,
403         /* isDisabled */        NULL,
404         /* updateDepgraph */    updateDepgraph,
405         /* updateDepsgraph */   updateDepsgraph,
406         /* dependsOnTime */     NULL,
407         /* dependsOnNormals */  NULL,
408         /* foreachObjectLink */ foreachObjectLink,
409         /* foreachIDLink */     NULL,
410         /* foreachTexLink */    NULL,
411 };