2D Transforms 101

A practitioner's introduction to transformations

Sundaram Ramaswamy / @legends2k

Read me first! Press ? for presentation controls.
Best viewed in Firefox, Chrome or Opera.

Overview

  • Definitions of transformation (noun)
    • the act of changing in form or shape or appearance
    • (logic) a set of algebraic formulas used to express the relations between elements, sets, etc., that form parts of a given system
    • (mathematics) a function that changes the position or direction of the axes of a coordinate system
  • Different, seemingly confusing, definitions alluding to a simple idea: conversion
  • Conversion of a value $P$ to $P'$ within a system
  • Conversion of a value $P_a$ in one system to $P_b$ in another system
  • Conversion of a system into another
  • Intuition favoured over rigour

Motivation

A basic concept in linear algebra underpinning many domains

  • Graphics
    • Rendering
    • Animation
    • Image Processing
    • Motion capture
    • UI Design
  • Computer Vision
  • Robotics
  • Parallel Computing
  • Concepts explained are dimension-independant; they work just as well in 3D as they do in 2D

Conventions Used

  • Canvas / Paper
  • RenderTarget, DeviceContext, GraphicsContext, Drawable, Frame buffer, Bitmap, Window, Form, Texture — domain-specific, confusing terms are unneeded
  • Math-textbook coordinate system used as default Origin sits at the left-bottom corner, X goes → and Y goes ↑
  • Default rotation is counter-clockwise
    • Rotates a point ↶ (counter-clockwise) when θ > 0, ↷ (clockwise) when θ < 0
    • Degrees despite most library functions expecting radians: π rad = 180°
  • Two ways to denote a 2D point $(x, y)$ as a matrix
    1. Row matrix $\begin{pmatrix} x & y \end{pmatrix}$ ← we use this
    2. Column matrix $\begin{pmatrix} x \\ y \end{pmatrix}$
  • Using column-vector convention? Transpose all equations shown
    Flip matrices and reverse multiplication order as $(AB)^{T} = B^T A^T$   e.g.
    $\begin{pmatrix}x & y\end{pmatrix}\begin{pmatrix}a & b \\c & d\end{pmatrix} = \begin{pmatrix}a & c \\b & d\end{pmatrix} \begin{pmatrix}x \\ y\end{pmatrix}$

Clarifications

  • Transformations act on points already existing Creation of shapes (and plotting of points) is beyond purview
  • Transforming a shape really means transforming its points individually Though transformation types (scale, rotate, shear, …) imply operation on a shape, a transform can only operate on a single point
  • A system/space within which values (points) lives has
    • to be relative; no such thing as “absolute system”
    • an agreed-upon origin w.r.t another system
    • $n$ lengths agreed-upon as 1 unit in every direction (axes) considered w.r.t another system

Part I

Transforming Points

Changes made to a value within a system

$X: P \rightarrow P'$

