Search

Kinetic solvers for incompressible fluid simulation were designed to run efficiently on massively parallel architectures such as GPUs. While these lattice Boltzmann solvers have recently proven much faster and more accurate than the macroscopic Navier-Stokes-based solvers traditionally used in graphics, it systematically comes at the price of a very large memory requirement: a mesoscopic discretization of statistical mechanics requires over an order of magnitude more variables per grid node than most fluid solvers in graphics. In order to open up kinetic simulation to gaming and simulation software packages on commodity hardware, we propose a HighOrder Moment-Encoded Lattice-Boltzmann-Method solver which we coined HOME-LBM, requiring only the storage of a few moments per grid node, with little to no loss of accuracy in the typical simulation scenarios encountered in graphics. We show that our lightweight and lightspeed fluid solver requires three times less memory and runs ten times faster than state-of-the-art kinetic solvers, for a nearly-identical visual output. [ABSTRACT FROM AUTHOR]

Virtual wind tunnel testing is a key ingredient in the engineering design process for the automotive and aeronautical industries as well as for urban planning: through visualization and analysis of the simulation data, it helps optimize lift and drag coefficients, increase peak speed, detect high pressure zones, and reduce wind noise at low cost prior to manufacturing. In this paper, we develop an efficient and accurate virtual wind tunnel system based on recent contributions from both computer graphics and computational fluid dynamics in high-performance kinetic solvers. Running on one or multiple GPUs, our massively-parallel lattice Boltzmann model meets industry standards for accuracy and consistency while exceeding current mainstream industrial solutions in terms of efficiency --- especially for unsteady turbulent flow simulation at very high Reynolds number (on the order of 107) --- due to key contributions in improved collision modeling and boundary treatment, automatic construction of multiresolution grids for complex models, as well as performance optimization. We demonstrate the efficacy and reliability of our virtual wind tunnel testing facility through comparisons of our results to multiple benchmark tests, showing an increase in both accuracy and efficiency compared to state-of-the-art industrial solutions. We also illustrate the fine turbulence structures that our system can capture, indicating the relevance of our solver for both VFX and industrial product design. [ABSTRACT FROM AUTHOR]

Real-life flows exhibit complex and visually appealing behaviors such as bubbling, splashing, glugging and wetting that simulation techniques in graphics have attempted to capture for years. While early approaches were not capable of reproducing multiphase flow phenomena due to their excessive numerical viscosity and low accuracy, kinetic solvers based on the lattice Boltzmann method have recently demonstrated the ability to simulate water-air interaction at high Reynolds numbers in a massively-parallel fashion. However, robust and accurate handling of fluid-solid coupling has remained elusive: be it for CG or CFD solvers, as soon as the motion of immersed objects is too fast or too sudden, pressures near boundaries and interfacial forces exhibit spurious oscillations leading to blowups. Built upon a phase-field and velocity-distribution based lattice-Boltzmann solver for multiphase flows, this paper spells out a series of numerical improvements in momentum exchange, interfacial forces, and two-way coupling to drastically reduce these typical artifacts, thus significantly expanding the types of fluid-solid coupling that we can efficiently simulate. We highlight the numerical benefits of our solver through various challenging simulation results, including comparisons to previous work and real footage. [ABSTRACT FROM AUTHOR]

Given a complex three-dimensional domain delimited by a closed and non-degenerate input triangle mesh without any self-intersection, a common geometry processing task consists in cutting up the domain into cells through a set of planar cuts, creating a "cut-cell mesh", i.e., a volumetric decomposition of the domain amenable to visualization (e.g., exploded views), animation (e.g., virtual surgery), or simulation (finite volume computations). A large number of methods have proposed either efficient or robust solutions, sometimes restricting the cuts to form a regular or adaptive grid for simplicity; yet, none can guarantee both properties, severely limiting their usefulness in practice. At the core of the difficulty is the determination of topological relationships among large numbers of vertices, edges, faces and cells in order to assemble a proper cut-cell mesh: while exact geometric computations provide a robust solution to this issue, their high computational cost has prompted a number of faster solutions based on, e.g., local floating-point angle sorting to significantly accelerate the process --- but losing robustness in doing so. In this paper, we introduce a new approach to planar cutting of 3D domains that substitutes topological inference for numerical ordering through a novel mesh data structure, and revert to exact numerical evaluations only in the few rare cases where it is strictly necessary. We show that our novel concept of topological cuts exploits the inherent structure of cut-cell mesh generation to save computational time while still guaranteeing exactness for, and robustness to, arbitrary cuts and surface geometry. We demonstrate the superiority of our approach over state-of-the-art methods on almost 10,000 meshes with a wide range of geometric and topological complexity. We also provide an open source implementation. [ABSTRACT FROM AUTHOR]

