i
i
i
i
i
i
i
i
438 17. Computer Animation
simultaneously operate on several 3D grids of possibly floating point values and
can be used for modeling dynamics of clouds and other gaseous phenomena or
biological systems for which this apparatus was originally invented (note the ter-
minology). Surprising pattern complexity can arise from just a few well-chosen
rules, but how to write such rules to create the desired behavior is often not obvi-
ous. This is a common problem with procedural techniques: there is only limited,
if any, guidance on how to create new procedures or even adjust parameters of
existing ones. Therefore, a lot of tweaking and learning by trial-and-error (“by
experience”) is usually needed to unlock the full potential of procedural methods.
Another interesting approach which was also originally developed to describe
biological objects is the technique called L-systems (after the name of their origi-
nal inventor, Astrid Lindenmayer). This approach is based on grammars or sets of
recursive rules for rewriting strings of symbols. There are two types of symbols:
terminal symbols stand for elements of something we want to represent with a
grammar. Depending on their meaning, grammars can describe structure of trees
and bushes, buildings and whole cities, or programming and natural languages.
In animation, L-systems are most popular for representing plants and correspond-
ing terminals are instructions to the geometric modeling system: put a leaf (or a
branch) at a current position—we will use the symbol @ and just draw a circle,
move current position forward by some number of units (symbol f), turn current
direction 60 degrees around world Z-axis (symbol +), pop (symbol [) or push
(symbol ]) current position/orientation, etc. Auxiliary nonterminal symbols (de-
noted by capital letters) have only semantic rather than any direct meaning. They
are intended to be eventually rewritten through terminals. We start from the spe-
cial nonterminal start symbol S and keep applying grammar rules to the current
string in parallel, i.e., replace all nonterminals currently present to get the new
string, until we end up with a string containing only terminals and no more sub-
stitution is therefore possible. This string of modeling instructions is then used to
B
B
A
B
A
B
B
AS
Figure 17.27. Con-
secutive derivation steps
using a simple L-system.
Capital letters denote
non-terminals and illustrate
positions at which corre-
sponding non-terminal will
be expanded. They are not
part of the actual output.
output the actual geometry. For example, a set of rules (productions)
S → A
A → [+B]fA
A → B
B → fB
B → f @
might result in the following sequence of rewriting steps demonstrated in Fig-
ure 17.27
S −→ A −→ [+B]fA −→ [+fB]f[+B]fA −→
[+ff@]f[+fB]fB −→ [+ff@]f[+ff@]ff@
i
i
i
i
i
i
i
i
17.7. Groups of Objects 439
As shown above, there are typically many different productions for the same non-
terminal allowing the generation of many different objects with the same gram-
mar. The choice of which rule to apply can depend on which symbols are located
next to the one being replaced (context-sensitivity) or can be performed at ran-
dom with some assigned probability for each rule (stochastic L-systems). More
complex rules can model interaction with the environment, such as pruning to a
particular shape, and parameters can be associated with symbols to control geo-
metric commands issued.
L-systems already capture plant topology changes with time: each interme-
diate string obtained in the rewriting process can be interpreted as a “younger”
version of the plant (see Figure 17.27). For more significant changes, different
productions can be in effect at different times allowing the structure of the plant
to change significantly as it grows. A young tree, for example, produces a lot of
new branches while an older one branches only moderately.
Very realistic plant models have been created with L-systems. However, as
with most procedural techniques, one needs some experience to meaningfully
apply existing L-systems, and writing new grammars to capture some desired
effect is certainly not easy.
17.7 Groups of Objects
To animate multiple objects one can, of course, simply apply standard techniques
outlined above to each of them. This works reasonably well for a moderate num-
ber of independent objects whose desired motion is known in advance. However,
in many cases, some kind of coordinated action in a dynamic environment is nec-
essary. If only a few objects are involved, the animator can use an artificial intel-
ligence (AI)-based system to automatically determine immediate tasks for each
object based on some high-level goal, plan necessary motion, and execute the
plan. Many modern games use such autonomous objects to create smart monsters
or player’s collaborators.
Interestingly, as the number of objects in a group grows from just a few to
several dozens, hundreds, and thousands, individual members of a group must
have only very limited “intelligence” in order for the group as a whole to exhibit
what looks like coordinated goal-driven motion. It turns out that this flocking
is emergent behavior which can arise as a result of limited interaction of group
members with just a few of their closest neighbors (Reynolds, 1987). Flocking
should be familiar to anyone who has observed the fascinatingly synchronized
motion of a flock of birds or a school of fish. The technique can also be used to
control groups of animals moving over terrain or even a human crowd.
i
i
i
i
i
i
i
i
440 17. Computer Animation
gravity
goal
velocity matching
collision avoidance
flock centering
physical forces
navigation module
steering
collision avoidance
goal
pilot module
physical constraints
desired velocity
feasible velocity
flight module
boid control adjustments
Figure 17.28. (Left) Individual flock member (boid) can experience several urges of different
importance (shown by line thickness) which have to be negotiated into a single velocity vec-
tor. A boid is aware of only its limited neighborhood (circle). (Right) Boid control is commonly
implemented as three separate modules.
At any given moment, the motion of a member of a group, often called boid
when applied to flocks, is the result of balancing several often contradictory ten-
dencies, each of which suggests its own velocity vector (see Figure 17.28). First,
there are external physical forces F acting on the boid, such as gravity or wind.
New velocity due to those forces can be computed directly through Newton’s law
as
v
physics
new
= v
old
+ FΔt/m.
Second, a boid should react to global environment and to the behavior of other
group members. Collision avoidance is one of the main results of such interac-
tion. It is crucial for flocking that each group member has only limited field of
view, and therefore is aware only of things happening within some neighborhood
of its current position. To avoid objects in the environment, the simplest, if imper-
fect, strategy is to set up a limited extent repulsive force field around each such
object. This will create a second desired velocity vector v
col avoid
new
,alsogiven
by Newton’s law. Interaction with other group members can be modeled by si-
multaneously applying different steering behaviors resulting in several additional
desired velocity vectors v
steer
new
. Moving away from neighbors to avoid crowding,
steering towards flock mates to ensure flock cohesion and adjusting a boid’s speed
to align with average heading of neighbors are most common. Finally, some addi-
tional desired velocity vectors v
goal
new
are usually applied to achieve needed global
goals. These can be vectors along some path in space, following some specific
i
i
i
i
i
i
i
i
17.7. Groups of Objects 441
designated leader of the flock, or simply representing migratory urge of a flock
member.
Once all v
new
are determined, the final desired vector is negotiated based on
priorities among them. Collision avoidance and velocity matching typically have
higher priority. Instead of simple averaging of desired velocity vectors which can
lead to cancellation of urges and unnatural “moving nowhere” behavior, an ac-
celeration allocation strategy is used. Some fixed total amount of acceleration is
made available for a boid and fractions of it are being given to each urge in order
of priority. If the total available acceleration runs out, some lower priority urges
will have less effect on the motion or be completely ignored. The hope is that
once the currently most important task (collision avoidance in most situations) is
accomplished, other tasks can be taken care of in near future. It is also important
to respect some physical limitations of real objects, for example, clamping too
high accelerations or speeds to some realistic values. Depending on the internal
complexity of the flock member, the final stage of animation might be to turn the
negotiated velocity vector into a specific set of parameters (bird’s wing positions,
orientation of plane model in space, leg skeleton bone configuration) used to con-
trol a boid’s motion. A diagram of a system implementing flocking is shown on
Figure 17.28 (right).
A much simpler, but still very useful, version of group control is implemented
by particle systems (Reeves, 1983). The number of particles in a system is typi-
cally much larger than number of boids in a flock and can be in the tens or hun-
dreds of thousands, or even more. Moreover, the exact number of particles can
fluctuate during animation with new particles being born and some of the old
ones destroyed at each step. Particles are typically completely independent from
each other, ignoring one’s neighbors and interacting with the environment only
by experiencing external forces and collisions with objects, not through collision
avoidance as was the case for flocks. At each step during animation, the sys-
tem first creates new particles with some initial parameters, terminates old ones,
and then computes necessary forces and updates velocities and positions of the
remaining particles according to Newton’s law.
All parameters of a particle system (number of particles, particle life span,
initial velocity, and location of a particle, etc.) are usually under the direct control
of the animator. Prime applications of particle systems include modeling fire-
works, explosions, spraying liquids, smoke and fire, or other fuzzy objects and
phenomena with no sharp boundaries. To achieve a realistic appearance, it is im-
portant to introduce some randomness to all parameters, for example, having a
random number of particles born (and destroyed) at each step with their velocities
generated according to some distribution. In addition to setting appropriate initial
i
i
i
i
i
i
i
i
442 17. Computer Animation
Particle source
Local wind field
Figure 17.29. After being emitted by a directional source, particles collide with an object
and then are blown down by a local wind field once they clear the obstacle.
parameters, controlling the motion of a particle system is commonly done by cre-
ating a specific force pattern in space—blowing a particle in a new direction once
it reaches some specific location or adding a center of attraction, for example.
One should remember that with all their advantages, simplicity of implementa-
tion and ease of control being the prime ones, particle systems typically do not
provide the level of realism characteristic of true physics-based simulation of the
same phenomena.
Notes
In this chapter we have concentrated on techniques used in 3D animation. There
also exist a rich set of algorithms to help with 2D animation production and post-
processing of images created by computer graphics rendering systems. These
include techniques for cleaning up scanned-in artist drawings, feature extrac-
tion, automatic 2D in-betweening, colorization, image warping, enhancement and
compositing, and many others.
One of the most significant developments in the area of computer animation
has been the increasing power and availability of sophisticated animation systems.
While different in their specific set of features, internal structure, details of user
interface, and price, most such systems include extensive support not only for
animation, but also for modeling and rendering turning them into complete pro-
duction platforms. It is also common to use these systems to create still images.
For example, many images for figures in this section were p roduced using Maya
software generously donated by Alias.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.