Chapter 6

Transformation Matrices

The machinery of linear algebra can be used to express many of the operations required to arrange objects in a 3D scene, view them with cameras, and get them onto the screen. Geometric transformations like rotation, translation, scaling, and projection can be accomplished with matrix multiplication, and the transformation matrices used to do this are the subject of this chapter.

We will show how a set of points transforms if the points are represented as offset vectors from the origin, and we will use the clock shown in Figure 6.1 as an example of a point set. So think of the clock as a bunch of points that are the ends of vectors whose tails are at the origin. We also discuss how these transforms operate differently on locations (points), displacement vectors, and surface normal vectors.

6.1 2D Linear Transformations

We can use a 2 × 2 matrix to change, or transform, a 2D vector:

$\left[\begin{array}{ll}{a}_{11}\hfill & a_{12}\hfill \\ a_{21}\hfill & a_{22}\hfill \end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}{a}_{11}x+a_{12}y\\ a_{21}x+a_{22}y\end{array}\right].$

This kind of operation, which takes in a 2-vector and produces another 2-vector by a simple matrix multiplication, is a linear transformation.

By this simple formula we can achieve a variety of useful transformations, depending on what we put in the entries of the matrix, as will be discussed in the following sections. For our purposes, consider moving along the x-axis a horizontal move and along the y-axis, a vertical move.

6.1.1 Scaling

The most basic transform is a scale along the coordinate axes. This transform can change length and possibly direction:

$\text{scale}\left(s_x,s_y\right)=\left[\begin{array}{ll}{s}_x\hfill & 0\hfill \\ 0\hfill & s_y\hfill \end{array}\right].$

Note what this matrix does to a vector with Cartesian components (x, y):

$\left[\begin{array}{ll}{s}_x\hfill & 0\hfill \\ 0\hfill & s_y\hfill \end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}{s}_{x}x\\ s_{y}y\end{array}\right].$

So, just by looking at the matrix of an axis-aligned scale, we can read off the two scale factors.

Example.

The matrix that shrinks x and y uniformly by a factor of two is (Figure 6.1)

$\text{scale}\left(\text{0}\text{.5,}\text{0}\text{.5}\right)=\left[\begin{array}{cc}0.5& 0\\ 0& 0.5\end{array}\right].$

A matrix which halves in the horizontal and increases by three-halves in the vertical is (see Figure 6.2)

$\text{scale}\left(\text{0}\text{.5,}\text{1}\text{.5}\right)=\left[\begin{array}{cc}0.5& 0\\ 0& 1.5\end{array}\right].$

6.1.2 Shearing

A shear is something that pushes things sideways, producing something like a deck of cards across which you push your hand; the bottom card stays put and cards move more the closer they are to the top of the deck. The horizontal and vertical shear matrices are

$\text{shear-x}\left(s\right)=\left[\begin{array}{cc}1& s\\ 0& 1\end{array}\right],\text{shear-y}\left(s\right)=\left[\begin{array}{cc}1& 0\\ s& 1\end{array}\right].$

Example.

The transform that shears horizontally so that vertical lines become 45° lines leaning toward the right is (see Figure 6.3)

$\text{shear-x}\left(1\right)=\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right].$

An analogous transform vertically is (see Figure 6.4)

$\text{shear-y}\left(1\right)=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right].$

In both cases, the square outline of the sheared clock becomes a parallelogram, and the circular face of the sheared clock becomes an ellipse.

Another way to think of a shear is in terms of rotation of only the vertical (or horizontal) axis. The shear transform that takes a vertical axis and tilts it clockwise by an angle ϕ is

$\left[\begin{array}{cc}\text{1}& \text{tan}\varphi \\ \text{0}& \text{1}\end{array}\right].$

Similarly, the shear matrix which rotates the horizontal axis counterclockwise by angle ϕ is

$\left[\begin{array}{cc}\text{1}& 0\\ \text{tan}\varphi & \text{1}\end{array}\right].$

6.1.3 Rotation

Suppose we want to rotate a vector a by an angle ϕ counterclockwise to get vector b (Figure 6.5). If a makes an angle α with the x-axis, and its length is $r=\sqrt{x_a^2+y_a^2}$, then we know that

$\begin{array}{c}{x}_a=r\cos \alpha ,\\ y_a=r\sin \alpha .\end{array}$

Because b is a rotation of a, it also has length r. Because it is rotated an angle ϕ from a, b makes an angle (α + ϕ) with the x-axis. Using the trigonometric addition identities (Section 2.3.3):

$\begin{array}{c}{x}_b=r\cos \left(\alpha +\varphi \right)=r\cos \alpha \cos \varphi -r\sin \alpha \sin \varphi ,\\ y_b=r\sin \left(\alpha +\varphi \right)=r\sin \alpha \cos \varphi +r\cos \alpha \sin \varphi .\end{array}\text{ (6.1)}$

Substituting xa = r cos α and ya = r sin α gives

$\begin{array}{c}{x}_b=x_a\cos \varphi -y_a\sin \varphi ,\\ y_b=y_a\cos \varphi +x_a\sin \varphi .\end{array}$

In matrix form, the transformation that takes a to b is then

$\text{rotate}\left(\varphi \right)=\left[\begin{array}{rr}\hfill \cos \varphi & \hfill -\sin \varphi \\ \hfill \sin \varphi & \hfill \cos \varphi \end{array}\right].$

Example

A matrix that rotates vectors by π/4 radians (45 degrees) is (see Figure 6.6)

$\left[\begin{array}{rr}\hfill \cos \frac{\pi }{4}& \hfill -\sin \frac{\pi }{4}\\ \hfill \sin \frac{\pi }{4}& \hfill \cos \frac{\pi }{4}\end{array}\right]=\left[\begin{array}{rr}\hfill 0.707& \hfill -0.707\\ \hfill 0.707& \hfill 0.707\end{array}\right].$

A matrix that rotates by π/6 radians (30 degrees) in the clockwise direction is a rotation by −π/6 radians in our framework (see Figure 6.7):

$\left[\begin{array}{rr}\hfill \cos \frac{-\pi }{6}& \hfill -\sin \frac{-\pi }{6}\\ \hfill \sin \frac{-\pi }{6}& \hfill \cos \frac{-\pi }{6}\end{array}\right]=\left[\begin{array}{ll}0.866\hfill & 0.5\hfill \\ -0.5\hfill & 0.866\hfill \end{array}\right].$

Because the norm of each row of a rotation matrix is one (sin2ϕ+cos2ϕ = 1), and the rows are orthogonal (cos ϕ(−sin ϕ) + sin ϕ cos ϕ = 0), we see that rotation matrices are orthogonal matrices (Section 5.2.4). By looking at the matrix we can read off two pairs of orthonormal vectors: the two columns, which are the vectors to which the transformation sends the canonical basis vectors (1, 0) and (0, 1); and the rows, which are the vectors that the transformations sends to the canonical basis vectors.

6.1.4 Reflection

