Quick History of Normal Calculations of Polyhedra

Different methods and who pioneered them
The study of computer graphics is still relatively new and has only been an in-depth field for about 40 years. Among the mathematicians and computer scientists who pioneered the field is French Computer Scientist Henri Gouraud. Gouraud is best noted for his research in Smooth shading, often called Gouraud Shading. In 1971 Gouraud released a book titled "Continuous Shading of Curved Surfaces." In the book Gouraud describes the most common method for computing normals. In the remainder of the article we will refer to his algorithm as "Mean Weighted Equally" (MWE). In essence, Gouraud suggested that if you were to compute the normals of each of the facets (surfaces) of a polyhedron then you could get relatively smooth shading by then taking all of the facets which are "attached" to a single vertex and averaging the surface normals. In this way, each surface normal contributes equally to the vertex normal – the vector representing the normal to the polyhedron at that vertex.

Gouraud's algorithm would remain the defacto algorithm for computing per-vertex lighting for more than 20 years. In 1997 however, two German Computer Scientists Thürmer & Wüthrich, proposed a new method for computing normals which was mathematically more accurate. Their algorithm, which is referred to as "Mean Weighted by Angle" (MWA), suggested that facets which are "attached" to a vertex normal should have their contribution to the vertex normal weighted by the angle of the triangle that the vertex is part of. In other words, all three vertices of a triangle have the same surface normal, however, the surface normal can be multiplied by each of the angles of the triangle in order to create three new normals which are weighted versions of the surface normal. These new normals could then be used to compute vertex normals in place of the surface normals used previously.

Not long after Thürmer & Wüthrich proposed their new algorithm a man named Nelson Max published his findings in the Journal of Graphics Tools describing four additional algorithms. I will list these here for brevity, however experiments have been done which show these methods are neither as accurate as MWA or as fast as MWE. For this reason, we will not be exploring these methods further. "Mean Weighted by Sine and Edge Length Reciprocal," "Mean Weighted by Areas of Adjacent Triangles," "Mean Weighted by Edge Length Reciprocals," and "Mean Weighted by Square Root of Edge Length Reciprocals."

Heightfields

What are heightfields used for?
Heightfields serve one primary purpose in video games – to act as the terrain upon which your actors move around and experience the world. To this degree, depending upon the genre of game you're making, players may spend a large amount of time looking at the terrain. With this in mind, it is often desirable to have a terrain which is realistic and attractive to look at. The most effective way to make this possible is by the use of lighting, shadows, textures, etc. Since we're focused primarily on lighting in this article, I'll leave the other elements for another time. Let's take a more detailed look at heightfields.

Heightfield general principles
At the most basic level a heightfield is a one or two dimensional array of data which represents the height of a piece of terrain at a specific (x, z) point in space. In other words, if you were to look at the [x][z] offset within a 2d array or compute the associated index into a one-dimensional array, the value at that location in memory would be the height at point X, Z. The index into a one dimensional array can be computed with the following equation, where numVertsWide is how many vertices are on your terrain in the x dimension:

index ═ z * numVertsWide + x

The value in memory can be stored as either a floating point value or an integer. In the case of an integer, the values are often stored as a 1 byte (8 bits) or 4 byte (32 bits) block of memory. When the height values are stored as 8-bit integers the heightfield can easily be saved and loaded to disk in the form of a grayscale bitmap. This makes it possible to use a standard image editing application to modify the terrain offline. The same can be done with a 32 bit value, but the alpha value and colors become less intuitive to work with in an image editing program.

When the value in memory is stored as an 8 bit integer it is also common to multiply the height values by a vertical scale component. This enables the heightfield to cover elevations of greater and lower than 255. Depending on the resolution of your terrain, however, 8 bit integers can often seem blocky and unrealistic. For the purpose of this article and demo, we will use 32 bit, single precision Floating Point values to represent height.

In addition to having a vertical scale factor in the case of 8 bit heightfield, it is also common in all cases to have a horizontal scale factor. The reason for this is quite simple. When using indices for your x,z pairs it would force all of your vertices to reside along 1 meter (world units) intervals (i.e. X = 0, 1, 2, 3….Z = 0, 1, 2, 3). As with using 8 bit values for height, forcing your vertices to reside 1 meter apart could cause the terrain to seem unrealistic in many cases. The horizontal scale factor, sometimes called "Scale" or "Units Per Vertex" allows your vertices to be spaced in distances greater or smaller than 1.0. For example, if your scale factor is 0.5f, then all of your vertices would be 0.5 meters apart, leading to more vertices in the same amount of space, and causing your terrain to be a higher "Resolution." It should be noted here that "Scale" and "Resolution" are inversely proportional. As your scale increases, causing a greater distance between your vertices, your resolution, or the complexity of the terrain, decreases.

Finally, although we represent a heightfield as a single array of floating point values in this article, it is common for culling and rendering purposes to break a large heightfield up into smaller "tiles." If this is what you're trying to do, you can think of the heightfield in this article as being a single tile of the larger system. Ultimately, tiling your heightfield means creating a mapping between tiles and vertices, and also extending your normal calculations to take into account the heights of vertices in tiles adjacent to the current tile. You will see later that our algorithm for computing surface normals already takes tiling into account, and with little modification you can get these algorithms to work within a tiled terrain system.

Normal Calculations for Heightfields