There are several representations of 3-D shape in common use today. However, by far the most common is the polygon mesh. Meshes are the ubiquitous data representation that essentially all graphics systems understand and use. Our course is devoted to exploring how to efficiently manipulate such surface meshes.
Before discussing how to process meshes, we must first understand how to represent them. Since meshes are essentially just graphs, all the usual graph representations — adjacency lists, adjacency matrices, etc. — can be used for meshes as well. However, since meshes are also more than just graphs, there are several mesh-specific data representations that are more convenient.
One of the more common data structures for representing meshes is the half-edge mesh.
L. Kettner. Using generic programming for designing a data structure for polyhedral surfaces. Computational Geometry: Theory and Applications, 13(1):65–90, 1999. [CiteSeer]
S. Campagna, L. Kobbelt, and H-P. Seidel. Directed Edges — A scalable representation for triangle meshes. Journal of Graphics Tools, 3(4):1–12, 1998. [CiteSeer]
There are several other useful mesh representation schemes aside from half-edges. One notable alternative is the quad-edge. This is quite similar to half-edges, but has some very elegant duality properties.
For applications that expect to frequently encounter non-manifold geometry, it can be useful to use a simpler cell adjacency structure. VTK is an example of a system that uses this type of mesh representation.
There are a number of fairly substantial open source mesh libraries currently available.
Unfortunately, there are a lot of file formats out there for describing polygon meshes. For the projects in this course, we’ll be using a variant of the Wavefront OBJ format. Here are some links that might help you deal with other formats as well.
Here are some places where you can get example meshes to play with.