Array modifier patch by Ben Batt! (#3788)

This modifier allows to make arrays of meshes, with multiple offset types:
- constant offset
- offset relative to object width
- offset with scale and rotation based on another object

The number of duplicates can be computed based on a fixed count, fixed length
or length of a curve. Duplicate vertices can be automatically merged.

Nice docs and example files available in the wiki:
http://mediawiki.blender.org/index.php/BlenderDev/ArrayModifier

6 files changed, 794 insertions, 62 deletions

diff --git a/source/blender/blenkernel/intern/modifier.c b/source/blender/blenkernel/intern/modifier.c
index 5f3a57ce4db..39e61fd63e3 100644
--- a/source/blender/blenkernel/intern/modifier.c
+++ b/source/blender/blenkernel/intern/modifier.c
@@ -5,6 +5,7 @@
 #include "BLI_blenlib.h"
 #include "BLI_rand.h"
 #include "BLI_arithb.h"
+#include "BLI_edgehash.h"
 
 #include "MEM_guardedalloc.h"
 
@@ -16,9 +17,14 @@
 #include "DNA_object_types.h"
 #include "DNA_object_force.h"
 #include "DNA_scene_types.h"
+#include "DNA_curve_types.h"
 
 #include "BLI_editVert.h"
 
+#include "MTC_matrixops.h"
+#include "MTC_vectorops.h"
+
+#include "BKE_anim.h"
 #include "BKE_bad_level_calls.h"
 #include "BKE_global.h"
 #include "BKE_utildefines.h"
@@ -38,6 +44,77 @@
 
 #include "CCGSubSurf.h"
 
+/* helper function for modifiers - usage is of this is discouraged, but
+   avoids duplicate modifier code for DispListMesh and EditMesh */
+
+DispListMesh *displistmesh_from_editmesh(EditMesh *em)
+{
+	DispListMesh *outDLM = MEM_callocN(sizeof(*outDLM), "em_mod_dlm");
+	EditVert *eve, *preveve;
+	EditEdge *eed;
+	EditFace *efa;
+	int i;
+
+	for (i=0,eve=em->verts.first; eve; eve= eve->next)
+		eve->prev = (EditVert*) i++;
+
+	outDLM->totvert = BLI_countlist(&em->verts);
+	outDLM->totedge = BLI_countlist(&em->edges);
+	outDLM->totface = BLI_countlist(&em->faces);
+
+	outDLM->mvert = MEM_mallocN(sizeof(*outDLM->mvert)*outDLM->totvert,
+	                           "em_mod_mv");
+	outDLM->medge = MEM_mallocN(sizeof(*outDLM->medge)*outDLM->totedge,
+	                           "em_mod_med");
+	outDLM->mface = MEM_mallocN(sizeof(*outDLM->mface)*outDLM->totface,
+	                           "em_mod_mf");
+
+	/* Need to be able to mark loose edges */
+	for (eed=em->edges.first; eed; eed=eed->next) {
+		eed->f2 = 0;
+	}
+	for (efa=em->faces.first; efa; efa=efa->next) {
+		efa->e1->f2 = 1;
+		efa->e2->f2 = 1;
+		efa->e3->f2 = 1;
+		if (efa->e4) efa->e4->f2 = 1;
+	}
+
+	for (i=0,eve=em->verts.first; i<outDLM->totvert; i++,eve=eve->next) {
+		MVert *mv = &outDLM->mvert[i];
+
+		VECCOPY(mv->co, eve->co);
+		mv->mat_nr = 0;
+		mv->flag = ME_VERT_STEPINDEX;
+	}
+	for (i=0,eed=em->edges.first; i<outDLM->totedge; i++,eed=eed->next) {
+		MEdge *med = &outDLM->medge[i];
+
+		med->v1 = (int) eed->v1->prev;
+		med->v2 = (int) eed->v2->prev;
+		med->crease = (unsigned char) (eed->crease*255.0f);
+		med->flag = ME_EDGEDRAW|ME_EDGERENDER|ME_EDGE_STEPINDEX;
+		
+		if (eed->seam) med->flag |= ME_SEAM;
+		if (!eed->f2) med->flag |= ME_LOOSEEDGE;
+	}
+	for (i=0,efa=em->faces.first; i<outDLM->totface; i++,efa=efa->next) {
+		MFace *mf = &outDLM->mface[i];
+		mf->v1 = (int) efa->v1->prev;
+		mf->v2 = (int) efa->v2->prev;
+		mf->v3 = (int) efa->v3->prev;
+		mf->v4 = efa->v4?(int) efa->v4->prev:0;
+		mf->mat_nr = efa->mat_nr;
+		mf->flag = efa->flag|ME_FACE_STEPINDEX;
+		test_index_face(mf, NULL, NULL, efa->v4?4:3);
+	}
+
+	for (preveve=NULL, eve=em->verts.first; eve; preveve=eve, eve= eve->next)
+		eve->prev = preveve;
+
+	return outDLM;
+}
+
 /***/
 
 static int noneModifier_isDisabled(ModifierData *md)
@@ -452,6 +529,506 @@ static void *buildModifier_applyModifier(ModifierData *md, Object *ob, void *der
 	return derivedmesh_from_displistmesh(ndlm, NULL);
 }
 
+/* Array */
+/* Array modifier: duplicates the object multiple times along an axis
+*/
+
+static void arrayModifier_initData(ModifierData *md)
+{
+	ArrayModifierData *amd = (ArrayModifierData*) md;
+
+	/* default to 2 duplicates distributed along the x-axis by an
+	   offset of 1 object-width
+	*/
+	amd->curve_ob = amd->offset_ob = NULL;
+	amd->count = 2;
+	amd->offset[0] = amd->offset[1] = amd->offset[2] = 0;
+	amd->scale[0] = 1;
+	amd->scale[1] = amd->scale[2] = 0;
+	amd->length = 0;
+	amd->merge_dist = 0.01;
+	amd->fit_type = MOD_ARR_FIXEDCOUNT;
+	amd->offset_type = MOD_ARR_OFF_RELATIVE;
+	amd->flags = 0;
+}
+
+static void arrayModifier_copyData(ModifierData *md, ModifierData *target)
+{
+	ArrayModifierData *amd = (ArrayModifierData*) md;
+	ArrayModifierData *tamd = (ArrayModifierData*) target;
+
+	tamd->curve_ob = amd->curve_ob;
+	tamd->offset_ob = amd->offset_ob;
+	tamd->count = amd->count;
+	VECCOPY(tamd->offset, amd->offset);
+	VECCOPY(tamd->scale, amd->scale);
+	tamd->length = amd->length;
+	tamd->merge_dist = amd->merge_dist;
+	tamd->fit_type = amd->fit_type;
+	tamd->offset_type = amd->offset_type;
+	tamd->flags = amd->flags;
+}
+
+static void arrayModifier_foreachObjectLink(ModifierData *md,
+                  Object *ob,
+                  void (*walk)(void *userData, Object *ob, Object **obpoin),
+                  void *userData)
+{
+	ArrayModifierData *amd = (ArrayModifierData*) md;
+
+	walk(userData, ob, &amd->curve_ob);
+	walk(userData, ob, &amd->offset_ob);
+}
+
+static void arrayModifier_updateDepgraph(ModifierData *md,
+                                         DagForest *forest,
+                                         Object *ob,
+                                         DagNode *obNode)
+{
+	ArrayModifierData *amd = (ArrayModifierData*) md;
+
+	if (amd->curve_ob) {
+		DagNode *curNode = dag_get_node(forest, amd->curve_ob);
+
+		dag_add_relation(forest, curNode, obNode,
+		                 DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
+	}
+	if (amd->offset_ob) {
+		DagNode *curNode = dag_get_node(forest, amd->offset_ob);
+
+		dag_add_relation(forest, curNode, obNode,
+		                 DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
+	}
+}
+
+float displistmesh_width(DispListMesh *dlm, int axis)
+{
+	int i;
+	float min_co, max_co;
+	MVert *mv;
+
+	/* if there are no vertices, width is 0 */
+	if(dlm->totvert == 0) return 0;
+
+	/* find the minimum and maximum coordinates on the desired axis */
+	min_co = max_co = dlm->mvert[0].co[axis];
+	for (i=1; i < dlm->totvert; i++) {
+		mv = &dlm->mvert[i];
+
+		if(mv->co[axis] < min_co) min_co = mv->co[axis];
+		if(mv->co[axis] > max_co) max_co = mv->co[axis];
+	}
+
+	return max_co - min_co;
+}
+
+typedef struct IndexMapEntry {
+	/* the new vert index that this old vert index maps to */
+	int new;
+	/* -1 if this vert isn't merged, otherwise the old vert index it
+	 * should be replaced with
+	 */
+	int merge;
+	/* 1 if this vert's first copy is merged with the last copy of its
+	 * merge target, otherwise 0
+	 */
+	short merge_final;
+} IndexMapEntry;
+
+static int calc_mapping(IndexMapEntry *indexMap, int oldVert, int copy)
+{
+	int newVert;
+
+	if(indexMap[oldVert].merge < 0) {
+		newVert = indexMap[oldVert].new + copy + 1;
+	} else if(indexMap[oldVert].merge == oldVert) {
+		/* This vert was merged with itself */
+		newVert = indexMap[oldVert].new;
+	} else {
+		/* This vert wasn't merged with itself, so increment vert number. */
+		newVert = indexMap[indexMap[oldVert].merge].new + copy;
+	}
+
+	return newVert;
+}
+
+static DispListMesh *arrayModifier_doArray(ArrayModifierData *amd,
+                                           Object *ob, DispListMesh *inDLM,
+                                           float (*vertexCos)[3],
+                                           int initFlags)
+{
+	int i, j;
+	/* offset matrix */
+	float offset[4][4];
+	float final_offset[4][4];
+	float tmp_mat[4][4];
+	float length = amd->length;
+	int count = amd->count;
+	DispListMesh *dlm = MEM_callocN(sizeof(*dlm), "array_dlm");
+
+	IndexMapEntry *indexMap;
+
+	EdgeHash *edges;
+
+	MTC_Mat4One(offset);
+
+	if(amd->offset_type & MOD_ARR_OFF_CONST)
+		VecAddf(offset[3], offset[3], amd->offset);
+	if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
+		for(j = 0; j < 3; j++)
+			offset[3][j] += amd->scale[j] * displistmesh_width(inDLM, j);
+	}
+
+	if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
+		float obinv[4][4];
+		float result_mat[4][4];
+
+		if(ob)
+			MTC_Mat4Invert(obinv, ob->obmat);
+		else
+			MTC_Mat4One(obinv);
+
+		MTC_Mat4MulSerie(result_mat, offset,
+		                 obinv, amd->offset_ob->obmat,
+		                 NULL, NULL, NULL, NULL, NULL);
+		MTC_Mat4CpyMat4(offset, result_mat);
+	}
+
+	if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
+		Curve *cu = amd->curve_ob->data;
+		if(cu) {
+			if(!cu->path)
+				calc_curvepath(amd->curve_ob);
+
+			if(cu->path)
+				length = cu->path->totdist;
+		}
+	}
+
+	/* calculate the maximum number of copies which will fit within the
+	   prescribed length */
+	if(amd->fit_type == MOD_ARR_FITLENGTH
+	   || amd->fit_type == MOD_ARR_FITCURVE) {
+		float dist = sqrt(MTC_dot3Float(offset[3], offset[3]));
+
+		if(dist != 0)
+			/* this gives length = first copy start to last copy end
+			   add a tiny offset for floating point rounding errors */
+			count = (length + 0.00001) / dist;
+		else
+			/* if the offset has no translation, just make one copy */
+			count = 1;
+	}
+
+	if(count < 1)
+		count = 1;
+
+	dlm->totvert = dlm->totedge = dlm->totface = 0;
+	indexMap = MEM_callocN(sizeof(*indexMap)*inDLM->totvert, "indexmap");
+
+	/* allocate memory for count duplicates (including original) */
+	dlm->mvert = MEM_callocN(sizeof(*dlm->mvert)*inDLM->totvert*count,
+	                         "dlm_mvert");
+	dlm->mface = MEM_callocN(sizeof(*dlm->mface)*inDLM->totface*count,
+	                         "dlm_mface");
+
+	if (inDLM->medge)
+		dlm->medge = MEM_callocN(sizeof(*dlm->medge)*inDLM->totedge*count,
+		                         "dlm_medge");
+	if (inDLM->tface)
+		dlm->tface = MEM_callocN(sizeof(*dlm->tface)*inDLM->totface*count,
+		                         "dlm_tface");
+	if (inDLM->mcol)
+		dlm->mcol = MEM_callocN(sizeof(*dlm->mcol)*inDLM->totface*4*count,
+		                        "dlm_mcol");
+
+	/* calculate the offset matrix of the final copy (for merging) */ 
+	MTC_Mat4One(final_offset);
+
+	for(j=0; j < count - 1; j++) {
+		MTC_Mat4MulMat4(tmp_mat, final_offset, offset);
+		MTC_Mat4CpyMat4(final_offset, tmp_mat);
+	}
+
+	for (i=0; i<inDLM->totvert; i++) {
+		MVert *inMV = &inDLM->mvert[i];
+		MVert *mv = &dlm->mvert[dlm->totvert++];
+		MVert *mv2;
+		float co[3];
+
+		*mv = *inMV;
+
+		if (vertexCos) {
+			VECCOPY(mv->co, vertexCos[i]);
+		}
+		if (initFlags) mv->flag |= ME_VERT_STEPINDEX;
+
+		indexMap[i].new = dlm->totvert-1;
+		indexMap[i].merge = -1; /* default to no merge */
+		indexMap[i].merge_final = 0; /* default to no merge */
+
+		VECCOPY(co, mv->co);
+		
+		/* Attempts to merge verts from one duplicate with verts from the
+		 * next duplicate which are closer than amd->merge_dist.
+		 * Only the first such vert pair is merged.
+		 * If verts are merged in the first duplicate pair, they are merged
+		 * in all pairs.
+		 */
+		if((count > 1) && (amd->flags & MOD_ARR_MERGE)) {
+			float tmp_co[3];
+			VECCOPY(tmp_co, mv->co);
+			MTC_Mat4MulVecfl(offset, tmp_co);
+
+			for(j = 0; j < inDLM->totvert; j++) {
+				inMV = &inDLM->mvert[j];
+				/* if this vert is within merge limit, merge */
+				if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist)) {
+					indexMap[i].merge = j;
+
+					/* test for merging with final copy of merge target */
+					if(amd->flags & MOD_ARR_MERGEFINAL) {
+						inMV = &inDLM->mvert[i];
+						VECCOPY(tmp_co, inDLM->mvert[j].co);
+						MTC_Mat4MulVecfl(final_offset, tmp_co);
+						if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist))
+							indexMap[i].merge_final = 1;
+					}
+					break;
+				}
+			}
+		}
+
+		/* if no merging, generate copies of this vert */
+		if(indexMap[i].merge < 0) {
+			for(j=0; j < count - 1; j++) {
+				mv2 = &dlm->mvert[dlm->totvert++];
+
+				*mv2 = *mv;
+				MTC_Mat4MulVecfl(offset, co);
+				VECCOPY(mv2->co, co);
+				mv2->flag &= ~ME_VERT_STEPINDEX;
+			}
+		} else if(indexMap[i].merge != i && indexMap[i].merge_final) {
+			/* if this vert is not merging with itself, and it is merging
+			 * with the final copy of its merge target, remove the first copy
+			 */
+			dlm->totvert--;
+		}
+	}
+
+	/* make a hashtable so we can avoid duplicate edges from merging */
+	edges = BLI_edgehash_new();
+
+	for (i=0; i<inDLM->totedge; i++) {
+		MEdge *inMED = &inDLM->medge[i];
+		MEdge med;
+		MEdge *med2;
+		int vert1, vert2;
+
+		med = *inMED;
+		med.v1 = indexMap[inMED->v1].new;
+		med.v2 = indexMap[inMED->v2].new;
+
+		/* if vertices are to be merged with the final copies of their
+		 * merge targets, calculate that final copy
+		 */
+		if(indexMap[inMED->v1].merge_final) {
+			med.v1 = calc_mapping(indexMap, indexMap[inMED->v1].merge,
+			                      count - 2);
+		}
+		if(indexMap[inMED->v2].merge_final) {
+			med.v2 = calc_mapping(indexMap, indexMap[inMED->v2].merge,
+			                      count - 2);
+		}
+
+		if (initFlags) {
+			med.flag |= ME_EDGEDRAW|ME_EDGERENDER|ME_EDGE_STEPINDEX;
+		}
+
+		if(!BLI_edgehash_haskey(edges, med.v1, med.v2)) {
+			dlm->medge[dlm->totedge++] = med;
+			BLI_edgehash_insert(edges, med.v1, med.v2, NULL);
+		}
+
+		for(j=0; j < count - 1; j++)
+		{
+			vert1 = calc_mapping(indexMap, inMED->v1, j);
+			vert2 = calc_mapping(indexMap, inMED->v2, j);
+			/* avoid duplicate edges */
+			if(!BLI_edgehash_haskey(edges, vert1, vert2)) {
+				med2 = &dlm->medge[dlm->totedge++];
+
+				*med2 = med;
+				med2->v1 = vert1;
+				med2->v2 = vert2;
+				med2->flag &= ~ME_EDGE_STEPINDEX;
+
+				BLI_edgehash_insert(edges, med2->v1, med2->v2, NULL);
+			}
+		}
+	}
+
+	/* don't need the hashtable any more */
+	BLI_edgehash_free(edges, NULL);
+
+	for (i=0; i<inDLM->totface; i++) {
+		MFace *inMF = &inDLM->mface[i];
+		MFace *mf = &dlm->mface[dlm->totface++];
+		MFace *mf2;
+		TFace *tf = NULL;
+		MCol *mc = NULL;
+
+		*mf = *inMF;
+		mf->v1 = indexMap[inMF->v1].new;
+		mf->v2 = indexMap[inMF->v2].new;
+		mf->v3 = indexMap[inMF->v3].new;
+		mf->v4 = indexMap[inMF->v4].new;
+
+		/* if vertices are to be merged with the final copies of their
+		 * merge targets, calculate that final copy
+		 */
+		if(indexMap[inMF->v1].merge_final)
+			mf->v1 = calc_mapping(indexMap, indexMap[inMF->v1].merge, count-2);
+		if(indexMap[inMF->v2].merge_final)
+			mf->v2 = calc_mapping(indexMap, indexMap[inMF->v2].merge, count-2);
+		if(indexMap[inMF->v3].merge_final)
+			mf->v3 = calc_mapping(indexMap, indexMap[inMF->v3].merge, count-2);
+		if(indexMap[inMF->v4].merge_final)
+			mf->v4 = calc_mapping(indexMap, indexMap[inMF->v4].merge, count-2);
+
+		if (initFlags) mf->flag |= ME_FACE_STEPINDEX;
+
+		if (inDLM->tface) {
+			TFace *inTF = &inDLM->tface[i];
+			TFace *tf = &dlm->tface[dlm->totface-1];
+
+			*tf = *inTF;
+		} else if (inDLM->mcol) {
+			MCol *inMC = &inDLM->mcol[i*4];
+			MCol *mc = &dlm->mcol[(dlm->totface-1)*4];
+
+			mc[0] = inMC[0];
+			mc[1] = inMC[1];
+			mc[2] = inMC[2];
+			mc[3] = inMC[3];
+		}
+		
+		for(j=0; j < count - 1; j++)
+		{
+			mf2 = &dlm->mface[dlm->totface++];
+
+			*mf2 = *mf;
+
+			mf2->v1 = calc_mapping(indexMap, inMF->v1, j);
+			mf2->v2 = calc_mapping(indexMap, inMF->v2, j);
+			mf2->v3 = calc_mapping(indexMap, inMF->v3, j);
+			if (inMF->v4)
+				mf2->v4 = calc_mapping(indexMap, inMF->v4, j);
+
+			mf2->flag &= ~ME_FACE_STEPINDEX;
+
+			if (inDLM->tface) {
+				TFace *inTF = &inDLM->tface[i];
+				tf = &dlm->tface[dlm->totface-1];
+
+				*tf = *inTF;
+			} else if (inDLM->mcol) {
+				MCol *inMC = &inDLM->mcol[i*4];
+				mc = &dlm->mcol[(dlm->totface-1)*4];
+
+				mc[0] = inMC[0];
+				mc[1] = inMC[1];
+				mc[2] = inMC[2];
+				mc[3] = inMC[3];
+			}
+
+			test_index_face(mf2, mc, tf, inMF->v4?4:3);
+
+			/* if the face has fewer than 3 vertices, don't create it */
+			if(mf2->v3 == 0)
+				dlm->totface--;
+		}
+	}
+
+	MEM_freeN(indexMap);
+
+	return dlm;
+}
+
+static void *arrayModifier_applyModifier_internal(ModifierData *md,
+                                                  Object *ob,
+                                                  void *derivedData,
+                                                  float (*vertexCos)[3],
+                                                  int useRenderParams,
+                                                  int isFinalCalc)
+{
+	DerivedMesh *dm = derivedData;
+	ArrayModifierData *amd = (ArrayModifierData*) md;
+	DispListMesh *outDLM, *inDLM;
+
+	if (dm) {
+		inDLM = dm->convertToDispListMesh(dm, 1);
+	} else {
+		Mesh *me = ob->data;
+
+		inDLM = MEM_callocN(sizeof(*inDLM), "inDLM");
+		inDLM->dontFreeVerts = inDLM->dontFreeOther = 1;
+		inDLM->mvert = me->mvert;
+		inDLM->medge = me->medge;
+		inDLM->mface = me->mface;
+		inDLM->tface = me->tface;
+		inDLM->mcol = me->mcol;
+		inDLM->totvert = me->totvert;
+		inDLM->totedge = me->totedge;
+		inDLM->totface = me->totface;
+	}
+
+	outDLM = arrayModifier_doArray(amd, ob, inDLM, vertexCos, dm?0:1);
+
+	displistmesh_free(inDLM);
+	
+	mesh_calc_normals(outDLM->mvert, outDLM->totvert, outDLM->mface,
+	                  outDLM->totface, &outDLM->nors);
+
+	return derivedmesh_from_displistmesh(outDLM, NULL);
+}
+
+static void *arrayModifier_applyModifier(ModifierData *md,
+                                         Object *ob,
+                                         void *derivedData,
+                                         float (*vertexCos)[3],
+                                         int useRenderParams,
+                                         int isFinalCalc)
+{
+	return arrayModifier_applyModifier_internal(md, ob, derivedData,
+	                                            vertexCos, 0, 1);
+}
+
+static void *arrayModifier_applyModifierEM(ModifierData *md,
+                                           Object *ob,
+                                           void *editData,
+                                           void *derivedData,
+                                           float (*vertexCos)[3])
+{
+	if (derivedData) {
+		return arrayModifier_applyModifier_internal(md, ob, derivedData,
+		                                            vertexCos, 0, 1);
+	} else {
+		ArrayModifierData *amd = (ArrayModifierData*) md;
+		DispListMesh *outDLM, *inDLM = displistmesh_from_editmesh(editData);
+
+		outDLM = arrayModifier_doArray(amd, ob, inDLM, vertexCos, 0);
+
+		displistmesh_free(inDLM);
+
+		mesh_calc_normals(outDLM->mvert, outDLM->totvert,
+		                  outDLM->mface, outDLM->totface, &outDLM->nors);
+
+		return derivedmesh_from_displistmesh(outDLM, NULL);
+	}
+}
+
 /* Mirror */
 
 static void mirrorModifier_initData(ModifierData *md)
