“reasonable” time step can be enormous: in their analysis of contact, Cirak and West5 present a counting argument and conclude that synchronous “contact simulation algorithms cannot attempt to exactly compute the sequence and timing of all impacts,” as this would preclude reasonable progress.

The graphics community’s prevailing emphasis on progress has motivated many efforts to find, retroactively, a physically plausible resolution to a given set of collisions that occurred over a preceding time interval. 4, 20 Such methods typically have adjustable parameters that must be carefully chosen to balance safety and progress; other methods discard causality in favor of progress. 19 The principled, faithful simulation of complex collisions for deformable objects, such as cloth and other flexible materials, remains an open, challenging, and important problem.

1. 3. asynchrony

We propose to place safety and correctness on an equal footing with progress. To overcome the fundamental opposition between these requirements, we turn to asynchronous integration, which integrates each geometric element of a discrete shape (e.g., the stretching resistance of cloth defined across a triangle) at its own pace, not in lockstep with the entire object. Asynchrony offers compelling long-term advantages for simulations of deformable objects in complex contact—advantages that remain unexplored, in particular, in terms of safety, correctness, and progress. For scenarios involving sharp boundaries or dispersed points of contact, such as crumpled clothing, asynchrony renders noninterpenetration and momentum conservation tractable. Because elements advance at their own pace, those not entangled in collisions can proceed at large time steps. As shown in Figure 2, the median time step of an asynchronous method can be moderate even when high-impact collisions force some elements to proceed at small time steps.

1. 4. asynchronous integration

As a point of departure we consider asynchronous variational integrators (AVIs), 16 which belong to a larger class of integrators that exactly conserve both momentum and symplecticity (loosely related to preservation of areas in phase space); such integrators are highly regarded because of their provable approximate conservation of energy over

figure 2. asynchrony in the curtain simulation, depicted by the time-evolving distribution of vertex time step sizes, enables adaptive allocation of computational resources in space time.

Time step (log scale)

(larger)(smaller)

3. 29´ 10− 6 3. 16´ 10− 4

0 20 40 60 80 100 Percentage of vertices 0 89

246 1357 Simulated time (seconds)

long spans of simulated time. However, a correct contact model remains unexplored.

1. 5. asynchronous collision detection

To ensure safety, we require an equally principled approach to collision detection. With every object able to collide with any other object, collision detection is fundamentally a quadratic problem. Thus, efficient collision detection algorithms are necessary to prune the non-intersecting pairs. Furthermore, we must reliably find those elements which are proximate rather than actually intersecting, so that we may counteract the impending penetration. This is a heavily studied problem; alas, the many reported successes are specific to the synchronous context, and as a group current methods can be intractably slow if naïvely applied after each local asynchronous step. This motivates our interest in kinetic data structures (KDSs)3: a KDS algorithm maintains a data structure governed by formal invariants describing some discrete attribute (such as absence of collisions), in response to the continuous movement of geometric elements. Many existing collision detection methods can be reformulated from a KDS perspective. KDSs seem destined for asynchronous applications, because their focus on fast, minimal, “ output-sensitive” data-structure updates makes them ideally suited for the small, local changes effected by each AVI step.

These observations motivate our interest in approaching contact mechanics for both graphics and mechanics applications from a new direction. In particular, (a) we formulate a contact model that is safe independent of user parameters, such as the stiffness and “bounciness” of collisions. (b) We correctly discretize time, using asynchrony to preserve the model’s safety and to respect causality, and using a sym-plectic-momentum integrator to exactly conserve momentum and approximately conserve energy over long runtimes. Finally, (c) we lay out the basic foundations for the union of AVIs with KDSs, making the safe, correct integration of complex contact for highly deformable objects tractable.

2. aSynchRonouS inteGRatoRS

Consider a physical system with a time-varying configuration q(t) in the space Q of all configurations; concretely, for a mesh with vertices x1, …, xn in 3D we represent Q = r3n by a vector of all the vertices’ Cartesian coordinates. We use a dot to denote differentiation in time, so that q·(t) is the velocity of the system. Let M be the mass matrix, so that p = Mq· is the momentum. The Störmer–Verlet (“leapfrog”) integrator evolves a sequence of positions q0, q1, q2, .. .and momenta 1 1 1 1+ 2+ 0+ 2 2 2, , ,... p p p via the update rules

1+ 1 2

+ 1

11

+

22

1

= , = ( ), =,

k
kk
kk
k
kk
hM
hF
tt h

−
−
−
−
−
−

qq p pp q

where h is the time step and F(q) is the force. The sub/super-scripted indices remind us that positions and velocities are staggered in time, with tk associated to qk, and (tk, tk+ 1) associated to

1+

2

k p . In effect, leapfrog first updates the position at tk using the constant momentum associated to the preceding interval (tk− 1, tk), and then impulsively “kicks,” obtaining