Cleanup: Rename callback flags from library_query to `IDWALK_CB_...`
[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  *                 Patrice Bertrand
27  *
28  * ***** END GPL LICENSE BLOCK *****
29  *
30  */
31
32 /** \file blender/modifiers/intern/MOD_array.c
33  *  \ingroup modifiers
34  *
35  * Array modifier: duplicates the object multiple times along an axis.
36  */
37
38 #include "MEM_guardedalloc.h"
39
40 #include "BLI_math.h"
41 #include "BLI_utildefines.h"
42
43 #include "DNA_curve_types.h"
44 #include "DNA_meshdata_types.h"
45 #include "DNA_object_types.h"
46 #include "DNA_scene_types.h"
47
48 #include "BKE_cdderivedmesh.h"
49 #include "BKE_displist.h"
50 #include "BKE_curve.h"
51 #include "BKE_library_query.h"
52 #include "BKE_modifier.h"
53
54 #include "MOD_util.h"
55
56 #include "depsgraph_private.h"
57
58 /* Due to cyclic dependencies it's possible that curve used for
59  * deformation here is not evaluated at the time of evaluating
60  * this modifier.
61  */
62 #define CYCLIC_DEPENDENCY_WORKAROUND
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         zero_v3(amd->offset);
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 #if 0
86         ArrayModifierData *amd = (ArrayModifierData *) md;
87         ArrayModifierData *tamd = (ArrayModifierData *) target;
88 #endif
89         modifier_copyData_generic(md, target);
90 }
91
92 static void foreachObjectLink(
93         ModifierData *md, Object *ob,
94         ObjectWalkFunc walk, void *userData)
95 {
96         ArrayModifierData *amd = (ArrayModifierData *) md;
97
98         walk(userData, ob, &amd->start_cap, IDWALK_CB_NOP);
99         walk(userData, ob, &amd->end_cap, IDWALK_CB_NOP);
100         walk(userData, ob, &amd->curve_ob, IDWALK_CB_NOP);
101         walk(userData, ob, &amd->offset_ob, IDWALK_CB_NOP);
102 }
103
104 static void updateDepgraph(ModifierData *md, DagForest *forest,
105                            struct Main *UNUSED(bmain),
106                            struct Scene *UNUSED(scene),
107                            Object *UNUSED(ob), DagNode *obNode)
108 {
109         ArrayModifierData *amd = (ArrayModifierData *) md;
110
111         if (amd->start_cap) {
112                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
113
114                 dag_add_relation(forest, curNode, obNode,
115                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
116         }
117         if (amd->end_cap) {
118                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
119
120                 dag_add_relation(forest, curNode, obNode,
121                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
122         }
123         if (amd->curve_ob) {
124                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
125                 curNode->eval_flags |= DAG_EVAL_NEED_CURVE_PATH;
126
127                 dag_add_relation(forest, curNode, obNode,
128                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
129         }
130         if (amd->offset_ob) {
131                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
132
133                 dag_add_relation(forest, curNode, obNode,
134                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
135         }
136 }
137
138 static void updateDepsgraph(ModifierData *md,
139                             struct Main *UNUSED(bmain),
140                             struct Scene *scene,
141                             Object *UNUSED(ob),
142                             struct DepsNodeHandle *node)
143 {
144         ArrayModifierData *amd = (ArrayModifierData *)md;
145         if (amd->start_cap != NULL) {
146                 DEG_add_object_relation(node, amd->start_cap, DEG_OB_COMP_TRANSFORM, "Array Modifier Start Cap");
147         }
148         if (amd->end_cap != NULL) {
149                 DEG_add_object_relation(node, amd->end_cap, DEG_OB_COMP_TRANSFORM, "Array Modifier End Cap");
150         }
151         if (amd->curve_ob) {
152                 DEG_add_object_relation(node, amd->curve_ob, DEG_OB_COMP_GEOMETRY, "Array Modifier Curve");
153                 DEG_add_special_eval_flag(scene->depsgraph, &amd->curve_ob->id, DAG_EVAL_NEED_CURVE_PATH);
154         }
155         if (amd->offset_ob != NULL) {
156                 DEG_add_object_relation(node, amd->offset_ob, DEG_OB_COMP_TRANSFORM, "Array Modifier Offset");
157         }
158 }
159
160 static float vertarray_size(const MVert *mvert, int numVerts, int axis)
161 {
162         int i;
163         float min_co, max_co;
164
165         /* if there are no vertices, width is 0 */
166         if (numVerts == 0) return 0;
167
168         /* find the minimum and maximum coordinates on the desired axis */
169         min_co = max_co = mvert->co[axis];
170         mvert++;
171         for (i = 1; i < numVerts; ++i, ++mvert) {
172                 if (mvert->co[axis] < min_co) min_co = mvert->co[axis];
173                 if (mvert->co[axis] > max_co) max_co = mvert->co[axis];
174         }
175
176         return max_co - min_co;
177 }
178
179 BLI_INLINE float sum_v3(const float v[3])
180 {
181         return v[0] + v[1] + v[2];
182 }
183
184 /* Structure used for sorting vertices, when processing doubles */
185 typedef struct SortVertsElem {
186         int vertex_num;     /* The original index of the vertex, prior to sorting */
187         float co[3];        /* Its coordinates */
188         float sum_co;       /* sum_v3(co), just so we don't do the sum many times.  */
189 } SortVertsElem;
190
191
192 static int svert_sum_cmp(const void *e1, const void *e2)
193 {
194         const SortVertsElem *sv1 = e1;
195         const SortVertsElem *sv2 = e2;
196
197         if      (sv1->sum_co > sv2->sum_co) return  1;
198         else if (sv1->sum_co < sv2->sum_co) return -1;
199         else                                return  0;
200 }
201
202 static void svert_from_mvert(SortVertsElem *sv, const MVert *mv, const int i_begin, const int i_end)
203 {
204         int i;
205         for (i = i_begin; i < i_end; i++, sv++, mv++) {
206                 sv->vertex_num = i;
207                 copy_v3_v3(sv->co, mv->co);
208                 sv->sum_co = sum_v3(mv->co);
209         }
210 }
211
212 /**
213  * Take as inputs two sets of verts, to be processed for detection of doubles and mapping.
214  * Each set of verts is defined by its start within mverts array and its num_verts;
215  * It builds a mapping for all vertices within source, to vertices within target, or -1 if no double found
216  * The int doubles_map[num_verts_source] array must have been allocated by caller.
217  */
218 static void dm_mvert_map_doubles(
219         int *doubles_map,
220         const MVert *mverts,
221         const int target_start,
222         const int target_num_verts,
223         const int source_start,
224         const int source_num_verts,
225         const float dist)
226 {
227         const float dist3 = ((float)M_SQRT3 + 0.00005f) * dist;   /* Just above sqrt(3) */
228         int i_source, i_target, i_target_low_bound, target_end, source_end;
229         SortVertsElem *sorted_verts_target, *sorted_verts_source;
230         SortVertsElem *sve_source, *sve_target, *sve_target_low_bound;
231         bool target_scan_completed;
232
233         target_end = target_start + target_num_verts;
234         source_end = source_start + source_num_verts;
235
236         /* build array of MVerts to be tested for merging */
237         sorted_verts_target = MEM_mallocN(sizeof(SortVertsElem) * target_num_verts, __func__);
238         sorted_verts_source = MEM_mallocN(sizeof(SortVertsElem) * source_num_verts, __func__);
239
240         /* Copy target vertices index and cos into SortVertsElem array */
241         svert_from_mvert(sorted_verts_target, mverts + target_start, target_start, target_end);
242
243         /* Copy source vertices index and cos into SortVertsElem array */
244         svert_from_mvert(sorted_verts_source, mverts + source_start, source_start, source_end);
245
246         /* sort arrays according to sum of vertex coordinates (sumco) */
247         qsort(sorted_verts_target, target_num_verts, sizeof(SortVertsElem), svert_sum_cmp);
248         qsort(sorted_verts_source, source_num_verts, sizeof(SortVertsElem), svert_sum_cmp);
249
250         sve_target_low_bound = sorted_verts_target;
251         i_target_low_bound = 0;
252         target_scan_completed = false;
253
254         /* Scan source vertices, in SortVertsElem sorted array, */
255         /* all the while maintaining the lower bound of possible doubles in target vertices */
256         for (i_source = 0, sve_source = sorted_verts_source;
257              i_source < source_num_verts;
258              i_source++, sve_source++)
259         {
260                 int best_target_vertex = -1;
261                 float best_dist_sq = dist * dist;
262                 float sve_source_sumco;
263
264                 /* If source has already been assigned to a target (in an earlier call, with other chunks) */
265                 if (doubles_map[sve_source->vertex_num] != -1) {
266                         continue;
267                 }
268
269                 /* If target fully scanned already, then all remaining source vertices cannot have a double */
270                 if (target_scan_completed) {
271                         doubles_map[sve_source->vertex_num] = -1;
272                         continue;
273                 }
274
275                 sve_source_sumco = sum_v3(sve_source->co);
276
277                 /* Skip all target vertices that are more than dist3 lower in terms of sumco */
278                 /* and advance the overall lower bound, applicable to all remaining vertices as well. */
279                 while ((i_target_low_bound < target_num_verts) &&
280                        (sve_target_low_bound->sum_co < sve_source_sumco - dist3))
281                 {
282                         i_target_low_bound++;
283                         sve_target_low_bound++;
284                 }
285                 /* If end of target list reached, then no more possible doubles */
286                 if (i_target_low_bound >= target_num_verts) {
287                         doubles_map[sve_source->vertex_num] = -1;
288                         target_scan_completed = true;
289                         continue;
290                 }
291                 /* Test target candidates starting at the low bound of possible doubles, ordered in terms of sumco */
292                 i_target = i_target_low_bound;
293                 sve_target = sve_target_low_bound;
294
295                 /* i_target will scan vertices in the [v_source_sumco - dist3;  v_source_sumco + dist3] range */
296
297                 while ((i_target < target_num_verts) &&
298                        (sve_target->sum_co <= sve_source_sumco + dist3))
299                 {
300                         /* Testing distance for candidate double in target */
301                         /* v_target is within dist3 of v_source in terms of sumco;  check real distance */
302                         float dist_sq;
303                         if ((dist_sq = len_squared_v3v3(sve_source->co, sve_target->co)) <= best_dist_sq) {
304                                 /* Potential double found */
305                                 best_dist_sq = dist_sq;
306                                 best_target_vertex = sve_target->vertex_num;
307
308                                 /* If target is already mapped, we only follow that mapping if final target remains
309                                  * close enough from current vert (otherwise no mapping at all).
310                                  * Note that if we later find another target closer than this one, then we check it. But if other
311                                  * potential targets are farther, then there will be no mapping at all for this source. */
312                                 while (best_target_vertex != -1 && !ELEM(doubles_map[best_target_vertex], -1, best_target_vertex)) {
313                                         if (compare_len_v3v3(mverts[sve_source->vertex_num].co,
314                                                              mverts[doubles_map[best_target_vertex]].co,
315                                                              dist))
316                                         {
317                                                 best_target_vertex = doubles_map[best_target_vertex];
318                                         }
319                                         else {
320                                                 best_target_vertex = -1;
321                                         }
322                                 }
323                         }
324                         i_target++;
325                         sve_target++;
326                 }
327                 /* End of candidate scan: if none found then no doubles */
328                 doubles_map[sve_source->vertex_num] = best_target_vertex;
329         }
330
331         MEM_freeN(sorted_verts_source);
332         MEM_freeN(sorted_verts_target);
333 }
334
335
336 static void dm_merge_transform(
337         DerivedMesh *result, DerivedMesh *cap_dm, float cap_offset[4][4],
338         unsigned int cap_verts_index, unsigned int cap_edges_index, int cap_loops_index, int cap_polys_index,
339         int cap_nverts, int cap_nedges, int cap_nloops, int cap_npolys)
340 {
341         int *index_orig;
342         int i;
343         MVert *mv;
344         MEdge *me;
345         MLoop *ml;
346         MPoly *mp;
347
348         /* needed for subsurf so arrays are allocated */
349         cap_dm->getVertArray(cap_dm);
350         cap_dm->getEdgeArray(cap_dm);
351         cap_dm->getLoopArray(cap_dm);
352         cap_dm->getPolyArray(cap_dm);
353
354         DM_copy_vert_data(cap_dm, result, 0, cap_verts_index, cap_nverts);
355         DM_copy_edge_data(cap_dm, result, 0, cap_edges_index, cap_nedges);
356         DM_copy_loop_data(cap_dm, result, 0, cap_loops_index, cap_nloops);
357         DM_copy_poly_data(cap_dm, result, 0, cap_polys_index, cap_npolys);
358
359         mv = CDDM_get_verts(result) + cap_verts_index;
360
361         for (i = 0; i < cap_nverts; i++, mv++) {
362                 mul_m4_v3(cap_offset, mv->co);
363                 /* Reset MVert flags for caps */
364                 mv->flag = mv->bweight = 0;
365         }
366
367         /* adjust cap edge vertex indices */
368         me = CDDM_get_edges(result) + cap_edges_index;
369         for (i = 0; i < cap_nedges; i++, me++) {
370                 me->v1 += cap_verts_index;
371                 me->v2 += cap_verts_index;
372         }
373
374         /* adjust cap poly loopstart indices */
375         mp = CDDM_get_polys(result) + cap_polys_index;
376         for (i = 0; i < cap_npolys; i++, mp++) {
377                 mp->loopstart += cap_loops_index;
378         }
379
380         /* adjust cap loop vertex and edge indices */
381         ml = CDDM_get_loops(result) + cap_loops_index;
382         for (i = 0; i < cap_nloops; i++, ml++) {
383                 ml->v += cap_verts_index;
384                 ml->e += cap_edges_index;
385         }
386
387         /* set origindex */
388         index_orig = result->getVertDataArray(result, CD_ORIGINDEX);
389         if (index_orig) {
390                 copy_vn_i(index_orig + cap_verts_index, cap_nverts, ORIGINDEX_NONE);
391         }
392
393         index_orig = result->getEdgeDataArray(result, CD_ORIGINDEX);
394         if (index_orig) {
395                 copy_vn_i(index_orig + cap_edges_index, cap_nedges, ORIGINDEX_NONE);
396         }
397
398         index_orig = result->getPolyDataArray(result, CD_ORIGINDEX);
399         if (index_orig) {
400                 copy_vn_i(index_orig + cap_polys_index, cap_npolys, ORIGINDEX_NONE);
401         }
402
403         index_orig = result->getLoopDataArray(result, CD_ORIGINDEX);
404         if (index_orig) {
405                 copy_vn_i(index_orig + cap_loops_index, cap_nloops, ORIGINDEX_NONE);
406         }
407 }
408
409 static DerivedMesh *arrayModifier_doArray(
410         ArrayModifierData *amd,
411         Scene *scene, Object *ob, DerivedMesh *dm,
412         ModifierApplyFlag flag)
413 {
414         const float eps = 1e-6f;
415         const MVert *src_mvert;
416         MVert *mv, *mv_prev, *result_dm_verts;
417
418         MEdge *me;
419         MLoop *ml;
420         MPoly *mp;
421         int i, j, c, count;
422         float length = amd->length;
423         /* offset matrix */
424         float offset[4][4];
425         float scale[3];
426         bool offset_has_scale;
427         float current_offset[4][4];
428         float final_offset[4][4];
429         int *full_doubles_map = NULL;
430         int tot_doubles;
431
432         const bool use_merge = (amd->flags & MOD_ARR_MERGE) != 0;
433         const bool use_recalc_normals = (dm->dirty & DM_DIRTY_NORMALS) || use_merge;
434         const bool use_offset_ob = ((amd->offset_type & MOD_ARR_OFF_OBJ) && amd->offset_ob);
435
436         int start_cap_nverts = 0, start_cap_nedges = 0, start_cap_npolys = 0, start_cap_nloops = 0;
437         int end_cap_nverts = 0, end_cap_nedges = 0, end_cap_npolys = 0, end_cap_nloops = 0;
438         int result_nverts = 0, result_nedges = 0, result_npolys = 0, result_nloops = 0;
439         int chunk_nverts, chunk_nedges, chunk_nloops, chunk_npolys;
440         int first_chunk_start, first_chunk_nverts, last_chunk_start, last_chunk_nverts;
441
442         DerivedMesh *result, *start_cap_dm = NULL, *end_cap_dm = NULL;
443
444         chunk_nverts = dm->getNumVerts(dm);
445         chunk_nedges = dm->getNumEdges(dm);
446         chunk_nloops = dm->getNumLoops(dm);
447         chunk_npolys = dm->getNumPolys(dm);
448
449         count = amd->count;
450
451         if (amd->start_cap && amd->start_cap != ob && amd->start_cap->type == OB_MESH) {
452                 start_cap_dm = get_dm_for_modifier(amd->start_cap, flag);
453                 if (start_cap_dm) {
454                         start_cap_nverts = start_cap_dm->getNumVerts(start_cap_dm);
455                         start_cap_nedges = start_cap_dm->getNumEdges(start_cap_dm);
456                         start_cap_nloops = start_cap_dm->getNumLoops(start_cap_dm);
457                         start_cap_npolys = start_cap_dm->getNumPolys(start_cap_dm);
458                 }
459         }
460         if (amd->end_cap && amd->end_cap != ob && amd->end_cap->type == OB_MESH) {
461                 end_cap_dm = get_dm_for_modifier(amd->end_cap, flag);
462                 if (end_cap_dm) {
463                         end_cap_nverts = end_cap_dm->getNumVerts(end_cap_dm);
464                         end_cap_nedges = end_cap_dm->getNumEdges(end_cap_dm);
465                         end_cap_nloops = end_cap_dm->getNumLoops(end_cap_dm);
466                         end_cap_npolys = end_cap_dm->getNumPolys(end_cap_dm);
467                 }
468         }
469
470         /* Build up offset array, cumulating all settings options */
471
472         unit_m4(offset);
473         src_mvert = dm->getVertArray(dm);
474
475         if (amd->offset_type & MOD_ARR_OFF_CONST)
476                 add_v3_v3v3(offset[3], offset[3], amd->offset);
477
478         if (amd->offset_type & MOD_ARR_OFF_RELATIVE) {
479                 for (j = 0; j < 3; j++)
480                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert, chunk_nverts, j);
481         }
482
483         if (use_offset_ob) {
484                 float obinv[4][4];
485                 float result_mat[4][4];
486
487                 if (ob)
488                         invert_m4_m4(obinv, ob->obmat);
489                 else
490                         unit_m4(obinv);
491
492                 mul_m4_series(result_mat, offset,
493                               obinv, amd->offset_ob->obmat);
494                 copy_m4_m4(offset, result_mat);
495         }
496
497         /* Check if there is some scaling.  If scaling, then we will not translate mapping */
498         mat4_to_size(scale, offset);
499         offset_has_scale = !is_one_v3(scale);
500
501         if (amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
502                 Curve *cu = amd->curve_ob->data;
503                 if (cu) {
504 #ifdef CYCLIC_DEPENDENCY_WORKAROUND
505                         if (amd->curve_ob->curve_cache == NULL) {
506                                 BKE_displist_make_curveTypes(scene, amd->curve_ob, false);
507                         }
508 #endif
509
510                         if (amd->curve_ob->curve_cache && amd->curve_ob->curve_cache->path) {
511                                 float scale_fac = mat4_to_scale(amd->curve_ob->obmat);
512                                 length = scale_fac * amd->curve_ob->curve_cache->path->totdist;
513                         }
514                 }
515         }
516
517         /* calculate the maximum number of copies which will fit within the
518          * prescribed length */
519         if (amd->fit_type == MOD_ARR_FITLENGTH || amd->fit_type == MOD_ARR_FITCURVE) {
520                 float dist = len_v3(offset[3]);
521
522                 if (dist > eps) {
523                         /* this gives length = first copy start to last copy end
524                          * add a tiny offset for floating point rounding errors */
525                         count = (length + eps) / dist + 1;
526                 }
527                 else {
528                         /* if the offset has no translation, just make one copy */
529                         count = 1;
530                 }
531         }
532
533         if (count < 1)
534                 count = 1;
535
536         /* The number of verts, edges, loops, polys, before eventually merging doubles */
537         result_nverts = chunk_nverts * count + start_cap_nverts + end_cap_nverts;
538         result_nedges = chunk_nedges * count + start_cap_nedges + end_cap_nedges;
539         result_nloops = chunk_nloops * count + start_cap_nloops + end_cap_nloops;
540         result_npolys = chunk_npolys * count + start_cap_npolys + end_cap_npolys;
541
542         /* Initialize a result dm */
543         result = CDDM_from_template(dm, result_nverts, result_nedges, 0, result_nloops, result_npolys);
544         result_dm_verts = CDDM_get_verts(result);
545
546         if (use_merge) {
547                 /* Will need full_doubles_map for handling merge */
548                 full_doubles_map = MEM_mallocN(sizeof(int) * result_nverts, "mod array doubles map");
549                 copy_vn_i(full_doubles_map, result_nverts, -1);
550         }
551
552         /* copy customdata to original geometry */
553         DM_copy_vert_data(dm, result, 0, 0, chunk_nverts);
554         DM_copy_edge_data(dm, result, 0, 0, chunk_nedges);
555         DM_copy_loop_data(dm, result, 0, 0, chunk_nloops);
556         DM_copy_poly_data(dm, result, 0, 0, chunk_npolys);
557
558         /* subsurf for eg wont have mesh data in the
559          * now add mvert/medge/mface layers */
560
561         if (!CustomData_has_layer(&dm->vertData, CD_MVERT)) {
562                 dm->copyVertArray(dm, result_dm_verts);
563         }
564         if (!CustomData_has_layer(&dm->edgeData, CD_MEDGE)) {
565                 dm->copyEdgeArray(dm, CDDM_get_edges(result));
566         }
567         if (!CustomData_has_layer(&dm->polyData, CD_MPOLY)) {
568                 dm->copyLoopArray(dm, CDDM_get_loops(result));
569                 dm->copyPolyArray(dm, CDDM_get_polys(result));
570         }
571
572         /* Remember first chunk, in case of cap merge */
573         first_chunk_start = 0;
574         first_chunk_nverts = chunk_nverts;
575
576         unit_m4(current_offset);
577         for (c = 1; c < count; c++) {
578                 /* copy customdata to new geometry */
579                 DM_copy_vert_data(result, result, 0, c * chunk_nverts, chunk_nverts);
580                 DM_copy_edge_data(result, result, 0, c * chunk_nedges, chunk_nedges);
581                 DM_copy_loop_data(result, result, 0, c * chunk_nloops, chunk_nloops);
582                 DM_copy_poly_data(result, result, 0, c * chunk_npolys, chunk_npolys);
583
584                 mv_prev = result_dm_verts;
585                 mv = mv_prev + c * chunk_nverts;
586
587                 /* recalculate cumulative offset here */
588                 mul_m4_m4m4(current_offset, current_offset, offset);
589
590                 /* apply offset to all new verts */
591                 for (i = 0; i < chunk_nverts; i++, mv++, mv_prev++) {
592                         mul_m4_v3(current_offset, mv->co);
593
594                         /* We have to correct normals too, if we do not tag them as dirty! */
595                         if (!use_recalc_normals) {
596                                 float no[3];
597                                 normal_short_to_float_v3(no, mv->no);
598                                 mul_mat3_m4_v3(current_offset, no);
599                                 normalize_v3(no);
600                                 normal_float_to_short_v3(mv->no, no);
601                         }
602                 }
603
604                 /* adjust edge vertex indices */
605                 me = CDDM_get_edges(result) + c * chunk_nedges;
606                 for (i = 0; i < chunk_nedges; i++, me++) {
607                         me->v1 += c * chunk_nverts;
608                         me->v2 += c * chunk_nverts;
609                 }
610
611                 mp = CDDM_get_polys(result) + c * chunk_npolys;
612                 for (i = 0; i < chunk_npolys; i++, mp++) {
613                         mp->loopstart += c * chunk_nloops;
614                 }
615
616                 /* adjust loop vertex and edge indices */
617                 ml = CDDM_get_loops(result) + c * chunk_nloops;
618                 for (i = 0; i < chunk_nloops; i++, ml++) {
619                         ml->v += c * chunk_nverts;
620                         ml->e += c * chunk_nedges;
621                 }
622
623                 /* Handle merge between chunk n and n-1 */
624                 if (use_merge && (c >= 1)) {
625                         if (!offset_has_scale && (c >= 2)) {
626                                 /* Mapping chunk 3 to chunk 2 is a translation of mapping 2 to 1
627                                  * ... that is except if scaling makes the distance grow */
628                                 int k;
629                                 int this_chunk_index = c * chunk_nverts;
630                                 int prev_chunk_index = (c - 1) * chunk_nverts;
631                                 for (k = 0; k < chunk_nverts; k++, this_chunk_index++, prev_chunk_index++) {
632                                         int target = full_doubles_map[prev_chunk_index];
633                                         if (target != -1) {
634                                                 target += chunk_nverts; /* translate mapping */
635                                                 while (target != -1 && !ELEM(full_doubles_map[target], -1, target)) {
636                                                         /* If target is already mapped, we only follow that mapping if final target remains
637                                                          * close enough from current vert (otherwise no mapping at all). */
638                                                         if (compare_len_v3v3(result_dm_verts[this_chunk_index].co,
639                                                                              result_dm_verts[full_doubles_map[target]].co,
640                                                                              amd->merge_dist))
641                                                         {
642                                                                 target = full_doubles_map[target];
643                                                         }
644                                                         else {
645                                                                 target = -1;
646                                                         }
647                                                 }
648                                         }
649                                         full_doubles_map[this_chunk_index] = target;
650                                 }
651                         }
652                         else {
653                                 dm_mvert_map_doubles(
654                                         full_doubles_map,
655                                         result_dm_verts,
656                                         (c - 1) * chunk_nverts,
657                                         chunk_nverts,
658                                         c * chunk_nverts,
659                                         chunk_nverts,
660                                         amd->merge_dist);
661                         }
662                 }
663         }
664
665         last_chunk_start = (count - 1) * chunk_nverts;
666         last_chunk_nverts = chunk_nverts;
667
668         copy_m4_m4(final_offset, current_offset);
669
670         if (use_merge && (amd->flags & MOD_ARR_MERGEFINAL) && (count > 1)) {
671                 /* Merge first and last copies */
672                 dm_mvert_map_doubles(
673                         full_doubles_map,
674                         result_dm_verts,
675                         last_chunk_start,
676                         last_chunk_nverts,
677                         first_chunk_start,
678                         first_chunk_nverts,
679                         amd->merge_dist);
680         }
681
682         /* start capping */
683         if (start_cap_dm) {
684                 float start_offset[4][4];
685                 int start_cap_start = result_nverts - start_cap_nverts - end_cap_nverts;
686                 invert_m4_m4(start_offset, offset);
687                 dm_merge_transform(
688                         result, start_cap_dm, start_offset,
689                         result_nverts - start_cap_nverts - end_cap_nverts,
690                         result_nedges - start_cap_nedges - end_cap_nedges,
691                         result_nloops - start_cap_nloops - end_cap_nloops,
692                         result_npolys - start_cap_npolys - end_cap_npolys,
693                         start_cap_nverts, start_cap_nedges, start_cap_nloops, start_cap_npolys);
694                 /* Identify doubles with first chunk */
695                 if (use_merge) {
696                         dm_mvert_map_doubles(
697                                 full_doubles_map,
698                                 result_dm_verts,
699                                 first_chunk_start,
700                                 first_chunk_nverts,
701                                 start_cap_start,
702                                 start_cap_nverts,
703                                 amd->merge_dist);
704                 }
705         }
706
707         if (end_cap_dm) {
708                 float end_offset[4][4];
709                 int end_cap_start = result_nverts - end_cap_nverts;
710                 mul_m4_m4m4(end_offset, current_offset, offset);
711                 dm_merge_transform(
712                         result, end_cap_dm, end_offset,
713                         result_nverts - end_cap_nverts,
714                         result_nedges - end_cap_nedges,
715                         result_nloops - end_cap_nloops,
716                         result_npolys - end_cap_npolys,
717                         end_cap_nverts, end_cap_nedges, end_cap_nloops, end_cap_npolys);
718                 /* Identify doubles with last chunk */
719                 if (use_merge) {
720                         dm_mvert_map_doubles(
721                                 full_doubles_map,
722                                 result_dm_verts,
723                                 last_chunk_start,
724                                 last_chunk_nverts,
725                                 end_cap_start,
726                                 end_cap_nverts,
727                                 amd->merge_dist);
728                 }
729         }
730         /* done capping */
731
732         /* Handle merging */
733         tot_doubles = 0;
734         if (use_merge) {
735                 for (i = 0; i < result_nverts; i++) {
736                         int new_i = full_doubles_map[i];
737                         if (new_i != -1) {
738                                 /* We have to follow chains of doubles (merge start/end especially is likely to create some),
739                                  * those are not supported at all by CDDM_merge_verts! */
740                                 while (!ELEM(full_doubles_map[new_i], -1, new_i)) {
741                                         new_i = full_doubles_map[new_i];
742                                 }
743                                 if (i == new_i) {
744                                         full_doubles_map[i] = -1;
745                                 }
746                                 else {
747                                         full_doubles_map[i] = new_i;
748                                         tot_doubles++;
749                                 }
750                         }
751                 }
752                 if (tot_doubles > 0) {
753                         result = CDDM_merge_verts(result, full_doubles_map, tot_doubles, CDDM_MERGE_VERTS_DUMP_IF_EQUAL);
754                 }
755                 MEM_freeN(full_doubles_map);
756         }
757
758         /* In case org dm has dirty normals, or we made some merging, mark normals as dirty in new dm!
759          * TODO: we may need to set other dirty flags as well?
760          */
761         if (use_recalc_normals) {
762                 result->dirty |= DM_DIRTY_NORMALS;
763         }
764
765         return result;
766 }
767
768
769 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
770                                   DerivedMesh *dm,
771                                   ModifierApplyFlag flag)
772 {
773         ArrayModifierData *amd = (ArrayModifierData *) md;
774         return arrayModifier_doArray(amd, md->scene, ob, dm, flag);
775 }
776
777
778 ModifierTypeInfo modifierType_Array = {
779         /* name */              "Array",
780         /* structName */        "ArrayModifierData",
781         /* structSize */        sizeof(ArrayModifierData),
782         /* type */              eModifierTypeType_Constructive,
783         /* flags */             eModifierTypeFlag_AcceptsMesh |
784                                 eModifierTypeFlag_SupportsMapping |
785                                 eModifierTypeFlag_SupportsEditmode |
786                                 eModifierTypeFlag_EnableInEditmode |
787                                 eModifierTypeFlag_AcceptsCVs,
788
789         /* copyData */          copyData,
790         /* deformVerts */       NULL,
791         /* deformMatrices */    NULL,
792         /* deformVertsEM */     NULL,
793         /* deformMatricesEM */  NULL,
794         /* applyModifier */     applyModifier,
795         /* applyModifierEM */   NULL,
796         /* initData */          initData,
797         /* requiredDataMask */  NULL,
798         /* freeData */          NULL,
799         /* isDisabled */        NULL,
800         /* updateDepgraph */    updateDepgraph,
801         /* updateDepsgraph */   updateDepsgraph,
802         /* dependsOnTime */     NULL,
803         /* dependsOnNormals */  NULL,
804         /* foreachObjectLink */ foreachObjectLink,
805         /* foreachIDLink */     NULL,
806         /* foreachTexLink */    NULL,
807 };