Composition, coordinates and inversion: the linear algebra of graphics

A bug report says a marker sits in the wrong place. The fault is rarely in the multiplication. This unit argues that a wrong composition order and a coordinate mismatch, not an arithmetic slip, are the failures worth modelling, and that the algebra is a vocabulary for them. A transformation maps one coordinate system into another, so a pipeline goes wrong in two ways: its transforms were composed in the wrong order, or a point was read in a frame other than the one the mapping expects. An arithmetic slip shows as wrong pixels everywhere; a coordinate mismatch shows only where two frames meet, and a singular map shows only once something has been lost.

Three ideas carry it: composition is multiplication and multiplication is ordered, translation needs an extra coordinate, and an inverse exists exactly when the determinant is not zero. Unit 9 asks how far a measurement on a handful of participants can carry a claim.

A transform acts on coordinates, not on a screen

Sutherland (1964) built Sketchpad so that a person and a computer could converse through line drawings rather than typed statements, built from constraints and reusable components; direct graphical manipulation, he argued, removes a translation step that had limited what could be communicated.

The platform definition is narrower than the slogan. The CSS Transforms specification defines a transformation matrix as the mathematical mapping from one coordinate system into another, computed from the transform and transform-origin properties (W3C, 2019). Hughes and colleagues (2013) develop the same account from points and vectors through transformations, viewing and projection, treating a transformation as a matrix acting on homogeneous coordinates. A transform is a change of frame, so a question about where a point lands is a question about which frame it is expressed in.

Composition is multiplication, and multiplication is ordered

A design that applies two transforms applies their product, and the product depends on the order. The specification states that the final transformation value is obtained by converting each function in the transform list to its matrix and then multiplying the matrices (W3C, 2019), and Vince (2012) derives the same composition for games and animation. Akenine-Moller, Haines and Hoffman (2018) give the pipeline account, in which transforms are composed and applied to geometry at frame rate.

A constructed case makes the difference plain. The point (10, 0) under rotate-then-translate reaches (5, 10), and under translate-then-rotate reaches (0, 15). A composition is one matrix, not a list of effects applied to a screen.

Translation needs a carry coordinate

Translation is the awkward case. Scaling and rotation fix the origin, so each can be written as a matrix acting on a point; translation cannot, because it is affine rather than linear and no matrix acting by multiplication moves the origin. The remedy is a carry coordinate. The specification records that a two-dimensional transform may be held as a 3 by 2 matrix, or as a 4 by 4 matrix whose unused entries are fixed at zero and one (W3C, 2019). Vince (2012) and Hughes and colleagues (2013) develop translation, rotation and scale inside that homogeneous representation, so translation composes like everything else.

A concrete matrix shows the carry coordinate working. Scale the point (2, 3) by two and translate the result by (10, 0), and it reaches (14, 6). In homogeneous coordinates that is a single 3 by 3 matrix whose last row is 0, 0, 1, with the scale on the diagonal and the translation in the third column, so one multiplication performs both steps; without the extra coordinate the operation would be a matrix product followed by an addition.

An inverse exists exactly when the determinant is not zero

An inverse undoes a transform exactly when it loses no information, and the test is the determinant. A rotation has determinant one and is invertible, while a map that flattens one axis onto another has determinant zero, so no inverse exists and the flattened direction is lost (Vince, 2012; Hughes and colleagues, 2013). Selection runs the pipeline backwards. To test whether a tap on a rotated marker hit it, the interface takes the inverse of the object's transform, maps the tapped point into the object's own coordinates and tests there (Hughes and colleagues, 2013). A hit test written in screen coordinates fails for a rotated or scaled object.

This is computed rather than stored because of cost. Klosowski and colleagues (1998) develop bounding-volume hierarchies of discrete orientation polytopes for collision detection among many moving objects. They were motivated by applications such as haptic force feedback that call for over a thousand collision queries per second, and determine contacts at real-time rates.

The representation decides which failures are possible

Every matrix above is one choice among representations of the same rotation, and the choice decides which failures are possible. Shoemake (1985) argued that rotations are best described by quaternions, giving a spherical spline curve for interpolating arbitrary rotations and reporting motion free of the artefacts of earlier methods. Hanson (2006) develops quaternions geometrically and presents the standard argument that they avoid the gimbal lock of Euler angles. Grassia (1998) supplies a third option, a parameterisation by the exponential map that also avoids gimbal lock while using only three numbers. The trade-off is between redundancy and singularity (Vince, 2012).