Real-life multiphase flows exhibit a number of complex and visually appealing behaviors, involving bubbling, wetting, splashing, and glugging. However, most state-of-the-art simulation techniques in graphics can only demonstrate a limited range of multiphase flow phenomena, due to their inability to handle the real water-air density ratio and to the large amount of numerical viscosity introduced in the flow simulation and its coupling with the interface. Recently, kinetic-based methods have achieved success in simulating large density ratios and high Reynolds numbers efficiently; but their memory overhead, limited stability, and numerically-intensive treatment of coupling with immersed solids remain enduring obstacles to their adoption in movie productions. In this paper, we propose a new kinetic solver to couple the incompressible Navier-Stokes equations with a conservative phase-field equation which remedies these major practical hurdles. The resulting two-phase immiscible fluid solver is shown to be efficient due to its massively-parallel nature and GPU implementation, as well as very versatile and reliable because of its enhanced stability to large density ratios, high Reynolds numbers, and complex solid boundaries. We highlight the advantages of our solver through various challenging simulation results that capture intricate and turbulent air-water interaction, including comparisons to previous work and real footage. [ABSTRACT FROM AUTHOR]

Singularity editing of a quadrangle mesh consists in shifting singularities around for either improving the quality of the mesh elements or canceling extraneous singularities, so as to increase mesh regularity. However, the particular structure of a quad mesh renders the exploration of allowable connectivity changes non-local and hard to automate. In this paper, we introduce a simple, principled, and general quad-mesh editing primitive with which pairs of arbitrarily distant singularities can be efficiently displaced around a mesh through a deterministic and reversible chain of local topological operations with a minimal footprint. Dubbed Q-zip as it acts as a zipper opening up and collapsing down quad strips, our practical mesh operator for singularity editing can be easily implemented via parallel transport of a reference compass between any two irregular vertices. Batches of Q-zips performed in parallel can then be used for efficient singularity editing. [ABSTRACT FROM AUTHOR]

Predicting the fine and intricate details of a turbulent flow field in both space and time from a coarse input remains a major challenge despite the availability of modern machine learning tools. In this paper, we present a simple and effective dictionary-based approach to spatio-temporal upsampling of fluid simulation. We demonstrate that our neural network approach can reproduce the visual complexity of turbulent flows from spatially and temporally coarse velocity fields even when using a generic training set. Moreover, since our method generates finer spatial and/or temporal details through embarrassingly-parallel upsampling of small local patches, it can efficiently predict high-resolution turbulence details across a variety of grid resolutions. As a consequence, our method offers a whole range of applications varying from fluid flow upsampling to fluid data compression. We demonstrate the efficiency and generalizability of our method for synthesizing turbulent flows on a series of complex examples, highlighting dramatically better results in spatio-temporal upsampling and flow data compression than existing methods as assessed by both qualitative and quantitative comparisons. [ABSTRACT FROM AUTHOR]

The intricate motions and complex vortical structures generated by the interaction between fluids and solids are visually fascinating. However, reproducing such a two-way coupling between thin objects and turbulent fluids numerically is notoriously challenging and computationally costly: existing approaches such as cut-cell or immersed-boundary methods have difficulty achieving physical accuracy, or even visual plausibility, of simulations involving fast-evolving flows with immersed objects of arbitrary shapes. In this paper, we propose an efficient and versatile approach for simulating two-way fluid-solid coupling within the kinetic (lattice-Boltzmann) fluid simulation framework, valid for both laminar and highly turbulent flows, and for both thick and thin objects. We introduce a novel hybrid approach to fluid-solid coupling which systematically involves a mesoscopic double-sided bounce-back scheme followed by a cut-cell velocity correction for a more robust and plausible treatment of turbulent flows near moving (thin) solids, preventing flow penetration and reducing boundary artifacts significantly. Coupled with an efficient approximation to simplify geometric computations, the whole boundary treatment method preserves the inherent massively parallel computational nature of the kinetic method. Moreover, we propose simple GPU optimizations of the core LBM algorithm which achieve an even higher computational efficiency than the state-of-the-art kinetic fluid solvers in graphics. We demonstrate the accuracy and efficacy of our two-way coupling through various challenging simulations involving a variety of rigid body solids and fluids at both high and low Reynolds numbers. Finally, comparisons to existing methods on benchmark data and real experiments further highlight the superiority of our method. [ABSTRACT FROM AUTHOR]

