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