Zhou and colleagues (2019) close the escape route: they define continuity for a representation and show that for three-dimensional rotations every representation in real Euclidean space of four or fewer dimensions is discontinuous. Quaternions and Euler angles are discontinuous too, and continuous representations exist only in five and six dimensions. The theorem is about continuity rather than gimbal lock, and it explains why those seams recur. Ghiassi and Kecskemethy (2024) survey the methods for mapping three-dimensional rotations to planar rotations, documenting that the choice of representation decides which rotations are awkward.

Gimbal lock is the concrete failure the choice buys and sells. Describe a camera by three Euler angles, called pitch, yaw and roll, and aim it straight up: pitch reaches ninety degrees, the pitch and yaw axes line up, and from that orientation a change in yaw and a change in roll produce the same motion, so one degree of freedom has gone. A quaternion or an exponential-map parameterisation spends a fourth or a third number to avoid that coincidence. That is the trade the unit describes: the singularity is not removed, it is moved to a seam. The seam is also where the algebra meets a user's tolerance. An interpolation that swings through ninety degrees is a visible jump, and for a user with a vestibular disorder the motion is itself the harm, which is why a platform's reduced-motion setting shortens exactly these interpolations. A hit test carries the same tolerance, since aim is a distribution rather than a point.

Huynh (2009) compares ways of measuring the distance between two three-dimensional rotations and shows that the choice of metric changes what counts as a small error.

Contested question: what correct algebra does not buy

Bowman, McMahan and Ragan (2012) press the widest case against the unit's thesis. They treat interaction fidelity as a continuum rather than a virtue in itself, and report that raising it is not sufficient: high-fidelity interaction performed well for difficult tasks, but a moderately natural technique was unfamiliar and did worse than a traditional low-fidelity one, so fidelity must be justified by context. Argelaguet and Andujar (2013) survey the techniques used to select objects in virtual environments. They report that no single technique is best, and that performance depends on the task and the environment, so the mathematics supplies the ray but not the disambiguation. Correct algebra is necessary and, these sources show, nowhere near sufficient. The strength of that evidence runs two ways: Bowman's case rests on studies reported in a magazine article, and Argelaguet and Andujar's is a survey, both comparative rather than a controlled test of the mathematics itself.

The representation debate is the second disagreement. One position keeps matrices as the universal form: composition is multiplication and the specification defines transforms as matrices, so staying in that form avoids converting between representations at each step (W3C, 2019; Akenine-Moller and colleagues, 2018). A second prefers quaternions or the exponential map for rotation, because they use fewer numbers and interpolate without gimbal lock (Shoemake, 1985; Hanson, 2006; Grassia, 1998). A third, from Zhou and colleagues (2019), changes the terms of the debate: since no representation in three or four numbers is continuous, the question becomes whether the task can tolerate a discontinuity or must pay the redundancy of five or six dimensions to avoid one.

What would settle it is a task-specific test. The decisive study would take one interpolation or inverse-kinematics task, encode it in each candidate representation, and measure two things on the same trials: the maximum angular error at the sample points, and the rate of artefacts that follow from crossing the representation's seam. A representation that wins on error but shows a visible artefact at the seam would confirm the trade-off; one that wins on both would refute the claim that no choice is free. Meanwhile, choose the representation the task can tolerate. Pay the redundancy where interpolation must be continuous, keep matrices where transforms compose in one pipeline, and test the choice against the task's own error measure.

Where the argument is heading

The direction of travel in the mathematics is towards representations that trade redundancy for continuity. Zhou and colleagues (2019) construct continuous representations of three-dimensional rotations in five and six dimensions, reporting that these outperform the discontinuous forms in an autoencoder, a rotation estimator for point clouds and an inverse-kinematics solver, while Ghiassi and Kecskemethy (2024) document that the mapping of a three-dimensional rotation to smaller parameterisations remains active in robotics and animation.

The sources this unit rests on