Many computer graphics applications boil down to solving sparse systems of linear equations. While the current arsenal of numerical solvers available in various specialized libraries and for different computer architectures often allow efficient and scalable solutions to image processing, modeling and simulation applications, an increasing number of graphics problems face large-scale and ill-conditioned sparse linear systems --- a numerical challenge which typically chokes both direct factorizations (due to high memory requirements) and iterative solvers (because of slow convergence). We propose a novel approach to the efficient preconditioning of such problems which often emerge from the discretization over unstructured meshes of partial differential equations with heterogeneous and anisotropic coefficients. Our numerical approach consists in simply performing a fine-to-coarse ordering and a multiscale sparsity pattern of the degrees of freedom, using which we apply an incomplete Cholesky factorization. By further leveraging supernodes for cache coherence, graph coloring to improve parallelism and partial diagonal shifting to remedy negative pivots, we obtain a preconditioner which, combined with a conjugate gradient solver, far exceeds the performance of existing carefully-engineered libraries for graphics problems involving bad mesh elements and/or high contrast of coefficients. We also back the core concepts behind our simple solver with theoretical foundations linking the recent method of operator-adapted wavelets used in numerical homogenization to the traditional Cholesky factorization of a matrix, providing us with a clear bridge between incomplete Cholesky factorization and multiscale analysis that we leverage numerically. [ABSTRACT FROM AUTHOR]

Multiphase flows exhibit a large realm of complex behaviors such as bubbling, glugging, wetting, and splashing which emerge from air-water and water-solid interactions. Current fluid solvers in graphics have demonstrated remarkable success in reproducing each of these visual effects, but none have offered a model general enough to capture all of them concurrently. In contrast, computational fluid dynamics have developed very general approaches to multiphase flows, typically based on kinetic models. Yet, in both communities, there is dearth of methods that can simulate density ratios and Reynolds numbers required for the type of challenging real-life simulations that movie productions strive to digitally create, such as air-water flows. In this article, we propose a kinetic model of the coupling of the Navier-Stokes equations with a conservative phase-field equation, and provide a series of numerical improvements over existing kinetic-based approaches to offer a general multiphase flow solver. The resulting algorithm is embarrassingly parallel, conservative, far more stable than current solvers even for real-life conditions, and general enough to capture the typical multiphase flow behaviors. Various simulation results are presented, including comparisons to both previous work and real footage, to highlight the advantages of our new method. [ABSTRACT FROM AUTHOR]

Simulating turbulent smoke flows with fine details is computationally intensive. For iterative editing or simply faster generation, efficiently upsampling a low-resolution numerical simulation is an attractive alternative. We propose a novel learning approach to the dynamic upsampling of smoke flows based on a training set of flows at coarse and fine resolutions. Our multiscale neural network turns an input coarse animation into a sparse linear combination of small velocity patches present in a precomputed over-complete dictionary. These sparse coefficients are then used to generate a high-resolution smoke animation sequence by blending the fine counterparts of the coarse patches. Our network is initially trained from a sequence of example simulations to both construct the dictionary of corresponding coarse and fine patches and allow for the fast evaluation of a sparse patch encoding of any coarse input. The resulting network provides an accurate upsampling when the coarse input simulation is well approximated by patches present in the training set (e.g., for re-simulation), or simply visually plausible upsampling when input and training sets differ significantly. We show a variety of examples to ascertain the strengths and limitations of our approach and offer comparisons to existing approaches to demonstrate its quality and effectiveness. [ABSTRACT FROM AUTHOR]

