Adaptive Image-Based Intersection Volume

Bin Wang, Francois Faure, Dinesh Pai

A method for image-based contact detection and modeling, with guaranteed precision on the intersection volume, is presented. Unlike previous image-based methods, our method optimizes a non-uniform ray sampling resolution and allows precise control of the volume error. By cumulatively projecting all mesh edges into a generalized 2D texture, we construct a novel data structure, the Error Bound Polynomial Image (EBPI), which allows efficient computation of the maximum volume error as a function of ray density. Based on a precision criterion, EBPI pixels are subdivided or clustered. The rays are then cast in the projection direction according to the non-uniform resolution. The EBPI data, combined with ray-surface intersection points and normals, is also used to detect transient edges at surface intersections. This allows us to model intersection volumes at arbitrary resolution, while avoiding the geometric computation of mesh intersections. Moreover, the ray casting acceleration data structures can be reused for the generation of high quality images.

Adaptive Image-Based Intersection Volume

Reflections on Simultaneous Impact

Breannan Smith, Danny Kaufman, Etienne Vouga, Rasmus Tamstorf, Eitan Grinspun

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

Interactive Editing of Deformable Simulations

Jernej Barbic, Funshing Sin, Eitan Grinspun

We present an interactive animation editor for complex deformable object animations. Given an existing animation, the artist directly manipulates the deformable body at any time frame, and the surrounding animation immediately adjusts in response. The automatic adjustments are designed to respect physics, preserve detail in both the input motion and geometry, respect prescribed bilateral contact constraints, and controllably and smoothly decay in spacetime. While the utility of interactive editing for rigid body and articulated figure animations is widely recognized, a corresponding approach to deformable bodies has not been technically feasible before. We achieve interactive rates by combining spacetime model reduction, rotation-strain coordinate warping, linearized elasticity, and direct manipulation. This direct editing tool can serve the final stages of animation production, which often call for detailed, direct adjustments that are otherwise tedious to realize by re-simulation or frame-by-frame editing.

Interactive Editing of Deformable Simulations

PolyDepth: Real-Time Penetration Depth Computation using Iterative Contact-Space Projection

Changsoo Je, Min Tang, Youngeun Lee, Minkyoung Lee, Young J. Kim

We present a real-time algorithm that finds the Penetration Depth (PD) between general polygonal models based on iterative and local optimization techniques. Given an in-collision configuration of an object in configuration space, we find an initial collision-free configuration using several methods such as centroid difference, maximally clear configuration, motion coherence, random configuration, and sampling-based search. We project this configuration on to a local contact space using a variant of continuous collision detection algorithm and construct a linear convex cone around the projected configuration. We then formulate a new projection of the in-collision configuration onto the convex cone as a Linear Complementarity Problem (LCP), which we solve using a type of Gauss-Seidel iterative algorithm. We repeat this procedure until a locally optimal PD is obtained. Our algorithm can process complicated models consisting of tens of thousands triangles at interactive rates.

PolyDepth: Real-Time Penetration Depth Computation using Iterative Contact-Space Projection

Efficient Geometrically Exact Continuous Collision Detection

Tyson Brochu, Essex Edwards, Robert Bridson

Continuous collision detection (CCD) between deforming triangle mesh elements in 3D is a critical tool for many applications. The standard method involving a cubic polynomial solver is vulnerable to rounding error, requiring the use of ad hoc tolerances, and nevertheless is particularly fragile in (near-)planar cases. Even with per-simulation tuning, it may still cause problems by missing collisions or erroneously flagging non-collisions. We present a geometrically exact alternative guaranteed to produce the correct Boolean result (significant collision or not) as if calculated with exact arithmetic, even in degenerate scenarios. Our critical insight is that only the parity of the number of collisions is needed for robust simulation, and this parity can be calculated with simpler non-constructive predicates. In essence we analyze the roots of the nonlinear system of equations defining CCD through careful consideration of the boundary of the parameter domain. The use of new conservative culling and interval filters allows typical simulations to run as fast as with the non-robust version, but without need for tuning or worries about failure cases even in geometrically degenerate scenarios. We demonstrate the effectiveness of geometrically exact detection with a novel adaptive cloth simulation, the first to guarantee to remain intersection-free despite frequent curvature-driven remeshing.

Efficient Geometrically Exact Continuous Collision Detection

Continuous Penalty Forces

Min Tang, Dinesh Manocha, Miguel Otaduy, Ruofeng Tong

We present a simple algorithm to compute continuous penalty forces to determine collision response between rigid and deformable models bounded by triangle meshes. Our algorithm provides a well-behaved solution in contrast to the traditional stability and robustness problems of penalty methods, induced by force discontinuities. We trace contact features along their deforming trajectories and accumulate penalty forces along the penetration time intervals between the overlapping feature pairs. Moreover, we present a closed-form expression to compute the continuous and smooth collision response. Our method has very small additional overhead compared to previous penalty methods, while significantly improves the stability and robustness. We highlight its benefits on several benchmarks.

Continuous Penalty Forces

STAR: Interactive Simulation of Rigid Body Dynamics in Computer Graphics

Jan Bender, Kenny Erleben, Jeff Trinkle, Erwin Coumans

Interactive rigid body simulation is an important part of many modern computer tools. No authoring tool nor a game engine can do without. The high performance computer tools open up new possibilities for changing how designers, engineers, modelers and animators work with their design problems.

This paper is a self contained state-of-the-art report on the physics, the models, the numerical methods and the algorithms used in interactive rigid body simulation all of which has evolved and matured over the past 20 years. The paper covers applications and the usage of interactive rigid body simulation.

Besides the mathematical and theoretical details that this paper communicates in a pedagogical manner the paper surveys common practice and reflects on applications of interactive rigid body simulation. The grand merger of interactive and off-line simulation methods is imminent, multi-core is everyman’s property. These observations pose future challenges for research which we reflect on. In perspective several avenues for possible future work is touched upon such as more descriptive models and contact point generation problems. This paper is not only a stake in the sand on what has been done, it also seeks to give newcomers practical hands on advices and reflections that can give experienced researchers afterthought for the future.

Interactive Simulation of Rigid Body Dynamics in Computer Graphics

VolCCD: Fast Continuous Collision Culling Between Deforming Volume Meshes

Min Tang, Dinesh Manocha, Sung-Eui Yoon, Peng Du, Jae-Pil Heo, Ruofeng Tong

We present a novel culling algorithm to perform fast and robust continuous collision detection between deforming volume meshes. This includes a continuous separating axis test that can conservatively check whether two volume meshes overlap during a given time interval. Moreover, we present efficient methods to eliminate redundant elementary tests between the features (e.g., vertices, edges, and faces) of volume elements (e.g., tetrahedra). Our approach is applicable to various deforming meshes, including those with changing topologies, and efficiently computes the first time of contact. We are able to perform inter-object and intra-object collision queries in models represented with tens of thousands of volume elements at interactive rates on a single CPU core. Moreover, we observe more than an order of magnitude performance improvement over prior methods.

VolCCD: Fast Continuous Collision Culling Between Deforming Volume Meshes

Asynchronous Integration with Phantom Meshes

David Harmon, Qingnan Zhou, Denis Zorin

Asynchronous variational integration of layered contact models provides a framework for robust collision handling, correct physical behavior, and guaranteed eventual resolution of even the most difficult contact problems. Yet, even for low-contact scenarios, this approach is significantly slower compared to its less robust alternatives — often due to handling of stiff elastic forces in an explicit framework. We propose a method that retains the guarantees, but allows for variational implicit integration of some of the forces, while maintaining asynchronous integration needed for contact handling. Our method uses phantom meshes for calculations with stiff forces, which are then coupled to the original mesh through constraints. We use the augmented discrete Lagrangian of the constrained system to derive a variational integrator with the desired conservation properties.

Asynchronous Integration with Phantom Meshes

Eulerian Solid Simulation with Contact

David I. W. Levin, Joshua Litven, Garrett L. Jones, Shinjiro Sueda, Dinesh K. Pai

Simulating viscoelastic solids undergoing large, nonlinear deformations in close contact is challenging. In addition to inter-object contact, methods relying on Lagrangian discretizations must handle degenerate cases by explicitly remeshing or resampling the object. Eulerian methods, which discretize space itself, provide an interesting alternative due to the fixed nature of the discretization. In this paper we present a new Eulerian method for viscoelastic materials that features a collision detection and resolution scheme which does not require explicit surface tracking to achieve accurate collision response. Time-stepping with contact is performed by the efficient solution of large sparse quadratic programs; this avoids constraint sticking and other difficulties. Simulation and collision processing can share the same uniform grid, making the algorithm easy to parallelize. We demonstrate an implementation of all the steps of the algorithm on the GPU. The method is effective for simulation of complicated contact scenarios involving multiple highly deformable objects, and can directly simulate volumetric models obtained from medical imaging techniques such as CT and MRI.

Eulerian Solid Simulation with Contact