@@ -649,72 +1226,13 @@ static void *mirrorModifier_applyModifierEM(ModifierData *md, Object *ob, void *
 	if (derivedData) {
 		return mirrorModifier_applyModifier__internal(md, ob, derivedData, vertexCos, 0, 1);
 	} else {
+		DispListMesh *inDLM, *outDLM;
 		MirrorModifierData *mmd = (MirrorModifierData*) md;
-		DispListMesh *outDLM, *inDLM = MEM_callocN(sizeof(*inDLM), "mm_dlm");
-		EditMesh *em = editData;
-		EditVert *eve, *preveve;
-		EditEdge *eed;
-		EditFace *efa;
-		int i;
-
-		for (i=0,eve=em->verts.first; eve; eve= eve->next)
-			eve->prev = (EditVert*) i++;
-
-		inDLM->totvert = BLI_countlist(&em->verts);
-		inDLM->totedge = BLI_countlist(&em->edges);
-		inDLM->totface = BLI_countlist(&em->faces);
-
-		inDLM->mvert = MEM_mallocN(sizeof(*inDLM->mvert)*inDLM->totvert*2, "mm_mv");
-		inDLM->medge = MEM_mallocN(sizeof(*inDLM->medge)*inDLM->totedge*2, "mm_med");
-		inDLM->mface = MEM_mallocN(sizeof(*inDLM->mface)*inDLM->totface*2, "mm_mf");
-
-			/* Need to be able to mark loose edges */
-		for (eed=em->edges.first; eed; eed=eed->next) {
-			eed->f2 = 0;
-		}
-		for (efa=em->faces.first; efa; efa=efa->next) {
-			efa->e1->f2 = 1;
-			efa->e2->f2 = 1;
-			efa->e3->f2 = 1;
-			if (efa->e4) efa->e4->f2 = 1;
-		}
-
-		for (i=0,eve=em->verts.first; i<inDLM->totvert; i++,eve=eve->next) {
-			MVert *mv = &inDLM->mvert[i];
-
-			VECCOPY(mv->co, eve->co);
-			mv->mat_nr = 0;
-			mv->flag = ME_VERT_STEPINDEX;
-		}
-		for (i=0,eed=em->edges.first; i<inDLM->totedge; i++,eed=eed->next) {
-			MEdge *med = &inDLM->medge[i];
-
-			med->v1 = (int) eed->v1->prev;
-			med->v2 = (int) eed->v2->prev;
-			med->crease = (unsigned char) (eed->crease*255.0f);
-			med->flag = ME_EDGEDRAW|ME_EDGERENDER|ME_EDGE_STEPINDEX;
-			
-			if (eed->seam) med->flag |= ME_SEAM;
-			if (!eed->f2) med->flag |= ME_LOOSEEDGE;
-		}
-		for (i=0,efa=em->faces.first; i<inDLM->totface; i++,efa=efa->next) {
-			MFace *mf = &inDLM->mface[i];
-			mf->v1 = (int) efa->v1->prev;
-			mf->v2 = (int) efa->v2->prev;
-			mf->v3 = (int) efa->v3->prev;
-			mf->v4 = efa->v4?(int) efa->v4->prev:0;
-			mf->mat_nr = efa->mat_nr;
-			mf->flag = efa->flag|ME_FACE_STEPINDEX;
-			test_index_face(mf, NULL, NULL, efa->v4?4:3);
-		}
-
+		
+		inDLM = displistmesh_from_editmesh((EditMesh*)editData);
 		outDLM = mirrorModifier__doMirror(mmd, inDLM, vertexCos, 0);
-
 		displistmesh_free(inDLM);
 
-		for (preveve=NULL, eve=em->verts.first; eve; preveve=eve, eve= eve->next)
-			eve->prev = preveve;
-
 		mesh_calc_normals(outDLM->mvert, outDLM->totvert, outDLM->mface, outDLM->totface, &outDLM->nors);
 
 		return derivedmesh_from_displistmesh(outDLM, NULL);
@@ -1291,6 +1809,19 @@ ModifierTypeInfo *modifierType_getInfo(ModifierType type)
 		mti->dependsOnTime = buildModifier_dependsOnTime;
 		mti->applyModifier = buildModifier_applyModifier;
 
+		mti = INIT_TYPE(Array);
+		mti->type = eModifierTypeType_Constructive;
+		mti->flags = eModifierTypeFlag_AcceptsMesh
+		             | eModifierTypeFlag_SupportsMapping
+		             | eModifierTypeFlag_SupportsEditmode
+		             | eModifierTypeFlag_EnableInEditmode;
+		mti->initData = arrayModifier_initData;
+		mti->copyData = arrayModifier_copyData;
+		mti->foreachObjectLink = arrayModifier_foreachObjectLink;
+		mti->updateDepgraph = arrayModifier_updateDepgraph;
+		mti->applyModifier = arrayModifier_applyModifier;
+		mti->applyModifierEM = arrayModifier_applyModifierEM;
+
 		mti = INIT_TYPE(Mirror);
 		mti->type = eModifierTypeType_Constructive;
 		mti->flags = eModifierTypeFlag_AcceptsMesh | eModifierTypeFlag_SupportsMapping | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_EnableInEditmode;
diff --git a/source/blender/blenlib/BLI_arithb.h b/source/blender/blenlib/BLI_arithb.h
index fedcefcd8b8..fcb72f7d8f0 100644
--- a/source/blender/blenlib/BLI_arithb.h
+++ b/source/blender/blenlib/BLI_arithb.h
@@ -490,6 +490,12 @@ VecMulf(
 	float *v1, 
 	float f
 );
+	int
+VecLenCompare(
+	float *v1,
+	float *v2,
+	float limit
+);
 	int 
 VecCompare(
 	float *v1, 
diff --git a/source/blender/blenlib/intern/arithb.c b/source/blender/blenlib/intern/arithb.c
index 0cc98a3b429..67f3cca92f3 100644
--- a/source/blender/blenlib/intern/arithb.c
+++ b/source/blender/blenlib/intern/arithb.c
@@ -1814,6 +1814,17 @@ void VecMulf(float *v1, float f)
 	v1[2]*= f;
 }
 
+int VecLenCompare(float *v1, float *v2, float limit)
+{
+    float x,y,z;
+
+	x=v1[0]-v2[0];
+	y=v1[1]-v2[1];
+	z=v1[2]-v2[2];
+
+	return ((x*x + y*y + z*z) < (limit*limit));
+}
+
 int VecCompare( float *v1, float *v2, float limit)
 {
 	if( fabs(v1[0]-v2[0])<limit )
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index 5f34c1af3dc..cfd3e4a195f 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -5859,6 +5859,12 @@ static void expand_modifier(FileData *fd, Main *mainvar, ModifierData *md)
 			
 		expand_doit(fd, mainvar, cmd->object);
 	}
+	else if (md->type==eModifierType_Array) {
+		ArrayModifierData *amd = (ArrayModifierData*) md;
+			
+		expand_doit(fd, mainvar, amd->curve_ob);
+		expand_doit(fd, mainvar, amd->offset_ob);
+	}
 }
 
 static void expand_object(FileData *fd, Main *mainvar, Object *ob)
diff --git a/source/blender/makesdna/DNA_modifier_types.h b/source/blender/makesdna/DNA_modifier_types.h
index 19128bd0286..5bc4015eb96 100644
--- a/source/blender/makesdna/DNA_modifier_types.h
+++ b/source/blender/makesdna/DNA_modifier_types.h
@@ -18,6 +18,7 @@ typedef enum ModifierType {
 	eModifierType_Hook,
 	eModifierType_Softbody,
 	eModifierType_Boolean,
+	eModifierType_Array,
 
 	NUM_MODIFIER_TYPES
 } ModifierType;
@@ -80,6 +81,60 @@ typedef struct BuildModifierData {
 	int randomize, seed;
 } BuildModifierData;
 
+typedef struct ArrayModifierData {
+	ModifierData modifier;
+
+	/* the curve object to use for MOD_ARR_FITCURVE */
+	struct Object *curve_ob;
+	/* the object to use for object offset */
+	struct Object *offset_ob;
+	/* a constant duplicate offset;
+	   1 means the duplicates are 1 unit apart
+    */
+	float offset[3];
+	/* a scaled factor for duplicate offsets;
+	   1 means the duplicates are 1 object-width apart
+    */
+	float scale[3];
+	/* the length over which to distribute the duplicates */
+	float length;
+	/* the limit below which to merge vertices in adjacent duplicates */
+	float merge_dist;
+	/* determines how duplicate count is calculated; one of:
+	      MOD_ARR_FIXEDCOUNT -> fixed
+	      MOD_ARR_FITLENGTH  -> calculated to fit a set length
+	      MOD_ARR_FITCURVE   -> calculated to fit the length of a Curve object
+    */
+	int fit_type;
+	/* flags specifying how total offset is calculated; binary OR of:
+	     MOD_ARR_OFF_CONST    -> total offset += offset
+	     MOD_ARR_OFF_RELATIVE -> total offset += relative * object width
+	     MOD_ARR_OFF_OBJ      -> total offset += offset_ob's matrix
+	   total offset is the sum of the individual enabled offsets
+	*/
+	int offset_type;
+	/* general flags:
+	      MOD_ARR_MERGE -> merge vertices in adjacent duplicates
+	*/
+	int flags;
+	/* the number of duplicates to generate for MOD_ARR_FIXEDCOUNT */
+	int count;
+} ArrayModifierData;
+
+/* ArrayModifierData->fit_type */
+#define MOD_ARR_FIXEDCOUNT 0
+#define MOD_ARR_FITLENGTH  1
+#define MOD_ARR_FITCURVE   2
+
+/* ArrayModifierData->offset_type */
+#define MOD_ARR_OFF_CONST    1<<0
+#define MOD_ARR_OFF_RELATIVE 1<<1
+#define MOD_ARR_OFF_OBJ      1<<2
+
+/* ArrayModifierData->flags */
+#define MOD_ARR_MERGE      1<<0
+#define MOD_ARR_MERGEFINAL 1<<1
+
 typedef struct MirrorModifierData {
 	ModifierData modifier;
 
diff --git a/source/blender/src/buttons_editing.c b/source/blender/src/buttons_editing.c
index cc8dfabb843..75bafb49b60 100644
--- a/source/blender/src/buttons_editing.c
+++ b/source/blender/src/buttons_editing.c
@@ -1236,6 +1236,8 @@ static void draw_modifier(uiBlock *block, Object *ob, ModifierData *md, int *xco
 			height = 26;
 		} else if (md->type==eModifierType_Boolean) {
 			height = 46;
+		} else if (md->type==eModifierType_Array) {
+			height = 186;
 		}
 
 							/* roundbox 4 free variables: corner-rounding, nop, roundbox type, shade */
@@ -1352,6 +1354,127 @@ static void draw_modifier(uiBlock *block, Object *ob, ModifierData *md, int *xco
 			BooleanModifierData *bmd = (BooleanModifierData*) md;
 			uiDefButI(block, MENU, B_MODIFIER_RECALC, "Operation%t|Intersect%x0|Union%x1|Difference%x2",	lx,(cy-=19),buttonWidth,19, &bmd->operation, 0.0, 1.0, 0, 0, "Boolean operation to perform");
 			uiDefIDPoinBut(block, modifier_testMeshObj, ID_OB, B_CHANGEDEP, "Ob: ", lx, (cy-=19), buttonWidth,19, &bmd->object, "Mesh object to use for boolean operation");
+		} else if (md->type==eModifierType_Array) {
+			ArrayModifierData *amd = (ArrayModifierData*) md;
+			float range = 10000;
+			int cytop, halfwidth = (width - 5)/2 - 15;
+			int halflx = lx + halfwidth + 10;
+
+			uiBlockSetEmboss(block, UI_EMBOSSX);
+			uiBlockEndAlign(block);
+
+			/* length parameters */
+			uiBlockBeginAlign(block);
+			sprintf(str, "Length Fit%%t|Fixed Count%%x%d|Fixed Length%%x%d"
+			        "|Fit To Curve Length%%x%d",
+			        MOD_ARR_FIXEDCOUNT, MOD_ARR_FITLENGTH, MOD_ARR_FITCURVE);
+			uiDefButI(block, MENU, B_MODIFIER_RECALC, str,
+			          lx, (cy-=19), buttonWidth, 19, &amd->fit_type,
+			          0.0, 1.0, 0, 0, "Array length calculation method");
+			switch(amd->fit_type)
+			{
+			case MOD_ARR_FIXEDCOUNT:
+				uiDefButI(block, NUM, B_MODIFIER_RECALC, "Count:",
+				          lx, (cy -= 19), buttonWidth, 19, &amd->count,
+				          1, 1000, 0, 0, "Number of duplicates to make");
+				break;
+			case MOD_ARR_FITLENGTH:
+				uiDefButF(block, NUM, B_MODIFIER_RECALC, "Length:",
+				          lx, (cy -= 19), buttonWidth, 19, &amd->length,
+				          0, range, 10, 2,
+				          "Length to fit array within");
+				break;
+			case MOD_ARR_FITCURVE:
+				uiDefIDPoinBut(block, modifier_testCurveObj, ID_OB,
+				               B_CHANGEDEP, "Ob: ",
+				               lx, (cy -= 19), buttonWidth, 19, &amd->curve_ob,
+				               "Curve object to fit array length to");
+				break;
+			}
+			uiBlockEndAlign(block);
+
+			/* offset parameters */
+			cy -= 10;
+			cytop= cy;
+			uiBlockBeginAlign(block);
+			uiDefButBitI(block, TOG, MOD_ARR_OFF_CONST, B_MODIFIER_RECALC,
+			             "Constant Offset", lx, (cy-=19), halfwidth, 19,
+			             &amd->offset_type, 0, 0, 0, 0,
+			             "Constant offset between duplicates");
+			uiDefButF(block, NUM, B_MODIFIER_RECALC, "X:",
+			          lx, (cy-=19), halfwidth, 19,
+			          &amd->offset[0],
+			          -range, range, 10, 3,
+			          "Constant component for duplicate offsets");
+			uiDefButF(block, NUM, B_MODIFIER_RECALC, "Y:",
+			          lx, (cy-=19), halfwidth, 19,
+			          &amd->offset[1],
+			          -range, range, 10, 3,
+			          "Constant component for duplicate offsets");
+			uiDefButF(block, NUM, B_MODIFIER_RECALC, "Z:",
+			          lx, (cy-=19), halfwidth, 19,
+			          &amd->offset[2],
+			          -range, range, 10, 3,
+			          "Constant component for duplicate offsets");
+			uiBlockEndAlign(block);
+
+			cy= cytop;
+			uiBlockBeginAlign(block);
+			uiDefButBitI(block, TOG, MOD_ARR_OFF_RELATIVE, B_MODIFIER_RECALC,
+			             "Relative Offset", halflx, (cy-=19), halfwidth, 19,
+			             &amd->offset_type, 0, 0, 0, 0,
+			             "Offset between duplicates relative to object width");
+			uiDefButF(block, NUM, B_MODIFIER_RECALC, "X:",
+			          halflx, (cy-=19), halfwidth, 19,
+			          &amd->scale[0],
+			          -range, range, 10, 3,
+			          "Component for duplicate offsets relative to object width");
+			uiDefButF(block, NUM, B_MODIFIER_RECALC, "Y:",
+			          halflx, (cy-=19), halfwidth, 19,
+			          &amd->scale[1],
+			          -range, range, 10, 3,
+			          "Component for duplicate offsets relative to object width");
+			uiDefButF(block, NUM, B_MODIFIER_RECALC, "Z:",
+			          halflx, (cy-=19), halfwidth, 19,
+			          &amd->scale[2],
+			          -range, range, 10, 3,
+			          "Component for duplicate offsets relative to object width");
+			uiBlockEndAlign(block);
+
+			/* vertex merging parameters */
+			cy -= 10;
+			cytop= cy;
+
+			uiBlockBeginAlign(block);
+			uiDefButBitI(block, TOG, MOD_ARR_MERGE, B_MODIFIER_RECALC,
+			             "Merge",
+			             lx, (cy-=19), halfwidth/2, 19, &amd->flags,
+			             0, 0, 0, 0,
+			             "Merge vertices in adjacent duplicates");
+			uiDefButBitI(block, TOG, MOD_ARR_MERGEFINAL, B_MODIFIER_RECALC,
+			             "First Last",
+			             lx + halfwidth/2, cy, (halfwidth+1)/2, 19,
+			             &amd->flags,
+			             0, 0, 0, 0,
+			             "Merge vertices in first duplicate with vertices"
+			             " in last duplicate");
+			uiDefButF(block, NUM, B_MODIFIER_RECALC, "Limit:",
+					  lx, (cy-=19), halfwidth, 19, &amd->merge_dist,
+					  0, 1.0f, 1, 4,
+					  "Limit below which to merge vertices");
+
+			/* offset ob */
+			cy = cytop;
+			uiBlockBeginAlign(block);
+			uiDefButBitI(block, TOG, MOD_ARR_OFF_OBJ, B_MODIFIER_RECALC,
+			             "Object Offset", halflx, (cy -= 19), halfwidth, 19,
+			             &amd->offset_type, 0, 0, 0, 0,
+			             "Add an object transformation to the total offset");
+			uiDefIDPoinBut(block, test_obpoin_but, ID_OB, B_CHANGEDEP,
+			               "Ob: ", halflx, (cy -= 19), halfwidth, 19,
+			               &amd->offset_ob,
+			               "Object from which to take offset transformation");
+			uiBlockEndAlign(block);
 		}
 		uiBlockEndAlign(block);