[ Previous Section | Next Section | Chapter Index | Main Index ]

Subsections
Indexed Face Sets
OBJ Files
Terraine and Grids

Section 3.3

Polygonal Meshes


When creating objects that are made up of more than just a few polygons, we need some way to organize the data and some strategy for using it effectively. The problem is how to represent polygonal meshes for efficient processing. A polygonal mesh is just a collection of connected polygons used to model a two-dimensional surface. The term includes polyhedra such as a cube or a dodecahdron, as well as meshes used to approximate smooth surfaces such as the geometry produced by my UVSphere class. In these cases, the mesh represents the surface of a solid object. However, the term is also used to refer to open surfaces with no interior, such as a mesh representing the graph of a function z = f(x,y).

There are many data structures that can be used to represent polygonal meshes. We will look at one general data structure, the indexed face set, that is often used in computer graphics. We will also consider the special case of a polygonal grid.


3.3.1  Indexed Face Sets

The polygons in a polygonal mesh are also referred to as "faces" (as in the faces of a polyhedron), and one of the primary means for representing a polygonal mesh is as an indexed face set, or IFS.

The data for an IFS includes a list of all the vertices that appear in the mesh, giving the coordinates of each vertex. A vertex can then be identified by an integer that specifies its index, or position, in the list. As an example, consider this pyramid, a simple five-sided polyhedron:

The vertex list for this polyhedron has the form

Vertex #0.  (1,0,1)
Vertex #1.  (1,0,-1)
Vertex #2.  (-1,0,-1)
Vertex #3.  (-1,0,1)
Vertex #4.  (0,1,0)

The order of the vertices is completely arbitrary. The purpose is simply to allow each vertex to be identified by an integer.

To describe a polygon, we have to give its vertices, being careful to enumerate them in counterclockwise order as seen from the front of the polygon. In this case, the fronts of the polygonal faces of the pyramid should be on the outside of the pyramid. Now for an IFS, we can specify a vertex by giving its index in the list. For example, we can say that one of the faces of the pyramid is the polygon formed by vertex #4, vertex #3, and vertex #0. To complete the data for our IFS, we just give the indexes of the vertices for each face:

Face #1:  4 3 0
Face #2:  4 0 1
Face #3:  4 1 2
Face #4:  4 2 3
Face #5:  0 3 2 1

In Java, we can store this data effectively in two two-dimensional arrays:

float[][] vertexList = {  {1,0,1}, {1,0,-1}, {-1,0,-1}, {-1,0,1}, {0,1,0}  };
int[][] faceList   = {  {4,3,0},  {4,0,1},  {4,1,2},  {4,2,3},  {0,3,2,1}  };

Note that each vertex is repeated three or four times in the face-list array. With the IFS representation, a vertex is represented in the face list by a single integer, giving an index into the vertex list array. This representation uses significantly less memory space than the alternative, which would be to write out the vertex in full each time it occurs in the face list. For this example, the IFS representation uses 31 numbers to represent the polygonal mesh. as opposed to 48 numbers for the alternative.

IFSs have another advantage. Suppose that we want to modify the shape of the polygon mesh by moving its vertices. We might do this in each frame of an animation, as a way of "morphing" the shape from one form to another. Since only the positions of the vertices are changing, and not the way that they are connected together, it will only be necessary to update the 15 numbers in the vertex list. The values in the face list will remain unchanged. So, in this example, we would only be modifying 15 numbers, instead of 48.

Suppose that we want to use the IFS data to draw the pyramid. It's easy to generate the OpenGL commands that are needed to generate the vertices. But to get a correct rendering, we also need to specify normal vectors. When the IFS represents an actual polyhedron, with flat faces, as it does in this case, we can compute a normal vector for each polygon, as discussed in Subsection 3.1.1. (In fact, if P1, P2, and P3 are the first three vertices of the polygon, then the cross product (P3P2)×(P1P2) is the desired normal as long as the three points do not lie on a line.) Let's suppose that we have a method, computeUnitNormalForPolygon, to compute the normal for us. Then the object represented by an IFS can be generated from the vertexList and faceList data with the following simple method:

