Mesh Processing

This is the webpage of the mesh processing tutorial at ECCV 2008 (Sunday October 12th - Morning : 9-12.30), see also this link: ECCV tutorials

Speaker: Bruno Lévy

Book

Polygon Mesh Processing, Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez and Bruno Levy, AK Peters / CRC press. More information

Abstract

Polygon Mesh is a widely used representation for 3D geometry. The reasons for its success is first the ease of representation. A mesh can be stored in a file as an array of vertices and an array of polygons. The other reason is the versatility, a mesh can be used for both designed objects and acquired objects, it works for both manufactured objects and natural shapes. However, manipulating this type of representation (i.e. geometry processing with meshes) requires special data structures and special mathematics.

Syllabus and references

1) Efficiently navigating in a mesh with the halfedge data structure

Designing a data structure for polyhedral surfaces, Lutz Kettner, SOCG 1998
N-dimensional generalized combinatorial maps and cellular quasi-manifolds, Lienhardt P, International Journal on Computational Geometry and Applications, Vol. 4, n° 3, pp. 275-324 - 1994
Implementations: see CGAL, OpenMesh, Graphite links below
Slides

2) Differential geometry for non-differentiable geometry

A Signal Processing Approach to Fair Surface Design, Gabriel Taubin, SIGGRAPH 1995
Discrete Fairing of Curves and Surfaces based on Linear Curvature Distribution, Schneider and Kobbelt, Curves and Surfaces, 1999
Using Partial Differential Equations to Generate Free-form Surfaces (1990), M.I.G. Bloor and M.J. Wilson, Computer Aided Design, 1990
Graphite software tutorial: MeshRepair

3) Bridging the gap between parametric representations (Splines) and Meshes: mesh parameterization

References on Michael Floater's homepage
Mesh Parameterization: Theory and Practice, Kai Hormann, Bruno Lévy and Alla Sheffer ACM SIGGRAPH tutorial, 2007
MIPS: an efficient global parametrization method, Kai Hormann and Gunther Greiner, Curve and Surface Design, 2000
Graphite software tutorials:
- Apparence preserving simplification, normal mapping tutorial: NormalMapping
- Constrained Texture Mapping tutorial: ConstrainedTex
- Periodic Global Parameterization tutorial: PGP
Slides

4) Computing on a mesh: Finite Elements Modeling and Discrete Exterior Calculus

Discrete Differential Geometry website

5) Local to global: Spectral geometry processing

ICIAM 2007 Minisymosium (Organized by M. Maggioni and N. Saito)

Manifold learning resources
non-rigid shape matching
- Non-Rigid Spectral Correspondence of Triangle Meshes, Varun Jain, Hao Zhang, and Oliver van Kaick
- Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration, Mateus, Diana and Horaud, Radu P. and Knossow, David and Cuzzolin, Fabio and Boyer, Edmond
Reconstruction and quadrangulation
- Spectral surface reconstruction, Kolluri, Shewchuk and O'Brien
- Spectral surface reconstruction, Alliez, Cohen-Steiner, Tong and Desbrun (+ "tensor voting" idea)
- Spectral Surface Quadrangulation, Dong, Bremer, Garland, Pascucci and Hart, ACM SIGGRAPH 2006
- Spectral Surface Quadrangulation,Jin Huang, Muyang Zhang, Jin Ma, Xinguo Liu, Leif Kobbelt, Hujun Bao, ACM SIGGRAPH Asia 2008
- Spectral conformal parameterization, Mullen, Tong, Alliez and Desbrun, ACM/EG SGP 2008
- Manifold Harmonics, Vallet and Lévy, Eurographics 2008 (+links to spectral geometry processing)
Graphite software tutorial: Spectral geometry processing with ManifoldHarmonics (also has spectral conformal parameterization)
Slides

6) The engine behind the scene: numerical optimization

The Conjugate Gradient without the agonizing pain, Jonathan Richard Shewchuck
SuperLU
TAUCS
Slides

Slides

Links, further reading

Geometric Modeling Based on Polygonal Meshes, Mario Botsch, Mark Pauly, Leif Kobbelt, Pierre Alliez and Bruno Lévy Eurographics Tutorial, 2008
- see also the companion Sourcecode on Mario Botsch's homepage
Geometric Modeling Based on Polygonal Meshes, Mario Botsch, Mark Pauly, Leif Kobbelt, Pierre Alliez, Bruno Lévy, Stephan Bischoff and Christian Rossl, ACM SIGGRAPH Tutorial, 2007
Mesh processing course on Gabriel Peyre's website
Bruno Lévy's habilitation thesis (available in French and English)

Software

Graphite An experimental 3D modeler with geometry processing algorithms
CGAL The "computational geometry algortihms library", robust and efficient implementations of Delaunay triangulations + other functionalities
OpenMesh Data structures + algorithms for geometry processing
Meshlab (complete mesh manipulation package)
VCG (triangle and tetrahedral meshes)

Data (publically available meshes)

Yellow pages

Some researchers in geometry processing and what they look like