Iterative algorithms are frequently used to resolve simultaneous impacts between rigid bodies in physical simulations. However, these algorithms lack formal guarantees of termination, which is sometimes viewed as potentially dangerous, so failsafes are used in practical codes to prevent infinite loops. We show such steps are unnecessary. In particular, we study the broad class of such algorithms that are conservative and satisfy a minimal set of physical correctness properties, and which encompasses recent methods like Generalized Reflections as well as pairwise schemes. We fully characterize finite termination of these algorithms. The only possible failure cases can be detected, and we describe a procedure for modifying the algorithms to provably ensure termination. We also describe modifications necessary to guarantee termination in the presence of numerical error due to the use of floating-point arithmetic. Finally, we discuss the challenges dissipation introduce for finite termination, and describe how dissipation models can be incorporated while retaining the termination guarantee.

All’s Well That Ends Well: Guaranteed Resolution of Simultaneous Rigid-Body Impact
Etienne Vouga, Breannan Smith, Danny M. Kaufman, Rasmus TamstorfEitan Grinspun
ACM Transactions on Graphics (Proceedings of SIGGRAPH 2017)


We consider the simulation of dense foams composed of microscopic bubbles, such as shaving cream and whipped cream. We represent foam not as a collection of discrete bubbles, but instead as a continuum. We employ the Material Point Method (MPM) to discretize a hyperelastic constitutive relation augmented with the Herschel-Bulkley model of non-Newtonian plastic flow, which is known to closely approximate foam behavior. Since large shearing flows in foam can produce poor distributions of material points, a typical MPM implementation can produce non-physical internal holes in the continuum. To address these artifacts, we introduce a particle resampling method for MPM. In addition, we introduce an explicit tearing model to prevent regions from shearing into artificially-thin, honey-like threads. We evaluate our method's efficacy by simulating a number of dense foams, and we validate our method by comparing to real-world footage of foam.

Continuum Foam: A Material Point Method for Shear-Dependent Flows
Yonghao Yue, Breannan Smith, Christopher Batty, Changxi Zheng, Eitan Grinspun
ACM Transactions on Graphics


We develop an algorithm for the efficient and stable simulation of large-scale elastic rod assemblies. We observe that the time-integration step is severely restricted by a strong nonlinearity in the response of stretching modes to transversal impact, the degree of this nonlinearity varying greatly with the shape of the rod. Building on these observations, we propose the ADONIS collision response algorithm that adapts the degree of nonlinearity in impact solves. We illustrate the advantages of the ADONIS algorithm by analyzing simulations involving elastic rod assemblies of varying density and scale, with up to 1.7 million individual contacts per time step.

Adaptive Nonlinearity for Collisions in Complex Rod Assemblies
Danny M. Kaufman, Rasmus Tamstorf, Breannan Smith, Jean-Marie Aubry, Eitan Grinspun
ACM Transactions on Graphics (Proceedings of SIGGRAPH 2014)


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.

Reflections on Simultaneous Impact
Breannan Smith, Danny M. Kaufman, Etienne Vouga, Rasmus Tamstorf, Eitan Grinspun
ACM Transactions on Graphics (Proceedings of SIGGRAPH 2012)


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.

Asynchronous Contact Mechanics
David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, Eitan Grinspun
ACM Transactions on Graphics (Proceedings of SIGGRAPH 2009)

Asynchronous Contact Mechanics
David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, Eitan Grinspun
Communications of the ACM, Volume 55, Issue 4, April 2012, Pages 102-109


Stress Communication in Viscoelastic Layers

Spatial Stress and Strain Distributions of Viscoelastic Layers in Oscillatory Shear
B. S. Lindley, M. G. Forest, B. D. Smith, S. M. Mitran, D. B. Hill
Mathematics and Computers in Simulation, Volume 82, Issue 7, March 2012, Pages 1249-1257

Stress Communication and Filtering of Viscoelastic Layers in Oscillatory Shear
B. Lindley, E. L. Howell, B. D. Smith, G. J. Rubinstein, M. G. Forest, S. M. Mitran, D. B. Hill, and R. Superfine
Journal of Non-Newtonian Fluid Mechanics, Volume 156, Issues 1-2, January 2009, Pages 112-120