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