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 color 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 the figure below, by specifying the coordinates of the 11 corners and filling in the interior.

[Picture]

For simplicity, we will disregard the thickness of the letter, so we require only five coordinates as in the figure below.

[Picture]

This simplified letter can then be stored as a data matrix

\[D =\begin{bmatrix} 0 & 6 & 5 & 1 & 3\\ 0 & 0 & 3 & 3 & 9 \end{bmatrix}\]

where the columns are the coordinates of the vertices. 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 a horizontal shear matrix \(A = \left [ \begin{array}{ll} 1 & 0.2\\ 0 & 1\\ \end{array} \right ]\) (See Formula form:shears.) The result is the letter with data matrix

\begin{equation*} 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 ] \end{equation*}

which is shown in the figure below.

[Picture]

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

\begin{align*} 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{align*}

which is drawn in the figure below.

[Picture]

On the other hand, we can rotate the letter about the origin through \(\frac {\pi }{6}\) (or \(30^\circ \)) by multiplying by the rotation 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 ]\]

(See Formula form:rotation.) This gives

\begin{align*} 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{align*}

and is plotted in the figure below.

[Picture]

This poses a problem: How do we rotate about 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 \(\vec {w}\), that is apply the transformation \(T_{w} : \RR ^2 \to \RR ^2\) given by \(T_{w}(\vec {v}) = \vec {v} + \vec {w}\) for all \(\vec {v}\) in \(\RR ^2\). The problem is that these translations are not matrix transformations \(\RR ^2 \to \RR ^2\) because they do not carry \(\vec {0}\) to \(\vec {0}\) (unless \(\vec {w} = \vec {0}\)). (See Practice Problem prob:translation_does_not_work.) However, there is a clever way around this.

The idea is to represent a point \(\vec {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 \(\vec {v}\). Then translation by \(\vec {w} = \left [ \begin{array}{r} p\\ q \end{array} \right ]\) can be achieved by multiplying by a \(3 \times 3\) matrix:

\begin{equation*} \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_{\vec {w}}(\vec {v})\\ 1 \end{array} \right ] \end{equation*}

Thus, by using homogeneous coordinates we can implement the translation \(T_{w}\) in the top two coordinates. At the same time, matrix transformations we performed earlier can still be accomplished using homogeneous coordinates. For instance, the matrix transformation induced by \(A = \left [ \begin{array}{rr} a & b\\ c & d \end{array} \right ]\) is given by a \(3 \times 3\) matrix:

\begin{equation*} \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\vec {v}\\ 1 \end{array} \right ] \end{equation*}

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

It is interesting to examine the geometric implications of homogeneous coordinates. All points of the form \(\begin{bmatrix}x\\y\end{bmatrix}\), originally located in the \(xy\)-plane in \(\RR ^2\), now have the form \(\begin{bmatrix}x\\y\\1\end{bmatrix}\) and are located in a horizontal plane \(z=1\) in \(\RR ^3\). What we perceive as a translation in the horizontal plane \(z=1\), is actually a shear in \(\RR ^3\). This is similar to how horizontal shears in \(\RR ^2\) affect points along the line \(y=1\): all such points move a fixed distance to the left or to the right.

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.

Practice Problems

Consider the letter \(A\) below.

[Picture]

Find the data matrix for the letter obtained by:

1.
Rotating the letter through \(\frac {\pi }{4}\) about the origin.
2.
Rotating the letter through \(\frac {\pi }{4}\) about the point \(\left [ \begin{array}{c} 1\\ 2 \end{array} \right ]\).

Click the arrow to see the answer.

\(\frac {1}{2}\left [ \begin{array}{ccccc} \sqrt {2} + 2 & 7\sqrt {2} + 2 & 3\sqrt {2} + 2 & -\sqrt {2} + 2 & -5\sqrt {2} + 2\\ -3\sqrt {2} + 4 & 3\sqrt {2} + 4 & 5\sqrt {2} + 4 & \sqrt {2} + 4 & 9\sqrt {2} + 4 \\ 2 & 2 & 2 & 2 & 2 \end{array} \right ]\)
Find the \(3 \times 3\) matrix for reflecting in the line \(y = mx + b\). Use \(\left [ \begin{array}{c} 1\\ m \end{array} \right ]\) as direction vector for the line.
Find the \(3 \times 3\) matrix for rotating through the angle \(\theta \) about the point \(P(a, b)\).
Find the reflection of the point \(P\) in the line \(y = 1 + 2x\) in \(\RR ^2\) if:
1.
\(P = P(1, 1)\)
2.
\(P = P(1, 4)\)

Click the arrow to see the answer.

\(P(\frac {9}{5}, \frac {18}{5})\)
3.
What about \(P = P(1, 3)\)? Explain.
See Example 1.