Cleanup: unused headers in editors
[blender.git] / source / blender / modifiers / intern / MOD_build.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software  Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2005 by the Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup modifiers
22  */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "BLI_utildefines.h"
27
28 #include "BLI_ghash.h"
29 #include "BLI_math_vector.h"
30 #include "BLI_rand.h"
31
32 #include "DNA_meshdata_types.h"
33 #include "DNA_mesh_types.h"
34 #include "DNA_object_types.h"
35
36 #include "DEG_depsgraph_query.h"
37
38 #include "BKE_mesh.h"
39 #include "BKE_modifier.h"
40 #include "BKE_particle.h"
41 #include "BKE_scene.h"
42
43 #include "MOD_modifiertypes.h"
44
45 static void initData(ModifierData *md)
46 {
47   BuildModifierData *bmd = (BuildModifierData *)md;
48
49   bmd->start = 1.0;
50   bmd->length = 100.0;
51 }
52
53 static bool dependsOnTime(ModifierData *UNUSED(md))
54 {
55   return true;
56 }
57
58 static Mesh *applyModifier(ModifierData *md, const ModifierEvalContext *ctx, struct Mesh *mesh)
59 {
60   Mesh *result;
61   BuildModifierData *bmd = (BuildModifierData *)md;
62   int i, j, k;
63   int numFaces_dst, numEdges_dst, numLoops_dst = 0;
64   int *vertMap, *edgeMap, *faceMap;
65   float frac;
66   MPoly *mpoly_dst;
67   MLoop *ml_dst, *ml_src /*, *mloop_dst */;
68   GHashIterator gh_iter;
69   /* maps vert indices in old mesh to indices in new mesh */
70   GHash *vertHash = BLI_ghash_int_new("build ve apply gh");
71   /* maps edge indices in new mesh to indices in old mesh */
72   GHash *edgeHash = BLI_ghash_int_new("build ed apply gh");
73   /* maps edge indices in old mesh to indices in new mesh */
74   GHash *edgeHash2 = BLI_ghash_int_new("build ed apply gh");
75
76   const int numVert_src = mesh->totvert;
77   const int numEdge_src = mesh->totedge;
78   const int numPoly_src = mesh->totpoly;
79   MPoly *mpoly_src = mesh->mpoly;
80   MLoop *mloop_src = mesh->mloop;
81   MEdge *medge_src = mesh->medge;
82   MVert *mvert_src = mesh->mvert;
83
84   vertMap = MEM_malloc_arrayN(numVert_src, sizeof(*vertMap), "build modifier vertMap");
85   edgeMap = MEM_malloc_arrayN(numEdge_src, sizeof(*edgeMap), "build modifier edgeMap");
86   faceMap = MEM_malloc_arrayN(numPoly_src, sizeof(*faceMap), "build modifier faceMap");
87
88   range_vn_i(vertMap, numVert_src, 0);
89   range_vn_i(edgeMap, numEdge_src, 0);
90   range_vn_i(faceMap, numPoly_src, 0);
91
92   struct Scene *scene = DEG_get_input_scene(ctx->depsgraph);
93   frac = (BKE_scene_frame_get(scene) - bmd->start) / bmd->length;
94   CLAMP(frac, 0.0f, 1.0f);
95   if (bmd->flag & MOD_BUILD_FLAG_REVERSE) {
96     frac = 1.0f - frac;
97   }
98
99   numFaces_dst = numPoly_src * frac;
100   numEdges_dst = numEdge_src * frac;
101
102   /* if there's at least one face, build based on faces */
103   if (numFaces_dst) {
104     MPoly *mpoly, *mp;
105     MLoop *ml, *mloop;
106     uintptr_t hash_num, hash_num_alt;
107
108     if (bmd->flag & MOD_BUILD_FLAG_RANDOMIZE) {
109       BLI_array_randomize(faceMap, sizeof(*faceMap), numPoly_src, bmd->seed);
110     }
111
112     /* get the set of all vert indices that will be in the final mesh,
113      * mapped to the new indices
114      */
115     mpoly = mpoly_src;
116     mloop = mloop_src;
117     hash_num = 0;
118     for (i = 0; i < numFaces_dst; i++) {
119       mp = mpoly + faceMap[i];
120       ml = mloop + mp->loopstart;
121
122       for (j = 0; j < mp->totloop; j++, ml++) {
123         void **val_p;
124         if (!BLI_ghash_ensure_p(vertHash, POINTER_FROM_INT(ml->v), &val_p)) {
125           *val_p = (void *)hash_num;
126           hash_num++;
127         }
128       }
129
130       numLoops_dst += mp->totloop;
131     }
132     BLI_assert(hash_num == BLI_ghash_len(vertHash));
133
134     /* get the set of edges that will be in the new mesh (i.e. all edges
135      * that have both verts in the new mesh)
136      */
137     hash_num = 0;
138     hash_num_alt = 0;
139     for (i = 0; i < numEdge_src; i++, hash_num_alt++) {
140       MEdge *me = medge_src + i;
141
142       if (BLI_ghash_haskey(vertHash, POINTER_FROM_INT(me->v1)) &&
143           BLI_ghash_haskey(vertHash, POINTER_FROM_INT(me->v2))) {
144         BLI_ghash_insert(edgeHash, (void *)hash_num, (void *)hash_num_alt);
145         BLI_ghash_insert(edgeHash2, (void *)hash_num_alt, (void *)hash_num);
146         hash_num++;
147       }
148     }
149     BLI_assert(hash_num == BLI_ghash_len(edgeHash));
150   }
151   else if (numEdges_dst) {
152     MEdge *medge, *me;
153     uintptr_t hash_num;
154
155     if (bmd->flag & MOD_BUILD_FLAG_RANDOMIZE) {
156       BLI_array_randomize(edgeMap, sizeof(*edgeMap), numEdge_src, bmd->seed);
157     }
158
159     /* get the set of all vert indices that will be in the final mesh,
160      * mapped to the new indices
161      */
162     medge = medge_src;
163     hash_num = 0;
164     BLI_assert(hash_num == BLI_ghash_len(vertHash));
165     for (i = 0; i < numEdges_dst; i++) {
166       void **val_p;
167       me = medge + edgeMap[i];
168
169       if (!BLI_ghash_ensure_p(vertHash, POINTER_FROM_INT(me->v1), &val_p)) {
170         *val_p = (void *)hash_num;
171         hash_num++;
172       }
173       if (!BLI_ghash_ensure_p(vertHash, POINTER_FROM_INT(me->v2), &val_p)) {
174         *val_p = (void *)hash_num;
175         hash_num++;
176       }
177     }
178     BLI_assert(hash_num == BLI_ghash_len(vertHash));
179
180     /* get the set of edges that will be in the new mesh */
181     for (i = 0; i < numEdges_dst; i++) {
182       j = BLI_ghash_len(edgeHash);
183
184       BLI_ghash_insert(edgeHash, POINTER_FROM_INT(j), POINTER_FROM_INT(edgeMap[i]));
185       BLI_ghash_insert(edgeHash2, POINTER_FROM_INT(edgeMap[i]), POINTER_FROM_INT(j));
186     }
187   }
188   else {
189     int numVerts = numVert_src * frac;
190
191     if (bmd->flag & MOD_BUILD_FLAG_RANDOMIZE) {
192       BLI_array_randomize(vertMap, sizeof(*vertMap), numVert_src, bmd->seed);
193     }
194
195     /* get the set of all vert indices that will be in the final mesh,
196      * mapped to the new indices
197      */
198     for (i = 0; i < numVerts; i++) {
199       BLI_ghash_insert(vertHash, POINTER_FROM_INT(vertMap[i]), POINTER_FROM_INT(i));
200     }
201   }
202
203   /* now we know the number of verts, edges and faces, we can create the mesh. */
204   result = BKE_mesh_new_nomain_from_template(
205       mesh, BLI_ghash_len(vertHash), BLI_ghash_len(edgeHash), 0, numLoops_dst, numFaces_dst);
206
207   /* copy the vertices across */
208   GHASH_ITER (gh_iter, vertHash) {
209     MVert source;
210     MVert *dest;
211     int oldIndex = POINTER_AS_INT(BLI_ghashIterator_getKey(&gh_iter));
212     int newIndex = POINTER_AS_INT(BLI_ghashIterator_getValue(&gh_iter));
213
214     source = mvert_src[oldIndex];
215     dest = &result->mvert[newIndex];
216
217     CustomData_copy_data(&mesh->vdata, &result->vdata, oldIndex, newIndex, 1);
218     *dest = source;
219   }
220
221   /* copy the edges across, remapping indices */
222   for (i = 0; i < BLI_ghash_len(edgeHash); i++) {
223     MEdge source;
224     MEdge *dest;
225     int oldIndex = POINTER_AS_INT(BLI_ghash_lookup(edgeHash, POINTER_FROM_INT(i)));
226
227     source = medge_src[oldIndex];
228     dest = &result->medge[i];
229
230     source.v1 = POINTER_AS_INT(BLI_ghash_lookup(vertHash, POINTER_FROM_INT(source.v1)));
231     source.v2 = POINTER_AS_INT(BLI_ghash_lookup(vertHash, POINTER_FROM_INT(source.v2)));
232
233     CustomData_copy_data(&mesh->edata, &result->edata, oldIndex, i, 1);
234     *dest = source;
235   }
236
237   mpoly_dst = result->mpoly;
238   ml_dst = result->mloop;
239
240   /* copy the faces across, remapping indices */
241   k = 0;
242   for (i = 0; i < numFaces_dst; i++) {
243     MPoly *source;
244     MPoly *dest;
245
246     source = mpoly_src + faceMap[i];
247     dest = mpoly_dst + i;
248     CustomData_copy_data(&mesh->pdata, &result->pdata, faceMap[i], i, 1);
249
250     *dest = *source;
251     dest->loopstart = k;
252     CustomData_copy_data(
253         &mesh->ldata, &result->ldata, source->loopstart, dest->loopstart, dest->totloop);
254
255     ml_src = mloop_src + source->loopstart;
256     for (j = 0; j < source->totloop; j++, k++, ml_src++, ml_dst++) {
257       ml_dst->v = POINTER_AS_INT(BLI_ghash_lookup(vertHash, POINTER_FROM_INT(ml_src->v)));
258       ml_dst->e = POINTER_AS_INT(BLI_ghash_lookup(edgeHash2, POINTER_FROM_INT(ml_src->e)));
259     }
260   }
261
262   BLI_ghash_free(vertHash, NULL, NULL);
263   BLI_ghash_free(edgeHash, NULL, NULL);
264   BLI_ghash_free(edgeHash2, NULL, NULL);
265
266   MEM_freeN(vertMap);
267   MEM_freeN(edgeMap);
268   MEM_freeN(faceMap);
269
270   if (mesh->runtime.cd_dirty_vert & CD_MASK_NORMAL) {
271     result->runtime.cd_dirty_vert |= CD_MASK_NORMAL;
272   }
273
274   /* TODO(sybren): also copy flags & tags? */
275   return result;
276 }
277
278 ModifierTypeInfo modifierType_Build = {
279     /* name */ "Build",
280     /* structName */ "BuildModifierData",
281     /* structSize */ sizeof(BuildModifierData),
282     /* type */ eModifierTypeType_Nonconstructive,
283     /* flags */ eModifierTypeFlag_AcceptsMesh | eModifierTypeFlag_AcceptsCVs,
284
285     /* copyData */ modifier_copyData_generic,
286
287     /* deformVerts */ NULL,
288     /* deformMatrices */ NULL,
289     /* deformVertsEM */ NULL,
290     /* deformMatricesEM */ NULL,
291     /* applyModifier */ applyModifier,
292
293     /* initData */ initData,
294     /* requiredDataMask */ NULL,
295     /* freeData */ NULL,
296     /* isDisabled */ NULL,
297     /* updateDepsgraph */ NULL,
298     /* dependsOnTime */ dependsOnTime,
299     /* dependsOnNormals */ NULL,
300     /* foreachObjectLink */ NULL,
301     /* foreachIDLink */ NULL,
302     /* foreachTexLink */ NULL,
303     /* freeRuntimeData */ NULL,
304 };