Month: October 2012

Simulation of Complex Nonlinear Elastic Bodies using Lattice Deformers

Taylor Patterson, Nathan Mitchell, Eftychios Sifakis

Lattice deformers are a popular option for modeling the behavior of elastic bodies as they avoid the need for conforming mesh generation, and their regular structure offers significant opportunities for performance optimizations. Our work expands the scope of current lattice-based elastic deformers, adding support for a number of important simulation features. We accommodate complex nonlinear, optionally anisotropic materials while using an economical one-point quadrature scheme. Our formulation fully accommodates near-incompressibility by enforcing accurate nonlinear constraints, supports implicit integration for large time steps, and is not susceptible to locking or poor conditioning of the discrete equations. Additionally, we increase the accuracy of our solver by employing a novel high-order quadrature scheme on lattice cells overlapping with the model boundary, which are treated at sub-cell precision. Finally, we detail how this accurate boundary treatment can be implemented at a minimal computational premium over the cost of a voxel-accurate discretization. We demonstrate our method in the simulation of complex musculoskeletal human models.

Simulation of Complex Nonlinear Elastic Bodies using Lattice Deformers

VriPhys 2012

Physics animation papers at VriPhys:

An implicit Tensor-Mass solver on the GPU for soft bodies simulation

Xavier Faure, Florence Zara, Fabrice Jaillet, Jean-Michel Moreau

The realistic and interactive simulation of deformable objects has become a challenge in Computer Graphics. In this paper, we propose a GPU implementation of the resolution of the mechanical equations, using a semi-implicit as well as an implicit integration scheme. At the contrary of the classical FEM approach, forces are directly computed at each node of the discretized objects, using the evaluation of the strain energy density of the elements. This approach allows to mix several mechanical behaviors in the same object. Results show a notable speedup of 30, especially in the case of complex scenes. Running times shows that this efficient implementation may contribute to make this model more popular for soft bodies simulations.

An implicit Tensor-Mass solver on the GPU for soft bodies simulation

High-Resolution Simulation of Granular Material with SPH

Markus Ihmsen, Arthur Wahl, Matthias Teschner

We present an efficient framework for simulating granular material with high visual detail. Our model solves the computationally and numerically critical forces on a coarsely sampled particle simulation. We incorporate a new frictional boundary force into an existing continuum-based method which enables realistic interactions and a more robust simulation. Visual realism is achieved by coupling a set of highly resolved particles with the base simulation at low computational costs. Thereby, visual details can be added which are not resolved by the base simulation.

High-Resolution Simulation of Granular Material with SPH

An Efficient Surface Reconstruction Pipeline for Particle-Based Fluids

Gizem Akinci, Nadir Akinci, Markus Ihmsen, Matthias Teschner

In this paper we present an efficient surface reconstruction pipeline for particle-based fluids such as smoothed particle hydrodynamics. After the scalar field computation and the marching cubes based triangulation, we post process the surface mesh by applying surface decimation and subdivision algorithms. In comparison to existing approaches, the decimation step alleviates the particle alignment related bumpiness very efficiently and reduces the number of triangles in flat regions. Later, the subdivision step ensures that the non-smooth regions are smoothed in a performance friendly way which allows our approach to run significantly faster by using lower resolution marching cubes grids. The presented pipeline is applicable to particle position data sets in a frame by frame basis. Throughout the paper, we present both visual and performance comparisons with different parameter settings, and with a state-of-the-art surface reconstruction technique. Our results demonstrate that in comparison to other approaches with comparable surface quality, our pipeline runs 15 to 20 times faster with up to 80% less memory and secondary storage consumption.

An Efficient Surface Reconstruction Pipeline for Particle-Based Fluids

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

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 rescheduling separating plane kinetic data structures—with an optimistic speculative method inspired by Mirtich’s rigid body Time Warp algorithm [2000]. Time warp allows us to perform collision detection over a window of time containing many of ACM’s asynchronous trajectory changes; in this way we cull away large intervals as being collision free. Moreover, by replacing force processing intermingled with KDS rescheduling by windows of pure processing followed by collision detection, we tranform an algorithm that is very difficult to parallelize into one that is embarrassingly parallel.

Speculative Parallel Asynchronous Contact Mechanics