Matt's Source Code Portal

Meshes

In a very straightforawrd sense, a mesh represents all the geometry and topology of an object. In mathematical terms, it is a piece-wise linear surface, or a surface of connected polygons. So we have a series of vertices, and faces that connect them. Each face can be defined by the list of vertices it connects, but we must be careful about the order of these vertices; for example, the face 1, 2, 4, 3 is very different from the face 1, 2, 3, 4.

Although they can be useful, from a programming standpoint we tend not to enjoy meshes in which faces can have an arbitrary number of vertices. This results in various problems, among them variable-length data structures and dealing with non-planar faces. Furthermore, graphics cards generally can only handle meshes in which each face is a triangle (although since any polygon can be triangulated, this is not a direct restriction.) Several graphics applications use quadrilaterals (quads) for faces, since artists prefer this and some simulations (ex. cloth) are simpler or better as quads. Mathematicans call triangular meshes "simplicial complexes" (meaning simplest) since a triangle is the simplest polygon.

Representations

Meshes store a lot of data, and when we store this in RAM we need to make a tradeoff between memory consumption, ease of programming, and the speed at which the stored information can be accessed. Let's look at a simple cube mesh:

When trying to represent this mesh digitally, there is a strong diffence between topological data (the connectivity and adjacency of the mesh) and the geometric data (the location of the vertices, the normals at these vertices, etc.). Generally topology is any variable stored as an integer or pointer; geometry data is a series of floating-point values. In the case above, we might store the mesh as follows:


	struct Vertex
	{
		double x, y, z;
	};
	struct Face
	{
		unsigned int Indices[4];
	};
	
	Vertex CubeVertices[8] = 
	{ {0.0, 0.0, 0.0},
	  {1.0, 0.0, 0.0},
	  {0.0, 1.0, 0.0},
	  {1.0, 1.0, 0.0},
	  {0.0, 0.0, 1.0},
	  {1.0, 0.0, 1.0},
	  {0.0, 1.0, 1.0},
	  {1.0, 1.0, 1.0}};
	  
	Face CubeFaces[6] =
	{ {0, 1, 3, 2},
	  {0, 1, 5, 4},
	  {3, 1, 5, 7},
	  {2, 3, 7, 6},
	  {0, 2, 6, 4},
	  {6, 7, 5, 4}};

Of course, this is far from the only possible representation. We might define each face as a triangle, rather than a quad. In this case there would be 12 faces, and we would just divide each quad into two triangles. Also, rather than definining a face as a series of indices into the vertices, we could define it as four (or three) pointers directly to the vertex structures. This would be useful if we thought we might be removing vertices from our cube, but is slower and wastes memory. There are many other useful things you might want to know about a mesh:

Given a vertex, return all the vertices connected to it by an edge
Given a vertex, return all the faces incident on it
Given a face, return all the adjacent faces
Iterate over all edges in the mesh exactly once
Given two vertices connected by an edge, return the two incident faces

Depending upon the representation chosen, all of the above functions can be made very easy to program and efficent calls. For example, we could just store at each vertex a list of incident faces and vertices. All of this adjacency and edge information is just for easy access; it can all be extracted from just the list of vertices and faces, which is why the simplest file format, OBJ, stores only vertex and face information.

Code

In my code I have two types of meshes, simple meshes (which store only triangle and vertex information) and edge meshes (which store a lot more topology information.) Edge meshes are used for complex things like subdivision, and simple meshes are used for simple things like rendering. If a complex function (like subdivide) is called on a simple mesh, the simple mesh converts itself into an edge mesh, performs the complex function, and then downloads the data from the edge mesh, making the transition transparent to the calling function. A simple mesh is actually implemented as an abstract class, called BaseMesh. There is a C-pointer implementation of this class called Mesh, usable in OpenGL, software, and DirectX, and a DirectX implementation of BaseMesh called D3DMesh. This D3D-only mesh class is very useful because many intricate functions, like mesh simplification, are built into DirectX.