Tuesday, August 7, 2012

3D Programming and Calculating Normals

So, I've had a really difficult time with calculating normal vectors (herein referred to as "normals") in OpenGL, and I've learned a lot to make sense of it, finally.  There are a few good tutorials, but they still don't explain everything you want to know.  So, I've decided to post about how they work and how to build them.

A normal is a vector that describes a direction perpendicular (pointing away) to a point (i.e. a vertex) or a face (i.e. a polygon).  It is important for lighting, since light needs to know how to reflect off of something.  I always figured lighting should be able to figure this out -- I mean, why shouldn't it?  However, that's another topic entirely.

Vertex and face normals serve their purposes.  For example, streamlined terrain generally looks better with vertex normals.  Since OpenGL blends the colors (and therefore lighting) between each point, you'll see a gradient between all vertices of your polygon with normals.  A face normal will basically have one normal for a vertex be applied to all vertices in the polygon, so the polygon as a whole will be flat with its lighting and uniformly lit/shaded.  This looks great for something like a cube where you'll want clear lines separating the object faces.  This looks really terrible on terrain.

For the sake of this tutorial, I'm going to explain how to calculate a face normal.  Since all polygons are composed of triangles, I will be using a triangle for our face.  You can calculate a face normal by averaging all of the normals in a complex polygon together (using a geometric average is the ideal way, but sometimes slow).

So, suppose we have a triangle with vertices A, B, and C.

We need to calculate the individual vectors and multiply them together.  Please note that you need to observe the right-hand rule when calculating the normals, such that you need to always build normals or vertices in the same order.  For example, in my example above, ABC is built counter-clockwise, from A to B to C.  Some people build their triangles in a format where the vertices A, B, C are the upper left corner, upper right corner, and then the lower left corner (whereas mine are upper left corner, lower left corner, and lower right corner, respectfully).  In the alternate case, it would built clockwise.  However, there are a number of ways to build a triangle -- just make sure you either build them all clockwise or counter-clockwise.  Make sure that each triangle is calculated in the same order as the prior.

From here, we need to calculate the vector of each component.  We use the middle vertex of a triangle (again, this can change based on how you build your triangles).  For my version, it is "B."  So, we want to calculate the vector of each direction around this "pivot" vertex.

Simply put, we will have two vectors, U and V, which will be built as follows:

U = B - A
V = C - B

To do vector addition and subtraction, we just add/subtract the components, so simply put...

method AddVectors( Vertex A, Vertex B )
  create Vector where Vector.X = A.X + B.X, Vector.Y = A.Y + B.Y, Vector.Z = A.Z + B.Z;

Now that we have U and V, we'll have to multiply the two vectors together... which is a bit more painful.

method MultiplyVectors( Vector U, Vector V )
  create MultipliedVector;
  MultipliedVector.X = ( ( U.Y x V.Z ) - ( U.Z x V.Y ) );
  MultipliedVector.Y = ( ( U.Z x V.X ) - ( U.X x V.Z ) );
  MultipliedVector.Z = ( ( U.X x V.Y ) - ( U.Y x V.X ) );

Aren't you glad we used vector names U and V, instead of X and Y?  That code would be impossible to read!

Now, you have a "normal" of the face of the triangle -- but you're STILL not done.  The normal should be normalized to a unit length.  If you want to calculate a vertex normal, you may save this operation until after you're finished calculating all of your face normals.

To normalize a vertex, you need to find the unit length, which is done with Pythagorean's theorem.

The unit length is built as follows with a vector T:

UnitLength = SquareRoot( ( T.X x T.X ) + ( T.Y x T.Y ) + ( T.Z x T.Z ) );

Then, divide each component of the normal by the unit length as follows:

T.X = T.X / UnitLength;
T.Y = T.Y / UnitLength;
T.Z = T.Z / UnitLength;

You have now "normalized" your normal.

But wait, there's more!  We really wanted to get the vertex normals!

We can calculate a vertex normal by adding all of the face normals that a vertex is used in and then performing the normalization we did prior after.

Suppose we use a data structure (I have a persistent Dictionary<int, Dictionary<int, Vertex>> object I use) that contains all of the vertices of a mesh by their X, Y values.  X, Y would refer to the X and Y coordinates of the triangle mesh, which in my case (and many others) are generally uniform distance from each other (i.e. always 1 unit away from the other).

Assume my earlier triangle now has another point directly above C, called D.  We now have a quadrangle.

Assume my format has several of these next to each other to make a surface of terrain or something else.  Assume that these share points, such that D and C become the next A and B vertices for a quad that would have an E and F added on.  (i.e. quad one is built with A, B, C, D; quad two is built with D, C, E, F)

Assume also, I can calculate a face normal by providing three vertices of a triangle with the method CalculateNormal.  This would utilize the same pseudo-code mentioned above.

I could loop through a mesh as follows:

normals = create Dictionary[int][int] containing Vector;

for( y = 0; y < mesh.Height - 1; y++ )
  for( x = 0; x < mesh.Width - 1; x++ )
    //Triangle ABC
    Vector normal = CalculateNormal( mesh[x][y], mesh[x][y + 1], mesh[x + 1][y + 1] );
    //Add the normal components to the vertices that are used
    normals[x][y] += normal;
    normals[x][y + 1] += normal;
    normals[x + 1][y + 1] += normal;

    //Triangle ACD
    normal = CalculateNormal( mesh[x][y], mesh[x + 1][y + 1], mesh[X + 1][y] );

    //Add the normal components to the vertices that are used
    normals[x][y] += normal;
    normals[x + 1][y + 1] += normal;
    normals[x + 1][y] += normal;
At this point I would have all of my normals added up, but they'd be huge and non-normalized.  So, we'd normalize them by calculating the unit length as I did for a face normal, and then finally dividing the components by that unit length.

That, my friends, is how you would go about building normals from a uniform mesh with differing heights.