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