There are three steps to transforming an observed phenomenon into a simulation, and at each step some amount of accuracy is lost in translation.

First, scientists devise mathematical models that capture the observed behavior.

Next, these smooth equations are

Finally, numerical algorithms are developed to solve these discrete equations accurately and efficiently using finite-precision arithmetic.

My research focus is in that middle step: the

Click the project titles or thumbnails to go to the project page/paper.

First, scientists devise mathematical models that capture the observed behavior.

Next, these smooth equations are

*discretized*: replaced with approximate equations involving only a finite amount of data.Finally, numerical algorithms are developed to solve these discrete equations accurately and efficiently using finite-precision arithmetic.

My research focus is in that middle step: the

*approximation of smooth physical models by discrete ones*. I'm particularly interested in the physics of everyday thin, elastic, deformable objects, like cloth, hair, paper, or leaves: how they deform, how they stretch, and how they collide. It turns out that the behavior of such objects is tied in a deep and fundamental way to their geometry: by understanding their essential geometric properties, we can build new algorithms that are more efficient and*and*more accurate at predicting how they behave.Click the project titles or thumbnails to go to the project page/paper.

All's Well That Ends Well: Guaranteed Resolution of Simultaneous Rigid Body ImpactEtienne Vouga, Breannan Smith, Danny M. Kaufman, Rasmus Tamstorf, Eitan Grinspun SIGGRAPH (ACM Transactions on Graphics), 2017 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. |

Simit: A Language for Physical SimulationFredrik Kjolstad, Shoaib Kamil, Jonathan Ragan-Kelley, David I. W. Levin, Shinjiro Sueda, Desai Chen, Etienne Vouga, Danny M. Kaufman, Gurtej Kanwar, Wojciech Matusik, and Saman Amarasinghe ACM Transactions on Graphics, 2016 With existing programming tools, writing high-performance simulation code is labor intensive and requires sacrificing readability and portability. The alternative is to prototype simulations in a high-level language like Matlab, thereby sacrificing performance. The Matlab programming model naturally describes the behavior of an entire physical system using the language of linear algebra. However, simulations also manipulate individual geometric elements, which are best represented using linked data structures like meshes. Translating between the linked data structures and linear algebra comes at significant cost, both to the programmer and to the machine. High-performance implementations avoid the cost by rephrasing the computation in terms of linked or index data structures, leaving the code complicated and monolithic, often increasing its size by an order of magnitude. In this article, we present Simit, a new language for physical simulations that lets the programmer view the system both as a linked data structure in the form of a hypergraph and as a set of global vectors, matrices, and tensors depending on what is convenient at any given time. Simit provides a novel assembly construct that makes it conceptually easy and computationally efficient to move between the two abstractions. Using the information provided by the assembly construct, the compiler generates efficient in-place computation on the graph. We demonstrate that Simit is easy to use: a Simit program is typically shorter than a Matlab program; that it is high performance: a Simit program running sequentially on a CPU performs comparably to hand-optimized simulations; and that it is portable: Simit programs can be compiled for GPUs with no change to the program, delivering 4 to 20× speedups over our optimized CPU code. |

Speculative Parallel Asynchronous Contact MechanicsSamantha Ainsley, Etienne Vouga, Eitan Grinspun, and Rasmus Tamstorf SIGGRAPH Asia ( ACM Transactions on Graphics ), 2012 We extend the Asynchronous Contact Mechanics algorithm and improve its performance by two orders of magnitude, using only optimizations that do not compromise ACM's three guarantees of safety, progress, and correctness. The key to this speedup is replacing ACM's timid, forward-looking mechanism for detecting collisions--locating and rescheduling separating plane kinetic data structures--with an optimistic speculative method inspired by Mirtich's rigid body Time Warp algorithm. Time warp allows us to perform collision detection over a window of time containing many of ACM's asynchronous trajectory changes; in this way we cull away large intervals as being collision free. Moreover, by replacing force processing intermingled with KDS rescheduling by windows of pure processing followed by collision detection, we transform an algorithm that is very difficult to parallelize into one that is embarrassingly parallel. |

Reflections on Simultaneous ImpactBreannan Smith, Danny Kaufman, Etienne Vouga, Rasmus Tamstorf, and Eitan Grinspun SIGGRAPH ( ACM Transactions on Graphics ), 2012 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. |

Asynchronous Variational Contact MechanicsEtienne Vouga, David Harmon, Rasmus Tamstorf, and Eitan Grinspun Computer Methods in Applied Mechanics and Engineering, 2011 An asynchronous, variational method for simulating elastica in complex contact and impact scenarios is developed. Asynchronous Variational Integrators (AVIs) are extended to handle contact forces by associating dierent time steps to forces instead of to spatial elements. By discretizing a barrier potential by an innite sum of nested quadratic potentials, these extended AVIs are used to resolve contact while obeying momentum- and energy-conservation laws. A series of two- and three-dimensional examples illustrate the robustness and good energy behavior of the method. |

Discrete Viscous ThreadsMiklos Bergou, Basile Audoly, Etienne Vouga, Max Wardetzky, and Eitan Grinspun SIGGRAPH ( ACM Transactions on Graphics ), 2010 We present a continuum-based discrete model for thin threads of viscous fluid by drawing upon the Rayleigh analogy to elastic rods, demonstrating canonical coiling, folding, and breakup in dynamic simulations. Our derivation emphasizes space-time symmetry, which sheds light on the role of time-parallel transport eliminating in approximation without all but an O(n) band of entries of the physical system's energy Hessian. The result is a fast, unified, implicit treatment of viscous threads and elastic rods that closely reproduces a variety of fascinating physical phenomena, including hysteretic transitions between coiling regimes, competition between surface tension and gravity, and the first numerical fluid-mechanical sewing machine. The novel implicit treatment also yields an order of magnitude speedup in our elastic rod dynamics. |

Asynchronous Contact MechanicsDavid Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, and Eitan Grinspun SIGGRAPH ( ACM Transactions on Graphics ), 2009 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. |

Robust Treatment of Simultaneous CollisionsDavid Harmon, Etienne Vouga, Rasmus Tamstorf, and Eitan Grinspun SIGGRAPH ( ACM Transactions on Graphics ), 2008 Robust treatment of complex collisions is a challenging problem in cloth simulation. Some state of the art methods resolve collisions iteratively, invoking a fail-safe when a bound on iteration count is exceeded. The best-known fail-safe rigidifies the contact region, causing simulation artifacts. We present a fail-safe that cancels impact but not sliding motion, considerably reducing artificial dissipation. We equip the proposed fail-safe with an approximation of Coulomb friction, allowing finer control of sliding dissipation. |