Bone Heat Weighting

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

This is a new automatic vertex weighting method, next to the existing
envelope based method. The details are here:

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

This is based on section 4 of the paper:

"Automatic Rigging and Animation of 3D Characters"
Ilya Baran and Jovan Popovic, SIGGRAPH 2007

Implementation Notes:

- Generic code for making mesh laplacian matrices has been added, which
  is only used by bone heat weighting at the moment.
- Bone to vertex visibility checking is done with the raytracing code.
- Fixed an issue in the subsurf limit calculation function, where the
  position of vertices on boundary edges was wrong. It is still not the
  correct position, but at least it's in the neighbourhood now.

2 files changed, 28 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_arithb.h b/source/blender/blenlib/BLI_arithb.h
index 4ee01f7fe33..a732f09ca58 100644
--- a/source/blender/blenlib/BLI_arithb.h
+++ b/source/blender/blenlib/BLI_arithb.h
@@ -258,6 +258,8 @@ void euler_rot(float *beul, float ang, char axis);
 
 float DistVL2Dfl(float *v1, float *v2, float *v3);
 float PdistVL2Dfl(float *v1, float *v2, float *v3);
+float PdistVL3Dfl(float *v1, float *v2, float *v3);
+void PclosestVL3Dfl(float *closest, float *v1, float *v2, float *v3);
 float AreaF2Dfl(float *v1, float *v2, float *v3);
 float AreaQ3Dfl(float *v1, float *v2, float *v3, float *v4);
 float AreaT3Dfl(float *v1, float *v2, float *v3);
diff --git a/source/blender/blenlib/intern/arithb.c b/source/blender/blenlib/intern/arithb.c
index 125c24a7ada..e98ce92787f 100644
--- a/source/blender/blenlib/intern/arithb.c
+++ b/source/blender/blenlib/intern/arithb.c
@@ -3284,6 +3284,31 @@ int point_in_tri_prism(float p[3], float v1[3], float v2[3], float v3[3])
 	return 1;
 }
 
+/* point closest to v1 on line v2-v3 in 3D */
+void PclosestVL3Dfl(float *closest, float *v1, float *v2, float *v3)
+{
+	float lambda, cp[3], len;
+
+	lambda= lambda_cp_line_ex(v1, v2, v3, cp);
+
+	if(lambda <= 0.0f)
+		VecCopyf(closest, v2);
+	else if(lambda >= 1.0f)
+		VecCopyf(closest, v3);
+	else
+		VecCopyf(closest, cp);
+}
+
+/* distance v1 to line-piece v2-v3 in 3D */
+float PdistVL3Dfl(float *v1, float *v2, float *v3) 
+{
+	float closest[3];
+
+	PclosestVL3Dfl(closest, v1, v2, v3);
+
+	return VecLenf(closest, v1);
+}
+
 /********************************************************/
 
 /* make a 4x4 matrix out of 3 transform components */
@@ -3331,3 +3356,4 @@ void LocQuatSizeToMat4(float mat[][4], float loc[3], float quat[4], float size[3
 	mat[3][1] = loc[1];
 	mat[3][2] = loc[2];
 }
+