teaching machines

CS 488: Lecture 5 – The Third Dimension

February 2, 2021 by . Filed under graphics-3d, lectures, spring-2021.

Dear students:

Our goal today is to render a rotating cube. No more flat geometry—we’re going to the third dimension! A few new concerns arise as we get more and more triangles in our scenes. We will overcome them with the power of our graphics API.

Indexed Triangles

In most of our computer games, triangles appear not individually but in groups. They are stitched together to form the surfaces of our characters and objects. Neighboring triangles share vertices. In the setup we’ve used thus far, we’d need to have duplicate entries for these shared vertices. But that’s wasteful and slow. A faster alternative is indexed geometry.

To share vertices, we abandon the implicit grouping of vertices by their sequence. In its place, we provide an explicit grouping via a list of vertex indices. To render a quadrilateral with two shared vertices, we’d build our vertex attributes up like this:

const positions = [
  -1, -1, 0,
   1, -1, 0,
  -1,  1, 0,
   1,  1, 0,
];

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

const faces = [
  0, 1, 2,
  1, 3, 2
];

const attributes = new VertexAttributes();
attributes.addAttribute('position', 4, 3, positions);
attributes.addAttribute('color', 4, 3, colors);
attributes.addIndices(faces);

Under the sequential system, we’d have needed 6 vertices to express the 2 triangles. The storage savings is more significant as our models become more complex. Additionally, with indexed geometry, the GPU can use the index as a key into a cache of the results of running the vertex shader. After we process the first triangle, the GPU only needs to run the vertex shader for the solitary uncached vertex of the second triangle.

We’ll come back to our positions and faces array in moment to add the other faces of our cube. First let’s get this front face rotating.

Rotation Around Other Axes

When we derived the matrix to rotate a vector around the z-axis, we reasoned through the math using just the x- and y-coordinates. Similar logic can be used to rotate around the y-axis, but we use the x- and z-coordinates instead. The matrix that we arrive at looks like this:

$$\begin{array}{rcl}\begin{bmatrix}\cos a & 0 & -\sin a & 0 \\0 & 1 & 0 & 0 \\\sin a & 0 & \cos a & 0 \\0 & 0 & 0 & 1\end{bmatrix} \cdot \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} &=& \begin{bmatrix}\cos a \cdot x-\sin a \cdot z \\y \\\sin a \cdot x+\cos a \cdot z \\1\end{bmatrix}\end{array}$$

To rotate around the x-axis, we use this matrix:

$$\begin{array}{rcl}\begin{bmatrix}1 & 0 & 0 & 0 \\0 & \cos a & -\sin a & 0 \\0 & \sin a & \cos a & 0 \\0 & 0 & 0 & 1\end{bmatrix} \cdot \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} &=& \begin{bmatrix}x \\\cos a \cdot y-\sin a \cdot z \\\sin a \cdot y+\cos a \cdot z \\1\end{bmatrix}\end{array}$$

Let’s spin the front face of the cube around the y-axis as the mouse moves, just as we did around the z-axis:

function initialize() {
  // ...

  modelToWorld = Matrix4.identity();

  window.addEventListener('mousemove', event => {
    modelToWorld = Matrix4.rotateY(-event.clientX);
    render();
  }); 

  // ...
}

Near and Far Clipping Planes

Something disturbing is going on after we add this code. As our front face turns, it starts to disappear. Why? Because of our orthographic projection. We set the near value to 0. The face of the cube is right on the front face of the bounding box of the world that we are projecting into normalized device coordinate. When we rotate the face, part of it leaves the bounding box. The triangle is clipped against the near clipping plane.

The fix is to make the bounding box bigger. With orthographic projections, we can make the near value negative. (But not with perspective projections.)

Back Face

Now we’re read to add the back face of the cube. First, let’s add the vertex attributes:

const positions = [
  -1, -1,  1,
   1, -1,  1,
  -1,  1,  1,
   1,  1,  1,
  -1, -1, -1,
   1, -1, -1,
  -1,  1, -1,
   1,  1, -1,
];

