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

Posted by christopherbatty on May 26th, 2018 | Comments Off on Fast Penetration Volume for Rigid Bodies Posted in 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

Posted by christopherbatty on May 26th, 2018 | Comments Off on Extended Narrow Band FLIP for Liquid Simulations Posted in Fluids

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

Posted by christopherbatty on May 25th, 2018 | Comments Off on Learning Three-Dimensional Flow for Interactive Aerodynamic Design Posted in Fluids

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

Posted by christopherbatty on May 23rd, 2018 | Comments Off on Scalable Laplacian Eigenfluids Posted in Fluids

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

Posted by christopherbatty on May 20th, 2018 | Comments Off on Stitch Meshing Posted in Cloth, Hair/Rods/Rope

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

Posted by christopherbatty on May 19th, 2018 | Comments Off on Active Animations of Reduced Deformable Models with Environment Interactions Posted in Uncategorized

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

Posted by christopherbatty on May 16th, 2018 | Comments Off on Immersion of Self-Intersecting Solids and Surfaces Posted in Deformables

Automatically Distributing Eulerian and Hybrid Fluid Simulations in the Cloud

Omid Mashayekhi, Chinmayee Shah, Hang Qu, Andrew Lim, Philip Levis
Distributing a simulation across many machines can drastically speed up computations and increase detail. The computing cloud provides tremendous computing resources, but weak service guarantees force programs to manage significant system complexity: nodes, networks, and storage occasionally perform poorly or fail. We describe Nimbus, a system that automatically distributes grid-based and hybrid simulations across cloud computing nodes. The main simulation loop is sequential code and launches distributed computations across many cores. The simulation on each core runs as if it is stand-alone: Nimbus automatically stitches these simulations into a single, larger one. To do this efficiently, Nimbus introduces a four-layer data model that translates between the contiguous, geometric objects used by simulation libraries and the replicated, fine-grained objects managed by its underlying cloud computing runtime. Using PhysBAM particle level set fluid simulations, we demonstrate that Nimbus can run higher detail simulations faster, distribute simulations on up to 512 cores, and run enormous simulations (10243 cells). Nimbus automatically manages these distributed simulations, balancing load across nodes and recovering from failures. Implementations of PhysBAM water and smoke simulations as well as an open source heat-diffusion simulation show that Nimbus is general and can support complex simulations.

Automatically Distributing Eulerian and Hybrid Fluid Simulations in the Cloud

Posted by christopherbatty on May 16th, 2018 | Comments Off on Automatically Distributing Eulerian and Hybrid Fluid Simulations in the Cloud Posted in Fluids

FEPR: Fast Energy Projection for Real-Time Simulation of Deformable Objects

Dimitar Dinev, Tiantian Liu, Jing Li, Bernhard Thomaszewski, Ladislav Kavan
We propose a novel projection scheme that corrects energy fluctuations in simulations of deformable objects, thereby removing unwanted numerical dissipation and numerical “explosions”. The key idea of our method is to first take a step using a conventional integrator, then project the result back to the constant energy-momentum manifold. We implement this strategy using fast projection, which only adds a small amount of overhead to existing physics-based solvers. We test our method with several implicit integration rules and demonstrate its benefits when used in conjunction with Position Based Dynamics and Projective Dynamics. When added to a dissipative integrator such as backward Euler, our method corrects the artificial damping and thus produces more vivid motion. Our projection scheme also effectively prevents
instabilities that can arise due to approximate solves or large time steps. Our method is fast, stable, and easy to implement—traits that make it well-suited for real-time physics applications such as games or training simulators.

FEPR: Fast Energy Projection for Real-Time Simulation of Deformable Objects

Posted by christopherbatty on May 16th, 2018 | Comments Off on FEPR: Fast Energy Projection for Real-Time Simulation of Deformable Objects Posted in Deformables

Anderson Acceleration for Geometry Optimization and Physics Simulation

Yue Peng, Bailin Deng, Juyong Zhang, Fanyu Geng, Wenjie Qin, Ligang liu

Many computer graphics problems require computing geometric shapes subject to certain constraints. This often results in non-linear and non-convex optimization problems with globally coupled variables, which pose great challenge for interactive applications. Local-global solvers developed in recent years can quickly compute an approximate solution to such problems, making them an attractive choice for applications that prioritize efficiency over accuracy. However, these solvers suffer from lower convergence rate, and may take a long time to compute an accurate result. In this paper, we propose a simple and effective technique to accelerate the convergence of such solvers. By treating each local-global step as a fixed-point iteration, we apply Anderson acceleration, a well-established technique for fixed-point solvers, to speed up the convergence of a local-global solver. To address the stability issue of classical Anderson acceleration, we propose a simple strategy to guarantee the decrease of target energy and ensure its global convergence. In addition, we analyze the connection between Anderson acceleration and quasi-Newton methods, and show that the canonical choice of its mixing parameter is suitable for accelerating local-global solvers. Moreover, our technique is effective beyond classical local-global solvers, and can be applied to iterative methods with a common structure. We evaluate the performance of our technique on a variety of geometry optimization and physics simulation problems. Our approach significantly reduces the number of iterations required to compute an accurate result, with only a slight increase of computational cost per iteration. Its simplicity and effectiveness makes it a promising tool for accelerating existing algorithms as well as designing efficient new algorithms.

Anderson Acceleration for Geometry Optimization and Physics Simulation

Posted by christopherbatty on May 16th, 2018 | Comments Off on Anderson Acceleration for Geometry Optimization and Physics Simulation Posted in Deformables
« Older Entries
Newer Entries »