In this paper, we provide a numerical tool to study a material's coherence from a set of 2D Lagrangian trajectories sampling a dynamical system, i.e., from the motion of passive tracers. We show that eigenvectors of the Burau representation of a topological braid derived from the trajectories have levelsets corresponding to components of the Nielsen–Thurston decomposition of the dynamical system. One can thus detect and identify clusters of space–time trajectories corresponding to coherent regions of the dynamical system by solving an eigenvalue problem. Unlike previous methods, the scalable computational complexity of our braid-based approach allows the analysis of large amounts of trajectories. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a hierarchical construction of material-adapted refinable basis functions and associated wavelets to offer efficient coarse-graining of linear elastic objects. While spectral methods rely on global basis functions to restrict the number of degrees of freedom, our basis functions are locally supported; yet, unlike typical polynomial basis functions, they are adapted to the material inhomogeneity of the elastic object to better capture its physical properties and behavior. In particular, they share spectral approximation properties with eigenfunctions, offering a good compromise between computational complexity and accuracy. Their construction involves only linear algebra and follows a fine-to-coarse approach, leading to a block-diagonalization of the stiffness matrix where each block corresponds to an intermediate scale space of the elastic object. Once this hierarchy has been precomputed, we can simulate an object at runtime on very coarse resolution grids and still capture the correct physical behavior, with orders of magnitude speedup compared to a fine simulation. We show on a variety of heterogeneous materials that our approach outperforms all previous coarse-graining methods for elasticity. [ABSTRACT FROM AUTHOR]

We present a compendium of Hodge decompositions of vector fields on tetrahedral meshes embedded in the 3D Euclidean space. After describing the foundations of the Hodge decomposition in the continuous setting, we describe how to implement a five-component orthogonal decomposition that generically splits, for a variety of boundary conditions, any given discrete vector field expressed as discrete differential forms into two potential fields, as well as three additional harmonic components that arise from the topology or boundary of the domain. The resulting decomposition is proper and mimetic, in the sense that the theoretical dualities on the kernel spaces of vector Laplacians valid in the continuous case (including correspondences to cohomology and homology groups) are exactly preserved in the discrete realm. Such a decomposition only involves simple linear algebra with symmetric matrices, and can thus serve as a basic computational tool for vector field analysis in graphics, electromagnetics, fluid dynamics and elasticity. [ABSTRACT FROM AUTHOR]

In this paper, an efficient and scalable approach for simulating inhomogeneous and non-linear elastic objects is introduced. Our numerical coarsening approach consists in optimizing non-conforming and matrix-valued shape functions to allow for predictive simulation of heterogeneous materials with non-linear constitutive laws even on coarse grids, thus saving orders of magnitude in computational time compared to traditional finite element computations. The set of local shape functions over coarse elements is carefully tailored in a preprocessing step to balance geometric continuity and local material stiffness. In particular, we do not impose continuity of our material-aware shape functions between neighboring elements to significantly reduce the fictitious numerical stiffness that conforming bases induce; however, we enforce crucial geometric and physical properties such as partition of unity and exact reproduction of representative fine displacements to eschew the use of discontinuous Galerkin methods. We demonstrate that we can simulate, with no parameter tuning, inhomogeneous and non-linear materials significantly better than previous approaches that traditionally try to homogenize the constitutive model instead. [ABSTRACT FROM AUTHOR]

We introduce an approach to quadrilateral meshing of arbitrary triangulated surfaces that combines the theoretical guarantees of Morse-based approaches with the practical advantages of parameterization methods. We first construct, through an eigensolver followed by a few Gauss-Newton iterations, a periodic four-dimensional vector field that aligns with a user-provided frame field and/or a set of features over the input mesh. A field-aligned parameterization is then greedily computed along a spanning tree based on the Dirichlet energy of the optimal periodic vector field, from which quad elements are efficiently extracted over most of the surface. The few regions not yet covered by elements are then upsampled and the first component of the periodic vector field is used as a Morse function to extract the remaining quadrangles. This hybrid parameterization- and Morse-based quad meshing method is not only fast (the parameterization is greedily constructed, and the Morse function only needs to be upsampled in the few uncovered patches), but is guaranteed to provide a feature-aligned quad mesh with non-degenerate cells that closely matches the input frame field over an arbitrary surface. We show that our approach is much faster than Morse-based techniques since it does not require a densely tessellated input mesh, and is significantly more robust than parameterization-based techniques on models with complex features. [ABSTRACT FROM AUTHOR]

