Asynchronous contact mechanics

ABSTRACT

We develop a method for reliable simulation of elastica in complex contact scenarios. Our focus is on firmly establishing three parameter-independent guarantees: that simulations of well-posed problems (a) have no interpenetrations, (b) obey causality, momentum- and energy-conservation laws, and (c) complete in finite time. We achieve these guarantees through a novel synthesis of asynchronous variational integrators, kinetic data structures, and a discretization of the contact barrier potential by an infinite sum of nested quadratic potentials. In a series of two- and three-dimensional examples, we illustrate that this method more easily handles challenging problems involving complex contact geometries, sharp features, and sliding during extremely tight contact.

REFERENCES

• 1: Agarwal, P., Basch, J., Guibas, L. J., Hershberger, J., and Zhang, L. 2002. Deformable free space tilings for kinetic collision detection. Intl. J. Robotics Research 21, 179--197.
• 2: Pankaj Agarwal , Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Computational Geometry: Theory and Applications, v.28 n.2-3, p.137-163, June 2004 [doi>10.1016/j.comgeo.2004.03.008]
• 3: Agarwal, P. K., Har-Peled, S., and Varadarajan, K. R. 2005. Geometric approximation via coresets. In Combinatorial and Computational Geometry, J. E. Goodman, J. Pach, and E. Welzl, Eds. Cambridge University Press, New York, 1--30.
• 4: Uri M. Ascher , Linda R. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998
• 5: David Baraff , Andrew Witkin , Michael Kass, Untangling cloth, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 6: D. Baraff, Analytical methods for dynamic simulation of non-penetrating rigid bodies, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.223-232, July 1989
• 7: David Baraff, Fast contact force computation for nonpenetrating rigid bodies, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.23-34, July 1994 [doi>10.1145/192161.192168]
• 8: Julien Basch , Leonidas J. Guibas , Li Zhang, Proximity problems on moving points, Proceedings of the thirteenth annual symposium on Computational geometry, p.344-351, June 04-06, 1997, Nice, France [doi>10.1145/262839.262998]
• 9: Julien Basch , Leonidas J. Guibas, Data structures for mobile data, Journal of Algorithms, v.31 n.1, p.1-28, April 1999 [doi>10.1006/jagm.1998.0988]
• 10: Robert Bridson , Ronald Fedkiw , John Anderson, Robust treatment of collisions, contact and friction for cloth animation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 11: R. Bridson , S. Marino , R. Fedkiw, Simulation of clothing with folds and wrinkles, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 12: Brilliantov, N. V., and Pöschel, T. 2004. Kinetic Theory of Granular Gases. Oxford University Press, USA.
• 13: W. Celes, Efficient Asynchronous Evolution of Physical Simulations, Proceedings of the International Symposium on Computer Graphics, Image Processing, and Vision, p.224, January 20-23, 1998 [doi>10.1109/SIBGRA.1998.722754]
• 14: Kwang-Jin Choi , Hyeong-Seok Ko, Stable but responsive cloth, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1198555.1198571]
• 15: Cirak, F., and West, M. 2005. Decomposition-based contact response (DCR) for explicit finite element dynamics. Int'l Journal for Numerical Methods in Engineering 64, 8, 1078--1110.
• 16: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 17: Dequidt, J., Grisoni, L., and Chaillou, C. 2004. Asynchronous interactive physical simulation. Tech. Rep. RR-5338, INRIA.
• 18: Eck, C., Janušek, J., and Krbec, M. 2005. Unilateral contact problems: variational methods and existence theorems. Chapman and Hall/CRC Press, Boca Raton.
• 19: Elliot English , Robert Bridson, Animating developable surfaces using nonconforming elements, ACM SIGGRAPH 2008 papers, August 11-15, 2008, Los Angeles, California
• 20: Jeff Erickson , Leonidas J. Guibas , Jorge Stolfi , Li Zhang, Separation-sensitive collision detection for convex objects, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.327-336, January 17-19, 1999, Baltimore, Maryland, United States
• 21: Christer Ericson, Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology) (The Morgan Kaufmann Series in Interactive 3D Technology), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 22: William Fong , Eric Darve , Adrian Lew, Stability of asynchronous variational integrators, Journal of Computational Physics, v.227 n.18, p.8367-8394, September, 2008 [doi>10.1016/j.jcp.2008.05.017]
• 23: Gao, J., Guibas, L., Hershberger, J., Zhang, L., and Zhu, A. 2003. Discrete mobile centers. Discrete and Computational Geometry 30, 1, 45--65.
• 24: Gao, J., Guibas, L. J., and Nguyen, A. 2005. Distributed proximity maintenance in ad hoc mobile network. In IEEE International Conference on Distributed Computing in Sensor System (DCOSS'05), 4--19.
• 25: Eitan Grinspun , Anil N. Hirani , Mathieu Desbrun , Peter Schröder, Discrete shells, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 26: Eran Guendelman , Robert Bridson , Ronald Fedkiw, Nonconvex rigid bodies with stacking, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 27: Guibas, L., Xie, F., and Zhang, L. 2001. Kinetic Collision detection: Algorithms and experiments. In Proceedings of the International Conference on Robotics and Automation, 2903--2910.
• 28: Guibas, L. J., Xie, F., and Zhang, L. 2001. Kinetic collision detection: Algorithms and experiments. In ICRA, 2903--2910.
• 29: Guibas, L., Karaveles, M., and Russel, D. 2004. A computational framework for handling motion. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments, 129--141.
• 30: Leonidas J. Guibas, Kinetic data structures: a state of the art report, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, p.191-209, August 1998, Houston, Texas, United States
• 31: James K. Hahn, Realistic animation of rigid bodies, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.299-308, June 1988
• 32: Hairer, E., Lubich, C., and Wanner, G. 2002. Geometric Numerical Integration: Structure-preserving Algorithms for Ordinary Differential Equations. Springer.
• 33: David Harmon , Etienne Vouga , Rasmus Tamstorf , Eitan Grinspun, Robust treatment of simultaneous collisions, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 34: Johnson, K. L. 2008. Contact mechanics. Cambridge University Press.
• 35: Danny M. Kaufman , Timothy Edmunds , Dinesh K. Pai, Fast frictional dynamics for rigid bodies, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 36: Danny M. Kaufman , Shinjiro Sueda , Doug L. James , Dinesh K. Pai, Staggered projections for frictional contact in multibody systems, ACM SIGGRAPH Asia 2008 papers, December 10-13, 2008, Singapore
• 37: L. Kharevych , Weiwei Yang , Y. Tong , E. Kanso , J. E. Marsden , P. Schröder , M. Desbrun, Geometric, variational integrators for computer animation, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
• 38: 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 [doi>10.1109/2945.675649]
• 39: Konečný, P., and Zikan, K. 1997. Lower Bound of Distance in 3D. In Proceedings of WSCG 1997, vol. 3, 640--649.
• 40: Kiselev Korneev , Victor Korneev , Andrew Kiselev, Modern Microprocessors (Computer Engineering Series), Charles River Media, Inc., Rockland, MA, 2004
• 41: Lew, A., Marsden, J. E., Ortiz, M., and West, M. 2003. Asynchronous variational integrators. Archive for Rational Mechanics and Analysis 167, 85--146.
• 42: Boris D. Lubachevsky, How to simulate billiards and similar systems, Journal of Computational Physics, v.94 n.2, p.255-283, May 1991 [doi>10.1016/0021-9991(91)90222-7]
• 43: Marsden, J., Patrick, G., and Shkoller, S. 1998. Multisymplectic Geometry, Variational Integrators, and Nonlinear PDEs. Communications in Mathematical Physics 199, 2, 351--395.
• 44: Marsden, J., Pekarsky, S., Shkoller, S., and West, M. 2001. Variational methods, multisymplectic geometry and contiunuum mechanics. Journal of Geometry and Physics 38, 3--4 (June), 253--284.
• 45: 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 [doi>10.1145/383259.383263]
• 46: Brian Mirtich , John Canny, Impulse-based dynamic simulation, Proceedings of the workshop on Algorithmic foundations of robotics, p.407-418, May 1995, San Francisco, California, United States
• 47: Brian Mirtich, Timewarp rigid body simulation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.193-200, July 2000 [doi>10.1145/344779.344866]
• 48: Pfeiffer, F., and Glocker, C., Eds. 2000. Multibody Dynamics With Unilateral Contacts. Springer Wien New York, ch. 2, 69--146.
• 49: Pöschel, T., and Schwager, T. 2005. Computational Granular Dynamics: Models and Algorithms. Springer.
• 50: Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation '97, Springer Verlag, Wien, 177--189.
• 51: Schwager, T., and Pöschel, T. 2007. Coefficient of restitution and linear dashpot model revisited. Granular Matter 9, 6 (November), 465--469.
• 52: Sifakis, E., Marino, S., and Teran, J. 2008. Globally coupled collision handling using volume preserving impulses. In 2008 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 147--154.
• 53: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.205-214, August 1987
• 54: Thomaszewski, B., Pabst, S., and Strasser, W. 2008. Asynchronous cloth simulation. In Computer Graphics International.
• 55: Trinkle, D. S. J. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction. Intl. Journal for Numerical Methods in Engineering 39, 2673--2691.
• 56: Pascal Volino , Nadia Magnenat-Thalmann, Resolving surface collisions through intersection contour minimization, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 57: Vouga, E., Harmon, D., Tamstorf, R., and Grinspun, E. 2009. Discrete penalty layers admit multisymplectic integration. Tech. rep., Columbia University.
• 58: Weller, R., and Zachmann, G. 2006. Kinetic separation lists for continuous collision detection of deformable objects. In Third Workshop in Virtual Reality Interactions and Physical Simulation (Vriphys).
• 59: Wriggers, P., and Laursen, T. A. 2007. Computational contact mechanics, vol. no. 498 of CISM courses and lectures. Springer, Wien.
• 60: Wriggers, P., and Panagiotopoulos, P., Eds. 1999. New Developments in Contact Problems. Springer Wien New York, ch. 1, 1--54.
• 61: Zhong, G., and Marsden, J. E. 1988. Lie-Poisson Hamilton-Jacobi theory and Lie-Poisson integrators. Physics Letters A 133 (Nov.), 134--139.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Keywords:
collision, contact, simulation, symplectic, variational