2.7 Applications to computer graphics

Big idea

Graphics hardware moves points, and almost every move is linear: rotate, scale, shear, reflect. One operation refuses to join in. Translation shifts the origin, and a linear transformation has to leave the origin alone, so sliding a shape sideways is not a $2 \times 2$ matrix and never will be.

The fix is a change of bookkeeping. Store the plane point $(x, y)$ as the triple $(x, y, 1)$, one dimension up. In that larger space, translation is a shear that leaves the extra coordinate alone, and a shear is linear. So a $3 \times 3$ matrix now performs translation, and the same $3 \times 3$ format absorbs rotation, scaling and reflection in its top-left corner.

Once every operation is a matrix, a chain of operations is a product, and a product can be computed once and applied to a million vertices. That is the practical payoff. A character model is transformed by a single matrix per frame, assembled from a list of moves that a person described one at a time.

Decoder

Homogeneous coordinates are a representation, not new geometry. The triple $(x, y, 1)$ names the plane point $(x, y)$. More generally $(X, Y, H)$ with $H$ nonzero names the point $(X/H, Y/H)$, so $(6, 4, 2)$ and $(3, 2, 1)$ are the same point. Dividing by the last coordinate at the end is called the homogeneous divide, and in two-dimensional work it is usually free because $H$ stays $1$.

Composition order is where mistakes live. If you rotate first and then translate, the matrix is $T$ times $R$, with the first operation on the right. Matrix products are read right to left because that is the order the point meets them: $TR\mathbf{p}$ applies $R$ to $\mathbf{p}$ before $T$ ever sees it.

Definitions and results

Homogeneous coordinates in the plane. The point $(x, y)$ is written $(x, y, 1)$. Any triple $(X, Y, H)$ with $H \neq 0$ represents $(X/H, Y/H)$. Triples with $H = 0$ represent directions rather than points, which is how parallel lines are handled in projective settings.

Linear transformations, extended. A linear transformation of the plane with $2 \times 2$ matrix $A$ becomes the $3 \times 3$ matrix with $A$ in the top-left corner, a bottom row of $(0, 0, 1)$, and zeros in the remaining positions of the last column. The third coordinate passes through untouched.

Translation. Moving every point by $(h, k)$ is

$$ \begin{bmatrix} 1 & 0 & h \\ 0 & 1 & k \\ 0 & 0 & 1 \end{bmatrix} $$

Applied to $(x, y, 1)$ it gives $(x + h, y + k, 1)$. The shift lives in the last column, which is exactly the column the old $2 \times 2$ format had no room for.

The standard moves. With $c = \cos\theta$ and $s = \sin\theta$, rotation about the origin by $\theta$ has top-left block $\begin{bmatrix} c & -s \\ s & c \end{bmatrix}$. Scaling by $a$ horizontally and $b$ vertically has top-left block $\begin{bmatrix} a & 0 \\ 0 & b \end{bmatrix}$. A horizontal shear by $k$ has block $\begin{bmatrix} 1 & k \\ 0 & 1 \end{bmatrix}$, and reflection across the $x$-axis has block $\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$.

Composite transformations. Performing transformations with matrices $M_1, M_2, \dots, M_k$ in that order is the single matrix $M_k \cdots M_2M_1$. Because the product is associative, the whole chain may be multiplied out in advance and applied to every vertex once.

Moving the centre of an operation. To rotate or scale about a point other than the origin, translate that point to the origin, do the operation, and translate back. The composite is $T(h,k) \, A \, T(-h,-k)$. This is the pattern behind rotating a sprite about its own centre and behind reflecting across a line that misses the origin.

Three dimensions. The same scheme uses $4 \times 4$ matrices on quadruples $(x, y, z, 1)$, with translation again in the last column and the linear part in the top-left $3 \times 3$ block.

Perspective projection. A projection onto the $xy$-plane with the viewer at $(0, 0, d)$ sends $(x, y, z)$ to $\big(\tfrac{x}{1 - z/d}, \tfrac{y}{1 - z/d}, 0\big)$. In homogeneous form it is the matrix with rows $(1,0,0,0)$, $(0,1,0,0)$, $(0,0,0,0)$ and $(0,0,-1/d,1)$, and the division by $1 - z/d$ happens in the homogeneous divide at the end. This is the one place the last coordinate stops being $1$, and it is the reason the representation is worth the extra row.

