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

  • ©David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, and Eitan Grinspun




    Asynchronous contact mechanics



    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

ACM Digital Library Publication: