Background Information and Techniques - Computer Animation: Algorithms and Techniques - page 489

Nonlinear, constrained optimization is where things get interesting—and complicated. One strategy
is to take a step in parameter space to reduce the objective function regardless of the constraints, fol-
lowed by a step to restore constraint satisfaction.
A different common method for considering constraints is to incorporate constraints in the objective
function. This adds a dimension to the parameter space. Assume f ( x ) is the objective function and
g ( x ) 0 is a constraint. The new objective function is shown in Equation B.168 , where l is an

unknown constant called the Lagrange multiplier . Differentiating produces Equation B.169 . To deal
with more complex constraint situations, sequential quadratic programming can be used.

c ¼

minimize f ð X Þþlðcð X ÞdÞ (B.168)

@Fð Þ

@ X ¼rf ð

X

Þþlrcð Þ¼

X X 0

(B.169)

@Fð X Þ

¼ cð X Þd ¼ 0

@l

If evaluation of the derivative of the function is expensive or unavailable, or if the parameter space is
expansive with many local minima, the parameter space can be randomly sampled.
Completely random sampling is blended with increased sampling in areas where low values are
found. Early sampling favors randomness while later sampling favors sampling in low value areas.
Maintaining some randomness ensures that the global minimum will be found in the limit.
This is the basis for the approaches such as genetic algorithms and genetic programming . They are
generally simple to program, but with finite resources do not guarantee convergence on the optimum.
They are very useful when finding “good” values are sufficient.

B.10 Standards for moving pictures
When producing computer animation, one must decide what format to use for storing the sequence of
images. Years ago the images were captured on film by taking pictures of refresh vector screens or by
plotting the images directly onto the film. This was a long and expensive process requiring single-frame
film cameras and the developing of nonreusable film stock. The advent of frame buffers and video
encoders made recording on videotape a convenient alternative. With today's cheap disks, memory,
and CPU cycles, all-digital desktop video production is a reality. While the entertainment industry
is still based on film, most of the rest of computer animation is produced using digital images intended
to be displayed on a raster-scan device in such forms as broadcast video, DVD video, animated Web
banners, and streaming video. This section is intended to give the reader some idea of the various stan-
dards used for recording moving pictures. Standards related to the digital image are emphasized.

B.10.1 In the beginning, there was analog
Before the rise of digital video, the two common formats for moving pictures were film and (analog)
video. Over the years there have been almost a hundred film formats. The formats differ in the size of
the frame, in the placement, size, and number of perforations, and in the placement and type of audio
tracks [ 15 ]. Silent film is played at 16 frames per second (fps). Some sound film is played at 18 fps, but
24 fps is more common. Film played at 24 fps is typically doubly projected; that is, each frame is
displayed twice to reduce the effects of flicker.