teaching machines

CS 488: Lecture 3 – Vectors and Matrices

January 27, 2021 by . Filed under graphics-3d, lectures, spring-2021.

Dear students:

Last time we explored the three common transformations that we use to move objects around the screen. We saw how to apply one transformation at a time using slow mathematical operations. Today we will learn a system for applying an arbitrarily long sequence of transformations in constant time. The system is built on two mathematical ideas: vectors and matrices.

Vectors

When we ship our vertex positions off to the GPU in a vertex buffer object, they arrive in the vertex shader as a vector. A vector is an array or sequence of numbers. In computer graphics and linear algebra, a vector has a fixed length. It’s not a growable array like std::vector in C++. In contrast, a solitary number is called a scalar.

Generally, the number of elements in the vector matches the number of dimensions you are working in. In 3D, we use 3-vectors. In 2D, we use 2-vectors. This is a lie, as you shall see.

Sometimes we write vectors as row vectors, like this:

$$\begin{array}{rcl}\mathbf{p} &=& \begin{bmatrix}x & y & z\end{bmatrix}\end{array}$$

Sometimes we write vectors as column vectors, like this:

$$\begin{array}{rcl}\mathbf{p} &=& \begin{bmatrix}x \\ y \\ z\end{bmatrix}\end{array}$$

Vectors are important because the GPU has hardware that can operate on all of a vector’s elements at the same time.

Physics has a different definition of vectors. A physics-vector is a direction and magnitude. The two definitions are related, and we’ll need both. For today, however, we are talking about absolute positions represented as a mathematical vector.

Dot Product

Just as scalars support operations like addition, subtraction, multiplication, and so on, vectors too have operations. The only one we care about today is called the dot product. The dot product of two vectors is the sum of the corresponding elements’ products:

$$\begin{array}{rcl}\mathbf{p} &=& \begin{bmatrix}a & b & c\end{bmatrix} \\\mathbf{q} &=& \begin{bmatrix}d & e & f\end{bmatrix} \\\mathbf{p} \cdot \mathbf{q} &=& ad+be+cf\end{array}$$

The dot product is a scalar value. It has some significance that we’ll discuss later. For now, we need only consider it as a mechanism for carrying out some multiplications and sums.

We now will recast our transforms by considering the vertex position as a vector.

Scale

Recall that we scale a vertex position $\mathbf{p}$ by multiplying to arrive the scaled vertex position $\mathbf{p’}$:

$$\begin{array}{rcl}x’ &=& s_x \cdot x \\y’ &=& s_y \cdot y \\z’ &=& s_z \cdot z \\\end{array}$$

This is the math we want to accelerate by using vector operations instead of scalar operations. We want to find a vector that when dotted with $\mathbf{p}$ will produce $x’$. The operation should look something like this:

$$\begin{array}{rcl}\begin{bmatrix} ? & ? & ? \end{bmatrix} \cdot \begin{bmatrix} x & y & z \end{bmatrix} &=& s_x \cdot x \\\end{array}$$

Given the mechanics of dot products, what values do we put in that first vector? We know that $x$ needs to get multiplied by $s_x$, and we know that the other two terms are not present in the result. Then our vector must be this:

$$\begin{array}{rcl}\begin{bmatrix} s_x & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} x & y & z \end{bmatrix} &=& s_x \cdot x \\\end{array}$$

Similarly, we have this operation to compute $y’$:

$$\begin{array}{rcl}\begin{bmatrix} 0 & s_y & 0 \end{bmatrix} \cdot \begin{bmatrix} x & y & z \end{bmatrix} &=& s_y \cdot y \\\end{array}$$

And this operation to compute $z’$:

$$\begin{array}{rcl}\begin{bmatrix} 0 & 0 & s_z \end{bmatrix} \cdot \begin{bmatrix} x & y & z \end{bmatrix} &=& s_z \cdot z \\\end{array}$$

Expressing these as dot products probably seems wasteful to you right now. The little bit of waste we see will get erased in due time.

Rotation

Recall that these are the operations we want to rotate a position around the z-axis:

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

Can we do the same recasting to the dot product machinery? Yes, the following vectors will do:

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

Translation

Recall these are the operations we want to translate a position:

$$\begin{array}{rcl}x’ &=& x+\Delta_x \\y’ &=& y+\Delta_y \\z’ &=& z+\Delta_z \\\end{array}$$

Can we recast the calculation of $x’$ as a dot product?

$$\begin{array}{rcl}\begin{bmatrix} ? & ? & ? \end{bmatrix} \cdot \begin{bmatrix} x & y & z \end{bmatrix} &=& x+\Delta_x \\\end{array}$$

Uhh, no. We can’t. That $\Delta_x$ term has no coefficient, so there’s no way the dot product can produce it. But hold on. Let’s apply a little trick that mathematicians of yore stumbled upon. We will add a fourth coordinate of 1 to our position:

$$\begin{array}{rcl}\begin{bmatrix} ? & ? & ? & ? \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& x+\Delta_x \\\end{array}$$

