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

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