We can reflect a vector across either of the coordinate axes by using a scale with one negative scale factor (see Figures 6.8 and 6.9):

$\text{reflect-y}=\left[\begin{array}{rr}\hfill -1& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right],\text{reflect-x}=\left[\begin{array}{rr}\hfill 1& \hfill 0\\ \hfill 0& \hfill -1\end{array}\right].$

While one might expect that the matrix with −1 in both elements of the diagonal is also a reflection, in fact it is just a rotation by π radians.

6.1.5 Composition and Decomposition of Transformations

It is common for graphics programs to apply more than one transformation to an object. For example, we might want to first apply a scale S, and then a rotation R. This would be done in two steps on a 2D vector v1:

$\text{first},{\mathbf{\text{v}}}_{\text{2}}={\mathbf{Sv}}_{\text{1}},\text{then},{\mathbf{v}}_{\text{3}}={\mathbf{Rv}}_{\text{2}}.$

Another way to write this is

$v_{\text{3}}=R\left({\mathrm{Sv}}_{\text{1}}\right).$

Because matrix multiplication is associative, we can also write

$v_{\text{3}}=\left(\mathrm{RS}\right)v_{\text{1}}.$

In other words, we can represent the effects of transforming a vector by two matrices in sequence using a single matrix of the same size, which we can compute by multiplying the two matrices: M = RS (Figure 6.10).

It is very important to remember that these transforms are applied from the right side first. So the matrix M = RS first applies S and then R.

Example.

Suppose we want to scale by one-half in the vertical direction and then rotate by π/4 radians (45 degrees). The resulting matrix is

$\left[\begin{array}{rr}\hfill 0.707& \hfill -0.707\\ \hfill 0.707& \hfill 0.707\end{array}\right]\left[\begin{array}{cc}1& 0\\ 0& 0.5\end{array}\right]=\left[\begin{array}{rr}\hfill 0.707& \hfill -0.353\\ \hfill 0.707& \hfill 0.353\end{array}\right].$

It is important to always remember that matrix multiplication is not commutative. So the order of transforms does matter. In this example, rotating first, and then scaling, results in a different matrix (see Figure 6.11):

$\left[\begin{array}{cc}1& 0\\ 0& 0.5\end{array}\right]\left[\begin{array}{rr}\hfill 0.707& \hfill -0.707\\ \hfill 0.707& \hfill 0.707\end{array}\right]=\left[\begin{array}{rr}\hfill 0.707& \hfill -0.707\\ \hfill 0.353& \hfill 0.353\end{array}\right].$

Example.

Using the scale matrices we have presented, nonuniform scaling can only be done along the coordinate axes. If we wanted to stretch our clock by 50% along one of its diagonals, so that 8:00 through 1:00 move to the northwest and 2:00 through 7:00 move to the southeast, we can use rotation matrices in combination with an axis-aligned scaling matrix to get the result we want. The idea is to use a rotation to align the scaling axis with a coordinate axis, then scale along that axis, then rotate back. In our example, the scaling axis is the “backslash” diagonal of the square, and we can make it parallel to the x-axis with a rotation by +45°. Putting these operations together, the full transformation is

$\text{rotate}\left(-45°\right)\text{scale}\left(\text{1}\text{.5,}\text{1}\right)\text{rotate}\left(45°\right).$

In mathematical notation, this can be written RSRT. The result of multiplying the three matrices together is

$\left[\begin{array}{rr}\hfill 1.25& \hfill -0.25\\ \hfill -0.25& \hfill 1.25\end{array}\right]$

Building up a transformation from rotation and scaling transformations actually works for any linear transformation, and this fact leads to a powerful way of thinking about these transformations, as explored in the next section.

6.1.6 Decomposition of Transformations

Sometimes it’s necessary to “undo” a composition of transformations, taking a transformation apart into simpler pieces. For instance, it’s often useful to present a transformation to the user for manipulation in terms of separate rotations and scale factors, but a transformation might be represented internally simply as a matrix, with the rotations and scales already mixed together. This kind of manipulation can be achieved if the matrix can be computationally disassembled into the desired pieces, the pieces adjusted, and the matrix reassembled by multiplying the pieces together again.

It turns out that this decomposition, or factorization, is possible, regardless of the entries in the matrix—and this fact provides a fruitful way of thinking about transformations and what they do to geometry that is transformed by them.

Symmetric Eigenvalue Decomposition

Let’s start with symmetric matrices. Recall from Section 5.4 that a symmetric matrix can always be taken apart using the eigenvalue decomposition into a product of the form

$A={\mathrm{RSR}}^{\text{T}}$

where R is an orthogonal matrix and S is a diagonal matrix; we will call the columns of R (the eigenvectors) by the names v1 and v2, and we’ll call the diagonal entries of S (the eigenvalues) by the names λ1 and λ2.

In geometric terms we can now recognize R as a rotation and S as a scale, so this is just a multi-step geometric transformation (Figure 6.13):

1. Rotate v1 and v2 to the x- and y-axes (the transform by RT).
2. Scale in x and y by (λ1, λ2) (the transform by S).
3. Rotate the x- and y-axes back to v1 and v2 (the transform by R).

Looking at the effect of these three transforms together, we can see that they have the effect of a nonuniform scale along a pair of axes. As with an axis-aligned scale, the axes are perpendicular, but they aren’t the coordinate axes; instead they are the eigenvectors of A. This tells us something about what it means to be a symmetric matrix: symmetric matrices are just scaling operations—albeit potentially nonuniform and non-axis-aligned ones.

Example.

Recall the example from Section 5.4:

$\begin{array}{cc}\hfill \left[\begin{array}{ll}\text{2}\hfill & \text{1}\hfill \\ \text{1}\hfill & \text{1}\hfill \end{array}\right]& =R\left[\begin{array}{ll}{\text{λ}}_{\text{1}}\hfill & \text{0}\hfill \\ \text{0}\hfill & {\text{λ}}_{\text{2}}\hfill \end{array}\right]R^{\text{T}}\hfill \\ \hfill & =\left[\begin{array}{rr}\hfill 0.8507& \hfill -0.5257\\ \hfill 0.5257& \hfill 0.8507\end{array}\right]\left[\begin{array}{cc}\hfill 2.618& 0\hfill \\ \hfill 0& 0.382\hfill \end{array}\right]\left[\begin{array}{rr}\hfill 0.8507& \hfill 0.5257\\ \hfill -0.5257& \hfill 0.8507\end{array}\right]\hfill \\ \hfill & =\text{rotate}\left(\text{31}\text{.7}°\right)\text{scale}\left(\text{2}\text{.618,}\text{0}\text{.382}\right)\text{rotate}\left(-\text{31}\text{.7}°\right)\hfill \end{array}$

The matrix above, then, according to its eigenvalue decomposition, scales in a direction 31.7° counterclockwise from three o’clock (the x-axis). This is a touch before 2 p.m. on the clockface as is confirmed by Figure 6.14.

We can also reverse the diagonalization process; to scale by (λ1, λ2) with the first scaling direction an angle ϕ clockwise from the x-axis, we have

