Publications
Speculative Parallel Asynchronous Contact Mechanics. Samantha 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 containingmany 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.
Design of Self-supporting Surfaces. Etienne Vouga, Mathias Höbinger, Johannes Wallner, and Helmut Pottmann, SIGGRAPH ( ACM Transactions on Graphics ), 2012.
Self-supporting masonry is one of the most ancient and elegant techniques for building curved shapes. Because of the very geometric nature of their failure, analyzing and modeling such strutures is more a geometry processing problem than one of classical continuum mechanics. This paper uses the thrust network method of analysis and presents an iterative nonlinear optimization algorithm for efficiently approximating freeform shapes by self-supporting ones. The rich geometry of thrust networks leads us to close connections between diverse topics in discrete differential geometry, such as a finite-element discretization of the Airy stress potential, perfect graph Laplacians, and computing admissible loads via curvatures of polyhedral surfaces. This geometric viewpoint allows us, in particular, to remesh self-supporting shapes by self-supporting quad meshes with planar faces, and leads to another application of the theory: steel/glass constructions with low moments in nodes.
Reflections on Simultaneous Impact. Breannan 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.
Flexible Developable Surfaces. Justin Solomon, Etienne Vouga, Max Wardetzky, and Eitan Grinspun, Eurographics Symposium on Geometry Processing, 2012.
We introduce a discrete paradigm for developable surface modeling. Unlike previous attempts at interactive developable
surface modeling, our system is able to enforce exact developability at every step, ensuring that users
do not inadvertently suggest configurations that leave the manifold of admissible folds of a flat two-dimensional
sheet. With methods for navigation of this highly nonlinear constraint space in place, we show how to formulate
a discrete mean curvature bending energy measuring how far a given discrete developable surface is from being
flat. This energy enables relaxation of user-generated configurations and suggests a straightforward subdivision
scheme that produces admissible smoothed versions of bent regions of our discrete developable surfaces.
Diamonds from the Rough: Improving Drawing, Painting, and Singing via Crowdsourcing. Yotam Gingold, Etienne Vouga, Eitan Grinspun, and Haym Hirsh, Proceedings of the AAAI Workshop on Human Computation (HCOMP), 2012.
It is well established that in certain domains, noisy inputs can be reliably combined to obtain a better answer than any individual. It is now possible to consider the crowdsourcing of physical actions, commonly used for creative expressions such as drawing, shading, and singing. We provide algorithms for converting low-quality input obtained from the physical actions of a crowd into high-quality output. The inputs take the form of line drawings, shaded images, and songs. We investigate single-individual crowds (multiple inputs from a single human) and multiple-individual crowds.
Asynchronous Variational Contact Mechanics. Etienne 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 Threads. Miklos 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 Mechanics. David 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.
On the Smoothness of Real-Valued Functions Generated by
Subdivision Schemes Using Nonlinear Binary Averaging. Ron Goldman, Etienne Vouga, and Scott Schaefer, Computer Aided Geometric Design, 2009.
Our main result is that two point interpolatory subdivision schemes using C^k nonlinear averaging
rules on pairs of real numbers generate real-valued functions that are also C^k. The signicance of this
result is the following consequence: Suppose that S is a subdivision algorithm operating on sequences
of real numbers using linear binary averaging that generates C^m real-valued functions and S is the
same subdivision procedure where linear binary averaging is replaced everywhere in the algorithm by
a C^n nonlinear binary averaging rule on pairs of real numbers; then the functions generated by the
nonlinear subdivision scheme S are C^k , where k = min(m, n).
Robust Treatment of
Simultaneous Collisions. David 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.
Two Blossoming Proofs of the
Lane-Riesenfeld Algorithm. Vouga, E. and Goldman, R. 2007.
Computing 79, 2
(Apr. 2007), 153-162.
The standard proof of the Lane-Riesenfeld algorithm for inserting knots
into uniform B-spline curves is based on the continuous convolution
formula for the uniform B-spline basis functions. Here we provide two new,
elementary, blossoming proofs of the Lane-Riesenfeld algorithm for uniform
B-spline curves of arbitrary degree.
Nonlinear Subdivision Through Nonlinear Averaging.
Schaefer S., Vouga E. and Goldman R.
Computer Aided Geometric Design, Vol. 25, No. 3 (2008), pages 162-180.
We investigate a general class of nonlinear subdivision algorithms for
functions of a real or complex variable built from linear subdivision
algorithms by replacing binary linear averages such as the arithmetic mean
by binary nonlinear averages such as the geometric mean. Using our method,
we can easily create stationary subdivision schemes for Gaussian
functions, spiral curves, and circles with uniform parametrizations. More
generally, we show that stationary subdivision schemes for e^p(x),
cos(p(x)) and sin(p(x)) for any polynomial or piecewise polynomial p(x)
can be generated using only addition, subtraction, multiplication, and
square roots. The smoothness of our nonlinear subdivision schemes is
inherited from the smoothness of the original linear subdivision schemes
and the differentiability of the corresponding nonlinear averaging rules.
While our results are quite general, our proofs are elementary, based
mainly on the observation that generic nonlinear averaging rules on a pair
of real or complex numbers can be constructed by conjugating linear
averaging rules with locally invertible nonlinear maps. In a forthcoming
paper we show that every continuous nonlinear averaging rule on a pair of
real or complex numbers can be constructed by conjugating a linear
averaging rule with an associated continuous locally invertible nonlinear
map. Thus the averaging rules considered in this paper are actually the
general case. As an application we show how to apply our nonlinear
subdivision algorithms to intersect some common transcendental functions.