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