static void drawIFS(GL gl, float[][] vertexList, int[][] faceList) {
    for (int i = 0; i < faceList.length; i++) {
       gl.glBegin(GL.GL_POLYGON);
       int[] faceData = faceList[i];  // List of vertex indices for this face.
       float[] normal = computeUnitNormalForPolygon(vertexList, faceData);
       gl.glNormal3fv( normal, 0 );
       for (int j = 0; j < faceData.length; j++) {
           int vertexIndex = faceData[j];  // Location of j-th vertex in list.
           float[] vertex = vertexList[ vertexIndex ];
           gl.glVertex3fv( vertex, 0 );
       }
       gl.glEnd();
    }
}

This leaves open the question of what to do about normals for an indexed face set that is meant to approximate a smooth surface. In that case, we want to use normals that are perpendicular to the surface, not to the polygons. One possibility is to expand our data structure to store a normal vector for each vertex, as we will do in the next subsection. Another possibility, which can give nice-looking results, is to calculate an approximate normal for each vertex from the data that we have. To do this for a particular vertex v, consider all the polygons in which v is a vertex. Compute vectors perpendicular to each of those polygons, and then use the average of all those vectors as the normal vector at v. Although that vector is probably not exactly perpendicular to the surface at v, it is usually good enough to pass visual inspection of the resulting image.


Before moving on, lets think about making a minor change to the way that we have stored the data for the vertex list. It is common in OpenGL to store this type of data in a one-dimensional array, instead of a two dimensional array. Store the first vertex in the first three array elements, the second vertex in the next three, and so on:

float[] vertexList = {  1,0,1, 1,0,-1, -1,0,-1, -1,0,1, 0,1,0  };

In general, the data for vertex number n will be stored starting at position 3*n in the array. Recall that the second parameter to gl.glVertex3fv gives the position in the array where the data for the vertex is stored. So, to use our modified data, we can now draw the IFS as follows:

static void drawIFS(GL gl, float[] vertexList, int[][] faceList) {
    for (int i = 0; i < faceList.length; i++) {
       gl.glBegin(GL.GL_POLYGON);
       int[] faceData = faceList[i];  // List of vertex indices for this face.
       float[] normal = computeUnitNormalForPolygon(vertexList, faceData);
       gl.glNormal3fv( normal, 0 );
       for (int j = 0; j < faceData.length; j++) {
           int vertexIndex = faceData[j];
           gl.glVertex3fv( vertexList, 3*vertexIndex );
       }
       gl.glEnd();
    }
}

This representation will be convenient when we look at new methods for drawing OpenGL primitives in the next section.


3.3.2  OBJ Files

For complex shapes that are not described by any simple mathematical formula, it's not feasible to generate the shape using Java code. We need a way to import shape data into our programs from other sources. The data might be generated by physical measurement, for example, or by an interactive 3D modeling program such as Blender (http://www.blender.org). To make this possible, one program must write data in a format that can be read by another program. The two programs need to use the same graphics file format. One of the most common file formats for the exchange of polygonal mesh data is the Wavefront OBJ file format. Although the official file format can store other types of geometric data, such as Bezier curves, it is mostly used for polygons, and that's the only use that we will consider here.

An OBJ file (with file extension ".obj") can store the data for an indexed face set, plus normal vectors and texture coordinates for each vertex. The data is stored as plain, human-readable text, using a simple format. Lines that begin with "v", "vn", "vt", or "f", followed by a space, contain data for one vertex, one normal vector, one set of texture coordinates, or one face, respectively. For our purposes here, other lines can be ignored.

A line that specifies a vertex has the form v x y z, where x, y, and z are numeric constants giving the coordinates of the vertex. For example:

v  0.707  -0.707  1

