Threaded object update and EvaluationContext
[blender.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_curve.h"
54 #include "BKE_mesh.h"
55 #include "BKE_modifier.h"
56 #include "BKE_object.h"
57
58 #include "MOD_util.h"
59
60 #include "bmesh.h"
61
62 #include "depsgraph_private.h"
63
64 #include <ctype.h>
65 #include <stdlib.h>
66 #include <string.h>
67
68 static void initData(ModifierData *md)
69 {
70         ArrayModifierData *amd = (ArrayModifierData *) md;
71
72         /* default to 2 duplicates distributed along the x-axis by an
73          * offset of 1 object-width
74          */
75         amd->start_cap = amd->end_cap = amd->curve_ob = amd->offset_ob = NULL;
76         amd->count = 2;
77         zero_v3(amd->offset);
78         amd->scale[0] = 1;
79         amd->scale[1] = amd->scale[2] = 0;
80         amd->length = 0;
81         amd->merge_dist = 0.01;
82         amd->fit_type = MOD_ARR_FIXEDCOUNT;
83         amd->offset_type = MOD_ARR_OFF_RELATIVE;
84         amd->flags = 0;
85 }
86
87 static void copyData(ModifierData *md, ModifierData *target)
88 {
89 #if 0
90         ArrayModifierData *amd = (ArrayModifierData *) md;
91         ArrayModifierData *tamd = (ArrayModifierData *) target;
92 #endif
93         modifier_copyData_generic(md, target);
94 }
95
96 static void foreachObjectLink(
97         ModifierData *md, Object *ob,
98         void (*walk)(void *userData, Object *ob, Object **obpoin),
99         void *userData)
100 {
101         ArrayModifierData *amd = (ArrayModifierData *) md;
102
103         walk(userData, ob, &amd->start_cap);
104         walk(userData, ob, &amd->end_cap);
105         walk(userData, ob, &amd->curve_ob);
106         walk(userData, ob, &amd->offset_ob);
107 }
108
109 static void updateDepgraph(ModifierData *md, DagForest *forest,
110                            struct Scene *UNUSED(scene), Object *UNUSED(ob), DagNode *obNode)
111 {
112         ArrayModifierData *amd = (ArrayModifierData *) md;
113
114         if (amd->start_cap) {
115                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
116
117                 dag_add_relation(forest, curNode, obNode,
118                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
119         }
120         if (amd->end_cap) {
121                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
122
123                 dag_add_relation(forest, curNode, obNode,
124                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
125         }
126         if (amd->curve_ob) {
127                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
128
129                 dag_add_relation(forest, curNode, obNode,
130                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
131         }
132         if (amd->offset_ob) {
133                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
134
135                 dag_add_relation(forest, curNode, obNode,
136                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
137         }
138 }
139
140 static float vertarray_size(MVert *mvert, int numVerts, int axis)
141 {
142         int i;
143         float min_co, max_co;
144
145         /* if there are no vertices, width is 0 */
146         if (numVerts == 0) return 0;
147
148         /* find the minimum and maximum coordinates on the desired axis */
149         min_co = max_co = mvert->co[axis];
150         mvert++;
151         for (i = 1; i < numVerts; ++i, ++mvert) {
152                 if (mvert->co[axis] < min_co) min_co = mvert->co[axis];
153                 if (mvert->co[axis] > max_co) max_co = mvert->co[axis];
154         }
155
156         return max_co - min_co;
157 }
158
159 static int *find_doubles_index_map(BMesh *bm, BMOperator *dupe_op,
160                                    const ArrayModifierData *amd,
161                                    int *index_map_length)
162 {
163         BMOperator find_op;
164         BMOIter oiter;
165         BMVert *v, *v2;
166         BMElem *ele;
167         int *index_map, i;
168
169         BMO_op_initf(bm, &find_op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE),
170                      "find_doubles verts=%av dist=%f keep_verts=%s",
171                      amd->merge_dist, dupe_op, "geom");
172
173         BMO_op_exec(bm, &find_op);
174
175         i = 0;
176         BMO_ITER (ele, &oiter, dupe_op->slots_in, "geom", BM_ALL) {
177                 BM_elem_index_set(ele, i); /* set_dirty */
178                 i++;
179         }
180
181         BMO_ITER (ele, &oiter, dupe_op->slots_out, "geom.out", BM_ALL) {
182                 BM_elem_index_set(ele, i); /* set_dirty */
183                 i++;
184         }
185         /* above loops over all, so set all to dirty, if this is somehow
186          * setting valid values, this line can be removed - campbell */
187         bm->elem_index_dirty |= BM_VERT | BM_EDGE | BM_FACE;
188
189         (*index_map_length) = i;
190         index_map = MEM_callocN(sizeof(int) * (*index_map_length), "index_map");
191
192         /*element type argument doesn't do anything here*/
193         BMO_ITER (v, &oiter, find_op.slots_out, "targetmap.out", 0) {
194                 v2 = BMO_iter_map_value_ptr(&oiter);
195
196                 index_map[BM_elem_index_get(v)] = BM_elem_index_get(v2) + 1;
197         }
198
199         BMO_op_finish(bm, &find_op);
200
201         return index_map;
202 }
203
204 /* Used for start/end cap.
205  *
206  * this function expects all existing vertices to be tagged,
207  * so we can know new verts are not tagged.
208  *
209  * All verts will be tagged on exit.
210  */
211 static void bm_merge_dm_transform(BMesh *bm, DerivedMesh *dm, float mat[4][4],
212                                   const ArrayModifierData *amd,
213                                   BMOperator *dupe_op,
214                                   BMOpSlot dupe_op_slot_args[BMO_OP_MAX_SLOTS], const char *dupe_slot_name,
215                                   BMOperator *weld_op)
216 {
217         const int is_input = (dupe_op->slots_in == dupe_op_slot_args);
218         BMVert *v, *v2, *v3;
219         BMIter iter;
220
221         /* Add the DerivedMesh's elements to the BMesh. The pre-existing
222          * elements were already tagged, so the new elements can be
223          * identified by not having the BM_ELEM_TAG flag set. */
224         DM_to_bmesh_ex(dm, bm, false);
225
226         if (amd->flags & MOD_ARR_MERGE) {
227                 /* if merging is enabled, find doubles */
228                 
229                 BMOIter oiter;
230                 BMOperator find_op;
231                 BMOpSlot *slot_targetmap;
232
233                 BMO_op_initf(bm, &find_op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE),
234                              is_input ?  /* ugh */
235                              "find_doubles verts=%Hv dist=%f keep_verts=%s" :
236                              "find_doubles verts=%Hv dist=%f keep_verts=%S",
237                              BM_ELEM_TAG, amd->merge_dist,
238                              dupe_op, dupe_slot_name);
239
240                 /* append the dupe's geom to the findop input verts */
241                 if (is_input) {
242                         BMO_slot_buffer_append(&find_op, slots_in, "verts",
243                                                dupe_op,  slots_in, dupe_slot_name);
244                 }
245                 else if (dupe_op->slots_out == dupe_op_slot_args) {
246                         BMO_slot_buffer_append(&find_op, slots_in,  "verts",
247                                                dupe_op,  slots_out, dupe_slot_name);
248                 }
249                 else {
250                         BLI_assert(0);
251                 }
252
253                 /* transform and tag verts */
254                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
255                         if (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
256                                 mul_m4_v3(mat, v->co);
257                                 BM_elem_flag_enable(v, BM_ELEM_TAG);
258                         }
259                 }
260
261                 BMO_op_exec(bm, &find_op);
262
263                 slot_targetmap = BMO_slot_get(weld_op->slots_in, "targetmap");
264
265                 /* add new merge targets to weld operator */
266                 BMO_ITER (v, &oiter, find_op.slots_out, "targetmap.out", 0) {
267                         v2 = BMO_iter_map_value_ptr(&oiter);
268                         /* check in case the target vertex (v2) is already marked
269                          * for merging */
270                         while ((v3 = BMO_slot_map_elem_get(slot_targetmap, v2))) {
271                                 v2 = v3;
272                         }
273                         BMO_slot_map_elem_insert(weld_op, slot_targetmap, v, v2);
274                 }
275
276                 BMO_op_finish(bm, &find_op);
277         }
278         else {
279                 /* transform and tag verts */
280                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
281                         if (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
282                                 mul_m4_v3(mat, v->co);
283                                 BM_elem_flag_enable(v, BM_ELEM_TAG);
284                         }
285                 }
286         }
287 }
288
289 static void merge_first_last(BMesh *bm,
290                              const ArrayModifierData *amd,
291                              BMOperator *dupe_first,
292                              BMOperator *dupe_last,
293                              BMOperator *weld_op)
294 {
295         BMOperator find_op;
296         BMOIter oiter;
297         BMVert *v, *v2;
298         BMOpSlot *slot_targetmap;
299
300         BMO_op_initf(bm, &find_op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE),
301                      "find_doubles verts=%s dist=%f keep_verts=%s",
302                      dupe_first, "geom", amd->merge_dist,
303                      dupe_first, "geom");
304
305         /* append the last dupe's geom to the findop input verts */
306         BMO_slot_buffer_append(&find_op,  slots_in,  "verts",
307                                dupe_last, slots_out, "geom.out");
308
309         BMO_op_exec(bm, &find_op);
310
311         /* add new merge targets to weld operator */
312         slot_targetmap = BMO_slot_get(weld_op->slots_in, "targetmap");
313         BMO_ITER (v, &oiter, find_op.slots_out, "targetmap.out", 0) {
314                 if (!BMO_slot_map_contains(slot_targetmap, v)) {
315                         v2 = BMO_iter_map_value_ptr(&oiter);
316                         BMO_slot_map_elem_insert(weld_op, slot_targetmap, v, v2);
317                 }
318         }
319
320         BMO_op_finish(bm, &find_op);
321 }
322
323 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
324                                           Scene *scene, Object *ob, DerivedMesh *dm,
325                                           ModifierApplyFlag flag)
326 {
327         DerivedMesh *result;
328         BMesh *bm = DM_to_bmesh(dm, false);
329         BMOperator first_dupe_op, dupe_op, old_dupe_op, weld_op;
330         BMVert **first_geom = NULL;
331         int i, j;
332         int index_len = -1;  /* initialize to an invalid value */
333         /* offset matrix */
334         float offset[4][4];
335         float final_offset[4][4];
336         float length = amd->length;
337         int count = amd->count, maxVerts;
338         int *indexMap = NULL;
339         DerivedMesh *start_cap = NULL, *end_cap = NULL;
340         MVert *src_mvert;
341         BMOpSlot *slot_targetmap = NULL;  /* for weld_op */
342
343         /* need to avoid infinite recursion here */
344         if (amd->start_cap && amd->start_cap != ob && amd->start_cap->type == OB_MESH)
345                 start_cap = get_dm_for_modifier(amd->start_cap, flag);
346         if (amd->end_cap && amd->end_cap != ob && amd->end_cap->type == OB_MESH)
347                 end_cap = get_dm_for_modifier(amd->end_cap, flag);
348
349         unit_m4(offset);
350
351         src_mvert = dm->getVertArray(dm);
352         maxVerts = dm->getNumVerts(dm);
353
354         if (amd->offset_type & MOD_ARR_OFF_CONST)
355                 add_v3_v3v3(offset[3], offset[3], amd->offset);
356         if (amd->offset_type & MOD_ARR_OFF_RELATIVE) {
357                 for (j = 0; j < 3; j++)
358                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert, maxVerts, j);
359         }
360
361         if ((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
362                 float obinv[4][4];
363                 float result_mat[4][4];
364
365                 if (ob)
366                         invert_m4_m4(obinv, ob->obmat);
367                 else
368                         unit_m4(obinv);
369
370                 mul_serie_m4(result_mat, offset,
371                              obinv, amd->offset_ob->obmat,
372                              NULL, NULL, NULL, NULL, NULL);
373                 copy_m4_m4(offset, result_mat);
374         }
375
376         if (amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
377                 Curve *cu = amd->curve_ob->data;
378                 if (cu) {
379                         if (!amd->curve_ob->curve_cache || !amd->curve_ob->curve_cache->path) {
380                                 cu->flag |= CU_PATH; // needed for path & bevlist
381                                 BKE_displist_make_curveTypes(scene, amd->curve_ob, 0);
382                         }
383                         if (amd->curve_ob->curve_cache->path) {
384                                 float scale = mat4_to_scale(amd->curve_ob->obmat);
385                                 length = scale * amd->curve_ob->curve_cache->path->totdist;
386                         }
387                 }
388         }
389
390         /* calculate the maximum number of copies which will fit within the
391          * prescribed length */
392         if (amd->fit_type == MOD_ARR_FITLENGTH || amd->fit_type == MOD_ARR_FITCURVE) {
393                 float dist = len_v3(offset[3]);
394
395                 if (dist > 1e-6f)
396                         /* this gives length = first copy start to last copy end
397                          * add a tiny offset for floating point rounding errors */
398                         count = (length + 1e-6f) / dist;
399                 else
400                         /* if the offset has no translation, just make one copy */
401                         count = 1;
402         }
403
404         if (count < 1)
405                 count = 1;
406
407         /* calculate the offset matrix of the final copy (for merging) */
408         unit_m4(final_offset);
409
410         for (j = 0; j < count - 1; j++) {
411                 float tmp_mat[4][4];
412                 mul_m4_m4m4(tmp_mat, offset, final_offset);
413                 copy_m4_m4(final_offset, tmp_mat);
414         }
415
416         /* BMESH_TODO: bumping up the stack level avoids computing the normals
417          * after every top-level operator execution (and this modifier has the
418          * potential to execute a *lot* of top-level BMOps. There should be a
419          * cleaner way to do this. One possibility: a "mirror" BMOp would
420          * certainly help by compressing it all into one top-level BMOp that
421          * executes a lot of second-level BMOps. */
422         BM_mesh_elem_toolflags_ensure(bm);
423         BMO_push(bm, NULL);
424         bmesh_edit_begin(bm, 0);
425
426         if (amd->flags & MOD_ARR_MERGE) {
427                 BMO_op_init(bm, &weld_op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE),
428                             "weld_verts");
429
430                 slot_targetmap = BMO_slot_get(weld_op.slots_in, "targetmap");
431         }
432
433         BMO_op_initf(bm, &dupe_op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE),
434                      "duplicate geom=%avef");
435         first_dupe_op = dupe_op;
436
437         for (j = 0; j < count - 1; j++) {
438                 BMVert *v, *v2, *v3;
439                 BMOpSlot *geom_slot;
440                 BMOpSlot *geom_out_slot;
441                 BMOIter oiter;
442
443                 if (j != 0) {
444                         BMO_op_initf(bm, &dupe_op,
445                                      (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE),
446                                      "duplicate geom=%S", &old_dupe_op, "geom.out");
447                 }
448                 BMO_op_exec(bm, &dupe_op);
449
450                 geom_slot   = BMO_slot_get(dupe_op.slots_in,  "geom");
451                 geom_out_slot = BMO_slot_get(dupe_op.slots_out, "geom.out");
452
453                 if ((amd->flags & MOD_ARR_MERGEFINAL) && j == 0) {
454                         int first_geom_bytes = sizeof(BMVert *) * geom_slot->len;
455                                 
456                         /* make a copy of the initial geometry ordering so the
457                          * last duplicate can be merged into it */
458                         first_geom = MEM_mallocN(first_geom_bytes, "first_geom");
459                         memcpy(first_geom, geom_slot->data.buf, first_geom_bytes);
460                 }
461
462                 /* apply transformation matrix */
463                 BMO_ITER (v, &oiter, dupe_op.slots_out, "geom.out", BM_VERT) {
464                         mul_m4_v3(offset, v->co);
465                 }
466
467                 if (amd->flags & MOD_ARR_MERGE) {
468                         /*calculate merge mapping*/
469                         if (j == 0) {
470                                 indexMap = find_doubles_index_map(bm, &dupe_op,
471                                                                   amd, &index_len);
472                         }
473
474 #define _E(s, i) ((BMVert **)(s)->data.buf)[i]
475
476                         /* ensure this is set */
477                         BLI_assert(index_len != -1);
478
479                         for (i = 0; i < index_len; i++) {
480                                 if (!indexMap[i]) continue;
481
482                                 /* merge v (from 'geom.out') into v2 (from old 'geom') */
483                                 v = _E(geom_out_slot, i - geom_slot->len);
484                                 v2 = _E(geom_slot, indexMap[i] - 1);
485
486                                 /* check in case the target vertex (v2) is already marked
487                                  * for merging */
488                                 while ((v3 = BMO_slot_map_elem_get(slot_targetmap, v2))) {
489                                         v2 = v3;
490                                 }
491
492                                 BMO_slot_map_elem_insert(&weld_op, slot_targetmap, v, v2);
493                         }
494
495 #undef _E
496                 }
497
498                 /* already copied earlier, but after executation more slot
499                  * memory may be allocated */
500                 if (j == 0)
501                         first_dupe_op = dupe_op;
502                 
503                 if (j >= 2)
504                         BMO_op_finish(bm, &old_dupe_op);
505                 old_dupe_op = dupe_op;
506         }
507
508         if ((amd->flags & MOD_ARR_MERGE) &&
509             (amd->flags & MOD_ARR_MERGEFINAL) &&
510             (count > 1))
511         {
512                 /* Merge first and last copies. Note that we can't use the
513                  * indexMap for this because (unless the array is forming a
514                  * loop) the offset between first and last is different from
515                  * dupe X to dupe X+1. */
516
517                 merge_first_last(bm, amd, &first_dupe_op, &dupe_op, &weld_op);
518         }
519
520         /* start capping */
521         if (start_cap || end_cap) {
522                 BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, FALSE);
523
524                 if (start_cap) {
525                         float startoffset[4][4];
526                         invert_m4_m4(startoffset, offset);
527                         bm_merge_dm_transform(bm, start_cap, startoffset, amd,
528                                               &first_dupe_op, first_dupe_op.slots_in, "geom", &weld_op);
529                 }
530
531                 if (end_cap) {
532                         float endoffset[4][4];
533                         mul_m4_m4m4(endoffset, offset, final_offset);
534                         bm_merge_dm_transform(bm, end_cap, endoffset, amd,
535                                               &dupe_op, (count == 1) ? dupe_op.slots_in : dupe_op.slots_out,
536                                               (count == 1) ? "geom" : "geom.out", &weld_op);
537                 }
538         }
539         /* done capping */
540
541         /* free remaining dupe operators */
542         BMO_op_finish(bm, &first_dupe_op);
543         if (count > 2)
544                 BMO_op_finish(bm, &dupe_op);
545
546         /* run merge operator */
547         if (amd->flags & MOD_ARR_MERGE) {
548                 BMO_op_exec(bm, &weld_op);
549                 BMO_op_finish(bm, &weld_op);
550         }
551
552         /* Bump the stack level back down to match the adjustment up above */
553         BMO_pop(bm);
554
555         result = CDDM_from_bmesh(bm, FALSE);
556
557         if ((dm->dirty & DM_DIRTY_NORMALS) ||
558             ((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)))
559         {
560                 /* Update normals in case offset object has rotation. */
561                 result->dirty |= DM_DIRTY_NORMALS;
562         }
563
564         BM_mesh_free(bm);
565
566         if (indexMap)
567                 MEM_freeN(indexMap);
568         if (first_geom)
569                 MEM_freeN(first_geom);
570
571         return result;
572 }
573
574 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
575                                   DerivedMesh *dm,
576                                   ModifierApplyFlag flag)
577 {
578         DerivedMesh *result;
579         ArrayModifierData *amd = (ArrayModifierData *) md;
580
581         result = arrayModifier_doArray(amd, md->scene, ob, dm, flag);
582
583         return result;
584 }
585
586
587 ModifierTypeInfo modifierType_Array = {
588         /* name */              "Array",
589         /* structName */        "ArrayModifierData",
590         /* structSize */        sizeof(ArrayModifierData),
591         /* type */              eModifierTypeType_Constructive,
592         /* flags */             eModifierTypeFlag_AcceptsMesh |
593                                 eModifierTypeFlag_SupportsMapping |
594                                 eModifierTypeFlag_SupportsEditmode |
595                                 eModifierTypeFlag_EnableInEditmode |
596                                 eModifierTypeFlag_AcceptsCVs,
597
598         /* copyData */          copyData,
599         /* deformVerts */       NULL,
600         /* deformMatrices */    NULL,
601         /* deformVertsEM */     NULL,
602         /* deformMatricesEM */  NULL,
603         /* applyModifier */     applyModifier,
604         /* applyModifierEM */   NULL,
605         /* initData */          initData,
606         /* requiredDataMask */  NULL,
607         /* freeData */          NULL,
608         /* isDisabled */        NULL,
609         /* updateDepgraph */    updateDepgraph,
610         /* dependsOnTime */     NULL,
611         /* dependsOnNormals */  NULL,
612         /* foreachObjectLink */ foreachObjectLink,
613         /* foreachIDLink */     NULL,
614         /* foreachTexLink */    NULL,
615 };