Added merge option to shrinkwrap when using projection mode (bruteforce for now)

Changed code to remove faces (now quad faces that got one vertice projected are turned on tri)

Merge option is still not very usefull since shrinkwrap does not yet moves unprojected vertices

5 files changed, 150 insertions, 19 deletions

diff --git a/source/blender/blenkernel/BKE_shrinkwrap.h b/source/blender/blenkernel/BKE_shrinkwrap.h
index babdcd78261..3eb0b6fa579 100644
--- a/source/blender/blenkernel/BKE_shrinkwrap.h
+++ b/source/blender/blenkernel/BKE_shrinkwrap.h
@@ -39,6 +39,8 @@ typedef char* BitSet;
 
 #define bitset_get(set,index)	((set)[(index)>>3] & (1 << ((index)&0x7)))
 #define bitset_set(set,index)	((set)[(index)>>3] |= (1 << ((index)&0x7)))
+#define bitset_unset(set,index)	((set)[(index)>>3] &= ~(1 << ((index)&0x7)))
+
 
 
 struct Object;
diff --git a/source/blender/blenkernel/intern/modifier.c b/source/blender/blenkernel/intern/modifier.c
index 63d2da31b20..cd65aace158 100644
--- a/source/blender/blenkernel/intern/modifier.c
+++ b/source/blender/blenkernel/intern/modifier.c
@@ -7021,6 +7021,7 @@ static void shrinkwrapModifier_initData(ModifierData *md)
 	smd->shrinkType = MOD_SHRINKWRAP_NEAREST_SURFACE;
 	smd->shrinkOpts = MOD_SHRINKWRAP_ALLOW_DEFAULT_NORMAL;
 	smd->keptDist	= 0.0f;
+	smd->mergeDist	= 0.0f;
 }
 
 static void shrinkwrapModifier_copyData(ModifierData *md, ModifierData *target)
diff --git a/source/blender/blenkernel/intern/shrinkwrap.c b/source/blender/blenkernel/intern/shrinkwrap.c
index 14ed29d0583..893cff3dd25 100644
--- a/source/blender/blenkernel/intern/shrinkwrap.c
+++ b/source/blender/blenkernel/intern/shrinkwrap.c
@@ -29,6 +29,7 @@
 #include <string.h>
 #include <float.h>
 #include <math.h>
+#include <memory.h>
 #include <stdio.h>
 #include <time.h>
 
@@ -58,7 +59,7 @@
 #define OUT_OF_MEMORY()	((void)printf("Shrinkwrap: Out of memory\n"))
 
 /* Benchmark macros */