$\left[\begin{array}{rr}\hfill \text{cos}\varphi & \hfill \sin \varphi \\ \hfill -\sin \varphi & \hfill \cos \varphi \end{array}\right]\left[\begin{array}{rr}\hfill {\text{λ}}_{\text{1}}& \hfill \text{0}\\ \hfill \text{0}& \hfill {\text{λ}}_{\text{2}}\end{array}\right]\left[\begin{array}{rr}\hfill \text{cos}\varphi & \hfill -\sin \varphi \\ \hfill \sin \varphi & \hfill \cos \varphi \end{array}\right]=\left[\begin{array}{ll}{\text{λ}}_{\text{1}}{\text{cos}}^{\text{2}}\varphi +{\text{λ}}_{\text{2}}{\text{sin}}^{\text{2}}\varphi \hfill & \left({\text{λ}}_{\text{2}}-{\text{λ}}_{\text{1}}\right)\cos \varphi \sin \varphi \hfill \\ \left({\text{λ}}_{\text{2}}-{\text{λ}}_{\text{1}}\right)\cos \varphi \sin \varphi \hfill & {\text{λ}}_{\text{2}}{\text{cos}}^{\text{2}}\varphi +{\text{λ}}_{\text{1}}{\text{sin}}^{\text{2}}\varphi \hfill \end{array}\right].$

We should take heart that this is a symmetric matrix as we know must be true since we constructed it from a symmetric eigenvalue decomposition.

Singular Value Decomposition

A very similar kind of decomposition can be done with nonsymmetric matrices as well: it’s the Singular Value Decomposition (SVD), also discussed in Section 5.4.1. The difference is that the matrices on either side of the diagonal matrix are no longer the same:

$A={\mathrm{USV}}^{\text{T}}$

The two orthogonal matrices that replace the single rotation R are called U and V, and their columns are called ui (the left singular vectors) and vi (the right singular vectors), respectively. In this context, the diagonal entries of S are called singular values rather than eigenvalues. The geometric interpretation is very similar to that of the symmetric eigenvalue decomposition (Figure 6.15):

1. Rotate v1 and v2 to the x- and y-axes (the transform by VT).
2. Scale in x and y by (σ1, σ2) (the transform by S).
3. Rotate the x- and y-axes to u1 and u2 (the transform by U).

The principal difference is between a single rotation and two different orthogonal matrices. This difference causes another, less important, difference. Because the SVD has different singular vectors on the two sides, there is no need for negative singular values: we can always flip the sign of a singular value, reverse the direction of one of the associated singular vectors, and end up with the same transformation again. For this reason, the SVD always produces a diagonal matrix with all positive entries, but the matrices U and V are not guaranteed to be rotations—they could include reflection as well. In geometric applications like graphics this is an inconvenience, but a minor one: it is easy to differentiate rotations from reflections by checking the determinant, which is +1 for rotations and −1 for reflections, and if rotations are desired, one of the singular values can be negated, resulting in a rotation-scale-rotation sequence where the reflection is rolled in with the scale, rather than with one of the rotations.

Example.

The example used in Section 5.4.1 is in fact a shear matrix (Figure 6.12):

$\begin{array}{cc}\hfill \left[\begin{array}{ll}1\hfill & 1\hfill \\ 0\hfill & 1\hfill \end{array}\right]& =R_2\left[\begin{array}{ll}{\sigma }_1\hfill & 0\hfill \\ 0\hfill & {\sigma }_2\hfill \end{array}\right]R_1\hfill \\ \hfill & =\left[\begin{array}{rr}\hfill 0.8507& \hfill -0.5257\\ \hfill 0.5257& \hfill 0.8507\end{array}\right]\left[\begin{array}{cc}\hfill 1.618& 0\hfill \\ \hfill 0& 0.618\hfill \end{array}\right]\left[\begin{array}{rr}\hfill 0.5257& \hfill 0.8507\\ \hfill -0.8507& \hfill 0.5257\end{array}\right]\hfill \\ \hfill & =\text{rotate}\left(\text{31}\text{.7}°\right)\text{scale}\left(\text{1}\text{.618,}\text{0}\text{.618}\right)\text{rotate}\left(-58.3°\right)\hfill \end{array}$

An immediate consequence of the existence of SVD is that all the 2D transformation matrices we have seen can be made from rotation matrices and scale matrices. Shear matrices are a convenience, but they are not required for expressing transformations.

In summary, every matrix can be decomposed via SVD into a rotation times a scale times another rotation. Only symmetric matrices can be decomposed via eigenvalue diagonalization into a rotation times a scale times the inverse-rotation, and such matrices are a simple scale in an arbitrary direction. The SVD of a symmetric matrix will yield the same triple product as eigenvalue decomposition via a slightly more complex algebraic manipulation.

Paeth Decomposition of Rotations

Another decomposition uses shears to represent nonzero rotations (Paeth, 1990). The following identity allows this:

$\left[\begin{array}{rr}\hfill \text{cos}\varphi & \hfill -\sin \varphi \\ \hfill \sin \varphi & \hfill \cos \varphi \end{array}\right]=\left[\begin{array}{cc}1& \frac{\cos \varphi -1}{\sin \varphi }\\ 0& 1\end{array}\right]\left[\begin{array}{cc}1& 0\\ \sin \varphi & 1\end{array}\right]\left[\begin{array}{cc}1& \frac{\cos \varphi -1}{\sin \varphi }\\ 0& 1\end{array}\right].$

For example, a rotation by π/4 (45 degrees) is (see Figure 6.16)

$\text{rotate}\left(\frac{\pi }{\text{4}}\right)=\left[\begin{array}{cc}1& 1-\sqrt{2}\\ 0& 1\end{array}\right]\left[\begin{array}{cc}1& 0\\ \frac{\sqrt{2}}{2}& 1\end{array}\right]\left[\begin{array}{cc}1& 1-\sqrt{2}\\ 0& 1\end{array}\right].\text{ (6.2)}$

This particular transform is useful for raster rotation because shearing is a very efficient raster operation for images; it introduces some jagginess, but will leave no holes. The key observation is that if we take a raster position (i, j) and apply a horizontal shear to it, we get

$\left[\begin{array}{ll}1\hfill & s\hfill \\ 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{c}i\\ j\end{array}\right]=\left[\begin{array}{c}i+sj\\ j\end{array}\right].$

If we round sj to the nearest integer, this amounts to taking each row in the image and moving it sideways by some amount—a different amount for each row. Because it is the same displacement within a row, this allows us to rotate with no gaps in the resulting image. A similar action works for a vertical shear. Thus, we can implement a simple raster rotation easily.

6.2 3D Linear Transformations

The linear 3D transforms are an extension of the 2D transforms. For example, a scale along Cartesian axes is

$\text{scale}\left(s_x,s_y,s_z\right)=\left[\begin{array}{lll}{s}_x\hfill & 0\hfill & 0\hfill \\ 0\hfill & s_y\hfill & 0\hfill \\ 0\hfill & 0\hfill & s_z\hfill \end{array}\right].\text{ (6.3)}$

