Month: May 2018

An Implicit Frictional Contact Solver for Adaptive Cloth Simulation

Jie Li, Gilles Daviet, Rahul Narain, Florence Bertails-Descoubes, Matthew Overby, George Brown, Laurence Boissieux

Cloth dynamics plays an important role in the visual appearance of moving characters. Properly accounting for contact and friction is of utmost importance to avoid cloth-body and cloth-cloth penetration and to capture typical folding and stick-slip behavior due to dry friction. We present here the first method able to account for cloth contact with exact Coulomb friction, treating both cloth self-contacts and contacts occurring between the cloth and an underlying character. Our key contribution is to observe that for a nodal system like cloth, the frictional contact problem may be formulated based on velocities as primary variables, without having to compute the costly Delassus operator. Then, by reversing the roles classically played by the velocities and the contact impulses, conical complementarity solvers of the literature can be adapted to solve for compatible velocities at nodes. To handle the full complexity of cloth dynamics scenarios, we have extended this base algorithm in two ways: first, towards the accurate treatment of frictional contact at any location of the cloth, through an adaptive node refinement strategy; second, towards the handling of multiple constraints at each node, through the duplication of constrained nodes and the adding of pin constraints between duplicata. Our method allows us to handle the complex cloth-cloth and cloth-body interactions in full-size garments with an unprecedented level of realism compared to former methods, while maintaining reasonable computational timings.

An Implicit Frictional Contact Solver for Adaptive Cloth Simulation

Example-based turbulence style transfer

Syuhei Sato, Yoshinori Dobashi, T. Kim, and Tomoyuki Nishita

Generating realistic fluid simulations remains computationally expensive, and animators can expend enormous effort trying to achieve a desired motion. To reduce such costs, several methods have been developed in which high-resolution turbulence is synthesized as a post process. Since global motion can then be obtained using a fast, low-resolution simulation, less effort is needed to create a realistic animation with the desired behavior. While much research has focused on accelerating the low-resolution simulation, the problem controlling the behavior of the turbulent, high-resolution motion has received little attention. In this paper, we show that style transfer methods from image editing can be adapted to transfer the turbulent style of an existing fluid simulation onto a new one. We do this by extending example-based image synthesis methods to handle velocity fields using a combination of patch-based and optimization-based texture synthesis. Importantly, this approach allows us to incorporate the incompressibility condition. Using our method, a user can easily and intuitively create high-resolution fluid animations that have a desired turbulent motion.

Example-based turbulence style transfer

Hyper-Reduced Projective Dynamics

Christopher Brandt, Elmar Eisemann, Klaus Hildebrandt

We present a method for the real-time simulation of deformable objects that combines the robustness, generality, and high performance of Projective Dynamics with the efficiency and scalability offered by model reduction techniques. The method decouples the cost for time integration from the mesh resolution and can simulate large meshes in real-time. The proposed hyper-reduction of Projective Dynamics combines a novel fast approximation method for constraint projections and a scalable construction of sparse subspace bases. The resulting system achieves real-time rates for large subspaces enabling rich dynamics and can resolve general user interactions, collision constraints, external forces and changes to the materials. The construction of the hyper-reduced system does not require user-interaction and refrains from using training data or modal analysis, which results in a fast preprocessing stage.

Hyper-Reduced Projective Dynamics

Fast Penetration Volume for Rigid Bodies

Dan Nirel, Dani Lischinski

Handling collisions among a large number of bodies can be a performance bottleneck in video games and many other real-time applications. We present a new framework for detecting and resolving collisions using the penetration volume as an interpenetration measure. Given two non-convex polyhedral bodies, a new sampling paradigm locates their near-contact configurations in advance, and stores associated contact information in a compact database. At runtime, we retrieve a given configuration’s nearest neighbors. By taking advantage of the penetration volume’s continuity, cheap geometric methods can use the neighbors to estimate contact information as well as a translational gradient. This results in an extremely fast, geometry-independent, and trivially parallelizable computation, which constitutes the first global volume-based collision resolution. When processing multiple collisions simultaneously on a 4-core processor, the average running cost is as low as 5 microseconds. Furthermore, no additional proximity or contact-regions queries are required. These results are orders of magnitude faster than previous penetration volume approaches.

Fast Penetration Volume for Rigid Bodies

Extended Narrow Band FLIP for Liquid Simulations

Takahiro Sato, Chris Wojtan, Nils Thuerey, Takeo Igarashi, Ryoichi Ando

The Fluid Implicit Particle method (FLIP) reduces numerical dissipation by combining particles with grids. To improve performance, the subsequent narrow band FLIP method (NB-FLIP) uses a FLIP-based fluid simulation only near the liquid surface and a traditional grid-based fluid simulation away from the surface. This spatially-limited FLIP simulation significantly reduces the number of particles and alleviates a computational bottleneck. In this paper, we extend the NB-FLIP idea even further, by allowing a simulation to transition between a FLIP-like fluid simulation and a grid-based simulation in arbitrary locations, not just near the surface. This approach leads to even more savings in memory and computation, because we can concentrate the particles only in areas where they are needed. More importantly, this new method allows us to seamlessly transition to smooth implicit surface geometry wherever the particle-based simulation is unnecessary. Consequently, our method leads to a practical algorithm for avoiding the noisy surface artifacts associated with particle-based liquid simulations, while simultaneously maintaining the benefits of a FLIP simulation in regions of dynamic motion.

