Computing Face and Vertex Normals
See Also: Class Point3, Class Mesh, Template Class Tab.
Overview
Developers often need to compute the face and vertex normals when working with meshes in MAX. This section discusses the process of computing these normals and provides some sample code to do so.
Face Normals
A face normal is a vector that defines which way a face is pointing. The direction that the normal points represents the front, or outer surface of the face. To compute the face normal of a face in a mesh you simply take the cross product of two edge vectors of the face. The following code shows how this is done using the 3ds max API. It loops through each face in a mesh and stores the computed face normal in a table of Point3s named fnorms. At the end of the code, the DebugPrint() API is used to display each normal in the table to the debug window of the VC++ IDE.
void Utility::ComputeFaceNormals(Mesh *mesh) {
Face *face;;
Point3 *verts;
Point3 v0, v1, v2;
Tab<Point3> fnorms;
// Compute face (surface) normals for the mesh
face = mesh->faces;
verts = mesh->verts;
fnorms.SetCount(mesh->getNumFaces());
for (int i = 0; i < mesh->getNumFaces(); i++, face++) {
v0 = verts[face->v[0]];
v1 = verts[face->v[1]];
v2 = verts[face->v[2]];
fnorms[i] = (v1-v0)^(v2-v1);
fnorms[i] = Normalize(fnorms[i]);
}
// Display the normals in the debug window of the VC++ IDE
DebugPrint("\n\nFace Normals ---");
for (i = 0; i < fnorms.Count(); i++) {
DebugPrint("\nFace Normal[%d]=(%.1f, %.1f, %.1f)",
i, fnorms[i].x, fnorms[i].y, fnorms[i].z);
}
DebugPrint("\n\n");
}
As a side note on face normals -- If you take the length of a face normal vector (for example using the Point3::Length() method), you get a quantity equal to twice the surface area of that face.
Vertex Normals
This section discusses the way vertex normals may be computed. Two algorithms are reviewed. The first ignores smoothing groups and returns an averaged normal at the vertex. The second one looks at the smoothing information and computes multiple normals when there are faces that have different smoothing groups that share a vertex. Sample code to handle the smoothing group aware case is shown.
First, consider the case where smoothing groups are not checked. In this case, 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.
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 hemi-spheres 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
void VNormal::AddNormal(Point3 &n,DWORD s) {
if (!(s&smooth) && init) {
if (next) next->AddNormal(n,s);
else {
next = new VNormal(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(DWORD s) {
if (smooth&s || !next) return norm;
else return 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 (int j=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);
}
Other Techniques for Computing Vertex Normals
This next section discusses two other techniques that may be used in computing vertex normals. The first technique weights the normals by the vertex angle on each face. The second weights the normal using the area of each face.
Weighting by Face Angle
To understand why using a weighted normal approach might be used consider the following example:
Create a default Box and convert it to an Editable Mesh. Go into SubObject mode, and find vertex 1 (generally found at the front lower left corner). Display the edges, and go into object properties to unclick "edges only" (so you see the hidden edges). You'll see that vertex 1 is used by bottom faces 1 and 2. (In the SDK, these are vertex 0 and faces 0 and 1.) It's also used by front faces 5 and 6, and left face 11. (4,5,10.)
If we simply averaged the normals of all incident faces, we'd get:
Normalize (2*(0,0,-1) + 2*(0,-1,0) + (-1,0,0)), which is (1/3, 2/3, 2/3).
Because this arrangement of diagonals is haphazard and (inherently) asymmetric, we'd get vertex normals on a box pointing odd, uncoordinated directions.
If we instead weight the normals by the vertex angle on each face, we get:
Normalize (PI/2*(0,0,-1) + PI/2*(0,-1,0) + PI/2*(-1,0,0)) = (1,1,1)/Sqrt(3)
This is more natural for the user. Each vertex normal points away from all three sides symmetrically. (The individual front and bottom triangles may have varying angles, but the pairs of them always add up to PI/2.)
This seems like the right approach in general -- when you divide a face, for example, you don't wind up changing the vertex normal when the surface hasn't essentially changed. If you change vertex angles by dragging neighboring verticies, the normal changes in a natural fashion.
You can compute the vertex angle by using dot products as shown below:
// Corner is 0, 1, or 2 -- which corner do we want the angle of?
float FindVertexAngle(Mesh *mesh, int face, int corner) {
int cnext = (corner+1)%3;
int cprev = (corner+2)%3;
DWORD *vv = mesh->faces[face];
// Get edge vectors:
Point3 A = mesh->verts[vv[cnext]] - mesh->verts[vv[corner]];
Point3 B = mesh->verts[vv[corner]] - mesh->verts[vv[cprev]];
// Normalize the edge-vectors, but return 0 if either has 0 length.
float len = Length(A);
if (!len) return len;
A = A/len;
len = Length(B);
if (!len) return len;
B = B/len;
// The dot product gives the cosine of the angle:
float dp = DotProd (A,B);
if (dp>1) dp=1.0f; // shouldn't happen, but might
if (dp<-1) dp=-1.0f; // shouldn't happen, but might
return acos(dp);
}
To be efficient when computing all normals, you may want to cache the normalized edge directions (A & B). You can index these by an adjacent edge list for the mesh, where edir[i] is the unit vector pointing from vertex ae->edges[i].v[0] to ae->edges[i].v[1] (AdjEdgeList *ae).
Weighting by Face Area
Another possibility is to weight the normals by the area of each face. The area of a face is very easy to compute, it's just half the length of the normal cross product:
void GetAreaAndNormal (Mesh *mesh, int face, Point3 & N, float area) {
DWORD *vv = mesh->faces[face].v;
Point3 A = mesh->verts[vv[1]] - mesh->verts[vv[0]];
Point3 B = mesh->verts[vv[2]] - mesh->verts[vv[0]];
N = A^B;
area = Length (N) / 2.0f;
Normalize (N);
}
This works using any two edges for A and B.
To weight face normals by area, you can just use the N=A^B vector directly.
Weighting by area gives an interesting result, but perhaps not as satisfactory as weighting by face angle.