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}
}

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.}
}

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}
}

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}
}

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}
}

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}
}

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)}
}

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}
}

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}
}

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}
}

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"
}

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}
}

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.

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}
}

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}
}

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{isnhw2020soapfilm_with_thickness,
  author    = {Sadashige Ishida and Peter Synak and Fumiya Narita and Toshiya Hachisuka and Chris Wojtan}
  title     = {A Model for Soap Film Dynamics with Evolving Thickness},
  journal   = {ACM Trans. on Graphics},
  number    = {4},
  volume    = {39},
  year      = {2020},
  pages     = {31:1--31:11},
  articleno = 31,
  url       = {http://dx.doi.org/10.1145/3386569.3392405},
  doi       = {10.1145/3386569.3392405},
  publisher = {ACM}
}

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",
}

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"
}

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}
}

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.

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}
}

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}
}

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},
}

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}
}

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",
}

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{WWAvWPI2015,
author = {Stefan Jeschke and Chris Wojtan},
title = {Water Wave Animation via Wavefront Parameter Interpolation},
journal = {ACM Transactions on Graphics},
year = {2015},
volume = {34},
number = {3},
pages = {1--14}
}

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}
}

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.

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{Guerrero-2014-GRF,
author = {Paul Guerrero and Stefan Jeschke and Michael Wimmer and Peter Wonka},
title = {Edit Propagation using Geometric Relationship Functions},
journal = {ACM Transactions on Graphics},
year = {2014},
volume = {33},
number = {2},
pages = {15:1--15:15}
}

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}
}

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}
}