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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. J. Kuffner Jr., An Architecture for the Design of Intelligent Animated Characters, Ph.D. thesis, Stanford University (in preparation).
J. C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, Boston, MA, 1991.
A. Witkin and Z. Popovic, “Motion warping,” in Proc. SIGGRAPH’ 95, 1995.
A. Bruderlin and L. Williams, “Motion signal processing,” in Proc. SIGGRAPH’ 95, Robert Cook, Ed. ACM SIGGRAPH, Aug. 1995, Annual Conference Series, pp. 97–104, Addison Wesley, held in Los Angeles, California, 06–11 August 1995.
D. Baraff, “Analytical methods for dynamic simulation of non-penetrating rigid bodies,” in Proc. SIGGRAPH’ 89, 1989, pp. 223–231.
B. Mirtich, Impulse-Based Dynamic Simulation of Rigid Body Systems, Ph.D. thesis, University of California, Berkeley, CA, 1996.
A. Witkin and Kass M., “Spacetime constraints,” in Proc. SIGGRAPH’ 88, 1988, pp. 159–168.
J. T. Ngo and J. Marks, “Spacetime constraints revisited,” in Proc. SIGGRAPH’ 93, 1993, pp. 343–350.
Z. Liu, S. J. Gortler, and F. C. Cohen, “Hierachical spacetime control,” in Proc. SIGGRAPH’ 94, 1994, pp. 35–42.
R. A. Brooks, “A layered intelligent control system for a mobile robot,” in Robotics Research The Third International Symposium. 1985, pp. 365–372, MIT Press, Cambridge, MA.
R. C. Arkin, “Cooperation without communication: Multiagent schema based robot navigation,” Journal of Robotic Systems, pp. 351–364, 1992.
J. Lengyel, M. Reichert, B. R. Donald, and D. P. Greenberg, “Real-time robot motion planning using rasterizing computer graphics hardware,” in Proc. SIGGRAPH’ 90, 1990.
Y. Koga, K. Kondo, J. Kuffner, and J.-C. Latombe, “Planning motions with intentions,” in Proc. SIGGRAPH’ 94, 1994, pp. 395–408.
D. Hsu and M. Cohen, “Task-level motion control for human figure animation,” Unpublished Manuscript, 1997.
M. R. Jung, N. Badler, and T. Noma, “Animated human agents with motion planning capability for 3D-space postural goals,” The Journal of Visualization and Computer Animation, vol. 5, no. 4, pp. 225–246, October 1994.
J. P. Granieri, W. Becket, B. D. Reich, J. Crabtree, and N. L. Badler, “Behavioral control for real-time simulated human agents,” in 1995 Symposium on Interactive 3D Graphics, Pat Hanrahan and Jim Winget, Eds. ACM SIGGRAPH, Apr. 1995, pp. 173–180, ISBN 0-89791-736-7.
E. Kokkevis, D. Metaxas, and N. I. Badler, “Autonomous animation and control of four-legged animals,” in Graphics Interface’ 95, Wayne A. Davis and Przemyslaw Prusinkiewicz, Eds. Canadian Information Processing Society, May 1995, pp. 10–17, Canadian Human-Computer Communications Society, ISBN 0-9695338-4-5.
N. Badler, “Real-time virtual humans,” Pacificc Graphics, 1997.
X. Tu and D. Terzopoulos, “Artificial fishes: Physics, locomotion, perception, behavior,” in Proc. SIGGRAPH’ 94, Andrew Glassner, Ed. ACM SIGGRAPH, July 1994, Computer Graphics Proceedings, Annual Conference Series, pp. 43–50, ACM Press, ISBN 0-89791-667-0.
H. Noser, O. Renault, D. Thalmann, and N. Magnenat Thalmann, “Navigation for digital actors based on synthetic vision, memory and learning,” Comput. Graphics, vol. 19, pp. 7–19, 1995.
K. Perlin and A. Goldberg, “IMPROV: A system for scripting interactive actors in virtual worlds,” in Proc. SIGGRAPH’ 96, Holly Rushmeier, Ed. ACM SIGGRAPH, 1996, Annual Conference Series, pp. 205–216, Addison Wesley.
K. Perlin, “Real time responsive animation with personality,” IEEE Transactions on Visualization and Computer Graphics, vol. 1, no. 1, pp. 5–15, March 1995, ISSN 1077-2626.
B. M. Blumberg and T. A. Galyean, “Multi-level direction of autonomous creatures for real-time virtual environments,” in Proc. SIGGRAPH’ 95, Robert Cook, Ed. ACM SIGGRAPH, Aug. 1995, Annual Conference Series, pp. 47–54, Addison Wesley, held in Los Angeles, California, 06–11 August 1995.
P. Maes, D. Trevor, B. Blumberg, and A. Pentland, “The ALIVE system full-body interaction with autonomous agents,” in Computer Animation’ 95, Apr. 1995.
J. Bates, A. B. Loyall, and W. S. Reilly, “An architecture for action, emotion, and social behavior,” in Artificial Social Systems: Proc of 4th European Wkshp on Modeling Autonomous Agents in a Multi-Agent World. 1994, Springer-Verlag.
D. C. Brogan and J. K. Hodgins, “Group behaviors with significant dynamics,” in Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, 1995.
J. K. Hodgins, “Three-dimensional human running,” in Proc. IEEE Int. Conf. on Robotics and Automation, 1996.
J. H. Reif, “Complexity of the mover’s problem and generalizations,” in Proc. 20th IEEE Symp. on Foundations of Computer Science (FOCS), 1979, pp. 421–427.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg1998
About this paper
Cite this paper
Kuffner, J.J. (1998). Goal-Directed Navigation for Animated Characters Using Real-Time Path Planning and Control. In: Magnenat-Thalmann, N., Thalmann, D. (eds) Modelling and Motion Capture Techniques for Virtual Environments. CAPTECH 1998. Lecture Notes in Computer Science(), vol 1537. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49384-0_14
Download citation
DOI: https://doi.org/10.1007/3-540-49384-0_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65353-0
Online ISBN: 978-3-540-49384-6
eBook Packages: Springer Book Archive