Graphics Reference
In-Depth Information
Y (global “up” vector: y -axis)
N (vector normal to surface)
D
Y
A
A N Y
FIGURE 3.48
Calculating the downhill vector,
D
.
3.4.5 Path finding
Finding a collision-free path in an arbitrarily complex environment can be a complicated task. In the
simple case, a point is to be moved through an otherwise stationary environment. If the obstacles are
moving, but their paths are known beforehand, then the problem is manageable. If the movements of
the obstructions are not known, then path finding can be very difficult. A further complication is
when the object to be moved is not just a point, but has spatial extent. If the object has a nontrivial
shape (i.e., not a sphere) and can be arbitrarily rotated as it moves, then the problem becomes even
more interesting. A few ideas for path finding are mentioned here.
In finding a collision-free path among static obstacles, it is often useful to break the problem into
simpler subproblems by introducing via points . These are points that the path should pass through—or
at least educated guesses of points that the path might pass through. In this manner, finding the path is
reduced to a number of simpler problems of finding paths between the via points.
If the size of the moving object might determine whether it can pass between obstacles, then finding
a collision-free path can be a problem. However, if the moving object can be approximated by a sphere,
then increasing the size of the obstacles by the size of the approximating sphere changes the problem
into one of finding the path of a point through the expanded environment. More complex cases, in
which the moving object has to adjust its orientation in order to pass by obstacles, are addressed in
the robotics literature, for example.
Situations in which the obstacles are moving present significant challenges. A path through the
static objects can be established and then movement along this path can be used to avoid moving obsta-
cles, although there is no guarantee that a successful movement can be found. If the environment is not
cluttered with moving obstacles, then a greedy-type algorithm can be used to avoid one obstacle at a
time, by angling in front of the moving obstacle or angling behind it, in order to produce a path. This
type of approach assumes that the motion of the obstacles, although unknown, is predictable.
3.5 Chapter summary
Interpolation is fundamental to much animation, and the ability to understand and control the interpo-
lation process is very important in computer animation programming. Interpolation of values takes
many forms, including arc length, image pixel color, and shape parameters. The control of the inter-
polation process can be key framed, scripted, or analytically determined. But in any case, interpolation
forms the foundation upon which most computer animation takes place, including those animations that
use advanced algorithms.
 
Search WWH ::




Custom Search