Rotation is considerably more complicated in 3D than in 2D, because there are more possible axes of rotation. However, if we simply want to rotate about the z-axis, which will only change x- and y-coordinates, we can use the 2D rotation matrix with no operation on z:

$\text{rotate-z}\left(\varphi \right)=\left[\begin{array}{ccc}\cos \varphi & -\sin \varphi & 0\\ \sin \varphi & \cos \varphi & 0\\ 0& 0& 1\end{array}\right].$

Similarly we can construct matrices to rotate about the x-axis and the y-axis:

$\begin{array}{c}\text{rotate-x}\left(\varphi \right)=\left[\begin{array}{ccc}1& 0& 0\\ 0& \cos \varphi & -\sin \varphi \\ 0& \sin \varphi & \cos \varphi \end{array}\right],\\ \text{rotate-y}\left(\varphi \right)=\left[\begin{array}{ccc}\cos \varphi & 0& \sin \varphi \\ 0& 1& 0\\ -\sin \varphi & 0& \cos \varphi \end{array}\right].\end{array}$

We will discuss rotations about arbitrary axes in the next section.

As in two dimensions, we can shear along a particular axis, for example,

$\text{shear-x}\left(d_y,d_z\right)=\left[\begin{array}{ccc}1& d_y& d_z\\ 0& 1& 0\\ 0& 0& 1\end{array}\right].$

As with 2D transforms, any 3D transformation matrix can be decomposed using SVD into a rotation, scale, and another rotation. Any symmetric 3D matrix has an eigenvalue decomposition into rotation, scale, and inverse-rotation. Finally, a 3D rotation can be decomposed into a product of 3D shear matrices.

6.2.1 Arbitrary 3D Rotations

As in 2D, 3D rotations are orthogonal matrices. Geometrically, this means that the three rows of the matrix are the Cartesian coordinates of three mutually orthogonal unit vectors as discussed in Section 2.4.5. The columns are three, potentially different, mutually orthogonal unit vectors. There are an infinite number of such rotation matrices. Let’s write down such a matrix:

${\text{R}}_{uvw}=\left[\begin{array}{lll}{x}_u\hfill & y_u\hfill & z_u\hfill \\ x_v\hfill & y_v\hfill & z_v\hfill \\ x_w\hfill & y_w\hfill & z_w\hfill \end{array}\right].$

Here, u = xux + yuy + zuz and so on for v and w. Since the three vectors are orthonormal we know that

$\begin{array}{c}u\cdot u=v\cdot v=w\cdot w=1,\\ u\cdot v=v\cdot w=w\cdot u=0.\end{array}$

We can infer some of the behavior of the rotation matrix by applying it to the vectors u, v and w. For example,

$R_{uvw}u=\left[\begin{array}{lll}{x}_u\hfill & y_u\hfill & z_u\hfill \\ x_v\hfill & y_v\hfill & z_v\hfill \\ x_w\hfill & y_w\hfill & z_w\hfill \end{array}\right]\left[\begin{array}{c}{x}_u\\ y_u\\ z_u\end{array}\right]=\left[\begin{array}{l}{x}_u{x}_u+y_u{y}_u+z_u{z}_u\hfill \\ x_v{x}_u+y_v{y}_u+z_v{z}_u\hfill \\ x_w{x}_u+y_w{y}_u+z_w{z}_u\hfill \end{array}\right].$

Note that those three rows of Ruvwu are all dot products:

$R_{uvw}u=\left[\begin{array}{l}u\cdot u\hfill \\ v\cdot u\hfill \\ w\cdot u\hfill \end{array}\right]=\left[\begin{array}{l}1\hfill \\ 0\hfill \\ 0\hfill \end{array}\right]=x\text{.}$

Similarly, Ruvwv = y, and Ruvww = z. So Ruvw takes the basis uvw to the corresponding Cartesian axes via rotation.

If Ruvw is a rotation matrix with orthonormal rows, then $R_{uvw}^{\text{T}}$ is also a rotation matrix with orthonormal columns, and in fact is the inverse of Ruvw (the inverse of an orthogonal matrix is always its transpose). An important point is that for transformation matrices, the algebraic inverse is also the geometric inverse. So if Ruvw takes u to x, then $R_{uvw}^{\text{T}}$ takes x to u. The same should be true of v and y as we can confirm:

$R_{uvw}^{\text{T}}y=\left[\begin{array}{lll}{x}_u\hfill & x_v\hfill & x_w\hfill \\ y_u\hfill & y_v\hfill & y_w\hfill \\ z_u\hfill & z_v\hfill & z_w\hfill \end{array}\right]\left[\begin{array}{c}0\\ 1\\ 0\end{array}\right]=\left[\begin{array}{c}{x}_v\\ y_v\\ z_v\end{array}\right]=v\text{.}$

So we can always create rotation matrices from orthonormal bases.

If we wish to rotate about an arbitrary vector a, we can form an orthonormal basis with w = a, rotate that basis to the canonical basis xyz, rotate about the z-axis, and then rotate the canonical basis back to the uvw basis. In matrix form, to rotate about the w-axis by an angle ϕ:

$\left[\begin{array}{lll}{x}_u\hfill & x_v\hfill & x_w\hfill \\ y_u\hfill & y_v\hfill & y_w\hfill \\ z_u\hfill & z_v\hfill & z_w\hfill \end{array}\right]\left[\begin{array}{ccc}\cos \varphi & -\sin \varphi & 0\\ \sin \varphi & \cos \varphi & 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{lll}{x}_u\hfill & y_u\hfill & z_u\hfill \\ x_v\hfill & y_v\hfill & z_v\hfill \\ x_w\hfill & y_w\hfill & z_w\hfill \end{array}\right].$

Here we have w a unit vector in the direction of a (i.e., a divided by its own length). But what are u and v? A method to find reasonable u and v is given in Section 2.4.6.

If we have a rotation matrix and we wish to have the rotation in axis-angle form, we can compute the one real eigenvalue (which will be λ = 1), and the corresponding eigenvector is the axis of rotation. This is the one axis that is not changed by the rotation.

See Chapter 16 for a comparison of the few most-used ways to represent rotations, besides rotation matrices.

6.2.2 Transforming Normal Vectors

While most 3D vectors we use represent positions (offset vectors from the origin) or directions, such as where light comes from, some vectors represent surface normals. Surface normal vectors are perpendicular to the tangent plane of a surface. These normals do not transform the way we would like when the underlying surface is transformed. For example, if the points of a surface are transformed by a matrix M, a vector t that is tangent to the surface and is multiplied by M will be tangent to the transformed surface. However, a surface normal vector n that is transformed by M may not be normal to the transformed surface (Figure 6.17).

We can derive a transform matrix N which does take n to a vector perpendicular to the transformed surface. One way to attack this issue is to note that a surface normal vector and a tangent vector are perpendicular, so their dot product is zero, which is expressed in matrix form as

