SVN maintenance.
[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 #include "stddef.h"
34 #include "string.h"
35 #include "stdarg.h"
36 #include "math.h"
37 #include "float.h"
38
39 #include "BLI_kdtree.h"
40 #include "BLI_rand.h"
41 #include "BLI_uvproject.h"
42
43 #include "MEM_guardedalloc.h"
44
45 #include "DNA_armature_types.h"
46 #include "DNA_camera_types.h"
47 #include "DNA_curve_types.h"
48 #include "DNA_key_types.h"
49 #include "DNA_material_types.h"
50 #include "DNA_object_fluidsim.h"
51
52
53 #include "BKE_action.h"
54 #include "BKE_bmesh.h"
55 #include "BKE_cloth.h"
56 #include "BKE_cdderivedmesh.h"
57 #include "BKE_displist.h"
58 #include "BKE_fluidsim.h"
59 #include "BKE_global.h"
60 #include "BKE_multires.h"
61 #include "BKE_key.h"
62 #include "BKE_lattice.h"
63 #include "BKE_material.h"
64 #include "BKE_mesh.h"
65 #include "BKE_modifier.h"
66 #include "BKE_object.h"
67 #include "BKE_paint.h"
68 #include "BKE_particle.h"
69 #include "BKE_pointcache.h"
70 #include "BKE_scene.h"
71 #include "BKE_smoke.h"
72 #include "BKE_softbody.h"
73 #include "BKE_subsurf.h"
74 #include "BKE_texture.h"
75
76 #include "depsgraph_private.h"
77
78 #include "MOD_modifiertypes.h"
79
80 /* Array */
81 /* Array modifier: duplicates the object multiple times along an axis
82 */
83
84 static void initData(ModifierData *md)
85 {
86         ArrayModifierData *amd = (ArrayModifierData*) md;
87
88         /* default to 2 duplicates distributed along the x-axis by an
89         offset of 1 object-width
90         */
91         amd->start_cap = amd->end_cap = amd->curve_ob = amd->offset_ob = NULL;
92         amd->count = 2;
93         amd->offset[0] = amd->offset[1] = amd->offset[2] = 0;
94         amd->scale[0] = 1;
95         amd->scale[1] = amd->scale[2] = 0;
96         amd->length = 0;
97         amd->merge_dist = 0.01;
98         amd->fit_type = MOD_ARR_FIXEDCOUNT;
99         amd->offset_type = MOD_ARR_OFF_RELATIVE;
100         amd->flags = 0;
101 }
102
103 static void copyData(ModifierData *md, ModifierData *target)
104 {
105         ArrayModifierData *amd = (ArrayModifierData*) md;
106         ArrayModifierData *tamd = (ArrayModifierData*) target;
107
108         tamd->start_cap = amd->start_cap;
109         tamd->end_cap = amd->end_cap;
110         tamd->curve_ob = amd->curve_ob;
111         tamd->offset_ob = amd->offset_ob;
112         tamd->count = amd->count;
113         VECCOPY(tamd->offset, amd->offset);
114         VECCOPY(tamd->scale, amd->scale);
115         tamd->length = amd->length;
116         tamd->merge_dist = amd->merge_dist;
117         tamd->fit_type = amd->fit_type;
118         tamd->offset_type = amd->offset_type;
119         tamd->flags = amd->flags;
120 }
121
122 static void foreachObjectLink(
123                                                 ModifierData *md, Object *ob,
124          void (*walk)(void *userData, Object *ob, Object **obpoin),
125                 void *userData)
126 {
127         ArrayModifierData *amd = (ArrayModifierData*) md;
128
129         walk(userData, ob, &amd->start_cap);
130         walk(userData, ob, &amd->end_cap);
131         walk(userData, ob, &amd->curve_ob);
132         walk(userData, ob, &amd->offset_ob);
133 }
134
135 static void updateDepgraph(ModifierData *md, DagForest *forest, Scene *scene,
136                                          Object *ob, DagNode *obNode)
137 {
138         ArrayModifierData *amd = (ArrayModifierData*) md;
139
140         if (amd->start_cap) {
141                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
142
143                 dag_add_relation(forest, curNode, obNode,
144                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
145         }
146         if (amd->end_cap) {
147                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
148
149                 dag_add_relation(forest, curNode, obNode,
150                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
151         }
152         if (amd->curve_ob) {
153                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
154
155                 dag_add_relation(forest, curNode, obNode,
156                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
157         }
158         if (amd->offset_ob) {
159                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
160
161                 dag_add_relation(forest, curNode, obNode,
162                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
163         }
164 }
165
166 static float vertarray_size(MVert *mvert, int numVerts, int axis)
167 {
168         int i;
169         float min_co, max_co;
170
171         /* if there are no vertices, width is 0 */
172         if(numVerts == 0) return 0;
173
174         /* find the minimum and maximum coordinates on the desired axis */
175         min_co = max_co = mvert->co[axis];
176         ++mvert;
177         for(i = 1; i < numVerts; ++i, ++mvert) {
178                 if(mvert->co[axis] < min_co) min_co = mvert->co[axis];
179                 if(mvert->co[axis] > max_co) max_co = mvert->co[axis];
180         }
181
182         return max_co - min_co;
183 }
184
185 typedef struct IndexMapEntry {
186         /* the new vert index that this old vert index maps to */
187         int new;
188         /* -1 if this vert isn't merged, otherwise the old vert index it
189         * should be replaced with
190         */
191         int merge;
192         /* 1 if this vert's first copy is merged with the last copy of its
193         * merge target, otherwise 0
194         */
195         short merge_final;
196 } IndexMapEntry;
197
198 /* indexMap - an array of IndexMap entries
199  * oldIndex - the old index to map
200  * copyNum - the copy number to map to (original = 0, first copy = 1, etc.)
201  */
202 static int calc_mapping(IndexMapEntry *indexMap, int oldIndex, int copyNum)
203 {
204         if(indexMap[oldIndex].merge < 0) {
205                 /* vert wasn't merged, so use copy of this vert */
206                 return indexMap[oldIndex].new + copyNum;
207         } else if(indexMap[oldIndex].merge == oldIndex) {
208                 /* vert was merged with itself */
209                 return indexMap[oldIndex].new;
210         } else {
211                 /* vert was merged with another vert */
212                 /* follow the chain of merges to the end, or until we've passed
213                 * a number of vertices equal to the copy number
214                 */
215                 if(copyNum <= 0)
216                         return indexMap[oldIndex].new;
217                 else
218                         return calc_mapping(indexMap, indexMap[oldIndex].merge,
219                                                 copyNum - 1);
220         }
221 }
222
223 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
224                                           Scene *scene, Object *ob, DerivedMesh *dm,
225            int initFlags)
226 {
227         int i, j;
228         /* offset matrix */
229         float offset[4][4];
230         float final_offset[4][4];
231         float tmp_mat[4][4];
232         float length = amd->length;
233         int count = amd->count;
234         int numVerts, numEdges, numFaces;
235         int maxVerts, maxEdges, maxFaces;
236         int finalVerts, finalEdges, finalFaces;
237         DerivedMesh *result, *start_cap = NULL, *end_cap = NULL;
238         MVert *mvert, *src_mvert;
239         MEdge *medge;
240         MFace *mface;
241
242         IndexMapEntry *indexMap;
243
244         EdgeHash *edges;
245
246         /* need to avoid infinite recursion here */
247         if(amd->start_cap && amd->start_cap != ob)
248                 start_cap = amd->start_cap->derivedFinal;
249         if(amd->end_cap && amd->end_cap != ob)
250                 end_cap = amd->end_cap->derivedFinal;
251
252         unit_m4(offset);
253
254         indexMap = MEM_callocN(sizeof(*indexMap) * dm->getNumVerts(dm),
255                                    "indexmap");
256
257         src_mvert = dm->getVertArray(dm);
258
259         maxVerts = dm->getNumVerts(dm);
260
261         if(amd->offset_type & MOD_ARR_OFF_CONST)
262                 add_v3_v3v3(offset[3], offset[3], amd->offset);
263         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
264                 for(j = 0; j < 3; j++)
265                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
266                                         maxVerts, j);
267         }
268
269         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
270                 float obinv[4][4];
271                 float result_mat[4][4];
272
273                 if(ob)
274                         invert_m4_m4(obinv, ob->obmat);
275                 else
276                         unit_m4(obinv);
277
278                 mul_serie_m4(result_mat, offset,
279                                  obinv, amd->offset_ob->obmat,
280          NULL, NULL, NULL, NULL, NULL);
281                 copy_m4_m4(offset, result_mat);
282         }
283
284         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
285                 Curve *cu = amd->curve_ob->data;
286                 if(cu) {
287                         float tmp_mat[3][3];
288                         float scale;
289                         
290                         object_to_mat3(amd->curve_ob, tmp_mat);
291                         scale = mat3_to_scale(tmp_mat);
292                                 
293                         if(!cu->path) {
294                                 cu->flag |= CU_PATH; // needed for path & bevlist
295                                 makeDispListCurveTypes(scene, amd->curve_ob, 0);
296                         }
297                         if(cu->path)
298                                 length = scale*cu->path->totdist;
299                 }
300         }
301
302         /* calculate the maximum number of copies which will fit within the
303         prescribed length */
304         if(amd->fit_type == MOD_ARR_FITLENGTH
305                   || amd->fit_type == MOD_ARR_FITCURVE) {
306                 float dist = sqrt(dot_v3v3(offset[3], offset[3]));
307
308                 if(dist > 1e-6f)
309                         /* this gives length = first copy start to last copy end
310                         add a tiny offset for floating point rounding errors */
311                         count = (length + 1e-6f) / dist;
312                 else
313                         /* if the offset has no translation, just make one copy */
314                         count = 1;
315                   }
316
317                   if(count < 1)
318                           count = 1;
319
320         /* allocate memory for count duplicates (including original) plus
321                   * start and end caps
322         */
323                   finalVerts = dm->getNumVerts(dm) * count;
324                   finalEdges = dm->getNumEdges(dm) * count;
325                   finalFaces = dm->getNumFaces(dm) * count;
326                   if(start_cap) {
327                           finalVerts += start_cap->getNumVerts(start_cap);
328                           finalEdges += start_cap->getNumEdges(start_cap);
329                           finalFaces += start_cap->getNumFaces(start_cap);
330                   }
331                   if(end_cap) {
332                           finalVerts += end_cap->getNumVerts(end_cap);
333                           finalEdges += end_cap->getNumEdges(end_cap);
334                           finalFaces += end_cap->getNumFaces(end_cap);
335                   }
336                   result = CDDM_from_template(dm, finalVerts, finalEdges, finalFaces);
337
338                   /* calculate the offset matrix of the final copy (for merging) */ 
339                   unit_m4(final_offset);
340
341                   for(j=0; j < count - 1; j++) {
342                           mul_m4_m4m4(tmp_mat, final_offset, offset);
343                           copy_m4_m4(final_offset, tmp_mat);
344                   }
345
346                   numVerts = numEdges = numFaces = 0;
347                   mvert = CDDM_get_verts(result);
348
349                   for (i = 0; i < maxVerts; i++) {
350                           indexMap[i].merge = -1; /* default to no merge */
351                           indexMap[i].merge_final = 0; /* default to no merge */
352                   }
353
354                   for (i = 0; i < maxVerts; i++) {
355                           MVert *inMV;
356                           MVert *mv = &mvert[numVerts];
357                           MVert *mv2;
358                           float co[3];
359
360                           inMV = &src_mvert[i];
361
362                           DM_copy_vert_data(dm, result, i, numVerts, 1);
363                           *mv = *inMV;
364                           numVerts++;
365
366                           indexMap[i].new = numVerts - 1;
367
368                           VECCOPY(co, mv->co);
369                 
370                 /* Attempts to merge verts from one duplicate with verts from the
371                           * next duplicate which are closer than amd->merge_dist.
372                           * Only the first such vert pair is merged.
373                           * If verts are merged in the first duplicate pair, they are merged
374                           * in all pairs.
375                 */
376                           if((count > 1) && (amd->flags & MOD_ARR_MERGE)) {
377                                   float tmp_co[3];
378                                   VECCOPY(tmp_co, mv->co);
379                                   mul_m4_v3(offset, tmp_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                                                           VECCOPY(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                                           VECCOPY(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                           if (initFlags) {
456                                   med.flag |= ME_EDGEDRAW | ME_EDGERENDER;
457                           }
458
459                           if(!BLI_edgehash_haskey(edges, med.v1, med.v2)) {
460                                   DM_copy_edge_data(dm, result, i, numEdges, 1);
461                                   medge[numEdges] = med;
462                                   numEdges++;
463
464                                   BLI_edgehash_insert(edges, med.v1, med.v2, NULL);
465                           }
466
467                           for(j = 1; j < count; j++)
468                           {
469                                   vert1 = calc_mapping(indexMap, inMED.v1, j);
470                                   vert2 = calc_mapping(indexMap, inMED.v2, j);
471                                   /* avoid duplicate edges */
472                                   if(!BLI_edgehash_haskey(edges, vert1, vert2)) {
473                                           med2 = &medge[numEdges];
474
475                                           DM_copy_edge_data(dm, result, i, numEdges, 1);
476                                           *med2 = med;
477                                           numEdges++;
478
479                                           med2->v1 = vert1;
480                                           med2->v2 = vert2;
481
482                                           BLI_edgehash_insert(edges, med2->v1, med2->v2, NULL);
483                                   }
484                           }
485                   }
486
487                   maxFaces = dm->getNumFaces(dm);
488                   mface = CDDM_get_faces(result);
489                   for (i=0; i < maxFaces; i++) {
490                           MFace inMF;
491                           MFace *mf = &mface[numFaces];
492
493                           dm->getFace(dm, i, &inMF);
494
495                           DM_copy_face_data(dm, result, i, numFaces, 1);
496                           *mf = inMF;
497
498                           mf->v1 = indexMap[inMF.v1].new;
499                           mf->v2 = indexMap[inMF.v2].new;
500                           mf->v3 = indexMap[inMF.v3].new;
501                           if(inMF.v4)
502                                   mf->v4 = indexMap[inMF.v4].new;
503
504                 /* if vertices are to be merged with the final copies of their
505                           * merge targets, calculate that final copy
506                 */
507                           if(indexMap[inMF.v1].merge_final)
508                                   mf->v1 = calc_mapping(indexMap, indexMap[inMF.v1].merge, count-1);
509                           if(indexMap[inMF.v2].merge_final)
510                                   mf->v2 = calc_mapping(indexMap, indexMap[inMF.v2].merge, count-1);
511                           if(indexMap[inMF.v3].merge_final)
512                                   mf->v3 = calc_mapping(indexMap, indexMap[inMF.v3].merge, count-1);
513                           if(inMF.v4 && indexMap[inMF.v4].merge_final)
514                                   mf->v4 = calc_mapping(indexMap, indexMap[inMF.v4].merge, count-1);
515
516                           if(test_index_face(mf, &result->faceData, numFaces, inMF.v4?4:3) < 3)
517                                   continue;
518
519                           numFaces++;
520
521                           /* if the face has fewer than 3 vertices, don't create it */
522                           if(mf->v3 == 0 || (mf->v1 && (mf->v1 == mf->v3 || mf->v1 == mf->v4))) {
523                                   numFaces--;
524                                   DM_free_face_data(result, numFaces, 1);
525                           }
526
527                           for(j = 1; j < count; j++)
528                           {
529                                   MFace *mf2 = &mface[numFaces];
530
531                                   DM_copy_face_data(dm, result, i, numFaces, 1);
532                                   *mf2 = *mf;
533
534                                   mf2->v1 = calc_mapping(indexMap, inMF.v1, j);
535                                   mf2->v2 = calc_mapping(indexMap, inMF.v2, j);
536                                   mf2->v3 = calc_mapping(indexMap, inMF.v3, j);
537                                   if (inMF.v4)
538                                           mf2->v4 = calc_mapping(indexMap, inMF.v4, j);
539
540                                   test_index_face(mf2, &result->faceData, numFaces, inMF.v4?4:3);
541                                   numFaces++;
542
543                                   /* if the face has fewer than 3 vertices, don't create it */
544                                   if(mf2->v3 == 0 || (mf2->v1 && (mf2->v1 == mf2->v3 || mf2->v1 ==
545                                                                  mf2->v4))) {
546                                           numFaces--;
547                                           DM_free_face_data(result, numFaces, 1);
548                                                                  }
549                           }
550                   }
551
552                   /* add start and end caps */
553                   if(start_cap) {
554                           float startoffset[4][4];
555                           MVert *cap_mvert;
556                           MEdge *cap_medge;
557                           MFace *cap_mface;
558                           int *origindex;
559                           int *vert_map;
560                           int capVerts, capEdges, capFaces;
561
562                           capVerts = start_cap->getNumVerts(start_cap);
563                           capEdges = start_cap->getNumEdges(start_cap);
564                           capFaces = start_cap->getNumFaces(start_cap);
565                           cap_mvert = start_cap->getVertArray(start_cap);
566                           cap_medge = start_cap->getEdgeArray(start_cap);
567                           cap_mface = start_cap->getFaceArray(start_cap);
568
569                           invert_m4_m4(startoffset, offset);
570
571                           vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
572                                           "arrayModifier_doArray vert_map");
573
574                           origindex = result->getVertDataArray(result, CD_ORIGINDEX);
575                           for(i = 0; i < capVerts; i++) {
576                                   MVert *mv = &cap_mvert[i];
577                                   short merged = 0;
578
579                                   if(amd->flags & MOD_ARR_MERGE) {
580                                           float tmp_co[3];
581                                           MVert *in_mv;
582                                           int j;
583
584                                           VECCOPY(tmp_co, mv->co);
585                                           mul_m4_v3(startoffset, tmp_co);
586
587                                           for(j = 0; j < maxVerts; j++) {
588                                                   in_mv = &src_mvert[j];
589                                                   /* if this vert is within merge limit, merge */
590                                                   if(compare_len_v3v3(tmp_co, in_mv->co, amd->merge_dist)) {
591                                                           vert_map[i] = calc_mapping(indexMap, j, 0);
592                                                           merged = 1;
593                                                           break;
594                                                   }
595                                           }
596                                   }
597
598                                   if(!merged) {
599                                           DM_copy_vert_data(start_cap, result, i, numVerts, 1);
600                                           mvert[numVerts] = *mv;
601                                           mul_m4_v3(startoffset, mvert[numVerts].co);
602                                           origindex[numVerts] = ORIGINDEX_NONE;
603
604                                           vert_map[i] = numVerts;
605
606                                           numVerts++;
607                                   }
608                           }
609                           origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
610                           for(i = 0; i < capEdges; i++) {
611                                   int v1, v2;
612
613                                   v1 = vert_map[cap_medge[i].v1];
614                                   v2 = vert_map[cap_medge[i].v2];
615
616                                   if(!BLI_edgehash_haskey(edges, v1, v2)) {
617                                           DM_copy_edge_data(start_cap, result, i, numEdges, 1);
618                                           medge[numEdges] = cap_medge[i];
619                                           medge[numEdges].v1 = v1;
620                                           medge[numEdges].v2 = v2;
621                                           origindex[numEdges] = ORIGINDEX_NONE;
622
623                                           numEdges++;
624                                   }
625                           }
626                           origindex = result->getFaceDataArray(result, CD_ORIGINDEX);
627                           for(i = 0; i < capFaces; i++) {
628                                   DM_copy_face_data(start_cap, result, i, numFaces, 1);
629                                   mface[numFaces] = cap_mface[i];
630                                   mface[numFaces].v1 = vert_map[mface[numFaces].v1];
631                                   mface[numFaces].v2 = vert_map[mface[numFaces].v2];
632                                   mface[numFaces].v3 = vert_map[mface[numFaces].v3];
633                                   if(mface[numFaces].v4) {
634                                           mface[numFaces].v4 = vert_map[mface[numFaces].v4];
635
636                                           test_index_face(&mface[numFaces], &result->faceData,
637                                                                           numFaces, 4);
638                                   }
639                                   else
640                                   {
641                                           test_index_face(&mface[numFaces], &result->faceData,
642                                                                           numFaces, 3);
643                                   }
644
645                                   origindex[numFaces] = ORIGINDEX_NONE;
646
647                                   numFaces++;
648                           }
649
650                           MEM_freeN(vert_map);
651                           start_cap->release(start_cap);
652                   }
653
654                   if(end_cap) {
655                           float endoffset[4][4];
656                           MVert *cap_mvert;
657                           MEdge *cap_medge;
658                           MFace *cap_mface;
659                           int *origindex;
660                           int *vert_map;
661                           int capVerts, capEdges, capFaces;
662
663                           capVerts = end_cap->getNumVerts(end_cap);
664                           capEdges = end_cap->getNumEdges(end_cap);
665                           capFaces = end_cap->getNumFaces(end_cap);
666                           cap_mvert = end_cap->getVertArray(end_cap);
667                           cap_medge = end_cap->getEdgeArray(end_cap);
668                           cap_mface = end_cap->getFaceArray(end_cap);
669
670                           mul_m4_m4m4(endoffset, final_offset, offset);
671
672                           vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
673                                           "arrayModifier_doArray vert_map");
674
675                           origindex = result->getVertDataArray(result, CD_ORIGINDEX);
676                           for(i = 0; i < capVerts; i++) {
677                                   MVert *mv = &cap_mvert[i];
678                                   short merged = 0;
679
680                                   if(amd->flags & MOD_ARR_MERGE) {
681                                           float tmp_co[3];
682                                           MVert *in_mv;
683                                           int j;
684
685                                           VECCOPY(tmp_co, mv->co);
686                                           mul_m4_v3(offset, tmp_co);
687
688                                           for(j = 0; j < maxVerts; j++) {
689                                                   in_mv = &src_mvert[j];
690                                                   /* if this vert is within merge limit, merge */
691                                                   if(compare_len_v3v3(tmp_co, in_mv->co, amd->merge_dist)) {
692                                                           vert_map[i] = calc_mapping(indexMap, j, count - 1);
693                                                           merged = 1;
694                                                           break;
695                                                   }
696                                           }
697                                   }
698
699                                   if(!merged) {
700                                           DM_copy_vert_data(end_cap, result, i, numVerts, 1);
701                                           mvert[numVerts] = *mv;
702                                           mul_m4_v3(endoffset, mvert[numVerts].co);
703                                           origindex[numVerts] = ORIGINDEX_NONE;
704
705                                           vert_map[i] = numVerts;
706
707                                           numVerts++;
708                                   }
709                           }
710                           origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
711                           for(i = 0; i < capEdges; i++) {
712                                   int v1, v2;
713
714                                   v1 = vert_map[cap_medge[i].v1];
715                                   v2 = vert_map[cap_medge[i].v2];
716
717                                   if(!BLI_edgehash_haskey(edges, v1, v2)) {
718                                           DM_copy_edge_data(end_cap, result, i, numEdges, 1);
719                                           medge[numEdges] = cap_medge[i];
720                                           medge[numEdges].v1 = v1;
721                                           medge[numEdges].v2 = v2;
722                                           origindex[numEdges] = ORIGINDEX_NONE;
723
724                                           numEdges++;
725                                   }
726                           }
727                           origindex = result->getFaceDataArray(result, CD_ORIGINDEX);
728                           for(i = 0; i < capFaces; i++) {
729                                   DM_copy_face_data(end_cap, result, i, numFaces, 1);
730                                   mface[numFaces] = cap_mface[i];
731                                   mface[numFaces].v1 = vert_map[mface[numFaces].v1];
732                                   mface[numFaces].v2 = vert_map[mface[numFaces].v2];
733                                   mface[numFaces].v3 = vert_map[mface[numFaces].v3];
734                                   if(mface[numFaces].v4) {
735                                           mface[numFaces].v4 = vert_map[mface[numFaces].v4];
736
737                                           test_index_face(&mface[numFaces], &result->faceData,
738                                                                           numFaces, 4);
739                                   }
740                                   else
741                                   {
742                                           test_index_face(&mface[numFaces], &result->faceData,
743                                                                           numFaces, 3);
744                                   }
745                                   origindex[numFaces] = ORIGINDEX_NONE;
746
747                                   numFaces++;
748                           }
749
750                           MEM_freeN(vert_map);
751                           end_cap->release(end_cap);
752                   }
753
754                   BLI_edgehash_free(edges, NULL);
755                   MEM_freeN(indexMap);
756
757                   CDDM_lower_num_verts(result, numVerts);
758                   CDDM_lower_num_edges(result, numEdges);
759                   CDDM_lower_num_faces(result, numFaces);
760
761                   return result;
762 }
763
764 static DerivedMesh *applyModifier(
765                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
766   int useRenderParams, int isFinalCalc)
767 {
768         DerivedMesh *result;
769         ArrayModifierData *amd = (ArrayModifierData*) md;
770
771         result = arrayModifier_doArray(amd, md->scene, ob, derivedData, 0);
772
773         if(result != derivedData)
774                 CDDM_calc_normals(result);
775
776         return result;
777 }
778
779 static DerivedMesh *applyModifierEM(
780                 ModifierData *md, Object *ob, EditMesh *editData,
781   DerivedMesh *derivedData)
782 {
783         return applyModifier(md, ob, derivedData, 0, 1);
784 }
785
786
787 ModifierTypeInfo modifierType_Array = {
788         /* name */              "Array",
789         /* structName */        "ArrayModifierData",
790         /* structSize */        sizeof(ArrayModifierData),
791         /* type */              eModifierTypeType_Constructive,
792         /* flags */             eModifierTypeFlag_AcceptsMesh
793                                                         | eModifierTypeFlag_SupportsMapping
794                                                         | eModifierTypeFlag_SupportsEditmode
795                                                         | eModifierTypeFlag_EnableInEditmode
796                                                         | eModifierTypeFlag_AcceptsCVs,
797
798         /* copyData */          copyData,
799         /* deformVerts */       0,
800         /* deformVertsEM */     0,
801         /* deformMatricesEM */  0,
802         /* applyModifier */     applyModifier,
803         /* applyModifierEM */   applyModifierEM,
804         /* initData */          initData,
805         /* requiredDataMask */  0,
806         /* freeData */          0,
807         /* isDisabled */        0,
808         /* updateDepgraph */    updateDepgraph,
809         /* dependsOnTime */     0,
810         /* foreachObjectLink */ foreachObjectLink,
811         /* foreachIDLink */     0,
812 };