
Discrete Connection and Covariant Derivative for Vector Field Analysis and Design
Beibei Liu, Yiying Tong, Fernando de Goes, and Mathieu Desbrun.
ACM Trans. Graph, to be published, 2016.
Abstract:
In this paper, we introduce a discrete definition of connection on simplicial
manifolds, involving closedform continuous expressions within simplices
and finite rotations across simplices. The finitedimensional parameters of
this connection are optimally computed by minimizing a quadratic measure
of the deviation to the (discontinuous) LeviCivita connection induced
by the embedding of the input triangle mesh, or to any metric connection
with arbitrary cone singularities at vertices. From this discrete connection,
a covariant derivative is constructed through exact differentiation, leading
to explicit expressions for local integrals of firstorder derivatives (such as
divergence, curl and the CauchyRiemann operator), and for L2based energies
(such as the Dirichlet energy). We finally demonstrate the utility, flexibility,
and accuracy of our discrete formulations for the design and analysis
of vector, nvector, and ndirection fields.


A Semianalytical Approach to Molecular Dynamics
Dominik L. Michels and Mathieu Desbrun.
Journal of Computational Physics, Volume 303, Pages 336354, December 2015.
Abstract:
Despite numerous computational advances over the last few decades, molecular
dynamics still favors explicit (and thus easilyparallelizable) time integrators for
large scale numerical simulation. As a consequence, computational efficiency in
solving its typically stiff oscillatory equations of motion is hampered by stringent
stability requirements on the time step size. In this paper, we present a semianalytical
integration scheme that others a total speedup of a factor 30 compared
to the Verlet method on typical MD simulation by allowing over three orders of
magnitude larger step sizes. By efficiently approximating the exact integration
of the strong (harmonic) forces of covalent bonds through matrix functions, far
improved stability with respect to time step size is achieved without sacrificing
the explicit, symplectic, timereversible, or finegrained parallelizable nature
of the integration scheme. We demonstrate the efficiency and scalability of
our integrator on simulations ranging from DNA strand unbinding and protein
folding to nanotube resonators.


TimeVarying Surface Reconstruction of an Actor’s Performance
Ludovic Blache, Mathieu Desbrun, Céline Loscos, and Laurent Lucas.
Advances in Visual Computing, Volume 9474 of Lecture Notes in Computer Science, 92101, December 2015.
Abstract:
We propose a fully automatic timevarying surface reconstruction
of an actor’s performance captured from a production stage
through omnidirectional video. The resulting mesh and its texture can
then directly be edited in postproduction. Our method makes no
assumption on the costumes or accessories present in the recording. We
take as input a raw sequence of volumetric static poses reconstructed
from video sequences acquired in a multiviewpoint chromakey studio.
The first frame is chosen as the reference mesh. An iterative approach is
applied throughout the sequence in order to induce a deformation of the
reference mesh for all input frames. At first, a pseudorigid transformation
adjusts the pose to match the input visual hull as closely as possible.
Then, local deformation is added to reconstruct fine details. We provide
examples of actors’ performance inserted into virtual scenes, including
dynamic interaction with the environment.


ModelReduced Variational Fluid Simulation
Beibei Liu, Gemma Mason, Julian Hodgson, Yiying Tong, and Mathieu Desbrun.
ACM Trans. Graph. (SIG Asia), 34(6), Art. 244, November 2015.
Abstract:
We present a modelreduced variational Eulerian integrator for incompressible fluids, which combines the efficiency gains of dimension
reduction, the qualitative robustness of coarse spatial and temporal resolutions of geometric integrators, and the simplicity of
subgrid accurate boundary conditions on regular grids to deal with arbitrarilyshaped domains. At the core of our contributions is a
functional map approach to fluid simulation for which scalar and vectorvalued eigenfunctions of the Laplacian operator can be easily
used as reduced bases. Using a variational integrator in time to preserve liveliness and a simple, yet accurate embedding of the fluid
domain onto a Cartesian grid, our modelreduced fluid simulator can achieve realistic animations in significantly less computational
time than fullscale nondissipative methods but without the numerical viscosity from which current reduced methods suffer. We also
demonstrate the versatility of our approach by showing how it easily extends to magnetohydrodynamics and turbulence modeling in 2D, 3D and curved domains.


Vector field processing on triangle meshes
Fernando de Goes, Mathieu Desbrun, and Yiying Tong.
Course notes, ACM SIGGRAPH Asia 2015.
Abstract:
While scalar fields on surfaces have been staples of geometry processing,
the use of tangent vector fields has steadily grown in geometry processing over the last two decades: they are crucial to encoding directions and sizing on surfaces as commonly required in tasks such as texture synthesis, nonphotorealistic rendering, digital grooming, and meshing. There are, however, a variety of discrete representations of tangent vector fields on triangle meshes, and each approach offers different tradeoffs among simplicity, efficiency, and accuracy depending on the targeted application.
This course reviews the three main families of discretizations used to design computational tools for vector field processing on triangle meshes: facebased, edgebased, and vertexbased representations. In the process of reviewing the computational tools offered by these representations, we go over a large body of recent developments in vector field processing in the area of discrete differential geometry. We also discuss the theoretical and practical limitations of each type of discretization, and cover increasinglycommon extensions such as ndirection and nvector fields.
While the course will focus on explaining the key approaches to practical encoding and manipulation of finitedimensional vector fields, important differential geometric notions will also be covered: as often in Discrete Differential Geometry, the discrete picture will be used to illustrate deep continuous concepts such as covariant derivatives, metric connections, or Bochner Laplacians.


Power Particles: An incompressible fluid solver based on power diagrams
Fernando de Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun.
ACM Transactions on Graphics (SIGGRAPH),34(4), Art. 50, 2015. Video part I, part II
Abstract:
This paper introduces a new particlebased approach to incompressible
fluid simulation. We depart from previous Lagrangian methods
by considering fluid particles no longer purely as material points,
but also as volumetric parcels that partition the fluid domain. The
fluid motion is described as a time series of wellshaped power diagrams
(hence the name power particles), offering evenly spaced
particles and accurate pressure computations. As a result, we circumvent
the typical excess damping arising from kernelbased evaluations
of internal forces or density without having recourse to auxiliary
Eulerian grids. The versatility of our solver is demonstrated
by the simulation of multiphase flows and free surfaces.


Frame Field Generation through Metric Customization
Tengfei Jiang, Xianzhong Fang, Jin Huang, Hujun Bao, Yiying Tong, and Mathieu Desbrun.
ACM Transactions on Graphics (SIGGRAPH), 34(4), Art. 40, 2015.
Abstract:
This paper presents a new technique for frame field generation. As
generic frame fields (with arbitrary anisotropy, orientation, and sizing)
can be regarded as cross fields in a specific Riemannian metric,
we tackle frame field design by first computing a discrete metric on
the input surface that is compatible with a sparse or dense set of input
constraints. The final frame field is then found by computing
an optimal cross field in this customized metric. We propose frame
field design constraints on alignment, size, and skewness at arbitrary
locations on the mesh as well as along feature curves, offering
much improved flexibility over previous approaches. We demonstrate
the advantages of our frame field generation through the automatic
quadrangulation of manmade and organic shapes with controllable
anisotropy, robust handling of narrow surface strips, and
precise feature alignment. We also extend our technique to the design
of nvector fields.


Computational Electromagnetism with Variational Integrators and Discrete Differential Forms
Ari Stern, Yiying Tong, Mathieu Desbrun, and Jerrold E. Marsden.
In Geometry, mechanics, and dynamics: the legacy of Jerry Marsden, Fields Institute Communications, 2014.
Abstract:
In this paper, we introduce a general family of variational, multisymplectic numerical methods for solving Maxwell's equations, using discrete differential forms in spacetime. In doing so, we demonstrate several new results, which apply both to some wellestablished numerical methods and to new methods introduced here. First, we show that Yee's finitedifference timedomain (FDTD) scheme, along with a number of related methods, are multisymplectic and derive from a discrete Lagrangian variational principle. Second, we generalize the Yee scheme to unstructured meshes, not just in space, but in 4dimensional spacetime. This relaxes the need to take uniform time steps, or even to have a preferred time coordinate at all. Finally, as an example of the type of methods that can be developed within this general framework, we introduce a new asynchronous variational integrator (AVI) for solving Maxwell's equations. These results are illustrated with some prototype simulations that show excellent energy and conservation behavior.


Discrete 2Tensor Fields on Triangulations
Fernando de Goes, Beibei Liu, Max Budninskiy, Yiying Tong, and Mathieu Desbrun.
Symposium on Geometry Processing, 2014.
Abstract:
Geometry processing has made ample use of discrete representations of tangent vector fields and antisymmetric
tensors (i.e., forms) on triangulations. Symmetric 2tensors, while crucial in the definition of inner products and
elliptic operators, have received only limited attention. They are often discretized by first defining a coordinate
system per vertex, edge or face, then storing their components in this frame field. In this paper, we introduce a
representation of arbitrary 2tensor fields on triangle meshes. We leverage a coordinatefree decomposition of
continuous 2tensors in the plane to construct a finitedimensional encoding of tensor fields through scalar values
on oriented simplices of a manifold triangulation. We also provide closedform expressions of pairing, inner
product, and trace for this discrete representation of tensor fields, and formulate a discrete covariant derivative
and a discrete Lie bracket. Our approach extends discrete/finiteelement exterior calculus, recovers familiar operators
such as the weighted Laplacian operator, and defines discrete notions of divergencefree, curlfree, and
traceless tensors—thus offering a numerical framework for discrete tensor calculus on triangulations. We finally
demonstrate the robustness and accuracy of our operators on analytical examples, before applying them to the
computation of anisotropic geodesic distances on discrete surfaces.


Fast TileBased Adaptive Sampling with UserSpecified Fourier Spectra
Florent Wachtel, Adrien Pilleboue, David Coeurjolly, Katherine Breeden, Gurprit Singh,
Gael Cathelin, Fernando de Goes, Mathieu Desbrun, and Victor Ostromoukhov.
ACM Transactions on Graphics (SIGGRAPH), Vol. 33(4), Art. 56, 2014. (see also Project Page (with code and data), supplementary material, and video)
Abstract:
We introduce a fast tilebased method for adaptive twodimensional
sampling with userspecified spectral properties. At the core of our
approach is a deterministic, hierarchical construction of selfsimilar,
equiarea, trihex tiles whose centroids have a spatial distribution
free of spurious spectral peaks. A lookup table of sample points,
computed offline using any existing point set optimizer to shape
the samples’ Fourier spectrum, is then used to populate the tiles.
The result is a lineartime, adaptive, and highquality sampling of
arbitrary density functions that conforms to the desired spectral
distribution, achieving a speed improvement of several orders of
magnitude over current spectrumcontrolled sampling methods.


SpaceTime Editing of Elastic Motion through Material Optimization and Reduction
Siwang Li, Jin Huang, Fernando de Goes, Xiaogang Jin, Hujun Bao, and Mathieu Desbrun.
ACM Transactions on Graphics (SIGGRAPH), Vol. 33(4), Art. 108, 2014. (video)
Abstract:
We present a novel method for elastic animation editing with spacetime
constraints. In a sharp departure from previous approaches,
we not only optimize control forces added to a linearized dynamic
model, but also optimize material properties to better match user
constraints and provide plausible and consistent motion. Our approach
achieves efficiency and scalability by performing all computations
in a reduced rotationstrain (RS) space constructed with
both cubature and geometric reduction, leading to two orders of
magnitude improvement over the original RS method. We demonstrate
the utility and versatility of our method in various applications,
including motion editing, pose interpolation, and estimation
of material parameters from existing animation sequences.


