“Asynchronous contact mechanics” by Harmon, Vouga, Smith, Tamstorf and Grinspun

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.

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.Google ScholarCross Ref
2. Agarwal, P., Guibas, L., Nguyen, A., Russel, D., and Zhang, L. 2004. Collision detection for deforming necklaces. Computational Geometry: Theory and Applications 28, 137–163. Google ScholarDigital Library
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.Google Scholar
4. Ascher, U. M., and Petzold, L. R. 1998. Computer methods for ordinary differential equations and differential-algebraic equations. Society for Industrial and Applied Mathematics, Philadelphia. Google ScholarDigital Library
5. Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. ACM Trans. Graph. 22, 3, 862–870. Google ScholarDigital Library
6. Baraff, D. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In SIGGRAPH ’89: Proceedings of the 16th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 223–232. Google ScholarDigital Library
7. Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In SIGGRAPH ’94, 23–34. Google ScholarDigital Library
8. Basch, J., Guibas, L. J., and Zhang, L. 1997. Proximity problems on moving points. In Proc. 13th Annu. ACM Sympos. Comput. Geom., 344–351. Google ScholarDigital Library
9. Basch, J., Guibas, L. J., and Hershberger, J. 1999. Data structures for mobile data. Journal of Algorithms 31, 1–28. Google ScholarDigital Library
10. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. In SIGGRAPH ’02, 594–603. Google ScholarDigital Library
11. Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. In SCA ’03, 28–36. Google ScholarDigital Library
12. Brilliantov, N. V., and Pöschel, T. 2004. Kinetic Theory of Granular Gases. Oxford University Press, USA.Google Scholar
13. Celes, W. 1998. Efficient asynchronous evolution of physical simulations. In SIBGRAPI ’98: Proceedings of the International Symposium on Computer Graphics, Image Processing, and Vision, IEEE Computer Society, Washington, DC, USA, 224. Google ScholarDigital Library
14. Choi, K.-J., and Ko, H.-S. 2005. Stable but responsive cloth. In SIGGRAPH ’05: ACM SIGGRAPH 2005 Courses, ACM, New York, NY, USA, 1. Google ScholarDigital Library
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.Google ScholarCross Ref
16. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic real-time deformations using space & time adaptive sampling. In SIGGRAPH ’01: Proceedings of the 28th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 31–36. Google ScholarDigital Library
17. Dequidt, J., Grisoni, L., and Chaillou, C. 2004. Asynchronous interactive physical simulation. Tech. Rep. RR-5338, INRIA.Google Scholar
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.Google Scholar
19. English, E., and Bridson, R. 2008. Animating developable surfaces using nonconforming elements. In SIGGRAPH ’08: ACM SIGGRAPH 2008 papers, ACM, New York, NY, USA, 1–5. Google ScholarDigital Library
20. Erickson, J., Guibas, L. J., Stolfi, J., and Zhang, L. 1999. Separation-sensitive collision detection for convex objects. In Proc. 10th ACM-SIAM Symp. Discrete Algorithms, 102–111. Google ScholarDigital Library
21. Ericson, C. 2004. Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3D Technology). Morgan Kaufmann, December. Google ScholarDigital Library
22. Fong, W., Darve, E., and Lew, A. 2008. Stability of asynchronous variational integrators. J. Comput. Phys. 227, 18, 8367–8394. Google ScholarDigital Library
23. Gao, J., Guibas, L., Hershberger, J., Zhang, L., and Zhu, A. 2003. Discrete mobile centers. Discrete and Computational Geometry 30, 1, 45–65.Google ScholarCross Ref
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. Google ScholarDigital Library
25. Grinspun, E., Hirani, A., Desbrun, M., and Schröder, P. 2003. Discrete Shells. In ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 62–67. Google ScholarDigital Library
26. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Non-convex rigid bodies with stacking. In SIGGRAPH ’03: ACM SIGGRAPH 2003 Papers, ACM, New York, NY, USA, 871–878. Google ScholarDigital Library
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.Google Scholar
28. Guibas, L. J., Xie, F., and Zhang, L. 2001. Kinetic collision detection: Algorithms and experiments. In ICRA, 2903–2910.Google Scholar
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.Google Scholar
30. Guibas, L. J. 1998. Kinetic data structures — a state of the art report. In Proc. 3rd Workshop on Algorithmic Foundations of Robotics (WAFR), 191–209. Google ScholarDigital Library
31. Hahn, J. K. 1988. Realistic animation of rigid bodies. In SIGGRAPH ’88: Proceedings of the 15th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 299–308. Google ScholarDigital Library
32. Hairer, E., Lubich, C., and Wanner, G. 2002. Geometric Numerical Integration: Structure-preserving Algorithms for Ordinary Differential Equations. Springer.Google Scholar
33. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust Treatment of Simultaneous Collisions. SIGGRAPH (ACM Transactions on Graphics) 27, 3, 1–4. Google ScholarDigital Library
34. Johnson, K. L. 2008. Contact mechanics. Cambridge University Press.Google Scholar
35. Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. In SIGGRAPH ’05, 946–956. Google ScholarDigital Library
36. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered projections for frictional contact in multibody systems. In SIGGRAPH Asia ’08: ACM SIGGRAPH Asia 2008 papers, ACM, New York, NY, USA, 1–11. Google ScholarDigital Library
37. Kharevych, L., Yang, W., Tong, Y., Kanso, E., Marsden, J. E., Schröder, P., and Desbrun, M. 2006. Geometric, variational integrators for computer animation. In SCA ’06: Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 43–51. Google ScholarDigital Library
38. Klosowski, J. T., Held, M., Mitchell, J. S. B., Sowizral, H., and Zikan, K. 1998. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Transactions on Visualization and Computer Graphics 4, 1, 21–36. Google ScholarDigital Library
39. Konečný, P., and Zikan, K. 1997. Lower Bound of Distance in 3D. In Proceedings of WSCG 1997, vol. 3, 640–649.Google Scholar
40. Korneev, V., and Kiselev, A. 2004. Modern Microprocessors. Charles River Media. Google ScholarDigital Library
41. Lew, A., Marsden, J. E., Ortiz, M., and West, M. 2003. Asynchronous variational integrators. Archive for Rational Mechanics and Analysis 167, 85–146.Google ScholarCross Ref
42. Lubachevsky, B. 1991. How to simulate billiards and similar systems. Journal of Computational Physics 94, 2 (June), 255–283. Google ScholarDigital Library
43. Marsden, J., Patrick, G., and Shkoller, S. 1998. Multisymplectic Geometry, Variational Integrators, and Nonlinear PDEs. Communications in Mathematical Physics 199, 2, 351–395.Google ScholarCross Ref
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.Google ScholarCross Ref
45. Milenkovic, V. J., and Schmidl, H. 2001. Optimization-based animation. In SIGGRAPH ’01: Proceedings of the 28th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 37–46. Google ScholarDigital Library
46. Mirtich, B., and Canny, J. 1995. Impulse-based dynamic simulation. In WAFR: Proceedings of the workshop on Algorithmic foundations of robotics, A. K. Peters, Ltd., Natick, MA, USA, 407–418. Google ScholarDigital Library
47. Mirtich, B. 2000. Timewarp rigid body simulation. In SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 193–200. Google ScholarDigital Library
48. Pfeiffer, F., and Glocker, C., Eds. 2000. Multibody Dynamics With Unilateral Contacts. Springer Wien New York, ch. 2, 69–146.Google Scholar
49. Pöschel, T., and Schwager, T. 2005. Computational Granular Dynamics: Models and Algorithms. Springer.Google Scholar
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.Google Scholar
51. Schwager, T., and Pöschel, T. 2007. Coefficient of restitution and linear dashpot model revisited. Granular Matter 9, 6 (November), 465–469.Google ScholarCross Ref
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. Google ScholarDigital Library
53. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In SIGGRAPH ’87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 205–214. Google ScholarDigital Library
54. Thomaszewski, B., Pabst, S., and Strasser, W. 2008. Asynchronous cloth simulation. In Computer Graphics International.Google Scholar
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.Google ScholarCross Ref
56. Volino, P., and Magnenat-Thalmann, N. 2006. Resolving surface collisions through intersection contour minimization. In SIGGRAPH ’06: ACM SIGGRAPH 2006 Papers, ACM, New York, NY, USA, 1154–1159. Google ScholarDigital Library
57. Vouga, E., Harmon, D., Tamstorf, R., and Grinspun, E. 2009. Discrete penalty layers admit multisymplectic integration. Tech. rep., Columbia University.Google Scholar
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).Google Scholar
59. Wriggers, P., and Laursen, T. A. 2007. Computational contact mechanics, vol. no. 498 of CISM courses and lectures. Springer, Wien.Google Scholar
60. Wriggers, P., and Panagiotopoulos, P., Eds. 1999. New Developments in Contact Problems. Springer Wien New York, ch. 1, 1–54.Google Scholar
61. Zhong, G., and Marsden, J. E. 1988. Lie-Poisson Hamilton-Jacobi theory and Lie-Poisson integrators. Physics Letters A 133 (Nov.), 134–139.Google ScholarCross Ref