Collision detection and response for computer animationr3

ABSTRACT

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	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, v.22 n.1, p.3-9, Jan. 1979 [doi>10.1145/359046.359048]
	3	John Canny, Collision Detection for Moving Polyhedra, Massachusetts Institute of Technology, Cambridge, MA, 1984
	4	Ingrid Carlbom, An algorithm for geometric set operations using cellular subdivision techniques, IEEE Computer Graphics and Applications, v.7 n.5, p.44-55, May 1987 [doi>10.1109/MCG.1987.276987]
	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 PTR, Upper Saddle River, NJ, 1971
	9	Jeffrey Goldsmith , John Salmon, Automatic creation of object hierarchies for ray tracing, IEEE Computer Graphics and Applications, v.7 n.5, p.14-20, May 1987 [doi>10.1109/MCG.1987.276983]
	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 , Michael F. Cohen, Controlling dynamic simulation with kinematic constraints, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.215-224, July 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	Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
	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, Proceedings of the 9th annual conference on Computer graphics and interactive techniques, p.289-296, July 26-30, 1982, Boston, Massachusetts, United States
	24	Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.25-34, July 1987
	25	David F. Rogers, Procedural elements for computer graphics, McGraw-Hill, Inc., New York, NY, 1984
	26	Robert Skinner, U Cal. Santa Cruz, CIS Dept. personal communication.
	27	Scott N. Steketee , Norman I. Badler, Parametric keyframe interpolation incorporating kinetic adjustment and phrasing control, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.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 Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.205-214, July 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 realistic animation of articulated bodies, IEEE Computer Graphics and Applications, v.7 n.6, p.12-27, June 1987 [doi>10.1109/MCG.1987.276893]