A Constructive Theory of Sampling for Image Synthesis using Reproducing Kernel Bases
Christian Lessig, Mathieu Desbrun, and Eugene Fiume.
ACM Transactions on Graphics (SIGGRAPH), Vol. 33(4), Art. 66, 2014 (see also Project Page).
Abstract:
Sampling a scene by tracing rays and reconstructing an image from
such pointwise samples is fundamental to computer graphics. To improve
the efficacy of these computations, we propose an alternative
theory of sampling. In contrast to traditional formulations for image
synthesis, which appeal to nonconstructive Dirac deltas, our theory
employs constructive reproducing kernels for the correspondence
between continuous functions and pointwise samples. Conceptually,
this allows us to obtain a common mathematical formulation of
almost all existing numerical techniques for image synthesis. Practically,
it enables novel sampling based numerical techniques designed
for light transport that provide considerably improved performance
per sample. We exemplify the practical benefits of our formulation
with three applications: pointwise transport of color spectra, projection
of the light energy density into spherical harmonics, and
approximation of the shading equation from a photon map. Experimental
results verify the utility of our sampling formulation, with
lower numerical error rates and enhanced visual quality compared
to existing techniques.


Weighted Triangulations for Geometry Processing
Fernando de Goes, Pooran Memari, Patrick Mullen, and Mathieu Desbrun.
ACM Transactions on Graphics, Vol. 33 (3). Art. 28, 2014.
Abstract:
In this paper, we investigate the use of weighted triangulations as discrete, augmented approximations of surfaces for digital geometry processing.
By incorporating a scalar weight per mesh vertex, we introduce a new notion of discrete metric that defines an orthogonal dual structure for arbitrary triangle meshes and thus extends weighted Delaunay triangulations to surface meshes.
We also present alternative characterizations of this primaldual structure (through combinations of angles, areas, and lengths) and, in the process, uncover closedform expressions of mesh energies that were previously known in implicit form only.
Finally, we demonstrate how weighted triangulations provide a faster and more robust approach to a series of geometry processing applications, including the generation of wellcentered meshes, selfsupporting surfaces, and sphere packing.


ℓ₁based Construction of Polycube Maps from Complex Shapes
Jin Huang, Tengfei Jiang, Zeyun Shi, Yiying Tong, Hujun Bao, and Mathieu Desbrun.
ACM Transactions on Graphics, Vol. 33(3), Art. 25, 2014.
Abstract:
Polycube maps of triangle meshes have proved useful in a wide range of applications including texture mapping and hexahedral mesh generation.
However, constructing either fully automatically or with limited user control a lowdistortion polycube from a detailed surface remains challenging
in practice. We propose a variational method for deforming an input triangle mesh into a polycube shape through minimization of the ℓ₁norm of the mesh normals, regularized via an asrigidaspossible volumetric distortion energy. Unlike previous work, our approach makes no assumption on the
orientation, or on the presence of features in the input model. Userguided control over the resulting polycube map is also offered to increase design
flexibility. We demonstrate the robustness, efficiency and controllability of our method on a variety of examples, and explore applications in hexahedral
remeshing and quadrangulation.


On the Coupling Between an Ideal Fluid and Immersed Particles
Henry O. Jacobs, Tudor S. Ratiu, and Mathieu Desbrun.
Physica D, 265(15), pp. 40–56, December 2013.
Abstract:
In this paper we present finite dimensional particlebased models for fluids which respect a number of geometric properties of the Euler equations of motion.
Specifically, we use LagrangePoincaré reduction to understand the coupling between a fluid and a set of
Lagrangian particles that are supposed to simulate it. We substitute the use of principal connections in [Cendra et al. 2001] with vector field valued interpolations
from particle velocity data. The consequence of writing evolution equations in terms of
interpolation is twofold. First, it provides estimates on the error incurred when interpolation is used to derive the
evolution of the system. Second, this form of the equations of motion can inspire a family of particle and hybrid
particlespectral methods, where the error analysis is "builtin''. We also discuss the influence of other
parameters attached to the particles, such as shape, orientation, or higherorder deformations, and how they can
help with conservation of momenta in the sense of Kelvin's circulation theorem.


On the Equilibrium of Simplicial Masonry Structures
Fernando de Goes, Pierre Alliez, Houman Owhadi, and Mathieu Desbrun
ACM Transactions on Graphics (SIGGRAPH) 32(4), Art. 93, 2013
Abstract:
We present a novel approach for the analysis and design of selfsupporting
simplicial masonry structures. A finitedimensional formulation
of their compressive stress field is derived, offering a new
interpretation of thrust networks through numerical homogenization
theory. We further leverage geometric properties of the resulting
force diagram to identify a set of reduced coordinates characterizing
the equilibrium of simplicial masonry. We finally derive computational
formfinding tools that improve over previous work in
efficiency, accuracy, and scalability.


The Chain Collocation Method: A Spectrally Accurate Calculus of Forms
Dzhelil Rufat, Gemma Mason, Patrick Mullen, and Mathieu Desbrun.
Journal of Computational Physics, Volume 257(B), Pages 1352–1372, 2014.[Project page]
Abstract:
Preserving in the discrete realm the underlying geometric, topological, and algebraic structures at stake in partial differential equations has proven to be a fruitful guiding principle for numerical methods in a variety of fields such as elasticity, electromagnetism, or fluid mechanics. However, structurepreserving methods have traditionally used spaces of piecewise polynomial basis functions for differential forms. Yet, in many problems where solutions are smoothly varying in space, a spectral numerical treatment is called for. In an effort to provide structurepreserving numerical tools with spectral accuracy on logically rectangular grids over periodic or bounded domains, we present a spectral extension of the discrete exterior calculus (DEC), with resulting computational tools extending wellknown collocationbased spectral methods. Its efficient implementation using fast Fourier transforms is provided as well.


Digital Geometry Processing using Discrete Exterior Calculus
Fernando de Goes, Keenan Crane, Peter Schröder, and Mathieu Desbrun
ACM SIGGRAPH'13 Course Notes (see also Keenan's page).
Abstract:
An introduction to geometry processing using discrete exterior calculus (DEC), which provides a simple, flexible, and efficient framework for building a unified geometryprocessing platform. The course provides essential mathematical background as well as a large array of realworld examples. It also provides a short survey of the most relevant recent developments in digital geometry processing and discrete differential geometry. Compared to previous SIGGRAPH courses, this course focuses heavily on practical aspects of DEC, with an emphasis on implementation and applications.
The course begins with the core ideas from exterior calculus, in both the smooth and discrete setting. Then it shows how a large number of fundamental geometryprocessing tools (smoothing, parameterization, geodesics, mesh optimization, etc) can be implemented quickly, robustly, and efficiently within this single common framework. It concludes with a discussion of recent extensions of DEC that improve efficiency, accuracy, and versatility.
The course notes grew out of the discrete differential geometry course taught over the past five years at the California Institute of Technology, for undergraduates and beginning graduate students in computer science, applied mathematics, and associated fields. The notes also provide guided exercises (both written and coding) that attendees can later use to deepen their understanding of the material.


Variational Discretization for Rotating Stratified Fluids
Mathieu Desbrun, Evan S. Gawlik, François GayBalmaz, and Vladimir Zeitlin
AIMS Discrete & Continuous Systems Series A, 34(2), pp. 477509, Feb 2014
Abstract. In this paper we develop and test a structurepreserving discretization
scheme for rotating and/or stratified fluid dynamics. The numerical
scheme is based on a finite dimensional approximation of the group of volume
preserving diffeomorphisms and is derived via a discrete version of the EulerPoincaré variational formulation of rotating
stratified fluids. The resulting variational integrator allows for a discrete version
of Kelvin circulation theorem, is applicable to irregular meshes and, being
symplectic, exhibits excellent long term energy behavior. We then report a
series of preliminary tests for rotating stratified flows in configurations that
are symmetric with respect to translation along one of the spatial directions.
In the benchmark processes of hydrostatic and/or geostrophic adjustments,
these tests show that the slow and fast component of the flow are correctly
reproduced. The harder test of inertial instability is in full agreement with the
common knowledge of the process of development and saturation of this instability,
while preserving energy nearly perfectly and respecting conservation laws.


Interactive Elastic Motion Editing through Spacetime Position Constraints
Siwang Li, Jin Huang, Mathieu Desbrun. and Xiaogang Jin
Journal of Computer Animation and Virtual Worlds (CASA), 2013
Abstract:
We present an intuitive and interactive approach for motion editing through spacetime constraints
on positions. Given an input motion of an elastic body, our approach enables the user to interactively
edit node positions in order to alter and finetune the motion. We formulate our motion
editing as an optimization problem with dynamics constraints to enforce a physicallyplausible result.
Through linearization of the editing around the input trajectory, we simplify this constrained optimal
control problem into an unconstrained quadratic optimization. The optimal motion thus becomes
the solution of a dense linear system, which we solve efficiently by applying the adjoint method
in each iteration of a conjugate gradient solver. We demonstrate the efficiency and quality of our
motion editing technique on a series of examples.


FeaturePreserving Surface Reconstruction and Simplification from DefectLaden Point Sets
Julie Digne, David CohenSteiner, Pierre Alliez, Mathieu Desbrun, and Fernando de Goes
Journal of Mathematical Imaging and Vision, Springer, Jan 2013
Abstract:
We introduce a robust and featurecapturing surface reconstruction and simplification method that turns an input point set into a low trianglecount simplicial complex. Our approach starts with a (possibly nonmanifold) simplicial complex filtered from a 3D Delaunay triangulation of the input points. This initial approximation is iteratively simplified based on an error metric that measures, through optimal transport, the distance between the input points and the current simplicial complex—both seen as mass distributions. Our approach is shown to exhibit both robustness to noise and outliers, as well as preservation of sharp features and boundaries. Our new featuresensitive metric between point sets and triangle meshes can also be used as a postprocessing tool that, from the smooth output of a reconstruction method, recovers sharp features and boundaries present in the initial point set.


Blue Noise through Optimal Transport
Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun.
ACM Transactions on Graphics (SIGGRAPH Asia), 2012 [Project page]
Abstract:
We present a fast, scalable algorithm to generate highquality blue noise point distributions of arbitrary density functions. At its core is a novel formulation of the recentlyintroduced concept of capacityconstrained Voronoi tessellation as an optimal transport problem. This insight leads to a continuous formulation able to enforce the capacity constraints exactly, unlike previous work. We exploit the variational nature of this formulation to design an efficient optimization technique of point distributions via constrained minimization in the space of power diagrams. Our mathematical, algorithmic, and practical contributions lead to highquality blue noise point sets with improved spectral and spatial properties.


Modeling Across Scales: Discrete Geometric Structures in Homogenization and Inverse Homogenization
Mathieu Desbrun, Roger Donaldson, and Houman Owhadi.
In Multiscale Analysis and Nonlinear Dynamics
Reviews of Nonlinear Dynamics and Complexity (Volume 8), Wiley, 2013. See also [arXiv 0904.2601]
Abstract:
Imaging and simulation methods are typically constrained to resolutions much coarser than the scale of physical microstructures present in body tissues or geological features. Mathematical and numerical homogenization address this practical issue by identifying and computing appropriate spatial averages that result in accuracy and consistency between the macroscales we observe and the underlying microscale models we
assume. Among the various applications benefiting from homogenization, Electric Impedance Tomography (EIT) images the electrical conductivity of a body by measuring electrical potentials consequential to electric currents applied to the exterior of the body. EIT is routinely used in breast cancer detection and cardiopulmonary imaging, where current flow in finescale tissues underlies the resulting coarsescale images.
In this paper, we introduce a geometric approach for the homogenization (simulation) and inverse homogenization (imaging) of divergenceform elliptic operators with rough conductivity coefficients in dimension two. We show that conductivity coefficients are in onetoone correspondence with divergencefree matrices and convex functions over the domain. Although homogenization is a nonlinear and noninjective operator when applied directly to conductivity coefficients, homogenization becomes a linear interpolation operator over triangulations of the domain when reexpressed using convex functions, and is a volume averaging operator when reexpressed with divergencefree matrices. We explicitly give the transformations which map conductivity coefficients into divergencefree matrices and convex functions, as well as their respective inverses. Using weighted Delaunay triangulations for linearly interpolating convex functions, we apply this geometric framework to obtain a robust homogenization algorithm for arbitrary rough coefficients, extending the global optimality of Delaunay triangulations with respect to a discrete Dirichlet energy to weighted Delaunay triangulations. We then consider inverse homogenization, which is known to be both nonlinear and severely illposed, but that we can decompose into a linear illposed problem and a wellposed nonlinear problem. Finally, our new geometric approach to homogenization and inverse homogenization is applied to EIT.


