Calculating normals in a triangle mesh
Solution 1:
Does each vertex have its own normals or does each triangle have its own normals?
Like so often the answer is: "It depends". Since a normal is defined as being the vector perpendicular to all vectors within a given plane (in N dimensions), you need a plane to calculate a normal. A vertex position is just a point and thus singular, so you actually need a face to calculate the normal. Thus, naively, one could assume that normals are per face as the first step in normal calculation is determining the face normals, by evaluating the cross product of the faces edges.
Say you have a triangle with points A, B, C, then these points have position vectors ↑A, ↑B, ↑C and the edges have vectors ↑B - ↑A and ↑C - ↑A so the face normal vector is ↑Nf = (↑B - ↑A) × (↑C - ↑A)
Note that the magnitude of ↑Nf as it's stated above is directly proportional to the face's area.
In smooth surfaces vertices are shared between faces (or you could say those faces share a vertex). In that case the normal at the vertex is not one of the face normals of the faces it is part of, but a linear combination of them:
↑Nv = ∑ p ↑Nf ; where p is a weighting for each face.
One could either assume a equal weighting between the participating face normals. But it makes more sense to assume that the larger a face is, the more it contributes to the normal.
Now recall that you normalize by a vector ↑v by scaling it with it's recipocal length: ↑vi = ↑v/|↑v|. But as already told the length of the face normals already depends on the face's area. So the weighting factor p given above is already contained in the vector itself: Its length, aka magnitude. So we can get the vertex normal vector by simply summing up all the face normals.
In lighting calculations the normal vector must be unit length, i.e. normalized to be useable. So after summing up, we normalize the newly found vertex normal and use that.
The carefull reader may have noticed I specifically said smooth surfaces share vertices. And in fact, if you have some creases / hard edges in your geometry, then the faces on either side don't share vertices. In OpenGL a vertex is the whole combination of
- position
- normal
- (colour)
- N texture coordinates
- M further attributes
You change one of these and you got a completely different vertex. Now some 3D modelers see a vertex only as a point's position and store the rest of those attributes per face (Blender is such a modeler). This saves some memory (or considerable memory, depending on the number of attributes). But OpenGL needs the whole thing, so if working with such a mixed paradigm file you will have to decompose it into OpenGL compatible data first. Have a look at one of Blender's export scripts, like the PLY exporter to see how it's done.
Now to cover some other thing. In your code you have this:
glIndexPointer( GL_UNSIGNED_BYTE, 0, indices );
The index pointer has nothing to do with vertex array indices! This is an anachronsim from the days, when graphics still used palettes instead of true color. A pixels colour wasn't set by giving it's RGB values, but by a single number offsetting into a limited palette of colours. Palette colours can still be found in several graphics file formats, but no decent piece of hardware uses them anymore.
Please erase glIndexPointer (and glIndex) from your memory and your code, they don't do what you think they do The whole indexed color mode is arcane to used, and frankly I don't know of any hardware built after 1998 that still supported it.
Solution 2:
Thumbs up for datenwolf! I completely agree with his approach. Adding the normal vectors of the adjacent triangles for each vertex and then normalising is the way to go. I just want to push the answer a little bit and have a closer look at the particular but quite common case of a rectangular, smooth mesh that has a constant x/y step. In other words, a rectangular x/y grid with a variable height at each point.
Such a mesh is created by looping over x and y and setting a value for z and can represent things like the surface of a hill. So each point of the mesh is represented by a vector
P = (x, y, f(x,y))
where f(x,y) is a function giving the z of each point on the grid.
Usually to draw such a mesh we use a TriangleStrip or a TriangleFan but any technique should give a similar topography for the resulting triangles.
|/ |/ |/ |/
...--+----U----UR---+--...
/| /| 2 /| /| Y
/ | / | / | / | ^
| / | / | / | / |
|/ 1 |/ 3 |/ |/ |
...--L----P----R----+--... +-----> X
/| 6 /| 4 /| /|
/ | / | / | / |
| /5 | / | / | /
|/ |/ |/ |/
...--DL---D----+----+--...
/| /| /| /|
For a triangleStrip each vertex P=(x0, y0, z0) has 6 adjacent vertices denoted
up = (x0 , y0 + ay, Zup)
upright = (x0 + ax, y0 + ay, Zupright)
right = (x0 + ax, y0 , Zright)
down = (x0 , y0 - ay, Zdown)
downleft = (x0 - ax, y0 - ay, Zdownleft)
left = (x0 - ax, y0 , Zleft)
where ax/ay is the constant grid step on the x/y axis respectively. On a square grid ax = ay.
ax = width / (nColumns - 1)
ay = height / (nRows - 1)
Thus each vertex has 6 adjacent triangles each one with its own normal vector (denoted N1 to N6). These can be calculated using the cross product of the two vectors defining the side of the triangle and being careful on the order in which we do the cross product. If the normal vector points in the Z direction towards you :
N1 = up x left =
= (Yup*Zleft - Yleft*Zup, Xleft*Zup - Xup*ZLeft, Xleft*Yup - Yleft*Xup)
=( (y0 + ay)*Zleft - y0*Zup,
(x0 - ax)*Zup - x0*Zleft,
x0*y0 - (y0 + ay)*(x0 - ax) )
N2 = upright x up
N3 = right x upright
N4 = down x right
N5 = downleft x down
N6 = left x downleft
And the resulting normal vector for each point P is the sum of N1 to N6. We normalise after summing. It's very easy to create a loop, calculate the values of each normal vector, add them and then normalise. However, as pointed out by Mr. Shickadance, this can take quite a while, especially for large meshes and/or on embedded devices.
If we have a closer look and perform the calculations by hand, we will find out that most of the terms cancel out each other, leaving us with a very elegant and easy to calculate final solution for the resulting vector N. The point here is to speed up calculations by avoiding calculating the coordinates of N1 to N6, doing 6 cross-products and 6 additions for each point. Algebra helps us to jump straight to the solution, use less memory and less CPU time.
I will not show the details of the calculations as it is long but straight-forward and will jump to the final expression of the Normal vector for any point on the grid. Only N1 is decomposed for the sake of clarity, the other vectors look alike. After summing we obtain N which is not yet normalized :
N = N1 + N2 + ... + N6
= .... (long but easy algebra) ...
= ( (2*(Zleft - Zright) - Zupright + Zdownleft + Zup - Zdown) / ax,
(2*(Zdown - Zup) + Zupright + Zdownleft - Zup - Zleft) / ay,
6 )
There you go! Just normalise this vector and you have the normal vector for any point on the grid, provided you know the Z values of its surrounding points and the horizontal/vertical step of your grid.
Note that this is the weighed average of the surrounding triangles' normal vectors. The weight is the area of the triangles and is already included in the cross product.
You can even simplify it more by only taking into account the Z values of four surrounding points (up,down,left and right). In that case you get :
| \|/ |
N = N1 + N2 + N3 + N4 ..--+----U----+--..
= ( (Zleft - Zright) / ax, | /|\ |
(Zdown - Zup ) / ay, | / | \ |
2 ) \ | / 1|2 \ | /
\|/ | \|/
..--L----P----R--...
/|\ | /|\
/ | \ 4|3 / | \
| \ | / |
| \|/ |
..--+----D----+--..
| /|\ |
which is even more elegant and even faster to calculate.
Hope this will make some meshes faster. Cheers
Solution 3:
Per-vertex.
Use cross-products to calculate the face normals for the triangles surrounding a given vertex, add them together, and normalize.