Interactively Cutting and Constraining Vertices in Meshes Using Augmented Matrices

Yu-Hong Yeung, Jessica Crouch, Alex Pothen

We present a finite element solution method that is well-suited for interactive simulations of cutting meshes in the regime of linear elastic models. Our approach features fast updates to the solution of the stiffness system of equations to account for real-time changes in mesh connectivity and boundary conditions. Updates are accomplished by augmenting the stiffness matrix to keep it consistent with the changes to the underlying model, without re-factoring the matrix at each step of cutting. The initial stiffness matrix and its Cholesky factors are used to implicitly form and solve a Schur complement system using an iterative solver. As changes accumulate over many simulation time steps, the augmented solution method slows down due to the size of the augmented matrix. However, by periodically re-factoring the stiffness matrix in a concurrent background process, fresh Cholesky factors that incorporate recent model changes can replace the initial factors. This controls the size of the augmented matrices and provides a way to maintain a fast solution rate as the number of changes to a model grows. We exploit sparsity in the stiffness matrix, the right-hand-side vectors and the solution vectors to compute the solutions fast, and show that the time complexity of the update steps is bounded linearly by the size of the Cholesky factor of the initial matrix. Our complexity analysis and experimental results demonstrate that this approach scales well with problem size. Results for cutting and deformation of 3D linear elastic models are reported for meshes representing the brain, eye, and model problems with element counts up to 167, 000; these show the potential of this method for real-time interactivity. An application to limbal incisions for surgical correction of astigmatism, where linear elastic models and small deformations are sufficient, is included.

Interactively Cutting and Constraining Vertices in Meshes Using Augmented Matrices

Simit: A Language for Physical Simulation

Fredrik Kjolstad, Shoaib Kamil Jonathan Ragan-Kelley, David I.W. Levin,Shinjiro Sueda, Desai Chen, Etienne Vouga, Danny M. Kaufman, Gurtej Kanwar,Wojciech Matusik, and Saman Amarasinghe

Using existing programming tools, writing high-performance simulation code is labor intensive and requires sacrificing readability and portability. The alternative is to prototype simulations in a high-level language like Matlab, thereby sacrificing performance. The Matlab programming model naturally describes the behavior of an entire physical system using the language of linear algebra. However, simulations also manipulate individual geometric elements, which are best represented using linked data structures like meshes. Translating between the linked data structures and linear algebra comes at significant cost, both to the programmer and the machine. High-performance implementations avoid the cost by rephrasing the computation in terms of linked or index data structures, leaving the code complicated and monolithic, often increasing its size by an order of magnitude. In this paper, we present Simit, a new language for physical simulations that lets the programmer view the system both as a linked data structure in the form of a hypergraph, and as a set of global vectors, matrices and tensors depending on what is convenient at any given time. Simit provides a novel assembly construct that makes it conceptually easy and computationally efficient to move between the two abstractions. Using the information provided by the assembly construct, the compiler generates efficient in-place computation on the graph. We demonstrate that Simit is easy to use: a Simit program is typically shorter than a Matlab program; that it is high-performance: a Simit program running sequentially on a CPU performs comparably to hand-optimized simulations; and that it is portable: Simit programs can be compiled for GPUs with no change to the program, delivering 4-20x speedups over our optimized CPU code.

Simit: A Language for Physical Simulation

Liquid boundaries for implicit incompressible SPH

Jens Cornelis, Markus Ihmsen, Andreas Peer, Matthias Teschner

We propose a novel unified particle representation for fluids and solid boundaries in Implicit Incompressible SPH (IISPH). In contrast to existing particle representations, the proposed concept does not require a separate processing of fluid and boundary particles. On one hand, this results in a simplified solver implementation with improved efficiency. On the other hand, the unified fluid and boundary representation adds flexibility to IISPH which enables versatile effects. In particular, particles can now dynamically interchange their role between fluid and boundary which we therefore refer to as liquid boundary. The paper mainly focuses on the description of the unified representation and on the application of the concept to visual effects such as solidification and liquefaction. To support the realization of these effects, the concept of unified fluid and liquid boundary particles is extended to a third particle type, so-called candidate particles that are used in a transition phase between fluid and liquid boundaries.

Liquid boundaries for implicit incompressible SPH

Real-time Hair Mesh Simulation

Kui Wu, Cem Yuksel

We present a robust real-time hair simulation method using hair meshes. Leveraging existing simulation models for sheet-based cloth, we introduce a volumetric force model for incorporating hair interactions inside the hair mesh volume. We also introduce a position correction method that minimizes the local deformation of the hair mesh due to collision handling. We demonstrate the robustness of our hair simulation method using large time steps with fast motion, and we show that our method can recover the initial hair shape even when the hair mesh goes through substantial deformation.

Real-Time Hair Mesh Simulation

Dexterous Manipulation of Cloth

Yunfei Bai, Wenhao Yu, and C. Karen Liu

