Subspace Condensation: Full Space Adaptivity for Subspace Deformations

Yun Teng, Mark Meyer, Tony DeRose, Theodore Kim

Subspace deformable body simulations can be very fast, but can behave unrealistically when behaviors outside the prescribed subspace, such as novel external collisions, are encountered. We address this limitation by presenting a fast, flexible new method that allows full space computation to be activated in the neighborhood of novel events while the rest of the body still computes in a subspace. We achieve this using a method we call subspace condensation, a variant on the classic static condensation precomputation. However, instead of a precomputation, we use the speed of subspace methods to perform the condensation at every frame. This approach allows the full space regions to be specified arbitrarily at runtime, and forms a natural two-way coupling with the subspace regions. While condensation is usually only applicable to linear materials, the speed of our technique enables its application to non-linear materials as well. We show the effectiveness of our approach by applying it to a variety of articulated character scenarios.

Subspace Condensation: Full Space Adaptivity for Subspace Deformations

Restoring the Missing Vortices in Advection-Projection Fluid Solvers

Xinxin Zhang, Robert Bridson, Chen Greif

Most visual effects fluid solvers use a time-splitting approach where velocity is first advected in the flow, then projected to be incompressible with pressure. Even if a highly accurate advection scheme is used, the self-advection step typically transfers some kinetic energy from divergence-free modes into divergent modes, which are then projected out by pressure, losing energy noticeably for large time steps. Instead of taking smaller time steps or using significantly more complex time integration, we propose a new scheme called IVOCK (Integrated Vorticity of Convective Kinematics) which cheaply captures much of what is lost in self-advection by identifying it as a violation of the vorticity equation. We measure vorticity on the grid before and after advection, taking into account vortex stretching, and use a cheap multigrid V-cycle approximation to a vector potential whose curl will correct the vorticity error. IVOCK works independently of the advection scheme (we present examples with various semi-Lagrangian methods and FLIP), works independently of how boundary conditions are applied (it just corrects error in advection, leaving pressure etc.\ to take care of boundaries and other forces), and other solver parameters (we provide smoke, fire, and water examples). For 10~25% extra computation time per step much larger steps can be used, while producing detailed vorticial structures and convincing turbulence that are lost without correction.

Restoring the Missing Vortices in Advection-Projection Fluid Solvers

Power particles: An incompressible fluid solver based on power diagrams

Fernando de Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, Mathieu Desbrun

This paper introduces a new particle-based approach to incompressible fluid simulation. We depart from previous Lagrangian methods by considering fluid particles no longer purely as material points, but also as volumetric parcels that partition the fluid domain. The fluid motion is described as a time series of well-shaped power diagrams (hence the name power particles), offering evenly spaced particles and accurate pressure computations. As a result, we circumvent the typical excess damping arising from kernel-based evaluations of internal forces or density without having recourse to auxiliary Eulerian grids. The versatility of our solver is demonstrated by the simulation of multiphase flows and free surfaces.

Power Particles: An incompressible fluid solver based on power diagrams

 

SIGGRAPH 2015

It’s my favourite time of the year. Stay tuned for more simulation paper links as they appear. As usual, see Ke-Sen Huang’s page for the full list.

 

TOG papers:

Water Wave Animation via Wavefront Parameter Interpolation

Stefan Jeschke, Chris Wojtan

We present an efficient wavefront tracking algorithm for animating bodies of water that interact with their environment. Our contributions include: a novel wavefront tracking technique that enables dispersion, refraction, reflection, and diffraction in the same simulation; a unique multi-valued function interpolation method that enables our simulations to elegantly sidestep the Nyquist limit; a dispersion approximation for efficiently amplifying the number of simulated waves by several orders of magnitude; and additional extensions that allow for time-dependent effects and interactive artistic editing of the resulting animation. Our contributions combine to give us multitudes more wave details than similar algorithms, while maintaining high frame rates and allowing close camera zooms.