Extended Narrow Band FLIP for Liquid Simulations

Learning Three-Dimensional Flow for Interactive Aerodynamic Design

Nobuyuki Umetani, Bernd Bickel

We present a data-driven technique to instantly predict how fluid flows around various three-dimensional objects. Such simulation is useful for computational fabrication and engineering, but is usually computationally expensive since it requires solving the Navier-Stokes equation for many time steps. To accelerate the process, we propose a machine learning framework which predicts aerodynamic forces and velocity and pressure fields given a three-dimensional shape input. Handling detailed free-form three-dimensional shapes in a data-driven framework is challenging because machine learning approaches usually require a consistent parametrization of input and output. We present a novel PolyCube maps-based parametrization that can be computed for three-dimensional shapes at interactive rates. This allows us to efficiently learn the nonlinear response of the flow using a Gaussian process regression. We demonstrate the effectiveness of our approach for the interactive design and optimization of a car body

Learning Three-Dimensional Flow for Interactive Aerodynamic Design

Scalable Laplacian Eigenfluids

Qiaodong Cui, Pradeep Sen, Theodore Kim

The Laplacian Eigenfunction method for fluid simulation, which we refer to as Eigenfluids, introduced an elegant new way to capture intricate fluid flows with near-zero viscosity. However, the approach does not scale well, as the memory cost grows prohibitively with the number of eigenfunctions. The method also lacks generality, because the dynamics are constrained to a closed box with Dirichlet boundaries, while open, Neumann boundaries are also needed in most practical scenarios. To address these limitations, we present a set of analytic eigenfunctions that supports uniform Neumann and Dirichlet conditions along each domain boundary, and show that by carefully applying the discrete sine and cosine transforms, the storage costs of the eigenfunctions can be made completely negligible. The resulting algorithm is both faster and more memory-efficient than previous approaches, and able to achieve lower viscosities than similar pseudo-spectral methods. We are able to surpass the scalability of the original Laplacian Eigenfunction approach by over two orders of magnitude when simulating rectangular domains. Finally, we show that the formulation allows forward scattering to be directed in a way that is not possible with any other method.

Scalable Laplacian Eigenfluids

Stitch Meshing

Kui Wu, Xifeng Gao, Zachary Ferguson, Daniele Panozzo, Cem Yuksel

We introduce the first fully automatic pipeline to convert arbitrary 3D shapes into knit models. Our pipeline is based on a global parametrization remeshing pipeline to produce an isotropic quad-dominant mesh aligned with a 2-RoSy field. The knitting directions over the surface are determined using a set of custom topological operations and a two-step global optimization that minimizes the number of irregularities. The resulting mesh is converted into a valid stitch mesh that represents the knit model. The yarn curves are generated from the stitch mesh and the final yarn geometry is computed using a yarn-level relaxation process. Thus, we produce topologically valid models that can be used with a yarn-level simulation. We validate our algorithm by automatically generating knit models from complex 3D shapes and processing over a hundred models with various shapes without any user input or parameter tuning. We also demonstrate applications of our approach for custom knit model generation using fabrication via 3D printing.

Stitch Meshing

Active Animations of Reduced Deformable Models with Environment Interactions

Zherong Pan., Dinesh Manocha

We present an efficient spacetime optimization method to automatically generate animations for a general volumetric, elastically deformable body. Our approach can model the interactions between the body and the environment and automatically generate active animations. We model the frictional contact forces using contact invariant optimization and the fluid drag forces using a simplified model. To handle complex objects, we use a reduced deformable model and present a novel hybrid optimizer to search for the local minima efficiently. This allows us to use long-horizon motion planning to automatically generate animations such as walking, jumping, swimming, and rolling. We evaluate the approach on different shapes and animations, including deformable body navigation and combining with an open-loop controller for realtime forward simulation.

Active Animations of Reduced Deformable Models with Environment Interactions

Immersion of Self-Intersecting Solids and Surfaces

Yijing Li, Jernej Barbič

Self-intersecting, or nearly self-intersecting, meshes are commonly found in 2D and 3D computer graphics practice. Self-intersections occur, for example, in the process of artist manual work, as a by-product of procedural methods for mesh generation, or due to modeling errors introduced by scanning equipment. If the space bounded by such inputs is meshed naively, the resulting mesh joins (“glues”) self-overlapping parts, precluding efficient further modeling and animation of the underlying geometry. Similarly, near self-intersections force the simulation algorithm to employ an unnecessarily detailed mesh to separate the nearly self-intersecting regions. Our work addresses both of these challenges, by giving an algorithm to generate an “un-glued” simulation mesh, of arbitrary user-chosen resolution, that properly accounts for self-intersections and near self-intersections. In order to achieve this result, we study the mathematical concept of immersion, and give a deterministic and constructive algorithm to determine if the input self-intersecting triangle mesh is the boundary of an immersion. For near self-intersections, we give a robust algorithm to properly duplicate mesh elements and correctly embed the underlying geometry into the mesh element copies. Both the self-intersections and near self-intersections are combined into one algorithm that permits successful meshing at arbitrary resolution. Applications of our work include volumetric shape editing, physically based simulation and animation, and volumetric weight and geodesic distance computation on self-intersecting inputs.

Immersion of Self-Intersecting Solids and Surfaces