${\mathbf{n}}^{\text{T}}\mathbf{t}=\mathbf{0}.\text{ (6.4)}$

If we denote the desired transformed vectors as tM = Mt and nN = Nn, our goal is to find N such that ${\mathbf{n}}_N^{\text{T}}{\mathbf{t}}_M=\mathbf{0}$. We can find N by some algebraic tricks. First, we can sneak an identity matrix into the dot product, and then take advantage of M−1M = I:

$n^{\text{T}}t=n^{\text{T}}\mathrm{It}=n^{\text{T}}{M}^{-1}\mathrm{Mt}=0\text{.}$

Although the manipulations above don’t obviously get us anywhere, note that we can add parentheses that make the above expression more obviously a dot product:

$\left({\mathbf{n}}^{\text{T}}{\mathbf{M}}^{-1}\right)\left(\mathbf{Mt}\right)=\left({\mathbf{n}}^{\text{T}}{\mathbf{M}}^{-1}\right){\mathbf{t}}_{\mathbf{M}}=\mathbf{0}$

This means that the row vector that is perpendicular to tM is the left part of the expression above. This expression holds for any of the tangent vectors in the tangent plane. Since there is only one direction in 3D (and its opposite) that is perpendicular to all such tangent vectors, we know that the left part of the expression above must be the row vector expression for nN, i.e., it is $n_N^{\text{T}}$, so this allows us to infer N:

$n_N^{\text{T}}=n^{\text{T}}{M}^{-1},$

so we can take the transpose of that to get

$n_N={\left(n^{\text{T}}{M}^{-1}\right)}^{\text{T}}={\left(M^{-1}\right)}^{\text{T}}n\text{.}\text{ (6.5)}$

Therefore, we can see that the matrix which correctly transforms normal vectors so they remain normal is N = (M−1)T, i.e., the transpose of the inverse matrix. Since this matrix may change the length of n, we can multiply it by an arbitrary scalar and it will still produce nN with the right direction. Recall from Section 5.3 that the inverse of a matrix is the transpose of the cofactor matrix divided by the determinant. Because we don’t care about the length of a normal vector, we can skip the division and find that for a 3 × 3 matrix,

$N=\left[\begin{array}{lll}{m}_{11}^c\hfill & m_{12}^c\hfill & m_{13}^c\hfill \\ m_{21}^c\hfill & m_{22}^c\hfill & m_{23}^c\hfill \\ m_{31}^c\hfill & m_{32}^c\hfill & m_{33}^c\hfill \end{array}\right].$

This assumes the element of M in row i and column j is mij. So the full expression for N is

$N=\left[\begin{array}{lll}{m}_{22}{m}_{33}-m_{23}{m}_{32}\hfill & m_{23}{m}_{31}-m_{21}{m}_{33}\hfill & m_{21}{m}_{32}-m_{22}{m}_{31}\hfill \\ m_{13}{m}_{32}-m_{12}{m}_{33}\hfill & m_{11}{m}_{33}-m_{13}{m}_{31}\hfill & m_{12}{m}_{31}-m_{11}{m}_{32}\hfill \\ m_{12}{m}_{23}-m_{13}{m}_{22}\hfill & m_{13}{m}_{21}-m_{11}{m}_{23}\hfill & m_{11}{m}_{22}-m_{12}{m}_{21}\hfill \end{array}\right].$

6.3 Translation and Affine Transformations

We have been looking at methods to change vectors using a matrix M. In two dimensions, these transforms have the form,

$\begin{array}{ccccc}{x}^{\prime }& =& m_{11}x& +& m_{12}y,\\ y^{\prime }& =& m_{21}x& +& m_{22}y.\end{array}$

We cannot use such transforms to move objects, only to scale and rotate them. In particular, the origin (0, 0) always remains fixed under a linear transformation. To move, or translate, an object by shifting all its points the same amount, we need a transform of the form,

$\begin{array}{ccccc}{x}^{\prime }& =& x& +& x_t,\\ y^{\prime }& =& y& +& y_t.\end{array}$

There is just no way to do that by multiplying (x, y) by a 2 × 2 matrix. One possibility for adding translation to our system of linear transformations is to simply associate a separate translation vector with each transformation matrix, letting the matrix take care of scaling and rotation and the vector take care of translation. This is perfectly feasible, but the bookkeeping is awkward and the rule for composing two transformations is not as simple and clean as with linear transformations.

Instead, we can use a clever trick to get a single matrix multiplication to do both operations together. The idea is simple: represent the point (x, y) by a 3D vector [x y 1]T, and use 3 × 3 matrices of the form

$\left[\begin{array}{lll}{m}_{11}\hfill & m_{12}\hfill & x_t\hfill \\ m_{21}\hfill & m_{22}\hfill & y_t\hfill \\ 0\hfill & 0\hfill & 1\hfill \end{array}\right].$

The fixed third row serves to copy the 1 into the transformed vector, so that all vectors have a 1 in the last place, and the first two rows compute x' and y' as linear combinations of x, y, and 1:

$\left[\begin{array}{c}{x}^{\prime }\\ y^{\prime }\\ 1\end{array}\right]=\left[\begin{array}{lll}{m}_{11}\hfill & m_{12}\hfill & x_t\hfill \\ m_{21}\hfill & m_{22}\hfill & y_t\hfill \\ 0\hfill & 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{c}x\\ y\\ 1\end{array}\right]=\left[\begin{array}{c}{m}_{11}x+m_{12}y+x_t\\ m_{21}x+m_{22}y+y_t\\ 1\end{array}\right].$

The single matrix implements a linear transformation followed by a translation! This kind of transformation is called an affine transformation, and this way of implementing affine transformations by adding an extra dimension is called homogeneous coordinates (Roberts, 1965; Riesenfeld, 1981; Penna & Patterson, 1986). Homogeneous coordinates not only clean up the code for transformations, but this scheme also makes it obvious how to compose two affine transformations: simply multiply the matrices.

A problem with this new formalism arises when we need to transform vectors that are not supposed to be positions—they represent directions, or offsets between positions. Vectors that represent directions or offsets should not change when we translate an object. Fortunately, we can arrange for this by setting the third coordinate to zero:

$\left[\begin{array}{lll}1\hfill & 0\hfill & x_t\hfill \\ 0\hfill & 1\hfill & y_t\hfill \\ 0\hfill & 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{c}x\\ y\\ 0\end{array}\right]=\left[\begin{array}{c}x\\ y\\ 0\end{array}\right].$

If there is a scaling/rotation transformation in the upper-left 2 × 2 entries of the matrix, it will apply to the vector, but the translation still multiplies with the zero and is ignored. Furthermore, the zero is copied into the transformed vector, so direction vectors remain direction vectors after they are transformed.

This is exactly the behavior we want for vectors, so they fit smoothly into the system: the extra (third) coordinate will be either 1 or 0 depending on whether we are encoding a position or a direction. We actually do need to store the homogeneous coordinate so we can distinguish between locations and other vectors. For example,

$\left[\begin{array}{c}3\\ 2\\ 1\end{array}\right]\text{is}a\text{location}\text{and}\left[\begin{array}{c}\text{3}\\ \text{2}\\ \text{0}\end{array}\right]\text{is}a\text{displacement}\text{or}\text{direction}\text{.}$

Later, when we do perspective viewing, we will see that it is useful to allow the homogeneous coordinate to take on values other than one or zero.

Homogeneous coordinates are used nearly universally to represent transformations in graphics systems. In particular, homogeneous coordinates underlie the design and operation of renderers implemented in graphics hardware. We will see in Chapter 7 that homogeneous coordinates also make it easy to draw scenes in perspective, another reason for their popularity.

Homogeneous coordinates can be considered just a clever way to handle the bookkeeping for translation, but there is also a different, geometric interpretation. The key observation is that when we do a 3D shear based on the z-coordinate we get this transform:

$\left[\begin{array}{lll}1\hfill & 0\hfill & x_t\hfill \\ 0\hfill & 1\hfill & y_t\hfill \\ 0\hfill & 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{c}x\\ y\\ z\end{array}\right]=\left[\begin{array}{c}x+x_{t}z\\ y+y_{t}z\\ z\end{array}\right].$

Note that this almost has the form we want in x and y for a 2D translation, but has a z hanging around that doesn’t have a meaning in 2D. Now comes the key decision: we will add a coordinate z = 1 to all 2D locations. This gives us

$\left[\begin{array}{lll}1\hfill & 0\hfill & x_t\hfill \\ 0\hfill & 1\hfill & y_t\hfill \\ 0\hfill & 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{c}x\\ y\\ 1\end{array}\right]=\left[\begin{array}{c}x+x_t\\ y+y_t\\ 1\end{array}\right].$

By associating a (z = 1)-coordinate with all 2D points, we now can encode translations into matrix form. For example, to first translate in 2D by (xt, yt) and then rotate by angle ϕ we would use the matrix

$M=\left[\begin{array}{ccc}\cos \varphi & -\sin \varphi & 0\\ \sin \varphi & \cos \varphi & 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& x_t\\ 0& 1& y_t\\ 0& 0& 1\end{array}\right].$

Note that the 2D rotation matrix is now 3 × 3 with zeros in the “translation slots.” With this type of formalism, which uses shears along z = 1 to encode translations, we can represent any number of 2D shears, 2D rotations, and 2D translations as one composite 3D matrix. The bottom row of that matrix will always be (0, 0, 1), so we don’t really have to store it. We just need to remember it is there when we multiply two matrices together.

In 3D, the same technique works: we can add a fourth coordinate, a homogeneous coordinate, and then we have translations:

$\left[\begin{array}{llll}\text{1}\hfill & \text{0}\hfill & \text{0}\hfill & x_t\hfill \\ \text{0}\hfill & \text{1}\hfill & \text{0}\hfill & y_t\hfill \\ \text{0}\hfill & \text{0}\hfill & \text{1}\hfill & z_t\hfill \\ \text{0}\hfill & \text{0}\hfill & \text{0}\hfill & 1\hfill \end{array}\right]\left[\begin{array}{c}x\\ y\\ z\\ 1\end{array}\right]=\left[\begin{array}{c}x+x_t\\ y+y_t\\ z+z_t\\ 1\end{array}\right].$

Again, for a direction vector, the fourth coordinate is zero and the vector is thus unaffected by translations.

Example (Windowing transformations).

Often in graphics we need to create a transform matrix that takes points in the rectangle [xl, xh] × [yl, yh] to the rectangle $\left[{x^{\prime }}_l,{x^{\prime }}_h\right]\times \left[{y^{\prime }}_l,{y^{\prime }}_h\right]$. This can be accomplished with a single scale and translate in sequence. However, it is more intuitive to create the transform from a sequence of three operations (Figure 6.18):

1. Move the point (xl, yl) to the origin.
2. Scale the rectangle to be the same size as the target rectangle.
3. Move the origin to point $\left({x^{\prime }}_l,{y^{\prime }}_l\right)$.

Remembering that the right-hand matrix is applied first, we can write

$\begin{array}{c}\text{window}=\text{translate}\left({x^{\prime }}_l,{y^{\prime }}_l\right)\text{scale}\left(\frac{{x^{\prime }}_h-{x^{\prime }}_l}{x_h-x_l},\frac{{y^{\prime }}_h-{y^{\prime }}_l}{y_h-y_l}\right)\text{translate}\left(-x_l,-y_l\right)\\ =\left[\begin{array}{ccc}1& 0& {x^{\prime }}_l\\ 0& 1& {y^{\prime }}_l\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}\frac{{x^{\prime }}_h-{x^{\prime }}_l}{x_h-x_l}& 0& 0\\ 0& \frac{{y^{\prime }}_h-{y^{\prime }}_l}{y_h-y_l}& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{rrr}\hfill 1& \hfill 0& \hfill -x_l\\ \hfill 0& \hfill 1& \hfill -y_l\\ \hfill 0& \hfill 0& \hfill 1\end{array}\right]\\ =\left[\begin{array}{ccc}\frac{{x^{\prime }}_h-{x^{\prime }}_l}{x_h-x_l}& 0& \frac{{x^{\prime }}_l{x}_h-{x^{\prime }}_h{x}_l}{x_h-x_l}\\ 0& \frac{{y^{\prime }}_h-{y^{\prime }}_l}{y_h-y_l}& \frac{{y^{\prime }}_l{y}_h-{y^{\prime }}_h{y}_l}{y_h-y_l}\\ 0& 0& 1\end{array}\right].\end{array}\text{ (6.6)}$

It is perhaps not surprising to some readers that the resulting matrix has the form it does, but the constructive process with the three matrices leaves no doubt as to the correctness of the result.

An exactly analogous construction can be used to define a 3D windowing transformation, which maps the box [xl, xh] × [yl, yh] × [zl, zh] to the box $\left[{x^{\prime }}_l,{x^{\prime }}_h\right]\times \left[{y^{\prime }}_l,{y^{\prime }}_h\right]\times \left[{z^{\prime }}_l,{z^{\prime }}_h\right]$:

$\left[\begin{array}{cccc}\frac{{x^{\prime }}_h-{x^{\prime }}_l}{x_h-x_l}& 0& 0& \frac{{x^{\prime }}_l{x}_h-{x^{\prime }}_h{x}_l}{x_h-x_l}\\ 0& \frac{{y^{\prime }}_h-{y^{\prime }}_l}{y_h-y_l}& 0& \frac{{y^{\prime }}_l{y}_h-{y^{\prime }}_h{y}_l}{y_h-y_l}\\ 0& 0& \frac{{z^{\prime }}_h,{z^{\prime }}_l}{z_h-z_l}& \frac{{z^{\prime }}_l{z}_h-{z^{\prime }}_h{z}_l}{z_h-z_l}\\ 0& 0& 0& 1\end{array}\right].\text{ (6.7)}$

