Month: May 2024

Junwei Zhou, Duowen Chen, Molin Deng, Yitong Deng, Yuchen Sun, Sinan Wang, Shiying Xiong, Bo Zhu

We propose a novel Particle Flow Map (PFM) method to enable accurate long-range advection for incompressible fluid simulation. The foundation of our method is the observation that a particle trajectory generated in a forward simulation naturally embodies a perfect flow map. Centered on this concept, we have developed an Eulerian-Lagrangian framework comprising four essential components: Lagrangian particles for a natural and precise representation of bidirectional flow maps; a dual-scale map representation to accommodate the mapping of various flow quantities; a particle-to-grid interpolation scheme for accurate quantity transfer from particles to grid nodes; and a hybrid impulse-based solver to enforce incompressibility on the grid. The efficacy of PFM has been demonstrated through various simulation scenarios, highlighting the evolution of complex vortical structures and the details of turbulent flows. Notably, compared to NFM, PFM reduces computing time by up to 49 times and memory consumption by up to 41%, while enhancing vorticity preservation as evidenced in various tests like
leapfrog, vortex tube, and turbulent flow.

Eulerian-Lagrangian Fluid Simulation on Particle Flow Maps

Octave Crespel , Emile Hohnadel, Thibaut Métivet, Florence Bertails-Descoubes

Computer Graphics has a long history in the design of effective algorithms for handling contact and friction between solid objects. For the sake of simplicity, most methods rely on low-order primitives such as line segments or triangles, both for the detection and the response stages. In this paper we carefully analyse, in the case of fibre systems, the impact of such choices on the retrieved contact forces. We highlight the presence of force artifacts due to the low-order geometry used for contact detection, that appear all the more visible as the fibre geometry at contact is curved. To remove such artifacts we develop an accurate detection scheme between two smooth curves, relying on an efficient adaptive pruning strategy. We use this algorithm to detect contact between super-helices at high precision, allowing us to recover, in the range of wavy to highly curly fibres, much smoother force profiles than with a classical segment-based strategy. Furthermore, our approach offers better scaling properties in terms of efficiency vs. precision compared to segment-based approaches, making it attractive for applications where accurate and reliable forces are desired. Finally, we demonstrate the robustness and accuracy of our fully high-order approach on a challenging hair combing scenario.

Contact detection between curved fibres: high order makes a difference

Yizhou Chen, Yushan Han, Jingyu Chen, Joseph Teran

Position based dynamics is a powerful technique for simulating a variety of materials. Its primary strength is its robustness when run with limited computational budget. We develop a novel approach to address problems with PBD for quasistatic hyperelastic materials. Even though PBD is based on the projection of static constraints, PBD is best suited for dynamic simulations. This is particularly relevant since the efficient creation of large data sets of plausible, but not necessarily accurate elastic equilibria is of increasing importance with the emergence of quasistatic neural networks. Furthermore, PBD projects one constraint at a time. We show that ignoring the effects of neighboring constraints limits its convergence and stability properties. Recent works have shown that PBD can be related to the Gauss-Seidel approximation of a Lagrange multiplier formulation of backward Euler time stepping, where each constraint is solved/projected independently of the others in an iterative fashion. We show that a position-based, rather than constraint-based nonlinear Gauss-Seidel approach solves these problems. Our approach retains the essential PBD feature of stable behavior with constrained computational budgets, but also allows for convergent behavior with expanded budgets. We demonstrate the efficacy of our method on a variety of representative hyperelastic problems and show that both successive over relaxation (SOR) and Chebyshev acceleration can be easily applied.

Position-Based Nonlinear Gauss-Seidel for Quasistatic Hyperelasticity

Leticia Mattos Da Silva, Oded Stein, Justin Solomon

We introduce a framework for solving a class of parabolic partial differential equations on triangle mesh surfaces, including the Hamilton-Jacobi equation and the Fokker-Planck equation. PDE in this class often have nonlinear or stiff terms that cannot be resolved with standard methods on curved triangle meshes. To address this challenge, we leverage a splitting integrator combined with a convex optimization step to solve these PDE. Our machinery can be used to compute entropic approximation of optimal transport distances on geometric domains, overcoming the numerical limitations of the state-of-the-art method. In addition, we demonstrate the versatility of our method on a number of linear and nonlinear PDE that appear in diffusion and front propagation tasks in geometry processing.

A Framework for Solving Parabolic Partial Differential Equations on Discrete Domains

Shusen Liu, Xiaowei He, Yuzhong Guo, Yue Chang, Wencheng Wang

Tensile instability is one of the major obstacles to particle methods in fluid simulation, which would cause particles to clump in pairs under tension and prevent fluid simulation to generate small-scale thin features. To address this issue, previous particle methods either use a background pressure or a finite difference scheme to alleviate the particle clustering artifacts, yet still fail to produce small-scale thin features in free-surface flows. In this paper, we propose a dual-particle approach for simulating incompressible fluids. Our approach involves incorporating supplementary virtual particles designed to capture and store particle pressures. These pressure samples undergo systematic redistribution at each time step, grounded in the initial positions of the fluid particles. By doing so, we effectively reduce tensile instability in standard SPH by narrowing down the unstable regions for particles experiencing tensile stress. As a result, we can accurately simulate free-surface flows with rich small-scale thin features, such as droplets, streamlines, and sheets, as demonstrated by experimental results.

