Merge branch 'master' into blender2.8
[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_meshdata_types.h"
44 #include "DNA_mesh_types.h"
45 #include "DNA_object_types.h"
46
47 #include "DEG_depsgraph_query.h"
48
49 #include "BKE_cdderivedmesh.h"
50 #include "BKE_mesh.h"
51 #include "BKE_modifier.h"
52 #include "BKE_particle.h"
53 #include "BKE_scene.h"
54
55
56
57 #ifdef _OPENMP
58 #  include "BKE_mesh.h"  /* BKE_MESH_OMP_LIMIT */
59 #endif
60
61 static void initData(ModifierData *md)
62 {
63         BuildModifierData *bmd = (BuildModifierData *) md;
64
65         bmd->start = 1.0;
66         bmd->length = 100.0;
67 }
68
69 static bool dependsOnTime(ModifierData *UNUSED(md))
70 {
71         return true;
72 }
73
74 static Mesh *applyModifier(ModifierData *md, const ModifierEvalContext *ctx,
75                            struct Mesh *mesh)
76 {
77         Mesh *result;
78         BuildModifierData *bmd = (BuildModifierData *) md;
79         int i, j, k;
80         int numFaces_dst, numEdges_dst, numLoops_dst = 0;
81         int *vertMap, *edgeMap, *faceMap;
82         float frac;
83         MPoly *mpoly_dst;
84         MLoop *ml_dst, *ml_src /*, *mloop_dst */;
85         GHashIterator gh_iter;
86         /* maps vert indices in old mesh to indices in new mesh */
87         GHash *vertHash = BLI_ghash_int_new("build ve apply gh");
88         /* maps edge indices in new mesh to indices in old mesh */
89         GHash *edgeHash = BLI_ghash_int_new("build ed apply gh");
90         /* maps edge indices in old mesh to indices in new mesh */
91         GHash *edgeHash2 = BLI_ghash_int_new("build ed apply gh");
92
93         const int numVert_src = mesh->totvert;
94         const int numEdge_src = mesh->totedge;
95         const int numPoly_src = mesh->totpoly;
96         MPoly *mpoly_src = mesh->mpoly;
97         MLoop *mloop_src = mesh->mloop;
98         MEdge *medge_src = mesh->medge;
99         MVert *mvert_src = mesh->mvert;
100
101         vertMap = MEM_malloc_arrayN(numVert_src, sizeof(*vertMap), "build modifier vertMap");
102         edgeMap = MEM_malloc_arrayN(numEdge_src, sizeof(*edgeMap), "build modifier edgeMap");
103         faceMap = MEM_malloc_arrayN(numPoly_src, sizeof(*faceMap), "build modifier faceMap");
104
105         range_vn_i(vertMap, numVert_src, 0);
106         range_vn_i(edgeMap, numEdge_src, 0);
107         range_vn_i(faceMap, numPoly_src, 0);
108
109         struct Scene *scene = DEG_get_input_scene(ctx->depsgraph);
110         frac = (BKE_scene_frame_get(scene) - bmd->start) / bmd->length;
111         CLAMP(frac, 0.0f, 1.0f);
112         if (bmd->flag & MOD_BUILD_FLAG_REVERSE) {
113                 frac = 1.0f - frac;
114         }
115
116         numFaces_dst = numPoly_src * frac;
117         numEdges_dst = numEdge_src * frac;
118
119         /* if there's at least one face, build based on faces */
120         if (numFaces_dst) {
121                 MPoly *mpoly, *mp;
122                 MLoop *ml, *mloop;
123                 uintptr_t hash_num, hash_num_alt;
124                 
125                 if (bmd->flag & MOD_BUILD_FLAG_RANDOMIZE) {
126                         BLI_array_randomize(faceMap, sizeof(*faceMap),
127                                             numPoly_src, bmd->seed);
128                 }
129
130                 /* get the set of all vert indices that will be in the final mesh,
131                  * mapped to the new indices
132                  */
133                 mpoly = mpoly_src;
134                 mloop = mloop_src;
135                 hash_num = 0;
136                 for (i = 0; i < numFaces_dst; i++) {
137                         mp = mpoly + faceMap[i];
138                         ml = mloop + mp->loopstart;
139
140                         for (j = 0; j < mp->totloop; j++, ml++) {
141                                 void **val_p;
142                                 if (!BLI_ghash_ensure_p(vertHash, SET_INT_IN_POINTER(ml->v), &val_p)) {
143                                         *val_p = (void *)hash_num;
144                                         hash_num++;
145                                 }
146                         }
147
148                         numLoops_dst += mp->totloop;
149                 }
150                 BLI_assert(hash_num == BLI_ghash_len(vertHash));
151
152                 /* get the set of edges that will be in the new mesh (i.e. all edges
153                  * that have both verts in the new mesh)
154                  */
155                 hash_num = 0;
156                 hash_num_alt = 0;
157                 for (i = 0; i < numEdge_src; i++, hash_num_alt++) {
158                         MEdge *me = medge_src + i;
159
160                         if (BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v1)) &&
161                             BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me->v2)))
162                         {
163                                 BLI_ghash_insert(edgeHash, (void *)hash_num, (void *)hash_num_alt);
164                                 BLI_ghash_insert(edgeHash2, (void *)hash_num_alt, (void *)hash_num);
165                                 hash_num++;
166                         }
167                 }
168                 BLI_assert(hash_num == BLI_ghash_len(edgeHash));
169         }
170         else if (numEdges_dst) {
171                 MEdge *medge, *me;
172                 uintptr_t hash_num;
173
174                 if (bmd->flag & MOD_BUILD_FLAG_RANDOMIZE)
175                         BLI_array_randomize(edgeMap, sizeof(*edgeMap),
176                                             numEdge_src, bmd->seed);
177
178                 /* get the set of all vert indices that will be in the final mesh,
179                  * mapped to the new indices
180                  */
181                 medge = medge_src;
182                 hash_num = 0;
183                 BLI_assert(hash_num == BLI_ghash_len(vertHash));
184                 for (i = 0; i < numEdges_dst; i++) {
185                         void **val_p;
186                         me = medge + edgeMap[i];
187
188                         if (!BLI_ghash_ensure_p(vertHash, SET_INT_IN_POINTER(me->v1), &val_p)) {
189                                 *val_p = (void *)hash_num;
190                                 hash_num++;
191                         }
192                         if (!BLI_ghash_ensure_p(vertHash, SET_INT_IN_POINTER(me->v2), &val_p)) {
193                                 *val_p = (void *)hash_num;
194                                 hash_num++;
195                         }
196                 }
197                 BLI_assert(hash_num == BLI_ghash_len(vertHash));
198
199                 /* get the set of edges that will be in the new mesh */
200                 for (i = 0; i < numEdges_dst; i++) {
201                         j = BLI_ghash_len(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         }
209         else {
210                 int numVerts = numVert_src * frac;
211
212                 if (bmd->flag & MOD_BUILD_FLAG_RANDOMIZE) {
213                         BLI_array_randomize(vertMap, sizeof(*vertMap),
214                                             numVert_src, bmd->seed);
215                 }
216
217                 /* get the set of all vert indices that will be in the final mesh,
218                  * mapped to the new indices
219                  */
220                 for (i = 0; i < numVerts; i++) {
221                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]), SET_INT_IN_POINTER(i));
222                 }
223         }
224
225         /* now we know the number of verts, edges and faces, we can create the mesh. */
226         result = BKE_mesh_from_template(mesh, BLI_ghash_len(vertHash), BLI_ghash_len(edgeHash),
227                                         0, numLoops_dst, numFaces_dst);
228
229         /* copy the vertices across */
230         GHASH_ITER (gh_iter, vertHash) {
231                 MVert source;
232                 MVert *dest;
233                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(&gh_iter));
234                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(&gh_iter));
235
236                 source = mvert_src[oldIndex];
237                 dest = &result->mvert[newIndex];
238
239                 CustomData_copy_data(&mesh->vdata, &result->vdata, oldIndex, newIndex, 1);
240                 *dest = source;
241         }
242
243         /* copy the edges across, remapping indices */
244         for (i = 0; i < BLI_ghash_len(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                 source = medge_src[oldIndex];
250                 dest = &result->medge[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                 CustomData_copy_data(&mesh->edata, &result->edata, oldIndex, i, 1);
256                 *dest = source;
257         }
258
259         mpoly_dst = result->mpoly;
260         ml_dst = result->mloop;
261         
262         /* copy the faces across, remapping indices */
263         k = 0;
264         for (i = 0; i < numFaces_dst; i++) {
265                 MPoly *source;
266                 MPoly *dest;
267
268                 source = mpoly_src + faceMap[i];
269                 dest = mpoly_dst + i;
270                 CustomData_copy_data(&mesh->pdata, &result->pdata, faceMap[i], i, 1);
271
272                 *dest = *source;
273                 dest->loopstart = k;
274                 CustomData_copy_data(&mesh->ldata, &result->ldata, source->loopstart, dest->loopstart, dest->totloop);
275
276                 ml_src = mloop_src + source->loopstart;
277                 for (j = 0; j < source->totloop; j++, k++, ml_src++, ml_dst++) {
278                         ml_dst->v = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(ml_src->v)));
279                         ml_dst->e = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash2, SET_INT_IN_POINTER(ml_src->e)));
280                 }
281         }
282
283         BLI_ghash_free(vertHash, NULL, NULL);
284         BLI_ghash_free(edgeHash, NULL, NULL);
285         BLI_ghash_free(edgeHash2, NULL, NULL);
286         
287         MEM_freeN(vertMap);
288         MEM_freeN(edgeMap);
289         MEM_freeN(faceMap);
290
291         if (mesh->runtime.cd_dirty_vert & CD_MASK_NORMAL) {
292                 result->runtime.cd_dirty_vert |= CD_MASK_NORMAL;
293         }
294
295         /* TODO(sybren): also copy flags & tags? */
296         return result;
297 }
298
299
300 ModifierTypeInfo modifierType_Build = {
301         /* name */              "Build",
302         /* structName */        "BuildModifierData",
303         /* structSize */        sizeof(BuildModifierData),
304         /* type */              eModifierTypeType_Nonconstructive,
305         /* flags */             eModifierTypeFlag_AcceptsMesh |
306                                 eModifierTypeFlag_AcceptsCVs,
307
308         /* copyData */          modifier_copyData_generic,
309
310         /* deformVerts_DM */    NULL,
311         /* deformMatrices_DM */ NULL,
312         /* deformVertsEM_DM */  NULL,
313         /* deformMatricesEM_DM*/NULL,
314         /* applyModifier_DM */  NULL,
315         /* applyModifierEM_DM */NULL,
316
317         /* deformVerts */       NULL,
318         /* deformMatrices */    NULL,
319         /* deformVertsEM */     NULL,
320         /* deformMatricesEM */  NULL,
321         /* applyModifier */     applyModifier,
322         /* applyModifierEM */   NULL,
323
324         /* initData */          initData,
325         /* requiredDataMask */  NULL,
326         /* freeData */          NULL,
327         /* isDisabled */        NULL,
328         /* updateDepsgraph */   NULL,
329         /* dependsOnTime */     dependsOnTime,
330         /* dependsOnNormals */  NULL,
331         /* foreachObjectLink */ NULL,
332         /* foreachIDLink */     NULL,
333         /* foreachTexLink */    NULL,
334 };