optimize mirror merging, remove array reallocation, replace with fixed size arrays.

4 files changed, 106 insertions, 75 deletions

diff --git a/source/blender/blenkernel/BKE_cdderivedmesh.h b/source/blender/blenkernel/BKE_cdderivedmesh.h
index af5e925987d..ddb36df74ca 100644
--- a/source/blender/blenkernel/BKE_cdderivedmesh.h
+++ b/source/blender/blenkernel/BKE_cdderivedmesh.h
@@ -61,7 +61,7 @@ struct DerivedMesh *CDDM_from_bmesh(struct BMesh *bm, int use_mdisps);
 DerivedMesh *CDDM_from_editbmesh(struct BMEditMesh *em, int use_mdisps, int use_tessface);
 
 /* merge verts  */
-DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap);
+DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap, const int tot_vtargetmap);
 
 /* creates a CDDerivedMesh from the given curve object */
 struct DerivedMesh *CDDM_from_curve(struct Object *ob);
diff --git a/source/blender/blenkernel/intern/cdderivedmesh.c b/source/blender/blenkernel/intern/cdderivedmesh.c
index d9dde6debc6..45dbf4cebc9 100644
--- a/source/blender/blenkernel/intern/cdderivedmesh.c
+++ b/source/blender/blenkernel/intern/cdderivedmesh.c
@@ -2308,14 +2308,18 @@ void CDDM_calc_normals_tessface(DerivedMesh *dm)
 }
 
 #if 1
-/* merge verts
+
+/**
+ * Merge Verts
  *
- * vtargetmap is a table that maps vertices to target vertices.  a value of -1
+ * \param vtargetmap  The table that maps vertices to target vertices.  a value of -1
  * indicates a vertex is a target, and is to be kept.
+ * This array is aligned with 'dm->numVertData'
  *
- * this frees dm, and returns a new one.
+ * \param tot_vtargetmap  The number of non '-1' values in vtargetmap.
+ * (not the size )
  *
- * this is a really horribly written function.  ger. - joeedh
+ * this frees dm, and returns a new one.
  *
  * note, CDDM_recalc_tessellation has to run on the returned DM if you want to access tessfaces.
  *
@@ -2324,49 +2328,66 @@ void CDDM_calc_normals_tessface(DerivedMesh *dm)
  *       of faces sharing the same set of vertices). If used elsewhere, it may
  *       be necessary to make this functionality optional.
  */
-DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap)
+DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap, const int tot_vtargetmap)
 {
 // #define USE_LOOPS
 	CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
 	CDDerivedMesh *cddm2 = NULL;
-	MVert *mv, *mvert = NULL;
-	BLI_array_declare(mvert);
-	MEdge *med, *medge = NULL;
-	BLI_array_declare(medge);
-	MPoly *mp, *mpoly = NULL;
-	BLI_array_declare(mpoly);
-	MLoop *ml, *mloop = NULL;
-	BLI_array_declare(mloop);
-	EdgeHash *ehash = BLI_edgehash_new();
-	int *newv = NULL, *newe = NULL;
-#ifdef USE_LOOPS
-	int *newl = NULL;
-#endif
-	int *oldv = NULL, *olde = NULL, *oldl = NULL, *oldp = NULL;
-	BLI_array_declare(oldv); BLI_array_declare(olde); BLI_array_declare(oldl); BLI_array_declare(oldp);
-	int i, j, c, totpoly;
-#ifdef USE_LOOPS
-	int totloop;
-#endif
 
+	const int totvert = dm->numVertData;
+	const int totedge = dm->numEdgeData;
+	const int totloop = dm->numLoopData;
+	const int totpoly = dm->numPolyData;
+
+	const int totvert_final = totvert - tot_vtargetmap;
+
+	MVert *mv, *mvert = MEM_mallocN(sizeof(*mvert) * totvert_final, __func__);
+	int *oldv         = MEM_mallocN(sizeof(*oldv)  * totvert_final, __func__);
+	int *newv         = MEM_mallocN(sizeof(*newv)  * totvert, __func__);
+	STACK_DECLARE(mvert);
+	STACK_DECLARE(oldv);
+
+	MEdge *med, *medge = MEM_mallocN(sizeof(*medge) * totedge, __func__);
+	int *olde          = MEM_mallocN(sizeof(*olde)  * totedge, __func__);
+	int *newe          = MEM_mallocN(sizeof(*newe)  * totedge, __func__);
+	STACK_DECLARE(medge);
+	STACK_DECLARE(olde);
+
+	MLoop *ml, *mloop = MEM_mallocN(sizeof(*mloop) * totloop, __func__);
+	int *oldl         = MEM_mallocN(sizeof(*oldl)  * totloop, __func__);
 #ifdef USE_LOOPS
-	totloop = dm->numLoopData;
+	int newl          = MEM_mallocN(sizeof(*newl)  * totloop, __func__);
 #endif
-	totpoly = dm->numPolyData;
+	STACK_DECLARE(mloop);
+	STACK_DECLARE(oldl);
+
+	MPoly *mp, *mpoly = MEM_mallocN(sizeof(*medge) * totpoly, __func__);
+	int *oldp         = MEM_mallocN(sizeof(*oldp)  * totpoly, __func__);
+	STACK_DECLARE(mpoly);
+	STACK_DECLARE(oldp);
+
+	EdgeHash *ehash = BLI_edgehash_new();
+
+	int i, j, c;
 	
-	newv = MEM_mallocN(sizeof(int) * dm->numVertData, "newv vtable CDDM_merge_verts");
-	newe = MEM_mallocN(sizeof(int) * dm->numEdgeData, "newv etable CDDM_merge_verts");
-#ifdef USE_LOOPS
-	newl = MEM_mallocN(sizeof(int) * totloop, "newv ltable CDDM_merge_verts");
-#endif
+	STACK_INIT(oldv);
+	STACK_INIT(olde);
+	STACK_INIT(oldl);
+	STACK_INIT(oldp);
+
+	STACK_INIT(mvert);
+	STACK_INIT(medge);
+	STACK_INIT(mloop);
+	STACK_INIT(mpoly);
+
 	/* fill newl with destination vertex indices */
 	mv = cddm->mvert;
 	c = 0;
-	for (i = 0; i < dm->numVertData; i++, mv++) {
+	for (i = 0; i < totvert; i++, mv++) {
 		if (vtargetmap[i] == -1) {
-			BLI_array_append(oldv, i);
+			STACK_PUSH(oldv, i);
+			STACK_PUSH(mvert, *mv);
 			newv[i] = c++;
-			BLI_array_append(mvert, *mv);
 		}
 		else {
 			/* dummy value */
@@ -2375,7 +2396,7 @@ DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap)
 	}
 	
 	/* now link target vertices to destination indices */
-	for (i = 0; i < dm->numVertData; i++) {
+	for (i = 0; i < totvert; i++) {
 		if (vtargetmap[i] != -1) {
 			newv[i] = newv[vtargetmap[i]];
 		}
@@ -2389,7 +2410,7 @@ DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap)
 	/* now go through and fix edges and faces */
 	med = cddm->medge;
 	c = 0;
-	for (i = 0; i < dm->numEdgeData; i++, med++) {
+	for (i = 0; i < totedge; i++, med++) {
 		
 		if (LIKELY(med->v1 != med->v2)) {
 			const unsigned int v1 = (vtargetmap[med->v1] != -1) ? vtargetmap[med->v1] : med->v1;
@@ -2400,9 +2421,9 @@ DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap)
 				newe[i] = GET_INT_FROM_POINTER(*eh_p);
 			}
 			else {
-				BLI_array_append(olde, i);
+				STACK_PUSH(olde, i);
+				STACK_PUSH(medge, *med);
 				newe[i] = c;
-				BLI_array_append(medge, *med);
 				BLI_edgehash_insert(ehash, v1, v2, SET_INT_IN_POINTER(c));
 				c++;
 			}
@@ -2414,7 +2435,7 @@ DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap)
 	
 	mp = cddm->mpoly;
 	for (i = 0; i < totpoly; i++, mp++) {
-		MPoly *mp2;
+		MPoly *mp_new;
 		
 		ml = cddm->mloop + mp->loopstart;
 
@@ -2441,10 +2462,10 @@ DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap)
 			med = cddm->medge + ml->e;
 			if (LIKELY(med->v1 != med->v2)) {
 #ifdef USE_LOOPS
-				newl[j + mp->loopstart] = BLI_array_count(mloop);
+				newl[j + mp->loopstart] = STACK_SIZE(mloop);
 #endif
-				BLI_array_append(oldl, j + mp->loopstart);
-				BLI_array_append(mloop, *ml);
+				STACK_PUSH(oldl, j + mp->loopstart);
+				STACK_PUSH(mloop, *ml);
 				c++;
 			}
 		}
@@ -2452,16 +2473,17 @@ DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap)
 		if (UNLIKELY(c == 0)) {
 			continue;
 		}
+
+		mp_new = STACK_PUSH_RET_PTR(mpoly);
+		*mp_new = *mp;
+		mp_new->totloop = c;
+		mp_new->loopstart = STACK_SIZE(mloop) - c;
 		
-		mp2 = BLI_array_append_r(mpoly, *mp);
-		mp2->totloop = c;
-		mp2->loopstart = BLI_array_count(mloop) - c;
-		
-		BLI_array_append(oldp, i);
+		STACK_PUSH(oldp, i);
 	}
 	
 	/*create new cddm*/
