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