-#if 1
+#if 0
 
 #define BENCH(a)	\
 	do {			\
@@ -323,6 +324,82 @@ static float squared_dist(const float *a, const float *b)
 }
 
 /*
+ *
+ */
+static void derivedmesh_mergeNearestPoints(DerivedMesh *dm, float mdist, BitSet skipVert)
+{
+	if(mdist > 0.0f)
+	{
+		int i, j, merged;
+		int	numVerts = dm->getNumVerts(dm);
+		int *translate_vert = MEM_mallocN( sizeof(int)*numVerts, "merge points array");
+
+		MVert *vert = dm->getVertDataArray(dm, CD_MVERT);
+
+		if(!translate_vert) return;
+
+		merged = 0;
+		for(i=0; i<numVerts; i++)
+		{
+			translate_vert[i] = i;
+
+			if(skipVert && bitset_get(skipVert, i)) continue;
+
+			for(j = 0; j<i; j++)
+			{
+				if(skipVert && bitset_get(skipVert, j)) continue;
+				if(squared_dist(vert[i].co, vert[j].co) < mdist)
+				{
+					translate_vert[i] = j;
+					merged++;
+					break;
+				}
+			}
+		}
+
+		//some vertexs were merged.. recalculate structure (edges and faces)
+		if(merged > 0)
+		{
+			int	numFaces = dm->getNumFaces(dm);
+			int freeVert;
+			MFace *face = dm->getFaceDataArray(dm, CD_MFACE);
+
+
+			//Adjust vertexs using the translation_table.. only translations to back indexs are allowed
+			//which means t[i] <= i must always verify
+			for(i=0, freeVert = 0; i<numVerts; i++)
+			{
+				if(translate_vert[i] == i)
+				{
+					memcpy(&vert[freeVert], &vert[i], sizeof(*vert));
+					translate_vert[i] = freeVert++;
+				}
+				else translate_vert[i] = translate_vert[ translate_vert[i] ];
+			}
+
+			CDDM_lower_num_verts(dm, numVerts - merged);
+
+			for(i=0; i<numFaces; i++)
+			{
+				MFace *f = face+i;
+				f->v1 = translate_vert[f->v1];
+				f->v2 = translate_vert[f->v2];
+				f->v3 = translate_vert[f->v3];
+				//TODO be carefull with vertexs v4 being translated to 0
+				f->v4 = translate_vert[f->v4];
+			}
+
+			//TODO: maybe update edges could be done outside this function
+			CDDM_calc_edges(dm);
+			//CDDM_calc_normals(dm);
+		}
+
+		if(translate_vert) MEM_freeN( translate_vert );
+	}
+}
+
+
+/*
  * This calculates the distance (in dir units) that the ray must travel to intersect plane
  * It can return negative values
  *
@@ -703,25 +780,57 @@ static void shrinkwrap_removeUnused(ShrinkwrapCalcData *calc)
 	BitSet used_faces = bitset_new(numFaces, "shrinkwrap used faces");
 	int numUsedFaces = 0;
 
+
+	//calculate which vertexs need to be used
+	//even unmoved vertices might need to be used if theres a face that needs it
 	//calc real number of faces, and vertices
 	//Count used faces
 	for(i=0; i<numFaces; i++)
 	{
-		char res = bitset_get(moved_verts, face[i].v1)
-				 | bitset_get(moved_verts, face[i].v2)
-				 | bitset_get(moved_verts, face[i].v3)
-				 | (face[i].v4 ? bitset_get(moved_verts, face[i].v4) : 0);
+		char res = 0;
+		if(bitset_get(moved_verts, face[i].v1)) res++;
+		if(bitset_get(moved_verts, face[i].v2)) res++;
+		if(bitset_get(moved_verts, face[i].v3)) res++;
+		if(face[i].v4 && bitset_get(moved_verts, face[i].v4)) res++;
+
+		//Ignore a face were not a single vertice moved
+		if(res == 0) continue;
 
-		if(res)
+		//Only 1 vertice moved.. (if its a quad.. remove the vertice oposite to it)
+		if(res == 1 && face[i].v4)
 		{
-			bitset_set(used_faces, i);	//Mark face to maintain
-			numUsedFaces++;
+			if(bitset_get(moved_verts, face[i].v1))
+			{
+				//remove vertex 3
+				face[i].v3 = face[i].v4;
+			}
+			else if(bitset_get(moved_verts, face[i].v2))
+			{
+				//remove vertex 4
+			}
+			else if(bitset_get(moved_verts, face[i].v3))
+			{
+				//remove vertex 1
+				face[i].v1 = face[i].v4;
+			}
+			else if(bitset_get(moved_verts, face[i].v4))
+			{
+				//remove vertex 2
+				face[i].v2 = face[i].v3;
+				face[i].v3 = face[i].v4;
+			}
 
-			vert_index[face[i].v1] = 1;
-			vert_index[face[i].v2] = 1;
-			vert_index[face[i].v3] = 1;
-			if(face[i].v4) vert_index[face[i].v4] = 1;
+			face[i].v4 = 0;	//this quad turned on a tri
 		}
+
+		bitset_set(used_faces, i);	//Mark face to maintain
+		numUsedFaces++;
+
+		//Mark vertices are needed
+		vert_index[face[i].v1] = 1;
+		vert_index[face[i].v2] = 1;
+		vert_index[face[i].v3] = 1;
+		if(face[i].v4) vert_index[face[i].v4] = 1;
 	}
 
 	//DP: Accumulate vertexs indexs.. (will calculate the new vertex index with a 1 offset)
@@ -736,10 +845,16 @@ static void shrinkwrap_removeUnused(ShrinkwrapCalcData *calc)
 	new_vert  = new->getVertDataArray(new, CD_MVERT);
 	for(i=0, t=0; i<numVerts; i++)
 	{
+		
 		if(vert_index[i] != t)
 		{
 			t = vert_index[i];
 			memcpy(new_vert++, vert+i, sizeof(MVert));
+
+			if(bitset_get(moved_verts, i))
+				bitset_set(moved_verts, t-1);
+			else
+				bitset_unset(moved_verts, t-1);
 		}
 	}
 
@@ -779,6 +894,7 @@ static void shrinkwrap_removeUnused(ShrinkwrapCalcData *calc)
 	calc->final = new;
 }
 
+
 /* Main shrinkwrap function */
 DerivedMesh *shrinkwrapModifier_do(ShrinkwrapModifierData *smd, Object *ob, DerivedMesh *dm, int useRenderParams, int isFinalCalc)
 {
@@ -820,10 +936,12 @@ DerivedMesh *shrinkwrapModifier_do(ShrinkwrapModifierData *smd, Object *ob, Deri
 	//Projecting target defined - lets work!
 	if(calc.target)
 	{
+/*
 		printf("Shrinkwrap (%s)%d over (%s)%d\n",
 			calc.ob->id.name,			calc.final->getNumVerts(calc.final),
 			calc.smd->target->id.name,	calc.target->getNumVerts(calc.target)
 		);
+*/
 
 		switch(smd->shrinkType)
 		{
@@ -845,14 +963,21 @@ DerivedMesh *shrinkwrapModifier_do(ShrinkwrapModifierData *smd, Object *ob, Deri
 
 	}
 
-	//Destroy faces, edges and stuff
 	if(calc.moved)
 	{
+		//Destroy faces, edges and stuff
 		shrinkwrap_removeUnused(&calc);
-		bitset_free(calc.moved);
+
+		if(calc.moved)
+			derivedmesh_mergeNearestPoints(calc.final, calc.smd->mergeDist, calc.moved);
 	}
 
-	CDDM_calc_normals(calc.final);	
+	CDDM_calc_normals(calc.final);
+
+	//clean memory
+	if(calc.moved)
+		bitset_free(calc.moved);
+
 
 	return calc.final;
 }
@@ -873,12 +998,11 @@ void shrinkwrap_calc_nearest_vertex(ShrinkwrapCalcData *calc)
 	BVHTree *tree	= NULL;
 	BVHTreeNearest nearest;
 
-	BENCH_VAR(query);
-
 	int	numVerts;
 	MVert *vert = NULL;
 	MDeformVert *dvert = NULL;
 
+	BENCH_VAR(query);
 
 
 	BENCH(tree = bvhtree_from_mesh_verts(calc->target));
diff --git a/source/blender/makesdna/DNA_modifier_types.h b/source/blender/makesdna/DNA_modifier_types.h
index 7590cd0c3b9..25830321b93 100644
--- a/source/blender/makesdna/DNA_modifier_types.h
+++ b/source/blender/makesdna/DNA_modifier_types.h
@@ -495,8 +495,11 @@ typedef struct ShrinkwrapModifierData {
 	struct Object *target;	/* shrink target */
 	char vgroup_name[32];	/* optional vertexgroup name */
 	float keptDist;			/* distance offset from mesh/projection point */
+	float mergeDist;		/* distance to merge vertexs */
 	short shrinkType;		/* shrink type projection */
 	short shrinkOpts;		/* shrink options */
+
+	int pad;
 } ShrinkwrapModifierData;
 
 /* Shrinkwrap->shrinkType */
diff --git a/source/blender/src/buttons_editing.c b/source/blender/src/buttons_editing.c
index 808a964019f..5e1cfbea183 100644
--- a/source/blender/src/buttons_editing.c
+++ b/source/blender/src/buttons_editing.c
@@ -1830,7 +1830,7 @@ static void draw_modifier(uiBlock *block, Object *ob, ModifierData *md, int *xco
 			ShrinkwrapModifierData *smd = (ShrinkwrapModifierData*) md;
 			height = 86;
 			if (smd->shrinkType == MOD_SHRINKWRAP_NORMAL)
-				height += 19*5;
+				height += 19*6;
 		}
 							/* roundbox 4 free variables: corner-rounding, nop, roundbox type, shade */
 		uiDefBut(block, ROUNDBOX, 0, "", x-10, y-height-2, width, height-2, NULL, 5.0, 0.0, 12, 40, ""); 
@@ -2461,9 +2461,10 @@ static void draw_modifier(uiBlock *block, Object *ob, ModifierData *md, int *xco
 
 				uiDefButBitS(block, TOG, MOD_SHRINKWRAP_CULL_TARGET_FRONTFACE, B_MODIFIER_RECALC, "Cull frontfaces",	lx,(cy-=19),buttonWidth,19, &smd->shrinkOpts, 0, 0, 0, 0, "Controls whether a vertex can be projected to a front face on target");
 				uiDefButBitS(block, TOG, MOD_SHRINKWRAP_CULL_TARGET_BACKFACE,  B_MODIFIER_RECALC, "Cull backfaces",	lx,(cy-=19),buttonWidth,19, &smd->shrinkOpts, 0, 0, 0, 0, "Controls whether a vertex can be projected to a back face on target");
+				uiDefButF(block, NUM, B_MODIFIER_RECALC, "Merge Dist:",	lx,(cy-=19),buttonWidth,19, &smd->mergeDist, 0.0f, 0.01f, 0.01f, 0.01f, "Specify merge distance");
 			}
 
-			but=uiDefBut(block, TEX, B_MODIFIER_RECALC, "VGroup: ",		lx, (cy-=19), buttonWidth,19, &smd->vgroup_name, 0.0, 31.0, 0, 0, "Vertex Group name");
+			but=uiDefBut(block, TEX, B_MODIFIER_RECALC, "VGroup: ",		lx, (cy-=19), buttonWidth,19, &smd->vgroup_name, 0, 31, 0, 0, "Vertex Group name");
 			uiButSetCompleteFunc(but, autocomplete_vgroup, (void *)ob);
 
 			uiDefIDPoinBut(block, modifier_testMeshObj, ID_OB, B_CHANGEDEP, "Ob: ",	lx, (cy-=19), buttonWidth,19, &smd->target, "Target to shrink to");