Goal-Directed Navigation for Animated Characters
Using Real-Time Path Planning and Control
- James Kuffner, Jr.
- Robotics Laboratory
- Department of Computer Science
- Stanford University
- Stanford, CA 94305, USA
Abstract
This paper presents a new technique for computing collision-free
navigation motions from task-level commands for animated human
characters in interactive virtual environments. The algorithm
implementation utilizes the hardware rendering pipeline commonly found
on graphics accelerator cards to perform fast 2D motion planning.
Given a 3D geometric description of an animated character and a
level-terrain environment, collision-free navigation paths can be
computed between initial and goal locations at interactive rates.
Speed is gained by leveraging the graphics hardware to quickly project
the obstacle geometry into a 2D bitmap for planning. The bitmap may
be searched by any number of standard dynamic programming techniques
to produce a final path. Cyclic motion capture data is used along
with a simple proportional derivative controller to animate the
character as it follows the computed path. The technique has been
implemented on an SGI Indigo2 workstation and runs at interactive
rates. It allows for real-time modification of the goal locations and
obstacle positions for multiple characters in complex environments
composed of more than 15,000 triangles.
Keywords:
Real-Time Motion Planning, Goal-Directed Navigation, Virtual Humans,
Task-Level Animation, Motion Capture Synthesis, Interactive Virtual
Environments
|
