Abstract:

Animators frequently choreograph complex motions for multiple objects that interact through collision and obstruction. In such situations, the use of physically based dynamics to confer visual realism creates challenging computational problems. Typically forward simulation is well understood, but the inverse problem of motion synthesis---that of synthesizing motions consistent both with physical law and with the animator\'s requirements---is generally tedious and sometimes intractable. We show how N-body inverse problems can be formulated as optimization tasks. We present a simply stated, but combinatorially formidable example that exhibits all of the essential sources of complexity common to N-body motion synthesis, and show how it can be solved approximately using heuristic methods based on evolutionary computation. Key Words and Phrases: Animation, motion synthesis, heuristic methods, stochastic optimization, evolutionary computation, billiard-ball problems.