Scale

  • 1D scaling is so ingrained we do it without forethought
  • 1 ticket = ₹50 ⇒ 3 tickets = 3 × 50 = ₹150 — here $x = 50, s = 3$
  • Multiplying the value $x$, with the scaling factor $s$ (scalar), does the conversion $\boxed{x' = s x}$.
  • Enlarges if $s > 1$; shrinks if $0 < s < 1$; does no conversion when $s = 1$ (identity)
  • Same formula works in 2D; use another scalar to tackle the extra dimension: $S_{x, y} = (s_{x}, s_{y})$
  • For some $P(x, y)$ and $S_{x, y}$, the scaled, or more generally transformed, point $\boxed{P'(x', y') = PS_{x, y} = (s_{x}x, s_{y}y)}$
  • Scaling is uniform when $s_{x} = s_{y}$

Example 1: Uniform Scale

$Square = \{ P_{1}, P_{2}, P_{3}, P_{4} \} \\ Scale = (2, 2)\\ \begin{array}{l|l} P & P' = PS_{2, 2}\\ \hline (2, 2) & (4, 4)\\ (-2, 2) & (-4, 4)\\ (-2, -2) & (-4, -4)\\ (2, -2) & (4, -4) \end{array}$


Square' $\{ P'_{1}, P'_{2}, P'_{3}, P'_{4} \}$ is a larger square.
$S_{2, 2}$ increases size while preserving shape — enlargement.

Example 2: Non-uniform Scale

$Square = \{ P_{1}, P_{2}, P_{3}, P_{4} \} \\ Scale = (2, \frac{1}{2})\\ \begin{array}{l|l} P & P' = PS_{2, \frac{1}{2}}\\ \hline (2, 2) & (4, 1)\\ (-2, 2) & (-4, 1)\\ (-2, -2) & (-4, -1)\\ (2, -2) & (4, -1) \end{array}$

Square' $\{ P'_{1}, P'_{2}, P'_{3}, P'_{4} \}$ is a rectangle.
$S_{2, \frac{1}{2}}$ is a shape-changing transformation — deformation.

Example 3: Reflection across X-axis

$Triangle = \{ P_{1}, P_{2}, P_{3} \} \\ Scale = (1, -1)\\ \begin{array}{l|l} P & P' = PS_{1, -1}\\ \hline (0, 2) & (0, -2)\\ (-2, -2) & (-2, 2)\\ (2, -2) & (2, 2) \end{array}$

Triangle' $\{ P'_{1}, P'_{2}, P'_{3} \}$ is triangle's reflection.
$S_{1, -1}$ mirrors an object while preserving shape and size.

Rotation

  • Doesn't make much sense in 1D, but well defined in 2D
  • Trigonometry says if some point $P(x, y)$ is rotated through an angle $θ$, the rotated point $\boxed{P'(x', y') = PR_{θ} = (x \cos θ - y \sin θ, x \sin θ + y \cos θ)}$
  • No conversion (identity) when $θ = 0$ ∵ cos 0 = 1, sin 0 = 0 → $PR_{0} = (1x - 0y, 0x + 1y) = (x, y) = P' = P$
  • These functions are periodic ⇒ $θ = θ \bmod 360$ (angle wraps around)
  • Negative angles can be made positive by adding 360 θ = −90, θ = 360 − 90 = 270 — works since the resulting orientation is the same; doesn't work when animating as the direction of rotation will differ

Example 4: Rotation

$Square = \{ P_{1}, P_{2}, P_{3}, P_{4} \} \\ Rotate = 45°\\ \begin{array}{l|l} P & P' = PR_{45}\\ \hline (2, 2) & (0, 2.828)\\ (-2, 2) & (-2.828, 0)\\ (-2, -2) & (0, -2.828)\\ (2, -2) & (2.828, 0) \end{array}$
Square' $\{ P'_{1}, P'_{2}, P'_{3}, P'_{4} \}$ is an oriented square.
$R_{45}$ is a rigid-body transform preserving both shape & size.

Example 5: X-Shear

$Square = \{ P_{1}, P_{2}, P_{3}, P_{4} \} \\ Shear = (1, 0)\\ \begin{array}{l|l} P & P' = PK_{1, 0}\\ \hline (2, 2) & (4, 2)\\ (-2, 2) & (0, 2)\\ (-2, -2) & (-4, -2)\\ (2, -2) & (0, -2) \end{array}$

Square' $\{ P'_{1}, P'_{2}, P'_{3}, P'_{4} \}$ is a parallelogram.

$K_{1, 0}$ is a shape-changing deformation.

Shear/Skew

  • Shift in one direction proportional to the value in the other
  • $\boxed{ P'(x', y') = PK_{a, b} = (x + ay, bx + y) }$
  • X-shear or skew-X when a ≠ 0, b = 0
  • Y-shear or skew-Y when a = 0, b ≠ 0
  • Shear in both directions simultaneously is possible too
  • Identity when a = b = 0

Linear Transformations

  • For some P(x, y), the transformation
    1. Scale $P' = (s_{x}x, s_{y}y)$
    2. Rotation $P' = (x \cos θ - y \sin θ, x \sin θ + y \cos θ)$
    3. Shear $P' = (x + ay, bx + y)$
  • Generalised equation $\boxed{ P'(x', y') = PX = (ax + by, cx + dy) }$
  • The resulting value is some scaled combination of x & y
  • Linear since equation deals only with first powers of x & y
  • Linear transforms preserve collinearity Points on a line before the transform continue to be so after it too — straight lines will remain straight
  • What about changes to P with no relation to x or y?

Translation

  • Translation in 1D is nothing but addition
  • 1 ticket = ₹50 ⇒ 3 tickets = 3 × 50 = ₹150 , but what about the flowers you got for your sweetheart on the way? ₹150 + ₹50 = ₹200. This has no correlation to the 3 friends going to the theatre.
  • Adding an offset $t$, to the value $x$, does the conversion $\boxed{ x' = x + t }$
  • Same works in 2D; use another constant to tackle the extra dimension: $T_{x, y} = (t_{x}, t_{y})$
  • For some $P(x, y)$ and $T_{x, y}$, the translated point $\boxed{P'(x', y') = PT_{x, y} = (x + t_{x}, y + t_{y})}$
  • The added constant lacks any correlation to $x$ or $y$, unlike linear transforms

Example 6: Translate

$Square = \{ P_{1}, P_{2}, P_{3}, P_{4} \} \\ Translate = (3, 4)\\ \begin{array}{l|l} P & P' = PT_{3, 4}\\ \hline (2, 2) & (5, 6)\\ (-2, 2) & (1, 6)\\ (-2, -2) & (1, 2)\\ (2, -2) & (5, 2) \end{array}$

Square' $\{ P'_{1}, P'_{2}, P'_{3}, P'_{4} \}$ is $P$ relocated.

$T_{3, 4}$ is a rigid-body transform that repositions an object.

Affine Transformations

  • For some P(x, y), the transformation
    1. Linear $P' = (ax + by, cx + dy)$
    2. Translation $P' = (x + t_{x}, x + t_{y})$
  • Generalised equation $\boxed{ P'(x', y') = PX = (ax + by + e, cx + dy + f) }$
  • A linear transformation followed by a translation
  • Properties
    • Preserves collinearity
    • Preserves parallelism of lines
    • Preserves relative distance between points on a straight line
    • Doesn't preserve angles between lines or distances between points

Affine Transforms


Image generously shared under Creative Commons 3.0
Credit: Ldo

Concatenating Point Transforms

  • Multiple transforms may be concatenated
  • Consider X₁, X₂, X₃ concatenated in that order: $P'(x', y') = PX_1X_2X_3$
  • Result of $PX_1 = P'_1$ is fed to X₂: $P'_1X_2 = P'_2$ is fed to $P'_2X_3 = P'$ — just function composition: $g(f(x))$
  • $P'_1 = (a_1x + b_1y + e_1, c_1x + d_1y + f_1)$ $P'_2 = (a_2(a_1x + b_1y + e_1) + b_2(c_1x + d_1y + f_1) + e_2,\\c_2(a_1x + b_1y + e_1) + d_2(c_1x + d_1y + f_1) + f_2)$
  • $P'_3$ = … seriously, should we be doing this? Isn't there a better way!
  • Yes, there is. Matrix to the rescue.

Transformation Matrices

  • Arthur Cayley demonstrated that matrices succinctly represent the algebraic form of transforms
  • $\begin{pmatrix}x' & y'\end{pmatrix} = \begin{pmatrix}x & y\end{pmatrix} \begin{pmatrix}a & c\\b & d\end{pmatrix}$ This only covers linear transforms. What about translation?
  • $\begin{pmatrix}x' & y' & 1\end{pmatrix} = \begin{pmatrix}x & y & 1\end{pmatrix} \begin{pmatrix}a & c & 0\\b & d & 0\\e & f & 1\end{pmatrix}$
  • Keep multiplying matrices while maintaining a concise form for any complex transform "One matrix to transform 'em all!"
  • 2D transforms need 3D matrices?! But why?
  • 2D has 3 DoF: X & Y axes (linear) and origin (translation)
  • Literature calls this homogeneous coordinates

Scale Matrix

$P'(x', y') = PS_{x, y} = (s_{x}x, s_{y}y)\\ \begin{pmatrix} x' & y' & 1 \end{pmatrix} = \begin{pmatrix}x & y & 1\end{pmatrix}\begin{pmatrix}s_x & 0 & 0\\0 & s_y & 0\\0 & 0 & 1\end{pmatrix} $

Rotation Matrix

$P'(x', y') = PR_{θ} = (x \cos θ − y \sin θ, x \sin θ + y \cos θ)\\ \begin{pmatrix} x' & y' & 1 \end{pmatrix} = \begin{pmatrix}x & y & 1\end{pmatrix}\begin{pmatrix}\cos θ & \sin θ & 0\\−\sin θ & \cos θ & 0\\0 & 0 & 1\end{pmatrix} $

Shear Matrix

$P'(x', y') = PK_{x, y} = (x + ay, bx + y)\\ \begin{pmatrix} x' & y' & 1 \end{pmatrix} = \begin{pmatrix}x & y & 1\end{pmatrix}\begin{pmatrix}1 & b & 0\\a & 1 & 0\\0 & 0 & 1\end{pmatrix} $

Translation Matrix

$P'(x', y') = PT_{x, y} = (x + t_{x}, y + t_{y})\\ \begin{pmatrix} x' & y' & 1 \end{pmatrix} = \begin{pmatrix}x & y & 1\end{pmatrix}\begin{pmatrix}1 & 0 & 0\\0 & 1 & 0\\t_{x} & t_{y} & 1\end{pmatrix} $

Matrices Don't Commute

  • You mean, they don't go to office!?
  • No, silly! The order of matrix multiplication matters
  • AB ≠ BA
  • This is unlike scalar multiplication …
    3 * 4 = 4 * 3
  • … but similar to scalar subtraction
    3 − 4 ≠ 4 − 3
  • Being mindful of anti-commutativity is important
  • Successive point transforms are concatenated to the right i.e. they are post-multiplied e.g. $X_1 X_2 … X_n$
  • Post multiplication is sometimes called right multiplication

Order Does Matter

Example 7: Scale not so centre

$Square = \{ P_{1}, P_{2}, P_{3}, P_{4} \} \\ Scale = (2, 2)\\ \begin{array}{l|l} P & P' = PS_{2, 2}\\ \hline (1, 1) & (2, 2)\\ (5, 1) & (10, 2)\\ (5, 5) & (10, 10)\\ (1, 5) & (2, 10) \end{array}$

Centre of square' is no longer the same.

Transforms, on objects not at origin, additionally translates.

Transform about arbitrary point

  • Transforms thus far operated only w.r.t. the system's origin
  • What if we need to transform w.r.t some arbitrary point?
  • Use cases of such scenarios are plenty
    • Scaling an object maintaining its centre
    • Zooming at a particular point
    • Rotating an object around its own axis
    • Not all objects are at the origin
  • Simple solution
    • Translate anchor to origin
    • Perform the transform
    • Translate anchor back to original spot


    $P' = P$ $T_{-c_{x}, -c_{y}}$ $X$ $T_{c_{x}, c_{y}}$

Example 8: Scale about centre

$Square = \{ P_{1}, P_{2}, P_{3}, P_{4} \} \\ Scale = (2, 2)\\ \begin{array}{l|l} P & PT_{-3, -3}S_{2, 2}T_{3, 3}\\ \hline (2, 2) & (1, 1)\\ (4, 2) & (5, 1)\\ (4, 4) & (5, 5)\\ (2, 4) & (1, 5) \end{array}$
Object scaled with respect to its centre.

Part II

Transforming Systems

Converting a system into another

$L_{a \rightarrow b}: A \rightarrow B$

Multiple Systems

  • What's the need for multiple coordinate systems?
  • Many times working in a single, global coordinate system doesn't work
  • You: Cute girl, 3'o clock — Friend: ☺ Nice!
    You: Cute girl, 17.37°N 78.48°E — Friend:(what did this dude have for lunch!?!)
  • We all work in our own local coordinate system
  • Gives enough abstraction to not worry about systems above or below us

Transforming A System

  • A system is defined by its origin and axes (unit distances) in all considered directions w.r.t another system
  • Transforming a system is just converting its frame (origin and axes) to superimpose another system's frame
  • A matrix can transform both a point and a system
  • $S_{6}$ moves the point within the ₹ system; it can also be used to transform ₹ system into $ system
    1D example where the transform is just a scalar, as the origins of both systems are coincident

The Double Life of a Matrix

Concatenating System Transforms

  • Like point transforms, system transforms too can be contatenated; after all they are matrices
  • However, the order of multiplication would be reversed; successive transforms are pre-mutliplied
  • $L_{a \rightarrow c} = $ $L_{b \rightarrow c}$ $L_{a \rightarrow b}$
  • System $S_1$ is transformed into system $S_n$ by transforming $S_1$ into $S_2$, then $S_2$ into $S_3$, and so on until $S_n$ is reached
  • After transforming to a system, all further matrices are calculated with respect to that system
    $L_{a \rightarrow b}$ is calcuated w.r.t system $A$, after concatenating it, $L_{b \rightarrow c}$ is calculated with respect to system $B$

Pot-ay-to — Pot-ah-to

Two ways to look at a complex transform

Transforming points & systems

  • A series of (concatenated) transforms may be seen
    1. left to right — points transformed in one (global) system Every transform is calculated with respect to this one system
    2. right to left — systems transformed Every transform is calculated with respect to the most recent local system in effect
  • Point transforms are concatenated by post-multiplying
    $X = $ $X_1$ $X_2$ $X_3$
  • System transforms are concatenated by pre-multiplying
    $L_{a \rightarrow b} = $ $X_3$ $X_2$ $X_1$
  • Since the order of multiplication is reversed result would be different (anti-commutativity)
  • Reason for same result in previous exercise: we transform in reverse order.
    Reverse order & pre-multiply ≡ original order & post-multiply (¬¬x = x)

Transform A into B

Part III

Mapping between systems

Converting a value in one system to another

$M_{a \rightarrow b}: P_a \rightarrow P_b$

Mapping

  • The most important feature of a transform
  • The benefit of having multiple systems is reaped when using matrices for mapping
  • Once a map is applied to a canvas/context, all values are implicitly converted from source to target space
  • Work entirely in a comfortable system after setting the right mapping
  • Multiple systems and mapping between them is common
    • Different countries, different currency and measurement systems
    • Most words of a language (system) has translations (mappings) to words of other languages
    • Every window on screen has its own viewport transform mapping to the screen canvas
    • Each group has a mapping to its parent group: SVG, PDF, …
  • (physics) Transforming points — active. Mapping — passive.
  • Active because old value becomes a new value — one system, two different values
    Passive since same value is just converted to a new unit — one value, two different systems
  • Active transforms are relatively less frequent
  • They are mostly used in animation

Map Red to Black

$P_r M_{r \rightarrow b} = P_b$

$M_{r \rightarrow b} = S_{2, 2} = L_{b \rightarrow r}$

$\boxed{ M_{r \rightarrow b} = L_{b \rightarrow r} }$
The transform that maps points of system A to B also transforms system B's frame into A.

Concatenating Mappings

  • Similar to point and system transforms, mappings can be concatenated too
  • Like point transforms, successive transforms are post-multiplied
  • $M_{a \rightarrow c} = $ $M_{a \rightarrow b}$ $M_{b \rightarrow c}$
  • $L_{c \rightarrow a} = $ $L_{b \rightarrow a}$ $L_{c \rightarrow b}$ $ = M_{a \rightarrow c}$
  • ∵ $M_{a \rightarrow b} = L_{b \rightarrow a}$
  • Intermediate maps $M_{a \rightarrow b}$ and $M_{b \rightarrow c}$ are found by transforming frame B to A and frame C to B respectively
  • Finding all intermediate maps is essentially transforming frame C to A
  • To find the mapping from system A to C, finding the matrix which transforms system C to A will do.

Mixing Active and Passive Transforms

  • A single matrix performing both active and passive transforms maybe needed
  • Concatenation order: active (point transforms) first, passive (maps) next
  • $C = $ $X_1 X_2 …$ $M_1 M_2 …$
  • Active part works in local space without any maps
  • Passive part then maps that to target space
  • Order is important again
  • If reversed the Active part would get interpreted in the target space

Hierarchical Transforms

  • Mapping with many systems in between is common
    • Boy is inside a room
    • Room is inside a house
    • House is inside … Alright, alright, I get it!
    • Now map points w.r.t to the boy to points w.r.t the city space
  • Different entites exist at different levels: root, parent and leaf
  • Knowing an entity's position in parent/root space requires mapping
  • All maps from entity to parent/root are concatenated
  • When visiting an entity, its map is concatenated with parent's
  • This happens recursively till the root node
  • Stack data structure is usually used to preserve parent's map
  • Each entity PUSHes before concatenation and POPs when done. Without this the parent's map would get altered by current node's transforms rendering it unusable for its siblings

Map Boy space to Street space

$M_{b \rightarrow s}$ = $L_{s \rightarrow b}$
$L_{s \rightarrow b}$ = $L_{k \rightarrow b}~$$L_{h \rightarrow k}~$$L_{s \rightarrow h}$
$L_{s \rightarrow h}$ = $T_{0, -6}~$$S_{1, -1}~$$S_{\frac{2}{3}, \frac{2}{3}}$
$L_{h \rightarrow k}$ = $R_{-90}~$$S_{\frac{1}{2}, \frac{1}{2}}~$$T_{2, 4}$
$L_{k \rightarrow b}$ = $R_{135}~$$T_{4, 2}$

$M_{b \rightarrow s} = \begin{pmatrix}0.2357 & -0.2357 & 0\\-0.2357 & -0.2357 & 0\\2 & 2.6667 & 1\end{pmatrix}$

Thank You