teaching machines

CS 488: Lecture 8 – Normal Generation

February 22, 2021 by Chris Johnson. Filed under graphics-3d, lectures, spring-2021.

Dear students:

Shading is dependent on normals. So far, we’ve limited ourselves to shapes whose normals can be computed with a little trigonometry. What do we do when our models start getting less algorithmic? We need a different strategy for computing normals of arbitrary triangle meshes. That strategy is our focus today.

Cross Product

The key to computing normals is a vector operation called the cross product. When you cross vector $\mathbf{a}$ with vector $\mathbf{b}$, you get a vector that is perpendicular to both. We’ll represent the cross product with this notation:

If we have a triangle, we can choose any two of its edges, find the vectors that lead from one vertex to the others, and cross them to compute a vector that points away from the triangle.

The equation for the cross product is not something I find intuitive. However, we can work out the equation in an accessible way that doesn’t give you any appreciation for its geometric interpretation. We start by drawing a table of our two vectors, with the components of $\mathbf{a}$ marking the rows and the components of $\mathbf{b}$ marking the columns:

With the dot product, we measure the “togetherness” of two vectors. With the cross product, we focus on the interactions of the two vectors across dimensions. In fact, we ignore the interaction within a dimension entirely. That idea leads us to the first step of our illustration. Mark each diagonal cell with 0, thereby canceling out the x-x, y-y, and z-z interactions:

Then move right from each cell and count up to 2, wrapping back to the beginning of the row as needed:

This table will be our guide as we compute the components of the cross product. To calculate the first component, we ignore the x-row and -column:

The cell with a 1 in it represents $a_y \cdot b_z$. The cell with a 2 in it represents $a_z \cdot b_y$. We subtract cell 2 from cell 1 to get $c_x$:

We play the same game for computing the y-component, ignoring the y-row and -column:

Following the same tactic of subtracting cell 2 from cell 1, we have this equation:

And one last round for the z-component, ignoring the z-row and -column:

Following the same tactic of subtracting cell 2 from cell 1, we have this equation:

Altogether, we have this equation for the cross product:

There are a couple of things to observe here. First, because there’s a subtraction involved, the cross product is not commutative. If we switch the order of $\mathbf{a}$ and $\mathbf{b}$, we end up with a vector pointing in the opposite direction. In other words:

Second, the new vector is not generally going to be normalized, even if $\mathbf{a}$ and $\mathbf{b}$ were. You will need to renormalize if that’s important to you.

Visualizing the Cross Product

As I learned about computer graphics, I coded up a lot of demos to help me understand the math that seemed like magic to me. Let’s create one of these demos for the cross product. We will plot three vectors. Two of them will be set by the user, and the third will be their cross product.

We can use our standard workflow of vertex attributes and shaders, but we’ll draw vertices from the vertex buffer objects in pairs and plot them as line segments. Our code might look something like this:

let a;
let b;
let c;

function render() {
  // ...
  vertexArray.drawSequence(gl.LINES);
  // ...
}

function initialize() {
  a = new Vector3(-0.9, -0.9, 0.5).normalize();
  b = new Vector3(-0.8, -0.7, 0.5).normalize();
  c = a.cross(b).normalize();

  const positions = [
    0.0, 0.0, 0.0,
    a.x, a.y, a.z,
    0.0, 0.0, 0.0,
    b.x, b.y, b.z,
    0.0, 0.0, 0.0,
    c.x, c.y, c.z,
  ];

  const colors = [
    1, 0, 0,
    1, 0, 0,
    0, 1, 0,
    0, 1, 0,
    0, 0, 1,
    0, 0, 1,
  ];

  // ...
}

Face Normals

The cross product gives us the power to compute the normal for each triangle in our mesh. To hide away the complexity of all this, probably we should have abstractions for vectors and meshes. That leads us to this pseudocode:

class Mesh
  constructor(positions, faces)
    store positions, which is an array of 3-vectors
    store faces, which is an array of 3-int-arrays

  calculateNormals
    for each face in faces
      a = positions[face[0]]
      b = positions[face[1]]
      c = positions[face[2]]
      
      v = b - a
      w = c - a

      faceNormal = normalize(cross(v, w))

Inside that loop, we’ve got each face’s normal. But how does that help us? We provide data at the vertex level, not the face level.

Vertex Normals

A vertex’s normal can be considered to be the average of the normals of the faces that include it. Since we have no easy way of iterating through the vertices and figuring out the neighboring faces, we instead extend the face loop above. Once we have a face normal, we tack it on to its three vertices’ accumulating normals. These normals must be zeroed out before the loop every starts and renormalized at the end, leading this pseudocode:

class Mesh
  constructor(positions, faces)
    store positions, which is an array of 3-vectors
    store faces, which is an array of 3-int-arrays

  calculateNormals
    vertexNormals = new array of zeroed out 3-vectors
      that has the same size as positions

    for each face
      a = positions[face[0]]
      b = positions[face[1]]
      c = positions[face[2]]
      
      v = b - a
      w = c - a

      faceNormal = normalize cross(v, w)

      vertexNormals[face[0]] += faceNormal
      vertexNormals[face[1]] += faceNormal
      vertexNormals[face[2]] += faceNormal

    for each vertexNormal
      normalize vertexNormal

TODO

Here’s your TODO list:

• Start implementing Vector3 class. Give it methods normalize, cross, dot. Give it getters and setters for magnitude, x, y, and z. Give it a method toVector4 that accepts the homogeneous coordinate as a parameter and returns a Vector4 instance that you can use with matrix multiplication. (The class Vector4 probably doesn’t need to support many operations. Getters and setters for the components and a method toVector3 are sufficient.)

See you next time.

Sincerely,

P.S. It’s time for a haiku!

After the sky fell
Chicken Little crossed the road
To see what was up