# Geometric Distance Algorithm for Finding Initial Vertex
Weights

This initial weight guessing algorithm uses mesh connectivity
and geometric distance rather than Euclidean distance to decide
which joints should influence a given vertex. This prevents a joint
from influencing a vertex that, although very close in Euclidean
distance, is not near to the joint in terms of the mesh. A classic
example of this is in the knees of a biped character. The vertices
at the inside of the knees may be very close to each other but you
would never want a left knee joint to influence a right knee
vertex, or vice versa.

The geometric distances between vertices is precomputed using
Dijkstra's algorithm using each vertex as the source. This is an
*N*x*N* matrix, for a mesh of *N* vertices. This is
one way to compute All Pairs Shortest Paths for a graph, or in my
case, a mesh.

So, you might ask, how do you compute distance from a vertex to
a joint? The answer, cut the mesh with the joint coordinate plane
and the store the "ring" of vertices in the mesh that approximate
the plane-mesh intersections. This ring of vertices are at distance
0 from the joint, then use the precomputed All Pairs Shortest Paths
matrix for the rest.

Below is a psuedocode outline of the algorithm:

/* Cut the mesh by each joint and get the ring of vertices. */
**for** each joint *j* in skeleton,
Cut the mesh by the plane defined by *j*'s coordinate system
Store list of *n* vertices in the mesh that best approximate
the *n* plane-mesh intersections
/* Find initial influence set and weights for each vertex */
**for** each vertex *v* in mesh,
Find the geometric distance *d* to each joint by finding the nearest vertex
in each plane-mesh approximation list
**do**,
**if** the current closest joint *d*_{j} = **min**( *D* ) < *Threshold*,
Add joint *j* to *v*'s influence set with *weight* = *d*_{j}
*D* = *D* - *d*_{j}
**until** we have selected the maximum number of influences
*Maximum-Distance* = **min**( *D* )
**for** each influence *j*,
*weight*_{j} = *F*( *weight*_{j} / *Maximum-Distance* )

For the weight normalization function *F* I use a Cubic
Hermite Spline. I tried a linear falloff function as well but this
one produced qualitatively better results.

Luke Tokheim, <ltokheim@cs.wisc.edu>, May 13,
2003