This paper introduces a new technique to synthesize dexterous manipulation of cloth. Given a simple description of the desired cloth motion, our algorithm computes appropriate joint torques for physically simulated hands, such that, via contact forces, the result of cloth simulation follows the desired motion. Instead of optimizing the hand control forces directly, we formulate an optimization problem that solves for the commanding forces from the hands to the cloth, which have more direct impact on the dynamic state of the hands and that of the cloth. The solution of the optimization provides commanding forces that achieve the desired cloth motion described by the user, while respecting the kinematic constraints of the hands. These commanding forces are then used to guide the joint torques of the hands. To balance between the effectiveness of control and computational costs, we formulate a model-predictive-control problem as a quadratic program at each time step. We demonstrate our technique on a set of cloth manipulation tasks in daily activities, including folding laundry, wringing a towel, and putting on a scarf.

Dexterous Manipulation of Cloth

A Practical Method for High-Resolution Embedded Liquid Surfaces

Ryan Goldade, Christopher Batty, Chris Wojtan

Combining high-resolution level set surface tracking with lower resolution physics is an inexpensive method for achieving highly detailed liquid animations. Unfortunately, the inherent resolution mismatch introduces several types of disturbing visual artifacts. We identify the primary sources of these artifacts and present simple, efficient, and practical solutions to address them. First, we propose an unconditionally stable filtering method that selectively removes sub-grid surface artifacts not seen by the fluid physics, while preserving fine detail in dynamic splashing regions. It provides comparable results to recent error-correction techniques at lower cost, without substepping, and with better scaling behavior. Second, we show how a modified narrow-band scheme can ensure accurate free surface boundary conditions in the presence of large resolution mismatches. Our scheme preserves the efficiency of the narrow-band methodology, while eliminating objectionable stairstep artifacts observed in prior work. Third, we demonstrate that the use of linear interpolation of velocity during advection of the high-resolution level set surface is responsible for visible grid-aligned kinks; we therefore advocate higher-order velocity interpolation, and show that it dramatically reduces this artifact. While these three contributions are orthogonal, our results demonstrate that taken together they efficiently address the dominant sources of visual artifacts arising with high-resolution embedded liquid surfaces; the proposed approach offers improved visual quality, a straightforward implementation, and substantially greater scalability than competing methods.

A Practical Method for High-Resolution Embedded Liquid Surfaces

Modeling and Estimation of Energy-Based Hyperelastic Objects

Eder Miguel, David Miraut, Miguel A. Otaduy

In this paper, we present a method to model hyperelasticity that is well suited for representing the nonlinearity of real-world objects, as well as for estimating it from deformation examples. Previous approaches suffer several limitations, such as lack of integrability of elastic forces, failure to enforce energy convexity, lack of robustness of parameter estimation, or difficulty to model cross-modal effects. Our method avoids these problems by relying on a general energy-based definition of elastic properties. The accuracy of the resulting elastic model is maximized by defining an additive model of separable energy terms, which allow progressive parameter estimation. In addition, our method supports efficient modeling of extreme nonlinearities thanks to energy-limiting constraints. We combine our energy-based model with an optimization method to estimate model parameters from force-deformation examples, and we show successful modeling of diverse deformable objects, including cloth, human finger skin, and internal human anatomy in a medical imaging application.

Modeling and Estimation of Energy-Based Hyperelastic Objects

Narrow Band FLIP for Liquid Simulations

Florian Ferstl, Ryoichi Ando, Chris Wojtan, Rudiger Westermann, Nils Thuerey

The Fluid Implicit Particle method (FLIP) for liquid simulations uses particles to reduce numerical dissipation and provide important visual cues for events like complex splashes and small-scale features near the liquid surface. Unfortunately, FLIP simulations can be computationally expensive, because they require a dense sampling of particles to fill the entire liquid volume. Furthermore, the vast majority of these FLIP particles contribute nothing to the fluid’s visual appearance, especially for larger volumes of liquid. We present a method that only uses FLIP particles within a narrow band of the liquid surface, while efficiently representing the remaining inner volume on a regular grid. We show that a naive realization of this idea introduces unstable and uncontrollable energy fluctuations, and we propose a novel coupling scheme between FLIP particles and regular grid which overcomes this problem. Our method drastically reduces the particle count and simulation times while yielding results that are nearly indistinguishable from regular FLIP simulations. Our approach is easy to integrate into any existing FLIP implementation.

Narrow Band FLIP for Liquid Simulations

CAMA: Contact-Aware Matrix Assembly with Unified Collision Handling for GPU-based Cloth Simulation

Min Tang, Huamin Wang, Le Tang, Ruofeng Tong, Dinesh Manocha

We present a novel GPU-based approach to robustly and efficiently simulate high-resolution and complexly layered cloth. The key component of our formulation is a parallelized matrix assembly algorithm that can quickly build a large and sparse matrix in a compressed format and accurately solve linear systems on GPUs. We also present a fast and integrated solution for parallel collision handling, including collision detection and response computations, which utilizes spatio-temporal coherence. We combine these algorithms as part of a new cloth simulation pipeline that incorporates contact forces into implicit time integration for collision avoidance. The entire pipeline is implemented on GPUs, and we evaluate its performance on complex benchmarks consisting of 100-300K triangles. In practice, our system takes a few seconds to simulate one frame of a complex cloth scene, which represents significant speedups over prior CPU and GPU-based cloth simulation systems.

CAMA: Contact-Aware Matrix Assembly with Unified Collision Handling for GPU-based Cloth Simulation

Eurographics 2016

Eurographics 2016, in Lisbon Portugal, will feature the following physics-related papers: