Category: Collisions

Defending Continuous Collision Detection against Errors

Huamin Wang

Numerical errors and rounding errors in continuous collision detection (CCD) can easily cause collision detection failures if they are not handled properly. A simple and effective approach is to use error tolerances, as shown in many existing CCD systems. Unfortunately, finding the optimal tolerance values is a difficult problem for users. Larger tolerance values will introduce false positive artifacts, while smaller tolerance values may cause collisions to be undetected. The biggest issue here is that we do not know whether or when CCD will fail, even though failures are extremely rare. In this paper, we demonstrate a set of simple modifications to make a basic CCD implementation failure-proof. Using error analysis, we prove the safety of this method and we formulate suggested tolerance values to reduce false positives. The resulting algorithms are safe, automatic, efficient, and easy to implement.

Defending Continuous Collision Detection against Errors

Adaptive Nonlinearity for Collisions in Complex Rod Assemblies

Danny M. Kaufman, Rasmus Tamstorf, Breannan Smith, Jean-Marie Aubry, Eitan Grinspun

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

Adaptive Tetrahedral Meshes for Brittle Fracture Simulation

Dan Koschier, Sebastian Lipponer, Jan Bender

We present a method for the adaptive simulation of brittle fracture of solid objects based on a novel reversible tetrahedral mesh refinement scheme. The refinement scheme preserves the quality of the input mesh to a large extent, it is solely based on topological operations, and does not alter the boundary, i.e. any geometric feature. Our fracture algorithm successively performs a stress analysis and increases the resolution of the input mesh in regions of high tensile stress. This results in an accurate location of crack origins without the need of a general high resolution mesh which would cause high computational costs throughout the whole simulation. A crack is initiated when the maximum tensile stress exceeds the material strength. The introduced algorithm then proceeds by iteratively recomputing the changed stress state and creating further cracks. Our approach can generate multiple cracks from a single impact but effectively avoids shattering artifacts. Once the tensile stress decreases, the mesh refinement is reversed to increase the performance of the simulation. We demonstrate that our adaptive method is robust, scalable and computes highly realistic fracture results.

Adaptive Tetrahedral Meshes for Brittle Fracture Simulation

Simulating Articulated Subspace Self-Contact

Yun Teng, Miguel Otaduy, Theodore Kim

We present an efficient new subspace method for simulating the self-contact of articulated deformable bodies, such as characters. Self-contact is highly structured in this setting, as the limited space of possible articulations produces a predictable set of coherent collisions. Subspace methods can leverage this coherence, and have been used in the past to accelerate the collision detection stage of contact simulation. We show that these methods can be used to accelerate the entire contact computation, and allow self-contact to be resolved without looking at all of the contact points. Our analysis of the problem yields a broader insight into the types of nonlinearities that subspace methods can efficiently approximate, and leads us to design a pose-space cubature scheme. Our algorithm accelerates self-contact by up to an order of magnitude over other subspace simulations, and accelerates the overall simulation by two orders of magnitude over full-rank simulations. We demonstrate the simulation of high resolution (100K – 400K elements) meshes
in self-contact at interactive rates (5.8 – 50 FPS).

Simulating Articulated Subspace Self-Contact

Implicit Multibody Penalty-based Distributed Contact

Hongyi Xu, Yili Zhao, and Jernej Barbic

The penalty method is a simple and popular approach to resolving contact in computer graphics and robotics. Penalty-based contact, however, suffers from stability problems due to the highly variable and unpredictable net stiffness, and this is particularly pronounced in simulations with time-varying distributed geometrically complex contact. We employ semi-implicit integration, exact analytical contact gradients, symbolic Gaussian elimination and a SVD solver to simulate stable penalty-based frictional contact with large, time-varying contact
areas, involving many rigid objects and articulated rigid objects in complex conforming contact and self-contact. We also derive implicit proportional-derivative control forces for real-time control of articulated structures with loops. We present challenging contact scenarios such as screwing a hexbolt into a hole, bowls stacked in perfectly conforming configurations, and manipulating many objects using actively controlled articulated mechanisms in real time.

Implicit Multibody Penalty-based Distributed Contact

Automatic Construction of Coarse, High-Quality Tetrahedralizations that Enclose and Approximate Surfaces for Animation

David A. Stuart, Joshua A. Levine, Ben Jones, Adam Bargteil

