Publications

Displaying publications with Levy as a co-author. The other publications are available here

Publications by year

2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  

Most documents on this website are protected by copyright. By clicking on a PDF icon, you confirm that you or your institution has the right to do so. Note that the definitive versions of all EG papers (Eurographics,...) can be downloaded from http://www.eg.org/EG/DL. ACM papers (Siggraph, ...) can be downloaded from http://www.acm.org/dl/.

 

“Numerical Methods for Digital Geometry Processing”
Bruno Lévy
Israel Korea Bi-National Conference - Invited talk, 2005

Abstract: Digital Geometry Processing recently appeared (in the middle of the 90's) as a promising avenue to solve the geometric modeling problems encountered when manipulating surfaces represented by discrete elements (i.e. meshes). Since a mesh may be considered to be a sampling of a surface - in other words a signal - the DGP (digital signal processing) formalism was a natural theoretic background for this discipline (see e.g. Taubin 95). In this discipline, discrete fairing Kobbelt 97 and mesh parameterization Floater 98 have been two active research topics these last few years. In parallel with the evolution of this discipline, acquisition techniques have made huge advances, and todays meshes acquired from real objects by range-laser scanners are larger and larger (30 million triangles is now common). This causes difficulties when trying to apply DGP tools to these meshes. The kernel of a DGP algorithm is a numerical method, used either to solve a linear system, or to minimize a multivariate function. The Gauss-Seidel iteration and gradient descent methods used at the early ages of DGP do not scale-up when applied to huge meshes. In this presentation, our goal is to give a survey of classic and more recent numerical methods, to show how they can be applied to DGP problems, from a theoretic point of view down to implementation. We will focus on two different classes of DGP problems (mesh fairing and mesh parameterization), show solutions for linear problems, quadratic problems, and general non-linear problems, with and without constraint. In particular, we give a general formulation of quadratic problems with reduced degrees of freedom that can be used as a general framework to solve a wide class of DGP problems. Our method is implemented in the OpenNL library, freely available on the web. The presentation will be illustrated with live demos of the methods.

BibTex reference

@INPROCEEDINGS{levy:NMD:2005,
   AUTHOR     = "Bruno Lévy",
   TITLE      = "Numerical Methods for Digital Geometry Processing",
   BOOKTITLE  = "Israel Korea Bi-National Conference",
   NOTE       = "Invited talk",
   YEAR       = "2005",
}

Supplemental material, links, hindsight ...

  • See our book Polygon Mesh Processing (Botsch, Kobbelt, Pauly, Alliez and Levy), "Numerics" chapter (Poisson and Laplace, data structure for sparse matrices, iterative solvers, direct solvers ...)
  • An implementation is available in our OpenNL numerical library (if you need something you can include in your own application),
  • ... and also in Graphite (if you need a GUI).