Four numbers, specifying homogeneous coordinates, are also legal but, I believe, rarely used. All the "v" lines in the file are considered to be part of one big list of vertices, and the vertices are assigned indices based on their position in the list. The indices start at one not zero, so vertex 1 is the vertex specified by the first "v" line in the file, vertex 2 is specified by the second "v" line, and so on. Note that there can be other types of lines interspersed among the "v" lines -- those extra lines are not counted when computing the index of a vertex.

Lines starting with "vn" or "vt" work very similarly. Each "vn" line specifies a normal vector, given by three numbers. Normal vectors are not required to be unit vectors. All the "vn" lines in the file are considered to be part of one list of normal vectors, and normal vectors are assigned indices based on their order in the list. A "vt" line defines texture coordinates with one, two, or three numbers. (Two numbers would be used for 2D image textures.) All the "vt" lines in the file create a list of texture coordinates, which can be referenced by their indices in the list.

Faces are more complicated. Each "f" line defines one face, that is, one polygon. The data on the "f" line must give the list of vertices for the face. The data can also assign a normal vector and texture coordinates to each vertex. Vertices, texture coordinates, and normals are referred to by giving their indices in the respective lists. (Remember that the numbering starts from one, not from zero; if you've stored the data in Java arrays, you have to subtract 1 from the numbers given in the "f" line to get the correct array indices. There reference numbers can be negative. A negative index in an "f" line means to count backwards from the position of the "f" line in the file. For example, a vertex index of −1 refers to the "v" line that was seen most recently in the file, before encountering the "f" line; a vertex index of −2 refers the "v" line that precedes that one, an so on. If you are reading the file sequentially and storing data in arrays as you go, then −1 simply refers to the last item that is currently in the array, −2 refers to the next-to-last item, and so on.)

In the simple case, where there are no normals or texture coordinates, an "f" line can simply list the vertex indices in order. For example, an OBJ file for the pyramid example from the previous subsection could look like this:

v 1 0 1
v 1 0 -1
v -1 0 -1
v -1 0 1
v 0 1 0
f 5 4 1
f 5 1 2
f 5 2 3
f 5 3 4
f 1 4 3 2

When texture coordinate or normal data is included, a single vertex index such as "5" is replaced by a data element in the format v/t/n, where v is a vertex index, t is a texture coordinates index, and n is a normal coordinate index. The texture coordinates index can be left out, but the two slash characters must still be there. For example, "5/3/7" specifies vertex number 5, with texture coordinates number 3, and normal vector number 7. And "2//1" specifies vertex 2 with normal vector 7. As an example, here is complete OBJ file representing a cube, with its normal vectors, exactly as exported from Blender. Note that it contains additional data lines, which we want to ignore:

# Blender3D v248 OBJ File: 
# www.blender3d.org
mtllib stage.mtl
v 1.000000 -1.000000 -1.000000
v 1.000000 -1.000000 1.000000
v -1.000000 -1.000000 1.000000
v -1.000000 -1.000000 -1.000000
v 1.000000 1.000000 -1.000000
v 0.999999 1.000000 1.000001
v -1.000000 1.000000 1.000000
v -1.000000 1.000000 -1.000000
vn -0.000000 -1.000000 0.000000
vn 0.000000 1.000000 -0.000000
vn 1.000000 0.000000 0.000000
vn -0.000000 -0.000000 1.000000
vn -1.000000 -0.000000 -0.000000
vn 0.000000 0.000000 -1.000000
usemtl Material
s off
f 1//1 2//1 3//1 4//1
f 5//2 8//2 7//2 6//2
f 1//3 5//3 6//3 2//3
f 2//4 6//4 7//4 3//4
f 3//5 7//5 8//5 4//5
f 5//6 1//6 4//6 8//6

Once you have read a geometric object from an OBJ file and stored the data in arrays, it is easy enough to use the arrays to draw the object with OpenGL.


3.3.3  Terraine and Grids

We look at one more common type of polygonal mesh, which occurs when the vertices in the mesh form a grid or net. A typical example in computer graphics programs would be to represent the ground or terrain by specifying the height of the ground at each point in a grid. That is, for example, we could use a two-dimensional array height[i][j], for 0 <= i <= N and 0 <= j <= N, to give the height of the ground over each of the points (i/N,j/N). (This defines the ground height only over a square that is one unit on a side, but we can easily scale to extend the terrain over a larger square.) The ground would then be approximated by a polygonal mesh containing the points (i/N,height[i][j],j/N), with the points joined by line segments. The result might look something like this (although certainly a larger value of N would be desirable):

Imagine looking down from above at the original grid of points and at the same grid connected by lines:

You can see that the geometry consists of N horizontal "strips." Each of these strips can be drawn using the GL_TRIANGLE_STRIP primitive. Again, we have to worry about normal vectors, but let's assume again that we have a way to compute them (although the computation in this case is more difficult than for indexed face sets). If we have a texture that we want to apply to the terrain, we can do so easily. As we have set things up, all the original grid points have xz-coordinates in the unit square, and we can simply use those coordinates as texture coordinates. We can then use the following method to draw the terrain

static void drawTerrain(GL gl, float[][] height, int N) {
    for (int row = 0; row < N; row++) {
       gl.glBegin(GL.GL_TRIANGLE_STRIP);
       // Draw strip number row.
       for (int col = 0; col <= N; col++) {
           // Generate one pair of points on the strip, at horizontal position col.
           float x1 = (float)col/N;     // Upper point on strip.
           float y1 = height[row+1][col];
           float z1 = (float)(row+1)/N;
           float[] normal1 = computeTerrainUnitNormal(height,N,row+1,col);
           gl.glNormal3fv( normal1, 0 );
           gl.glTexCoord2f( x1, z1 );
           gl.glVertex3f( x1, y1, z1 );
           float x2 = (float)col/N;     // Lower point on strip.
           float y2 = height[row][col];
           float z2 = (float)row/N;
           float[] normal2 = computeTerrainUnitNormal(height,N,row,col);
           gl.glNormal3fv( normal2, 0 );
           gl.glTexCoord2f( x2, z2 );
           gl.glVertex3f( x2, y2, z2 );
       }
       gl.glEnd();
    }
}

For readers with some background in calculus, this example is actually just a special case of drawing the graph of a mathematical function of two variables by plotting some points on the surface and connecting them to form lines and triangles. In that case, thinking of the function as giving y = f(x,z), we would use the points (x,f(x,z),z) for a grid of points (x,z) in the xz-plane.

The graph of the function is a surface, which will be smooth if f is a differentiable function. We are approximating the smooth surface by a polygonal mesh, so we would like to use normal vectors that are perpendicular to the surface. The normal vectors can be calculated from the partial derivatives of f.

More generally, we can easily draw a polygonal approximation of a parametric surface given by a set of three functions of two variables, x(u,v), y(u,v), and z(u,v). Points on the surface are given by (x,y,z) = (x(u,v), y(u,v), z(u,v)). The surface defined by a rectangular area in the uv-plane can be approximated by plotting points on the surface for a grid of uv-points in that rectangle and using the resulting points to draw a sequence of triangle strips. The normal at a point on the surface can be computed from partial derivatives. In fact, if we use the notation Du to mean the partial derivative with respect to u and Dv for the partial derivative with respect to v, then a normal at the point (x(u,v), y(u,v), z(u,v)) is given by the cross product

(Dux(u,v), Duy(u,v), Duz(u,v)) × (Dvx(u,v), Dvy(u,v), Dvz(u,v))

In fact, it's not even necessary to compute exact formulas for the partial derivatives. A rough numerical approximation, using the difference quotient, is good enough to produce nice-looking surfaces.


[ Previous Section | Next Section | Chapter Index | Main Index ]