Meshes with curvilinear elements hold the appealing promise of enhanced geometric flexibility and higher-order numerical accuracy compared to their commonly-used straight-edge counterparts. However, the generation of curved meshes remains a computationally expensive endeavor with current meshing approaches: high-order parametric elements are notoriously difficult to conform to a given boundary geometry, and enforcing a smooth and non-degenerate Jacobian everywhere brings additional numerical difficulties to the meshing of complex domains. In this paper, we propose an extension of Optimal Delaunay Triangulations (ODT) to curved and graded isotropic meshes. By exploiting a continuum mechanics interpretation of ODT instead of the usual approximation theoretical foundations, we formulate a very robust geometry and topology optimization of Bézier meshes based on a new simple functional promoting isotropic and uniform Jacobians throughout the domain. We demonstrate that our resulting curved meshes can adapt to complex domains with high precision even for a small count of elements thanks to the added flexibility afforded by more control points and higher order basis functions. [ABSTRACT FROM AUTHOR]

In this paper, we propose a controllable embedding method for high- and low-dimensional geometry processing through sparse matrix eigenanalysis. Our approach is equally suitable to perform non-linear dimensionality reduction on big data, or to offer non-linear shape editing of 3D meshes and pointsets. At the core of our approach is the construction of a multi-Laplacian quadratic form that is assembled from local operators whose kernels only contain locally-affine functions. Minimizing this quadratic form provides an embedding that best preserves all relative coordinates of points within their local neighborhoods. We demonstrate the improvements that our approach brings over existing nonlinear dimensionality reduction methods on a number of datasets, and formulate the first eigen-based as-rigid-as-possible shape deformation technique by applying our affine-kernel embedding approach to 3D data augmented with user-imposed constraints on select vertices. [ABSTRACT FROM AUTHOR]

We introduce an efficient computational method for generating dense and low distortion maps between two arbitrary surfaces of same genus. Instead of relying on semantic correspondences or surface parameterization, we directly optimize a variance-minimizing transport plan between two input surfaces that defines an as-conformal-as-possible inter-surface map satisfying a user-prescribed bound on area distortion. The transport plan is computed via two alternating convex optimizations, and is shown to minimize a generalized Dirichlet energy of both the map and its inverse. Computational efficiency is achieved through a coarse-to-fine approach in diffusion geometry, with Sinkhorn iterations modified to enforce bounded area distortion. The resulting inter-surface mapping algorithm applies to arbitrary shapes robustly, with little to no user interaction. [ABSTRACT FROM AUTHOR]

We present a full geometric parameterization of generalized barycentric coordinates on convex polytopes. We show that these continuous and non-negative coefficients ensuring linear precision can be efficiently and exactly computed through a power diagram of the polytope's vertices and the evaluation point. In particular, we point out that well-known explicit coordinates such as Wachspress, Discrete Harmonic, Voronoi, or Mean Value correspond to simple choices of power weights. We also present examples of new barycentric coordinates, and discuss possible extensions such as power coordinates for non-convex polygons and smooth shapes. [ABSTRACT FROM AUTHOR]

In this paper, we formulate an automatic approach to the detection of partial, local, and global symmetries and orbits in arbitrary 3D datasets. We improve upon existing voting-based symmetry detection techniques by leveraging the Lie group structure of geometric transformations. In particular, we introduce a logarithmic mapping that ensures that orbits are mapped to linear subspaces, hence unifying and extending many existing mappings in a single Lie-algebra voting formulation. Compared to previous work, our resulting method offers significantly improved robustness as it guarantees that our symmetry detection of an input model is frame, scale, and reflection invariant. As a consequence, we demonstrate that our approach efficiently and reliably discovers symmetries and orbits of geometric datasets without requiring heavy parameter tuning. [ABSTRACT FROM AUTHOR]

This paper introduces a new computational method to solve differential equations on subdivision surfaces. Our approach adapts the numerical framework of Discrete Exterior Calculus (DEC) from the polygonal to the subdivision setting by exploiting the refin-ability of subdivision basis functions. The resulting Subdivision Exterior Calculus (SEC) provides significant improvements in accuracy compared to existing polygonal techniques, while offering exact finite-dimensional analogs of continuum structural identities such as Stokes' theorem and Helmholtz-Hodge decomposition. We demonstrate the versatility and efficiency of SEC on common geometry processing tasks including parameterization, geodesic distance computation, and vector field design. [ABSTRACT FROM AUTHOR]