-	cddm2 = (CDDerivedMesh *) CDDM_from_template((DerivedMesh *)cddm, BLI_array_count(mvert), BLI_array_count(medge), 0, BLI_array_count(mloop), BLI_array_count(mpoly));
+	cddm2 = (CDDerivedMesh *) CDDM_from_template((DerivedMesh *)cddm, STACK_SIZE(mvert), STACK_SIZE(medge), 0, STACK_SIZE(mloop), STACK_SIZE(mpoly));
 	
 	/*update edge indices and copy customdata*/
 	med = medge;
@@ -2498,30 +2520,38 @@ DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap)
 	}
 	
 	/*copy over data.  CustomData_add_layer can do this, need to look it up.*/
-	memcpy(cddm2->mvert, mvert, sizeof(MVert) * BLI_array_count(mvert));
-	memcpy(cddm2->medge, medge, sizeof(MEdge) * BLI_array_count(medge));
-	memcpy(cddm2->mloop, mloop, sizeof(MLoop) * BLI_array_count(mloop));
-	memcpy(cddm2->mpoly, mpoly, sizeof(MPoly) * BLI_array_count(mpoly));
-	BLI_array_free(mvert); BLI_array_free(medge); BLI_array_free(mloop); BLI_array_free(mpoly);
-	
-	if (newv) 
-		MEM_freeN(newv); 
-	if (newe)
-		MEM_freeN(newe); 
+	memcpy(cddm2->mvert, mvert, sizeof(MVert) * STACK_SIZE(mvert));
+	memcpy(cddm2->medge, medge, sizeof(MEdge) * STACK_SIZE(medge));
+	memcpy(cddm2->mloop, mloop, sizeof(MLoop) * STACK_SIZE(mloop));
+	memcpy(cddm2->mpoly, mpoly, sizeof(MPoly) * STACK_SIZE(mpoly));
+
+	MEM_freeN(mvert);
+	MEM_freeN(medge);
+	MEM_freeN(mloop);
+	MEM_freeN(mpoly);
+
+	MEM_freeN(newv);
+	MEM_freeN(newe);
 #ifdef USE_LOOPS