Water Wave Animation via Wavefront Parameter Interpolation

Scalable Partitioning for Parallel Position Based Dynamics

Marco Fratarcangeli, Fabio Pellacini

We introduce a practical partitioning technique designed for parallelizing Position Based Dynamics, and exploit- ing the ubiquitous multi-core processors present in current commodity GPUs. The input is a set of particles whose dynamics is influenced by spatial constraints. In the initialization phase, we build a graph in which each node corresponds to a constraint and two constraints are connected by an edge if they influence at least one com- mon particle. We introduce a novel greedy algorithm for inserting additional constraints (phantoms) in the graph such that the resulting topology is qˆ-colourable, where qˆ ≥ 2 is an arbitrary number. We color the graph, and the constraints with the same color are assigned to the same partition. Then, the set of constraints belonging to each partition is solved in parallel during the animation phase. We demonstrate this by using our partitioning technique; the performance hit caused by the GPU kernel calls is significantly decreased, leaving unaffected the visual quality, robustness and speed of serial position based dynamics.

Scalable Partitioning for Parallel Position Based Dynamics

Implicit Formulation for SPH-Based Viscous Fluids

Tetsuya Takahashi, Yoshinori Dobashi, Issei Fujishiro, Tomoyuki Nishita, Ming C. Lin

We propose a stable and efficient particle-based method for simulating highly viscous fluids that can generate coiling and buckling phenomena and handle variable viscosity. In contrast to previous methods that use explicit integration, our method uses an implicit formulation to improve the robustness of viscosity integration, therefore enabling use of larger time steps and higher viscosities. We use Smoothed Particle Hydrodynamics to solve the full form of viscosity, constructing a sparse linear system with a symmetric positive definite matrix, while exploiting the variational principle that automatically enforces the boundary condition on free surfaces. We also propose a new method for extracting coefficients of the matrix contributed by second-ring neighbor particles to efficiently solve the linear system using a conjugate gradient solver. Several examples demonstrate the robustness and efficiency of our implicit formulation over previous methods and illustrate the versatility of our method.

Implicit Formulation for SPH-Based Viscous Fluids

A Dimension-reduced Pressure Solver for Liquid Simulations

Ryoichi Ando, Nils Thuerey, Chris Wojtan

This work presents a method for efficiently simplifying the pressure projection step in a liquid simulation. We first devise a straightforward dimension reduction technique that dramatically reduces the cost of solving the pressure projection. Next, we introduce a novel change of basis that satisfies free-surface boundary conditions {\em exactly}, regardless of the accuracy of the pressure solve. When combined, these ideas greatly reduce the computational complexity of the pressure solve without compromising free surface boundary conditions at the highest level of detail. Our techniques are easy to parallelize, and they effectively eliminate the computational bottleneck for large liquid simulations.

A Dimension-reduced Pressure Solver for Liquid Simulations

 

Yarn-Level Simulation of Woven Cloth

Gabriel Cirio, Jorge Lopez-Moreno, David Miraut, Miguel A. Otaduy

The large-scale mechanical behavior of woven cloth is determined by the mechanical properties of the yarns, the weave pattern, and frictional contact between yarns. Using standard simulation methods for elastic rod models and yarn-yarn contact handling, the simulation of woven garments at realistic yarn densities is deemed intractable. This paper introduces an efficient solution for simulating woven cloth at the yarn level. Central to our solution is a novel discretization of interlaced yarns based on yarn crossings and yarn sliding, which allows modeling yarn-yarn contact implicitly, avoiding contact handling at yarn crossings altogether. Combined with models for internal yarn forces and inter-yarn frictional contact, as well as a massively parallel solver, we are able to simulate garments with hundreds of thousands of yarn crossings at practical framerates on a desktop machine, showing combinations of large-scale and fine-scale effects induced by yarn-level mechanics.

Yarn-Level Simulation of Woven Cloth