Tightening the Precision of Perspective Rendering
Paul Upchurch and Mathieu Desbrun.
Journal of Graphics Tools, Volume 16, Issue 1, 2012.
Abstract:
Precise depth calculation is of crucial importance in graphics rendering. Improving precision raises the quality of all downstream graphical techniques that rely on computed depth (e.g.,, depth buffers, soft and hard shadow maps, screen space ambient occlusion, and 3D stereo projection). In addition, the domain of correctly renderable scenes is expanded by allowing larger far to near plane ratios and smaller depth separation between mesh elements. Depth precision is an ongoing problem as visible artifacts continue to plague applications from interactive games to scientific visualizations despite advances in graphics hardware.
In this paper we present and analyze two methods that can greatly impact visual quality by automatically improving the precision of depth values calculated in a standard perspective divide rendering system such as OpenGL® or DirectX®. The methods are easy to implement and compatible with standard depth value calculations.


Parameterization of Generalized PrimalDual Triangulations
Pooran Memari, Patrick Mullen, and Mathieu Desbrun.
International Meshing Roundtable, 2011.
Abstract:
Motivated by practical numerical issues in a number of modeling and simulation
problems, we introduce the notion of a compatible dual complex to a
primal triangulation, such that a simplicial mesh and its compatible dual complex
(made out of convex cells) form what we call a primaldual triangulation.
Using algebraic and computational geometry results, we show that compatible
dual complexes exist only for a particular type of triangulation known as
weakly regular. We also demonstrate that the entire space of primaldual triangulations,
which extends the well known (weighted) Delaunay/Voronoi duality,
has a convenient, geometric parametrization. We finally discuss how this
parametrization may play an important role in discrete optimization problems
such as optimal mesh generation, as it allows us to easily explore the space of
primaldual structures along with some important subspaces.


Geometric, Variational Discretization of Continuum Theories
Evan Gawlik, Patrick Mullen, Dmitry Pavlov, Jerrold E. Marsden, and Mathieu Desbrun.
Physica D: Nonlinear Phenomena, 240(21), 17241760, 2011.
Abstract:
This study derives geometric, variational discretizations of continuum theories arising in fluid dynamics, magnetohydrodynamics (MHD), and the dynamics of complex fluids. A central role in these discretizations is played by the geometric formulation of fluid dynamics, which views solutions to the governing equations for perfect fluid flow as geodesics on the group of volumepreserving diffeomorphisms of the fluid domain. Inspired by this framework, we construct a finitedimensional approximation to the diffeomorphism group and its Lie algebra, thereby permitting a variational temporal discretization of geodesics on the spatially discretized diffeomorphism group. The extension to MHD and complex fluid flow is then made through an appeal to the theory of EulerPoincaré systems with advection, which provides a generalization of the variational formulation of ideal fluid flow to fluids with one or more advected parameters. Upon deriving a family of structured integrators for these systems, we test their performance via a numerical implementation of the update schemes on a cartesian grid. Among the hallmarks of these new numerical methods are exact preservation of momenta arising from symmetries, automatic satisfaction of solenoidal constraints on vector fields, good longterm energy behavior, robustness with respect to the spatial and temporal resolution of the discretization, and applicability to irregular meshes.


An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes
Fernando de Goes, David CohenSteiner, Pierre Alliez, and Mathieu Desbrun.
Symposium on Geometry Processing, 2011.
Abstract:
We propose a robust 2D shape reconstruction and simplification algorithm which takes as input a defect
laden point set with noise and outliers. We introduce an optimaltransport driven approach where the
input point set, considered as a sum of Dirac measures, is approximated by a simplicial complex
considered as a sum of uniform measures on 0 and 1simplices. A finetocoarse scheme is devised
to construct the resulting simplicial complex through greedy decimation of a Delaunay triangulation of
the input point set. Our method performs well on a variety of examples ranging from line drawings to
grayscale images, with or without noise, features, and boundaries.


HOT: HodgeOptimized Triangulations
Patrick Mullen, Pooran Memari, Fernando de Goes, Mathieu Desbrun.
Transactions on Graphics (SIGGRAPH) 2011.
Abstract:
We introduce Hodgeoptimized triangulations (HOT), a family of wellshaped primaldual pairs of complexes designed for fast and accurate computations in computer graphics. Previous work most commonly employs barycentric or circumcentric duals; while barycentric duals guarantee that the dual of each simplex lies within the simplex, circumcentric duals are often preferred due to the induced orthogonality between primal and dual complexes. We instead promote the use of weighted duals (power diagrams). They allow greater flexibility in the location of
dual vertices while keeping primaldual orthogonality, thus providing a valuable extension to the usual choices of dual by only adding one additional scalar per primal vertex. Furthermore, we introduce a family of functionals on pairs of complexes that we derive from bounds on the errors induced by diagonal Hodge stars, commonly used in discrete computations. The minimizers of these functionals, called HOT meshes, are shown to be generalizations of Centroidal Voronoi Tesselations and Optimal Delaunay Triangulations, and to provide increased accuracy and flexibility for a variety of computational purposes.


Exoskeleton: Curve Network Abstraction for 3D Shapes
F. de Goes, S. Goldenstein, M. Desbrun, L. Velho.
Computer & Graphics, 35(1), February 2011, 112121.
Abstract:
In this paper, we introduce the concept of an exoskeleton as a new abstraction of arbitrary shapes that succinctly conveys both
the perceptual and the geometric structure of a 3D model. We extract exoskeletons via a principled framework that combines
segmentation and shape approximation. Our method starts from a segmentation of the shape into perceptually relevant parts and
then constructs the exoskeleton using a novel extension of the Variational Shape Approximation method. Benefits of the exoskeleton abstraction to graphics applications such as simplification and chartification are presented.


Discrete Lie Advection of Differential Forms
P. Mullen, A. McKenzie, D. Pavlov, L. Durant, Y. Tong, E. Kanso, J. E. Marsden, and M. Desbrun.
FoCM (Foundations of Computational Mathematics), in press, 2010.
Abstract:
In this paper, we present a numerical technique for performing Lie advection of arbitrary differential forms. Leveraging advances in highresolution finite volume methods for scalar hyperbolic conservation laws, we first discretize the interior product (also called~\emph{contraction}) through integrals over Eulerian approximations of extrusions. This, along with Cartan's homotopy formula and a discrete exterior derivative, can then be used to derive a discrete Lie derivative. The usefulness of this operator is demonstrated through the numerical advection of scalar fields and 1forms on regular grids.


Interactive Shape Interpolation through Controllable Dynamic Deformation
J. Huang, Y. Tong, K. Zhou, H. Bao and M. Desbrun.
To appear in Transactions on Visualization and Computer Graphics, 2010.
Abstract:
In this paper, we introduce an interactive approach to generate physicallybased shape interpolation between poses. We extend linear modal analysis to offer an efficient and robust numerical technique to generate physicallyplausible dynamics even for very large deformation. Our method also provides a rich set of intuitive editing tools with realtime feedback, including control over vibration frequencies, amplitudes, and damping of the resulting interpolation sequence. We demonstrate the versatility of our approach through a series of complex dynamic shape interpolations.