• W3C (2019). CSS Transforms Module Level 1. W3C Candidate Recommendation, 14 February 2019. https://www.w3.org/TR/css-transforms-1/ Defines a transformation matrix as the mathematical mapping from one coordinate system into another, records that a two-dimensional transform is a 3 by 2 or 4 by 4 matrix, and states that a transform list is composed by multiplying the matrices.
• Sutherland, I. E. (1964). Sketchpad, a man-machine graphical communication system. SIMULATION, 2(5), R-3-R-20. doi:10.1177/003754976400200514 Let a person and a computer converse through line drawings rather than typed statements, and supported drawings built from constraints and reusable components. It argues that direct graphical manipulation removes a translation step.
• Shoemake, K. (1985). Animating rotation with quaternion curves. Proceedings of the 12th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH). doi:10.1145/325334.325242 Argues that rotations are best described using quaternions and gives a spherical spline curve for interpolating arbitrary rotations, the representation the unit contrasts with matrices.
• Hughes, J. F., van Dam, A., McGuire, M., Sklar, D. F., Foley, J. D., Feiner, S. K. and Akeley, K. (2013). Computer Graphics: Principles and Practice. Addison-Wesley, 3rd edition. https://www.pearson.com/en-us/subject-catalog/p/computer-graphics-principles-and-practice/P200000003505 Develops two- and three-dimensional graphics from points and vectors through transformations, viewing and projection, treating a transformation as a matrix acting on homogeneous coordinates. It supplies the coordinate-system account and the reason hit testing runs in object coordinates.
• Akenine-Moller, T., Haines, E. and Hoffman, N. (2018). Real-Time Rendering. CRC Press, 4th edition. doi:10.1201/9781315365459 Covers the real-time rendering pipeline, transforms and their composition, and the steps from geometry through rasterisation. It is the engineering account of the pipeline the unit's matrices act inside.
• Hanson, A. J. (2006). Visualizing Quaternions. Morgan Kaufmann. https://shop.elsevier.com/books/visualizing-quaternions/hanson/978-0-12-088400-1 Develops quaternions geometrically as an extension of complex numbers to three dimensions, covering rotation, interpolation and the avoidance of gimbal lock.
• Klosowski, J. T., Held, M., Mitchell, J. S. B., Sowizral, H. and Zikan, K. (1998). Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Transactions on Visualization and Computer Graphics, 4(1), 21-36. doi:10.1109/2945.675649 Develops bounding-volume hierarchies of discrete orientation polytopes for collision detection among many moving objects, motivated by haptic force feedback requiring over a thousand collision queries per second, and shows the linear algebra behind a query cost proportional to the number of objects.
• Vince, J. (2012). Matrix Transforms for Computer Games and Animation. Springer-Verlag. doi:10.1007/978-1-4471-4321-5 Sets out the matrix algebra for translation, rotation and scaling, including homogeneous coordinates, the composition of transforms and quaternions. It is the compact reference for the arithmetic the unit asks a student to do by hand.
• Bowman, D. A., McMahan, R. P. and Ragan, E. D. (2012). Questioning naturalism in 3D user interfaces. Communications of the ACM, 55(9), 78-88. doi:10.1145/2330667.2330687 Treats interaction fidelity as a continuum and reports that raising it is not sufficient: high fidelity helped difficult tasks, but a moderately natural technique was unfamiliar and did worse than a traditional low-fidelity one.
• Argelaguet, F. and Andujar, C. (2013). A survey of 3D object selection techniques for virtual environments. Computers and Graphics, 37(3), 121-136. doi:10.1016/j.cag.2012.12.003 Organises the techniques used to select objects in virtual environments and compares how they disambiguate a selection and provide feedback, reporting that no single technique is best and that performance depends on the task and the environment.
• Huynh, D. Q. (2009). Metrics for 3D rotations: comparison and analysis. Journal of Mathematical Imaging and Vision, 35(2), 155-164. doi:10.1007/s10851-009-0161-2 Compares ways of measuring the distance between two three-dimensional rotations and analyses each metric and its computational cost. It shows the choice of metric changes what counts as a small rotation error.
• Grassia, F. S. (1998). Practical parameterization of rotations using the exponential map. Journal of Graphics Tools, 3(3), 29-48. doi:10.1080/10867651.1998.10487493 Presents a parameterisation of rotations by the exponential map that avoids the gimbal lock of Euler angles while using only three numbers, with the derivatives interpolation and optimisation need.
• Zhou, Y., Barnes, C., Lu, J., Yang, J. and Li, H. (2019). On the continuity of rotation representations in neural networks. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). doi:10.1109/CVPR.2019.00589 Defines continuity for a representation and shows that for three-dimensional rotations every representation in real Euclidean space of four or fewer dimensions is discontinuous, before constructing continuous representations in five and six dimensions.
• Ghiassi, M. and Kecskemethy, A. (2024). A review of methods for mapping 3D rotations to one-dimensional planar rotations. Robotica, 42(12), 3994-4018. doi:10.1017/S0263574724001498 Surveys methods for representing three-dimensional rotations by one-dimensional planar rotations and compares them on continuity, singularity and computational behaviour. It documents that the choice of representation determines which rotations are awkward and which are cheap.