Fast contact force computation for nonpenetrating rigid bodies

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast contact force computation for nonpenetrating rigid bodies

Full text

Pdf (1.51 MB),

Ps (396 KB)

Source

International Conference on Computer Graphics and Interactive Techniques archive
Proceedings of the 21st annual conference on Computer graphics and interactive techniques table of contents

Pages: 23 - 34

Year of Publication: 1994

ISBN:0-89791-667-0

Author

David Baraff

Robotics Institute, Carnegie Mellon University, Pittsburgh, PA

Sponsor

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 22, Downloads (12 Months): 134, Citation Count: 56

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/192161.192168 What is a DOI?

ABSTRACT

A new algorithm for computing contact forces between solid objects with friction is presented. The algorithm allows a mix of contact points with static and dynamic friction. In contrast to previous approaches, the problem of computing contact forces is not transformed into an optimization problem. Because of this, the need for sophisticated optimization software packages is eliminated. For both systems with and without friction, the algorithm has proven to be considerably faster, simple, and more reliable than previous approaches to the problem. In particular, implementation of the algorithm by nonspecialists in numerical programming is quite feasible.

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	D. Baraff, Analytical methods for dynamic simulation of non-penetrating rigid bodies, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.223-232, July 1989
	2	David Baraff, Curved surfaces and coherence for non-penetrating rigid body simulation, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.19-28, Aug. 1990
	3	D. Baraff. Issues in computing contact forces for non-penetrating rigid bodies. Algorithmica, 10:292-352, 1993.
	4	R.W. Cottle and G.B. Dantzig. Complementary pivot theory of mathematical programming. Linear Algebra and its Appli-cations, 1:103-125, 1968.
	5	R.W. Cottle, J.S. Pang, and R.E. Stone. The Linear Comple-mentarity Problem. Academic-Press, Inc., 1992.
	6	P. Gill, S. Hammarling, W. Murray, M. Saunders, and M. Wright. User's guide for LSSOL: A Fortran package for constrained linear least-squares and convex quadratic pro-gramming. Technical Report Sol 86-1, Systems Optimiza-tion Laboratory, Department of Operations Research, Stanford University, 1986.
	7	P. Gill, W. Murray, M. Saunders, and M. Wright. User's guide for QPSOL: A Fortran package for quadratic programming. Technical Report Sol 84-6, Systems Optimization Labora-tory, Department of Operations Research, Stanford University, 1984.
	8	P. Gill, W. Murray, M. Saunders, and M. Wright. User's guide for NPSOL: A Fortran package for nonlinear programming. Technical Report Sol 86-2, Systems Optimization Labora-tory, Department of Operations Research, Stanford University, 1986.
	9	P.E. Gill, W. Murray, M.A. Saunders, and H.W. Wright. Main-taining LU factors of a general sparse matrix. Linear Algebra and its Applications, 88/89:239-270, 1987.
	10	P. L~ otstedt. Numerical simulation of time-dependent contact friction problems in rigid body mechanics. SIAM Journal of Scientific Statistical Computing, 5(2):370-393, 1984.
	11	Roy E. Marsten, The Design of the XMP Linear Programming Library, ACM Transactions on Mathematical Software (TOMS), v.7 n.4, p.481-497, Dec. 1981 [doi>10.1145/355972.355976]
	12	B. Murtagh and M. Saunders. MINOS 5.1 User's guide. Technical Report Sol 83-20R, Systems Optimization Labora-tory, Department of Operations Research, Stanford University, 1987.
	13	M. Saunders. Personal communication. September 1993.