Trivial Connections on Discrete Surfaces
K. Crane, M. Desbrun, and P.Schröder.
Symposium on Geometry Processing (Computer Graphics Forum), 2010.
(see also Keenan's project page for code and pictures; SGP Best Paper award)
Abstract:
This paper presents a straightforward algorithm for constructing connections on discrete surfaces that are as smooth as possible everywhere but on a set of isolated singularities with given index. We compute these connections by solving a single linear system built from standard operators. The solution can be used to design rotationally symmetric direction fields with userspecified singularities and directional constraints.


Signing the Unsigned: Robust Surface Reconstruction from Raw Pointsets
P. Mullen, F. de Goes, M. Desbrun, D. CohenSteiner, and P. Alliez.
Symposium on Geometry Processing (to appear in Computer Graphics Forum), 2010.
Abstract:
We propose a modular framework for robust 3D reconstruction from unorganized, unoriented, noisy, and outlierridden
geometric data. We gain robustness and scalability over previous methods through an unsigned distance
approximation to the input data followed by a global stochastic signing of the function. An isosurface reconstruction
is finally deduced via a sparse linear solve. We show with experiments on large, raw, geometric datasets that
this approach is scalable while robust to noise, outliers, and holes. The modularity of our approach facilitates
customization of the pipeline components to exploit specific idiosyncracies of datasets, while the simplicity of each
component leads to a straightforward implementation.


StructurePreserving Discretization of Incompressible Fluids
D. Pavlov, P. Mullen, Y. Tong, E. Kanso, J. E. Marsden, and M. Desbrun.
Physica D: Nonlinear Phenomena
Volume 240, Issue 6, 1 March 2011, Pages 443458.
Abstract:
The geometric nature of Euler fluids has been clearly identified and extensively studied over the years, culminating with Lagrangian and Hamiltonian descriptions of fluid dynamics where the configuration space is defined as the volumepreserving diffeomorphisms, and Kelvin's circulation theorem is viewed as a consequence of Noether's theorem associated with the particle relabeling symmetry of fluid mechanics. However computational approaches to fluid mechanics have been largely derived from a numericalanalytic point of view, and are rarely designed with structure preservation in mind, and often suffer from spurious numerical artifacts such as energy and circulation drift. In contrast, this paper geometrically derives discrete equations of motion for fluid dynamics from first principles in a purely Eulerian form. Our approach approximates the group of volumepreserving diffeomorphisms using a finite dimensional Lie group, and associated discrete Euler equations are derived from a variational principle with nonholonomic constraints. The resulting discrete equations of motion yield a structurepreserving time integrator with good longterm energy behavior and for which an exact discrete Kelvin's circulation theorem holds.


Deformation Transfer to MultiComponent Objects
Kun Zhou, Weiwei Xu, Yiying Tong, and Mathieu Desbrun.
Proceedings of Eurographics 2010. (movie)
Abstract:
We present a simple and effective algorithm to transfer deformation between surface meshes with multiple components.
The algorithm automatically computes spatial relationships between components of the target object, builds
correspondences between source and target, and finally transfers deformation of the source onto the target while
preserving cohesion between the target’s components. We demonstrate the versatility of our approach on various complex models.


Height and Tilt Geometric Texture
Vedrana Andersen, Mathieu Desbrun, J. Andreas Bærentzen, and Henrik Aanæs.
Internation Symposium on Visual Computing 2009.
Lecture Notes in Computer Science, SpringerVerlag.
Abstract:
We propose a new intrinsic representation of geometric texture over triangle meshes. Our approach extends the conventional height
field texture representation by incorporating displacements in the tangential plane in the form of a normal tilt. This texture representation
offers a good practical compromise between functionality and simplicity: it can efficiently handle and process geometric texture too complex to be represented as a height field, without having recourse to full blown mesh editing algorithms. The heightandtilt representation proposed here is fully intrinsic to the mesh, making texture editing and animation (such as bending or waving) intuitively controllable over arbitrary base mesh. We also provide simple methods for texture extraction and transfer using our heightandfield representation.


Energypreserving Integrators for Fluid Animation (corrected version; the pseudocode was missing a term)
Patrick Mullen, Keenan Crane, Dmitry Pavlov, Yiying Tong, and Mathieu Desbrun.
ACM Transactions on Graphics (SIGGRAPH), 28(3), 2009.
Abstract:
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 adaptivetime 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 timereversible 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 energypreserving HarlowWelch / Crank
Nicolson scheme to simplicial grids.


Numerical Coarsening of Inhomogeneous Elastic Materials
Lily Kharevych, Patrick Mullen, Houman Owhadi, and Mathieu Desbrun.
ACM Transactions on Graphics (SIGGRAPH), 28(3), 2009.
Abstract:
We propose an approach for efficiently simulating elastic objects
made of nonhomogeneous, nonisotropic 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 dynamicallysimilar
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 with
a numericallycoarsened model made of a few mesh elements.


Interleaving Delaunay Refinement and Optimization
for Practical Isotropic Tetrahedron Mesh Generation
Jane Tournois, Camille Wormser, Pierre Alliez, and Mathieu Desbrun.
ACM Transactions on Graphics (SIGGRAPH), 28(3), 2009.
Abstract:
We present a practical approach to isotropic tetrahedral meshing of
3D domains bounded by piecewise smooth surfaces. Building upon
recent theoretical and practical advances, our algorithm interleaves
Delaunay refinement and mesh optimization to generate quality
meshes that satisfy a set of userdefined criteria. This interleaving is
shown to be more conservative in number of Steiner point insertions
than refinement alone, and to produce higher quality meshes than
optimization alone. A careful treatment of boundaries and their
features is presented, offering a versatile framework for designing
smoothly graded tetrahedral meshes.


Lie Group Integrators for Animation and Control of Vehicles
Marin Kobilarov, Keenan Crane, and Mathieu Desbrun.
To appear in ACM Transactions on Graphics, 2009.
(see also Keenan's project page for movies).
Abstract:
This paper is concerned with the animation and control of vehicles with complex dynamics such as helicopters, boats, and cars. Motivated by recent developments in discrete geometric mechanics we develop a general framework for integrating the dynamics of holonomic and nonholonomic vehicles by preserving their statespace geometry and motion invariants. We demonstrate that the resulting integration schemes are superior to standard methods in numerical robustness and efficiency, and can be applied to many types of vehicles. In addition, we show how to use this framework in an optimal control setting to automatically compute accurate and realistic motions for arbitrary userspecified constraints.


Variational Integrators for Maxwell's Equations with Sources
Ari Stern, Yiying Tong, Mathieu Desbrun, and Jerrold E. Marsden.
In Progress in Electromagnetics Research Symposium (PIERS), Vol. 4, No. 7, 711715, 2008.
Abstract:
In recent years, two important techniques for geometric numerical discretization
have been developed. In computational electromagnetics, spatial discretization has been
improved by the use of mixed finite elements and discrete differential forms. Simultaneously, the
dynamical systems and mechanics communities have developed structurepreserving time
integrators, notably variational integrators that are constructed from a Lagrangian action principle.
Here, we discuss how to combine these two frameworks to develop variational spacetime
integrators for Maxwell's equations. Extending our previous work, we also show here how to incorporate
free sources of charge and current.


Spectral Conformal Parameterization
Patrick Mullen, Yiying Tong, Pierre Alliez, Mathieu Desbrun.
Symposium of Geometry Processing, 2008.
Abstract:
We present a spectral approach to automatically and efficiently obtain discrete freeboundary conformal parameterizations of triangle mesh patches, without the common artifacts due to positional constraints on vertices and without undue bias introduced by sampling irregularity. Highquality 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.


Voronoibased Variational Reconstruction of Unoriented Point Sets
Pierre Alliez, David CohenSteiner, Yiying Tong, and Mathieu Desbrun.
Symposium on Geometry Processing, pp. 3948, 2007.
Abstract:
We introduce an algorithm for reconstructing watertight surfaces from unoriented point sets. Using the Voronoi diagram of the input point set, we deduce a tensor field whose principal axes and eccentricities locally represent respectively the most likely direction of the normal to the surface, and the confidence in this direction estimation. An implicit function is then computed by solving a generalized eigenvalue problem such that its gradient is most aligned with the principal axes of the tensor field, providing a bestfitting isosurface reconstruction. Our approach possesses a number of distinguishing features. In particular, the implicit function optimization provides resilience to noise, adjustable fitting to the data, and controllable smoothness of the reconstructed surface. Finally, the use of simplicial meshes (possibly restricted to a thin crust around the input data) and (an)isotropic Laplace operators renders the numerical treatment simple and robust.


Generalized Surface Flows for Deformable Registration and Cortical Matching
Ilya Eckstein, Anand A. Joshi, C.C. Jay Kuo, Richard Leahy, and Mathieu Desbrun.
Proceedings of MICCAI, 2007.
Abstract:
Despite being routinely required in medical applications, deformable surface registration is notoriously difficult due to large intersubject variability and complex geometry of most medical datasets. We present a general and flexible deformable matching framework based on generalized surface flows that efficiently tackles these issues through tailored deformation priors and multiresolution computations. The value of our approach over existing methods is demonstrated for automatic and userguided cortical registration.


Generalized Surface Flows for Mesh Processing
Ilya Eckstein, JeanPhilippe Pons, Yiying Tong, C.C. Jay Kuo, and Mathieu Desbrun.
Symposium on Geometry Processing, pp. 183192 2007.
Abstract:
Geometric flows are ubiquitous in mesh processing.
Curve and surface evolutions based on functional minimization
have been used in the context of surface diffusion, denoising,
shape optimization, minimal surfaces, and geodesic
paths to mention a few. Such gradient flows are nearly always,
yet often implicitly, based on the canonical L2
inner product of vector fields. In this paper, we point out that
changing this inner product provides a simple,
powerful, and untapped approach to extend current flows. We
demonstrate the value of such a norm alteration
for regularization and volumepreservation purposes and in the
context of shape matching, where deformation
priors (ranging from rigid motion to articulated motion) can be
incorporated into a gradient flow to drastically
improve results. Implementation details, including a differentiable
approximation of the Hausdorff distance between
irregular meshes, are presented.


A Discrete Geometric Optimal Control Framework for Systems with Symmetries
Marin Kobilarov, Mathieu Desbrun, Jerrold E. Marsden, and Gaurav S. Sukhatme.
Proceedings of Robotics: Science and Systems, 2007.
Abstract:
This paper studies the optimal motion control of
mechanical systems through a discrete geometric approach. At
the core of our formulation is a discrete Lagranged’AlembertPontryagin
variational principle, from which are derived discrete
equations of motion that serve as constraints in our optimization
framework. We apply this discrete mechanical approach to
holonomic systems with symmetries and, as a result, geometric
structure and motion invariants are preserved. We illustrate our
method by computing optimal trajectories for a simple model of
an air vehicle flying through a digital terrain elevation.


Design of Tangent Vector Fields (version with no movies here)
Matthew Fisher, Peter Schröder, Mathieu Desbrun, and Hugues Hoppe.
ACM Trans. on Graphics (SIGGRAPH) 26(3), art. 56, 2007.
Abstract:
Tangent vector fields are an essential ingredient in controlling
surface appearance for applications ranging from anisotropic
shading to texture synthesis and nonphotorealistic rendering. To
achieve a desired effect one is typically interested in smoothly
varying fields that satisfy a sparse set of userprovided constraints.
Using tools from Discrete Exterior Calculus, we present a simple
and efficient algorithm for designing such fields over arbitrary
triangle meshes. By representing the field as scalars over mesh
edges (i.e., discrete 1forms), we obtain an intrinsic, coordinatefree
formulation in which field smoothness is enforced through
discrete Laplace operators. Unlike previous methods, such a formulation
leads to a linear system whose sparsity permits efficient
prefactorization. Constraints are incorporated through weighted
least squares and can be updated rapidly enough to enable interactive
design, as we demonstrate in the context of anisotropic
texture synthesis.


Mesh Puppetry: Cascading Optimization of Mesh Deformation with Inverse Kinematics
Xiaohan Shi, Kun Zhou, Yiying Tong, Mathieu Desbrun, Hujun Bao, and Baining Guo.
ACM Trans. on Graphics (SIGGRAPH) 26(3), art. 81, 2007. (movie)
Abstract:
We present mesh puppetry, a variational framework for detailpreserving
mesh manipulation through a set of highlevel, intuitive,
and interactive design tools. Our approach builds upon traditional
rigging by optimizing skeleton position and vertex weights in an
integrated manner. New poses and animations are created by specifying
a few desired constraints on vertex positions, balance of the
character, length and rigidity preservation, joint limits, and/or
selfcollision avoidance. Our algorithm then adjusts the skeleton and
solves for the deformed mesh simultaneously through a novel cascading
optimization procedure, allowing realtime manipulation of
meshes with 50K+ vertices for fast design of pleasing and realistic
poses. We demonstrate the potential of our framework through an
interactive deformation platform and various applications such as
deformation transfer and motion retargeting.


A Variational Approach to Eulerian Geometry Processing
Patrick Mullen, Alexander McKenzie, Yiying Tong, and Mathieu Desbrun
ACM Trans. on Graphics (SIGGRAPH) 26(3), art. 66, 2007. (movie)
Abstract:
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
highgenus surfaces, weighted offsetting, foliation smoothing of
medical datasets, and incompressible fluid animation.


On the Geometric Character of Stress in Continuum Mechanics
Eva Kanso, Marino Arroyo, Yiying Tong, Arash Yavari, Jerrold E. Marsden, and Mathieu Desbrun
Z. angew. Math. Phys. 58 (2007) 1–14.
Abstract:
This paper shows that the stress field in the classical theory of continuum mechanics
may be taken to be a covectorvalued differential twoform. The balance laws and other fundamental
laws of continuum mechanics may be neatly rewritten in terms of this geometric stress. A
geometrically attractive and covariant derivation of the balance laws from the principle of energy
balance in terms of this stress is presented.


Unconstrained Spherical Parameterization
Ilja Friedel, Peter Schröder, and Mathieu Desbrun
Journal of Graphics Tools, 12(1), pp. 1726, 2007.
(see also: ACM SIGGRAPH Technical Sketch '05).
Abstract:
We introduce a novel approach for the construction of spherical
parameterizations based on energy minimization. The energies are
derived in a general manner from classic formulations well
known in the planar parameterization setting (e.g., conformal, Tutte,
area, stretch energies, etc), based on the following principles:
the energy should (1) be a measure of spherical triangles; (2) treat
energies independently of the triangle location on the sphere; and
(3) converge to the continuous energy \emph{from above} under
refinement. Based on these considerations we give a very simple
nonlinear modification of standard formulas that fulfills all these
requirements. The method avoids the usual collapse of flat
energies when they are transferred to the spherical setting without
additional constraints (e.g., fixing three or more vertices). Our
unconstrained energy minimization problem is amenable to the
use of standard solvers. Consequently the implementation effort is
minimal while still achieving excellent robustness and performance
through the use of widely available numerical minimization software.


Geometric, Variational Integrators for Computer Animation
L. Kharevych, Weiwei, Y. Tong, E. Kanso, J. E. Marsden, P. Schröder, and Mathieu Desbrun
ACM/EG Symposium on Computer Animation 2006, pp. 4351
Abstract:
We present a generalpurpose numerical scheme for time integration of Lagrangian dynamical systems—an important
computational tool at the core of most physicsbased animation techniques. Several features make this
particular time integrator highly desirable for computer animation: it numerically preserves important invariants,
such as linear and angular momenta; the symplectic nature of the integrator also guarantees a correct energy
behavior, even when dissipation and external forces are added; holonomic constraints can also be enforced quite
simply; finally, our simple methodology allows for the design of highorder accurate schemes if needed. Two key
properties set the method apart from earlier approaches. First, the nonlinear equations that must be solved during
an update step are replaced by a minimization of a novel functional, speeding up time stepping by more than a
factor of two in practice. Second, the formulation introduces additional variables that provide key flexibility in the
implementation of the method. These properties are achieved using a discrete form of a general variational principle
called the PontryaginHamilton principle, expressing time integration in a discrete geometric manner analog
in spirit to geometric modeling techniques to design smooth curves or surfaces. We demonstrate the applicability
of our integrators to the simulation of nonlinear elasticity with implementation details.


Designing Quadrangulations with Discrete Harmonic Forms
Yiying Tong, Pierre Alliez, David CohenSteiner, and Mathieu Desbrun
ACM/EG Symposium on Geometry Processing 2006, pp. 201210
Abstract:
We introduce a framework for quadrangle meshing of discrete
manifolds. Based on discrete differential forms, our method
hinges on extending the discrete Laplacian operator (used
extensively in modeling and animation) to allow for line
singularities and singularities with fractional indices. When
assembled into a singularity graph, these line singularities are
shown to considerably increase the design flexibility of quad
meshing. In particular, control over edge alignments and mesh
sizing are unique features of our novel approach. Another appeal
of our method is its robustness and scalability from a numerical
viewpoint: we simply solve a sparse linear system to generate
a pair of piecewisesmooth scalar fields whose isocontours form a
pure quadrangle tiling, with no Tjunctions.


Stable, CirculationPreserving, Simplicial Fluids
Sharif Elcott, Yiying Tong, Eva Kanso, Peter Schröder, and Mathieu Desbrun
ACM Transactions on Graphics, 26(1), art. 4, Jan. 2007.(movie)
Abstract:
Visual quality, low computational cost, and numerical stability are foremost goals in computer
animation. An important ingredient in achieving these goals is the conservation of fundamental
motion invariants. For example, rigid and deformable body simulation benefits greatly from
conservation of linear and angular momenta. In the case of fluids, however, none of the current
techniques focuses on conserving invariants, and consequently, they often introduce a visually
disturbing numerical diffusion of vorticity. Visually just as important is the resolution of complex
simulation domains. Doing so with regular (even if adaptive) grid techniques can be computationally
delicate. In this paper, we propose a novel technique for the simulation of fluid flows.
It is designed to respect the defining differential properties, i.e., the conservation of circulation
along arbitrary loops as they are transported by the flow. Consequently, our method offers several
new and desirable properties: arbitrary simplicial meshes (triangles in 2D, tetrahedra in 3D) can
be used to define the fluid domain; the computations involved in the update procedure are efficient
due to discrete operators with small support; and it preserves discrete circulation avoiding
numerical diffusion of vorticity.


Discrete Differential Forms for Computational Modeling
Mathieu Desbrun, Eva Kanso, and Yiying Tong
Chapter in ACM SIGGRAPH'05 and '06 Course
Notes on Discrete Differential Geometry (revised)
Abstract:
The emergence of computers as an essential tool in scientific research
has shaken the very foundations of differential modeling.
Indeed, the deeplyrooted abstraction of smoothness, or differentiability,
seems to inherently clash with a computer’s ability of storing
only finite sets of numbers. While there has been a series of computational
techniques that proposed discretizations of differential
equations, the geometric structures they are supposed to simulate
are often lost in the process.


Edge Subdivision Schemes and the Construction of Smooth Vector Fields
Ke Wang, Weiwei, Yiying Tong, Mathieu Desbrun, and Peter Schröder
ACM Trans. on Graphics (SIGGRAPH '06), 25(3), pp. 10411048
Abstract:
Vertex and facebased subdivision schemes are now routinely
used in geometric modeling and computational science, and
their primal/dual relationships are well studied. In this paper,
we interpret these schemes as defining bases for discrete differential
0 resp. 2forms, and complete the picture by introducing
edgebased subdivision schemes to construct the missing bases
for discrete differential 1forms. Such subdivision schemes map
scalar coefficients on edges from the coarse to the refined mesh
and are intrinsic to the surface. Our construction is based on
treating vertex, edge, and facebased subdivision schemes as
a joint triple and enforcing that subdivision commutes with the
topological exterior derivative. We demonstrate our construction
for the case of arbitrary topology triangle meshes. Using
Loop’s scheme for 0forms and generalized halfbox splines for 2
forms results in a unique generalized spline scheme for 1forms,
easily incorporated into standard subdivision surface codes. We
also provide corresponding boundary stencils. Once a metric is
supplied, the scalar 1form coefficients define a smooth tangent
vector field on the underlying subdivision surface. Design of tangent
vector fields is made particularly easy with this machinery
as we demonstrate.


Mesh Quilting For Geometric Texture Synthesis
K. Zhou, X. Huang, X. Wang, Y. Tong, M. Desbrun, B. Guo, H.Y. Sheum
In ACM Trans. on Graphics (SIGGRAPH '06). 25(3), pp. 690697
Abstract:
We introduce mesh quilting, a geometric texture synthesis algorithm
in which a 3D texture sample given in the form of a triangle
mesh is seamlessly applied inside a thin shell around an arbitrary
surface through local stitching and deformation. We show that
such geometric textures allow interactive and versatile editing and
animation, producing compelling visual effects that are difficult to
achieve with traditional texturing methods. Unlike pixelbased image
quilting, mesh quilting is based on stitching together 3D geometry
elements. Our quilting algorithm finds corresponding geometry
elements in adjacent texture patches, aligns elements through
local deformation, and merges elements to seamlessly connect texture
patches. For mesh quilting on curved surfaces, a critical issue
is to reduce distortion of geometry elements inside the 3D space of
the thin shell. To address this problem we introduce a lowdistortion
parameterization of the shell space so that geometry elements can
be synthesized even on very curved objects without the visual distortion
present in previous approaches. We demonstrate how mesh
quilting can be used to generate convincing decorations for a wide
range of geometric textures.


Discrete Geometric Mechanics for Variational Integrators (A Primer for CS)
Ari Stern, and Mathieu Desbrun
Chapter in ACM SIGGRAPH'06 Course
Notes on Discrete Differential Geometry
Abstract:
In this chapter, we present a geometricinstead of a
traditional numericalanalyticapproach to the problem of time
integration. Geometry at its most abstract is the study of
symmetries and their associated invariants. Variational approaches
based on such notions are commonly used in geometric modeling and
discrete differential geometry. Here we will treat mechanics in a
similar way. Indeed, the very essence of a mechanical system is
characterized by its symmetries and invariants. Thus
preserving these symmetries and invariants (e.g., certain momenta)
into the discrete computational setting is of paramount importance
if one wants discrete time integration to properly capture the
underlying continuous motion. Motivated by the wellknown
variational and geometric nature of most dynamical systems, we
review the use of discrete variational principles as a way to
derive robust, and accurate time integrators.


Compression of Time Varying Isosurfaces
Ilya Eckstein, Mathieu Desbrun, and C.C. Jay Kuo
In Graphics Interface '06, pp. 99105
Abstract:
Compressing sequences of complex timevarying surfaces as generated
by medical instrumentations or complex physical simulations
can be extremely challenging: repeated topology changes during
the surface evolution render most of the previous techniques for
compression of timevarying surfaces inefficient or impractical. In
order to provide a viable solution, we propose a new approach based
upon an existing isosurface compression technique designed for static
surfaces. We exploit temporal coherence of the data by adopting
the paradigm of blockbased motion prediction developed in video
coding and extending it using local surface registration. The resulting
prediction errors across frames are treated as a static isosurface
and encoded progressively using an adaptive octreebased scheme.
We also exploit local spatiotemporal patterns through contextbased
arithmetic coding. Finegrain geometric residuals are encoded separately
with userspecified precision. The other design choices
made to handle large datasets are detailed.


Discrete Differential Geometry: An Applied Introduction
Eitan Grinspun, Peter Schröder, and Mathieu Desbrun
ACM SIGGRAPH'05 Course Notes (see also: DDG Forum).
Slides: Calculus on Meshes,
Discrete Differential Fluids, and
Meshing
Abstract:
This volume documents the full day course Discrete Differential Geometry: An Applied Introduction presented
at SIGGRAPH ’05 on July 31st, 2005. These notes supplement the lectures given by Mathieu Desbrun,
Eitan Grinspun, and Peter Schr¨oder, compiling contributions from: Pierre Alliez, Alexander Bobenko,
David CohenSteiner, Sharif Elcott, Eva Kanso, Liliya Kharevych, Adrian Secord, John M. Sullivan, Yiying
Tong, Mariette Yvinec.


Variational Tetrahedral Meshing
Pierre Alliez, David CohenSteiner, Mariette Yvinec,
and Mathieu Desbrun
ACM Trans. on Graphics (SIGGRAPH '05), 24(3), pp. 617625
Abstract:
In this paper, a novel Delaunaybased variational approach to
isotropic tetrahedral meshing is presented. To achieve both robustness
and efficiency, we minimize a simple meshdependent energy
through global updates of both vertex positions and connectivity.
As this energy is known to be the L1 distance between an isotropic
quadratic function and its linear interpolation on the mesh, our minimization
procedure generates wellshaped tetrahedra. Mesh design
is controlled through a gradation smoothness parameter and selection
of the desired number of vertices. We provide the foundations
of our approach by explaining both the underlying variational principle
and its geometric interpretation. We demonstrate the quality
of the resulting meshes through a series of examples.


TextureMontage: Seamless Texturing of Surfaces From Multiple Images
Kun Zhou, Xi Wang, Yiying Tong,
Mathieu Desbrun, Baining Guo, and H.Y. Shum
ACM Trans. on Graphics (SIGGRAPH '05), 24(3), pp. 11481155.
Abstract:
We propose a technique, called TextureMontage, to seamlessly map
a patchwork of texture images onto an arbitrary 3D model. A texture
atlas can be created through the specification of a set of correspondences
between the model and any number of texture images.
First, our technique automatically partitions the mesh and the images,
driven solely by the choice of feature correspondences. Most
charts will then be parameterized over their corresponding image
planes through the minimization of a distortion metric based on
both geometric distortion and texture mismatch across patch boundaries
and images. Lastly, a surface texture inpainting technique is
used to fill in the remaining charts of the surface with no corresponding
texture patches. The resulting texture mapping satisfies
the (sparse or dense) userspecified constraints while minimizing
the distortion of the texture images and ensuring a smooth transition
across the boundaries of different mesh patches.


Barycentric Coordinates for Convex Sets
Joe Warren, Scott Schaefer, Anil Hirani,
and Mathieu Desbrun
Advances in Computational Mathematics 27(3) (2007), 319338.
Abstract:
Convex Sets
Barycentric coordinates are one of the most basic mathematical tools in graphics,
as well as in many computational sciences. Although the formulas for simplices
(triangles, tetrahedra and so on) are widely known and
routinely used, there has been no satisfactory extension of these to arbitrary convex
polytopes despite a plethora of potential applications. In this paper, we propose a
simple, computationally convenient formula of a canonical form of barycentric coordinates.
These functions are rational, smooth and of low degree. Next, we extend
the formulas for convex polytopes to smooth, convex functions. Finally, we
present an application of barycentric coordinates to freeform deformation.


A Geometric Construction of
Coordinates for Convex Polyhedra using Polar Duals
Tao Ju, Scott Schaefer, Joe Warren, and Mathieu Desbrun
ACM SIGGRAPH/EG Symposium of Geometry Processing 2005, pp. 181186.
Abstract:
A fundamental problem in geometry processing is that of expressing a point inside a convex polyhedron as a
combination of the vertices of the polyhedron. Instances of this problem arise often in mesh parameterization and
3D deformation. A related problem is to express a vector lying in a convex cone as a nonnegative combination
of edge rays of this cone. This problem also arises in many applications such as planar graph embedding and
spherical parameterization. In this paper, we present a unified geometric construction for building these weighted
combinations using the notion of polar duals. We show that our method yields a simple geometric construction
for Wachspress’s barycentric coordinates, as well as for constructing Colin de Verdière matrices from convex
polyhedra—a critical step in Lovasz’s method with applications to parameterizations.


Vector Field Analysis and Visualization through Variational Clustering
Alexander McKenzie, Santiago Lombeyda, Mathieu Desbrun
EG  IEEE VGTC Symposium on Visualization (2005), 1–7.
Abstract:
Scientific computing is an increasingly crucial component of research in various disciplines. Despite its potential,
exploration of the results is an often laborious task, owing to excessively large and verbose datasets output by these simulation runs. Several approaches have been proposed to analyze, classify, and simplify such data to facilitate
an informative visualization and deeper understanding of the underlying system. However, traditional methods
leave much room for improvement. In this article we investigate the visualization of large vector fields, departing
from accustomed processing algorithms by casting vector field simplification as a variational partitioning problem.
Adopting an iterative strategy, we introduce the notion of vector “proxies” to minimize the distortion error of our
simplification by clustering the dataset into multiple bestfitting characteristic regions. This error driven
approach can be performed with respect to various similarity metrics, offering a convenient set of tools to design
clear and succinct representations of high dimensional datasets. We illustrate the benefits of such tools through
visualization experiments of threedimensional vector fields.


Discrete Poincaré Lemma
Mathieu Desbrun, Melvin Leok, Jerrold E. Marsden
Applied Numerical Mathematics 53 (2005) 231–248.
Abstract:
This paper proves a discrete analogue of the Poincaré lemma in the context of a discrete exterior calculus based
on simplicial cochains. The proof requires the construction of a generalized cone operator as the geometric cone of a simplex cannot, in general, be interpreted as a chain in the simplicial complex. The
corresponding cocone operatorcan be shown to be a homotopy operator, and this yields
the discrete Poincaré lemma. The generalized cone operator is a combinatorial operator that can be
constructed for any simplicial complex that can be grown by a process of local augmentation.
In particular, regular triangulations and tetrahedralizations in R^2 and R^3 are presented, for which
the discrete Poincaré lemma is globally valid.


Geodesicsbased OnetoOne Parameterization of 3D Triangle Meshes
Haeyoung Lee, Yiying Tong, and Mathieu Desbrun
IEEE Multimedia journal, Volume 12,
Issue 1, Jan.March 2005, 2733.
Abstract:
Digital geometry is a new data type for multimedia applications. To
foster the use of 3D geometry, we introduce a piecewise linear
parameterization of 3D surfaces that we can use for texture mapping, morphing,
remeshing, and geometry imaging. Our method
guarantees onetoone mapping without foldovers in
a geometrically intuitive way.


A HapticRendering
Technique Based on Hybrid Surface Representation
Laehyun Kim, Gaurav Sukhatme, and Mathieu Desbrun
IEEE Computer Graphics and Applications
Volume 24, Number 2, March/April 2004, 6675.
Abstract:
Our novel haptic rendering technique using a hybrid surface representation
addresses conventional limitations in haptic displays.


Removing Excess Topology From Isosurfaces
Zoë Wood, Hugues
Hoppe, Mathieu Desbrun and Peter Schröder
ACM Trans. on Graphics, 23(2), pp. 190  203, April 2004
Abstract:
Many highresolution surfaces are created through isosurface extraction from volumetric representations, obtained by 3D photography, CT, or MRI. Noise inherent in the acquisition process can lead to geometrical and topological errors. Reducing geometrical errors during reconstruction is well studied. However, isosurfaces often contain many topological errors in the form of tiny handles. These nearly invisible artifacts hinder subsequent operations like mesh simplification, remeshing, and parametrization. In this article we present a practical method for removing handles in an isosurface. Our algorithm makes an axisaligned sweep through the volume to locate handles, compute their sizes, and selectively remove them. The algorithm is designed to facilitate outofcore execution. It finds the handles by incrementally constructing and analyzing a Reeb graph. The size of a handle is measured by a short nonseparating cycle. Handles are removed robustly by modifying the volume rather than attempting “mesh surgery.” Finally, the volumetric modifications are spatially localized to preserve geometrical detail. We demonstrate topology simplification on several complex models, and show its benefits for subsequent surface processing.


Variational Shape Approximation
David CohenSteiner, Pierre Alliez,
and Mathieu Desbrun
ACM Trans. of Graphics (SIGGRAPH '04).
Abstract:
Achieving efficiency in mesh processing often demands that overly
verbose 3D datasets be reduced to more concise, yet faithful representations.
Despite numerous applications ranging from geometry
compression to reverse engineering, concisely capturing the geometry
of a surface remains a tedious task. In this paper, we present
both theoretical and practical contributions that result in a novel and
versatile framework for geometric approximation of surfaces. We
depart from the usual strategy by casting shape approximation as
a variational geometric partitioning problem. Using the concept of
geometric proxies, we drive the distortion error down through repeated
clustering of faces into bestfitting regions. Our approach is
entirely discrete and errordriven, and does not require parameterization
or local estimations of differential quantities. We also introduce
a new metric based on normal deviation, and demonstrate its
superior behavior at capturing anisotropy.


Discrete Exterior Calculus for Variational Problems in Computer Graphics and Vision
Mathieu Desbrun, Anil Hirani,
and Jerrold E. Marsden
In the 42nd IEEE Conference on Decision and Control Proceedings (CDC '03), 42, 49024907.
Abstract:
This paper demonstrates how discrete exterior
calculus tools may be useful in computer vision and graphics.
A variational approach provides a link with mechanics. [This is an invited paper, gathering different pieces of work already published]


Interactive Extraction of HighFrequency AestheticallyCoherent Colormaps
Santiago V. Lombeyda and Mathieu Desbrun
Technical report, Caltech, 2003.
Abstract:
Color transfer functions (i.e. colormaps) exhibiting a high
frequency luminosity component have proven to be useful in the
visualization of data where feature detection or isocontours
recognition is essential. Having these colormaps also display a
wide range of color and an aesthetically pleasing composition
holds the potential to further aid image understanding and
analysis. However producing such colormaps in an efficient
manner with current colormap creation tools is difficult. We
hereby demonstrate an interactive technique for extracting
colormaps from artwork and pictures. We show how the rich and
careful color design and dynamic luminance range of an existing
image can be gracefully captured in a colormap and be utilized
effectively in the exploration of complex datasets.


Discrete Shells
Eitan Grinspun, Anil Hirani,
Mathieu Desbrun and Peter Schröder
In ACM/Eurographics Symposium of Computer Animation 2003
Abstract:
In this paper we introduce a discrete shell model describing the behavior of thin flexible structures, such as hats, leaves, and aluminum cans, which are characterized by a curved undeformed configuration. Previously such
models required complex continuum mechanics formulations and correspondingly complex algorithms. We show that a simple shell model can be derived geometrically for triangle meshes and implemented quickly by modifying a
standard cloth simulator. Our technique convincingly simulates a variety of curved objects with materials ranging from paper to metal, as we demonstrate with several examples including a comparison of a real and simulated falling hat.
Check out the videos on the Multires Group website


Learning Controls for Blend Shape Based Realistic Facial Animation
Pushkar Joshi, Wen Tien,
Mathieu Desbrun and Fred Pighin
In ACM/Eurographics Symposium of Computer Animation 2003
Abstract:
Blend shape animation is the method of choice for keyframe facial animation: a set of
blend shapes (key facial expressions) are used to define a linear space of facial expressions.
However, in order to capture a significant range of complexity of human expressions,
blend shapes need to be segmented into smaller regions where key
idiosyncracies of the face being animated are present. Performing this segmentation by hand
requires skill and a lot of time. In this paper, we propose an automatic, physicallymotivated
segmentation that learns the controls and parameters directly from the set of blend shapes.
We show the usefulness and efficiency of this technique for both,
motioncapture animation and keyframing. We also provide a rendering algorithm to enhance
the visual realism of a blend shape model.
Movies (divX):
Capture,
Result,
Editing1,
Editing2,
Editing3.


Anisotropic
Polygonal Remeshing
Pierre Alliez,
David CohenSteiner, Olivier Devillers, Bruno Lévy,
and Mathieu Desbrun
In ACM SIGGRAPH '03 / ACM TOG
Abstract:
In this paper, we propose a novel polygonal remeshing technique
that exploits a key aspect of surfaces: the intrinsic anisotropy of
natural or manmade geometry. In particular, we use curvature directions
to drive the remeshing process, mimicking the lines that
artists themselves would use when creating 3d models from scratch.
After extracting and smoothing the curvature tensor field of an input
geometry, lines of minimum and maximum curvatures are used to
determine adequate edges for the remeshed version in anisotropic
regions, while spherical regions are simply pointsampled since
there is no natural direction of symmetry locally. As a result our
technique generates polygon meshes mainly composed of quads
on anisotropic regions, and of triangles in spherical regions. Our
approach provides the flexibility to produce meshes ranging from
isotropic to anisotropic, from coarse to dense, and from uniform to
curvature adapted.


Noniterative,
FeaturePreserving Mesh Smoothing
Thouis R. Jones,
Frédo Durand, and Mathieu Desbrun
In ACM SIGGRAPH '03 / ACM TOG
Abstract:
With the increasing use of geometry scanners to create 3D models,
there is a rising need for fast and robust mesh smoothing to
remove inevitable noise in the measurements. While most previous
work has favored diffusionbased iterative techniques for featurepreserving
smoothing, we propose a radically different approach,
based on robust statistics and local firstorder predictors of the surface.
The robustness of our local estimates allows us to derive a
noniterative featurepreserving filtering technique applicable to arbitrary
"triangle soups". We demonstrate its simplicity of implementation
and its efficiency, which makes it an excellent solution
for smoothing large, noisy, and nonmanifold meshes.


Discrete
Multiscale Vector Field Decomposition
Yiying Tong, Santiago Lombeyda,
Anil Hirani, Mathieu Desbrun
In ACM SIGGRAPH '03 / ACM TOG
Abstract:
While 2D and 3D vector fields are ubiquitous in computational sciences,
their use in graphics is often limited to regular grids, where
computations are easily handled through finitedifference methods.
In this paper, we propose a set of simple and accurate tools for
the analysis of 3D discrete vector fields on arbitrary tetrahedral
grids. We introduce a variational, multiscale decomposition of vector
fields into three intuitive components: a divergencefree part, a
curlfree part, and a harmonic part. We show how our discrete approach
matches its wellknown smooth analog, called the HelmotzHodge
decomposition, and that the resulting computational tools
have very intuitive geometric interpretation. We demonstrate the
versatility of these tools in a series of applications, ranging from
data visualization to fluid and deformable object simulation.


Progressive
Encoding of Complex Isosurfaces
(see our executable)
Haeyoung Lee,
Mathieu Desbrun, and Peter Schröder
In ACM SIGGRAPH '03 / ACM TOG
Abstract:
We present a progressive encoding technique specifically designed
for complex isosurfaces. It achieves better rate distortion performance
than all standard mesh coders, and even improves on all previous single rate
isosurface coders. Our novel algorithm handles isosurfaces with or without
sharp features, and deals gracefully with high topologic and geometric
complexity. The inside/outside function of the volume data is
progressively transmitted through the use of an adaptive octree,
while a local frame based encoding is used for the fine level
placement of surface samples.
Local patterns in topology and local smoothness in geometry
are exploited by contextbased arithmetic encoding,
allowing us to achieve an average of 6.3 bits per vertex (b/v) at
very low distortion. Of this rate only 0.69 b/v are dedicated to
connectivity data: this improves by 18% over the best previous
single rate isosurface encoder.


Haptic Editing for Decoration and Material Properties
Laehyun Kim,
Gaurav S. Sukhatme and Mathieu Desbrun
Accepted in 11th Symposium on Haptic Interfaces for Virtual Environment and Teleoperator Systems, IEEE Computer Society, 2003
Abstract: In this paper, we explore haptic editing as a powerful way
to enhance haptic realism. Building upon the framework of a
previous implicitbased haptic technique, our haptic decoration
technique allows the user to first paint directly on 3D models,
and then to sense the thickness variation due to the added paint.
Meanwhile, material editing permits the user to edit and feel
local material properties such as friction and stiffness in a
natural way. In addition, we extended the initial haptic model to
support some novel features including a magnetic surface
attraction that forces the tool tip to stick to the surface of
complex models.


An
Implicitbased Haptic Rendering Technique (go to
the haptics page to download
library)
Laehyun Kim, Anna Kyrikou,
Gaurav S. Sukhatme and Mathieu Desbrun
In IEEE/RSJ IROS 2002 Proceedings
Abstract: We present a novel
haptic rendering technique. Building upon previous work, we propose a haptic
model based on a volumetric description of the geometry of an object. Unlike
previous volumetric approaches, we also find a virtual contact point on
the surface in order to derive a penalty force that is consistent with
the real geometry of the object, without introducing force discontinuity.
We also demonstrate that other surface properties such as friction and
texture can be added elegantly. The resulting technique is fast (1000 Hz
refresh rate) and can handle large geometry models on lowend computers.


Intrinsic
Parameterizations of Surface Meshes (here is a hindsight:
LSCM=DNCP)
Mathieu Desbrun, Mark
Meyer, and Pierre Alliez
In Eurographics 2002 Conference
Proceedings
Abstract: Parameterization
of discrete surfaces is a fundamental and widelyused operation in graphics,
required, for instance, for texture mapping or remeshing. As 3D data becomes
more and more detailed, there is an increased need for fast and robust
techniques to automatically compute leastdistorted parameterizations of
large meshes. In this paper, we present new theoretical and practical results
on the parameterization of triangulated surface patches. Given a few desirable
properties such as rotation and translation invariance, we show that the
only admissible parameterizations form a twodimensional set and each parameterization
in this set can be computed using a simple, sparse, linear system. Since
these parameterizations minimize the distortion of different intrinsic
measures of the original mesh, we call them Intrinsic Parameterizations.
In addition to the theoretical analysis, we propose robust, efficient and
tunable tools to obtain leastdistorted parameterizations automatically.
In particular, we give details on a novel, fast technique to provide an
optimal mapping without fixing any boundary conditions, thus providing
a unique Natural Intrinsic Parameterization. Other techniques based on
this parameterization family, designed to ease the rapid design of parameterizations,
are also proposed.


Processing
Irregular Meshes
Mathieu Desbrun
In Shape Modelling International
'02 Conference Proceedings
Abstract: Most meshes are
usually produced with both topological and geometrical irregularity (arbitrary
valence, nonuniform sampling). This has been seen as a flaw hindering
subsequent mesh processing, because most of the other signals we manipulate
everyday (sound, image, video) are acquired and processed as regularly
sampled data. Threedimensional (3D) signals, be they surfaces or volumes,
are however drastically and inherently different. Although the main body
of work on mesh processing has focused on semiregular meshes (on which
the usual DSP tools can be extended quite nicely), we have focused on fully
irregular meshes. Understanding this problem of irregularity, inherent
to 3D sampling, is fundamental in widely different applications ranging
from mesh modeling to smoothing, parameterization, remeshing, and to even
compression or animation. In this talk, we will show some of our latest
results (both theoretical and practical) and will also point to the remaining
challenges. [This is just a short overview to illustrate an invited
talk]


AngleAnalyzer:
A TriangleQuad Mesh Codec
Haeyoung Lee, Pierre
Alliez, and Mathieu Desbrun
In Eurographics 2002 Conference
Proceedings
Abstract: We present AngleAnalyzer,
a new singlerate compression algorithm for trianglequad hybrid meshes.
Using a carefullydesigned geometrydriven mesh traversal and an efficient
encoding of intrinsic mesh properties, AngleAnalyzer produces compression
ratios 40\% better in connectivity and 20% better in geometry than the
leading Touma and Gotsman technique for the same level of geometric distortion.
The simplicity and performance of this new technique is demonstrated, and
we provide extensive comparative tests to contrast our results with the
current stateoftheart techniques.


Interactive
Geometry Remeshing
Pierre Alliez, Mark Meyer,
and Mathieu Desbrun
In Siggraph 2002 Conference
Proceedings
Abstract: We present a novel
technique, both flexible and efficient, for interactive remeshing of irregular
geometry. First, the original (arbitrary genus) mesh is substituted by
a series of 2D maps in parameter space. Using these maps, our algorithm
is then able to take advantage of established signal processing and halftoning
tools that offer realtime interaction and intricate control. The user
can easily combine these maps to create a control map, a map which controls
the sampling density over the surface patch. This map is then nearoptimally
sampled at interactive rates allowing the user to interactively design
a tailored resampling. Once this sampling is complete, a Delaunay triangulation
and fast optimization are performed to perfect the final mesh. As a result,
our remeshing technique is extremely versatile and general being able to
produce arbitrarily complex meshes with a variety of properties including:
uniformity, regularity, semiregularity, curvature sensitive resampling,
and feature preservation. We provide a high level of control over the sampling
distribution allowing the user to interactively custom design the mesh
based on their requirements thereby increasing their productivity in creating
a large variety of meshes.


Generalized
Barycentric Coordinates for Irregular Ngons
Mark Meyer, Haeyoung
Lee, Alan H. Barr, Mathieu Desbrun
Accepted in Journal of Graphics
Tools
Abstract: In this paper
we develop a generalized form of barycentric coordinates for irregular,
convex nsided polygons. Triangular barycentric coordinates have had many
classical applications in computer graphics, from texture mapping to raytracing.
Our new equations preserve many of the familiar properties of the triangular
barycentric coordinates, which suggests that the new nsided formulation
can prove to be similarly useful. We exhibit the properties and behavior
of these new generalized barycentric coordinates through several examples
of applications.


Discrete
DifferentialGeometry Operators for Triangulated 2Manifolds
Mark Meyer, Mathieu Desbrun,
Peter Schröder, Alan H. Barr
VisMath '02, Berlin (Germany)
Abstract: This paper provides
a consistent set of flexible tools to approximate important geometric attributes,
including normal vectors and curvatures, on arbitrary 2D and 3D meshes
embedded in n dimensions. We present a consistent derivation of these first
and second order differential properties using Voronoi cells and the mixed
Finite Element/Finite Volume method. The new operators are closely related
to the continuous case, guaranteeing an appropriate extension from the
continuous to the discrete setting: they respect the intrinsic properties
of the continuous differential operators. We show that these estimates
are optimal in accuracy under mild smoothness conditions, and demonstrate
their numerical quality. We finally present applications of these operators,
such as mesh smoothing and enhancement, quality checking, and denoising
of arbitrary vectors fields, such as flow fields or tensor images.


NearOptimal
Connectivity Encoding of 2Manifold Polygon Meshes
Andrei Khodakovsky, Pierre
Alliez, Mathieu Desbrun, and Peter Schröder
Graphical Models 64(34), pp. 147168, 2002
Abstract: Encoders for triangle
mesh connectivity based on enumeration of vertex valences are among the
best reported to date. They are both simple to implement and report the
best compressed file sizes for a large corpus of test models. Additionally
they have recently been shown to be nearoptimal since they realize the
Tutte entropy bound for all planar triangulations. In this paper we introduce
a connectivity encoding method which extends these ideas to 2manifold
meshes consisting of faces with arbitrary degree. The encoding algorithm
exploits duality by applying valence enumeration to both the primal and
dual mesh in a symmetric fashion. It generates two sequences of symbols,
vertex valences and face degrees, and encodes them separately using two
contextbased arithmetic coders. This allows us to exploit vertex and/or
face regularity if present. When the mesh exhibits perfect face regularity
(e.g., a pure triangle or quad mesh) and/or perfect vertex regularity (resp.
valence six or four) the corresponding bit rate vanishes to zero asymptotically.
For triangle meshes, our technique is equivalent to earlier valence driven
approaches. We report compression results for a corpus of standard meshes.
In all cases we are able to show coding gains over earlier coders, sometimes
as large as 50%. Remarkably, this is true even for coders specialized to
triangle or quad meshes. A theoretical analysis reveals that our approach
is nearoptimal as we achieve the Tutte entropy bound for arbitrary planar
graphs of 2 bits per edge in the worst case.


Interactive
Animation of Clothlike Objects in Virtual Reality.
Mark Meyer, Gilles Debunne,
Mathieu Desbrun, Alan H. Barr
The Journal of Visualization
and Computer Animation, Volume 12, Issue 1, May 2001, pages 112.
Abstract: Modeling and animation
of cloth has experienced important developments in recent years. As a consequence,
complex textile models can be used to realistically drape objects or human
characters in a fairly efficient way. However, realtime realistic simulation
remains a major challenge, even if applications are numerous, from rapid
prototyping to ecommerce. In this paper, we present a stable, realtime
algorithm for animating clothlike materials. Using a hybrid explicit/implicit
algorithm, we perform fast and stable time integration of a physicallybased
model with rapid collision detection and response, as well as wind or liquid
drag effects to enhance realism. We demonstrate our approach through a
series of examples in VR environments, proving that realtime animation
of cloth, even on lowend computers, is now achievable.


Efficient
Viewdependent Refinement of 3D Meshes using Sqrt(3)Subdivision (pdf,
A4 format, 3.5 MBytes)
Pierre Alliez, Nathalie
Laurent, Henri Sanson and Francis Schmitt
In Visual Computer
Abstract: In this paper
we introduce an efficient view dependent refinement technique wellsuited
to adaptive visualization of 3D triangle meshes on a graphic terminal.
Our main goal is the design of fast and robust smooth surface reconstruction
from coarse meshes. We demonstrate that the sqrt{3} subdivision operator
recently introduced by Kobbelt offers many benefits, including viewdependent
refinement, removal of polygonal aspect and highly tunable level of detail
adaptation. In particular, we propose a new data structure that requires
neither edges nor hierarchies for efficient and reversible viewdependent
refinement. Results on various 3D meshes illustrate the relevance of the
technique.


ValenceDriven
Connectivity Encoding for 3D Meshes [Slides,
8 MBytes]
Pierre Alliez and Mathieu
Desbrun
In EUROGRAPHICS '2001 Conference
Proceedings
Abstract: In this paper,
we propose a valencedriven, singleresolution encoding technique for lossless
compression of triangle mesh connectivity. Building upon a valencebased
approach pioneered by Touma and Gotsman, we design a new valencedriven
conquest for arbitrary meshes that always guarantees smaller compression
rates than the original method. Furthermore, we provide a novel theoretical
entropy study of our technique, hinting the optimality of the valencedriven
approach. Finally, we demonstrate the practical efficiency of this approach
(in agreement with the theoretical prediction) on a series of test meshes,
resulting in the lowest compression ratios published so far, for both irregular
and regular meshes, small or large.


Meshes
on Fire
Haeyoung Lee, Laehyun
Kim, Mark Meyer, Mathieu Desbrun
In EG Workshop on Computer
Animation and Simulation '2001
Abstract:We present a new
method for the animation of fire on polyhedral surfaces. Using the notion
of discrete straightest geodesics, we evolve fire fronts directly on the
surface of arbitrarily complex objects. Animator control and motion complexity
is achieved by driving the fire motion using multiscale turbulent wind
fields and geometric quantities. Our model also supports adaptivity of
the fire fronts, multiple simultaneous fires, and merging of multiple fires.
This new technique produces convincing simulations at interactive rates
even on a lowend PC, greatly increasing the productivity of the animation
design process.


Dynamic
RealTime Deformations using Space and Time Adaptive Sampling
Gilles Debunne, Mathieu
Desbrun, Alan H. Barr and MariePaule Cani
In ACM SIGGRAPH '01 Conference
Proceedings
Abstract: This paper presents
a robust, adaptive method for animating dynamic viscoelastic deformable
objects that provides a guaranteed frame rate. Our approach uses a novel
automatic space and time adaptive level of detail technique, in combination
with a largedisplacement (Green) strain tensor formulation. The body is
partitioned in a nonnested multiresolution hierarchy of tetrahedral meshes.
The local resolution is determined by a quality condition that indicates
where and when the resolution is too coarse. As the object moves and deforms,
the sampling is refined to concentrate the computational load into the
regions that deform the most. Our model consists of a continuous differential
equation that is solved using a local explicit finite element method. We
demonstrate that our adaptive Green strain tensor formulation suppresses
unwanted artifacts in the dynamic behavior, compared to adaptive massspring
and other adaptive approaches. In particular, damped elastic vibration
modes are shown to be nearly unchanged for several levels of refinement.
Results are presented in the context of a virtual reality system. The user
interacts in realtime with the dynamic object through the control of a
rigid tool, attached to a haptic device driven with forces derived from
the method.


Progressive
Encoding for Lossless Transmission of 3D Meshes  (1200 dpi,9.8 MBytes)
[300
dpi, 2.4 MBytes] [Slides,
8 MBytes]
Pierre Alliez and Mathieu
Desbrun
In ACM SIGGRAPH '01 Conference
Proceedings
Abstract: Lossless transmission
of 3D meshes is a very challenging and timely problem for many applications,
ranging from collaborative design to engineering. Additionally, frequent
delays in transmissions call for progressive transmission in order for
the end user to receive useful successive refinements of the final mesh.
In this paper, we present a novel, fully progressive encoding approach
for lossless transmission of triangle meshes with a very fine granularity.
A new valencedriven decimating conquest, combined with patch tiling and
an original strategic retriangulation is used to maintain the regularity
of valence. We demonstrate that this technique leads to good mesh quality,
nearoptimal connectivity encoding, and therefore a good ratedistortion
ratio throughout the transmission. We also improve upon previous lossless
geometry encoding by decorrelating the normal and tangential components
of the surface. For typical meshes, our method compresses connectivity
down to less than 3.7 bits per vertex, 40% better in average than the best
methods previously reported; we further reduce the usual geometry bit rates
by 20% in average by exploiting the smoothness of meshes. Concretely, our
technique can reduce an ascii VRML 3D model down to 1.7% of its size for
a 10bit quantization (2.3% for a 12bit quantization) while providing
a very progressive reconstruction.


Adaptive
Simulation of Soft Bodies in RealTime
Gilles Debunne, Mathieu
Desbrun, MariePaule Cani, Alan H. Barr
In Computer Animation '00
Abstract: This paper presents
an adaptive technique to animate deformable bodies in realtime. In contrast
to most previous work, we introduce a multiresolution model that locally
refines or simplifies the simulated object over time in order to optimize
the computational effort. We use the mixed FiniteVolume/FiniteElement
method to derive fast, local discrete differential operators over irregular
grids with tight error bounds. The linear elasticity equations can be simulated
using an arbitrary nonnested hierarchy of volumetric meshes, allowing
the computation load to be automatically concentrated where and when needed.
Realtime simulation, with a guaranteed frame rate, can be achieved as
demonstrated through a series of examples on our video.


SemiRegular
Mesh Extraction from Volumes
Zoë J. Wood, Mathieu
Desbrun, Peter Schröder, David Breen
In ACM/IEEE Visualization
'00 Proceedings
Abstract: We present a novel
method to extract isosurfaces from distance volumes. It generates high
quality semiregular multiresolution meshes of arbitrary topology. Our
technique proceeds in two stages. First, a very coarse mesh with guaranteed
topology is extracted. Subsequently an iterative multiscale forcebased
solver refines the initial mesh into a semiregular mesh with geometrically
adaptive sampling rate and good aspect ratio triangles. The coarse mesh
extraction is performed using a new approach we call surface wavefront
propagation. A set of discrete isodistance ribbons are rapidly built and
connected while respecting the topology of the isosurface implied by the
data. Subsequent multiscale refinement is driven by a simple forcebased
solver designed to combine good isosurface fit and high quality sampling
through reparameterization. In contrast to the Marching Cubes technique
our output meshes adapt gracefully to the isosurface geometry, have a
natural multiresolution structure and good aspect ratio triangles, as demonstrated
with a number of examples.


Anisotropic
FeaturePreserving Denoising of Bivariate Data
Mathieu Desbrun, Mark
Meyer, Peter Schröder, Alan H. Barr
In Graphics Interface '00
Proceedings
Abstract: In this paper,
we present an efficient way to denoise bivariate data like height fields,
color pictures or vector fields, while preserving edges and other features.
Mixing surface area minimization, graph flow, and nonlinear edge preservation
metrics, our method generalizes previous anisotropic diffusion approaches
in image processing, and is applicable to data of arbitrary dimension.
Another notable difference is the use of a more robust discrete differential
operator, which captures the fundamental surface properties. We demonstrate
the method on range images and height fields, as well as greyscale or color
images.


Implicit
Fairing of Arbitrary Meshes using Diffusion and Curvature Flow
Mathieu Desbrun, Mark
Meyer, Peter Schröder, Alan H. Barr
In ACM Siggraph '99 Proceedings
Abstract: In this paper,
we develop methods to rapidly remove rough features from irregularly triangulated
data intended to portray a smooth surface. The main task is to remove undesirable
noise and uneven edges while retaining desirable geometric features. The
problem arises mainly when creating highfidelity computer graphics objects
using imperfectlymeasured data from the real world. Our approach contains
three novel features: an implicit integration method to achieve efficiency,
stability, and large timesteps; a scaledependent Laplacian operator to
improve the diffusion process; and finally, a robust curvature flow operator
that achieves a smoothing of the shape itself, distinct from any parameterization.
Additional features of the algorithm include automatic exact volume preservation,
and hard and soft constraints on the positions of the points in the mesh.
We compare our method to previous operators and related algorithms, and
prove that our curvature and Laplacian operators have several mathematicallydesirable
qualities that improve the appearance of the resulting surface. In consequence,
the user can easily select the appropriate operator according to the desired
type of fairing. Finally, we provide a series of examples to graphically
and numerically demonstrate the quality of our results.


Interactive
multiresolution animation of deformable models
Gilles Debunne, Mathieu
Desbrun, Alan Barr, and MariePaule Cani
In Eurographics Workshop
on Computer Animation and Simulation '99
Abstract: This paper presents
an approach to animate elastic deformable materials at interactive rates
using spacetime adaptive resolution. We propose a new computational model,
based on the conventional Hooke’s law, that uses a discrete approximation
of differential operators on irregular grid. It allows local refinement
or simplification of the computational model based on local error measurement.
We in effect minimize calculations while ensuring a realistic and scaleindependent
behavior within a given accuracy threshold. We demonstrate this technique
on a realtime virtual liver surgery application.


Interactive
Animation of Structured Deformable Objects
Mathieu Desbrun, Peter
Schröder, Alan H. Barr
In Graphics Interface '99
Abstract: In this paper,
we propose a stable and efficient algorithm for animating massspring systems.
An integration scheme derived from implicit integration allows us to obtain
interactive realistic animation of any massspring network. We alleviate
the need to solve a linear system through the use of a predictorcorrector
approach: We first compute a rapid approximation of the implicit integration,
then we correct this estimate in a poststep process to preserve momentum.
Combined with an inverse kinematics process to implement collisions and
other constraints, this method provides a simple, stable and tunable model
for deformable objects suitable for virtual reality. An implementation
in a VR environment demonstrates this approach.


Active
Implicit Surface for Animation
Mathieu Desbrun and MariePaule
CaniGascuel
In Graphics Interface'98
Abstract:This paper introduces
a new model of deformable surfaces designed for animation, which we call
active implicit surfaces. The underlying idea is to animate a potential
field defined by discrete values stored in a grid, rather than directly
animating a surface. This surface, defined as an isopotential of the field,
has the ability to follow a given object using a snakelike strategy. Surface
tension and other characteristics such as constant surface area or constant
volume may be added to this model. The implicit formulation allows the
surface to easily experience topology changes during simulation. We present
an optimized implementation: computations are restricted to a close neighborhood
around the surface. Applications range from the coating of deformable materials
simulated by particle systems (the surface hides the granularity of the
underlying model) to the generation of metamorphosis between shapes that
may not have the same topology.


SpaceTime
Adaptive Simulation of Highly Deformable Substances
Mathieu Desbrun, MariePaule
Cani
INRIA Technical Report, '98
Abstract: This report presents
an approach for efficiently, yet precisely simulating highly deformable
substances ranging from solids to liquids. The key idea is to use a state
equation for specifying the dynamics of the substance. During a simulation,
the material is sampled by particles that derive their interaction forces
from this state equation. Since this ensures the same qualitative behavior
whatever the discretization rate, an adaptive scheme can be used during
simulations: the particle system adapts over space and time according to
a given compromise between precision and computational efficiency. The
system refines (i.e., particles are subdivided) in areas undergoing large
or fast deformations, while it simplifies (i.e., neighboring particles
are merged) in stable regions. Meanwhile, the values of the individual
integration time steps used for each particle are automatically adapted
to avoid instabilities. An active implicit surface is used to visualize
the substance. It smoothly coats the particles and filters internal changes
of granularity over time..


Animation
of Deformable Models using Implicit Surfaces
MariePaule CaniGascuel
and Mathieu Desbrun
IEEE Transactions on Vision
and Computer Graphics, March 97
Abstract: This paper presents
a general approach for designing and animating complex deformable models
with implicit surfaces. Implicit surfaces are introduced as an extra layer
coating any kind of structure that moves and deforms over time. O ering
a compact de nition of a smooth surface around an object, they provide
an efficient collision detection mechanism. The implicit layer deforms
in order to generate exact contact surfaces between colliding bodies. A
simple physicallybased model approximating elastic behavior is then used
for computing collision response. The implicit formulation also eases the
control of the object's volume with a new method based on local controllers.
We present two different applications that illustrate the benefits of these
techniques. First, the animation of simple characters made of articulated
skeletons coated with implicit flesh exploits the compactness and enhanced
control of the model. The second builds on the specific properties of implicit
surfaces for modeling soft inelastic substances capable of separation and
fusion that maintain a constant volume when animated.


Adaptive
Sampling of Implicit Surfaces for Interactive Modeling & Animation
Mathieu Desbrun, Nicolas
Tsingos and MariePaule Gascuel
in Computer Graphics Forum,
15(5), Dec. 96
Abstract: This paper presents
a new adaptive sampling method for implicit surfaces that can been used
in both interactive modeling and animation. The algorithm samples implicit
objects generated by skeletons and efficiently maintains this sampling,
even when their topology changes over time such as during fractures and
fusions. It provides two complementary modes of immediate visualization:
displaying "scales" lying on the surface, or a piecewise polygonization.
The sampling method is particularly well suited to efficiently avoid "unwanted
blending" between different parts of an object. Moreover, it can be used
for partitioning the implicit surface into local bounding boxes that will
accelerate collision detection during animations and rayintersections
during final rendering.


Smoothed
Particles: A new paradigm for highly deformable bodies
Mathieu Desbrun and MariePaule
Gascuel
In 6th Eurographics Workshop
on Animation and Simulation'96
Abstract: This paper presents
a new adaptive sampling method for implicit surfaces that can been used
in both interactive modeling and animation. The algorithm samples implicit
objects generated by skeletons and efficiently maintains this sampling,
even when their topology changes over time such as during fractures and
fusions. It provides two complementary modes of immediate visualization:
displaying \scales" lying on the surface, or a piecewise polygonization.
The sampling method is particularly well suited to efficiently avoid "unwanted
blending" between different parts of an object. Moreover, it can be used
for partitioning the implicit surface into local bounding boxes that will
accelerate collision detection during animations and rayintersections
during final rendering.


Animating
Soft Substances with Implicit Surfaces
Mathieu Desbrun and MariePaule
Gascuel.
In SIGGRAPH'95 Proceedings
Abstract: This paper presents
a hybrid model for animation of soft inelastic substance which undergo
topological changes, e.g. separation and fusion and which fit with the
objects they are in contact with. The model uses a particle system coated
with a smooth isosurface that is used for performing collision detection,
precise contact modeling and integration of response forces. The animation
technique solves three problems inherent in implicit modeling. Firstly,
local volume controllers are defined to insure constant volume deformation,
even during highly inelastic processes such as splitting or fusion. Secondly,
we avoid unwanted distance blending between disconnected pieces of the
same substance. Finally, we simulate both collisions and progressive merging
under compression between implicit surfaces that do not blend together.
Parameter tuning is facilitated by the layered model and animation is generated
at interactive rates.
