Publications

Energy-Preserving Integrators for Fluid Animation (pdf)

Patrick Mullen, Keenan Crane, Dmitry Pavlov, Yiying Tong and

Mathieu Desbrun.
To Appear: ACM Transactions on Graphics (SIGGRAPH), 2009.

Numerical viscosity has long been a problem in fluid animation. Existing methods suffer from intrinsic artificial dissipation and often apply complicated computational mechanisms to combat such effects. Consequently, dissipative behavior cannot be controlled or modeled explicitly in a manner independent of time step size, complicating the use of coarse previews and adaptive-time stepping methods. This paper proposes simple, unconditionally stable, fully Eulerian integration schemes with no numerical viscosity that are capable of maintaining the liveliness of fluid motion without recourse to corrective devices. Pressure and fluxes are solved efficiently and simultaneously in a time-reversible manner on simplicial grids, and the energy is preserved exactly over long time scales in the case of inviscid fluids. These integrators can be viewed as an extension of the classical energy-preserving Harlow-Welch / Crank-Nicolson scheme to simplicial grids.

Video (divx)  YouTube

Numerical Coarsening of Inhomogeneous Elastic Materials (pdf)

Lily Kharevych, Patrick Mullen, Houman Owhadi and Mathieu Desbrun.
To Appear: ACM Transactions on Graphics (SIGGRAPH), 2009.

We propose an approach for efficiently simulating elastic objects made of non-homogeneous, non-isotropic materials. Based on recent developments in homogenization theory, a methodology is introduced to approximate a deformable object made of arbitrary fine structures of various linear elastic materials with a dynamically similar coarse model. This numerical coarsening of the material properties allows for simulation of fine, heterogeneous structures on very coarse grids while capturing the proper dynamics of the original dynamical system, thus saving orders of magnitude in computational time. Examples including inhomogeneous and/or anisotropic materials can be realistically simulated in realtime using a numerically-coarsened model made of a few mesh elements.

Video (divx)

Spectral Conformal Parameterization (pdf)

Patrick Mullen, Yiying Tong, Pierre Alliez and Mathieu Desbrun.
Symposium on Geometry Processing, 2008.

We present a spectral approach to automatically and efficiently obtain discrete free-boundary conformal parameterizations of triangle mesh patches, without the common artifacts due to positional constraints on vertices and without undue bias introduced by sampling irregularity. High-quality parameterizations are computed through a constrained minimization of a discrete weighted conformal energy by finding the largest eigenvalue/eigenvector of a generalized eigenvalue problem involving sparse, symmetric matrices. We demonstrate that this novel and robust approach improves on previous linear techniques both quantitatively and qualitatively.

A Variational Approach to Eulerian Geometry Processing (pdf)

Patrick Mullen, Alexander McKenzie, Yiying Tong and Mathieu Desbrun.
ACM Transactions on Graphics (SIGGRAPH), 2007.

We present a purely Eulerian framework for geometry processing of surfaces and foliations. Contrary to current Eulerian methods used in graphics, we use conservative methods and a variational interpretation, offering a unified framework for routine surface operations such as smoothing, offsetting, and animation. Computations are performed on a fixed volumetric grid without recourse to Lagrangian techniques such as triangle meshes, particles, or path tracing. At the core of our approach is the use of the Coarea Formula to express area integrals over isosurfaces as volume integrals. This enables the simultaneous processing of multiple isosurfaces, while a single interface can be treated as the special case of a dense foliation. We show that our method is a powerful alternative to conventional geometric representations in delicate cases such as the handling of high-genus surfaces, weighted offsetting, foliation smoothing of medical datasets, and incompressible fluid animation.

Supplemental Video (divx)

Data-Dependent Fairing of Subdivision Surfaces (pdf)

Ilja Friedel, Patrick Mullen and Peter Schröder

Solid Modeling, 2003

In this paper we present a new algorithm for solving the data dependent fairing problem for subdivision surfaces, using Catmull-Clark surfaces as an example. Earlier approaches to subdivision surface fairing encountered problems with singularities in the parametrization of the surface. We address these issues through the use of the characteristic map parametrization, leading to well defined membrane and bending energies even at irregular vertices. Combining this approach with ideas from data-dependent energy operators we are able to express the associated nonlinear stiffness matrices for Catmull-Clark surfaces as linear combinations of precomputed energy matrices. This machinery also provides exact, inexpensive gradients and Hessians of the new energy operators. With these the nonlinear minimization problem can be solved in a stable and efficient way using Steihaug's Newton/CG trust-region method. We compare properties of linear and nonlinear methods through a number of examples and report on the performance of the algorithm.

Teaching

Co-taught and TA’d CS101.3: Numerical Geometric Integration Winter 2008-2009 w/ Mathieu Desbrun