converted more mixed tab/space indentations to tabs. only whitespace changes.
[blender.git] / source / blender / modifiers / intern / MOD_array.c
1 /*
2 * $Id$
3 *
4 * ***** BEGIN GPL LICENSE BLOCK *****
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software  Foundation,
18 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 *
20 * The Original Code is Copyright (C) 2005 by the Blender Foundation.
21 * All rights reserved.
22 *
23 * Contributor(s): Daniel Dunbar
24 *                 Ton Roosendaal,
25 *                 Ben Batt,
26 *                 Brecht Van Lommel,
27 *                 Campbell Barton
28 *
29 * ***** END GPL LICENSE BLOCK *****
30 *
31 */
32
33 /** \file blender/modifiers/intern/MOD_array.c
34  *  \ingroup modifiers
35  */
36
37
38 /* Array modifier: duplicates the object multiple times along an axis */
39
40 #include "MEM_guardedalloc.h"
41
42 #include "BLI_math.h"
43 #include "BLI_utildefines.h"
44 #include "BLI_ghash.h"
45 #include "BLI_edgehash.h"
46
47 #include "DNA_curve_types.h"
48 #include "DNA_meshdata_types.h"
49 #include "DNA_object_types.h"
50
51 #include "BKE_cdderivedmesh.h"
52 #include "BKE_displist.h"
53 #include "BKE_mesh.h"
54 #include "BKE_modifier.h"
55 #include "BKE_object.h"
56
57 #include "depsgraph_private.h"
58
59 #include "MOD_util.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         amd->offset[0] = amd->offset[1] = amd->offset[2] = 0;
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         ArrayModifierData *amd = (ArrayModifierData*) md;
83         ArrayModifierData *tamd = (ArrayModifierData*) target;
84
85         tamd->start_cap = amd->start_cap;
86         tamd->end_cap = amd->end_cap;
87         tamd->curve_ob = amd->curve_ob;
88         tamd->offset_ob = amd->offset_ob;
89         tamd->count = amd->count;
90         copy_v3_v3(tamd->offset, amd->offset);
91         copy_v3_v3(tamd->scale, amd->scale);
92         tamd->length = amd->length;
93         tamd->merge_dist = amd->merge_dist;
94         tamd->fit_type = amd->fit_type;
95         tamd->offset_type = amd->offset_type;
96         tamd->flags = amd->flags;
97 }
98
99 static void foreachObjectLink(
100                                                 ModifierData *md, Object *ob,
101          void (*walk)(void *userData, Object *ob, Object **obpoin),
102                 void *userData)
103 {
104         ArrayModifierData *amd = (ArrayModifierData*) md;
105
106         walk(userData, ob, &amd->start_cap);
107         walk(userData, ob, &amd->end_cap);
108         walk(userData, ob, &amd->curve_ob);
109         walk(userData, ob, &amd->offset_ob);
110 }
111
112 static void updateDepgraph(ModifierData *md, DagForest *forest,
113         struct Scene *UNUSED(scene), Object *UNUSED(ob), DagNode *obNode)
114 {
115         ArrayModifierData *amd = (ArrayModifierData*) md;
116
117         if (amd->start_cap) {
118                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
119
120                 dag_add_relation(forest, curNode, obNode,
121                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
122         }
123         if (amd->end_cap) {
124                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
125
126                 dag_add_relation(forest, curNode, obNode,
127                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
128         }
129         if (amd->curve_ob) {
130                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
131
132                 dag_add_relation(forest, curNode, obNode,
133                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
134         }
135         if (amd->offset_ob) {
136                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
137
138                 dag_add_relation(forest, curNode, obNode,
139                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
140         }
141 }
142
143 static float vertarray_size(MVert *mvert, int numVerts, int axis)
144 {
145         int i;
146         float min_co, max_co;
147
148         /* if there are no vertices, width is 0 */
149         if(numVerts == 0) return 0;
150
151         /* find the minimum and maximum coordinates on the desired axis */
152         min_co = max_co = mvert->co[axis];
153         ++mvert;
154         for(i = 1; i < numVerts; ++i, ++mvert) {
155                 if(mvert->co[axis] < min_co) min_co = mvert->co[axis];
156                 if(mvert->co[axis] > max_co) max_co = mvert->co[axis];
157         }
158
159         return max_co - min_co;
160 }
161
162 /* XXX This function fixes bad merging code, in some cases removing vertices creates indices > maxvert */
163
164 static int test_index_face_maxvert(MFace *mface, CustomData *fdata, int mfindex, int nr, int maxvert)
165 {
166         if(mface->v1 >= maxvert) {
167                 // printf("bad index in array\n");
168                 mface->v1= maxvert - 1;
169         }
170         if(mface->v2 >= maxvert) {
171                 // printf("bad index in array\n");
172                 mface->v2= maxvert - 1;
173         }
174         if(mface->v3 >= maxvert) {
175                 // printf("bad index in array\n");
176                 mface->v3= maxvert - 1;
177         }
178         if(mface->v4 >= maxvert) {
179                 // printf("bad index in array\n");
180                 mface->v4= maxvert - 1;
181         }
182         
183         return test_index_face(mface, fdata, mfindex, nr);
184 }
185
186 typedef struct IndexMapEntry {
187         /* the new vert index that this old vert index maps to */
188         int new;
189         /* -1 if this vert isn't merged, otherwise the old vert index it
190         * should be replaced with
191         */
192         int merge;
193         /* 1 if this vert's first copy is merged with the last copy of its
194         * merge target, otherwise 0
195         */
196         short merge_final;
197 } IndexMapEntry;
198
199 /* indexMap - an array of IndexMap entries
200  * oldIndex - the old index to map
201  * copyNum - the copy number to map to (original = 0, first copy = 1, etc.)
202  */
203 static int calc_mapping(IndexMapEntry *indexMap, int oldIndex, int copyNum)
204 {
205         if(indexMap[oldIndex].merge < 0) {
206                 /* vert wasn't merged, so use copy of this vert */
207                 return indexMap[oldIndex].new + copyNum;
208         } else if(indexMap[oldIndex].merge == oldIndex) {
209                 /* vert was merged with itself */
210                 return indexMap[oldIndex].new;
211         } else {
212                 /* vert was merged with another vert */
213                 /* follow the chain of merges to the end, or until we've passed
214                 * a number of vertices equal to the copy number
215                 */
216                 if(copyNum <= 0)
217                         return indexMap[oldIndex].new;
218                 else
219                         return calc_mapping(indexMap, indexMap[oldIndex].merge,
220                                                 copyNum - 1);
221         }
222 }
223
224 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
225                                           struct Scene *scene, Object *ob, DerivedMesh *dm,
226            int initFlags)
227 {
228         int i, j;
229         /* offset matrix */
230         float offset[4][4];
231         float final_offset[4][4];
232         float tmp_mat[4][4];
233         float length = amd->length;
234         int count = amd->count;
235         int numVerts, numEdges, numFaces;
236         int maxVerts, maxEdges, maxFaces;
237         int finalVerts, finalEdges, finalFaces;
238         DerivedMesh *result, *start_cap = NULL, *end_cap = NULL;
239         MVert *mvert, *src_mvert;
240         MEdge *medge;
241         MFace *mface;
242
243         IndexMapEntry *indexMap;
244
245         EdgeHash *edges;
246
247         /* need to avoid infinite recursion here */
248         if(amd->start_cap && amd->start_cap != ob)
249                 start_cap = amd->start_cap->derivedFinal;
250         if(amd->end_cap && amd->end_cap != ob)
251                 end_cap = amd->end_cap->derivedFinal;
252
253         unit_m4(offset);
254
255         indexMap = MEM_callocN(sizeof(*indexMap) * dm->getNumVerts(dm),
256                                    "indexmap");
257
258         src_mvert = dm->getVertArray(dm);
259
260         maxVerts = dm->getNumVerts(dm);
261
262         if(amd->offset_type & MOD_ARR_OFF_CONST)
263                 add_v3_v3(offset[3], amd->offset);
264         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
265                 for(j = 0; j < 3; j++)
266                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
267                                         maxVerts, j);
268         }
269
270         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
271                 float obinv[4][4];
272                 float result_mat[4][4];
273
274                 if(ob)
275                         invert_m4_m4(obinv, ob->obmat);
276                 else
277                         unit_m4(obinv);
278
279                 mul_serie_m4(result_mat, offset,
280                                  obinv, amd->offset_ob->obmat,
281          NULL, NULL, NULL, NULL, NULL);
282                 copy_m4_m4(offset, result_mat);
283         }
284
285         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
286                 Curve *cu = amd->curve_ob->data;
287                 if(cu) {
288                         float tmp_mat[3][3];
289                         float scale;
290                         
291                         object_to_mat3(amd->curve_ob, tmp_mat);
292                         scale = mat3_to_scale(tmp_mat);
293                                 
294                         if(!cu->path) {
295                                 cu->flag |= CU_PATH; // needed for path & bevlist
296                                 makeDispListCurveTypes(scene, amd->curve_ob, 0);
297                         }
298                         if(cu->path)
299                                 length = scale*cu->path->totdist;
300                 }
301         }
302
303         /* calculate the maximum number of copies which will fit within the
304         prescribed length */
305         if(amd->fit_type == MOD_ARR_FITLENGTH
306                   || amd->fit_type == MOD_ARR_FITCURVE) {
307                 float dist = sqrt(dot_v3v3(offset[3], offset[3]));
308
309                 if(dist > 1e-6f)
310                         /* this gives length = first copy start to last copy end
311                         add a tiny offset for floating point rounding errors */
312                         count = (length + 1e-6f) / dist;
313                 else
314                         /* if the offset has no translation, just make one copy */
315                         count = 1;
316         }
317
318         if(count < 1)
319                 count = 1;
320
321         /* allocate memory for count duplicates (including original) plus
322                   * start and end caps
323         */
324         finalVerts = dm->getNumVerts(dm) * count;
325         finalEdges = dm->getNumEdges(dm) * count;
326         finalFaces = dm->getNumFaces(dm) * count;
327         if(start_cap) {
328                 finalVerts += start_cap->getNumVerts(start_cap);
329                 finalEdges += start_cap->getNumEdges(start_cap);
330                 finalFaces += start_cap->getNumFaces(start_cap);
331         }
332         if(end_cap) {
333                 finalVerts += end_cap->getNumVerts(end_cap);
334                 finalEdges += end_cap->getNumEdges(end_cap);
335                 finalFaces += end_cap->getNumFaces(end_cap);
336         }
337         result = CDDM_from_template(dm, finalVerts, finalEdges, finalFaces);
338
339         /* calculate the offset matrix of the final copy (for merging) */
340         unit_m4(final_offset);
341
342         for(j=0; j < count - 1; j++) {
343                 mul_m4_m4m4(tmp_mat, final_offset, offset);
344                 copy_m4_m4(final_offset, tmp_mat);
345         }
346
347         numVerts = numEdges = numFaces = 0;
348         mvert = CDDM_get_verts(result);
349
350         for (i = 0; i < maxVerts; i++) {
351                 indexMap[i].merge = -1; /* default to no merge */
352                 indexMap[i].merge_final = 0; /* default to no merge */
353         }
354
355         for (i = 0; i < maxVerts; i++) {
356                 MVert *inMV;
357                 MVert *mv = &mvert[numVerts];
358                 MVert *mv2;
359                 float co[3];
360
361                 inMV = &src_mvert[i];
362
363                 DM_copy_vert_data(dm, result, i, numVerts, 1);
364                 *mv = *inMV;
365                 numVerts++;
366
367                 indexMap[i].new = numVerts - 1;
368
369                 copy_v3_v3(co, mv->co);
370                 
371                 /* Attempts to merge verts from one duplicate with verts from the
372                           * next duplicate which are closer than amd->merge_dist.
373                           * Only the first such vert pair is merged.
374                           * If verts are merged in the first duplicate pair, they are merged
375                           * in all pairs.
376                 */
377                 if((count > 1) && (amd->flags & MOD_ARR_MERGE)) {
378                         float tmp_co[3];
379                         mul_v3_m4v3(tmp_co, offset, mv->co);
380
381                         for(j = 0; j < maxVerts; j++) {
382                                 /* if vertex already merged, don't use it */
383                                 if( indexMap[j].merge != -1 ) continue;
384
385                                 inMV = &src_mvert[j];
386                                 /* if this vert is within merge limit, merge */
387                                 if(compare_len_v3v3(tmp_co, inMV->co, amd->merge_dist)) {
388                                         indexMap[i].merge = j;
389
390                                         /* test for merging with final copy of merge target */
391                                         if(amd->flags & MOD_ARR_MERGEFINAL) {
392                                                 copy_v3_v3(tmp_co, inMV->co);
393                                                 inMV = &src_mvert[i];
394                                                 mul_m4_v3(final_offset, tmp_co);
395                                                 if(compare_len_v3v3(tmp_co, inMV->co, amd->merge_dist))
396                                                         indexMap[i].merge_final = 1;
397                                         }
398                                         break;
399                                 }
400                         }
401                 }
402
403                 /* if no merging, generate copies of this vert */
404                 if(indexMap[i].merge < 0) {
405                         for(j=0; j < count - 1; j++) {
406                                 mv2 = &mvert[numVerts];
407
408                                 DM_copy_vert_data(result, result, numVerts - 1, numVerts, 1);
409                                 *mv2 = *mv;
410                                 numVerts++;
411
412                                 mul_m4_v3(offset, co);
413                                 copy_v3_v3(mv2->co, co);
414                         }
415                 } else if(indexMap[i].merge != i && indexMap[i].merge_final) {
416                         /* if this vert is not merging with itself, and it is merging
417                                   * with the final copy of its merge target, remove the first copy
418                         */
419                         numVerts--;
420                         DM_free_vert_data(result, numVerts, 1);
421                 }
422         }
423
424         /* make a hashtable so we can avoid duplicate edges from merging */
425         edges = BLI_edgehash_new();
426
427         maxEdges = dm->getNumEdges(dm);
428         medge = CDDM_get_edges(result);
429         for(i = 0; i < maxEdges; i++) {
430                 MEdge inMED;
431                 MEdge med;
432                 MEdge *med2;
433                 int vert1, vert2;
434
435                 dm->getEdge(dm, i, &inMED);
436
437                 med = inMED;
438                 med.v1 = indexMap[inMED.v1].new;
439                 med.v2 = indexMap[inMED.v2].new;
440
441                 /* if vertices are to be merged with the final copies of their
442                           * merge targets, calculate that final copy
443                 */
444                 if(indexMap[inMED.v1].merge_final) {
445                         med.v1 = calc_mapping(indexMap, indexMap[inMED.v1].merge,
446                         count - 1);
447                 }
448                 if(indexMap[inMED.v2].merge_final) {
449                         med.v2 = calc_mapping(indexMap, indexMap[inMED.v2].merge,
450                         count - 1);
451                 }
452
453                 if(med.v1 == med.v2) continue;
454
455                 /* XXX Unfortunately the calc_mapping returns sometimes numVerts... leads to bad crashes */
456                 if(med.v1 >= numVerts)
457                         med.v1= numVerts-1;
458                 if(med.v2 >= numVerts)
459                         med.v2= numVerts-1;
460
461                 if (initFlags) {
462                         med.flag |= ME_EDGEDRAW | ME_EDGERENDER;
463                 }
464
465                 if(!BLI_edgehash_haskey(edges, med.v1, med.v2)) {
466                         DM_copy_edge_data(dm, result, i, numEdges, 1);
467                         medge[numEdges] = med;
468                         numEdges++;
469
470                         BLI_edgehash_insert(edges, med.v1, med.v2, NULL);
471                 }
472
473                 for(j = 1; j < count; j++)
474                 {
475                         vert1 = calc_mapping(indexMap, inMED.v1, j);
476                         vert2 = calc_mapping(indexMap, inMED.v2, j);
477
478                         /* edge could collapse to single point after mapping */
479                         if(vert1 == vert2) continue;
480
481                         /* XXX Unfortunately the calc_mapping returns sometimes numVerts... leads to bad crashes */
482                         if(vert1 >= numVerts)
483                                 vert1= numVerts-1;
484                         if(vert2 >= numVerts)
485                                 vert2= numVerts-1;
486
487                         /* avoid duplicate edges */
488                         if(!BLI_edgehash_haskey(edges, vert1, vert2)) {
489                                 med2 = &medge[numEdges];
490
491                                 DM_copy_edge_data(dm, result, i, numEdges, 1);
492                                 *med2 = med;
493                                 numEdges++;
494
495                                 med2->v1 = vert1;
496                                 med2->v2 = vert2;
497
498                                 BLI_edgehash_insert(edges, med2->v1, med2->v2, NULL);
499                         }
500                 }
501         }
502
503         maxFaces = dm->getNumFaces(dm);
504         mface = CDDM_get_faces(result);
505         for (i=0; i < maxFaces; i++) {
506                 MFace inMF;
507                 MFace *mf = &mface[numFaces];
508
509                 dm->getFace(dm, i, &inMF);
510
511                 DM_copy_face_data(dm, result, i, numFaces, 1);
512                 *mf = inMF;
513
514                 mf->v1 = indexMap[inMF.v1].new;
515                 mf->v2 = indexMap[inMF.v2].new;
516                 mf->v3 = indexMap[inMF.v3].new;
517                 if(inMF.v4)
518                         mf->v4 = indexMap[inMF.v4].new;
519
520                 /* if vertices are to be merged with the final copies of their
521                           * merge targets, calculate that final copy
522                 */
523                 if(indexMap[inMF.v1].merge_final)
524                         mf->v1 = calc_mapping(indexMap, indexMap[inMF.v1].merge, count-1);
525                 if(indexMap[inMF.v2].merge_final)
526                         mf->v2 = calc_mapping(indexMap, indexMap[inMF.v2].merge, count-1);
527                 if(indexMap[inMF.v3].merge_final)
528                         mf->v3 = calc_mapping(indexMap, indexMap[inMF.v3].merge, count-1);
529                 if(inMF.v4 && indexMap[inMF.v4].merge_final)
530                         mf->v4 = calc_mapping(indexMap, indexMap[inMF.v4].merge, count-1);
531
532                 if(test_index_face_maxvert(mf, &result->faceData, numFaces, inMF.v4?4:3, numVerts) < 3)
533                         continue;
534
535                 numFaces++;
536
537                 /* if the face has fewer than 3 vertices, don't create it */
538                 if(mf->v3 == 0 || (mf->v1 && (mf->v1 == mf->v3 || mf->v1 == mf->v4))) {
539                         numFaces--;
540                         DM_free_face_data(result, numFaces, 1);
541                 }
542
543                 for(j = 1; j < count; j++)
544                 {
545                         MFace *mf2 = &mface[numFaces];
546
547                         DM_copy_face_data(dm, result, i, numFaces, 1);
548                         *mf2 = *mf;
549
550                         mf2->v1 = calc_mapping(indexMap, inMF.v1, j);
551                         mf2->v2 = calc_mapping(indexMap, inMF.v2, j);
552                         mf2->v3 = calc_mapping(indexMap, inMF.v3, j);
553                         if (inMF.v4)
554                                 mf2->v4 = calc_mapping(indexMap, inMF.v4, j);
555
556                         numFaces++;
557
558                         /* if the face has fewer than 3 vertices, don't create it */
559                         if(test_index_face_maxvert(mf2, &result->faceData, numFaces-1, inMF.v4?4:3, numVerts) < 3) {
560                                 numFaces--;
561                                 DM_free_face_data(result, numFaces, 1);
562                         }
563                 }
564         }
565
566         /* add start and end caps */
567         if(start_cap) {
568                 float startoffset[4][4];
569                 MVert *cap_mvert;
570                 MEdge *cap_medge;
571                 MFace *cap_mface;
572                 int *origindex;
573                 int *vert_map;
574                 int capVerts, capEdges, capFaces;
575
576                 capVerts = start_cap->getNumVerts(start_cap);
577                 capEdges = start_cap->getNumEdges(start_cap);
578                 capFaces = start_cap->getNumFaces(start_cap);
579                 cap_mvert = start_cap->getVertArray(start_cap);
580                 cap_medge = start_cap->getEdgeArray(start_cap);
581                 cap_mface = start_cap->getFaceArray(start_cap);
582
583                 invert_m4_m4(startoffset, offset);
584
585                 vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
586                 "arrayModifier_doArray vert_map");
587
588                 origindex = result->getVertDataArray(result, CD_ORIGINDEX);
589                 for(i = 0; i < capVerts; i++) {
590                         MVert *mv = &cap_mvert[i];
591                         short merged = 0;
592
593                         if(amd->flags & MOD_ARR_MERGE) {
594                                 float tmp_co[3];
595                                 MVert *in_mv;
596                                 int j;
597
598                                 copy_v3_v3(tmp_co, mv->co);
599                                 mul_m4_v3(startoffset, tmp_co);
600
601                                 for(j = 0; j < maxVerts; j++) {
602                                         in_mv = &src_mvert[j];
603                                         /* if this vert is within merge limit, merge */
604                                         if(compare_len_v3v3(tmp_co, in_mv->co, amd->merge_dist)) {
605                                                 vert_map[i] = calc_mapping(indexMap, j, 0);
606                                                 merged = 1;
607                                                 break;
608                                         }
609                                 }
610                         }
611
612                         if(!merged) {
613                                 DM_copy_vert_data(start_cap, result, i, numVerts, 1);
614                                 mvert[numVerts] = *mv;
615                                 mul_m4_v3(startoffset, mvert[numVerts].co);
616                                 origindex[numVerts] = ORIGINDEX_NONE;
617
618                                 vert_map[i] = numVerts;
619
620                                 numVerts++;
621                         }
622                 }
623                 origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
624                 for(i = 0; i < capEdges; i++) {
625                         int v1, v2;
626
627                         v1 = vert_map[cap_medge[i].v1];
628                         v2 = vert_map[cap_medge[i].v2];
629
630                         if(!BLI_edgehash_haskey(edges, v1, v2)) {
631                                 DM_copy_edge_data(start_cap, result, i, numEdges, 1);
632                                 medge[numEdges] = cap_medge[i];
633                                 medge[numEdges].v1 = v1;
634                                 medge[numEdges].v2 = v2;
635                                 origindex[numEdges] = ORIGINDEX_NONE;
636
637                                 numEdges++;
638                         }
639                 }
640                 origindex = result->getFaceDataArray(result, CD_ORIGINDEX);
641                 for(i = 0; i < capFaces; i++) {
642                         DM_copy_face_data(start_cap, result, i, numFaces, 1);
643                         mface[numFaces] = cap_mface[i];
644                         mface[numFaces].v1 = vert_map[mface[numFaces].v1];
645                         mface[numFaces].v2 = vert_map[mface[numFaces].v2];
646                         mface[numFaces].v3 = vert_map[mface[numFaces].v3];
647                         if(mface[numFaces].v4) {
648                                 mface[numFaces].v4 = vert_map[mface[numFaces].v4];
649
650                                 test_index_face_maxvert(&mface[numFaces], &result->faceData,
651                                 numFaces, 4, numVerts);
652                         }
653                         else
654                         {
655                                 test_index_face(&mface[numFaces], &result->faceData,
656                                 numFaces, 3);
657                         }
658
659                         origindex[numFaces] = ORIGINDEX_NONE;
660
661                         numFaces++;
662                 }
663
664                 MEM_freeN(vert_map);
665                 start_cap->release(start_cap);
666         }
667
668         if(end_cap) {
669                 float endoffset[4][4];
670                 MVert *cap_mvert;
671                 MEdge *cap_medge;
672                 MFace *cap_mface;
673                 int *origindex;
674                 int *vert_map;
675                 int capVerts, capEdges, capFaces;
676
677                 capVerts = end_cap->getNumVerts(end_cap);
678                 capEdges = end_cap->getNumEdges(end_cap);
679                 capFaces = end_cap->getNumFaces(end_cap);
680                 cap_mvert = end_cap->getVertArray(end_cap);
681                 cap_medge = end_cap->getEdgeArray(end_cap);
682                 cap_mface = end_cap->getFaceArray(end_cap);
683
684                 mul_m4_m4m4(endoffset, final_offset, offset);
685
686                 vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
687                 "arrayModifier_doArray vert_map");
688
689                 origindex = result->getVertDataArray(result, CD_ORIGINDEX);
690                 for(i = 0; i < capVerts; i++) {
691                         MVert *mv = &cap_mvert[i];
692                         short merged = 0;
693
694                         if(amd->flags & MOD_ARR_MERGE) {
695                                 float tmp_co[3];
696                                 MVert *in_mv;
697                                 int j;
698
699                                 copy_v3_v3(tmp_co, mv->co);
700                                 mul_m4_v3(offset, tmp_co);
701
702                                 for(j = 0; j < maxVerts; j++) {
703                                         in_mv = &src_mvert[j];
704                                         /* if this vert is within merge limit, merge */
705                                         if(compare_len_v3v3(tmp_co, in_mv->co, amd->merge_dist)) {
706                                                 vert_map[i] = calc_mapping(indexMap, j, count - 1);
707                                                 merged = 1;
708                                                 break;
709                                         }
710                                 }
711                         }
712
713                         if(!merged) {
714                                 DM_copy_vert_data(end_cap, result, i, numVerts, 1);
715                                 mvert[numVerts] = *mv;
716                                 mul_m4_v3(endoffset, mvert[numVerts].co);
717                                 origindex[numVerts] = ORIGINDEX_NONE;
718
719                                 vert_map[i] = numVerts;
720
721                                 numVerts++;
722                         }
723                 }
724                 origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
725                 for(i = 0; i < capEdges; i++) {
726                         int v1, v2;
727
728                         v1 = vert_map[cap_medge[i].v1];
729                         v2 = vert_map[cap_medge[i].v2];
730
731                         if(!BLI_edgehash_haskey(edges, v1, v2)) {
732                                 DM_copy_edge_data(end_cap, result, i, numEdges, 1);
733                                 medge[numEdges] = cap_medge[i];
734                                 medge[numEdges].v1 = v1;
735                                 medge[numEdges].v2 = v2;
736                                 origindex[numEdges] = ORIGINDEX_NONE;
737
738                                 numEdges++;
739                         }
740                 }
741                 origindex = result->getFaceDataArray(result, CD_ORIGINDEX);
742                 for(i = 0; i < capFaces; i++) {
743                         DM_copy_face_data(end_cap, result, i, numFaces, 1);
744                         mface[numFaces] = cap_mface[i];
745                         mface[numFaces].v1 = vert_map[mface[numFaces].v1];
746                         mface[numFaces].v2 = vert_map[mface[numFaces].v2];
747                         mface[numFaces].v3 = vert_map[mface[numFaces].v3];
748                         if(mface[numFaces].v4) {
749                                 mface[numFaces].v4 = vert_map[mface[numFaces].v4];
750
751                                 test_index_face(&mface[numFaces], &result->faceData,
752                                 numFaces, 4);
753                         }
754                         else
755                         {
756                                 test_index_face(&mface[numFaces], &result->faceData,
757                                 numFaces, 3);
758                         }
759                         origindex[numFaces] = ORIGINDEX_NONE;
760
761                         numFaces++;
762                 }
763
764                 MEM_freeN(vert_map);
765                 end_cap->release(end_cap);
766         }
767
768         BLI_edgehash_free(edges, NULL);
769         MEM_freeN(indexMap);
770
771         CDDM_lower_num_verts(result, numVerts);
772         CDDM_lower_num_edges(result, numEdges);
773         CDDM_lower_num_faces(result, numFaces);
774
775         return result;
776 }
777
778 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
779                                                 DerivedMesh *dm,
780                                                 int UNUSED(useRenderParams),
781                                                 int UNUSED(isFinalCalc))
782 {
783         DerivedMesh *result;
784         ArrayModifierData *amd = (ArrayModifierData*) md;
785
786         result = arrayModifier_doArray(amd, md->scene, ob, dm, 0);
787
788         if(result != dm)
789                 CDDM_calc_normals(result);
790
791         return result;
792 }
793
794 static DerivedMesh *applyModifierEM(ModifierData *md, Object *ob,
795                                                 struct EditMesh *UNUSED(editData),
796                                                 DerivedMesh *dm)
797 {
798         return applyModifier(md, ob, dm, 0, 1);
799 }
800
801
802 ModifierTypeInfo modifierType_Array = {
803         /* name */              "Array",
804         /* structName */        "ArrayModifierData",
805         /* structSize */        sizeof(ArrayModifierData),
806         /* type */              eModifierTypeType_Constructive,
807         /* flags */             eModifierTypeFlag_AcceptsMesh
808                                                         | eModifierTypeFlag_SupportsMapping
809                                                         | eModifierTypeFlag_SupportsEditmode
810                                                         | eModifierTypeFlag_EnableInEditmode
811                                                         | eModifierTypeFlag_AcceptsCVs,
812
813         /* copyData */          copyData,
814         /* deformVerts */       NULL,
815         /* deformMatrices */    NULL,
816         /* deformVertsEM */     NULL,
817         /* deformMatricesEM */  NULL,
818         /* applyModifier */     applyModifier,
819         /* applyModifierEM */   applyModifierEM,
820         /* initData */          initData,
821         /* requiredDataMask */  NULL,
822         /* freeData */          NULL,
823         /* isDisabled */        NULL,
824         /* updateDepgraph */    updateDepgraph,
825         /* dependsOnTime */     NULL,
826         /* dependsOnNormals */  NULL,
827         /* foreachObjectLink */ foreachObjectLink,
828         /* foreachIDLink */     NULL,
829 };