Physics-Based Animation

Xinxin Zhang, Minchen Li, Robert Bridson

Most fluid scenarios in graphics have a high Reynolds number, where viscosity is dominated by inertial effects, thus most solvers drop viscosity altogether: numerical damping from coarse grids is generally stronger than physical viscosity while resembling it in character. However, viscosity remains crucial near solid boundaries, in the boundary layer, to a large extent determining the look of the flow as a function of Reynolds number. Typical graphics simulations do not resolve boundary layer dynamics, so their look is determined mostly by numerical errors with the given grid size and time step, rather than physical parameters. We introduce two complementary techniques to capture boundary layer dynamics, bringing more physical control and predictability. We extend the FLIP particle-grid method with viscous particle strength exchange[Rivoalen and Huberson 2001] to better transfer momentum at solid boundaries, dubbed VFLIP. We also introduce Weakly Higher Resolution Regional Projection (WHIRP), a cheap and simple way to increase grid resolution where important by overlaying high resolution grids on the global coarse grid.

Resolving Fluid Boundary Layers with Particle Strength Exchange and Weak Adaptivity

SIGGRAPH 2016 papers:

• Ebb: A DSL for Physical Simulation on CPUs and GPUs
• Pose-Space Subspace Dynamics
• Surface-Only Liquids
• Generalized Non-reflecting Boundaries for Fluid Re-Simulation
• Fast Approximations for Boundary Element Based Brittle Fracture Simulation
• Resolving Fluid Boundary Layers with Particle Strength Exchange and Weak Adaptivity
• Drucker-Prager Elastoplasticity for Sand Animation
• A Semi-Implicit Material Point Method for the Continuum Simulation of Granular Materials
• Schrodinger’s Smoke
• Preserving Geometry and Topology for Fluid Flows with Thin Obstacles and Narrow Gaps
• Artist-Directed Dynamics for 2D Animation
• Physics-Driven Pattern Adjustment for Direct 3D Garment Editing
• Example-based Plastic Deformation of Rigid Bodies
• Multiphase SPH Simulation for Interactive Fluids and Solids

TOG presentations at SIGGRAPH 2016:

• Simit: A Language for Physical Simulation
• Interactively cutting and constraining nodes in a mesh by augmented matrices
• Efficient Fluid Simulation on the Surface of a Sphere
• Non-smooth developable geometry for interactively animating paper crumpling

Gilbert Bernstein, Chinmayee Shah, Crystal Lemire, Zachery DeVito, Matthew Fisher, Philip Levis, Pat Hanrahan

Designing programming environments for physical simulation is challenging because simulations rely on diverse algorithms and geometric domains. These challenges are compounded when we try to run efficiently on heterogeneous parallel architectures. We present Ebb, a domain-specific language (DSL) for simulation, that runs efficiently on both CPUs and GPUs. Unlike previous DSLs, Ebb uses a three-layer architecture to separate (1) simulation code, (2) definition of data structures for geometric domains, and (3) runtimes supporting parallel architectures. Different geometric domains are implemented as libraries that use a common, unified, relational data model. By structuring the simulation framework in this way, programmers implementing simulations can focus on the physics and algorithms for each simulation without worrying about their implementation on parallel computers. Because the geometric domain libraries are all implemented using a common runtime based on relations, new geometric domains can be added as needed, without specifying the details of memory management, mapping to different parallel architectures, or having to expand the runtime’s interface. We evaluate Ebb by comparing it to several widely used simulations, demonstrating comparable performance to hand-written GPU code where available, and surpassing existing CPU performance optimizations by up to 9x when no GPU code exists.

Ebb: A DSL for Physical Simulation on CPUs and GPUs

Marcos Sandim, Douglas Cedrim, Luis Gustavo Nonato, Paulo Pagliosa, and Afonso Paiva

This paper presents a novel method to detect free-surfaces on particle-based volume representation. In contrast to most particle-based free-surface detection methods, which perform the surface identification based on physical and geometrical properties derived from the underlying fluid flow simulation, the proposed approach only demands the spatial location of the particles to properly recognize surface particles, avoiding even the use of kernels. Boundary particles are identified through a Hidden Point Removal (HPR) operator used for visibility test. Our method is very simple, fast, easy to implement and robust to changes in the distribution of particles, even when facing large deformation of the free-surface. A set of comparisons against state-of-the-art boundary detection methods show the effectiveness of our approach. The good performance of our method is also attested in the context of fluid flow simulation involving free-surface, mainly when using level-sets for rendering purposes.

Boundary detection in particle-based fluids

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

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

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

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

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

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