Interpolating Values - Computer Animation: Algorithms and Techniques - page 107

An easy way to determine a path along a polygonal surface mesh is to determine a plane that con-
tains the two points and is generally perpendicular to the surface. Generally perpendicular can be
defined, for example, as the plane containing the two vertices and the average of the two vertex normals
that the path is being formed between. The intersection of the plane with the faces making up the sur-
face mesh will define a path between the two points ( Figure 3.47 ) .
If the surface is a higher order surface and the known points are defined in the u , v coordinates of the
surface definition, then a straight line (or curve) can be defined in the parametric space and transferred
to the surface. A linear interpolation of u , v coordinates does not guarantee the most direct route, but it
should produce a reasonably short path.
Over a complex surface mesh, a greedy-type algorithm can be used to construct a path of edges
along a surface from a given start vertex to a given destination vertex. For each edge emanating
from the current vertex (initially the start vertex), calculate the projection of the edge onto the unit
vector from the current vertex to the destination vertex. Divide this distance by the length of the edge
to get the cosine of the angle between the edge and the straight line. The edge with the largest
cosine is the edge most in the direction of the straight line; choose this edge to add to the path. Keep
applying this until the destination edge is reached. Improvements to this approach can be made by
allowing the path to cut across polygons to arrive at points along edges rather than by going vertex to
vertex. For example, using the current path point and the line from the start and end vertices to form a
plane, intersect the plane with the plane of the current triangle. If the line of intersection falls inside
of the current triangle, use the segment inside of the triangle as part of the path. If the line of
intersection leaving the current vertex is outside of the triangle, find the adjacent triangle and use
it as the current triangle, and repeat. For the initial plane, the start and end vertex can be used along
with some point on the surface that is judged to lie in the general direction of the path that is yet to be
determined.
If a path downhill from an initial point on the surface is desired, then the surface normal and global
“up” vector can be used to determine the downhill vector. The cross-product of the normal and
global up vector defines a vector that lies on the surface perpendicular to the downhill direction.
So the cross-product of this vector and the normal vector define the downhill (and uphill) vector on
a plane ( Figure 3.48 ). This same approach works with curved surfaces to produce the instantaneous
downhill vector.
FIGURE 3.47
Determining a path along a polygonal surface mesh by using plane intersection.