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 […]

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 […]

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, […]

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 […]

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 […]

Interpenetration Free Simulation of Thin Shell Rigid Bodies

R. Elliot English, Michael Lentine, Ron Fedkiw We propose a new algorithm for rigid body simulation that guarantees each body is in an interpenetration free state, both increasing the accuracy and robustness of the simulation as well as alleviating the need for ad hoc methods to separate bodies for subsequent simulation and rendering. We cleanly separate collision […]

Speculative Parallel Asynchronous Contact Mechanics

Samantha Ainsley, Etienne Vouga, Eitan Grinspun, Rasmus Tamstorf We extend the Asynchronous Contact Mechanics algorithm [Harmon et al. 2009] 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 […]

Energy-Based Self-Collision Culling for Arbitrary Mesh Deformations

Changxi Zheng, Doug James In this paper, we accelerate self-collision detection (SCD) for a deforming triangle mesh by exploiting the idea that a mesh cannot self collide unless it deforms enough. Unlike prior work on subspace self-collision culling which is restricted to low-rank deformation subspaces, our energy-based approach supports arbitrary mesh deformations while still being […]

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 […]

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 […]