Ignoring Smoothing Groups

In the case where smoothing groups are not checked there will be a single vertex normal for each vertex of the mesh. The vertex normal is the average of the face normals of each of the faces that share that vertex. The algorithm to compute such vertex normals is as follows:

First, allocate an array of normals, one for each vertex in the mesh, and initialize them to zero (Point3( 0,0,0)). Then for each face, compute its face normal, and add it into each of the three vertex normals that the face contributes to. For example, if you have a vertex normal shared by five faces, each face will add in its normal to that vertex, and thus the result will be average normal of those five faces. When all the faces in the mesh have been processed, the average normal vector has been computed. As a last step, all the normals in the array can be normalized.

Considering Smoothing Groups

The above algorithm does not take smoothing groups into account. When smoothing groups are involved, you may have multiple normals for each vertex. For example, if you had a sphere that had the top and bottom hemispheres smoothed separately (i.e. not smoothed across the equator), then the vertices across the equator would have two normals for each vertex while the other vertices would have one. There may be as many normals as there are smoothing groups colliding at a vertex. However, it is by far the most common case to have one, and anything other than one or two is very rare.

The class used to compute vertex normals considering smoothing is shown below. This class, VNormal, is similar to the RNormal class used by 3ds Max internally. The class contains a Point3 which is the normal, a DWORD for the smoothing groups, and a pointer to the next normal -- this class is a linked list. The init variable is used as a flag to indicate if the first normal in the list has been initialized.

// Linked list of vertex normals
class VNormal
{
   public:
     Point3 norm;
     DWORD smooth;
     VNormal *next;
     BOOL init;
 
     VNormal() {smooth=0;next=NULL;init=FALSE;norm=Point3(0,0,0);}
     VNormal(Point3 &n,DWORD s) {next=NULL;init=TRUE;norm=n;smooth=s;}
     ~VNormal() {delete next;}
     void AddNormal(Point3 &n,DWORD s);
     Point3 &GetNormal(DWORD s);
     void Normalize();
};

A key method to this class is AddNormal(). It is used when a face is going to add its normal to a vertex. This method is passed the normal and the smoothing information for that face. It checks if the normal passed shares smoothing information with the existing normal. If it does, the normal is added in, and the smoothing bits are bitwise OR-ed in. If it does not, a new vertex normal is created. In this way, as normals that share smoothing information are added, they contribute to the overall normal for that smoothing condition at the vertex. If it is a normal whose face does not share smoothing information, a new vertex normal is allocated.

// Add a normal to the list if the smoothing group bits overlap,
// otherwise create a new vertex normal in the list
voidVNormal::AddNormal(Point3 &n,DWORD s) {
   if (!(s&smooth) && init) {
     if (next) next->AddNormal(n,s);
     else {
      next = newVNormal(n,s);
     }
   }
   else {
     norm += n;
     smooth |= s;
     init = TRUE;
   }
}
 
// Retrieves a normal if the smoothing groups overlap or there is
// only one in the list
Point3 &VNormal::GetNormal(DWORDs)
{
   if (smooth&s || !next) returnnorm;
   elsereturn next->GetNormal(s); 
}
 
// Normalize each normal in the list
void VNormal::Normalize() {
   VNormal *ptr = next, *prev = this;
   while (ptr)
   {
     if (ptr->smooth&smooth) {
      norm += ptr->norm;
      prev->next = ptr->next;
       delete ptr;
      ptr = prev->next;
     }
     else {
      prev = ptr;
      ptr = ptr->next;
     }
   }
   norm = ::Normalize(norm);
   if (next) next->Normalize();
}

The method ComputeVertexNormals() shown below is a demonstration method that uses the VNormal class above. The first thing done is to create a table of the vertex normals. Note that since the Tab class does not do any initialization (it only allocates the memory), the code loops through each normal and call the constructor to perform the initialization. Then it goes through each face , calculates the surface normal, and adds it into each of the three vertex normals for the face using AddNormal(). When all the faces have been processed, it goes through each of the vertex normals and normalizes them.

In the code below, the vertex normals are displayed using DebugPrint() to the output window. If there is more than one normal at a vertex, each one is displayed (the DisplayVertexNormal() method recursively calls itself to display each one).

// Compute the face and vertex normals
void Utility::ComputeVertexNormals(Mesh *mesh)
{
   Face *face; 
   Point3 *verts;
   Point3 v0, v1, v2;
   Tab<VNormal> vnorms;
   Tab<Point3> fnorms;
   face = mesh->faces; 
   verts = mesh->verts;
   vnorms.SetCount(mesh->getNumVerts());
   fnorms.SetCount(mesh->getNumFaces());
 
   // Compute face and vertex surface normals
   for (int i = 0; i < mesh->getNumVerts(); i++) {
     vnorms[i] = VNormal();
   }
   for (i = 0; i < mesh->getNumFaces(); i++, face++) {
     // Calculate the surface normal
     v0 = verts[face->v[0]];
     v1 = verts[face->v[1]];
     v2 = verts[face->v[2]];
     fnorms[i] = (v1-v0)^(v2-v1);
     for (intj=0; j<3; j++) { 
      vnorms[face->v[j]].AddNormal(fnorms[i],face->smGroup);
     }
     fnorms[i] = Normalize(fnorms[i]);
   }
   for (i=0; i < mesh->getNumVerts(); i++) {
     vnorms[i].Normalize();
   }
   // Display the normals in the debug window of the VC++ IDE
   DebugPrint(";\n\nVertex Normals ---";);
   for (i = 0; i < vnorms.Count(); i++) {
     DisplayVertexNormal(vnorms.Addr(i), i, 0);
   }
   DebugPrint("\n\n");
}
 
void Utility::DisplayVertexNormal(VNormal *vn, int i, int n)
{
   DebugPrint("\nVertex %d Normal %d=(%.1f, %.1f, %.1f)&",
     i, n, vn->norm.x, vn->norm.y, vn->norm.z);
   if (vn->next) DisplayVertexNormal(vn->next, i, n+1);
}