4.5: An Application to Computer Graphics

Computer graphics deals with images displayed on a computer screen, and so arises in a variety of applications, ranging from word processors, to Star Wars animations, to video games, to wire-frame images of an airplane. These images consist of a number of points on the screen, together with instructions on how to fill in areas bounded by lines and curves. Often curves are approximated by a set of short straight-line segments, so that the curve is specified by a series of points on the screen at the end of these segments. Matrix transformations are important here because matrix images of straight line segments are again line segments.¹ Note that a colour image requires that three images are sent, one to each of the red, green, and blue phosphorus dots on the screen, in varying intensities.

Consider displaying the letter \(A\). In reality, it is depicted on the screen, as in Figure [fig:013289], by specifying the coordinates of the 11 corners and filling in the interior.

For simplicity, we will disregard the thickness of the letter, so we require only five coordinates as in Figure [fig:013290].

This simplified letter can then be stored as a data matrix

\[\begin{aligned} \mbox{\textit{Vertex}} & \ \ \ \ \ \ \ \begin{array}{rrrrr} 1 & 2 & 3 & 4 & 5 \end{array} \\ D &= \left[ \begin{array}{rrrrr} 0 & 6 & 5 & 1 & 3\\ 0 & 0 & 3 & 3 & 9 \end{array} \right]\end{aligned} \nonumber \]

where the columns are the coordinates of the vertices in order. Then if we want to transform the letter by a \(2 \times 2\) matrix \(A\), we left-multiply this data matrix by \(A\) (the effect is to multiply each column by \(A\) and so transform each vertex).

For example, we can slant the letter to the right by multiplying by an \(x\)-shear matrix \(A = \left[ \begin{array}{ll} 1 & 0.2\\ 0 & 1\\ \end{array} \right]\) —see Section [sec:2_2]. The result is the letter with data matrix

\[A = \left[ \begin{array}{ll} 1 & 0.2\\ 0 & 1 \end{array} \right] \left[ \begin{array}{rrrrr} 0 & 6 & 5 & 1 & 3\\ 0 & 0 & 3 & 3 & 9 \end{array} \right] = \left[ \begin{array}{lllll} 0 & 6 & 5.6 & 1.6 & 4.8\\ 0 & 0 & 3 & 3 & 9 \end{array} \right] \nonumber \]

which is shown in Figure [fig:013296].

If we want to make this slanted matrix narrower, we can now apply an \(x\)-scale matrix \(B = \left[ \begin{array}{ll} 0.8 & 0\\ 0 & 1 \end{array} \right]\) that shrinks the \(x\)-coordinate by \(0.8\). The result is the composite transformation

\[\begin{aligned} BAD &= \left[ \begin{array}{ll} 0.8 & 0\\ 0 & 1 \end{array} \right] \left[ \begin{array}{ll} 1 & 0.2\\ 0 & 1 \end{array} \right] \left[ \begin{array}{rrrrr} 0 & 6 & 5 & 1 & 3\\ 0 & 0 & 3 & 3 & 9 \end{array} \right] \\ &= \left[ \begin{array}{lllll} 0 & 4.8 & 4.48 & 1.28 & 3.84\\ 0 & 0 & 3 & 3 & 9 \end{array} \right]\end{aligned} \nonumber \]

which is drawn in Figure [fig:013297].

On the other hand, we can rotate the letter about the origin through \(\frac{\pi}{6}\) (or \(30^\circ\)) by multiplying by the matrix \(R_{\frac{\pi}{2}} = \left[ \def\arraystretch{1.5}\begin{array}{rr} \cos(\frac{\pi}{6}) & -\sin(\frac{\pi}{6})\\ \sin(\frac{\pi}{6}) & \cos(\frac{\pi}{6}) \end{array} \right] = \left[ \begin{array}{ll} 0.866 & -0.5\\ 0.5 & 0.866 \end{array} \right]\). This gives

\[\begin{aligned} R_{\frac{\pi}{2}} &= \left[ \begin{array}{ll} 0.866 & -0.5\\ 0.5 & 0.866 \end{array} \right] \left[ \begin{array}{rrrrr} 0 & 6 & 5 & 1 & 3\\ 0 & 0 & 3 & 3 & 9 \end{array} \right] \\ &= \left[ \begin{array}{lllrr} 0 & 5.196 & 2.83 & -0.634 & -1.902\\ 0 & 3 & 5.098 & 3.098 & 9.294 \end{array} \right]\end{aligned} \nonumber \]

and is plotted in Figure [fig:013303].

This poses a problem: How do we rotate at a point other than the origin? It turns out that we can do this when we have solved another more basic problem. It is clearly important to be able to translate a screen image by a fixed vector \(\mathbf{w}\), that is apply the transformation \(T_{w} : \mathbb{R}^2 \to \mathbb{R}^2\) given by \(T_{w}(\mathbf{v}) = \mathbf{v} + \mathbf{w}\) for all \(\mathbf{v}\) in \(\mathbb{R}^2\). The problem is that these translations are not matrix transformations \(\mathbb{R}^2 \to \mathbb{R}^2\) because they do not carry \(\mathbf{0}\) to \(\mathbf{0}\) (unless \(\mathbf{w} = \mathbf{0}\)). However, there is a clever way around this.