Now we can find vectors that dot with the position to produce the translated coordinates:

$$\begin{array}{rcl}\begin{bmatrix} 1 & 0 & 0 & \Delta_x \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& x+\Delta_x \\\begin{bmatrix} 0 & 1 & 0 & \Delta_y \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& y+\Delta_y \\\begin{bmatrix} 0 & 0 & 1 & \Delta_z \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& z+\Delta_z\end{array}$$

Homogeneous Coordinates

This extra coordinate is called the homogeneous coordinate or the w-coordinate. It pushes us to use 4-vectors even though we’re really dealing with 3D space. To make a uniform system of transformations built on dot products, we need to add the coordinate to our scaling and rotation schemes too. Also, since we want to eventually apply sequences of transformations, we need our dot products to compute $w’$.

Let’s enumerate our complete system of dot product transformations. Here are our scaling calculations:

$$\begin{array}{rcl}\begin{bmatrix} s_x & 0 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& s_x \cdot x \\\begin{bmatrix} 0 & s_y & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& s_y \cdot y \\\begin{bmatrix} 0 & 0 & s_z & 0 \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& s_z \cdot z \\\begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& 1 \\\end{array}$$

Here are our rotation calculations:

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

Here are our translation calculations:

$$\begin{array}{rcl}\begin{bmatrix} 1 & 0 & 0 & \Delta_x \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& x+\Delta_x \\\begin{bmatrix} 0 & 1 & 0 & \Delta_y \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& y+\Delta_y \\\begin{bmatrix} 0 & 0 & 1 & \Delta_z \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& z+\Delta_z \\\begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} x & y & z & 1 \end{bmatrix} &=& 1 \\\end{array}$$

Matrix-Vector Multiplication

The GPU can perform all four dot products for a transformation in parallel if we merge the left operand vectors together into a matrix. We can think of a matrix as a stack of vectors. We write the transformations not as a sequence of four dot products, but as a matrix-vector multiplication. The product is a vector.

Our scaling operation becomes this matrix-vector multiplcation:

$$\begin{array}{rcl}\begin{bmatrix}s_x & 0 & 0 & 0 \\0 & s_y & 0 & 0 \\0 & 0 & s_z & 0 \\0 & 0 & 0 & 1\end{bmatrix} \cdot \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} &=& \begin{bmatrix}s_x \cdot x \\s_y \cdot y \\s_z \cdot z \\1\end{bmatrix}\end{array}$$

Our rotation around the z-axis operation becomes this matrix-vector multiplcation:

$$\begin{array}{rcl}\begin{bmatrix}\cos a & -\sin a & 0 & 0 \\\sin a & \cos a & 0 & 0 \\0 & 0 & 1 & 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 y \\\sin a \cdot x+\cos a \cdot y \\z \\1\end{bmatrix}\end{array}$$

Our translation becomes this matrix-vector multiplication:

$$\begin{array}{rcl}\begin{bmatrix}1 & 0 & 0 & \Delta_x \\0 & 1 & 0 & \Delta_y \\0 & 0 & 1 & \Delta_z \\0 & 0 & 0 & 1\end{bmatrix} \cdot \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} &=& \begin{bmatrix}x + \Delta_x \\y + \Delta_y \\z + \Delta_z \\1\end{bmatrix}\end{array}$$

Matrices in WebGL and GLSL

Suppose we go and implement methods for generating these matrices in helpful Matrix class, which you’ll do in Friday’s lab. We can use these matrices to transform our objects by making these adjustments to our code:

let transform;

function initialize() {
  transform = Matrix.scale(2, 0.5, 1);
  // transform = Matrix.translate(0.3, -0.5);
  // transform = Matrix.rotateZ(45);
  // ...
}

function render() {
  // ...
  shaderProgram.bind();
  shaderProgram.setUniformMatrix4('transform', transform);
  // ...
}

In the vertex shader, which is responsible for computing the clip space position of the vertex, we apply the transformation:

uniform mat4 transform;

in vec3 position;

void main() {
  gl_Position = transform * vec4(position, 1.0);
}

These transforms get more interesting when we tie them to user actions. Let’s rotate our object based on the mouse’s x-coordinate by adding a mouse event listener at the end of initialize:

window.addEventListener('mousemove', event => {
  const degrees = event.clientX;
  transform = Matrix4.rotateZ(degrees);
  render();
});

This code uses JavaScript’s arrow function syntax. We’re passing a function body directly as a parameter without naming it.

Horizon

We now have a unified system for expressing transformations. We will use this system for animation, for arranging a complete world of objects, for situating a camera inside the world, and for fixing the distortion that we currently see when the window isn’t square. Right now we’re still only applying one matrix transformation at a time, but soon we’ll look at how to combine many transforms into a single matrix.

TODO

Here’s your very first TODO list:

See you next time.

Sincerely,

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

I get a * b
But a * b * c * ...?
Dot-dot-dot product

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *