The following code assumes that a vertex array exists, a face array exists (where faces are simply a set of indices into the vertex array) and that suitable data structures for holding 3D vectors, faces etc. exist.
// Step 1: Initialize all the vertices to (0,0,0)
foreach vertex v{
v = Vertex3D(0,0,0);
}
// Step 2: Assign normals...
foreach face f1{
Vector faceNormal = CrossProduct(f1.v1-f1.v0, f1.v2-f1.v0);
foreach vertex v1 in f1{
if (v1.normal is not initialized){
v1.normal = faceNormal;
}
else{
if (condition for not smoothing){
/* duplicate v1 */
/* set the index in f1 to the index
of the duplicated vertex*/
/* set the normal of the duplicated vertex to
be the normal of f1*/
}
else{
v1.normal += faceNormal;
}
}
}
}
// Step 3: Average normals in vertices that were stupidly
// duplicated (optional - but necessary for .3DS file loading)
foreach vertex v1{
foreach vertex v2{
if (v1 == v2){
continue;
}
if (v1.position == v2.position && condition for smoothing
e.g., v1.smoothgrp == v2.smoothgrp){
v1.position = v2.position;
v1.normal += v2.normal;
v2.normal += v1.normal;
}
}
}
// Step 4: Normalize every normal
foreach vertex v{
v.normalize();
}
Explanation:
In step 1 we make sure all normals are initialized to a null vector so that we can add onto them without any consequences (as we do in the next part of the algorithm). In step 2 we iterate through each face and calculate its face normal (this would be the normal of all its vertices in the case of a purely faceted mesh). With this normal we can now pick and choose what vertices will average that with other face normals and which will actually be faceted/unsmoothed.
I have placed the phrase "condition for not smoothing", typically this can be derived from smoothing groups (e.g., in the case of .3DS file loading we could check to see if the smoothing group associated with v1 isn't the same as f1's) or it could be derived from the angle between v1's normal and the current faceNormal (e.g., if the angle between the two normals is greater than 75 degrees then we don't average the normal). In the case where the smoothing group isn't the same or the angle is greater then we have to make another vertex and ensure that f1 uses that vertex instead (this is because the normal must be different to allow for a faceted/unsmoothed look).
Step 3 is a bit of a caveat, in certain cases we have file formats (*cough .3DS), that decided to duplicate certain vertices in the same smoothing group (or within a degree/radian range that should be considered smooth). As a result this will give the appearence of seams on certain rounded objects - most notably spheres. The seam is a result of the point where multiple normals are present at a single vertex; these normals are pointing in the directions of their faces, which leads to multiple normals at a single location in space which should be smooth. The effect of this is faceted faces around the affected vertices. By averaging out the normals of these vertices we gain a normal which is appropriate and eliminates the hideous seams in the mesh. Another important point to mention is that when doing the comparsion between the positions of the two vertices (i.e., v1.position == v2.position, we should be using an "EPSILON" value) - numerical compuation is a slippery slope and we need to ensure that we take the floating point accuracy of the two positions very seriously (floats can very often not be completely equal even when they are supposed to be). Thus the "equals" (==) computation should be carried out as follows:
bool operator==(vector v1, vector v2){
if (v1 - EPSILON <= v2 <= v1 + EPSILON){
return true;
}
return false;
}Where an operation like v1 + EPSILON is interpretted: (v1.x + EPSILON, v1.y + EPSILON, v1.z + EPSILON)(Note that there are better ways to do this... epsilon should be a well established concept in your type sturctures/classes/libraries). With that said I would like to point out that we are very lucky that this is a loading procedure and not a real-time, per frame procedure... because O(n^2) algorithms suck.
The final step (step 4) in the algorithm is to simply normalize the normals for every vertex. In doing this we average the normals for any vertices where multiple normals were added on and make the normals acceptable by any typical graphics API (e.g., OpenGL, D3D).
Further Points:
- It might be a good idea to simply remove duplicated vertices within the same smoothing group altogether - this is especially true if you plan on deforming surfaces or manipulating the normals in the future (... and in real-time especially).
- The above procedure could be accomplished as follows:
foreach smoothing group (or some other condition) s{
foreach vertex v1 in s{
foreach vertex v2 in s{
if (v1 == v2){ continue; }
// As before, use EPSILON in the following
if (v1.position == v2.position){
// We must now eliminate either v1 or v2
// and point (i.e., change the reference on)
// all faces that referenced that vertex towards
// the one we don't eliminate
// 1. Eliminate v2
// 2. Foreach face with a previous
// reference to v2, reference it to v1
}
}
}
} - Don't fall into the floating point error trap, becareful of reading in very small vertex coordinates as well as calculating very small normals (usually < 1E-06 can be a bad thing, especially when you're dividing)