It is interesting to note that if we multiply an arbitrary matrix composed of scales, shears, and rotations with a simple translation (translation comes second), we get

$\left[\begin{array}{cccc}1& 0& 0& x_t\\ 0& 1& 0& y_t\\ 0& 0& 1& z_t\\ 0& 0& 0& 1\end{array}\right]\left[\begin{array}{cccc}{a}_{11}& a_{12}& a_{13}& 0\\ a_{21}& a_{22}& a_{23}& 0\\ a_{31}& a_{32}& a_{33}& 0\\ 0& 0& 0& 1\end{array}\right]=\left[\begin{array}{cccc}{a}_{11}& a_{12}& a_{13}& x_t\\ a_{21}& a_{22}& a_{23}& y_t\\ a_{31}& a_{32}& a_{33}& z_t\\ 0& 0& 0& 1\end{array}\right].$

Thus, we can look at any matrix and think of it as a scaling/rotation part and a translation part because the components are nicely separated from each other.

An important class of transforms are rigid-body transforms. These are composed only of translations and rotations, so they have no stretching or shrinking of the objects. Such transforms will have a pure rotation for the aij above.

6.4 Inverses of Transformation Matrices

While we can always invert a matrix algebraically, we can use geometry if we know what the transform does. For example, the inverse of scale(sx, sy, sz) is scale(1/sx, 1/sy, 1/sz). The inverse of a rotation is the same rotation with the opposite sign on the angle. The inverse of a translation is a translation in the opposite direction. If we have a series of matrices M = M1M2 ... Mn then $M^{-1}=M_n^{-1}\cdots M_2^{-1}{M}_1^{-1}.$

Also, certain types of transformation matrices are easy to invert. We’ve already mentioned scales, which are diagonal matrices; the second important example is rotations, which are orthogonal matrices. Recall (Section 5.2.4) that the inverse of an orthogonal matrix is its transpose. This makes it easy to invert rotations and rigid body transformations (see Exercise 6). Also, it’s useful to know that a matrix with [0 0 0 1] in the bottom row has an inverse that also has [0 0 0 1] in the bottom row (see Exercise 7).

Interestingly, we can use SVD to invert a matrix as well. Since we know that any matrix can be decomposed into a rotation times a scale times a rotation, inversion is straightforward. For example, in 3D we have

$M=R_{\text{1}}\text{scale}\left({\sigma }_{\text{1}},{\sigma }_2,{\sigma }_3\right)R_{\text{2}},$

and from the rules above it follows easily that

$M^{-1}=R_2^{\text{T}}\text{scale}\left(1/{\sigma }_{\text{1}},1/{\sigma }_2,1/{\sigma }_3\right)R_1^{\text{T}}.$

6.5 Coordinate Transformations

All of the previous discussion has been in terms of using transformation matrices to move points around. We can also think of them as simply changing the coordinate system in which the point is represented. For example, in Figure 6.19, we see two ways to visualize a movement. In different contexts, either interpretation may be more suitable.

For example, a driving game may have a model of a city and a model of a car. If the player is presented with a view out the windshield, objects inside the car are always drawn in the same place on the screen, while the streets and buildings appear to move backward as the player drives. On each frame, we apply a transformation to these objects that moves them farther back than on the previous frame. One way to think of this operation is simply that it moves the buildings backward; another way to think of it is that the buildings are staying put but the coordinate system in which we want to draw them—which is attached to the car—is moving. In the second interpretation, the transformation is changing the coordinates of the city geometry, expressing them as coordinates in the car’s coordinate system. Both ways will lead to exactly the same matrix that is applied to the geometry outside the car.

If the game also supports an overhead view to show where the car is in the city, the buildings and streets need to be drawn in fixed positions while the car needs to move from frame to frame. The same two interpretations apply: we can think of the changing transformation as moving the car from its canonical position to its current location in the world; or we can think of the transformation as simply changing the coordinates of the car’s geometry, which is originally expressed in terms of a coordinate system attached to the car, to express them instead in a coordinate system fixed relative to the city. The change-of-coordinates interpretation makes it clear that the matrices used in these two modes (city-to-car coordinate change vs. car-to-city coordinate change) are inverses of one another.

The idea of changing coordinate systems is much like the idea of type conversions in programming. Before we can add a floating-point number to an integer, we need to convert the integer to floating point or the floating-point number to an integer, depending on our needs, so that the types match. And before we can draw the city and the car together, we need to convert the city to car coordinates or the car to city coordinates, depending on our needs, so that the coordinates match.

When managing multiple coordinate systems, it’s easy to get confused and wind up with objects in the wrong coordinates, causing them to show up in unexpected places. But with systematic thinking about transformations between coordinate systems, you can reliably get the transformations right.

Geometrically, a coordinate system, or coordinate frame, consists of an origin and a basis—a set of three vectors. Orthonormal bases are so convenient that we’ll normally assume frames are orthonormal unless otherwise specified. In a frame with origin p and basis {u, v, w}, the coordinates (u, v, w) describe the point

$p+uu+vv+ww\text{.}$

When we store these vectors in the computer, they need to be represented in terms of some coordinate system. To get things started, we have to designate some canonical coordinate system, often called “global” or “world” coordinates, which is used to describe all other systems. In the city example, we might adopt the street grid and use the convention that the x-axis points along Main Street, the y-axis points up, and the z-axis points along Central Avenue. Then when we write the origin and basis of the car frame in terms of these coordinates it is clear what we mean.

In 2D our convention is is to use the point o for the origin, and x and y for the right-handed orthonormal basis vectors x and y (Figure 6.20).

Another coordinate system might have an origin e and right-handed orthonormal basis vectors u and v. Note that typically the canonical data o, x, and y are never stored explicitly. They are the frame-of-reference for all other coordinate systems. In that coordinate system, we often write down the location of p as an ordered pair, which is shorthand for a full vector expression:

$\mathbf{p}=\left(x_p,y_p\right)\equiv \mathbf{0}+x_p\mathbf{x}+y_p\mathbf{y}.$

For example, in Figure 6.20, (xp, yp) = (2.5, 0.9). Note that the pair (xp, yp) implicitly assumes the origin o. Similarly, we can express p in terms of another equation:

$p=\left(u_p,v_p\right)\equiv e+u_{p}u+v_{p}v.$

In Figure 6.20, this has (up, vp) = (0.5, −0.7). Again, the origin e is left as an implicit part of the coordinate system associated with u and v.

We can express this same relationship using matrix machinery, like this:

$\left[\begin{array}{c}{x}_p\\ y_p\\ 1\end{array}\right]=\left[\begin{array}{ccc}1& 0& x_e\\ 0& 1& y_e\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}{x}_u& x_v& 0\\ y_u& y_v& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{c}{u}_p\\ v_p\\ 1\end{array}\right]=\left[\begin{array}{ccc}{x}_u& x_v& x_e\\ y_u& y_v& y_e\\ 0& 0& 1\end{array}\right]\left[\begin{array}{c}{u}_p\\ v_p\\ 1\end{array}\right].$