Worked examples

Order changes the answer

Translate by $(3, -1)$, then scale by $2$ in both directions. The matrices are

$$ T = \begin{bmatrix} 1 & 0 & 3 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{bmatrix}, \qquad S = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

Translate first means the composite is $ST$:

$$ ST = \begin{bmatrix} 2 & 0 & 6 \\ 0 & 2 & -2 \\ 0 & 0 & 1 \end{bmatrix} $$

Apply it to the point $(1, 2)$, written $(1, 2, 1)$: the result is $(2(1) + 6, \; 2(2) - 2, \; 1) = (8, 2, 1)$, the point $(8, 2)$.

Check by doing the two steps by hand. Translating $(1, 2)$ by $(3, -1)$ gives $(4, 1)$, and doubling gives $(8, 2)$. Agreed.

Now the other order. Scaling first means the composite is $TS$:

$$ TS = \begin{bmatrix} 2 & 0 & 3 \\ 0 & 2 & -1 \\ 0 & 0 & 1 \end{bmatrix} $$

which sends $(1, 2, 1)$ to $(2 + 3, \; 4 - 1, \; 1) = (5, 3, 1)$. By hand: doubling $(1, 2)$ gives $(2, 4)$, then translating gives $(5, 3)$. Same ingredients, different point, because the scaling also scaled the shift.

Rotating about a point that is not the origin

Rotate by $90$ degrees about the point $(2, 1)$. At $\theta = 90$ degrees the rotation block is $\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}$. Build the sandwich $T(2,1) \, R \, T(-2,-1)$, rightmost first:

$$ R \, T(-2,-1) = \begin{bmatrix} 0 & -1 & 1 \\ 1 & 0 & -2 \\ 0 & 0 & 1 \end{bmatrix}, \qquad M = T(2,1) \, R \, T(-2,-1) = \begin{bmatrix} 0 & -1 & 3 \\ 1 & 0 & -1 \\ 0 & 0 & 1 \end{bmatrix} $$

Apply $M$ to the point $(3, 1)$: the result is $(0(3) - 1(1) + 3, \; 1(3) + 0(1) - 1, \; 1) = (2, 2, 1)$.

Two checks. First, by hand: shifting $(3,1)$ by $(-2,-1)$ gives $(1, 0)$, rotating a quarter turn gives $(0, 1)$, shifting back gives $(2, 2)$. Second, the centre of rotation must not move. $M$ applied to $(2, 1, 1)$ gives $(0(2) - 1(1) + 3, \; 1(2) + 0(1) - 1, \; 1) = (2, 1, 1)$. Fixed, as required.

A perspective projection

Put the viewer at $(0, 0, 10)$, so $d = 10$, and project the point $(6, 4, 5)$. In homogeneous form the point is $(6, 4, 5, 1)$ and the matrix sends it to

$$ (6, \; 4, \; 0, \; 1 - \tfrac{5}{10}) = (6, \; 4, \; 0, \; 0.5) $$

The last coordinate is not $1$, so divide through by it: the screen point is $(12, 8, 0)$.

Check against the formula directly: $1 - z/d = 0.5$, so $x/(1 - z/d) = 6/0.5 = 12$ and $y/(1 - z/d) = 4/0.5 = 8$. The point sits halfway from the screen to the eye, so it projects twice as far from the axis as it sits, which is the enlargement you expect from something close to you.

Practice

Write the matrix for a described rotation, scaling, shear or reflection, and apply it to a point.

Multiply the matrices of a chain of moves into one composite, keeping the order right.

Videos

Watch for the claim that a matrix is determined by where it sends the two basis vectors, and read each graphics matrix in this section that way: its first two columns are the images of the basis vectors and its last column is the shift. The video works in two dimensions without homogeneous coordinates, so the extra row here is the one thing it does not show.

Quiz

Five items on transformation matrices and composites.