Embedding high-resolution surface geometry in coarse control meshes is a standard approach to achieving high-quality computer animation at low computational expense. In this paper we present an effective, automatic method for generating such control meshes. The resulting high-quality, tetrahedral meshes enclose and approximate an input surface mesh, avoiding extrapolation artifacts and ensuring that the resulting coarse volumetric meshes are adequate collision proxies. Our approach comprises three steps: we begin with a tetrahedral mesh built from the body-centered cubic lattice that tessellates the bounding box of the input surface; we then perform a sculpting phase that carefully removes elements from the lattice; and finally a variational vertex adjustment phase iteratively adjusts vertex positions to more closely approximate the surface geometry. Our approach provides explicit trade-offs between mesh quality, resolution, and surface approximation. Our experiments demonstrate the technique can be used to build high-quality meshes appropriate for simulations within games.

Automatic Construction of Coarse, High-Quality Tetrahedralizations that  Enclose and Approximate Surfaces for Animation

Object-Centric Parallel Rigid Body Simulation with Timewarp

John Koenig, Ioannis Karamouzas, Stephen J. Guy

We present an object-centric formulation for parallel rigid body simulation that supports variable length integration time steps through rollbacks. We combine our object-centric simulation
framework with a novel spatiotemporal data structure to reduce global synchronization and achieve interactive, real-time simulations which scale across many CPU cores. Additionally, we provide proofs that both our proposed data structure and our object-centric formulation are deadlock-free. We implement our approach with the functional programming language Erlang, and test the performance and scalability of our method over several scenarios consisting of hundreds of interacting objects.

Object-Centric Parallel Rigid Body Simulation with Timewarp

A GPU-Based Streaming Algorithm for High Resolution Cloth Simulation

Min Tang, Ruofeng Tong, Rahul Narain, Chang Meng, Dinesh Manocha

We present a GPU-based streaming algorithm to perform high-resolution and accurate cloth simulation. We map all the components of cloth simulation pipeline, including time integration, collision detection, collision response, and velocity updating to GPU-based kernels and data structures. Our algorithm perform intra-object and inter-object collisions, handles contacts and friction, and is able to accurately simulate folds and wrinkles. We describe the streaming pipeline and address many issues in terms of obtaining high throughput on many-core GPUs. In practice, our algorithm can perform high-fidelity simulation on a cloth mesh with 2M triangles using 3GB of GPU memory. We highlight the parallel performance of our algorithm on three different generations of GPUs. On a high-end NVIDIA Tesla K20c, we observe up to two orders of magnitude performance improvement as compared to a single-threaded CPU-based algorithm, and about one order of magnitude improvement over a 16-core CPU-based parallel implementation.

A GPU-Based Streaming Algorithm for High Resolution Cloth Simulation

Efficient Penetration Depth Approximation using Active Learning

Jia Pan, Xinyu Zhang, Dinesh Manocha

We present a new method for efficiently computing the global penetration depth between two rigid objects using machine learning techniques. Our approach consists of two phases: offline learning and performing run-time queries. In the learning phase, we pre-compute an approximation of the contact space of a pair of intersecting objects from a set of samples in the configuration space. We use active and incremental learning algorithms to accelerate the pre-computation and improve the accuracy. During the run-time phase, our algorithm performs a nearest-neighbor query based on translational or rotational distance metrics. The run-time query has a small overhead and computes an approximation to global penetration depth in a few milliseconds. We use our algorithm for collision response computations in Box2D and Bullet game physics engines and observe more than an order of magnitude improvement over prior PD computation techniques.

Efficient Penetration Depth Approximation using Active Learning

Geometric Numerical Integration of Inequality Constrained Nonsmooth Hamiltonian Systems

Danny Kaufman, Dinesh Pai

We consider the geometric numerical integration of Hamiltonian systems subject to both equality and “hard” inequality constraints. As in the standard geometric integration setting, we target long-term structure preservation. Additionally, however, we also consider invariant preservation over persistent, simultaneous, and/or frequent boundary interactions. Appropriately formulating geometric methods for these cases has long remained challenging due the inherent nonsmoothness and one-sided conditions that they impose. To resolve these issues we thus focus both on symplectic-momentum preserving behavior and the preservation of additional structures, unique to the inequality constrained setting. Toward these goals we introduce, for the first time, a fully nonsmooth, discrete Hamilton’s principle and obtain an associated framework for composing geometric numerical integration methods for inequality-equality–constrained systems. Applying this framework, we formulate a new family of geometric numerical integration methods that, by construction, preserve momentum and equality constraints and are observed to retain good long-term energy behavior. Along with these standard geometric properties, the derived methods also enforce multiple simultaneous inequality constraints, obtain smooth unilateral motion along constraint boundaries, and allow for both nonsmooth and smooth boundary approach and exit trajectories. Numerical experiments are presented to illustrate the behavior of these methods on difficult test examples where both smooth and nonsmooth active constraint modes persist with high frequency.

Geometric Numerical Integration of Inequality Constrained Nonsmooth Hamiltonian Systems