4366ea7ee086e460ca7dc6fa7ccc4991be48bdde
[blender-staging.git] / source / blender / modifiers / intern / MOD_array.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_array.c
32  *  \ingroup modifiers
33  */
34
35
36 /* Array modifier: duplicates the object multiple times along an axis */
37
38 #include "MEM_guardedalloc.h"
39
40 #include "BLI_math.h"
41 #include "BLI_utildefines.h"
42 #include "BLI_string.h"
43 #include "BLI_ghash.h"
44 #include "BLI_edgehash.h"
45
46 #include "DNA_curve_types.h"
47 #include "DNA_meshdata_types.h"
48 #include "DNA_object_types.h"
49 #include "DNA_scene_types.h"
50
51 #include "BKE_cdderivedmesh.h"
52 #include "BKE_displist.h"
53 #include "BKE_mesh.h"
54 #include "BKE_modifier.h"
55 #include "BKE_object.h"
56 #include "BKE_tessmesh.h"
57
58 #include "depsgraph_private.h"
59
60 #include <ctype.h>
61 #include <stdlib.h>
62 #include <string.h>
63
64 static void initData(ModifierData *md)
65 {
66         ArrayModifierData *amd = (ArrayModifierData*) md;
67
68         /* default to 2 duplicates distributed along the x-axis by an
69         offset of 1 object-width
70         */
71         amd->start_cap = amd->end_cap = amd->curve_ob = amd->offset_ob = NULL;
72         amd->count = 2;
73         amd->offset[0] = amd->offset[1] = amd->offset[2] = 0;
74         amd->scale[0] = 1;
75         amd->scale[1] = amd->scale[2] = 0;
76         amd->length = 0;
77         amd->merge_dist = 0.01;
78         amd->fit_type = MOD_ARR_FIXEDCOUNT;
79         amd->offset_type = MOD_ARR_OFF_RELATIVE;
80         amd->flags = 0;
81 }
82
83 static void copyData(ModifierData *md, ModifierData *target)
84 {
85         ArrayModifierData *amd = (ArrayModifierData*) md;
86         ArrayModifierData *tamd = (ArrayModifierData*) target;
87
88         tamd->start_cap = amd->start_cap;
89         tamd->end_cap = amd->end_cap;
90         tamd->curve_ob = amd->curve_ob;
91         tamd->offset_ob = amd->offset_ob;
92         tamd->count = amd->count;
93         copy_v3_v3(tamd->offset, amd->offset);
94         copy_v3_v3(tamd->scale, amd->scale);
95         tamd->length = amd->length;
96         tamd->merge_dist = amd->merge_dist;
97         tamd->fit_type = amd->fit_type;
98         tamd->offset_type = amd->offset_type;
99         tamd->flags = amd->flags;
100 }
101
102 static void foreachObjectLink(
103                                                 ModifierData *md, Object *ob,
104          void (*walk)(void *userData, Object *ob, Object **obpoin),
105                 void *userData)
106 {
107         ArrayModifierData *amd = (ArrayModifierData*) md;
108
109         walk(userData, ob, &amd->start_cap);
110         walk(userData, ob, &amd->end_cap);
111         walk(userData, ob, &amd->curve_ob);
112         walk(userData, ob, &amd->offset_ob);
113 }
114
115 static void updateDepgraph(ModifierData *md, DagForest *forest,
116         struct Scene *UNUSED(scene), Object *UNUSED(ob), DagNode *obNode)
117 {
118         ArrayModifierData *amd = (ArrayModifierData*) md;
119
120         if (amd->start_cap) {
121                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
122
123                 dag_add_relation(forest, curNode, obNode,
124                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
125         }
126         if (amd->end_cap) {
127                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
128
129                 dag_add_relation(forest, curNode, obNode,
130                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
131         }
132         if (amd->curve_ob) {
133                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
134
135                 dag_add_relation(forest, curNode, obNode,
136                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
137         }
138         if (amd->offset_ob) {
139                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
140
141                 dag_add_relation(forest, curNode, obNode,
142                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
143         }
144 }
145
146 static float vertarray_size(MVert *mvert, int numVerts, int axis)
147 {
148         int i;
149         float min_co, max_co;
150
151         /* if there are no vertices, width is 0 */
152         if(numVerts == 0) return 0;
153
154         /* find the minimum and maximum coordinates on the desired axis */
155         min_co = max_co = mvert->co[axis];
156         ++mvert;
157         for(i = 1; i < numVerts; ++i, ++mvert) {
158                 if(mvert->co[axis] < min_co) min_co = mvert->co[axis];
159                 if(mvert->co[axis] > max_co) max_co = mvert->co[axis];
160         }
161
162         return max_co - min_co;
163 }
164
165 /* Used for start/end cap.
166  *
167  * this function expects all existing vertices to be tagged,
168  * so we can know new verts are not tagged.
169  *
170  * All verts will be tagged on exit.
171  */
172 static void bmesh_merge_dm_transform(BMesh* bm, DerivedMesh *dm, float mat[4][4])
173 {
174         BMVert *v;
175         BMIter iter;
176
177         DM_to_bmesh_ex(dm, bm);
178
179         /* transform all verts */
180         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
181                 if (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
182                         mul_m4_v3(mat, v->co);
183                         BM_elem_flag_enable(v, BM_ELEM_TAG);
184                 }
185         }
186 }
187
188 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
189                                           Scene *scene, Object *ob, DerivedMesh *dm,
190                                                                                   int UNUSED(initFlags))
191 {
192         DerivedMesh *result;
193         BMEditMesh *em = DM_to_editbmesh(ob, dm, NULL, FALSE);
194         BMOperator op, oldop, weldop;
195         int i, j, indexLen;
196         /* offset matrix */
197         float offset[4][4];
198         float final_offset[4][4];
199         float tmp_mat[4][4];
200         float length = amd->length;
201         int count = amd->count, maxVerts;
202         int *indexMap = NULL;
203         DerivedMesh *start_cap = NULL, *end_cap = NULL;
204         MVert *src_mvert;
205
206         /* need to avoid infinite recursion here */
207         if(amd->start_cap && amd->start_cap != ob)
208                 start_cap = mesh_get_derived_final(scene, amd->start_cap, CD_MASK_MESH);
209         if(amd->end_cap && amd->end_cap != ob)
210                 end_cap = mesh_get_derived_final(scene, amd->end_cap, CD_MASK_MESH);
211
212         unit_m4(offset);
213
214         src_mvert = dm->getVertArray(dm);
215         maxVerts = dm->getNumVerts(dm);
216
217         if(amd->offset_type & MOD_ARR_OFF_CONST)
218                 add_v3_v3v3(offset[3], offset[3], amd->offset);
219         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
220                 for(j = 0; j < 3; j++)
221                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
222                                         maxVerts, j);
223         }
224
225         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
226                 float obinv[4][4];
227                 float result_mat[4][4];
228
229                 if(ob)
230                         invert_m4_m4(obinv, ob->obmat);
231                 else
232                         unit_m4(obinv);
233
234                 mul_serie_m4(result_mat, offset,
235                              obinv, amd->offset_ob->obmat,
236                              NULL, NULL, NULL, NULL, NULL);
237                 copy_m4_m4(offset, result_mat);
238         }
239
240         /* calculate the offset matrix of the final copy (for merging) */
241         unit_m4(final_offset);
242
243         for(j=0; j < count - 1; j++) {
244                 mult_m4_m4m4(tmp_mat, offset, final_offset);
245                 copy_m4_m4(final_offset, tmp_mat);
246         }
247
248         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
249                 Curve *cu = amd->curve_ob->data;
250                 if(cu) {
251                         float tmp_mat[3][3];
252                         float scale;
253                         
254                         object_to_mat3(amd->curve_ob, tmp_mat);
255                         scale = mat3_to_scale(tmp_mat);
256                                 
257                         if(!cu->path) {
258                                 cu->flag |= CU_PATH; // needed for path & bevlist
259                                 makeDispListCurveTypes(scene, amd->curve_ob, 0);
260                         }
261                         if(cu->path)
262                                 length = scale*cu->path->totdist;
263                 }
264         }
265
266         /* calculate the maximum number of copies which will fit within the
267         prescribed length */
268         if(amd->fit_type == MOD_ARR_FITLENGTH
269                   || amd->fit_type == MOD_ARR_FITCURVE) {
270                 float dist = sqrt(dot_v3v3(offset[3], offset[3]));
271
272                 if(dist > 1e-6f)
273                         /* this gives length = first copy start to last copy end
274                         add a tiny offset for floating point rounding errors */
275                         count = (length + 1e-6f) / dist;
276                 else
277                         /* if the offset has no translation, just make one copy */
278                         count = 1;
279         }
280
281         if(count < 1)
282                 count = 1;
283
284         /* BMESH_TODO: bumping up the stack level avoids computing the normals
285            after every top-level operator execution (and this modifier has the
286            potential to execute a *lot* of top-level BMOps. There should be a
287            cleaner way to do this. One possibility: a "mirror" BMOp would
288            certainly help by compressing it all into one top-level BMOp that
289            executes a lot of second-level BMOps. */
290         BMO_push(em->bm, NULL);
291         bmesh_begin_edit(em->bm, 0);
292
293         BMO_op_init(em->bm, &weldop, "weldverts");
294         BMO_op_initf(em->bm, &op, "dupe geom=%avef");
295         oldop = op;
296         for (j=0; j < count - 1; j++) {
297                 BMVert *v, *v2;
298                 BMOpSlot *s1;
299                 BMOpSlot *s2;
300
301                 BMO_op_initf(em->bm, &op, "dupe geom=%s", &oldop, j==0 ? "geom" : "newout");
302                 BMO_op_exec(em->bm, &op);
303
304                 s1 = BMO_slot_get(&op, "geom");
305                 s2 = BMO_slot_get(&op, "newout");
306
307                 BMO_op_callf(em->bm, "transform mat=%m4 verts=%s", offset, &op, "newout");
308
309                 #define _E(s, i) ((BMVert **)(s)->data.buf)[i]
310
311                 /*calculate merge mapping*/
312                 if (j == 0) {
313                         BMOperator findop;
314                         BMOIter oiter;
315                         BMVert *v, *v2;
316                         BMHeader *h;
317
318                         BMO_op_initf(em->bm, &findop,
319                                      "finddoubles verts=%av dist=%f keepverts=%s",
320                                      amd->merge_dist, &op, "geom");
321
322                         i = 0;
323                         BMO_ITER(h, &oiter, em->bm, &op, "geom", BM_ALL) {
324                                 BM_elem_index_set(h, i); /* set_dirty */
325                                 i++;
326                         }
327
328                         BMO_ITER(h, &oiter, em->bm, &op, "newout", BM_ALL) {
329                                 BM_elem_index_set(h, i); /* set_dirty */
330                                 i++;
331                         }
332                         /* above loops over all, so set all to dirty, if this is somehow
333                          * setting valid values, this line can be remvoed - campbell */
334                         em->bm->elem_index_dirty |= BM_VERT | BM_EDGE | BM_FACE;
335
336
337                         BMO_op_exec(em->bm, &findop);
338
339                         indexLen = i;
340                         indexMap = MEM_callocN(sizeof(int)*indexLen, "indexMap");
341
342                         /*element type argument doesn't do anything here*/
343                         BMO_ITER(v, &oiter, em->bm, &findop, "targetmapout", 0) {
344                                 v2 = BMO_iter_map_value_p(&oiter);
345
346                                 indexMap[BM_elem_index_get(v)] = BM_elem_index_get(v2)+1;
347                         }
348
349                         BMO_op_finish(em->bm, &findop);
350                 }
351
352                 /*generate merge mappping using index map.  we do this by using the
353                   operator slots as lookup arrays.*/
354                 #define E(i) (i) < s1->len ? _E(s1, i) : _E(s2, (i)-s1->len)
355
356                 for (i=0; i<indexLen; i++) {
357                         if (!indexMap[i]) continue;
358
359                         v = E(i);
360                         v2 = E(indexMap[i]-1);
361
362                         BMO_slot_map_ptr_insert(em->bm, &weldop, "targetmap", v, v2);
363                 }
364
365                 #undef E
366                 #undef _E
367
368                 BMO_op_finish(em->bm, &oldop);
369                 oldop = op;
370         }
371
372         if (j > 0) BMO_op_finish(em->bm, &op);
373
374         /* BMESH_TODO - cap ends are not welded, even though weld is called after */
375
376         /* start capping */
377         if ((start_cap || end_cap) &&
378
379             /* BMESH_TODO - theres a bug in DM_to_bmesh_ex() when in editmode!
380                  * this needs investigation, but for now at least dont crash */
381             ob->mode != OB_MODE_EDIT
382
383             )
384         {
385                 BM_mesh_elem_flag_enable_all(em->bm, BM_VERT, BM_ELEM_TAG);
386
387                 if (start_cap) {
388                         float startoffset[4][4];
389                         invert_m4_m4(startoffset, offset);
390                         bmesh_merge_dm_transform(em->bm, start_cap, startoffset);
391                 }
392
393                 if (end_cap) {
394                         float endoffset[4][4];
395                         mult_m4_m4m4(endoffset, offset, final_offset);
396                         bmesh_merge_dm_transform(em->bm, end_cap, endoffset);
397                 }
398         }
399         /* done capping */
400
401         if (amd->flags & MOD_ARR_MERGE)
402                 BMO_op_exec(em->bm, &weldop);
403
404         BMO_op_finish(em->bm, &weldop);
405
406         /* Bump the stack level back down to match the adjustment up above */
407         BMO_pop(em->bm);
408
409         BLI_assert(em->looptris == NULL);
410         result = CDDM_from_BMEditMesh(em, NULL, FALSE, FALSE);
411
412         BMEdit_Free(em);
413         MEM_freeN(em);
414         MEM_freeN(indexMap);
415
416         return result;
417 }
418
419 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
420                                                 DerivedMesh *dm,
421                                                 int UNUSED(useRenderParams),
422                                                 int UNUSED(isFinalCalc))
423 {
424         DerivedMesh *result;
425         ArrayModifierData *amd = (ArrayModifierData*) md;
426
427         result = arrayModifier_doArray(amd, md->scene, ob, dm, 0);
428
429         //if(result != dm)
430         //      CDDM_calc_normals_mapping(result);
431
432         return result;
433 }
434
435 static DerivedMesh *applyModifierEM(ModifierData *md, Object *ob,
436                                                 struct BMEditMesh *UNUSED(editData),
437                                                 DerivedMesh *dm)
438 {
439         return applyModifier(md, ob, dm, 0, 1);
440 }
441
442
443 ModifierTypeInfo modifierType_Array = {
444         /* name */              "Array",
445         /* structName */        "ArrayModifierData",
446         /* structSize */        sizeof(ArrayModifierData),
447         /* type */              eModifierTypeType_Constructive,
448         /* flags */             eModifierTypeFlag_AcceptsMesh
449                                                         | eModifierTypeFlag_SupportsMapping
450                                                         | eModifierTypeFlag_SupportsEditmode
451                                                         | eModifierTypeFlag_EnableInEditmode
452                                                         | eModifierTypeFlag_AcceptsCVs,
453
454         /* copyData */          copyData,
455         /* deformVerts */       NULL,
456         /* deformMatrices */    NULL,
457         /* deformVertsEM */     NULL,
458         /* deformMatricesEM */  NULL,
459         /* applyModifier */     applyModifier,
460         /* applyModifierEM */   applyModifierEM,
461         /* initData */          initData,
462         /* requiredDataMask */  NULL,
463         /* freeData */          NULL,
464         /* isDisabled */        NULL,
465         /* updateDepgraph */    updateDepgraph,
466         /* dependsOnTime */     NULL,
467         /* dependsOnNormals */  NULL,
468         /* foreachObjectLink */ foreachObjectLink,
469         /* foreachIDLink */     NULL,
470         /* foreachTexLink */    NULL,
471 };