Category: Rigid bodies

Real-Time Dynamic Fracture with Volumetric Approximate Convex Decompositions

Matthias Mueller, Nuttapong Chentanez, Tae-Yong Kim

We propose a new fast, robust and controllable method to simulate the dynamic destruction of large and complex objects in real time. The common method for fracture simulation in computer games is to pre-fracture models and replace objects by their pre-computed parts at run-time. This popular method is computationally cheap but has the disadvantages that the fracture pattern does not align with the impact location and that the number of hierarchical fracture levels is fixed. Our method allows dynamic fracturing of large objects into an unlimited number of pieces fast enough to be used in computer games. We represent visual meshes by volumetric approximate convex decompositions (VACD) and apply user-defined fracture patterns dependent on the impact location. The method supports partial fracturing meaning that fracture patterns can be applied locally at multiple locations of an object. We propose new methods for computing a VACD, for approximate convex hull construction and for detecting islands in the convex decomposition after partial destruction in order to determine support structures.

Real-Time Dynamic Fracture with Volumetric Approximate Convex Decompositions

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

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 and contact resolution such that objects move and collide in the first step, with resting contact handled in the second step. The first step of our algorithm guarantees that each time step produces geometry that does not intersect or overlap by using an approximation to the continuous collision detection (and response) problem and thus is amenable to thin shells and degenerately flat objects moving at high speeds. In addition we introduce a novel failsafe which allows us to resolve all interpenetration without iterating to convergence. Since the first step guarantees a non-interfering state for the geometry, in the second step we propose a contact model for handling thin shells in proximity considering only the instantaneous locations at the ends of the time step.

Interpenetration Free Simulation of Thin Shell Rigid Bodies

Automated Constraint Placement to Maintain Pile Shape

Shu-Wei Hsu, John Keyser

We present a simulation control to support art-directable stacking designs by automatically adding constraints to stabilize the stacking structure. We begin by adapting equilibrium analysis in a local scheme to find “stable” objects of the stacking structure. Next, for stabilizing the structure, we pick suitable objects from those passing the  equilibrium analysis and then restrict their DOFs by managing the insertion of constraints on them. The method is suitable for controlling stacking behavior of large scale. Results show that our control method can be used in varied ways for creating plausible animation. In addition, the method can be easily implemented as a plug-in into existing simulation solvers without changing the fundamental operations of the solvers.

Automated Constraint Placement to Maintain Pile Shape

Efficient Collision Detection for Brittle Fracture

Loiez Glondu, Sarah Schvartzman, Maud Marchal, Georges Dumon, Miguel Otaduy

In complex scenes with many objects, collision detection plays a key role in the simulation performance. This is particularly true for fracture simulation, where multiple new objects are dynamically created. In this paper, we present novel algorithms and data structures for collision detection in real-time brittle fracture simulations. We build on a combination of well-known efficient data structures, namely distance fields and sphere trees, making our algorithm easy to integrate on existing simulation engines. We propose novel methods to construct these data structures, such that they can be efficiently updated upon fracture events and integrated in a simple yet effective self-adapting contact selection algorithm. Altogether, we drastically reduce the cost of both collision detection and collision response. We have evaluated our global solution for collision detection on challenging scenarios, achieving high frame rates suited for hard real-time applications such as video games or haptics. Our solution opens promising perspectives for complex brittle fracture simulations involving many dynamically created objects.

Efficient Collision Detection for Brittle Fracture

Mass-Splitting for Jitter-Free Parallel Rigid Body Simulation

Richard Tonge, Feodor Benevolenski, Andrey Voroshilov

We present a parallel iterative rigid body solver that avoids common artifacts at low iteration counts. In large or real-time simulations, iteration is often terminated before convergence to maximize scene size. If the distribution of the resulting residual energy varies too much from frame to frame, then bodies close to rest can visibly jitter. Projected Gauss-Seidel (PGS) distributes the residual according to the order in which contacts are processed, and preserving the order in parallel implementations is very challenging. In contrast, Jacobi-based methods provide order independence, but have slower convergence. We accelerate projected Jacobi by dividing each body mass term in the effective mass by the number of contacts acting on the body, but use the full mass to apply impulses. We further accelerate the method by solving contacts in blocks, providing wallclock performance competitive with PGS while avoiding visible artifacts. We prove convergence to the solution of the underlying linear complementarity problem and present results for our GPU implementation,which can simulate a pile of 5000 objects with no visible jittering at over 60 FPS.

Mass-Splitting for Jitter-Free Parallel Rigid Body Simulation

Versatile Rigid-Fluid Coupling for Incompressible SPH

Nadir Akinci, Markus Ihmsen, Gizem Akinci, Barbara Solenthaler, Matthias Teschner

We propose a momentum-conserving two-way coupling method of SPH fluids and arbitrary rigid objects based on hydrodynamic forces. Our approach samples the surface of rigid bodies with boundary particles that interact with the fluid, preventing deficiency issues and both spatial and temporal discontinuities. The problem of inhomogeneous boundary sampling is addressed by considering the relative contribution of a boundary particle to a physical quantity. This facilitates not only the initialization process but also allows the simulation of multiple dynamic objects. Thin structures consisting of only one layer or one line of boundary particles, and also non-manifold geometries can be handled without any additional treatment. We have integrated our approach into WCSPH and PCISPH, and demonstrate its stability and flexibility with several scenarios including multiphase flow.

Versatile Rigid-Fluid Coupling for Incompressible SPH

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

Underwater Rigid Body Dynamics

Steffen Weissman, Ulrich Pinkall

We show that the motion of rigid bodies under water can be realistically simulated by replacing the usual inertia tensor and scalar mass by the so-called Kirchhoff tensor. This allows us to model fluid-body interaction without simulating the surrounding fluid at all. We explain some of the phenomena that arise and compare our results against real experiments. It turns out that many real scenarios (sinking bodies, balloons) can be matched using a single, hand-tuned scaling parameter. We describe how to integrate our method into an existing physics engine, which makes underwater rigid body dynamics run in real time.

Underwater Rigid Body Dynamics