-	if (newl)
-		MEM_freeN(newl);
+	MEM_freeN(newl);
 #endif
-	if (oldv) 
-		MEM_freeN(oldv); 
-	if (olde) 
-		MEM_freeN(olde); 
-	if (oldl) 
-		MEM_freeN(oldl); 
-	if (oldp) 
-		MEM_freeN(oldp);
-	if (ehash)
-		BLI_edgehash_free(ehash, NULL);
+
+	MEM_freeN(oldv);
+	MEM_freeN(olde);
+	MEM_freeN(oldl);
+	MEM_freeN(oldp);
+
+	STACK_FREE(oldv);
+	STACK_FREE(olde);
+	STACK_FREE(oldl);
+	STACK_FREE(oldp);
+
+	STACK_FREE(mvert);
+	STACK_FREE(medge);
+	STACK_FREE(mloop);
+	STACK_FREE(mpoly);
+
+	BLI_edgehash_free(ehash, NULL);
 
 	/*free old derivedmesh*/
 	dm->needsFree = 1;
diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h
index 2b86569024f..c28726e541c 100644
--- a/source/blender/blenlib/BLI_utildefines.h
+++ b/source/blender/blenlib/BLI_utildefines.h
@@ -296,6 +296,7 @@ typedef bool _BLI_Bool;
 #define STACK_SIZE(stack)      ((void)stack, (_##stack##_index))
 #define STACK_PUSH(stack, val)  (void)((stack)[(_##stack##_index)++] = val)
 #define STACK_PUSH_RET(stack)  ((void)stack, ((stack)[(_##stack##_index)++]))
+#define STACK_PUSH_RET_PTR(stack)  ((void)stack, &((stack)[(_##stack##_index)++]))
 #define STACK_POP(stack)       ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : NULL)
 #define STACK_FREE(stack)      ((void)stack)
 
diff --git a/source/blender/modifiers/intern/MOD_mirror.c b/source/blender/modifiers/intern/MOD_mirror.c
index 00c343d1918..b85ca2c1532 100644
--- a/source/blender/modifiers/intern/MOD_mirror.c
+++ b/source/blender/modifiers/intern/MOD_mirror.c
@@ -99,7 +99,7 @@ static DerivedMesh *doMirrorOnAxis(MirrorModifierData *mmd,
 {
 	const float tolerance_sq = mmd->tolerance * mmd->tolerance;
 	const int do_vtargetmap = !(mmd->flag & MOD_MIR_NO_MERGE);
-	int is_vtargetmap = FALSE; /* true when it should be used */
+	int tot_vtargetmap = 0;  /* total merge vertices */
 
 	DerivedMesh *result;
 	const int maxVerts = dm->getNumVerts(dm);
@@ -187,7 +187,7 @@ static DerivedMesh *doMirrorOnAxis(MirrorModifierData *mmd,
 			 * should be mapped for merging */
 			if (UNLIKELY(len_squared_v3v3(mv_prev->co, mv->co) < tolerance_sq)) {
 				*vtmap_a = maxVerts + i;
-				is_vtargetmap = TRUE;
+				tot_vtargetmap++;
 			}
 			else {
 				*vtmap_a = -1;
@@ -288,8 +288,8 @@ static DerivedMesh *doMirrorOnAxis(MirrorModifierData *mmd,
 	if (do_vtargetmap) {
 		/* slow - so only call if one or more merge verts are found,
 		 * users may leave this on and not realize there is nothing to merge - campbell */
-		if (is_vtargetmap) {
-			result = CDDM_merge_verts(result, vtargetmap);
+		if (tot_vtargetmap) {
+			result = CDDM_merge_verts(result, vtargetmap, tot_vtargetmap);
 		}
 		MEM_freeN(vtargetmap);
 	}