Composition Order in Graphics Pipelines

Why Order Matters in a Graphics Pipeline

A graphics pipeline often applies several operations to the same point: first one transformation, then another, and perhaps a third. Matrices let us replace that sequence with a single matrix, but the order of multiplication can be easy to misread. With column vectors, the matrix for the operation performed last appears on the left of the product. Reversing the factors can describe a different sequence and send a point somewhere else.

We work in \(\mathbb{R}^2\), using column vectors for points. In homogeneous coordinates, the point \((x,y)\) is represented by the column \(\begin{bmatrix}x\\y\\1\end{bmatrix}\). A two-dimensional affine transformation consists of a linear part, represented by a \(2\times2\) matrix \(\mathbf{A}\), and a translation vector \(\mathbf{b}\in\mathbb{R}^2\). Its homogeneous matrix is a \(3\times3\) matrix of the form below.

Multiplying this matrix by a homogeneous point gives \(\begin{bmatrix}\mathbf{A}\mathbf{x}+\mathbf{b}\\1\end{bmatrix}\), where \(\mathbf{x}=\begin{bmatrix}x\\y\end{bmatrix}\). Thus, the top-left block acts linearly on the point, while the last column adds the translation. The bottom row preserves the final coordinate \(1\).

Deriving the Composition Rule

Suppose the first operation has matrix \(\mathbf{H}_1\), and the second has matrix \(\mathbf{H}_2\). Applying the first operation to a point \(\mathbf{p}\) gives \(\mathbf{H}_1\mathbf{p}\). Applying the second to that result gives \(\mathbf{H}_2(\mathbf{H}_1\mathbf{p})\), which is \((\mathbf{H}_2\mathbf{H}_1)\mathbf{p}\). The order follows from the action: the matrix nearest the point acts first.

Proof. Write the product in \(2\times2\) block form. Block multiplication gives

The product has the required form, with linear part \(\mathbf{A}_2\mathbf{A}_1\) and translation part \(\mathbf{A}_2\mathbf{b}_1+\mathbf{b}_2\). For any point \(\mathbf{x}\in\mathbb{R}^2\), applying the two affine maps in sequence gives \(\mathbf{A}_2(\mathbf{A}_1\mathbf{x}+\mathbf{b}_1)+\mathbf{b}_2 =(\mathbf{A}_2\mathbf{A}_1)\mathbf{x}+\mathbf{A}_2\mathbf{b}_1+\mathbf{b}_2\). That is exactly the action of the product matrix, so it represents the stated sequence. \(\square\)

This rule is about the order of actions, not a special feature of graphics. It follows from matrix-vector multiplication. A useful way to read any product is from right to left: in \(\mathbf{H}_3\mathbf{H}_2\mathbf{H}_1\mathbf{p}\), \(\mathbf{H}_1\) acts on \(\mathbf{p}\) first, followed by \(\mathbf{H}_2\), then \(\mathbf{H}_3\).

A Translation Followed by a Linear Transformation

When Reversing the Order Does Not Matter

Some transformations do commute: performing them in either order gives the same result. For example, two translations add their displacement vectors. Addition of vectors in \(\mathbb{R}^2\) is commutative, so the order of two translations does not affect the final point. This special case should not be mistaken for a general rule about transformation matrices.

Combining Three Stages

A pipeline with more than two stages follows the same right-to-left reading rule. The products may be grouped in different ways when computing them, but the order of the factors must be preserved. The associativity of matrix multiplication justifies grouping a sequence of products without changing the result.

Proof. Let \(\mathbf{A}\) be \(m\times n\), \(\mathbf{B}\) be \(n\times r\), and \(\mathbf{C}\) be \(r\times s\). For any row \(i\) and column \(j\), the \((i,j)\) entry of \((\mathbf{A}\mathbf{B})\mathbf{C}\) is \(\sum_{k=1}^{r}\left(\sum_{\ell=1}^{n}a_{i\ell}b_{\ell k}\right)c_{kj} =\sum_{k=1}^{r}\sum_{\ell=1}^{n}a_{i\ell}b_{\ell k}c_{kj}\). The \((i,j)\) entry of \(\mathbf{A}(\mathbf{B}\mathbf{C})\) is \(\sum_{\ell=1}^{n}a_{i\ell}\left(\sum_{k=1}^{r}b_{\ell k}c_{kj}\right) =\sum_{\ell=1}^{n}\sum_{k=1}^{r}a_{i\ell}b_{\ell k}c_{kj}\). Both are the same finite sum, with its terms grouped in a different way. Thus the entries agree for every \(i,j\), so the matrices are equal. \(\square\)

Common Mistake: Writing the Factors in Action Order

A frequent error is to write the matrices from left to right in the order the operations are performed. In the first worked example, translating and then applying \(\mathbf{L}\) does not give \(\mathbf{T}\mathbf{L}\). That product applies \(\mathbf{L}\) first, because its rightmost factor acts first. The wrong calculation is not merely a different way to group the same operations: it changes the sequence.

To correct the error, state the sequence in words, attach each operation to its matrix, and then place the first operation closest to the point column. For “first \(\mathbf{T}\), then \(\mathbf{L}\),” write \(\mathbf{L}\mathbf{T}\mathbf{p}\). Check the order by applying the matrices one at a time to a simple point. If the combined product gives a different point from the sequential calculation, either the product order or the arithmetic must be corrected.

In general, matrix products need not commute: \(\mathbf{A}\mathbf{B}\) may differ from \(\mathbf{B}\mathbf{A}\). The translation example showed a special pair that commutes, while the translation and linear map in the first example did not. Therefore, do not infer from one pipeline that reversing all operations is safe. Preserve the stated sequence, and use the product order dictated by column-vector multiplication.