Foundations of Computational Mathematics (FoCM, 2024)
We present a discretization of the dynamic optimal transport problem for which we can obtain the convergence rate for the value of the transport cost to its continuous value when the temporal and spatial stepsize vanish. This convergence result does not require any regularity assumption on the measures, though experiments suggest that the rate is not sharp. Via an analysis of the duality gap we also obtain the convergence rates for the gradient of the optimal potentials and the velocity field under mild regularity assumptions. To obtain such rates, we discretize the dual formulation of the dynamic optimal transport problem and use the mature literature related to the error due to discretizing the Hamilton–Jacobi equation.
@article{IshidaLavenant2024DualOT,
author={Ishida, Sadashige
and Lavenant, Hugo},
title={Quantitative Convergence of a Discretization of Dynamic Optimal Transport Using the Dual Formulation},
journal={Foundations of Computational Mathematics},
year={2024},
month={Nov},
day={11},
abstract={We present a discretization of the dynamic optimal transport problem for which we can obtain the convergence rate for the value of the transport cost to its continuous value when the temporal and spatial stepsize vanish. This convergence result does not require any regularity assumption on the measures, though experiments suggest that the rate is not sharp. Via an analysis of the duality gap we also obtain the convergence rates for the gradient of the optimal potentials and the velocity field under mild regularity assumptions. To obtain such rates, we discretize the dual formulation of the dynamic optimal transport problem and use the mature literature related to the error due to discretizing the Hamilton--Jacobi equation.},
issn={1615-3383},
doi={10.1007/s10208-024-09686-3},
url={https://doi.org/10.1007/s10208-024-09686-3}
}
Physics simulation in computer graphics can bring triangle meshes into topologically invalid states. The method in this thesis contributed to Multi-Material Mesh-Based Surface Tracking with Implicit Topology Changes, which presents a non-manifold hybrid surface tracker—a surface tracker that repairs explicit non-manifold triangle meshes with the help of the implicit domain. Specifically, this thesis provides an algorithm for filling the holes that are left after removing problematic parts of the mesh.
@mastersthesis{Etemadi2024,
author = {Etemadi, Arian},
title = {Filling the holes of non-manifold self-intersecting meshes for implicit topology changes in surface tracking},
school = {ISTA},
year = {2024},
month = {10}
}
SIAM Journal on Applied Algebra and Geometry (SIAGA, 2024)
We present a formula for the signed area of a spherical polygon via prequantization. In contrast to the traditional formula based on the Gauss–Bonnet theorem that requires measuring angles, the new formula mimics Green’s theorem and is applicable to a wider range of degenerate spherical curves and polygons.
@article{ChernIshida2024,
author = {Chern, Albert and Ishida, Sadashige},
title = {Area Formula for Spherical Polygons via Prequantization},
journal = {SIAM Journal on Applied Algebra and Geometry},
volume = {8},
number = {3},
pages = {782-796},
year = {2024},
doi = {10.1137/23M1565255},
URL = {https://doi.org/10.1137/23M1565255},
eprint = {https://doi.org/10.1137/23M1565255},
abstract = {We present a formula for the signed area of a spherical polygon via prequantization. In contrast to the traditional formula based on the Gauss–Bonnet theorem that requires measuring angles, the new formula mimics Green’s theorem and is applicable to a wider range of degenerate spherical curves and polygons.}
}
ACM Transactions on Graphics (Siggraph 2024)
The behavior of a rigid body primarily depends on its mass moments, which consist of the mass, center of mass, and moments of inertia. It is possible to manipulate these quantities without altering the geometric appearance of an object by introducing cavities in its interior. Algorithms that find cavities of suitable shapes and sizes have enabled the computational design of spinning tops, yo-yos, wheels, buoys, and statically balanced objects. Previous work is based, for example, on topology optimization on voxel grids, which introduces a large number of optimization variables and box constraints, or offset surface computation, which cannot guarantee that solutions to a feasible problem will always be found.
In this work, we provide a mathematical analysis of constrained topology optimization problems that depend only on mass moments. This class of problems covers, among others, all applications mentioned above. Our main result is to show that no matter the outer shape of the rigid body to be optimized or the optimization objective and constraints considered, the optimal solution always features a quadric-shaped interface between material and cavities. This proves that optimal interfaces are always ellipsoids, hyperboloids, paraboloids, or one of a few degenerate cases, such as planes.
This insight lets us replace a difficult topology optimization problem with a provably equivalent non-linear equation system in a small number (<10) of variables, which represent the coefficients of the quadric. This system can be solved in a few seconds for most examples, provides insights into the geometric structure of many specific applications, and lets us describe their solution properties. Finally, our method integrates seamlessly into modern fabrication workflows because our solutions are analytical surfaces that are native to the CAD domain.
@article{SpinItFasterHafner24,
author = {Hafner, Christian and Ly, Mickaël and Wojtan, Chris},
title = {Spin-It Faster: Quadrics Solve All Topology Optimization Problems That Depend Only On Mass Moments},
year = {2024},
issue_date = {October 2024},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {43},
number = {4},
url = {https://doi.org/10.1145/3658194},
doi = {10.1145/3658194},
journal = {ACM Trans. Graph.},
month = {sep},
articleno = {171},
numpages = {13},
keywords = {Topology Optimization, Mass Moments, Computational Geometry}
}
ACM Transactions on Graphics (Siggraph 2024)
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.
@article{MultimaterialMeshing24,
author = {Heiss-Synak, Peter and Kalinov, Aleksei and Strugaru, Malina and Etemadi, Arian and Yang, Huidong and Wojtan, Chris},
title = {Multi-Material Mesh-Based Surface Tracking with Implicit Topology Changes},
year = {2024},
issue_date = {October 2024},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {43},
number = {4},
journal = {ACM Trans. Graph.},
month = {sep},
articleno = {171},
numpages = {14},
keywords = {surface tracking, topology change, nonmanifold meshes, multi-material flows, solid modeling}
}
ACM Siggraph 2024 Conference Papers
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.
@article{PrimalDualChen24,
author = {Chen, Yi-Lu and Ly, Mickaël and Wojtan, Chris},
title = {Primal–Dual Non-Smooth Friction for Rigid Body Animation},
year = {2024},
issue_date = {October 2024},
publisher = {Association for Computing Machinery},
booktitle = {SIGGRAPH 2024 Conference Papers},
address = {New York, NY, USA},
month = {sep},
numpages = {10},
keywords = {physical simulation, frictional contact, rigid body mechanics, nonsmooth dynamics}
}
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 2023 Posters)
We present a rigid body animation technique which prevents solids from interpenetrating, dissipates energy through friction, and propagates shocks through contacts. We employ the Alternating Direction Method of Multipliers (ADMM) to couple non-smooth Coulomb friction with impact propagation, allowing efficient and accurate non-smooth dynamics along with a correct transmission of impacts through assemblies of rigid bodies. We further extend our method to model adhesion, dynamic friction and lubricated contact.
@inproceedings{FrictionShockChen23,
author = {Chen, Yi-Lu and Ly, Micka\"{e}l and Wojtan, Chris},
title = {Unified treatment of contact, friction and shock-propagation in rigid body animation},
year = {2023},
isbn = {9798400702686},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3606037.3606836},
doi = {10.1145/3606037.3606836},
articleno = {5},
numpages = {2},
keywords = {rigid body mechanics, non-smooth dynamics, friction, adhesion},
location = {Los Angeles, CA, USA},
series = {SCA '23}
}
ACM Transactions on Graphics (Siggraph 2023)
We introduce a compact, intuitive procedural graph representation for cellular metamaterials, which are small-scale, tileable structures that can be architected to exhibit many useful material properties. Because the structures’ “architectures” vary widely—with elements such as beams, thin shells, and solid bulks—it is difficult to explore them using existing representations. Generic approaches like voxel grids are versatile, but it is cumbersome to represent and edit individual structures; architecture-specific approaches address these issues, but are incompatible with one another. By contrast, our procedural graph succinctly represents the construction process for any structure using a simple skeleton annotated with spatially varying thickness. To express the highly constrained triply periodic minimal surfaces (TPMS) in this manner, we present the first fully automated version of the conjugate surface construction method, which allows novices to create complex TPMS from intuitive input. We demonstrate our representation’s expressiveness, accuracy, and compactness by constructing a wide range of established structures and hundreds of novel structures with diverse architectures and material properties. We also conduct a user study to verify our representation’s ease-of-use and ability to expand engineers’ capacity for exploration.
@article{MakaturaMeta23,
author = {Makatura, Liane and Wang, Bohan and Chen, Yi-Lu and Deng, Bolei and Wojtan, Chris and Bickel, Bernd and Matusik, Wojciech},
title = {Procedural Metamaterials: A Unified Procedural Graph for Metamaterial Design},
year = {2023},
issue_date = {October 2023},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {42},
number = {5},
issn = {0730-0301},
url = {https://doi.org/10.1145/3605389},
doi = {10.1145/3605389},
month = {jul},
articleno = {168},
numpages = {19},
keywords = {microstructures, hybrid metamaterials, conjugate surface construction method, procedural representation, procedural graph, shellular, cellular metamaterials, Graph representation, truss structures, triply periodic minimal surfaces (TPMS)}
}
ACM Transactions on Graphics (Siggraph 2023)
This paper introduces a novel method for simulating large bodies of water as a height field. At the start of each time step, we partition the waves into a bulk flow (which approximately satisfies the assumptions of the shallow water equations) and surface waves (which approximately satisfy the assumptions of Airy wave theory). We then solve the two wave regimes separately using appropriate state-of-the-art techniques, and re-combine the resulting wave velocities at the end of each step. This strategy leads to the first heightfield wave model capable of simulating complex interactions between both deep and shallow water effects, like the waves from a boat wake sloshing up onto a beach, or a dam break producing wave interference patterns and eddies. We also analyze the numerical dispersion created by our method and derive an exact correction factor for waves at a constant water depth, giving us a numerically perfect re-creation of theoretical water wave dispersion patterns.
@article{10.1145/3592098,
author = {Jeschke, Stefan and Wojtan, Chris},
title = {Generalizing Shallow Water Simulations with Dispersive Surface Waves},
year = {2023},
issue_date = {August 2023},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {42},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/3592098},
doi = {10.1145/3592098},
month = {jul},
articleno = {83},
numpages = {12},
keywords = {real-time animation, natural phenomena, water animation}
}
ACM Transactions on Graphics (Siggraph Asia 2022)
This paper presents a new representation of curve dynamics, with applications to vortex filaments in fluid dynamics. Instead of representing these filaments with explicit curve geometry and Lagrangian equations of motion, we represent curves implicitly with a new co-dimensional 2 level set description. Our implicit representation admits several redundant mathematical degrees of freedom in both the configuration and the dynamics of the curves, which can be tailored specifically to improve numerical robustness, in contrast to naive approaches for implicit curve dynamics that suffer from overwhelming numerical stability problems. Furthermore, we note how these hidden degrees of freedom perfectly map to a Clebsch representation in fluid dynamics. Motivated by these observations, we introduce untwisted level set functions and non-swirling dynamics which successfully regularize sources of numerical instability, particularly in the twisting modes around curve filaments. A consequence is a novel simulation method which produces stable dynamics for large numbers of interacting vortex filaments and effortlessly handles topological changes and re-connection events.
@article{
iwc2022implicit_filaments,
title = Hidden Degrees of Freedom in Implicit Vortex Filaments,
author = {Sadashige Ishida and Chris Wojtan and Albert Chern}
journal = {ACM Transactions on Graphics},
year = 2022,
volume = 41,
number = 6,
pages = {241:1--241:14},
articleno = 241,
url = {http://dx.doi.org/10.1145/3550454.3555459},
doi = {10.1145/3550454.3555459},
publisher = {ACM}
}
The complex yarn structure of knitted and woven fabrics gives rise to both a mechanical and visual complexity. The small-scale interactions of yarns colliding with and pulling on each other result in drastically different large-scale stretching and bending behavior, introducing anisotropy, curling, and more. While simulating cloth as individual yarns can reproduce this complexity and match the quality of real fabric, it may be too computationally expensive for large fabrics. On the other hand, continuum-based approaches do not need to discretize the cloth at a stitch-level, but it is non-trivial to find a material model that would replicate the large-scale behavior of yarn fabrics, and they discard the intricate visual detail. In this thesis, we discuss three methods to try and bridge the gap between small-scale and large-scale yarn mechanics using numerical homogenization: fitting a continuum model to periodic yarn simulations, adding mechanics-aware yarn detail onto thin-shell simulations, and quantitatively fitting yarn parameters to physical measurements of real fabric.
To start, we present a method for animating yarn-level cloth effects using a thin-shell solver. We first use a large number of periodic yarn-level simulations to build a model of the potential energy density of the cloth, and then use it to compute forces in a thin-shell simulator. The resulting simulations faithfully reproduce expected effects like the stiffening of woven fabrics and the highly deformable nature and anisotropy of knitted fabrics at a fraction of the cost of full yarn-level simulation.
While our thin-shell simulations are able to capture large-scale yarn mechanics, they lack the rich visual detail of yarn-level simulations. Therefore, we propose a method to animate yarn-level cloth geometry on top of an underlying deforming mesh in a mechanics-aware fashion in real time. Using triangle strains to interpolate precomputed yarn geometry, we are able to reproduce effects such as knit loops tightening under stretching at negligible cost.
Finally, we introduce a methodology for inverse-modeling of yarn-level mechanics of cloth, based on the mechanical response of fabrics in the real world. We compile a database from physical tests of several knitted fabrics used in the textile industry spanning diverse physical properties like stiffness, nonlinearity, and anisotropy. We then develop a system for approximating these mechanical responses with yarn-level cloth simulation, using homogenized shell models to speed up computation and adding some small-but-necessary extensions to yarn-level models used in computer graphics.
@phdthesis{SperlThesis2022,
author = {Georg Sperl},
title = {Homogenizing Yarn Simulations: Large-Scale Mechanics, Small-Scale Detail, and Quantitative Fitting},
school = {ISTA},
year = {2022},
month = {9}
}
ACM Transactions on Graphics (Siggraph 2022)
This paper introduces a methodology for inverse-modeling of yarn-level mechanics of cloth, based on the mechanical response of fabrics in the real world. We compiled a database from physical tests of several different knitted fabrics used in the textile industry. These data span different types of complex knit patterns, yarn compositions, and fabric finishes, and the results demonstrate diverse physical properties like stiffness, nonlinearity, and anisotropy. We then develop a system for approximating these mechanical responses with yarn-level cloth simulation. To do so, we introduce an efficient pipeline for converting between fabric-level data and yarn-level simulation, including a novel swatch-level approximation for speeding up computation, and some small-but-necessary extensions to yarn-level models used in computer graphics.
@article{sperl2022eylsmpf,
author = {Sperl, Georg and Sánchez-Banderas, Rosa M. and Li, Manwen and Wojtan, Chris and Otaduy, Miguel A.},
title = {Estimation of Yarn-Level Simulation Models for Production Fabrics},
journal = {ACM Transactions on Graphics (TOG)},
number = {4},
volume = {41},
year = {2022},
publisher = {ACM}
}
Computer Graphics Forum (Eurographics 2022)
This paper proposes a method for simulating liquids in large bodies of water by coupling together a water surface wave simulator with a 3D Navier-Stokes simulator. The surface wave simulation uses the equivalent sources method (ESM) to efficiently animate large bodies of water with precisely controllable wave propagation behavior. The 3D liquid simulator animates complex non-linear fluid behaviors like splashes and breaking waves using off-the-shelf simulators using FLIP or the level set method with semi-Lagrangian advection. We combine the two approaches by using the 3D solver to animate localized non-linear behaviors, and the 2D wave solver to animate larger regions with linear surface physics. We use the surface motion from the 3D solver as boundary conditions for 2D surface wave simulator, and we use the velocity and surface heights from the 2D surface wave simulator as boundary conditions for the 3D fluid simulation. We also introduce a novel technique for removing visual artifacts caused by numerical errors in 3D fluid solvers: we use experimental data to estimate the artificial dispersion caused by the 3D solver and we then carefully tune the wave speeds of the 2D solver to match it, effectively eliminating any differences in wave behavior across the boundary. To the best of our knowledge, this is the first time such a empirically driven error compensation approach has been used to remove coupling errors from a physics simulator. Our coupled simulation approach leverages the strengths of each simulation technique, animating large environments with seamless transitions between 2D and 3D physics.
@article {10.1111:cgf.14478,
journal = "Computer Graphics Forum",
title = "Coupling 3D Liquid Simulation with 2D Wave Propagation for Large Scale Water Surface Animation Using the Equivalent Sources Method",
author = "Schreck, Camille and Wojtan, Chris",
year = "2022",
publisher = "The Eurographics Association and John Wiley & Sons Ltd.",
ISSN = "1467-8659",
DOI = "10.1111/cgf.14478"
}
ACM Transactions on Graphics (Siggraph 2021)
Triangle mesh-based simulations are able to produce satisfying animations of knitted and woven cloth; however, they lack the rich geometric detail of yarn-level simulations. Naive texturing approaches do not consider yarn-level physics, while full yarn-level simulations may become prohibitively expensive for large garments. We propose a method to animate yarn-level cloth geometry on top of an underlying deforming mesh in a mechanics-aware fashion. Using triangle strains to interpolate precomputed yarn geometry, we are able to reproduce effects such as knit loops tightening under stretching. In combination with precomputed mesh animation or real-time mesh simulation, our method is able to animate yarn-level cloth in real-time at large scales.
@article{sperl2021madypg,
author = {Sperl, Georg and Narain, Rahul and Wojtan, Chris},
title = {Mechanics-Aware Deformation of Yarn Pattern Geometry},
journal = {ACM Transactions on Graphics (TOG)},
number = {4},
volume = {40},
year = {2021},
publisher = {ACM}
}
Computer Graphics Forum (SCA 2020)
The “procedural” approach to animating ocean waves is the dominant algorithm for animating larger bodies of water in interactive applications as well as in off-line productions — it provides high visual quality with a low computational demand. In this paper, we widen the applicability of procedural water wave animation with an extension that guarantees the satisfaction of boundary conditions imposed by terrain while still approximating physical wave behavior. In combination with a particle system that models wave breaking, foam, and spray, this allows us to naturally model waves interacting with beaches and rocks. Our system is able to animate waves at large scales at interactive frame rates on a commodity PC.
ACM Transactions on Graphics (Siggraph 2020)
We propose a method to enhance the visual detail of a water surface simulation. Our method works as a post-processing step which takes a simulation as input and increases its apparent resolution by simulating many detailed Lagrangian water waves on top of it. We extend linear water wave theory to work in non-planar domains which deform over time, and we discretize the theory using Lagrangian wave packets attached to spline curves. The method is numerically stable and trivially parallelizable, and it produces high frequency ripples with dispersive wave-like behaviors customized to the underlying fluid simulation.
@article{skrivan2020wc,
author = {Skřivan, Tomáš and Söderström, Andreas and Johansson, John and Sprenger, Christoph and Museth, Ken and Wojtan, Chris},
title = {Wave Curves: Simulating Lagrangian water waves on dynamically deforming surfaces},
journal = {ACM Transactions on Graphics (TOG)},
number = {4},
volume = {39},
year = {2020},
publisher = {ACM}
}
ACM Transactions on Graphics (Siggraph 2020)
We present a method for animating yarn-level cloth effects using a thin-shell solver. We accomplish this through numerical homogenization: we first use a large number of yarn-level simulations to build a model of the potential energy density of the cloth, and then use this energy density function to compute forces in a thin shell simulator. We model several yarn-based materials, including both woven and knitted fabrics. Our model faithfully reproduces expected effects like the stiffness of woven fabrics, and the highly deformable nature and anisotropy of knitted fabrics. Our approach does not require any real-world experiments nor measurements; because the method is based entirely on simulations, it can generate entirely new material models quickly, without the need for testing apparatuses or human intervention. We provide data-driven models of several woven and knitted fabrics, which can be used for efficient simulation with an off-the-shelf cloth solver.
@article{sperl2020hylc,
author = {Sperl, Georg and Narain, Rahul and Wojtan, Chris},
title = {Homogenized Yarn-Level Cloth},
journal = {ACM Transactions on Graphics (TOG)},
number = {4},
volume = {39},
year = {2020},
publisher = {ACM}
}
ACM Transactions on Graphics (Siggraph 2020)
Previous research on animations of soap bubbles, films, and foams largely focuses on the motion and geometric shape of the bubble surface. These works neglect the evolution of the bubble’s thickness, which is normally responsible for visual phenomena like surface vortices, Newton’s interference patterns, capillary waves, and deformation-dependent rupturing of films in a foam. In this paper, we model these natural phenomena by introducing the film thickness as a reduced degree of freedom in the Navier-Stokes equations and deriving their equations of motion. We discretize the equations on a non-manifold triangle mesh surface and couple it to an existing bubble solver. In doing so, we also introduce an incompressible fluid solver for 2.5D films and a novel advection algorithm for convecting fields across non-manifold surface junctions. Our simulations enhance state-of-the-art bubble solvers with additional effects caused by convection, rippling, draining, and evaporation of the thin film.
@article{10.1145/3386569.3392405,
author = {Ishida, Sadashige and Synak, Peter and Narita, Fumiya and Hachisuka, Toshiya and Wojtan, Chris},
title = {A model for soap film dynamics with evolving thickness},
year = {2020},
issue_date = {August 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {39},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/3386569.3392405},
doi = {10.1145/3386569.3392405},
journal = {ACM Trans. Graph.},
month = aug,
articleno = {31},
numpages = {11},
keywords = {fluid dynamics, physical modeling, soap films}
}
Computer Graphics Forum (Eurographics 2020)
This paper introduces a simple method for simulating highly anisotropic elastoplastic material behaviors like the dissolution of fibrous phenomena (splintering wood, shredding bales of hay) and materials composed of large numbers of irregularly-shaped bodies (piles of twigs, pencils, or cards). We introduce a simple transformation of the anisotropic problem into an equivalent isotropic one, and we solve this new ``fictitious’’ isotropic problem using an existing simulator based on the material point method. Our approach results in minimal changes to existing simulators, and it allows us to re-use popular isotropic plasticity models like the Drucker-Prager yield criterion instead of inventing new anisotropic plasticity models for every phenomenon we wish to simulate.
@article{SW_ampm20,
author = "Schreck, Camille and Wojtan, Chris"
title = "A Practical Method for Animating Anisotropic Elastoplastic Materials",
journal = "Computer Graphics Forum - Eurographics 2020",
number = "2",
volume = "39",
year = "2020",
}
ACM Transactions on Graphics (Siggraph 2019)
This paper investigates the use of fundamental solutions for animating detailed linear water surface waves. We first propose an analytical solution for efficiently animating circular ripples in closed form. We then show how to adapt the method of fundamental solutions (MFS) to create ambient waves interacting with complex obstacles. Subsequently, we present a novel wavelet-based discretization which outperforms the state of the art MFS approach for simulating time-varying water surface waves with moving obstacles. Our results feature high-resolution spatial details, interactions with complex boundaries, and large open ocean domains. Our method compares favorably with previous work as well as known analytical solutions. We also present comparisons between our method and real world examples.
@article{SHW_fsww19,
author = "Schreck, Camille and Hafner, Christian and Wojtan, Chris"
title = "Fundamental Solutions for Water Wave Animation",
journal = "ACM Trans. on Graphics - Siggraph 2019",
number = "4",
volume = "38",
pages = "14",
month = "July",
year = "2019",
note = "https://doi.org/10.1145/3306346.3323002"
}
IEEE Transactions on Visualization and Computer Graphics (2018)
We introduce dynamically warping grids for adaptive liquid simulation. Our primary contributions are a strategy for dynamically deforming regular grids over the course of a simulation and a method for efficiently utilizing these deforming grids for liquid simulation. Prior work has shown that unstructured grids are very effective for adaptive fluid simulations. However, unstructured grids often lead to complicated implementations and a poor cache hit rate due to inconsistent memory access. Regular grids, on the other hand, provide a fast, fixed memory access pattern and straightforward implementation. Our method combines the advantages of both: we leverage the simplicity of regular grids while still achieving practical and controllable spatial adaptivity. We demonstrate that our method enables adaptive simulations that are fast, flexible, and robust to null-space issues. At the same time, our method is simple to implement and takes advantage of existing highly-tuned algorithms.
@article{ibayashi2018simulating,
title={Simulating liquids on dynamically warping grids},
author={Ibayashi, Hikaru and Wojtan, Chris and Thuerey, Nils and Igarashi, Takeo and Ando, Ryoichi},
journal={IEEE transactions on visualization and computer graphics},
volume={26},
number={6},
pages={2288--2302},
year={2018},
publisher={IEEE}
doi={10.1109/TVCG.2018.2883628}
}
Computer Graphics Forum (Eurographics 2018)
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.
@article{https://doi.org/10.1111/cgf.13351,
author = {Sato, T. and Wojtan, C. and Thuerey, N. and Igarashi, T. and Ando, R.},
title = {Extended Narrow Band FLIP for Liquid Simulations},
journal = {Computer Graphics Forum},
volume = {37},
number = {2},
pages = {169-177},
keywords = {CCS Concepts, •Computing methodologies → Physical simulation},
doi = {https://doi.org/10.1111/cgf.13351},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1111/cgf.13351},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.13351},
year = {2018}
}
ACM Transactions on Graphics (Siggraph 2018)
The current state of the art in real-time two-dimensional water wave simulation requires developers to choose between efficient Fourier-based methods, which lack interactions with moving obstacles, and finite-difference or finite element methods, which handle environmental interactions but are significantly more expensive. This paper attempts to bridge this long-standing gap between complexity and performance, by proposing a new wave simulation method that can faithfully simulate wave interactions with moving obstacles in real time while simultaneously preserving minute details and accommodating very large simulation domains.
Previous methods for simulating 2D water waves directly compute the change in height of the water surface, a strategy which imposes limitations based on the CFL condition (fast moving waves require small time steps) and Nyquist’s limit (small wave details require closely-spaced simulation variables). This paper proposes a novel wavelet transformation that discretizes the liquid motion in terms of amplitude-like functions that vary over {\em space, frequency, and direction}, effectively generalizing Fourier-based methods to handle local interactions. Because these new variables change much more slowly over space than the original water height function, our change of variables drastically reduces the limitations of the CFL condition and Nyquist limit, allowing us to simulate highly detailed water waves at very large visual resolutions. Our discretization is amenable to fast summation and easy to parallelize. We also present basic extensions like pre-computed wave paths and two-way solid fluid coupling. Finally, we argue that our discretization provides a convenient set of variables for artistic manipulation, which we illustrate with a novel wave-painting interface.
Computer Graphics Forum (2017)
One of the major challenges in physically based modelling is making simulations efficient. Adaptive models provide an essential solution to these efficiency goals. These models are able to self-adapt in space and time, attempting to provide the best possible compromise between accuracy and speed. This survey reviews the adaptive solutions proposed so far in computer graphics. Models are classified according to the strategy they use for adaptation, from time-stepping and freezing techniques to geometric adaptivity in the form of structured grids, meshes and particles. Applications range from fluids, through deformable bodies, to articulated solids.
@article{https://doi.org/10.1111/cgf.12941,
author = {Manteaux, P.-L. and Wojtan, C. and Narain, R. and Redon, S. and Faure, F. and Cani, M.-P.},
title = {Adaptive Physically Based Models in Computer Graphics},
journal = {Computer Graphics Forum},
volume = {36},
number = {6},
pages = {312-337},
keywords = {adaptivity, physically based animation, I.3.7 Computer GraphicsThree-Dimensional Graphics and Realism-Animation},
doi = {https://doi.org/10.1111/cgf.12941},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1111/cgf.12941},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.12941},
year = {2017}
}
This thesis describes a brittle fracture simulation method for visual effects applications. Building upon a symmetric Galerkin boundary element method, we first compute stress intensity factors following the theory of linear elastic fracture mechanics. We then use these stress intensities to simulate the motion of a propagating crack front at a significantly higher resolution than the overall deformation of the breaking object. Allowing for spatial variations of the material’s toughness during crack propagation produces visually realistic, highly-detailed fracture surfaces.
Furthermore, we introduce approximations for stress intensities and crack opening displacements, resulting in both practical speed-up and theoretically superior runtime complexity compared to previous methods. While we choose a quasi-static approach to fracture mechanics, ignoring dynamic deformations, we also couple our fracture simulation framework to a standard rigid-body dynamics solver, enabling visual effects artists to simulate both large scale motion, as well as fracturing due to collision forces in a combined system.
As fractures inside of an object grow, their geometry must be represented both in the coarse boundary element mesh, as well as at the desired fine output resolution. Using a boundary element method, we avoid complicated volumetric meshing operations. Instead we describe a simple set of surface meshing operations that allow us to progressively add cracks to the mesh of an object and still re-use all previously computed entries of the linear boundary element system matrix. On the high resolution level, we opt for an implicit surface representation. We then describe how to capture fracture surfaces during crack propagation, as well as separate the individual fragments resulting from the fracture process, based on this implicit representation.
We show results obtained with our method, either solving the full boundary element system in every time step, or alternatively using our fast approximations. These results demonstrate that both of these methods perform well in basic test cases and produce realistic fracture surfaces. Furthermore we show that our fast approximations substantially out-perform the standard approach in more demanding scenarios. Finally, these two methods naturally combine, using the full solution while the problem size is manageably small and switching to the fast approximations later on. The resulting hybrid method gives the user a direct way to choose between speed and accuracy of the simulation.
@phdthesis{HahnThesis2017,
author = {David Hahn},
title = {Brittle Fracture Simulation with Boundary Elements for Computer Graphics},
school = {IST Austria},
year = {2017},
month = {8}
}
ACM Transactions on Graphics (Siggraph 2017)
This paper presents a method for simulating water surface waves as a displacement field on a 2D domain. Our method relies on Lagrangian particles that carry packets of water wave energy; each packet carries information about an entire group of wave trains, as opposed to only a single wave crest. Our approach is unconditionally stable and can simulate high resolution geometric details. This approach also presents a straightforward interface for artistic control, because it is essentially a particle system with intuitive parameters like wavelength and amplitude. Our implementation parallelizes well and runs in real time for moderately challenging scenarios.
@article{Jeschke2017,
author = {Stefan Jeschke and Chris Wojtan},
title = {Water Wave Packets},
journal = {ACM Transactions on Graphics (SIGGRAPH 2017)},
year = {2017},
volume = {36},
number = {4}
}
International Conference on Motion in Games (MIG 2016)
We propose an interactive sculpting system for seamlessly editing pre-computed animations of liquid, without the need for any resimulation. The input is a sequence of meshes without correspondences representing the liquid surface over time. Our method enables the efficient selection of consistent space-time parts of this animation, such as moving waves or droplets, which we call space-time features. Once selected, a feature can be copied, edited, or duplicated and then pasted back anywhere in space and time in the same or in another liquid animation sequence. Our method circumvents tedious user interactions by automatically computing the spatial and temporal ranges of the selected feature. We also provide space-time shape editing tools for non-uniform scaling, rotation, trajectory changes, and temporal editing to locally speed up or slow down motion. Using our tools, the user can edit and progressively refine any input simulation result, possibly using a library of pre-computed space-time features extracted from other animations. In contrast to the trial-and-error loop usually required to edit animation results through the tuning of indirect simulation parameters, our method gives the user full control over the edited space-time behaviors.
@inproceedings{10.1145/2994258.2994261,
author = {Manteaux, Pierre-Luc and Vimont, Ulysse and Wojtan, Chris and Rohmer, Damien and Cani, Marie- Paule},
title = {Space-time sculpting of liquid animation},
year = {2016},
isbn = {9781450345927},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2994258.2994261},
doi = {10.1145/2994258.2994261},
booktitle = {Proceedings of the 9th International Conference on Motion in Games},
pages = {61–71},
numpages = {11},
keywords = {space-time editing, sculpture, fluid animation},
location = {Burlingame, California},
series = {MIG '16}
}
Computer graphics is an extremely exciting field for two reasons. On the one hand, there is a healthy injection of pragmatism coming from the visual effects industry that want robust algorithms that work so they can produce results at an increasingly frantic pace. On the other hand, they must always try to push the envelope and achieve the impossible to wow their audiences in the next blockbuster, which means that the industry has not succumb to conservatism, and there is plenty of room to try out new and crazy ideas if there is a chance that it will pan into something useful.
Water simulation has been in visual effects for decades, however it still remains extremely challenging because of its high computational cost and difficult art-directability. The work in this thesis tries to address some of these difficulties. Specifically, we make the following three novel contributions to the state-of-the-art in water simulation for visual effects.
@phdthesis{TCaAWSW2016,
author = {Morten Bojsen-Hansen},
title = {Tracking, Correcting and Absorbing Water Surface Waves},
school = {IST Austria},
year = {2016},
month = {9}
}
ACM Transactions on Graphics (Siggraph 2016)
We propose a novel surface-only technique for simulating incompressible, inviscid and uniform-density liquids with surface tension in three dimensions. The liquid surface is captured by a triangle mesh on which a Lagrangian velocity field is stored. Because advection of the velocity field may violate the incompressibility condition, we devise an orthogonal projection technique to remove the divergence while requiring the evaluation of only two boundary integrals. The forces of surface tension, gravity, and solid contact are all treated by a boundary element solve, allowing us to perform detailed simulations of a wide range of liquid phenomena, including waterbells, droplet and jet collisions, fluid chains, and crown splashes.
@article{10.1145/2897824.2925899,
author = {Da, Fang and Hahn, David and Batty, Christopher and Wojtan, Chris and Grinspun, Eitan},
title = {Surface-only liquids},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {35},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/2897824.2925899},
doi = {10.1145/2897824.2925899},
journal = {ACM Trans. Graph.},
month = jul,
articleno = {78},
numpages = {12},
keywords = {surface tension, liquids, helmholtz decomposition, boundary element method}
}
ACM Transactions on Graphics (Siggraph 2016)
When aiming to seamlessly integrate a fluid simulation into a larger scenario (like an open ocean), careful attention must be paid to boundary conditions. In particular, one must implement special “non-reflecting” boundary conditions, which dissipate out-going waves as they exit the simulation. Unfortunately, the state of the art in non-reflecting boundary conditions (perfectly-matched layers, or PMLs) only permits trivially simple inflow/outflow conditions, so there is no reliable way to integrate a fluid simulation into a more complicated environment like a stormy ocean or a turbulent river.
This paper introduces the first method for combining non-reflecting boundary conditions based on PMLs with inflow/outflow boundary conditions that vary arbitrarily throughout space and time. Our algorithm is a generalization of state-of-the-art mean-flow boundary conditions in the computational fluid dynamics literature, and it allows for seamless integration of a fluid simulation into much more complicated environments. Our method also opens the door for previously-unseen post-process effects like retroactively changing the location of solid obstacles, and locally increasing the visual detail of a pre-existing simulation.
@article{GNRBfFRS2016,
author = {Morten Bojsen-Hansen and Chris Wojtan},
title = {Generalized Non-Reflecting Boundaries for Fluid Re-Simulation},
journal = {ACM Transactions on Graphics (SIGGRAPH 2016)},
year = {2016},
volume = {35},
number = {4},
}
ACM Transactions on Graphics (Siggraph 2016)
We present a boundary element based method for fast simulation of brittle fracture. By introducing simplifying assumptions that allow us to quickly estimate stress intensities and opening displacements during crack propagation, we build a fracture algorithm where the cost of each time step scales linearly with the length of the crack-front.
The transition from a full boundary element method to our faster variant is possible at the beginning of any time step. This allows us to build a hybrid method, which uses the expensive but more accurate BEM while the number of degrees of freedom is low, and uses the fast method once that number exceeds a given threshold as the crack geometry becomes more complicated.
Furthermore, we integrate this fracture simulation with a standard rigid-body solver. Our rigid-body coupling solves a Neumann boundary value problem by carefully separating translational, rotational and deformational components of the collision forces and then applying a Tikhonov regularizer to the resulting linear system. We show that our method produces physically reasonable results in standard test cases and is capable of dealing with complex scenes faster than previous finite- or boundary element approaches.
@article{10.1145/2897824.2925902,
author = {Hahn, David and Wojtan, Chris},
title = {Fast approximations for boundary element based brittle fracture simulation},
year = {2016},
issue_date = {July 2016},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {35},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/2897824.2925902},
doi = {10.1145/2897824.2925902},
journal = {ACM Trans. Graph.},
month = jul,
articleno = {104},
numpages = {11},
keywords = {boundary elements, brittle fracture, crack propagation}
}
Computer Graphics Forum (Eurographics 2016)
The Fluid Implicit Particle method (FLIP) for liquid simulations uses particles to reduce numerical dissipation and provide important visual cues for events like complex splashes and small-scale features near the liquid surface. Unfortunately, FLIP simulations can be computationally expensive, because they require a dense sampling of particles to fill the entire liquid volume. Furthermore, the vast majority of these FLIP particles contribute nothing to the fluid’s visual appearance, especially for larger volumes of liquid. We present a method that only uses FLIP particles within a narrow band of the liquid surface, while efficiently representing the remaining inner volume on a regular grid. We show that a naïve realization of this idea introduces unstable and uncontrollable energy fluctuations, and we propose a novel coupling scheme between FLIP particles and regular grid which overcomes this problem. Our method drastically reduces the particle count and simulation times while yielding results that are nearly indistinguishable from regular FLIP simulations. Our approach is easy to integrate into any existing FLIP implementation.
@article{https://doi.org/10.1111/cgf.12825,
author = {Ferstl, Florian and Ando, Ryoichi and Wojtan, Chris and Westermann, Rüdiger and Thuerey, Nils},
title = {Narrow Band FLIP for Liquid Simulations},
journal = {Computer Graphics Forum},
volume = {35},
number = {2},
pages = {225-232},
keywords = {Categories and Subject Descriptors (according to ACM CCS), I.3.7 Computer Graphics: Three-Dimensional Graphics and Realism—Animation},
doi = {https://doi.org/10.1111/cgf.12825},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1111/cgf.12825},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.12825},
year = {2016}
}
Computer Graphics Forum (Eurographics 2016)
Combining high-resolution level set surface tracking with lower resolution physics is an inexpensive method for achieving highly detailed liquid animations. Unfortunately, the inherent resolution mismatch introduces several types of disturbing visual artifacts. We identify the primary sources of these artifacts and present simple, efficient, and practical solutions to address them. First, we propose an unconditionally stable filtering method that selectively removes sub-grid surface artifacts not seen by the fluid physics, while preserving fine detail in dynamic splashing regions. It provides comparable results to recent error-correction techniques at lower cost, without substepping, and with better scaling behavior. Second, we show how a modified narrow-band scheme can ensure accurate free surface boundary conditions in the presence of large resolution mismatches. Our scheme preserves the efficiency of the narrow-band methodology, while eliminating objectionable stairstep artifacts observed in prior work. Third, we demonstrate that the use of linear interpolation of velocity during advection of the high-resolution level set surface is responsible for visible grid-aligned kinks; we therefore advocate higher-order velocity interpolation, and show that it dramatically reduces this artifact. While these three contributions are orthogonal, our results demonstrate that taken together they efficiently address the dominant sources of visual artifacts arising with high-resolution embedded liquid surfaces; the proposed approach offers improved visual quality, a straightforward implementation, and substantially greater scalability than competing methods.
@article{https://doi.org/10.1111/cgf.12826,
author = {Goldade, Ryan and Batty, Christopher and Wojtan, Chris},
title = {A Practical Method for High-Resolution Embedded Liquid Surfaces},
journal = {Computer Graphics Forum},
volume = {35},
number = {2},
pages = {233-242},
keywords = {Categories and Subject Descriptors (according to ACM CCS), I.3.7 Computer Graphics: Three-Dimensional Graphics and Realism—Animation},
doi = {https://doi.org/10.1111/cgf.12826},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1111/cgf.12826},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.12826},
year = {2016}
}
Computer Graphics Forum (Eurographics 2016)
This paper generalizes the well-known Diffusion Curves Images (DCI), which are composed of a set of Bezier curves with colors specified on either side. These colors are diffused as Laplace functions over the image domain, which results in smooth color gradients interrupted by the Bezier curves. Our new formulation allows for more color control away from the boundary, providing a similar expressive power as recent Bilaplace image models without introducing associated issues and computational costs. The new model is based on a special Laplace function blending and a new edge blur formulation. We demonstrate that given some user-defined boundary curves over an input raster image, fitting colors and edge blur from the image to the new model and subsequent editing and animation is equally convenient as with DCIs. Numerous examples and comparisons to DCIs are presented.
@article{GDCI2016,
author = {Stefan Jeschke},
title = {Generalized Diffusion Curves: An Improved Vector Representation for Smooth-Shaded Images},
journal = {Computer Graphics Forum},
year = {2016},
volume = {35},
number = {2},
pages = {1--9}
}
ACM Transactions on Graphics (Siggraph 2015)
This paper presents a liquid simulation technique that enforces the incompressibility condition using a stream function solve instead of a pressure projection. Previous methods have used stream function techniques for the simulation of detailed single-phase flows, but a formulation for liquid simulation has proved elusive in part due to the free surface boundary conditions. In this paper, we introduce a stream function approach to liquid simulations with novel boundary conditions for free surfaces, solid obstacles, and solid-fluid coupling.
Although our approach increases the dimension of the linear system necessary to enforce incompressibility, it provides interesting and surprising benefits. First, the resulting flow is guaranteed to be divergence-free regardless of the accuracy of the solve. Second, our free-surface boundary conditions guarantee divergence-free motion even in the un-simulated air phase, which enables two-phase flow simulation by only computing a single phase. We implemented this method using a variant of FLIP simulation which only samples particles within a narrow band of the liquid surface, and we illustrate the effectiveness of our method for detailed two-phase flow simulations with complex boundaries, detailed bubble interactions, and two-way solid-fluid coupling.
@article{10.1145/2766935,
author = {Ando, Ryoichi and Thuerey, Nils and Wojtan, Chris},
title = {A stream function solver for liquid simulations},
year = {2015},
issue_date = {August 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {34},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/2766935},
doi = {10.1145/2766935},
journal = {ACM Trans. Graph.},
month = jul,
articleno = {53},
numpages = {9},
keywords = {vector potential, two-phase flow, stream function, fluid}
}
ACM Transactions on Graphics (Siggraph 2015)
We present a method to learn and propagate shape placements in 2D polygonal scenes from a few examples provided by a user. The placement of a shape is modeled as an oriented bounding box. Simple geometric relationships between this bounding box and nearby scene polygons define a feature set for the placement. The feature sets of all example placements are then used to learn a probabilistic model over all possible placements and scenes. With this model, we can generate a new set of placements with similar geometric relationships in any given scene. We introduce extensions that enable propagation and generation of shapes in 3D scenes, as well as the application of a learned modeling session to large scenes without additional user interaction. These concepts allow us to generate complex scenes with thousands of objects with relatively little user interaction.
@article{guerrero-2015-lsp,
title = "Learning Shape Placements by Example",
author = "Paul Guerrero and Stefan Jeschke and Michael Wimmer and Peter Wonka",
year = "2015",
pages = "1--13",
month = aug,
event = "ACM SIGGRAPH 2015",
journal = "ACM Transactions on Graphics",
location = "Los Angeles, CA",
keywords = "complex model generation, modeling by example",
}
ACM Transactions on Graphics (Siggraph 2015)
We present a method for simulating brittle fracture under the assumptions of quasi-static linear elastic fracture mechanics (LEFM). Using the boundary element method (BEM) and Lagrangian crack-fronts, we produce highly detailed fracture surfaces. The computational cost of the BEM is alleviated by using a low-resolution mesh and interpolating the resulting stress intensity factors when propagating the high-resolution crack-front.
Our system produces physics-based fracture surfaces with high spatial and temporal resolution, taking spatial variation of material toughness and/or strength into account. It also allows for crack initiation to be handled separately from crack propagation, which is not only more reasonable from a physics perspective, but can also be used to control the simulation.
Separating the resolution of the crack-front from the resolution of the computational mesh increases the efficiency and therefore the amount of visual detail on the resulting fracture surfaces. The BEM also allows us to re-use previously computed blocks of the system matrix.
@article{10.1145/2766896,
author = {Hahn, David and Wojtan, Chris},
title = {High-resolution brittle fracture simulation with boundary elements},
year = {2015},
issue_date = {August 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {34},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/2766896},
doi = {10.1145/2766896},
journal = {ACM Trans. Graph.},
month = jul,
articleno = {151},
numpages = {12},
keywords = {crack propagation, brittle fracture, boundary elements}
}
ACM Transactions on Graphics (Siggraph 2015)
Simulating the delightful dynamics of soap films, bubbles, and foams has traditionally required the use of a fully three-dimensional many-phase Navier-Stokes solver, even though their visual appearance is completely dominated by the thin liquid surface. We depart from earlier work on soap bubbles and foams by noting that their dynamics are naturally described by a Lagrangian vortex sheet model in which circulation is the primary variable. This leads us to derive a novel circulation-preserving surface-only discretization of foam dynamics driven by surface tension on a non-manifold triangle mesh. We represent the surface using a mesh-based multimaterial surface tracker which supports complex bubble topology changes, and evolve the surface according to the ambient air flow induced by a scalar circulation field stored on the mesh. Surface tension forces give rise to a simple update rule for circulation, even at non-manifold Plateau borders, based on a discrete measure of signed scalar mean curvature. We further incorporate vertex constraints to enable the interaction of soap films with wires. The result is a method that is at once simple, robust, and efficient, yet able to capture an array of soap films behaviors including foam rearrangement, catenoid collapse, blowing bubbles, and double bubbles being pulled apart.
@article{10.1145/2767003,
author = {Da, Fang and Batty, Christopher and Wojtan, Chris and Grinspun, Eitan},
title = {Double bubbles sans toil and trouble: discrete circulation-preserving vortex sheets for soap films and foams},
year = {2015},
issue_date = {August 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {34},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/2767003},
doi = {10.1145/2767003},
journal = {ACM Trans. Graph.},
month = jul,
articleno = {149},
numpages = {9},
keywords = {circulation, fluids, non-manifold mesh, vortex sheet}
}
ACM Transactions on Graphics (Siggraph 2015)
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 multivalued 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.
@article{10.1145/2714572,
author = {Jeschke, Stefan and Wojtan, Chris},
title = {Water Wave Animation via Wavefront Parameter Interpolation},
year = {2015},
issue_date = {April 2015},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {34},
number = {3},
issn = {0730-0301},
url = {https://doi.org/10.1145/2714572},
doi = {10.1145/2714572},
journal = {ACM Trans. Graph.},
month = may,
articleno = {27},
numpages = {14},
keywords = {Ocean simulation, computational fluid dynamics, liquid animation, wavefront tracking}
}
Computer Graphics Forum (Eurographics 2015)
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 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.
@article{https://doi.org/10.1111/cgf.12576,
author = {Ando, Ryoichi and Thürey, Nils and Wojtan, Chris},
title = {A Dimension-reduced Pressure Solver for Liquid Simulations},
journal = {Computer Graphics Forum},
volume = {34},
number = {2},
pages = {473-480},
keywords = {Categories and Subject Descriptors (according to ACM CCS), I.3.7 Computer Graphics: Three-Dimensional Graphics and Realism—Animation},
doi = {https://doi.org/10.1111/cgf.12576},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1111/cgf.12576},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.12576},
abstract = {Abstract 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 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.},
year = {2015}
}
Computer Graphics Forum (Eurographics 2016)
In this paper, we present a method for non-rigid, partial shape matching in vector graphics. Given a user-specified query region in a 2D shape, similar regions are found, even if they are non-linearly distorted. Furthermore, a non-linear mapping is established between the query regions and these matches, which allows the automatic transfer of editing operations such as texturing. This is achieved by a two-step approach. First, point-wise correspondences between the query region and the whole shape are established. The transformation parameters of these correspondences are registered in an appropriate transformation space. For transformations between similar regions, these parameters form surfaces in transformation space, which are extracted in the second step of our method. The extracted regions may be related to the query region by a non-rigid transform, enabling non-rigid shape matching.
@article{Guerrero-2014-TPS,
author = {Paul Guerrero and Thomas Auzinger and Michael Wimmer and Stefan Jeschke},
title = {Partial Shape Matching using Transformation Parameter Similarity},
journal = {Computer Graphics Forum},
year = {2014},
volume = {33},
number = {8},
pages = {1--14}
issn = {1467-8659}
}
ACM Transactions on Graphics (Siggraph 2014)
We present a method for smoothly blending between existing liquid animations. We introduce a semi-automatic method for matching two existing liquid animations, which we use to create new fluid motion that plausibly interpolates the input. Our contributions include a new space-time non-rigid iterative closest point algorithm that incorporates user guidance, a subsampling technique for efficient registration of meshes with millions of vertices, and a fast surface extraction algorithm that produces 3D triangle meshes from a 4D space-time surface. Our technique can be used to instantly create hundreds of new simulations, or to interactively explore complex parameter spaces. Our method is guaranteed to produce output that does not deviate from the input animations, and it generalizes to multiple dimensions. Because our method runs at interactive rates after the initial precomputation step, it has potential applications in games and training simulations.
@article{10.1145/2601097.2601126,
author = {Raveendran, Karthik and Wojtan, Chris and Thuerey, Nils and Turk, Greg},
title = {Blending liquids},
year = {2014},
issue_date = {July 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {33},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/2601097.2601126},
doi = {10.1145/2601097.2601126},
abstract = {We present a method for smoothly blending between existing liquid animations. We introduce a semi-automatic method for matching two existing liquid animations, which we use to create new fluid motion that plausibly interpolates the input. Our contributions include a new space-time non-rigid iterative closest point algorithm that incorporates user guidance, a subsampling technique for efficient registration of meshes with millions of vertices, and a fast surface extraction algorithm that produces 3D triangle meshes from a 4D space-time surface. Our technique can be used to instantly create hundreds of new simulations, or to interactively explore complex parameter spaces. Our method is guaranteed to produce output that does not deviate from the input animations, and it generalizes to multiple dimensions. Because our method runs at interactive rates after the initial precomputation step, it has potential applications in games and training simulations.},
journal = {ACM Trans. Graph.},
month = jul,
articleno = {137},
numpages = {10},
keywords = {shape blending, non-rigid registration, fluid simulation}
}
ACM Transactions on Graphics (Siggraph 2014)
We propose a method for propagating edit operations in 2D vector graphics, based on geometric relationship functions. These functions quantify the geometric relationship of a point to a polygon, such as the distance to the boundary or the direction to the closest corner vertex. The level sets of the relationship functions describe points with the same relationship to a polygon. For a given query point we ?rst determine a set of relationships to local features, construct all level sets for these relationships and accumulate them. The maxima of the resulting distribution are points with similar geometric relationships. We show extensions to handle mirror symmetries, and discuss the use of relationship functions as local coordinate systems. Our method can be applied for example to interactive ?oor-plan editing, and is especially useful for large layouts, where individual edits would be cumbersome. We demonstrate populating 2D layouts with tens to hundreds of objects by propagating relatively few edit operations.
@article{10.1145/2591010,
author = {Guerrero, Paul and Jeschke, Stefan and Wimmer, Michael and Wonka, Peter},
title = {Edit propagation using geometric relationship functions},
year = {2014},
issue_date = {March 2014},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {33},
number = {2},
issn = {0730-0301},
url = {https://doi.org/10.1145/2591010},
doi = {10.1145/2591010},
abstract = {We propose a method for propagating edit operations in 2D vector graphics, based on geometric relationship functions. These functions quantify the geometric relationship of a point to a polygon, such as the distance to the boundary or the direction to the closest corner vertex. The level sets of the relationship functions describe points with the same relationship to a polygon. For a given query point, we first determine a set of relationships to local features, construct all level sets for these relationships, and accumulate them. The maxima of the resulting distribution are points with similar geometric relationships. We show extensions to handle mirror symmetries, and discuss the use of relationship functions as local coordinate systems. Our method can be applied, for example, to interactive floorplan editing, and it is especially useful for large layouts, where individual edits would be cumbersome. We demonstrate populating 2D layouts with tens to hundreds of objects by propagating relatively few edit operations.},
journal = {ACM Trans. Graph.},
month = apr,
articleno = {15},
numpages = {15},
keywords = {Edit propagation, geometric relationships}
}
We present a generalization of the bilateral filter that can be applied to feature-preserving smoothing of signals on images, meshes, and other domains within a single unified framework. Our discretization is competitive with state-of-the-art smoothing techniques in terms of both accuracy and speed, is easy to implement, and has parameters that are straightforward to understand. Unlike previous bilateral filters developed for meshes and other irregular domains, our construction reduces exactly to the image bilateral on rectangular domains and comes with a rigorous foundation in both the smooth and discrete settings. These guarantees allow us to construct unconditionally convergent mean-shift schemes that handle a variety of extremely noisy signals. We also apply our framework to geometric edge-preserving effects like feature enhancement and show how it is related to local histogram techniques.
@article{DBLP:journals/corr/SolomonCBW14,
author = {Justin Solomon and
Keenan Crane and
Adrian Butscher and
Chris Wojtan},
title = {A General Framework for Bilateral and Mean Shift Filtering},
journal = {CoRR},
volume = {abs/1405.4734},
year = {2014},
url = {http://arxiv.org/abs/1405.4734},
eprinttype = {arXiv},
eprint = {1405.4734},
timestamp = {Thu, 16 Apr 2020 07:55:10 +0200},
biburl = {https://dblp.org/rec/journals/corr/SolomonCBW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
ACM Transactions on Graphics (Siggraph 2013)
Our work concerns the combination of an Eulerian liquid simulation with a high-resolution surface tracker (e.g. the level set method or a Lagrangian triangle mesh). The naive application of a high-resolution surface tracker to a low-resolution velocity field can produce many visually disturbing physical and topological artifacts that limit their use in practice. We address these problems by defining an error function which compares the current state of the surface tracker to the set of physically valid surface states. By reducing this error with a gradient descent technique, we introduce a novel physics-based surface fairing method. Similarly, by treating this error function as a potential energy, we derive a new surface correction force that mimics the vortex sheet equations. We demonstrate our results with both level set and mesh-based surface trackers.
@article{LSTwEC2013,
author = {Morten Bojsen-Hansen and Chris Wojtan},
title = {Liquid Surface Tracking with Error Compensation},
journal = {ACM Transactions on Graphics (SIGGRAPH 2013)},
year = {2013},
volume = {32},
number = {4},
pages = {79:1--79:10}
}
ACM Transactions on Graphics (Siggraph 2013)
This paper presents a method for computing topology changes for triangle meshes in an interactive geometric modeling environment. Most triangle meshes in practice do not exhibit desirable geometric properties, so we develop a solution that is independent of standard assumptions and robust to geometric errors. Specifically, we provide the first method for topology change applicable to arbitrary non-solid, non-manifold, non-closed, self-intersecting surfaces. We prove that this new method for topology change produces the expected conventional results when applied to solid (closed, manifold, non-self-intersecting) surfaces—that is, we prove a backwards-compatibility property relative to prior work. Beyond solid surfaces, we present empirical evidence that our method remains tolerant to a variety of surface aberrations through the incorporation of a novel error correction scheme. Finally, we demonstrate how topology change applied to non-solid objects enables wholly new and useful behaviors.
@article{10.1145/2461912.2462027,
author = {Bernstein, Gilbert Louis and Wojtan, Chris},
title = {Putting holes in holey geometry: topology change for arbitrary surfaces},
year = {2013},
issue_date = {July 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {32},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/2461912.2462027},
doi = {10.1145/2461912.2462027},
abstract = {This paper presents a method for computing topology changes for triangle meshes in an interactive geometric modeling environment. Most triangle meshes in practice do not exhibit desirable geometric properties, so we develop a solution that is independent of standard assumptions and robust to geometric errors. Specifically, we provide the first method for topology change applicable to arbitrary non-solid, non-manifold, non-closed, self-intersecting surfaces. We prove that this new method for topology change produces the expected conventional results when applied to solid (closed, manifold, non-self-intersecting) surfaces---that is, we prove a backwards-compatibility property relative to prior work. Beyond solid surfaces, we present empirical evidence that our method remains tolerant to a variety of surface aberrations through the incorporation of a novel error correction scheme. Finally, we demonstrate how topology change applied to non-solid objects enables wholly new and useful behaviors.},
journal = {ACM Trans. Graph.},
month = jul,
articleno = {34},
numpages = {12},
keywords = {topology, sculpting, non-manifold geometry, intersections, deformations, 3d modeling}
}
ACM Transactions on Graphics (Siggraph 2013)
We introduce a new method for efficiently simulating liquid with extreme amounts of spatial adaptivity. Our method combines several key components to drastically speed up the simulation of large-scale fluid phenomena: We leverage an alternative Eulerian tetrahedral mesh discretization to significantly reduce the complexity of the pressure solve while increasing the robustness with respect to element quality and removing the possibility of locking. Next, we enable subtle free-surface phenomena by deriving novel second-order boundary conditions consistent with our discretization. We couple this discretization with a spatially adaptive Fluid-Implicit Particle (FLIP) method, enabling efficient, robust, minimally-dissipative simulations that can undergo sharp changes in spatial resolution while minimizing artifacts. Along the way, we provide a new method for generating a smooth and detailed surface from a set of particles with variable sizes. Finally, we explore several new sizing functions for determining spatially adaptive simulation resolutions, and we show how to couple them to our simulator. We combine each of these elements to produce a simulation algorithm that is capable of creating animations at high maximum resolutions while avoiding common pitfalls like inaccurate boundary conditions and inefficient computation.
@article{10.1145/2461912.2461982,
author = {Ando, Ryoichi and Th\"{u}rey, Nils and Wojtan, Chris},
title = {Highly adaptive liquid simulations on tetrahedral meshes},
year = {2013},
issue_date = {July 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {32},
number = {4},
issn = {0730-0301},
url = {https://doi.org/10.1145/2461912.2461982},
doi = {10.1145/2461912.2461982},
abstract = {We introduce a new method for efficiently simulating liquid with extreme amounts of spatial adaptivity. Our method combines several key components to drastically speed up the simulation of large-scale fluid phenomena: We leverage an alternative Eulerian tetrahedral mesh discretization to significantly reduce the complexity of the pressure solve while increasing the robustness with respect to element quality and removing the possibility of locking. Next, we enable subtle free-surface phenomena by deriving novel second-order boundary conditions consistent with our discretization. We couple this discretization with a spatially adaptive Fluid-Implicit Particle (FLIP) method, enabling efficient, robust, minimally-dissipative simulations that can undergo sharp changes in spatial resolution while minimizing artifacts. Along the way, we provide a new method for generating a smooth and detailed surface from a set of particles with variable sizes. Finally, we explore several new sizing functions for determining spatially adaptive simulation resolutions, and we show how to couple them to our simulator. We combine each of these elements to produce a simulation algorithm that is capable of creating animations at high maximum resolutions while avoiding common pitfalls like inaccurate boundary conditions and inefficient computation.},
journal = {ACM Trans. Graph.},
month = jul,
articleno = {103},
numpages = {10},
keywords = {adaptivity, fluid simulation, tetrahedral discretization}
}
ACM Transactions on Graphics (Siggraph 2012)
We present a method for recovering a temporally coherent, deforming triangle mesh with arbitrarily changing topology from an incoherent sequence of static closed surfaces. We solve this problem using the surface geometry alone, without any prior information like surface templates or velocity fields. Our system combines a proven strategy for triangle mesh improvement, a robust multi-resolution non-rigid registration routine, and a reliable technique for changing surface mesh topology. We also introduce a novel topological constraint enforcement algorithm to ensure that the output and input always have similar topology. We apply our technique to a series of diverse input data from video reconstructions, physics simulations, and artistic morphs. The structured output of our algorithm allows us to efficiently track information like colors and displacement maps, recover velocity information, and solve PDEs on the mesh as a post process.
@article{TSwET2012,
author = {Morten Bojsen-Hansen and Hao Li and Chris Wojtan},
title = {Tracking Surfaces with Evolving Topology},
journal = {ACM Transactions on Graphics (SIGGRAPH 2012)},
year = {2012},
volume = {31},
number = {4},
pages = {53:1--53:10}
}
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 2012)
We present an approach for artist-directed animation of liquids using multiple levels of control over the simulation, ranging from the overall tracking of desired shapes to highly detailed secondary effects such as dripping streams, separating sheets of fluid, surface waves and ripples. The first portion of our technique is a volume preserving morph that allows the animator to produce a plausible fluid-like motion from a sparse set of control meshes. By rasterizing the resulting control meshes onto the simulation grid, the mesh velocities act as boundary conditions during the projection step of the fluid simulation. We can then blend this motion together with uncontrolled fluid velocities to achieve a more relaxed control over the fluid that captures natural inertial effects. Our method can produce highly detailed liquid surfaces with control over sub-grid details by using a mesh-based surface tracker on top of a coarse grid-based fluid simulation. We can create ripples and waves on the fluid surface attracting the surface mesh to the control mesh with spring-like forces and also by running a wave simulation over the surface mesh. Our video results demonstrate how our control scheme can be used to create animated characters and shapes that are made of water.
@inproceedings{10.5555/2422356.2422393,
author = {Raveendran, Karthik and Thuerey, Nils and Wojtan, Chris and Turk, Greg},
title = {Controlling liquids using meshes},
year = {2012},
isbn = {9783905674378},
publisher = {Eurographics Association},
address = {Goslar, DEU},
abstract = {We present an approach for artist-directed animation of liquids using multiple levels of control over the simulation, ranging from the overall tracking of desired shapes to highly detailed secondary effects such as dripping streams, separating sheets of fluid, surface waves and ripples. The first portion of our technique is a volume preserving morph that allows the animator to produce a plausible fluid-like motion from a sparse set of control meshes. By rasterizing the resulting control meshes onto the simulation grid, the mesh velocities act as boundary conditions during the projection step of the fluid simulation. We can then blend this motion together with uncontrolled fluid velocities to achieve a more relaxed control over the fluid that captures natural inertial effects. Our method can produce highly detailed liquid surfaces with control over sub-grid details by using a mesh-based surface tracker on top of a coarse grid-based fluid simulation. We can create ripples and waves on the fluid surface attracting the surface mesh to the control mesh with spring-like forces and also by running a wave simulation over the surface mesh. Our video results demonstrate how our control scheme can be used to create animated characters and shapes that are made of water.},
booktitle = {Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation},
pages = {255–264},
numpages = {10},
location = {Lausanne, Switzerland},
series = {SCA '12}
}
Computer Graphics Forum (Eurographics 2012)
We introduce the idea of using an explicit triangle mesh to track the air/fluid interface in a smoothed particle hydrodynamics (SPH) simulator. Once an initial surface mesh is created, this mesh is carried forward in time using nearby particle velocities to advect the mesh vertices. The mesh connectivity remains mostly unchanged across time-steps; it is only modified locally for topology change events or for the improvement of triangle quality. In order to ensure that the surface mesh does not diverge from the underlying particle simulation, we periodically project the mesh surface onto an implicit surface defined by the physics simulation. The mesh surface gives us several advantages over previous SPH surface tracking techniques. We demonstrate a new method for surface tension calculations that clearly outperforms the state of the art in SPH surface tension for computer graphics. We also demonstrate a method for tracking detailed surface information (like colors) that is less susceptible to numerical diffusion than competing techniques. Finally, our temporally-coherent surface mesh allows us to simulate high-resolution surface wave dynamics without being limited by the particle resolution of the SPH simulation.
@article{https://doi.org/10.1111/j.1467-8659.2012.03062.x,
author = {Yu, Jihun and Wojtan, Chris and Turk, Greg and Yap, Chee},
title = {Explicit Mesh Surfaces for Particle Based Fluids},
journal = {Computer Graphics Forum},
volume = {31},
number = {2pt4},
pages = {815-824},
keywords = {I.3.5 Computer Graphics: Computational Geometry and Object Modeling—Physically based modeling, I.3.7 Computer Graphics: Three-Dimensional Graphics and Realism—Animation},
doi = {https://doi.org/10.1111/j.1467-8659.2012.03062.x},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-8659.2012.03062.x},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-8659.2012.03062.x},
year = {2012}
}
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 2011)
We present a new algorithm for enforcing incompressibility for Smoothed Particle Hydrodynamics (SPH) by preserving uniform density across the domain. We propose a hybrid method that uses a Poisson solve on a coarse grid to enforce a divergence free velocity field, followed by a local density correction of the particles. This avoids typical grid artifacts and maintains the Lagrangian nature of SPH by directly transferring pressures onto particles. Our method can be easily integrated with existing SPH techniques such as the incompressible PCISPH method as well as weakly compressible SPH by adding an additional force term. We show that this hybrid method accelerates convergence towards uniform density and permits a significantly larger time step compared to earlier approaches while producing similar results. We demonstrate our approach in a variety of scenarios with significant pressure gradients such as splashing liquids.
@inproceedings{10.1145/2019406.2019411,
author = {Raveendran, Karthik and Wojtan, Chris and Turk, Greg},
title = {Hybrid smoothed particle hydrodynamics},
year = {2011},
isbn = {9781450309233},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2019406.2019411},
doi = {10.1145/2019406.2019411},
booktitle = {Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation},
pages = {33–42},
numpages = {10},
location = {Vancouver, British Columbia, Canada},
series = {SCA '11}
}
Animating detailed liquid surfaces has continually been a challenge for computer graphics researchers and visual effects artists. Over the past few years, a strong trend has emerged among researchers in this field towards mesh-based surface tracking in order to synthesize extremely detailed liquid surfaces as efficiently as possible. This course will provide attendees with a solid understanding of the steps necessary to create a fluid simulator with a meshbased liquid surface.
The course will begin with an overview of several existing liquid surface tracking techniques, discussing the pros and cons of each method. We will then provide instructions and a simple demonstration on how to embed a triangle mesh into a finite-difference-based fluid simulator. Once this groundwork has been laid, the next section of the course will stress the importance of surface quality and review techniques for maintaining a high quality triangle mesh. Afterward, we will describe several methods for allowing the liquid surface to merge together or break apart. The final section of this course showcase the benefits and further applications of a mesh-based liquid surface, highlighting state-of-the-art methods for tracking colors and textures, maintaining liquid volume, preserving small surface features, and simulating realistic surface tension waves.
Level of Difficulty: Advanced.
This course is intended for both researchers and developers in industry who want to implement and have a solid understanding of the state of the art in fluid simulation for computer animation.
A familiarity with Eulerian fluid simulation techniques for computer animation. The necessary background material can be found in the book Fluid Simulation for Computer Graphics by Robert Bridson (available from A K Peters), or the SIGGRAPH 2007 course notes on Fluid Simulation by Robert Bridson and Matthias Müller-Fischer. In addition, a passing knowledge of basic triangle mesh algorithms like subdivision and edge collapses will be useful.
@inproceedings{wojtan2011liquid,
title={Liquid simulation with mesh-based surface tracking},
author={Wojtan, C. and M{\"u}ller-Fischer, M. and Brochu, T.},
booktitle={ACM SIGGRAPH 2011 Courses},
year={2011},
organization={ACM}
}
Georgia Institute of Technology (PhD Thesis, 2010)
Accurate computational representations of highly deformable surfaces are indispensable in the fields of computer animation, medical simulation, computer vision, digital modeling, and computational physics. The focus of this dissertation is on the animation of physics-based phenomena with highly detailed deformable surfaces represented by triangle meshes. We first present results from an algorithm that generates continuum mechanics animations with intricate surface features. This method combines a finite element method with a tetrahedral mesh generator and a high resolution surface mesh, and it is orders of magnitude more efficient than previous approaches. Next, we present an efficient solution for the challenging problem of computing topological changes in detailed dynamic surface meshes. We then introduce a new physics-inspired surface tracking algorithm that is capable of preserving arbitrarily thin features and reproducing realistic fine-scale topological changes like Rayleigh-Plateau instabilities. This physics-inspired surface tracking technique also opens the door for a unique coupling between surficial finite element methods and volumetric finite difference methods, in order to simulate liquid surface tension phenomena more efficiently than any previous method. Due to its dramatic increase in computational resolution and efficiency, this method yielded the first computer simulations of a fully developed crown splash with droplet pinch off.
@phdthesis{WojtanPhd2010,
author = {Chris Wojtan},
title = {Animating Physical Phenomena with Embedded Surface Meshes},
school = {Georgia Institute of Technology},
year = {2010},
month = {11}
}
ACM Transactions on Graphics (Siggraph 2010)
We propose a mesh-based surface tracking method for fluid animation that both preserves fine surface details and robustly adjusts the topology of the surface in the presence of arbitrarily thin features like sheets and strands. We replace traditional re-sampling methods with a convex hull method for connecting surface features during topological changes. This technique permits arbitrarily thin fluid features with minimal re-sampling errors by reusing points from the original surface. We further reduce re-sampling artifacts with a subdivision-based mesh-stitching algorithm, and we use a higher order interpolating subdivision scheme to determine the location of any newly-created vertices. The resulting algorithm efficiently produces detailed fluid surfaces with arbitrarily thin features while maintaining a consistent topology with the underlying fluid simulation.
@article{1778787,
author = {Wojtan, Chris and Th\"{u}rey, Nils and Gross, Markus and Turk, Greg},
title = {Physics-inspired topology changes for thin fluid features},
journal = {ACM Trans. Graph.},
volume = {29},
number = {4},
year = {2010},
issn = {0730-0301},
pages = {1--8},
doi = {http://doi.acm.org/10.1145/1778765.1778787},
publisher = {ACM},
address = {New York, NY, USA},
}
ACM Transactions on Graphics (Siggraph 2010)
We present an approach to simulate flows driven by surface tension based on triangle meshes. Our method consists of two simulation layers: the first layer is an Eulerian method for simulating surface tension forces that is free from typical strict time step constraints. The second simulation layer is a Lagrangian finite element method that simulates sub-grid scale wave details on the fluid surface. The surface wave simulation employs an unconditionally stable, symplectic time integration method that allows for a high propagation speed due to strong surface tension. Our approach can naturally separate the grid- and sub-grid scales based on a volume-preserving mean curvature flow. As our model for the sub-grid dynamics enforces a local conservation of mass, it leads to realistic pinch off and merging effects. In addition to this method for simulating dynamic surface tension effects, we also present an efficient non-oscillatory approximation for capturing damped surface tension behavior. These approaches allow us to efficiently simulate complex phenomena associated with strong surface tension, such as Rayleigh-Plateau instabilities and crown splashes, in a short amount of time.
@inproceedings{1778785,
author = {Th\"{u}rey, Nils and Wojtan, Chris and Gross, Markus and Turk, Greg},
title = {A multiscale approach to mesh-based surface tension flows},
booktitle = {SIGGRAPH '10: ACM SIGGRAPH 2010 papers},
year = {2010},
isbn = {978-1-4503-0210-4},
pages = {1--10},
location = {Los Angeles, California},
doi = {http://doi.acm.org/10.1145/1833349.1778785},
publisher = {ACM},
address = {New York, NY, USA},
}
IEEE Transactions on Visualization and Computer Graphics (TVCG 2010)
We present an algorithm for creating realistic animations of characters that are swimming through fluids. Our approach combines dynamic simulation with data-driven kinematic motions (motion capture data) to produce realistic animation in a fluid. The interaction of the articulated body with the fluid is performed by incorporating joint constraints with rigid animation and by extending a solid/fluid coupling method to handle articulated chains. Our solver takes as input the current state of the simulation and calculates the angular and linear accelerations of the connected bodies needed to match a particular motion sequence for the articulated body. These accelerations are used to estimate the forces and torques that are then applied to each joint. Based on this approach, we demonstrate simulated swimming results for a variety of different strokes, including crawl, backstroke, breaststroke, and butterfly. The ability to have articulated bodies interact with fluids also allows us to generate simulations of simple water creatures that are driven by simple controllers.
@ARTICLE{5089323,
author={Kwatra, Nipun and Wojtan, Chris and Carlson, Mark and Essa, Irfan A. and Mucha, Peter J. and Turk, Greg},
journal={IEEE Transactions on Visualization and Computer Graphics},
title={Fluid Simulation with Articulated Bodies},
year={2010},
volume={16},
number={1},
pages={70-80},
keywords={Animation;Computational modeling;Kinematics;Acceleration;Marine animals;Fluid dynamics;Solids;Computer graphics;Computer simulation;Physically-based animation;fluid simulation;motion capture.},
doi={10.1109/TVCG.2009.66}
}
ACM Transactions on Graphics (Siggraph 2009)
We present a method for accurately tracking the moving surface of deformable materials in a manner that gracefully handles topological changes. We employ a Lagrangian surface tracking method, and we use a triangle mesh for our surface representation so that fine features can be retained. We make topological changes to the mesh by first identifying merging or splitting events at a particular grid resolution, and then locally creating new pieces of the mesh in the affected cells using a standard isosurface creation method. We stitch the new, topologically simplified portion of the mesh to the rest of the mesh at the cell boundaries. Our method detects and treats topological events with an emphasis on the preservation of detailed features, while simultaneously simplifying those portions of the material that are not visible. Our surface tracker is not tied to a particular method for simulating deformable materials. In particular, we show results from two significantly different simulators: a Lagrangian FEM simulator with tetrahedral elements, and an Eulerian grid-based fluid simulator. Although our surface tracking method is generic, it is particularly well-suited for simulations that exhibit fine surface details and numerous topological events. Highlights of our results include merging of viscoplastic materials with complex geometry, a taffy-pulling animation with many fold and merge events, and stretching and slicing of stiff plastic material.
@inproceedings{10.1145/1576246.1531382,
author = {Wojtan, Chris and Th\"{u}rey, Nils and Gross, Markus and Turk, Greg},
title = {Deforming meshes that split and merge},
year = {2009},
isbn = {9781605587264},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1576246.1531382},
doi = {10.1145/1576246.1531382},
booktitle = {ACM SIGGRAPH 2009 Papers},
articleno = {76},
numpages = {10},
keywords = {topological control, physically based animation, fluid simulation, deformable meshes},
location = {New Orleans, Louisiana},
series = {SIGGRAPH '09}
}
ACM Transactions on Graphics (Siggraph 2008)
We introduce a method for efficiently animating a wide range of deformable materials. We combine a high resolution surface mesh with a tetrahedral finite element simulator that makes use of frequent re-meshing. This combination allows for fast and detailed simulations of complex elastic and plastic behavior. We significantly expand the range of physical parameters that can be simulated with a single technique, and the results are free from common artifacts such as volume-loss, smoothing, popping, and the absence of thin features like strands and sheets. Our decision to couple a high resolution surface with low-resolution physics leads to efficient simulation and detailed surface features, and our approach to creating the tetrahedral mesh leads to an order-of-magnitude speedup over previous techniques in the time spent re-meshing. We compute masses, collisions, and surface tension forces on the scale of the fine mesh, which helps avoid visual artifacts due to the differing mesh resolutions. The result is a method that can simulate a large array of different material behaviors with high resolution features in a short amount of time.
@article{10.1145/1360612.1360646,
author = {Wojtan, Chris and Turk, Greg},
title = {Fast viscoelastic behavior with thin features},
year = {2008},
issue_date = {August 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {27},
number = {3},
issn = {0730-0301},
url = {https://doi.org/10.1145/1360612.1360646},
doi = {10.1145/1360612.1360646},
journal = {ACM Trans. Graph.},
month = aug,
pages = {1–8},
numpages = {8},
keywords = {computational fluid dynamics, deformable models, explicit surface, finite element method, free-form deformation, viscoelastic behavior}
}
Eurographics conference on Natural Phenomena (NPH 2007)
In this paper, we present a simple method for animating natural phenomena such as erosion, sedimentation, and acidic corrosion. We discretize the appropriate physical or chemical equations using finite differences, and we use the results to modify the shape of a solid body. We remove mass from an object by treating its surface as a level set and advecting it inward, and we deposit the chemical and physical byproducts into simulated fluid. Similarly, our technique deposits sediment onto a surface by advecting the level set outward. Our idea can be used for off-line high quality animations as well as interactive applications such as games, and we demonstrate both in this paper.
@inproceedings{10.5555/2381384.2381387,
author = {Wojtan, Chris and Carlson, Mark and Mucha, Peter J. and Turk, Greg},
title = {Animating corrosion and erosion},
year = {2007},
isbn = {9783905673494},
publisher = {Eurographics Association},
address = {Goslar, DEU},
booktitle = {Proceedings of the Third Eurographics Conference on Natural Phenomena},
pages = {15–22},
numpages = {8},
location = {Prague, Czech Republic},
series = {NPH'07}
}
ACM Transactions on Graphics (Siggraph 2007)
We present an extension to Lagrangian finite element methods to allow for large plastic deformations of solid materials. These behaviors are seen in such everyday materials as shampoo, dough, and clay as well as in fantastic gooey and blobby creatures in special effects scenes. To account for plastic deformation, we explicitly update the linear basis functions defined over the finite elements during each simulation step. When these updates cause the basis functions to become ill-conditioned, we remesh the simulation domain to produce a new high-quality finite-element mesh, taking care to preserve the original boundary. We also introduce an enhanced plasticity model that preserves volume and includes creep and work hardening/softening. We demonstrate our approach with simulations of synthetic objects that squish, dent, and flow. To validate our methods, we compare simulation results to videos of real materials.
@inproceedings{10.1145/1275808.1276397,
author = {Bargteil, Adam W. and Wojtan, Chris and Hodgins, Jessica K. and Turk, Greg},
title = {A finite element method for animating large viscoplastic flow},
year = {2007},
isbn = {9781450378369},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1275808.1276397},
doi = {10.1145/1275808.1276397},
booktitle = {ACM SIGGRAPH 2007 Papers},
pages = {16–es},
keywords = {viscoplastic, viscoelastic, physically based animation, natural phenomena, finite element methods, elastoplastic, deformable models, computational fluid dynamics},
location = {San Diego, California},
series = {SIGGRAPH '07}
}
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA 2006)
Control of physical simulation has become a popular topic in the field of computer graphics. Keyframe control has been applied to simulations of rigid bodies, smoke, liquid, flocks, and finite element-based elastic bodies. In this paper, we create a framework for controlling systems of interacting particles – paying special attention to simulations of cloth and flocking behavior. We introduce a novel integrator-swapping approximation in order to apply the adjoint method to linearized implicit schemes appropriate for cloth simulation. This allows the control of cloth while avoiding computationally infeasible derivative calculations. Meanwhile, flocking control using the adjoint method is significantly more efficient than currently-used methods for constraining group behaviors, allowing the controlled simulation of greater numbers of agents in fewer optimization iterations.
@inproceedings{1218067,
author = {Chris Wojtan and Peter J. Mucha and Greg Turk},
title = {Keyframe control of complex particle systems using the adjoint method},
booktitle = {SCA '06: Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation},
year = {2006},
isbn = {3-905673-34-7},
pages = {15--23},
location = {Vienna, Austria},
publisher = {Eurographics Association},
address = {Aire-la-Ville, Switzerland, Switzerland},
}
The generation of realistic motion satisfying user-defined requirements is one of the most important goals of computer animation. Our aim in this paper is the synthesis of realistic, controllable motion for lightweight natural objects in a gaseous medium. We formulate this problem as a large-scale spacetime optimization with user controls and fluid motion equations as constraints. We have devised novel and effective methods to make this large optimization tractable. Initial trajectories are generated with data-driven synthesis based on stylistic motion planning. Smoothed particle hydrodynamics (SPH) is used during optimization to produce fluid simulations at a reasonable computational cost, while interesting vortex-based fluid motion is generated by recording the presence of vortices in the initial trajectories and maintaining them through optimization. Object rotations are refined as a postprocess to enhance the visual quality of the results. We demonstrate our techniques on a number of animations involving single or multiple objects.
@article{shi2005controllable,
title={Controllable motion synthesis in a gaseous medium},
author={Shi, Lin and Yu, Yizhou and Wojtan, Christopher and Chenney, Stephen},
journal={The Visual Computer},
volume={21},
pages={474--487},
year={2005},
publisher={Springer}
}