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