CITED BY 56

	Greg J. Badros , Alan Borning , Peter J. Stuckey, The Cassowary linear arithmetic constraint solving algorithm, ACM Transactions on Computer-Human Interaction (TOCHI), v.8 n.4, p.267-306, December 2001
	Mikako Harada , Andrew Witkin , David Baraff, Interactive physically-based manipulation of discrete/continuous models, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.199-208, September 1995
	Benjamin Bishop , Thomas P. Kelliher , Mary Jane Irwin, SPARTA: Simulation of Physics on a Real-Time Architecture, Proceedings of the 10th Great Lakes symposium on VLSI, p.177-182, March 02-04, 2000, Chicago, Illinois, United States
	Victor J. Milenkovic , Harald Schmidl, Optimization-based animation, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.37-46, August 2001
	Alan Borning , Kim Marriott , Peter Stuckey , Yi Xiao, Solving linear arithmetic constraints for user interface applications, Proceedings of the 10th annual ACM symposium on User interface software and technology, p.87-96, October 14-17, 1997, Banff, Alberta, Canada
	David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998
	Young J. Kim , Miguel A. Otaduy , Ming C. Lin , Dinesh Manocha, Fast penetration depth computation for physically-based animation, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas
	G. Hotz , A. Kerzmann , C. Lennerz , R. Schmid , E. Schömer , T. Warken, Calculation of contact forces, Proceedings of the ACM symposium on Virtual reality software and technology, p.180-181, December 20-22, 1999, London, United Kingdom
	Jovan Popović , Steven M. Seitz , Michael Erdmann , Zoran Popović , Andrew Witkin, Interactive manipulation of rigid body simulations, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.209-217, July 2000
	Nathan Hurst , Kim Marriott , Peter Moulder, Dynamic approximation of complex graphical constraints by linear constraints, Proceedings of the 15th annual ACM symposium on User interface software and technology, October 27-30, 2002, Paris, France
	Brian Mirtich, Timewarp rigid body simulation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.193-200, July 2000
	Victor J. Milenkovic, Position-based physics: simulating the motion of many highly interacting spheres and polyhedra, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.129-136, August 1996
	William A. McNeely , Kevin D. Puterbaugh , James J. Troy, Six degree-of-freedom haptic rendering using voxel sampling, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.401-408, July 1999
	David E. Johnson , Peter Willemsen , Elaine Cohen, Six Degree-of-Freedom Haptic Rendering Using Spatialized Normal Cone Search, IEEE Transactions on Visualization and Computer Graphics, v.11 n.6, p.661-670, November 2005
	David Baraff, Linear-time dynamics using Lagrange multipliers, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.137-146, August 1996
	Yoshifumi Kitamura , Susumu Ogata , Fumio Kishino, A manipulation environment of virtual and real objects using a magnetic metaphor, Proceedings of the ACM symposium on Virtual reality software and technology, November 11-13, 2002, Hong Kong, China
	Young J. Kim , Miguel A. Otaduy , Ming C. Lin , Dinesh Manocha, Six-degree-of-freedom haptic rendering using incremental and localized computations, Presence: Teleoperators and Virtual Environments, v.12 n.3, p.277-295, 1 June 2003
	Jovan Popović , Steven M. Seitz , Michael Erdmann, Motion sketching for control of rigid-body simulations, ACM Transactions on Graphics (TOG), v.22 n.4, p.1034-1054, October 2003
	Richard W. Bukowski , Carlo H. Séquin, Object associations: a simple and practical approach to virtual 3D manipulation, Proceedings of the 1995 symposium on Interactive 3D graphics, p.131-ff., April 09-12, 1995, Monterey, California, United States
	Sumantro Ray , Hong Qin, Novel solver for dynamic surfaces, No description on Graphics interface 2001, p.47-54, June 07-09, 2001, Ottawa, Ontario, Canada
	François Faure, Fast Iterative Refinement of Articulated Solid Dynamics, IEEE Transactions on Visualization and Computer Graphics, v.5 n.3, p.268-276, July 1999
	Harald Schmidl , Victor J. Milenkovic, A Fast Impulsive Contact Suite for Rigid Body Simulation, IEEE Transactions on Visualization and Computer Graphics, v.10 n.2, p.189-197, March 2004
	Qi Luo , Jing Xiao, Physically Accurate Haptic Rendering with Dynamic Effects, IEEE Computer Graphics and Applications, v.24 n.6, p.60-69, November 2004
	Mark Pauly , Dinesh K. Pai , Leonidas J. Guibas, Quasi-rigid objects in contact, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France
	Eran Guendelman , Andrew Selle , Frank Losasso , Ronald Fedkiw, Coupling water and smoke to thin deformable and rigid shells, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
	James T. Klosowski , Martin Held , Joseph S. B. Mitchell , Henry Sowizral , Karel Zikan, Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs, IEEE Transactions on Visualization and Computer Graphics, v.4 n.1, p.21-36, January 1998
	David Baraff, Interactive Simulation of Solid Rigid Bodies, IEEE Computer Graphics and Applications, v.15 n.3, p.63-75, May 1995
	Danny M. Kaufman , Timothy Edmunds , Dinesh K. Pai, Fast frictional dynamics for rigid bodies, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
	Eran Guendelman , Robert Bridson , Ronald Fedkiw, Nonconvex rigid bodies with stacking, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	Paul G. Kry , Dinesh K. Pai, Interaction capture and synthesis, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	Robert Bridson , Ronald Fedkiw , John Anderson, Robust treatment of collisions, contact and friction for cloth animation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	William A. McNeely , Kevin D. Puterbaugh , James J. Troy, Six degree-of-freedom haptic rendering using voxel sampling, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Robert Bridson , Ronald Fedkiw , John Anderson, Robust treatment of collisions, contact and friction for cloth animation, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Miguel A. Otaduy , Ming C. Lin, Introduction to haptic rendering, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Hyungi Kim , Maenghyo Cho, Fast update of elastic body simulation under impact load by efficient reduction method, Advances in Engineering Software, v.38 n.3, p.193-211, March, 2007
	Christopher D. Twigg , Doug L. James, Many-worlds browsing for control of multibody dynamics, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
	Doug L. James , Christopher D. Twigg , Andrew Cove , Robert Y. Wang, Mesh Ensemble Motion Graphs: Data-driven mesh animation with constraints, ACM Transactions on Graphics (TOG), v.26 n.4, p.17-es, October 2007
	A. V. Anisimov , S. F. Zabaryanskii, Simulation of Motion of a Collection of Rigid Bodies, Taking into Account Their Collisions and Joints, Cybernetics and Systems Analysis, v.41 n.4, p.500-508, July 2005
	Wilhelm F. (Wilfred) van der Vegte , Joris S. M. Vergeest , Imre Horváth, Towards A Unified Description Of Product Related Processes, Journal of Integrated Design & Process Science, v.5 n.2, p.53-63, April 2001
	Chih-Hao Ho , Cagatay Basdogan , Mandayam A. Srinivasan, Efficient Point-Based Rendering Techniques for Haptic Display of Virtual Objects, Presence: Teleoperators and Virtual Environments, v.8 n.5, p.477-491, October 1999
	Yasuyoshi Yokokohji , Ralph L. Hollis , Takeo Kanade, WYSIWYF Display: A Visual/Haptic Interface to Virtual Environment, Presence: Teleoperators and Virtual Environments, v.8 n.4, p.412-434, August 1999
	Arthur Gregory , Ajith Mascarenhas , Stephen Ehmann , Ming Lin , Dinesh Manocha, Six degree-of-freedom haptic display of polygonal models, Proceedings of the conference on Visualization '00, p.139-146, October 2000, Salt Lake City, Utah, United States
	Terry L. Huntsberger , Abhijit Sengupta, Game theory basis for control of long-lived lunar/planetary surface robots, Autonomous Robots, v.20 n.2, p.85-95, March 2006
	O. Bruneau , F. B. Ouezdou, Distributed ground/walking robot interaction, Robotica, v.17 n.3, p.313-323, May 1999
	Christian Duriez , Frederic Dubois , Abderrahmane Kheddar , Claude Andriot, Realistic Haptic Rendering of Interacting Deformable Objects in Virtual Environments, IEEE Transactions on Visualization and Computer Graphics, v.12 n.1, p.36-47, January 2006
	Andrew D. Wilson , Shahram Izadi , Otmar Hilliges , Armando Garcia-Mendoza , David Kirk, Bringing physics to the surface, Proceedings of the 21st annual ACM symposium on User interface software and technology, October 19-22, 2008, Monterey, CA, USA
	Rafael de Sousa Rocha , Maria Andréia Formico Rodrigues, An evaluation of a collision handling system using sphere-trees for plausible rigid body animation, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	Evan Drumwright, A Fast and Stable Penalty Method for Rigid Body Simulation, IEEE Transactions on Visualization and Computer Graphics, v.14 n.1, p.231-240, January 2008
	Christopher D. Twigg , Doug L. James, Backward steps in rigid body simulation, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
	Marco da Silva , Yeuhi Abe , Jovan Popović, Interactive simulation of stylized human locomotion, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
	Danny M. Kaufman , Shinjiro Sueda , Doug L. James , Dinesh K. Pai, Staggered projections for frictional contact in multibody systems, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
	David Harmon , Etienne Vouga , Rasmus Tamstorf , Eitan Grinspun, Robust treatment of simultaneous collisions, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
	Bernhard Thomaszewski , Andreas Gumann , Simon Pabst , Wolfgang Straßer, Magnets in motion, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
	Evan Drumwright , Dylan A. Shell, A robust and tractable contact model for dynamic robotic simulation, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Chris Truszkowski , Benjamin Bishop, GPU-based spatial interaction force simulation, Proceedings of the 46th Annual Southeast Regional Conference on XX, March 28-29, 2008, Auburn, Alabama
	David Harmon , Etienne Vouga , Breannan Smith , Rasmus Tamstorf , Eitan Grinspun, Asynchronous contact mechanics, ACM Transactions on Graphics (TOG), v.28 n.3, August 2009