const colors = [
  0, 0, 0,
  1, 0, 0,
  0, 1, 0,
  1, 1, 0,

  0, 0, 1,
  1, 0, 1,
  0, 1, 1,
  1, 1, 1,
];

const faces = [
  // Front
  0, 1, 2,
  1, 3, 2,

  // Back
  4, 5, 6,
  5, 7, 6,
];

const attributes = new VertexAttributes();
attributes.addAttribute('position', 8, 3, positions);
attributes.addAttribute('color', 8, 3, colors);
attributes.addIndices(faces);

Depth Test

As we spin the cube, we see both faces. For some strange reason, however, the back face always appears in front of the front face. It feels like an optical illusion.

What’s happening is that the back face is always drawn last and it overwrites whatever was drawn earlier. Why is it drawn last? It’s later in the face indices array. How we ensure that whatever’s nearest to the viewer is drawn on top of whatever’s farther away?

Maybe we could sort the the triangles based on their clip-space z-coordinate. That’s going to be very expensive. Sorting has linearithmic complexity, and our number of triangles might get very big.

Instead we’ll use an algorithm pioneered by Ed Catmull of Pixar fame. (Wolfgang Straßer published first.) In addition to the color framebuffer, we’re going to ask the GPU to track another raster for our pixels. Instead of storing color, it’ll store the pixel’s depth.

When our render function clears the color framebuffer, we also ask it to clear the depth buffer or z-buffer to the farthest possible value:

gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT)

Then we enable a check:

gl.enable(gl.DEPTH_TEST);

As a fragment is processed, we ask if it’s z-coordinate is less than what’s stored in the depth buffer. If it is, the fragment color is written to the framebuffer and the depth is written to the depth buffer. Fragments processed later will only replace it if they have less depth.

The illusion should go away after these changes.

Concatenating Transforms

Let’s add the top face to the cube:

const faces = [
  // ...

  // Top
  // 2, 3, 6,
  // 3, 7, 6,
];

We can’t see it. In fact, once the cube is complete, we’ll only ever see two faces at a time. That doesn’t feel 3D to me. So, let’s also tilt the cube a bit so we can see its top. We want both an initial tilt and mouse-spinning, so we’ll use two separate rotation matrices but combine them into one with some matrix multiplication before shipping them off to the GPU:

function initialize() {
  // ...

  const tilt = Matrix4.rotateX(20);
  modelToWorld = tilt;

  window.addEventListener('mousemove', event => {
    const spin = Matrix4.rotateY(-event.clientX);
    modelToWorld = spin.multiplyMatrix(tilt);
    render();
  }); 

  // ...
}

Face Culling

Notice how we can see inside the box? Once the box is closed off, those inside faces will never be rendered. Either they will fail the depth test, or they will get overwritten. This is wasted computation. WebGL provides an optimization that can stop those triangles from ever being rasterized. We enable back-face culling in initialize:

gl.enable(gl.CULL_FACE);

This won’t seem to have worked. That’s because we’re not obeying that helps WebGL figure out which faces is outside and which is inside. We are supposed to enumerate the indices of the triangle in counter-clockwise order as we face the triangle.

So, our back face, along with the left and right faces, look like this:

const faces = [
  // ...

  // Back
  5, 4, 7,
  4, 6, 7,

  // ...

  // Bottom
  4, 5, 0,
  5, 1, 0,

  // Right
  1, 5, 3,
  5, 7, 3,

  // Left
  4, 0, 6,
  0, 2, 6,
];

Horizon

We have a rotating cube and we can see all of its sides. The color has fascinating gradients. However, the faces are not distinct. (We do clearly see the edges because of a quirk in our visual system called Mach banding.) Next week we’ll make these faces very distinct by adding lighting.

TODO

Here’s your very first TODO list:

See you next time.

Sincerely,

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

We see just outsides
Just those between near and far
So much is hidden