Note that this assumes we have the point e and vectors u and v stored in canonical coordinates; the (x, y)-coordinate system is the first among equals. In terms of the basic types of transformations we’ve discussed in this chapter, this is a rotation (involving u and v) followed by a translation (involving e). Looking at the matrix for the rotation and translation together, you can see it’s very easy to write down: we just put u, v, and e into the columns of a matrix, with the usual [0 0 1] in the third row. To make this even clearer we can write the matrix like this:

$P_{xy}=\left[\begin{array}{lll}u\hfill & v\hfill & e\hfill \\ 0\hfill & 0\hfill & 1\hfill \end{array}\right]P_{uv}.$

We call this matrix the frame-to-canonical matrix for the (u, v) frame. It takes points expressed in the (u, v) frame and converts them to the same points expressed in the canonical frame.

To go in the other direction we have

$\left[\begin{array}{c}{u}_p\\ v_p\\ 1\end{array}\right]=\left[\begin{array}{ccc}{x}_u& y_u& 0\\ x_v& y_v& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& -x_e\\ 0& 1& -y_e\\ 0& 0& 1\end{array}\right]\left[\begin{array}{c}{x}_p\\ y_p\\ 1\end{array}\right].$

This is a translation followed by a rotation; they are the inverses of the rotation and translation we used to build the frame-to-canonical matrix, and when multiplied together they produce the inverse of the frame-to-canonical matrix, which is (not surprisingly) called the canonical-to-frame matrix:

$P_{uv}={\left[\begin{array}{lll}u\hfill & v\hfill & e\hfill \\ 0\hfill & 0\hfill & 1\hfill \end{array}\right]}^{-1}{P}_{xy}.$

The canonical-to-frame matrix takes points expressed in the canonical frame and converts them to the same points expressed in the (u, v) frame. We have written this matrix as the inverse of the frame-to-canonical matrix because it can’t immediately be written down using the canonical coordinates of e, u, and v. But remember that all coordinate systems are equivalent; it’s only our convention of storing vectors in terms of x- and y-coordinates that creates this seeming asymmetry. The canonical-to-frame matrix can be expressed simply in terms of the (u, v) coordinates of o, x, and y:

$P_{uv}=\left[\begin{array}{ccc}{x}_{uv}& y_{uv}& o_{uv}\\ 0& 0& 1\end{array}\right]p_{xy}.$

All these ideas work strictly analogously in 3D, where we have

$\begin{array}{cc}\hfill \left[\begin{array}{c}{x}_p\hfill \\ \hfill y_p\\ z_p\hfill \\ \hfill 1\end{array}\right]& =\left[\begin{array}{llll}1\hfill & 0\hfill & 0\hfill & x_e\hfill \\ 0\hfill & 1\hfill & 0\hfill & y_e\hfill \\ 0\hfill & 0\hfill & 1\hfill & z_e\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{llll}{x}_u\hfill & x_v\hfill & x_w\hfill & 0\hfill \\ y_u\hfill & y_v\hfill & y_w\hfill & 0\hfill \\ z_u\hfill & z_v\hfill & z_w\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill u_p\\ v_p\hfill \\ \hfill w_p\\ 1\hfill \end{array}\right]\hfill \\ \hfill P_{xyz}& =\left[\begin{array}{llll}u\hfill & v\hfill & w\hfill & e\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right]P_{uvw},\hfill \end{array}\text{ (6.8)}$

and

$\begin{array}{cc}\hfill \left[\begin{array}{c}{u}_p\hfill \\ \hfill v_p\\ w_p\hfill \\ \hfill 1\end{array}\right]& =\left[\begin{array}{llll}{x}_u\hfill & y_u\hfill & z_u\hfill & 0\hfill \\ x_v\hfill & y_v\hfill & z_v\hfill & 0\hfill \\ x_w\hfill & y_w\hfill & z_w\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{cccc}\hfill 1& 0\hfill & \hfill 0& -x_e\hfill \\ \hfill 0& 1\hfill & \hfill 0& -y_e\hfill \\ \hfill 0& 0\hfill & \hfill 1& -z_e\hfill \\ \hfill 0& 0\hfill & \hfill 0& 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_p\\ y_p\hfill \\ \hfill z_p\\ 1\hfill \end{array}\right]\hfill \\ \hfill P_{uvw}& ={\left[\begin{array}{llll}u\hfill & v\hfill & w\hfill & e\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right]}^{-1}{P}_{xyz}.\hfill \end{array}\text{ (6.9)}$

Frequently Asked Questions

• Can’t I just hardcode transforms rather than use the matrix formalisms?

  Yes, but in practice it is harder to derive, harder to debug, and not any more efficient. Also, all current graphics APIs use this matrix formalism so it must be understood even to use graphics libraries.

• The bottom row of the matrix is always (0,0,0,1). Do I have to store it?

  You do not have to store it unless you include perspective transforms (Chapter 7).

Notes

The derivation of the transformation properties of normals is based on Properties of Surface Normal Transformations (Turkowski, 1990). In many treatments through the mid-1990s, vectors were represented as row vectors and premultiplied, e.g., b = aM. In our notation this would be bT = aTMT. If you want to find a rotation matrix R that takes one vector a to a vector b of the same length: b = Ra you could use two rotations constructed from orthonormal bases. Amore efficient method is given in Efficiently Building a Matrix to Rotate One Vector to Another (Akenine-Möller, Haines, & Hoffman, 2008).

Exercises

1. Write down the 4 × 4 3D matrix to move by (xm, ym, zm).
2. Write down the 4 × 4 3D matrix to rotate by an angle θ about the y-axis.
3. Write down the 4 × 4 3D matrix to scale an object by 50% in all directions.
4. Write the 2D rotation matrix that rotates by 90 degrees clockwise.
5. Write the matrix from Exercise 4 as a product of three shear matrices.

6. Find the inverse of the rigid body transformation:

   $\left[\begin{array}{cc}R& t\\ 000& 1\end{array}\right]$

   where R is a 3 × 3 rotation matrix and t is a 3-vector.

7. Show that the inverse of the matrix for an affine transformation (one that has all zeros in the bottom row except for a one in the lower right entry) also has the same form.

8. Describe in words what this 2D transform matrix does:

   $\left[\begin{array}{ccc}0& -1& 1\\ 1& 0& 1\\ 0& 0& 1\end{array}\right].$

9. Write down the 3 × 3 matrix that rotates a 2D point by angle θ about a point p = (xp, yp).
10. Write down the 4 × 4 rotation matrix that takes the orthonormal 3D vectors u = (xu, yu, zu), v = (xv, yv, zv), and w = (xw, yw, zw), to orthonormal 3D vectors a = (xa, ya, za), b = (xb, yb, zb), and c = (xc, yc, zc), So Mu = a, Mv = b, and Mw = c.
11. What is the inverse matrix for the answer to the previous problem?