Mesh Modifiers: refactor copying using a generic function
[blender.git] / source / blender / modifiers / intern / MOD_build.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_build.c
32  *  \ingroup modifiers
33  */
34
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BLI_utildefines.h"
39 #include "BLI_rand.h"
40 #include "BLI_math_vector.h"
41 #include "BLI_ghash.h"
42
43 #include "DNA_scene_types.h"
44 #include "DNA_meshdata_types.h"
45
46 #include "BKE_cdderivedmesh.h"
47 #include "BKE_mesh.h"
48 #include "BKE_modifier.h"
49 #include "BKE_object.h"
50 #include "BKE_particle.h"
51 #include "BKE_scene.h"
52
53 #include "MOD_util.h"
54
55 static void initData(ModifierData *md)
56 {
57         BuildModifierData *bmd = (BuildModifierData *) md;
58
59         bmd->start = 1.0;
60         bmd->length = 100.0;
61 }
62
63 static void copyData(ModifierData *md, ModifierData *target)
64 {
65 #if 0
66         BuildModifierData *bmd = (BuildModifierData *) md;
67         BuildModifierData *tbmd = (BuildModifierData *) target;
68 #endif
69         modifier_copyData_generic(md, target);
70 }
71
72 static bool dependsOnTime(ModifierData *UNUSED(md))
73 {
74         return true;
75 }
76
77 static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
78                                   DerivedMesh *derivedData,
79                                   ModifierApplyFlag UNUSED(flag))
80 {
81         DerivedMesh *dm = derivedData;
82         DerivedMesh *result;
83         BuildModifierData *bmd = (BuildModifierData *) md;
84         int i, j, k;
85         int numFaces_dst, numEdges_dst, numLoops_dst = 0;
86         int *vertMap, *edgeMap, *faceMap;
87         float frac;
88         MPoly *mpoly_dst;
89         MLoop *ml_dst, *ml_src /*, *mloop_dst */;
90         GHashIterator *hashIter;
91         /* maps vert indices in old mesh to indices in new mesh */
92         GHash *vertHash = BLI_ghash_int_new("build ve apply gh");
93         /* maps edge indices in new mesh to indices in old mesh */
94         GHash *edgeHash = BLI_ghash_int_new("build ed apply gh");
95         GHash *edgeHash2 = BLI_ghash_int_new("build ed apply gh");
96
97         const int numVert_src = dm->getNumVerts(dm);
98         const int numEdge_src = dm->getNumEdges(dm);
99         const int numPoly_src = dm->getNumPolys(dm);
100         MPoly *mpoly_src = dm->getPolyArray(dm);
101         MLoop *mloop_src = dm->getLoopArray(dm);
102         MEdge *medge_src = dm->getEdgeArray(dm);
103         MVert *mvert_src = dm->getVertArray(dm);
104
105
106         vertMap = MEM_mallocN(sizeof(*vertMap) * numVert_src, "build modifier vertMap");
107         edgeMap = MEM_mallocN(sizeof(*edgeMap) * numEdge_src, "build modifier edgeMap");
108         faceMap = MEM_mallocN(sizeof(*faceMap) * numPoly_src, "build modifier faceMap");
109
110 #pragma omp parallel sections if (numVert_src + numEdge_src + numPoly_src >= BKE_MESH_OMP_LIMIT)
111         {
112 #pragma omp section
113                 { range_vn_i(vertMap, numVert_src, 0); }
114 #pragma omp section
115                 { range_vn_i(edgeMap, numEdge_src, 0); }
116 #pragma omp section
117                 { range_vn_i(faceMap, numPoly_src, 0); }
118         }
119
120         frac = (BKE_scene_frame_get(md->scene) - bmd->start) / bmd->length;
121         CLAMP(frac, 0.0f, 1.0f);
122
123         numFaces_dst = numPoly_src * frac;
124         numEdges_dst = numEdge_src * frac;
125
126         /* if there's at least one face, build based on faces */
127         if (numFaces_dst) {
128                 MPoly *mpoly, *mp;
129                 MLoop *ml, *mloop;
130                 MEdge *medge;
131                 
132                 if (bmd->randomize) {
133                         BLI_array_randomize(faceMap, sizeof(*faceMap),
134                                             numPoly_src, bmd->seed);
135                 }
136
137                 /* get the set of all vert indices that will be in the final mesh,
138                  * mapped to the new indices
139                  */
140                 mpoly = mpoly_src;
141                 mloop = mloop_src;
142                 for (i = 0; i < numFaces_dst; i++) {
143                         mp = mpoly + faceMap[i];
144                         ml = mloop + mp->loopstart;
145
146                         for (j = 0; j < mp->totloop; j++, ml++) {
147                                 if (!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(ml->v)))
148                                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(ml->v),
149                                                          SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
150                         }
151                         
152                         numLoops_dst += mp->totloop;
153                 }
154
155                 /* get the set of edges that will be in the new mesh (i.e. all edges
156                  * that have both verts in the new mesh)
157                  */
158                 medge = medge_src;
159                 for (i = 0; i < numEdge_src; i++) {
160                         MEdge *me = medge + i;
161
162                         if (BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v1)) &&
163                             BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v2)))
164                         {
165                                 j = BLI_ghash_size(edgeHash);
166                                 
167                                 BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(j),
168                                                  SET_INT_IN_POINTER(i));
169                                 BLI_ghash_insert(edgeHash2, SET_INT_IN_POINTER(i),
170                                                  SET_INT_IN_POINTER(j));
171                         }
172                 }
173         }
174         else if (numEdges_dst) {
175                 MEdge *medge, *me;
176
177                 if (bmd->randomize)
178                         BLI_array_randomize(edgeMap, sizeof(*edgeMap),
179                                             numEdge_src, bmd->seed);
180
181                 /* get the set of all vert indices that will be in the final mesh,
182                  * mapped to the new indices
183                  */
184                 medge = medge_src;
185                 for (i = 0; i < numEdges_dst; i++) {
186                         me = medge + edgeMap[i];
187
188                         if (!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v1))) {
189                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me->v1),
190                                                  SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
191                         }
192                         if (!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v2))) {
193                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me->v2), SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
194                         }
195                 }
196
197                 /* get the set of edges that will be in the new mesh */
198                 for (i = 0; i < numEdges_dst; i++) {
199                         j = BLI_ghash_size(edgeHash);
200                         
201                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(j),
202                                          SET_INT_IN_POINTER(edgeMap[i]));
203                         BLI_ghash_insert(edgeHash2,  SET_INT_IN_POINTER(edgeMap[i]),
204                                          SET_INT_IN_POINTER(j));
205                 }
206         }
207         else {
208                 int numVerts = numVert_src * frac;
209
210                 if (bmd->randomize) {
211                         BLI_array_randomize(vertMap, sizeof(*vertMap),
212                                             numVert_src, bmd->seed);
213                 }
214
215                 /* get the set of all vert indices that will be in the final mesh,
216                  * mapped to the new indices
217                  */
218                 for (i = 0; i < numVerts; i++) {
219                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]), SET_INT_IN_POINTER(i));
220                 }
221         }
222
223         /* now we know the number of verts, edges and faces, we can create
224          * the mesh
225          */
226         result = CDDM_from_template(dm, BLI_ghash_size(vertHash),
227                                     BLI_ghash_size(edgeHash), 0, numLoops_dst, numFaces_dst);
228
229         /* copy the vertices across */
230         for (hashIter = BLI_ghashIterator_new(vertHash);
231              BLI_ghashIterator_done(hashIter) == false;
232              BLI_ghashIterator_step(hashIter)
233              )
234         {
235                 MVert source;
236                 MVert *dest;
237                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
238                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
239
240                 source = mvert_src[oldIndex];
241                 dest = CDDM_get_vert(result, newIndex);
242
243                 DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
244                 *dest = source;
245         }
246         BLI_ghashIterator_free(hashIter);
247         
248         /* copy the edges across, remapping indices */
249         for (i = 0; i < BLI_ghash_size(edgeHash); i++) {
250                 MEdge source;
251                 MEdge *dest;
252                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_INT_IN_POINTER(i)));
253                 
254                 source = medge_src[oldIndex];
255                 dest = CDDM_get_edge(result, i);
256                 
257                 source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
258                 source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
259                 
260                 DM_copy_edge_data(dm, result, oldIndex, i, 1);
261                 *dest = source;
262         }
263
264         mpoly_dst = CDDM_get_polys(result);
265         /* mloop_dst = */ ml_dst = CDDM_get_loops(result);
266         
267         /* copy the faces across, remapping indices */
268         k = 0;
269         for (i = 0; i < numFaces_dst; i++) {
270                 MPoly *source;
271                 MPoly *dest;
272                 
273                 source = mpoly_src + faceMap[i];
274                 dest = mpoly_dst + i;
275                 DM_copy_poly_data(dm, result, faceMap[i], i, 1);
276                 
277                 *dest = *source;
278                 dest->loopstart = k;
279                 
280                 DM_copy_loop_data(dm, result, source->loopstart, dest->loopstart, dest->totloop);
281
282                 ml_src = mloop_src + source->loopstart;
283                 for (j = 0; j < source->totloop; j++, k++, ml_src++, ml_dst++) {
284                         ml_dst->v = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(ml_src->v)));
285                         ml_dst->e = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash2, SET_INT_IN_POINTER(ml_src->e)));
286                 }
287         }
288
289         BLI_ghash_free(vertHash, NULL, NULL);
290         BLI_ghash_free(edgeHash, NULL, NULL);
291         BLI_ghash_free(edgeHash2, NULL, NULL);
292         
293         MEM_freeN(vertMap);
294         MEM_freeN(edgeMap);
295         MEM_freeN(faceMap);
296
297         if (dm->dirty & DM_DIRTY_NORMALS) {
298                 result->dirty |= DM_DIRTY_NORMALS;
299         }
300
301         return result;
302 }
303
304
305 ModifierTypeInfo modifierType_Build = {
306         /* name */              "Build",
307         /* structName */        "BuildModifierData",
308         /* structSize */        sizeof(BuildModifierData),
309         /* type */              eModifierTypeType_Nonconstructive,
310         /* flags */             eModifierTypeFlag_AcceptsMesh |
311                                 eModifierTypeFlag_AcceptsCVs,
312         /* copyData */          copyData,
313         /* deformVerts */       NULL,
314         /* deformMatrices */    NULL,
315         /* deformVertsEM */     NULL,
316         /* deformMatricesEM */  NULL,
317         /* applyModifier */     applyModifier,
318         /* applyModifierEM */   NULL,
319         /* initData */          initData,
320         /* requiredDataMask */  NULL,
321         /* freeData */          NULL,
322         /* isDisabled */        NULL,
323         /* updateDepgraph */    NULL,
324         /* dependsOnTime */     dependsOnTime,
325         /* dependsOnNormals */  NULL,
326         /* foreachObjectLink */ NULL,
327         /* foreachIDLink */     NULL,
328         /* foreachTexLink */    NULL,
329 };