“Collision Detection and Response for Computer Animation” by Moore and Wilhelms

When several objects are moved about by computer animation, there is the chance that they will interpenetrate. This is often an undesired state, particularly if the animation is seeking to model a realistic world. Two issues are involved: detecting that a collision has occurred, and responding to it. The former is fundamentally a kinematic problem, involving the positional relationship of objects in the world. The latter is a dynamic problem, in that it involves predicting behavior according to physical laws. This paper discusses collision detection and response in general, presents two collision detection algorithms, describes modeling collisions of arbitrary bodies using springs, and presents an analytical collision response algorithm for articulated rigid bodies that conserves linear and angular momentum.

1. William W. Armstrong and Mark W. Green, “The Dynamics of Articulated Rigid Bodies for Purposes of Animation,” Proceedings of Graphics Interface ’85, pp. 407-415, Canadian Information Processing Society, Toronto, Ontario, Canada, May 1985.
2. John W. Boyse, “Interference Detection Among Solids and Surfaces,” Communications of the ACM, vol. 22:1, pp. 3-9, January, 1979.
3. John Canny, “Collision Detection for Moving Polyhedra,” MIT Aar. Lab Memo 806, October, 1984.
4. Ingrid Carlbom, “An Algorithm for Geometric Set Operations Using Cellular Subdivision Techniques,” IEEE Computer Graphics and Applications, vol. 7, pp. 44-55, Computer Society of the IEEE, Los Alamitos, CA, May 1987.
5. Brice Carnahan and James O. Wilkes, Digital Computing and Numerical Methods, John Wiley and Sons, Inc., New York, 1973.
6. Scott E. Fahlman, “A Planning System for Robot Construction Tasks,” Artificial Intelligence, vol. 5, pp. 1-49, 1974.
7. Wm. Randolph Franklin, “Efficient Polyhedron Intersection and Union,” Proceedings of Graphics Interface 1982, pp. 73-80, 1982.
8. C. William Gear, Numerical Initial Value Problems in Ordinary Differential Equations, Prentice-Hall, Englewood Cliffs, NJ, 1971.
9. Jeffrey Goldsmith and John Salmon, “Automatic Creation of Object Hierarchies for Ray Tracing,” IEEE Computer Graphics and Applications, vol. 7, pp. 14-20, Computer Society of the IEEE, Los Alamitos, CA, May 1987.
10. I.N. Herstein, Topics in Algebra, Xerox College Publishing, Lexington, MA, 1964.
11. J.E. Hopcroft, J.T. Schwartz, and M. Sharir, “Efficient Detection of Intersections among Spheres,” The International Journal of Robotics Research, vol. 2:4, pp. 77-80, Winter 1983.
12. Paul M. Isaacs and Michael F. Cohen, “Controlling Dynamie Simulation with Kinematic Constraints,” Computer Graphics, vol. 21, no. 4. Proceedings of SIG- GRAPH’87 (Anaheim, CA, July 27-31, 1987)
13. Donald Knuth, Fundamental Algorithms, Addison- Wesley Publishing Co., Reading, MA, 1975.
14. Donald Knuth, Searching and Sorting, Addison-Wesley Publishing Co., Reading, MA, 1975.
15. Tomas Lozano-Perez and Michael A. Wesley, “An Algorithm for Planning CoUision-Free Paths Among Polyhedral Obstacles,” Communications of ACM, vol. 22, no. 10, pp. 560-570, October, 1979.
16. Richard V. Lundin, “Motion Simulation,” Proceedings of Nicograph 1984, pp. 2-10, November, 1984.
17. William D. MacMillan, Dynamics of Rigid Bodies, Dover Publications, Inc, New York, 1936.
18. W.G. McLean and E. W. Nelson, Engineering Mechanics: Statics and Dynamics, Shaum’s Outline Series, McGraw-Hill Book Co., New York, 1978.
19. Matthew Moore, “A Flexible Object Animation System,” Masters Thesis, University of California, Santa Cruz, Computer & Information Sciences, Santa Cruz, California, March, 1988.
20. Ole Osterby and Zahari Zlatev, Direct Methods for Sparse Matrices, Springer-Verlag, Berlin, 1983.
21. Sergio Pissanetsky, Sparse Matrix Technology, Academic Press, London, 1984.
22. William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling, Numerical Recipes, Cambridge University Press, Cambridge, England, 1986.
23. Craig W. Reynolds, “Computer Animation with Scripts and Actors,” Computer Graphics, vol. 16, no. 4, pp. 289-296, Association for Computing Machinery, July, 1982. Proceedings of SIGGRAPH’82
24. Craig W. Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model,” Computer Graphics, vol. 21, no. 4, pp. 25-34, Association for Computing Machinery. Proceedings of SIGGRAPH’87 (Anaheim, CA, July 27-31, 1987)
25. David F. Rogers, Procedural Elements for Computer Graphics, McGraw-HiU Book Company, New York, 1985.
26. Robert Skinner, U Cal. Santa Cruz, CIS Dept. personal communication.
27. Scott N. Steketee and Norman I. Badler, “Parametric Keyframe Interpolation Incorporating Kinetic Adjustment and Phrasing Control,” Proceedings of SIGGRAPH ’85, vol. 19, no. 4, pp. 255-262, July, 1985.
28. David Sturman, A Discussion on the Development of Motion Control Systems, Association for Computing Machinery, July 1987. SIGgraph ’87 Course 10 Notes: Computer Animation: 3-D Motion Specification and Control.
29. Demetri Terzopoulous, John Platt, Alan H. Barr, and Kurt Fleischer, “Elastically Deformable Models,” Computer Graphics, vol. 21, no. 4. Proceedings of SIG- GRAPH’87 (Anaheim, CA, July 27-31, 1987)
30. Tetsuya Uchild, Toshiaki Ohashi, and Mario Tokoro, “Collision Detection in Motion Simulation,” Computers & Graphics, vol. 7:3-4, pp. 285-293, 1983.
31. Jane Wilhelms, “‘Towards Automatic Motion Control,” IEEE Computer Graphics and Animation April, 1987, vol. 7, no. 4, pp. 11-22, April, 1987.
32. Jane Wilhelms, “Using Dynamic Analysis for Animation of Articulated Bodies,” IEEE Computer Graphics and Applications, vol. 7, no. 6, June, 1987.