Saturday, December 20, 2008

More on OpenGL and Normals

In an earlier post I talked about surface normals in OpenGL. In writing the Wavefront OBJ loading class, I've learned far more about normals than I ever wanted to know. Among those things I learned is that there are two different kinds of normals - surface normals, which are what I talked about in the surface normals posting, and vertex normals.

Finding a nice, simple explanation of what vertex normals is, is not actually that easy. Which is a shame, because it's really not a difficult concept. A vertex normal is simply the average of the surface normals of all the polygons that a particular vertex is part of. Look at the following image:



That's not a cube, by the way, For simplicity, we're looking at a flat, two-dimensional mesh of six triangles. There are a total of seven vertices used to make the shape. That vertex marked A is shared by all six triangles, so the vertex normal for that vertex is the average of the surface normals for all seven triangles. Averaging is done per element, so the x values are averaged, the y values are averaged, and the z values are averaged, and the result, put into a new Vector3D is the average vector.

Let's look at how these were calculated in the Wavefront OBJ loader:

GL_FLAT and Surface Normals


If we're using GL_FLAT shading, the array of normals we need to build for the mesh pictured above will have six vectors in it, which means eighteen GLfloats. Each vector in that array needs to be the normalized surface normal for one triangle, and the normals need to be in the array in the same order that the triangles are passed into glDrawElements().

Here's how we can calculate the surface normal again (this is a slightly different algorithm than the one in my previous posting). The second function calculates the surface normal, but uses the first function.

static inline Vector3D Vector3DMakeWithStartAndEndPoints(Vertex3D start, Vertex3D end)
{
Vector3D ret;
ret.x = end.x - start.x;
ret.y = end.y - start.y;
ret.z = end.z - start.z;
vectorNormalize(&ret);
return ret;
}

static inline Vector3D Triangle3DCalculateSurfaceNormal(Triangle3D triangle)
{
Vector3D u = Vector3DMakeWithStartAndEndPoints(triangle.v2, triangle.v1);
Vector3D v = Vector3DMakeWithStartAndEndPoints(triangle.v3, triangle.v1);

Vector3D ret;
ret.x = (u.y * v.z) - (u.z * v.y);
ret.y = (u.z * v.x) - (u.x * v.z);
ret.z = (u.x * v.y) - (u.y * v.x);
return ret;
}

So, to create the array of normals for GL_FLAT, we simply need to loop through the triangles (in the same order we'll later loop through them to draw them, and call Triangle3DCalculateSurfaceNormal(), storing the results in an array of GLfloats or Vector3D (remember, one Vector3D is the same as an array of three GLfloats.

GL_SMOOTH and Vertex Normals


Now, if we're using a shading model of GL_SMOOTH, however, we need to pass in a different normal array - an array of vertex normals. And this time, instead of passing an array that contains one normal for each triangle, we need to pass one normal for each vertex, in the same order that the vertices appear in the vertex array that we pass to OpenGL using GLVertexPointer(). For speed and simplicity, I calculate both surface and vertex normals in the same method in the Wavefront OBJ loader:
- (void)calculateNormals
{
if (surfaceNormals)
free(surfaceNormals);

// Calculate surface normals and keep running sum of vertex normals
surfaceNormals = calloc(numberOfFaces, sizeof(Vector3D));
vertexNormals = calloc(numberOfVertices, sizeof(Vector3D));

NSUInteger index = 0;
NSUInteger *facesUsedIn = calloc(numberOfVertices, sizeof(NSUInteger)); // Keeps track of how many triangles any given vertex is used in
for (int i = 0; i < [groups count]; i++)
{
OpenGLWaveFrontGroup *oneGroup = [groups objectAtIndex:i];
for (int j = 0; j < oneGroup.numberOfFaces; j++)
{
Triangle3D triangle = Triangle3DMake(vertices[oneGroup.faces[j].v1], vertices[oneGroup.faces[j].v2], vertices[oneGroup.faces[j].v3]);

surfaceNormals[index] = Triangle3DCalculateSurfaceNormal(triangle);
vectorNormalize(&surfaceNormals[index]);
vertexNormals[oneGroup.faces[j].v1] = Vector3DAdd(surfaceNormals[index], vertexNormals[oneGroup.faces[j].v1]);
vertexNormals[oneGroup.faces[j].v2] = Vector3DAdd(surfaceNormals[index], vertexNormals[oneGroup.faces[j].v2]);
vertexNormals[oneGroup.faces[j].v3] = Vector3DAdd(surfaceNormals[index], vertexNormals[oneGroup.faces[j].v3]);

facesUsedIn[oneGroup.faces[j].v1]++;
facesUsedIn[oneGroup.faces[j].v2]++;
facesUsedIn[oneGroup.faces[j].v3]++;


index++;
}
}

// Loop through vertices again, dividing those that are used in multiple faces by the number of faces they are used in
for (int i = 0; i < numberOfVertices; i++)
{
if (facesUsedIn[i] > 1)
{
vertexNormals[i].x /= facesUsedIn[i];
vertexNormals[i].y /= facesUsedIn[i];
vertexNormals[i].z /= facesUsedIn[i];
}
vectorNormalize(&vertexNormals[i]);

}
free(facesUsedIn);
}
The basic idea is that as we loop through the triangles, we keep track of how many times each vertex is used, and every time we use one, we add the surface normal of the triangle to the vertex array element corresponding to the vertex being used. When we're all done, we loop through the vertices, dividing vertex array, which has the sum of all the surface normals for all the triangles in which that vertex is used, and divide it by the number of triangles it's used in.

One thing that you might have noticed is that I used calloc() rather than malloc(). These two calls do pretty much the same thing, except that calloc initializes all elements to 0, which is important when you're doing running counts and adding values rather than setting values.

Now, on to texture mapping...



3 comments:

Eric said...

I can't wait to see more on textures, as I seem to struggle with them most out of anything I've tried so far.

Anytime my RSS shows a new post on this blog I can't wait to see it. :)

fenster said...

Thanks man, your blog is awesome. These topics are not easy, and take a lot of time to get to grips with. Thanks for putting it in, and hope to be able to help you out in the future.

h4ns said...

What youre saying is completely true. I know that everybody must say the same thing, but I just think that you put it in a way that everyone can understand. I also love the images you put in here. They fit so well with what youre trying to say. Im sure youll reach so many people with what youve got to say.

Arsenal vs Huddersfield Town live streaming
Arsenal vs Huddersfield Town live streaming
Wolverhampton Wanderers vs Stoke City Live Streaming
Wolverhampton Wanderers vs Stoke City Live Streaming
Notts County vs Manchester City Live Streaming
Notts County vs Manchester City Live Streaming
Bologna vs AS Roma Live Streaming
Bologna vs AS Roma Live Streaming
Juventus vs Udinese Live Streaming
Juventus vs Udinese Live Streaming
Napoli vs Sampdoria Live Streaming
Napoli vs Sampdoria Live Streaming
Fulham vs Tottenham Hotspur Live Streaming
Fulham vs Tottenham Hotspur Live Streaming
AS Monaco vs Marseille Live Streaming
AS Monaco vs Marseille Live Streaming
Alajuelense vs Perez Zeledon Live Streaming
Alajuelense vs Perez Zeledon Live Streaming
Technology News | News Today | Live Streaming TV Channels