The idea is to represent a point \(\mathbf{v} = \left[ \begin{array}{r} x\\ y \end{array} \right]\) as a \(3 \times 1\) column \(\left[ \begin{array}{r} x\\ y\\ 1 \end{array} \right]\), called the homogeneous coordinates of \(\mathbf{v}\). Then translation by \(\mathbf{w} = \left[ \begin{array}{r} p\\ q \end{array} \right]\) can be achieved by multiplying by a \(3 \times 3\) matrix:

\[\left[ \begin{array}{rrr} 1 & 0 & p\\ 0 & 1 & q\\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{r} x\\ y\\ 1 \end{array} \right] = \left[ \begin{array}{c} x + p\\ y + q\\ 1 \end{array} \right] = \left[ \begin{array}{c} T_{\mathbf{w}}(\mathbf{v})\\ 1 \end{array} \right] \nonumber \]

Thus, by using homogeneous coordinates we can implement the translation \(T_{w}\) in the top two coordinates. On the other hand, the matrix transformation induced by \(A = \left[ \begin{array}{rr} a & b\\ c & d \end{array} \right]\) is also given by a \(3 \times 3\) matrix:

\[\left[ \begin{array}{rrr} a & b & 0\\ c & d & 0\\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{r} x\\ y\\ 1 \end{array} \right] = \left[ \begin{array}{c} ax + by\\ cx + dy\\ 1 \end{array} \right] = \left[ \begin{array}{c} A\mathbf{v}\\ 1 \end{array} \right] \nonumber \]

So everything can be accomplished at the expense of using \(3 \times 3\) matrices and homogeneous coordinates.

013322 Rotate the letter \(A\) in Figure [fig:013290] through \(\frac{\pi}{6}\) about the point \(\left[ \begin{array}{c} 4\\ 5 \end{array} \right]\).

Using homogeneous coordinates for the vertices of the letter results in a data matrix with three rows:

\[K_{d} = \left[ \begin{array}{rrrrr} 0 & 6 & 5 & 1 & 3\\ 0 & 0 & 3 & 3 & 9 \\ 1 & 1 & 1 & 1 & 1 \end{array} \right] \nonumber \]

If we write \(\mathbf{w} = \left[ \begin{array}{c} 4\\ 5 \end{array} \right]\), the idea is to use a composite of transformations: First translate the letter by \(-\mathbf{w}\) so that the point \(\mathbf{w}\) moves to the origin, then rotate this translated letter, and then translate it by \(\mathbf{w}\) back to its original position. The matrix arithmetic is as follows (remember the order of composition!):

\[\begin{aligned} & \left[ \begin{array}{rrr} 1 & 0 & 4\\ 0 & 1 & 5\\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{lrr} 0.866 & -0.5 & 0\\ 0.5 & 0.866 & 0\\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{rrr} 1 & 0 & -4\\ 0 & 1 & -5\\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{rrrrr} 0 & 6 & 5 & 1 & 3\\ 0 & 0 & 3 & 3 & 9 \\ 1 & 1 & 1 & 1 & 1 \end{array} \right] \\ &= \left[ \begin{array}{lllll} 3.036 & 8.232 & 5.866 & 2.402 & 1.134\\ -1.33 & 1.67 & 3.768 & 1.768 & 7.964 \\ 1 & 1 & 1 & 1 & 1 \end{array} \right]\end{aligned} \nonumber \]

This is plotted in Figure [fig:013335].

This discussion merely touches the surface of computer graphics, and the reader is referred to specialized books on the subject. Realistic graphic rendering requires an enormous number of matrix calculations. In fact, matrix multiplication algorithms are now embedded in microchip circuits, and can perform over 100 million matrix multiplications per second. This is particularly important in the field of three-dimensional graphics where the homogeneous coordinates have four components and \(4 \times 4\) matrices are required.

---

1. If \(\mathbf{v}_{0}\) and \(\mathbf{v}_{1}\) are vectors, the vector from \(\mathbf{v}_{0}\) to \(\mathbf{v}_{1}\) is \(\mathbf{d} = \mathbf{v}_{1} - \mathbf{v}_{0}\). So a vector \(\mathbf{v}\) lies on the line segment between \(\mathbf{v}_{0}\) and \(\mathbf{v}_{1}\) if and only if \(\mathbf{v} = \mathbf{v}_{0} + t\mathbf{d}\) for some number \(t\) in the range \(0 \leq t \leq 1\). Thus the image of this segment is the set of vectors \(A\mathbf{v} = A\mathbf{v}_{0} + tA \mathbf{d}\) with \(0 \leq t \leq 1\), that is the image is the segment between \(A\mathbf{v}_{0}\) and \(A\mathbf{v}_{1}\).↩