Publications

	On the Equilibrium of Simplicial Masonry Structures Fernando de Goes, Pierre Alliez, Houman Owhadi, and Mathieu Desbrun ACM Transactions on Graphics (SIGGRAPH) 32(4), 2013 Abstract: We present a novel approach for the analysis and design of selfsupporting simplicial masonry structures. A finite-dimensional 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 form-finding tools that improve over previous work in efficiency, accuracy, and scalability.
	Variational Discretization for Rotating Stratified Fluids Mathieu Desbrun, Evan S. Gawlik, François Gay-Balmaz, and Vladimir Zeitlin To appear, AIMS Discrete & Continuous Systems Series A, 2013 Abstract: Abstract. In this paper we develop and test a structure-preserving 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 Euler-Poincaré 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 fine-tune the motion. We formulate our motion editing as an optimization problem with dynamics constraints to enforce a physically-plausible 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.
	Feature-Preserving Surface Reconstruction and Simplification from Defect-Laden Point Sets Julie Digne, David Cohen-Steiner, Pierre Alliez, Mathieu Desbrun, and Fernando de Goes Journal of Mathematical Imaging and Vision, Springer, Jan 2013 Abstract: We introduce a robust and feature-capturing surface reconstruction and simplification method that turns an input point set into a low triangle-count simplicial complex. Our approach starts with a (possibly non-manifold) 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 feature-sensitive metric between point sets and triangle meshes can also be used as a post-processing 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 high-quality blue noise point distributions of arbitrary density functions. At its core is a novel formulation of the recently-introduced concept of capacity-constrained 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 high-quality 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 micro-structures 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 macro-scales we observe and the underlying micro-scale 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 cardio-pulmonary imaging, where current flow in fine-scale tissues underlies the resulting coarse-scale images. In this paper, we introduce a geometric approach for the homogenization (simulation) and inverse homogenization (imaging) of divergence-form elliptic operators with rough conductivity coefficients in dimension two. We show that conductivity coefficients are in one-to-one correspondence with divergence-free matrices and convex functions over the domain. Although homogenization is a non-linear and non-injective operator when applied directly to conductivity coefficients, homogenization becomes a linear interpolation operator over triangulations of the domain when re-expressed using convex functions, and is a volume averaging operator when re-expressed with divergence-free matrices. We explicitly give the transformations which map conductivity coefficients into divergence-free 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 non-linear and severely ill-posed, but that we can decompose into a linear ill-posed problem and a well-posed non-linear problem. Finally, our new geometric approach to homogenization and inverse homogenization is applied to EIT.
	The Chain Collocation Method: A Spectrally Accurate Calculus of Forms Dzhelil Rufat, Gemma Mason, Patrick Mullen, and Mathieu Desbrun. (submitted) 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, structure-preserving 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 structure-preserving 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 well-known collocation-based spectral methods. Its efficient implementation using fast Fourier transforms is provided as well.
	On the Coupling Between an Ideal Fluid and Immersed Particles Henry O. Jacobs, Tudor S. Ratiu, and Mathieu Desbrun. To appear, Physica D, 2013 [arXiv:1208.6561] Abstract: In this paper we use Lagrange-Poincaré reduction to understand the coupling between a fluid and a set of Lagrangian particles that are supposed to simulate it. In particular, we reinterpret the work of Cendra et al. [CMR01] by substituting velocity interpolation from particle velocities for their principal connection. The consequence of writing evolution equations in terms of interpolation is two-fold. First, it gives 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 particle spectral methods where the error analysis is "built-in". We also discuss the influence of other parameters attached to the particles, such as shape, orientation, or higher-order deformations, and how they can help with conservation of momenta in the sense of Kelvin's circulation theorem.
	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 Primal-Dual 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 primal-dual 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 primal-dual 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 primal-dual 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), 1724-1760, 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 volume-preserving diffeomorphisms of the fluid domain. Inspired by this framework, we construct a finite-dimensional 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 Euler-Poincaré 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 long-term 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 Cohen-Steiner, 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 optimal-transport 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 1-simplices. A fine-to-coarse 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: Hodge-Optimized Triangulations Patrick Mullen, Pooran Memari, Fernando de Goes, Mathieu Desbrun. Transactions on Graphics (SIGGRAPH) 2011. Abstract: We introduce Hodge-optimized triangulations (HOT), a family of well-shaped primal-dual 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 primal-dual 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, 112-121. 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 high-resolution 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 1-forms 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 physically-based shape interpolation between poses. We extend linear modal analysis to offer an efficient and robust numerical technique to generate physically-plausible dynamics even for very large deformation. Our method also provides a rich set of intuitive editing tools with real-time 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 user-specified singularities and directional constraints.
	Signing the Unsigned: Robust Surface Reconstruction from Raw Pointsets P. Mullen, F. de Goes, M. Desbrun, D. Cohen-Steiner, 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.
	Structure-Preserving 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 443-458. 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 volume-preserving 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 numerical-analytic 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 volume-preserving diffeomorphisms using a finite dimensional Lie group, and associated discrete Euler equations are derived from a variational principle with non-holonomic constraints. The resulting discrete equations of motion yield a structure-preserving time integrator with good long-term energy behavior and for which an exact discrete Kelvin's circulation theorem holds.
	Deformation Transfer to Multi-Component 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 height-and-tilt 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 height-and-field representation.
	Energy-preserving 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 adaptive-time stepping methods. This paper proposes simple, unconditionally stable, fully Eulerian integration schemes with no numerical viscosity that are capable of maintaining the liveliness of fluid motion without recourse to corrective devices. Pressure and fluxes are solved efficiently and simultaneously in a time-reversible manner on simplicial grids, and the energy is preserved exactly over long time scales in the case of inviscid fluids. These integrators can be viewed as an extension of the classical energy-preserving Harlow-Welch / Crank- Nicolson scheme to simplicial grids.
	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 non-homogeneous, non-isotropic materials. Based on recent developments in homogenization theory, a methodology is introduced to approximate a deformable object made of arbitrary fine structures of various linear elastic materials with a dynamically-similar coarse model. This numerical coarsening of the material properties allows for simulation of fine, heterogeneous structures on very coarse grids while capturing the proper dynamics of the original dynamical system, thus saving orders of magnitude in computational time. Examples including inhomogeneous and/or anisotropic materials can be realistically simulated in realtime with a numerically-coarsened 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 user-defined 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 state-space 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 user-specified 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, 711-715, 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 structure-preserving 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 free-boundary conformal parameterizations of triangle mesh patches, without the common artifacts due to positional constraints on vertices and without undue bias introduced by sampling irregularity. High-quality parameterizations are computed through a constrained minimization of a discrete weighted conformal energy by finding the largest eigenvalue/eigenvector of a generalized eigenvalue problem involving sparse, symmetric matrices. We demonstrate that this novel and robust approach improves on previous linear techniques both quantitatively and qualitatively.
	Computational Electromagnetism with Variational Integrators and Discrete Differential Forms Ari Stern, Yiying Tong, Mathieu Desbrun, and Jerrold E. Marsden. Submitted (see arXiv:0707.4470v2). 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 well-established numerical methods and to new methods introduced here. First, we show that Yee's finite-difference time-domain (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 4-dimensional 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.
	Voronoi-based Variational Reconstruction of Unoriented Point Sets Pierre Alliez, David Cohen-Steiner, Yiying Tong, and Mathieu Desbrun. Symposium on Geometry Processing, pp. 39-48, 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 best-fitting 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 user-guided cortical registration.
	Generalized Surface Flows for Mesh Processing Ilya Eckstein, Jean-Philippe Pons, Yiying Tong, C.C. Jay Kuo, and Mathieu Desbrun. Symposium on Geometry Processing, pp. 183-192 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 volume-preservation 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 Lagrange-d’Alembert-Pontryagin 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 non-photorealistic rendering. To achieve a desired effect one is typically interested in smoothly varying fields that satisfy a sparse set of user-provided 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 1-forms), we obtain an intrinsic, coordinate-free 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 pre-factorization. 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 detail-preserving mesh manipulation through a set of high-level, 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 self-collision 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 high-genus 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 covector-valued differential two-form. 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. 17-26, 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 non-linear 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. 43-51 Abstract: We present a general-purpose numerical scheme for time integration of Lagrangian dynamical systems—an important computational tool at the core of most physics-based 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 high-order 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 Pontryagin-Hamilton 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 non-linear elasticity with implementation details.
	Designing Quadrangulations with Discrete Harmonic Forms Yiying Tong, Pierre Alliez, David Cohen-Steiner, and Mathieu Desbrun ACM/EG Symposium on Geometry Processing 2006, pp. 201-210 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 piecewise-smooth scalar fields whose isocontours form a pure quadrangle tiling, with no T-junctions.
	Stable, Circulation-Preserving, 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 deeply-rooted 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. 1041-1048 Abstract: Vertex- and face-based 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. 2-forms, and complete the picture by introducing edge-based subdivision schemes to construct the missing bases for discrete differential 1-forms. 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 face-based 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 0-forms and generalized half-box splines for 2- forms results in a unique generalized spline scheme for 1-forms, easily incorporated into standard subdivision surface codes. We also provide corresponding boundary stencils. Once a metric is supplied, the scalar 1-form 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. 690-697 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 pixel-based 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 low-distortion 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 geometric---instead of a traditional numerical-analytic---approach 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 well-known 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. 99-105 Abstract: Compressing sequences of complex time-varying 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 time-varying 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 block-based 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 octree-based scheme. We also exploit local spatiotemporal patterns through context-based arithmetic coding. Fine-grain geometric residuals are encoded separately with user-specified 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 Cohen-Steiner, Sharif Elcott, Eva Kanso, Liliya Kharevych, Adrian Secord, John M. Sullivan, Yiying Tong, Mariette Yvinec.
	Variational Tetrahedral Meshing Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, and Mathieu Desbrun ACM Trans. on Graphics (SIGGRAPH '05), 24(3), pp. 617-625 Abstract: In this paper, a novel Delaunay-based variational approach to isotropic tetrahedral meshing is presented. To achieve both robustness and efficiency, we minimize a simple mesh-dependent 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 well-shaped 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. 1148-1155. 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) user-specified 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), 319--338. 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 free-form 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. 181-186. 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 non-negative 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 best-fitting 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 three-dimensional 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.
	Geodesics-based One-to-One Parameterization of 3D Triangle Meshes Haeyoung Lee, Yiying Tong, and Mathieu Desbrun IEEE Multimedia journal, Volume 12, Issue 1, Jan.-March 2005, 27--33. 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 one-to-one mapping without foldovers in a geometrically intuitive way.
	A Haptic-Rendering 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, 66--75. 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 high-resolution 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 axis-aligned sweep through the volume to locate handles, compute their sizes, and selectively remove them. The algorithm is designed to facilitate out-of-core execution. It finds the handles by incrementally constructing and analyzing a Reeb graph. The size of a handle is measured by a short non-separating 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 Cohen-Steiner, 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 best-fitting regions. Our approach is entirely discrete and error-driven, 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, 4902-4907. 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 High-Frequency Aesthetically-Coherent 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 iso-contours 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, physically-motivated 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, motion-capture 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 Cohen-Steiner, 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 man-made 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 point-sampled 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.
	Non-iterative, Feature-Preserving 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 diffusion-based iterative techniques for feature-preserving smoothing, we propose a radically different approach, based on robust statistics and local first-order predictors of the surface. The robustness of our local estimates allows us to derive a non-iterative feature-preserving 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 non-manifold 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 finite-difference 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 divergence-free part, a curl-free part, and a harmonic part. We show how our discrete approach matches its well-known smooth analog, called the Helmotz-Hodge 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 context-based 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 implicit-based 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 Implicit-based 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 low-end 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 widely-used 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 least-distorted 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 two-dimensional 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 least-distorted 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, non-uniform 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. Three-dimensional (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 semi-regular 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]
	Angle-Analyzer: A Triangle-Quad Mesh Codec Haeyoung Lee, Pierre Alliez, and Mathieu Desbrun In Eurographics 2002 Conference Proceedings Abstract: We present Angle-Analyzer, a new single-rate compression algorithm for triangle-quad hybrid meshes. Using a carefully-designed geometry-driven mesh traversal and an efficient encoding of intrinsic mesh properties, Angle-Analyzer 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 state-of-the-art 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 real-time 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 near-optimally 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, semi-regularity, 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 N-gons 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 n-sided polygons. Triangular barycentric coordinates have had many classical applications in computer graphics, from texture mapping to ray-tracing. Our new equations preserve many of the familiar properties of the triangular barycentric coordinates, which suggests that the new n-sided 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 Differential-Geometry Operators for Triangulated 2-Manifolds 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 condi-tions, 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.
	Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes Andrei Khodakovsky, Pierre Alliez, Mathieu Desbrun, and Peter Schröder Graphical Models 64(3-4), pp. 147-168, 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 near-optimal 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 2-manifold 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 context-based 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 re-veals that our approach is near-optimal as we achieve the Tutte en-tropy bound for arbitrary planar graphs of 2 bits per edge in the worst case.
	Interactive Animation of Cloth-like 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 1-12. 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, real-time realistic simulation remains a major challenge, even if applications are numerous, from rapid prototyping to e-commerce. In this paper, we present a stable, real-time al-gorithm for animating cloth-like materials. Using a hybrid explicit/implicit algorithm, we perform fast and stable time integration of a physically-based 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 real-time animation of cloth, even on low-end computers, is now achievable.
	Efficient View-dependent 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 well-suited 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 view-dependent 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 view-dependent refinement. Results on various 3D meshes illustrate the relevance of the technique.
	Valence-Driven 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 valence-driven, single-resolution encoding technique for lossless compression of triangle mesh connectivity. Building upon a valence-based approach pioneered by Touma and Gotsman, we design a new valence-driven 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 valence-driven 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 multi-scale 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 low-end PC, greatly increasing the productivity of the animation design process.
	Dynamic Real-Time Deformations using Space and Time Adaptive Sampling Gilles Debunne, Mathieu Desbrun, Alan H. Barr and Marie-Paule Cani In ACM SIGGRAPH '01 Conference Proceedings Abstract: This paper presents a robust, adaptive method for animating dynamic visco-elastic 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 large-displacement (Green) strain tensor formulation. The body is partitioned in a non-nested 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 mass-spring 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 real-time 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 valence-driven 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, near-optimal connectivity encoding, and therefore a good rate-distortion 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 10-bit quantization (2.3% for a 12-bit quantization) while providing a very progressive reconstruction.
	Adaptive Simulation of Soft Bodies in Real-Time Gilles Debunne, Mathieu Desbrun, Marie-Paule Cani, Alan H. Barr In Computer Animation '00 Abstract: This paper presents an adaptive technique to animate deformable bodies in real-time. In contrast to most previous work, we introduce a multi-resolution model that locally refines or simplifies the simulated object over time in order to optimize the computational effort. We use the mixed Finite-Volume/Finite-Element 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 non-nested hierarchy of volumetric meshes, allowing the computation load to be automatically concentrated where and when needed. Real-time simulation, with a guaranteed frame rate, can be achieved as demonstrated through a series of examples on our video.
	Semi-Regular 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 iso-surfaces from distance volumes. It generates high quality semi-regular multiresolution meshes of arbitrary topology. Our technique proceeds in two stages. First, a very coarse mesh with guaranteed topology is extracted. Subsequently an iterative multi-scale force-based solver refines the initial mesh into a semi-regular mesh with geometrically adaptive sampling rate and good aspect ratio triangles. The coarse mesh extraction is performed using a new approach we call surface wave-front propagation. A set of discrete iso-distance ribbons are rapidly built and connected while respecting the topology of the iso-surface implied by the data. Subsequent multi-scale refinement is driven by a simple force-based solver designed to combine good iso-surface fit and high quality sampling through reparameterization. In contrast to the Marching Cubes technique our output meshes adapt gracefully to the iso-surface geometry, have a natural multiresolution structure and good aspect ratio triangles, as demonstrated with a number of examples.
	Anisotropic Feature-Preserving 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 high-fidelity computer graphics objects using imperfectly-measured data from the real world. Our approach contains three novel features: an implicit integration method to achieve efficiency, stability, and large time-steps; a scale-dependent 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 mathematically-desirable 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 Marie-Paule 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 space-time 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 scale-independent behavior within a given accuracy threshold. We demonstrate this technique on a real-time 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 mass-spring systems. An integration scheme derived from implicit integration allows us to obtain interactive realistic animation of any mass-spring network. We alleviate the need to solve a linear system through the use of a predictor-corrector approach: We first compute a rapid approximation of the implicit integration, then we correct this estimate in a post-step 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 Marie-Paule Cani-Gascuel 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 iso-potential of the field, has the ability to follow a given object using a snake-like 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.
	Space-Time Adaptive Simulation of Highly Deformable Substances Mathieu Desbrun, Marie-Paule 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 Marie-Paule Cani-Gascuel 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 physically-based 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 Marie-Paule 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 ray-intersections during final rendering.
	Smoothed Particles: A new paradigm for highly deformable bodies  Mathieu Desbrun and Marie-Paule 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 ray-intersections during final rendering.
	Animating Soft Substances with Implicit Surfaces Mathieu Desbrun and Marie-Paule 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 iso-surface 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.

Last change: July 29nd, 2010

Under eternal construction. No trees have been injured in the making of this page.

© desbrun / Applied Geometry / Caltech 2009