Mesh Deform Modifier

====================

The MeshDeform modifier can deform a mesh with another 'cage' mesh.
It is similar to a lattice modifier, but instead of being restricted
to the regular grid layout of a lattice, the cage mesh can be modeled
to fit the mesh better.

http://www.blender.org/development/current-projects/changes-since-244/modifiers/

Implementation Notes:
- OpenNL has been refactored a bit to allow least squares matrices to
  be built without passing the matrix row by row, but instead with
  random access. MDef doesn't need this actually, but it's using this
  version of OpenNL so I'm just committing it now.
- Mean value weights for polygons have been added to arithb.c, a type
  of barycentric coordinates for polygons with >= 3 vertices. This
  might be useful for other parts of blender too.

2 files changed, 49 insertions, 2 deletions

diff --git a/source/blender/blenlib/BLI_arithb.h b/source/blender/blenlib/BLI_arithb.h
index fc132250fc6..2942439504c 100644
--- a/source/blender/blenlib/BLI_arithb.h
+++ b/source/blender/blenlib/BLI_arithb.h
@@ -282,7 +282,8 @@ extern short IsectLL2Ds(short *v1, short *v2, short *v3, short *v4);
 
 /* interpolation weights of point in a triangle or quad, v4 may be NULL */
 void InterpWeightsQ3Dfl(float *v1, float *v2, float *v3, float *v4, float *co, float *w);
-
+/* interpolation weights of point in a polygon with >= 3 vertices */
+void MeanValueWeights(float v[][3], int n, float *co, float *w);
 
 void i_lookat(
 	float vx, float vy, 
diff --git a/source/blender/blenlib/intern/arithb.c b/source/blender/blenlib/intern/arithb.c
index f95d102763a..721df3a1a0c 100644
--- a/source/blender/blenlib/intern/arithb.c
+++ b/source/blender/blenlib/intern/arithb.c
@@ -2506,7 +2506,53 @@ void InterpWeightsQ3Dfl(float *v1, float *v2, float *v3, float *v4, float *co, f
 		else
 			BarycentricWeights(v1, v2, v3, co, n, w);
 	}
-} 
+}
+
+/* Mean value weights - smooth interpolation weights for polygons with
+ * more than 3 vertices */
+static float MeanValueHalfTan(float *v1, float *v2, float *v3)
+{
+	float d2[3], d3[3], cross[3], area, dot, len;
+
+	VecSubf(d2, v2, v1);
+	VecSubf(d3, v3, v1);
+	Crossf(cross, d2, d3);
+
+	area= VecLength(cross);
+	dot= Inpf(d2, d3);
+	len= VecLength(d2)*VecLength(d3);
+
+	if(area == 0.0f)
+		return 0.0f;
+	else
+		return (len - dot)/area;
+}
+
+void MeanValueWeights(float v[][3], int n, float *co, float *w)
+{
+	float totweight, t1, t2, len, *vmid, *vprev, *vnext;
+	int i;
+
+	totweight= 0.0f;
+
+	for(i=0; i<n; i++) {
+		vmid= v[i];
+		vprev= (i == 0)? v[n-1]: v[i-1];
+		vnext= (i == n-1)? v[0]: v[i+1];
+
+		t1= MeanValueHalfTan(co, vprev, vmid);
+		t2= MeanValueHalfTan(co, vmid, vnext);
+
+		len= VecLenf(co, vmid);
+		w[i]= (t1+t2)/len;
+		totweight += w[i];
+	}
+
+	if(totweight != 0.0f)
+		for(i=0; i<n; i++)
+			w[i] /= totweight;
+}
+
 
 /* ************ EULER *************** */