“Reflections on simultaneous impact” by Smith, Kaufman, Vouga, Tamstorf and Grinspun

  • ©Breannan Smith, Danny M. Kaufman, Etienne Vouga, Rasmus Tamstorf, and Eitan Grinspun




    Reflections on simultaneous impact



    Resolving simultaneous impacts is an open and significant problem in collision response modeling. Existing algorithms in this domain fail to fulfill at least one of five physical desiderata. To address this we present a simple generalized impact model motivated by both the successes and pitfalls of two popular approaches: pair-wise propagation and linear complementarity models. Our algorithm is the first to satisfy all identified desiderata, including simultaneously guaranteeing symmetry preservation, kinetic energy conservation, and allowing break-away. Furthermore, we address the associated problem of inelastic collapse, proposing a complementary generalized restitution model that eliminates this source of nontermination. We then consider the application of our models to the synchronous time-integration of large-scale assemblies of impacting rigid bodies. To enable such simulations we formulate a consistent frictional impact model that continues to satisfy the desiderata. Finally, we validate our proposed algorithm by correctly capturing the observed characteristics of physical experiments including the phenomenon of extended patterns in vertically oscillated granular materials.


    1. Alduán, I., and Otaduy, M. A. 2011. SPH granular flow with friction and cohesion. In Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, New York, NY, USA, SCA ’11, 25–32. Google ScholarDigital Library
    2. Alduán, I., Tena, A., and Otaduy, M. A. 2009. Simulation of High-Resolution Granular Media. In Proc. of Congreso Español de Informática Gráfica.Google Scholar
    3. Amestoy, P. R., Duff, I. S., Koster, J., and L’Excellent, J.-Y. 2001. A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM Journal on Matrix Analysis and Applications 23, 1, 15–41. Google ScholarDigital Library
    4. Amestoy, P. R., Guermouche, A., L’Excellent, J.-Y., and Pralet, S. 2006. Hybrid scheduling for the parallel solution of linear systems. Parallel Computing 32, 2, 136–156. Google ScholarDigital Library
    5. Anitescu, M., and Potra, F. R. 1997. Formulating Dynamic Multirigid-Body Contact Problems with Friction as Solvable Linear Complementarity Problems. ASME Nonlinear Dynamics 14, 231–247.Google ScholarCross Ref
    6. Baraff, D. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Computer Graphics (SIGGRAPH 89), 223–232. Google ScholarDigital Library
    7. Bell, N., Yu, Y., and Mucha, P. J. 2005. Particle-based simulation of granular materials. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, ACM, New York, NY, USA, SCA ’05, 77–86. Google ScholarDigital Library
    8. Bernoulli, J. 1742. Op. CLXXVII, Propositiones variæ Mechanico-dynamicæ. In Opera Omnia. 253–313.Google Scholar
    9. Bernu, B., and Mazighi, R. 1990. One-Dimensional Bounce of Inelastically Colliding Marbles on a Wall. Journal of Physics A: Mathematical and General 23, 24, 5745–5754.Google ScholarCross Ref
    10. Bizon, C., Shattuck, M. D., Swift, J. B., McCormick, W. D., and Swinney, H. L. 1998. Patterns in 3d vertically oscillated granular layers: Simulation and experiment. Phys. Rev. Lett. 80, 1 (Jan), 57–60.Google ScholarCross Ref
    11. Boyd, S., and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press. Google ScholarDigital Library
    12. Bridson, R., Fedkiw, R. P., and Anderson, J. 2002. Robust Treatment of Collisions, Contact, and Friction for Cloth Animation. ACM Trans. Graph. (SIGGRAPH 02) 21, 3 (July), 594–603. Google ScholarDigital Library
    13. Brogliato, B. 1999. Nonsmooth Mechanics: models, dynamics, and control, 2nd ed. Springer-Verlag.Google Scholar
    14. Chatterjee, A., and Ruina, A. L. 1998. A New Algebraic Rigid-Body Collision Law Based on Impulse Space Considerations. Journal of Applied Mechanics 65, 4, 939–951.Google ScholarCross Ref
    15. Cottle, R. W., Pang, J. S., and Stone, R. E. 1992. The Linear Complementarity Problem. Academic Press.Google Scholar
    16. D’Alembert, J. 1743. Traite de Dynamique.Google Scholar
    17. Ericson, C. 2004. Real-Time Collision Detection. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Google ScholarDigital Library
    18. Erleben, K., and Dohlmann, H. 2007. Signed Distance Fields Using Single-Pass GPU Scan Conversion of Tetrahedra. In GPU Gems 3, 741–762.Google Scholar
    19. Erleben, K. 2007. Velocity-based shock propagation for multi-body dynamics animation. ACM Trans. Graph. 26, 2. Google ScholarDigital Library
    20. Friedlander, M. P., 2007. BCLS: Bound Constrained Least Squares.Google Scholar
    21. Glocker, C. 2004. Concepts for Modeling Impacts without Friction. Acta Mechanica 168, 1–19.Google ScholarCross Ref
    22. Goldfarb, D., and Idnani, G. 1983. A numerically stable dual method for solving strictly convex quadratic programs. Mathematical Programming 27, 1–33.Google ScholarDigital Library
    23. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Non-convex Rigid Bodies with Stacking. ACM Trans. Graph. (SIGGRAPH 03) 22, 3, 871–878. Google ScholarDigital Library
    24. Hahn, J. K. 1988. Realistic animation of rigid bodies. In Computer Graphics (SIGGRAPH 88), 299–308. Google ScholarDigital Library
    25. Hairer, E., and Vilmart, G. 2006. Preprocessed discrete Moser–Veselov algorithm for the full dynamics of a rigid body. Journal of Physics A: Mathematical and General 39, 42, 13225.Google ScholarCross Ref
    26. Hairer, E., Lubich, C., and Wanner, G. 2002. Geometric numerical integration: Structure-Preserving Algorithms for Odinary Differential Equations. Springer.Google Scholar
    27. Hairer, E., Lubich, C., and Wanner, G. 2002. Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations. Springer-Verlag.Google Scholar
    28. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust Treatment of Simultaneous Collisions. SIGGRAPH 08, ACM TOG. Google ScholarDigital Library
    29. Hascoët, E., Herrmann, H. J., and Loreto, V. 1999. Shock Propagation in a Granular Chain. Phys. Rev. E 59.Google ScholarCross Ref
    30. HSL. 2001. A collection of Fortran codes for large scale scientific computation. http://www.hsl.rl.ac.uk.Google Scholar
    31. Ivanov, A. P. 1995. On Multiple Impact. Journal Applied Mathematics and Mechanics 59, 6, 887–902.Google ScholarCross Ref
    32. Johnson, W. 1976. Simple Linear Impact. Int. J. Mech. Eng. Educ. 4, 167–181.Google Scholar
    33. Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. ACM TOG (SIGGRAPH 05) 24, 3, 946–956. Google ScholarDigital Library
    34. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered Projections for Frictional Contact in Multibody Systems. ACM TOG (SIGGRAPH Asia 08) 27, 5, 1–11. Google ScholarDigital Library
    35. Lawson, C. L., and Hanson, R. J. 1974. Solving least squares problems. Prentice-Hall.Google Scholar
    36. Lenaerts, T., and Dutré, P. 2009. Mixing fluids and granular materials. Computer Graphics Forum 28, 2, 213–218.Google ScholarCross Ref
    37. Lubachevsky, B. 1991. How to Simulate Billiards and Similar Systems. Journal of Computational Physics 94, 255–283. Google ScholarDigital Library
    38. Luciani, A., Habibi, A., and Manzotti, E. 1995. A multi-scale physical model of granular materials. In Graph. Interf.Google Scholar
    39. Maclaurin, C. 1742. A Treatise on Fluxions.Google Scholar
    40. McNamara, S., and Young, W. R. 1994. Inelastic collapse in two dimensions. Phys. Rev. E 50, 1 (Jul), R28–R31.Google ScholarCross Ref
    41. Melo, F., Umbanhowar, P., and Swinney, H. L. 1994. Transition to parametric wave patterns in a vertically oscillated granular layer. Phys. Rev. Lett. 72, 1 (Jan), 172–175.Google ScholarCross Ref
    42. Miller, G., and Pearce, A. 1989. Globular dynamics: A connected particle system for animating viscous fluids. Computers and Graphics 13, 3, 305–309.Google ScholarCross Ref
    43. Mirtich, B., and Canny, J. F. 1995. Impulse-based dynamic simulation of rigid bodies. In Symp. on Inter. 3D Graph. Google ScholarDigital Library
    44. Moon, S. J., Swift, J. B., and Swinney, H. L. 2004. Role of friction in pattern formation in oscillated granular layers. Phys. Rev. E 69, 3 (Mar), 031301.Google ScholarCross Ref
    45. Moreau, J. J. 1983. Unilateral Problems in Structural Analysis. International Centre for Mechanical Sciences, Courses and Lectures – No. 288. ch. Standard Inelastic Shocks and the Dynamics of Unilateral Constraints., 173–221.Google Scholar
    46. Moreau, J. J. 1988. Unilateral Contact and Dry Friction in Finite Freedom Dynamics. Nonsmooth Mechanics and Applications, CISM Courses and Lectures, 302, 1–82.Google Scholar
    47. Moser, and Veselov. 1991. Discrete Versions of Some Classical Integrable Systems and Factorization of Matrix Polynomials. Communications in Mathematical Physics 139, 2, 217–243.Google ScholarCross Ref
    48. Narain, R., Golas, A., and Lin, M. C. 2010. Free-Flowing Granular Materials with Two-Way Solid Coupling. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2010). Google ScholarDigital Library
    49. Pöschel, T., and Schwager, T. 2005. Computational granular dynamics: models and algorithms. Springer-Verlag.Google Scholar
    50. Pudasaini, S. P., and Kröner, C. 2008. Shock waves in rapid flows of dense granular materials: Theoretical predictions and experimental results. Phys. Rev. E 78 (Oct), 041308.Google ScholarCross Ref
    51. Schittkowski, K. 2005. QL: A Fortran code for convex quadratic programming – User’s guide, Version 2.11. Report, Department of Mathematics, University of Bayreuth.Google Scholar
    52. Smith, R. 2006. Open Dynamics Engine, V0.5, User Guide.Google Scholar
    53. Stewart, D. E. 2000. Rigid-Body Dynamics with Friction and Impact. SIAM Rev. 42, 1, 3–39. Google ScholarDigital Library
    54. Umbanhowar, P. B., Melo, F., and Swinney, H. L. 1996. Localized excitations in a vertically vibrated granular layer. Nature 382 (8/1996), 793–796.Google Scholar
    55. van der Weele, K., van der Meer, D., Versluis, M., and Lohse, D. 2001. Hysteretic clustering in granular gas. EPL (Europhysics Letters) 53, 3, 328.Google Scholar
    56. Wächter, A., and Biegler, L. T. 2006. On the Implementation of an Interior-Point Filter Line-Search Algorithm for Large-Scale Nonlinear Programming. Mathematical Programming 106, 25–57. Google ScholarDigital Library
    57. Witkin, A., and Baraff, D. 2001. Physically Based Modeling. In SIGGRAPH 2001 COURSE NOTES.Google Scholar
    58. Zhong, G., and Marsden, J. E. 1988. Lie-Poisson Hamilton-Jacobi theory and Lie-Poisson integrators. Physics Letters A 133, 3 (Nov), 134–139.Google ScholarCross Ref
    59. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. (SIGGRAPH 05) 24 (July), 965–972. Google ScholarDigital Library

ACM Digital Library Publication: