svn merge ^/trunk/blender -r41230:41266
[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_ghash.h"
41
42 #include "DNA_scene_types.h"
43 #include "DNA_meshdata_types.h"
44
45 #include "BKE_cdderivedmesh.h"
46 #include "BKE_mesh.h"
47 #include "BKE_modifier.h"
48 #include "BKE_object.h"
49 #include "BKE_particle.h"
50 #include "BKE_scene.h"
51
52 #include "MOD_util.h"
53
54 static void initData(ModifierData *md)
55 {
56         BuildModifierData *bmd = (BuildModifierData*) md;
57
58         bmd->start = 1.0;
59         bmd->length = 100.0;
60 }
61
62 static void copyData(ModifierData *md, ModifierData *target)
63 {
64         BuildModifierData *bmd = (BuildModifierData*) md;
65         BuildModifierData *tbmd = (BuildModifierData*) target;
66
67         tbmd->start = bmd->start;
68         tbmd->length = bmd->length;
69         tbmd->randomize = bmd->randomize;
70         tbmd->seed = bmd->seed;
71 }
72
73 static int dependsOnTime(ModifierData *UNUSED(md))
74 {
75         return 1;
76 }
77
78 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
79                                                 DerivedMesh *derivedData,
80                                                 int UNUSED(useRenderParams),
81                                                 int UNUSED(isFinalCalc))
82 {
83         DerivedMesh *dm = derivedData;
84         DerivedMesh *result;
85         BuildModifierData *bmd = (BuildModifierData*) md;
86         int i, j, k;
87         int numFaces, numEdges, numLoops = 0;
88         int *vertMap, *edgeMap, *faceMap;
89         float frac;
90         MPoly *mpolys, *mpolyd;
91         MLoop *mld, *mloops, *mls, *mloopd;
92         GHashIterator *hashIter;
93         /* maps vert indices in old mesh to indices in new mesh */
94         GHash *vertHash = BLI_ghash_new(BLI_ghashutil_inthash,
95                                         BLI_ghashutil_intcmp, "build ve apply gh");
96         /* maps edge indices in new mesh to indices in old mesh */
97         GHash *edgeHash = BLI_ghash_new(BLI_ghashutil_inthash,
98                                         BLI_ghashutil_intcmp, "build ed apply gh");
99         GHash *edgeHash2 = BLI_ghash_new(BLI_ghashutil_inthash,
100                                         BLI_ghashutil_intcmp, "build ed apply gh");
101
102         const int maxVerts= dm->getNumVerts(dm);
103         const int maxEdges= dm->getNumEdges(dm);
104         const int maxFaces= dm->getNumFaces(dm);
105         
106         if (!CDDM_Check(dm)) {
107                 result = CDDM_copy(dm, 0);
108                 dm = result;
109         }
110         
111         vertMap = MEM_callocN(sizeof(*vertMap) * maxVerts, "build modifier vertMap");
112         for(i = 0; i < maxVerts; ++i) vertMap[i] = i;
113         edgeMap = MEM_callocN(sizeof(*edgeMap) * maxEdges, "build modifier edgeMap");
114         for(i = 0; i < maxEdges; ++i) edgeMap[i] = i;
115         faceMap = MEM_callocN(sizeof(*faceMap) * maxFaces, "build modifier faceMap");
116         for(i = 0; i < maxFaces; ++i) faceMap[i] = i;
117
118         if (ob) {
119                 frac = bsystem_time(md->scene, ob, md->scene->r.cfra,
120                                         bmd->start - 1.0f) / bmd->length;
121         } else {
122                 frac = BKE_curframe(md->scene) - bmd->start / bmd->length;
123         }
124         CLAMP(frac, 0.0f, 1.0f);
125
126         numFaces = dm->getNumFaces(dm) * frac;
127         numEdges = dm->getNumEdges(dm) * frac;
128
129         /* if there's at least one face, build based on faces */
130         if(numFaces) {
131                 MPoly *mpoly, *mp;
132                 MLoop *ml, *mloop;
133                 MEdge *medge;
134                 
135                 if(bmd->randomize)
136                         BLI_array_randomize(faceMap, sizeof(*faceMap),
137                                                 maxFaces, bmd->seed);
138
139                 /* get the set of all vert indices that will be in the final mesh,
140                 * mapped to the new indices
141                 */
142                 mpoly = CDDM_get_polys(dm);
143                 mloop = CDDM_get_loops(dm);
144                 for(i = 0; i < numFaces; ++i) {
145                         mp = mpoly + faceMap[i];
146                         ml = mloop + mp->loopstart;
147
148                         for (j=0; j<mp->totloop; j++, ml++) {
149                                 if (!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(ml->v)))
150                                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(ml->v), 
151                                                 SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
152                         }
153                         
154                         numLoops += mp->totloop;
155                 }
156
157                 /* get the set of edges that will be in the new mesh (i.e. all edges
158                 * that have both verts in the new mesh)
159                 */
160                 medge = CDDM_get_edges(dm);
161                 for(i = 0; i < maxEdges; ++i) {
162                         MEdge *me = medge + i;
163
164                         if(BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v1))
165                                                 && BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v2)))
166                         {
167                                 j = BLI_ghash_size(edgeHash);
168                                 
169                                 BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(j), SET_INT_IN_POINTER(i));
170                                 BLI_ghash_insert(edgeHash2, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(j));
171                         }
172                 }
173         } else if(numEdges) {
174                 MEdge *medge, *me;
175
176                 if(bmd->randomize)
177                         BLI_array_randomize(edgeMap, sizeof(*edgeMap),
178                                                 maxEdges, bmd->seed);
179
180                 /* get the set of all vert indices that will be in the final mesh,
181                 * mapped to the new indices
182                 */
183                 medge = CDDM_get_edges(dm);
184                 for(i = 0; i < numEdges; ++i) {
185                         me = medge + edgeMap[i];
186
187                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v1)))
188                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me->v1),
189                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
190                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v2)))
191                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me->v2),
192                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
193                 }
194
195                 /* get the set of edges that will be in the new mesh
196                 */
197                 for(i = 0; i < numEdges; ++i) {
198                         j = BLI_ghash_size(edgeHash);
199                         
200                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(j),
201                                          SET_INT_IN_POINTER(edgeMap[i]));
202                         BLI_ghash_insert(edgeHash2,  SET_INT_IN_POINTER(edgeMap[i]),
203                                                          SET_INT_IN_POINTER(j));
204                 }
205         } else {
206                 int numVerts = dm->getNumVerts(dm) * frac;
207
208                 if(bmd->randomize)
209                         BLI_array_randomize(vertMap, sizeof(*vertMap),
210                                                 maxVerts, bmd->seed);
211
212                 /* get the set of all vert indices that will be in the final mesh,
213                 * mapped to the new indices
214                 */
215                 for(i = 0; i < numVerts; ++i)
216                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]), SET_INT_IN_POINTER(i));
217         }
218
219         /* now we know the number of verts, edges and faces, we can create
220         * the mesh
221         */
222         result = CDDM_from_template(dm, BLI_ghash_size(vertHash),
223                                         BLI_ghash_size(edgeHash), 0, numLoops, numFaces);
224
225         /* copy the vertices across */
226         for(    hashIter = BLI_ghashIterator_new(vertHash);
227                         !BLI_ghashIterator_isDone(hashIter);
228                         BLI_ghashIterator_step(hashIter)
229         ) {
230                 MVert source;
231                 MVert *dest;
232                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
233                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
234
235                 dm->getVert(dm, oldIndex, &source);
236                 dest = CDDM_get_vert(result, newIndex);
237
238                 DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
239                 *dest = source;
240         }
241         BLI_ghashIterator_free(hashIter);
242         
243         /* copy the edges across, remapping indices */
244         for(i = 0; i < BLI_ghash_size(edgeHash); ++i) {
245                 MEdge source;
246                 MEdge *dest;
247                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_INT_IN_POINTER(i)));
248                 
249                 dm->getEdge(dm, oldIndex, &source);
250                 dest = CDDM_get_edge(result, i);
251                 
252                 source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
253                 source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
254                 
255                 DM_copy_edge_data(dm, result, oldIndex, i, 1);
256                 *dest = source;
257         }
258
259         mpolys = CDDM_get_polys(dm);
260         mpolyd = CDDM_get_polys(result);
261         mloops = CDDM_get_loops(dm);
262         mloopd = mld = CDDM_get_loops(result);
263         
264         /* copy the faces across, remapping indices */
265         k = 0;
266         for(i = 0; i < numFaces; ++i) {
267                 MPoly *source;
268                 MPoly *dest;
269                 
270                 source = mpolys + faceMap[i];
271                 dest = mpolyd + i;
272                 DM_copy_face_data(dm, result, faceMap[i], i, 1);
273                 
274                 *dest = *source;
275                 dest->loopstart = k;
276                 
277                 DM_copy_loop_data(dm, result, source->loopstart, dest->loopstart, dest->totloop);
278
279                 mls = mloops + source->loopstart;
280                 for (j=0; j<source->totloop; j++, k++, mls++, mld++) {
281                         mld->v = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(mls->v)));
282                         mld->e = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash2, SET_INT_IN_POINTER(mls->e)));
283                 }
284         }
285
286         CDDM_calc_normals(result);
287         
288         BLI_ghash_free(vertHash, NULL, NULL);
289         BLI_ghash_free(edgeHash, NULL, NULL);
290         BLI_ghash_free(edgeHash2, NULL, NULL);
291         
292         MEM_freeN(vertMap);
293         MEM_freeN(edgeMap);
294         MEM_freeN(faceMap);
295         
296         if (dm != derivedData) {
297                 dm->needsFree = 1;
298                 dm->release(dm);
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 };