skip to main content
research-article

Reflections on simultaneous impact

Published: 01 July 2012 Publication History

Abstract

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.

Supplementary Material

JPG File (tp219_12.jpg)
ZIP File (a106-smith.zip)
Supplemental material.
MP4 File (tp219_12.mp4)

References

[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.
[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.
[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.
[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.
[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.
[6]
Baraff, D. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Computer Graphics (SIGGRAPH 89), 223--232.
[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.
[8]
Bernoulli, J. 1742. Op. CLXXVII, Propositiones variæ Mechanico-dynamicæ. In Opera Omnia. 253--313.
[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.
[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.
[11]
Boyd, S., and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press.
[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.
[13]
Brogliato, B. 1999. Nonsmooth Mechanics: models, dynamics, and control, 2nd ed. Springer-Verlag.
[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.
[15]
Cottle, R. W., Pang, J. S., and Stone, R. E. 1992. The Linear Complementarity Problem. Academic Press.
[16]
D'Alembert, J. 1743. Traite de Dynamique.
[17]
Ericson, C. 2004. Real-Time Collision Detection. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
[18]
Erleben, K., and Dohlmann, H. 2007. Signed Distance Fields Using Single-Pass GPU Scan Conversion of Tetrahedra. In GPU Gems 3, 741--762.
[19]
Erleben, K. 2007. Velocity-based shock propagation for multi-body dynamics animation. ACM Trans. Graph. 26, 2.
[20]
Friedlander, M. P., 2007. BCLS: Bound Constrained Least Squares.
[21]
Glocker, C. 2004. Concepts for Modeling Impacts without Friction. Acta Mechanica 168, 1--19.
[22]
Goldfarb, D., and Idnani, G. 1983. A numerically stable dual method for solving strictly convex quadratic programs. Mathematical Programming 27, 1--33.
[23]
Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Non-convex Rigid Bodies with Stacking. ACM Trans. Graph. (SIGGRAPH 03) 22, 3, 871--878.
[24]
Hahn, J. K. 1988. Realistic animation of rigid bodies. In Computer Graphics (SIGGRAPH 88), 299--308.
[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.
[26]
Hairer, E., Lubich, C., and Wanner, G. 2002. Geometric numerical integration: Structure-Preserving Algorithms for Odinary Differential Equations. Springer.
[27]
Hairer, E., Lubich, C., and Wanner, G. 2002. Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations. Springer-Verlag.
[28]
Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust Treatment of Simultaneous Collisions. SIGGRAPH 08, ACM TOG.
[29]
Hascoët, E., Herrmann, H. J., and Loreto, V. 1999. Shock Propagation in a Granular Chain. Phys. Rev. E 59.
[30]
HSL. 2001. A collection of Fortran codes for large scale scientific computation. http://www.hsl.rl.ac.uk.
[31]
Ivanov, A. P. 1995. On Multiple Impact. Journal Applied Mathematics and Mechanics 59, 6, 887--902.
[32]
Johnson, W. 1976. Simple Linear Impact. Int. J. Mech. Eng. Educ. 4, 167--181.
[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.
[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.
[35]
Lawson, C. L., and Hanson, R. J. 1974. Solving least squares problems. Prentice-Hall.
[36]
Lenaerts, T., and Dutré, P. 2009. Mixing fluids and granular materials. Computer Graphics Forum 28, 2, 213--218.
[37]
Lubachevsky, B. 1991. How to Simulate Billiards and Similar Systems. Journal of Computational Physics 94, 255--283.
[38]
Luciani, A., Habibi, A., and Manzotti, E. 1995. A multi-scale physical model of granular materials. In Graph. Interf.
[39]
Maclaurin, C. 1742. A Treatise on Fluxions.
[40]
McNamara, S., and Young, W. R. 1994. Inelastic collapse in two dimensions. Phys. Rev. E 50, 1 (Jul), R28--R31.
[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.
[42]
Miller, G., and Pearce, A. 1989. Globular dynamics: A connected particle system for animating viscous fluids. Computers and Graphics 13, 3, 305--309.
[43]
Mirtich, B., and Canny, J. F. 1995. Impulse-based dynamic simulation of rigid bodies. In Symp. on Inter. 3D Graph.
[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.
[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.
[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.
[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.
[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).
[49]
Pöschel, T., and Schwager, T. 2005. Computational granular dynamics: models and algorithms. Springer-Verlag.
[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.
[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.
[52]
Smith, R. 2006. Open Dynamics Engine, V0.5, User Guide.
[53]
Stewart, D. E. 2000. Rigid-Body Dynamics with Friction and Impact. SIAM Rev. 42, 1, 3--39.
[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.
[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.
[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.
[57]
Witkin, A., and Baraff, D. 2001. Physically Based Modeling. In SIGGRAPH 2001 COURSE NOTES.
[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.
[59]
Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. (SIGGRAPH 05) 24 (July), 965--972.

Cited By

View all
  • (2024)Set-valued rigid-body dynamics for simultaneous, inelastic, frictional impactsThe International Journal of Robotics Research10.1177/0278364924123686043:10(1594-1628)Online publication date: 24-May-2024
  • (2024)Primal-Dual Non-Smooth Friction for Rigid Body AnimationACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657485(1-10)Online publication date: 13-Jul-2024
  • (2024)Determining predictable strike points on tossed objects: A 2D physics simulation approachEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.107268127(107268)Online publication date: Jan-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 31, Issue 4
July 2012
935 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/2185520
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2012
Published in TOG Volume 31, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. impact
  2. mechanics
  3. physics
  4. rigid bodies
  5. simulation

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)38
  • Downloads (Last 6 weeks)11
Reflects downloads up to 03 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Set-valued rigid-body dynamics for simultaneous, inelastic, frictional impactsThe International Journal of Robotics Research10.1177/0278364924123686043:10(1594-1628)Online publication date: 24-May-2024
  • (2024)Primal-Dual Non-Smooth Friction for Rigid Body AnimationACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657485(1-10)Online publication date: 13-Jul-2024
  • (2024)Determining predictable strike points on tossed objects: A 2D physics simulation approachEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.107268127(107268)Online publication date: Jan-2024
  • (2024)A novel collision model for inextensible textiles and its experimental validationApplied Mathematical Modelling10.1016/j.apm.2024.01.030128(287-308)Online publication date: Apr-2024
  • (2024)A quadratic programming based simultaneous impact model (QPSIM) for mechanismsSādhanā10.1007/s12046-024-02525-949:2Online publication date: 5-Jun-2024
  • (2024)3D Stochastic Simulation of Rockfall Mechanism and Mitigation in the Batseri ZoneGeotechnical and Geological Engineering10.1007/s10706-024-03035-543:1Online publication date: 5-Dec-2024
  • (2023)Unified treatment of contact, friction and shock-propagation in rigid body animationProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.1145/3606037.3606836(1-2)Online publication date: 4-Aug-2023
  • (2022)Generalized resampled importance samplingACM Transactions on Graphics10.1145/3528223.353015841:4(1-23)Online publication date: 22-Jul-2022
  • (2022)A unified newton barrier method for multibody dynamicsACM Transactions on Graphics10.1145/3528223.353007641:4(1-14)Online publication date: 22-Jul-2022
  • (2022)Affine body dynamicsACM Transactions on Graphics10.1145/3528223.353006441:4(1-14)Online publication date: 22-Jul-2022
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media