We present a new approach to fluid simulation that balances the speed of model reduction with the flexibility of grid-based methods. We construct a set of composable reduced models, or tiles, which capture spatially localized fluid behavior. We then precompute coupling terms so that these models can be rearranged at runtime. To enforce consistency between tiles, we introduce constraint reduction. This technique modifies a reduced model so that a given set of linear constraints can be fulfilled. Because dynamics and constraints can be solved entirely in the reduced space, our method is extremely fast and scales to large domains.
Interactive Simulation of Surgical Needle Insertion and Steering
We present algorithms for simulating and visualizing the insertion and steering of needles through deformable tissues for surgical training and planning. Needle insertion is an essential component of manyclinical procedures such as biopsies, injections, neurosurgery, and brachytherapy cancer treatment. The success of these procedures dependson accurate guidanceofthe needletiptoaclinical target while avoiding vital tissues. Needle insertion deforms body tissues, making accurate placement difficult. Our interactive needle insertion simulator models the coupling between a steerable needle and deformable tissue. We introduce (1) a novel algorithm for local remeshing that quickly enforces the conformity of a tetrahedral mesh to a curvilinear needle path, enabling accurate computation of contact forces, (2) an efficient method for coupling a 3D finite element simulation with a 1D inextensible rod with stick-slip friction, and (3) optimizations that reduce the computation time for physically based simulations.We can realistically and interactively simulate needle insertion into a prostate mesh of 13,375 tetrahedra and 2,763 vertices at a 25 Hz frame rate on an 8-core 3.0 GHz Intel Xeon PC. The simulation models prostate brachytherapy with needles of varying stiffness, steering needles around obstacles, and supports motion planning for robotic needle insertion. We evaluate the accuracyof the simulation by comparing against real-world experiments in which flexible, steerable needles were inserted into gel tissue phantoms.
Interactive Simulation of Surgical Needle Insertion and Steering
Deforming Meshes that Split and Merge
We present a method for accurately tracking the moving surface of deformable materials in a manner that gracefully handles topological changes.We employ a Lagrangian surface tracking method, and we use a triangle mesh for our surface representation so that fine features can be retained. We make topological changes to the mesh by first identifying merging or splitting events at a particular grid resolution, and then locally creating new pieces of the mesh in the affected cells using a standard isosurface creation method.We stitch the new, topologically simplified portion of the mesh to the rest of the mesh at the cell boundaries. Our method detects and treats topological events with an emphasis on the preservation of detailed features, while simultaneously simplifying those portions of the material that are not visible. Our surface tracker is not tied to a particular method for simulating deformable materials. In particular, we show results from two significantly different simulators: a Lagrangian FEM simulator with tetrahedral elements, and an Eulerian grid-based fluid simulator. Although our surface tracking method is generic, it is particularly well-suited for simulations that exhibit fine surface details and numerous topological events. Highlights of our results include merging of viscoplastic materials with complex geometry, a taffy-pulling animation with many fold and merge events, and stretching and slicing of stiff plastic material.
Deformable Object Animation Using Reduced Optimal Control
Keyframe animation is a common technique to generate animations of deformable characters and other soft bodies. With spline interpolation, however, it can be difficult to achieve secondary motion effects such as plausible dynamics when there are thousands of degrees of freedom to animate. Physical methods can provide more realism with less user effort, but it is challenging to apply them to quickly create specific animations that closely follow prescribed animator goals. We present a fast space-time optimization method to author physically based deformable object simulations that conform to animator-specified keyframes. We demonstrate our method with FEM deformable objects and mass-spring systems. Our method minimizes an objective function that penalizes the sum of keyframe deviations plus the deviation of the trajectory from physics. With existing methods, such minimizations operate in high dimensions, are slow, memory consuming, and prone to local minima. We demonstrate that significant computational speedups and robustness improvements can be achieved if the optimization problem is properly solved in a low-dimensional space. Selecting a low-dimensional space so that the intent of the animator is accommodated, and that at the same time space-time optimization is convergent and fast, is difficult. We present a method that generates a quality low-dimensional space using the given keyframes. It is then possible to find quality solutions to difficult space-time optimization problems robustly and in a manner of minutes.
Preserving Topology and Elasticity for Embedded Deformable Models
In this paper we introduce a new approach for the embedding of linear elastic deformable models. Our technique results in significant improvements in the efficient physically based simulation of highly detailed objects. First, our embedding takes into account topological details, that is, disconnected parts that fall into the same coarse element are simulated independently. Second, we account for the varying material properties by computing stiffness and interpolation functions for coarse elements which accurately approximate the behavior of the embedded material. Finally, we also take into account empty space in the coarse embeddings, which provides a better simulation of the boundary. The result is a straightforward approach to simulating complex deformable models with the ease and speed associated with a coarse regular embedding, and with a quality of detail that would only be possible at much finer resolution.
Preserving Topology and Elasticity for Embedded Deformable Models
Numerical Coarsening of Inhomogeneous Elastic Materials
We propose an approach for efficiently simulating elastic objects made of non-homogeneous, non-isotropic materials. Based on recent developments in homogenization theory, a methodology is introduced to approximate a deformable object made of arbitrary fine structures of various linear elastic materials with a dynamically-similar coarse model. This coarsening of the material properties allows for simulation of fine, heterogeneous structures on very coarse grids while capturing the proper dynamics of the original dynamical system, thus saving orders of magnitude in computational time. Examples including inhomogeneous and/or anisotropic materials can be realistically simulated in realtime using a numerically-coarsened model made of a few mesh elements.
Energy-Preserving Integrators for Fluid Animation
Numerical viscosity has long been a problem in fluid animation. Existing methods suffer from intrinsic artificial dissipation and often apply complicated computational mechanisms to combat such effects. Consequently, dissipative behavior cannot be controlled or modeled explicitly in a manner independent of time step size, complicating the use of coarse previews and adaptive-time stepping methods. This paper proposes simple, unconditionally stable, fully Eulerian integration schemes with no numerical viscosity that are capable of maintaining the liveliness of fluid motion without recourse to corrective devices. Pressure and fluxes are solved efficiently and simultaneously in a time-reversible manner on simplicial grids, and the energy is preserved exactly over long time scales in the case of inviscid fluids. These integrators can be viewed as an extension of the classical energy-preserving Harlow-Welch / Crank-Nicolson scheme to simplicial grids.
Co-rotated SPH for Deformable Solids
Smoothed Particle Hydrodynamics (SPH) is a powerful technique for the animation of natural phenomena. While early SPH approaches in Computer Graphics have mainly been concerned with liquids or gases, recent research also focuses on the dynamics of deformable solids using SPH. In this paper, we present a novel corotational SPH formulation for deformable solids. The rigid body modes are extracted from the deformation field which allows to use a linear strain tensor. In contrast to previous rotationally invariant meshless approaches, we show examples using coplanar and collinear particle data sets. The presented approach further allows for a unified meshfree representation of deformable solids and fluids. This enables the animation of sophisticated phenomena, such as phase transitions. The versatility and the efficiency of the presented SPH scheme for deformable solids is illustrated in various experiments.
Triangular Springs for Modeling Nonlinear Membranes
This paper provides a formal connexion between springs and continuum mechanics in the context of onedimensional
and two-dimensional elasticity. In a first stage, the equivalence between tensile springs and the finite element
discretization of stretching energy on planar curves is established. Furthermore, when considering a quadratic strain function of stretch, we introduce a new type of springs called tensile biquadratic springs. In a second stage, we extend this equivalence to non-linear membranes (St Venant-Kirchhoff materials) on triangular meshes leading to triangular biquadratic and quadratic springs. Those tensile and angular springs produce isotropic deformations parameterized by Young modulus and Poisson ratios on unstructured meshes in an efficient and simple way. For a specific choice of the Poisson ratio, 0.3, we show that regular spring-mass models may be used realistically to simulate a membrane behavior. Finally, the different spring formulations are tested in pure traction and cloth simulation experiments.
An Edge-Based Computationally Efficient Formulation of Saint-Venant Kirchhoff Tetrahedral Finite Elements
This article describes a computationally efficient formulation and an algorithm for tetrahedral finite-element simulation of elastic objects subject to Saint Venant-Kirchhoff (StVK) material law. The number of floating point operations required by the algorithm is in the range of 15% to 27% for computing the vertex forces from a given set of vertex positions, and 27% to 38% for the tangent stiffness matrix, in comparison to a well-optimized algorithm directly derived from the conventional Total Lagrangian formulation. In the new algorithm, the data is associated with edges and tetrahedron-sharing edge-pairs (TSEPs), as opposed to tetrahedra, to avoid redundant computation. Another characteristic of the presented formulation is that it reduces to that of a spring-network model by simply ignoring all the TSEPs. The technique is demonstrated through an interactive application involving haptic interaction, being combined with a linearized implicit integration technique employing a preconditioned conjugate gradient method.