Project: Generic Mesh Algorithms

Design the interface between data structures that represent 3D meshes and generic algorithms on meshes, for example, compression, subdivision surfaces, etc.

The Standard Template Library (STL) [Austern98, SGI-STL] contains several examples of a similar interface design: Iterators are the interface between sequences of items in container classes and generic algorithms on sequences. However, they (usually) do not modify the container. Among the container classes some modifying functions, e.g., insert or remove, describe a standardized interface for modifying the container classes and can be used for generic algorithms on container classes. This project is expected to design a generic interface in the same spirit for mesh algorithms. Typical operations to consider could be edge collapse, edge split, edge flip, etc.

We start with a set of data structures that can represent a 3D mesh, and with a set of algorithms working on it. We focus on algorithms modifying the mesh because this is the difficult design question here. Since such algorithms usually need neighborhood relationships on the mesh, we need to work with more elaborate data structures than just containers of polygons. Possible choices can be:

• The 3D polyhedral surface in CGAL, e.g., the class CGAL::Polyhedron_3. CGAL is the Computational Geometry Algorithms Library <www.cgal.org> [Fabri99], a good source of data structures and algorthms in geometry that also could be used to implement mesh algorithms.
• The class CGAL::Triangulation_2 is based on a triangulation data structure that could be used in three-dimensions to represent triangulated meshes.
• The OpenMesh project <www.openmesh.org> contains a generic mesh data structure and several example programs realizing algorithms with it.

Meshes can be distinguished into polygonal and triangulated meshes. An optional extension could be the distinction between structured and unstructured meshes: structured meshes have the combinatorics of a regular grid (square, triangle, or hexagonal grid). The general case of unstructured meshes has no restriction on the mesh combinatorics.

A wide variety of algorithms exist for meshes. The actual choice for this project depends on the interest and knowledge of the student in this field. We sketch some ideas, collecting actual references would be part of the project start (with our help). This project is also suitable for team work among several students, for example, selecting different set of algorithms to study. A collaboration with the polygon triangulation project could be possible as well. Algorithm examples are:

• Mesh compression and decompression.
• Mesh smoothing and subdivision surfaces, e.g., recent quad/triangle subdivision from stam/loop or Levin.
• Mesh simplification.
• Remeshing; by resampling (eg, Turk92, ours), or by adaptation (local modification).

The goal of the project is to design the interface and to realize some of the data structures and algorithms, possibly based on already existing implementations, for example, in CGAL. The task includes:

• Analyse the set of operations of each agorithm and how it could be implemented for each data structure considered.
• Find a common set (or several sets) of operations that support the different combinations.
• Implement the interface for the data structures, possibly with adaptors for existing data structures.
• Implement the algorithm based on this interface, maybe also with adaptors to already existing algorithms.
• Test your generic algorithms on the different representations.
• Document the design, for example, in the style of CGAL or using Doxygen.

Prerequisites

This project requires interest in mesh algorithms and graphics. Since CGAL will be covered later in the course, it might be necessary to learn about CGAL prior to that.

References

[Austern98]

Mathew H. Austern. Generic Programming and the STL: Using and Extending the C++ Standard Template Library. Addison-Wesley, 1998.

[SGI-STL]

Silicon Graphics Computer Systems, Inc. Standard Template Library Programmer's Guide. http://www.sgi.com/tech/stl/.

[Fabri99]

Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr. On the Design of CGAL, the Computational Geometry Algorithms Library. Software -- Practice and Experience, submitted 1999, to appear. (also available as technical report)