A Dual-Particle Approach for Incompressible SPH Fluids

Xingyu Ni*, Ruicheng Wang* (joint 1st authors), Bin Wang, Baoquan Chen

This paper introduces a novel Induce-on-Boundary (IoB) solver designed to address the magnetostatic governing equations of ferrofluids. The IoB solver is based on a single-layer potential and utilizes only the surface point cloud of the object, offering a lightweight, fast, and accurate solution for calculating magnetic fields. Compared to existing methods, it eliminates the need for complex linear system solvers and maintains minimal computational complexities. Moreover, it can be seamlessly integrated into conventional fluid simulators without compromising boundary conditions. Through extensive theoretical analysis and experiments, we validate both the convergence and scalability of the IoB solver, achieving state-of-the-art performance. Additionally, a straightforward coupling approach is proposed and executed to showcase the solver’s effectiveness when integrated into a grid-based fluid simulation pipeline, allowing for realistic simulations of representative ferrofluid instabilities.

An Induce-on-Boundary Magnetostatic Solver for Grid-Based Ferrofluids

Aryamaan Jain, Bedrich Benes, Guillaume Cordonnier

Erosion simulation is a common approach used for generating and authoring mountainous terrains. While water is considered the primary erosion factor, its simulation fails to capture steep slopes near the ridges. In these low-drainage areas, erosion is often approximated with slope-reducing erosion, which yields unrealistically uniform slopes. However, geomorphology observed that another process dominates the low-drainage areas: erosion by debris flow, which is a mixture of mud and rocks triggered by strong climatic events. We propose a new method to capture the interactions between debris flow and fluvial erosion thanks to a new mathematical formulation for debris flow erosion derived from geomorphology and a unified GPU algorithm for erosion and deposition. In particular, we observe that sediment and debris deposition tend to intersect river paths, which motivates the design of a new, approximate flow routing algorithm on the GPU to estimate the water path out of these newly formed depressions. We demonstrate that debris flow carves distinct patterns in the form of erosive scars on steep slopes and cones of deposited debris competing with fluvial erosion downstream.

Efficient Debris-flow Simulation for Steep Terrain Erosion

Logan Numerow, Yue Li, Stelian Coros, Bernhard Thomaszewski

Navigating topological transitions in cellular mechanical systems is a significant challenge for existing simulation methods. While abstract models lack predictive capabilities at the cellular level, explicit network representations struggle with topology changes, and per-cell representations are computationally too demanding for large-scale simulations. To address these challenges, we propose a novel cell-centered approach based on differentiable Voronoi diagrams. Representing each cell with a Voronoi site, our method defines shape and topology of the interface network implicitly. In this way, we substantially reduce the number of problem variables, eliminate the need for explicit contact handling, and ensure continuous geometry changes during topological transitions. Closed-form derivatives of network positions facilitate simulation with Newton-type methods for a wide range of per-cell energies. Finally, we extend our differentiable Voronoi diagrams to enable coupling with arbitrary rigid and deformable boundaries. We apply our approach to a diverse set of examples, highlighting splitting and merging of cells as well as neighborhood changes. We illustrate applications to inverse problems by matching soap foam simulations to real-world images. Comparative analysis with explicit cell models reveals that our method achieves qualitatively comparable results at significantly faster computation times.

Differentiable Voronoi Diagrams for Simulation of Cell-Based Mechanical Systems

Peter Heiss-Synak*, Aleksei Kalinov*, Malina Strugaru, Arian Etemadi, Huidong Yang, Chris Wojtan (*joint first authors)

We introduce a multi-material non-manifold mesh-based surface tracking algorithm that converts self-intersections into topological changes. Our algorithm generalizes prior work on manifold surface tracking with topological changes: it preserves surface features like mesh-based methods, and it robustly handles topological changes like level set methods. Our method also offers improved efficiency and robustness over the state of the art. We demonstrate the effectiveness of the approach on a range of examples, including complex soap film simulations with thousands of interacting bubbles, and Boolean unions of non-manifold meshes consisting of millions of triangles.

Multi-Material Mesh-Based Surface Tracking with Implicit Topology Changes

Yi-Lu Chen, Mickaël Ly, Chris Wojtan

Current numerical algorithms for simulating friction fall in one of two camps: smooth solvers sacrifice the stable treatment of static friction in exchange for fast convergence, and non-smooth solvers accurately compute friction at convergence rates that are often prohibitive for large graphics applications. We introduce a novel bridge between these two ideas that computes static and dynamic friction stably and efficiently. Our key idea is to convert the highly constrained non-smooth problem into an unconstrained smooth problem using logarithmic barriers that converges to the exact solution as accuracy increases. We phrase the problem as an interior point primal-dual problem that can be solved efficiently with Newton iteration. We observe quadratic convergence despite the non-smooth nature of the original problem, and our method is well-suited for large systems of tightly packed objects with many contact points. We demonstrate the efficacy of our method with stable piles of grains and stacks of objects, complex granular flows, and robust interlocking assemblies of rigid bodies.

Primal-Dual Non-Smooth Friction for Rigid Body Animation