Computer Graphics

2D Transformations and Homogeneous Coordinates

Prof. Dr. Ulrich Schwanecke

RheinMain University of Applied Sciences

🚀 by Decker

Vector Space \(\R^n\)

Scalars \(\alpha, \beta, \gamma, t \in \R\)
- are written in italic font.
Vectors \(\vec{x} \in \R^n\)
- are written in bold font,
- are column vectors \(\vec{x} \in \R^{n \times 1}\), and
- their components are denoted as \(\vec{x}=\trans{(x_1, \dots, x_n)}\), which means go \(x_i\) units in the direction of the
  \(i\)-the basis vector of a given (Cartesian) coordinate system
Linear combinations \(\alpha\,\vec{x} + \beta\,\vec{y} \in \R^n\) are performed component-wise and stay in the vector space.

Euclidean Vector Space \(\R^n\)

Inner product aka dot product aka scalar product \[ \iprod{ \vec{x} , \vec{y} } = \vec{x} \cdot \vec{y} = \trans{\vec{x}}\vec{y} = \sum_{i=1}^{n} x_i y_i \]
The induced metric measures geometric length \[ \norm{\vec{x}} = \sqrt{ \trans{\vec{x}}\vec{x}} = \sqrt{ \sum_{i=1}^n x_i^2 }\]
Scalar product can measure angle \(\theta\) between two vectors

\[ \mathbf{x}^\top \mathbf{y} = \cos\theta \, \|\mathbf{x}\| \, \|\mathbf{y}\| \quad\Rightarrow\quad \theta = \mathrm{acos}\left( \frac{\mathbf{x}^\top \mathbf{y}}{\|\mathbf{x}\| \|\mathbf{y}\|}\right)\]

Points vs. Vectors

Subtle distinction
- Points denote positions in \(\R^3\)
- Vectors denote differences of points
Meaningful operations
- vector + vector = vector
- point - point = vector
- point + vector = point
- point + point = ???
  - only meaningful if \(\vec{q} = \sum_{i=1}^n \alpha_i \vec{p}_i\) with
    - \(\sum_{i=1}^n \alpha_i = 1 \quad\Longrightarrow\quad \vec{q} = \vec{p}_1 + \sum_{i=2}^n \alpha_i (\vec{p}_i-\vec{p}_1)\)
    - \(\sum_{i=1}^n \alpha_i = 0 \quad\Longrightarrow\quad \vec{q} = \sum_{i=2}^n \alpha_i (\vec{p}_i-\vec{p}_1)\)

Application: Point in Convex Polygon

Test whether the point \(\vec{p}\) lies in the convex polygon \(\vec{p}_0,\ldots , \vec{p}_5=\vec{p}_0\):

Calculate the edges \(\vec{v}=\vec{p}_{i+1}-\vec{p}_i\) of the polygon
Determine the normal vectors \(\vec{n}_i\)
[\(\vec{n}_i=(-y_i, x_i)^T\) if \(\vec{v}_i=(x_i, y_i)^T\)]
\(\vec{p}\) lies inside the polygon, iff \(\langle \vec{n}_i, (\vec{p}-\vec{p}_i)\rangle <0 \quad\forall\; i = 0,\ldots , n-1\)
- if \(\langle \vec{n}_i, (\vec{p}-\vec{p}_i)\rangle >0\) for any \(i\), then \(\vec{p}\) is outside the polygon
- \(\vec{p}\) lies on the boundary of the polygon iff \(\langle \vec{n}_i, (\vec{p}-\vec{p}_i)\rangle \leq 0\quad\forall\; i = 0,\ldots , n-1\),
  where at least once “\(=\)” holds.

images/pointinpolygontest.png — point in polygon test

Vector Product

The vector product of the vectors \(\vec{v}, \vec{w}\) is given as

\[ \small \begin{pmatrix}v_1 \\ v_2 \\ v_3\end{pmatrix} \times \begin{pmatrix}w_1 \\ w_2 \\ w_3\end{pmatrix} = \begin{vmatrix} \vec{e}_1 & \vec{e}_2 & \vec{e}_3 \\ v_1 & v_2 & v_3 \\ w_1 & w_2 & w_3 \end{vmatrix} = \begin{pmatrix} v_2w_3 - v_3w_2 \\ v_3w_1 - v_1w_3 \\ v_1w_2 - v_2w_1 \end{pmatrix} = \underbrace{ \begin{pmatrix} 0 & -v_3 & v_2 \\ v_3 & 0 & -v_1 \\ -v_2 & v_1 & 0 \end{pmatrix}}_{=:[\vec{v}]_\times} \begin{pmatrix}w_1 \\ w_2 \\ w_3\end{pmatrix} \]

It holds

\(\vec{v}\times\vec{w} = [\vec{v}]_\times \vec{w} = -[\vec{w}]_\times \vec{v}= -\vec{w}\times\vec{v}\)
the vector \(\vec{v}\times\vec{w}\) is orthogonal to the plane defined by \(\vec{v}\) and \(\vec{w}\)
\(\norm{\vec{v}\times\vec{w}}\) equals the area of the parallelogram given by \(\vec{v}\) and \(\vec{w}\)
if \(\vec{v}\times\vec{w} = \vec{0}\in\R^3\) the vectors \(\vec{v}\) and \(\vec{w}\) are collinear

images/vectorproduct.png — vector product

2D Transformations

images/trafo-translation.svg translation images/trafo-scaling.svg scaling

rotation

2D Translation

Translate object by \(t_x\) in \(x\) and \(t_y\) in \(y\) \[ \vector{x \\ y} \mapsto \vector{x+t_x \\ y+t_y} \]

images/trafo-translation.svg — translation by \((2,1)\)

2D Scaling

Scale object by \(s_x\) in \(x\) and \(s_y\) in \(y\)
(around the origin!) \[ \vector{x \\ y} \mapsto \vector{s_x \cdot x \\ s_y \cdot y} \]

images/trafo-scaling.svg — scaling by \((2,2)\)

2D Rotation

Rotate object by \(\theta\) degrees
(around the origin!)

2D Rotation

Rotate point \((x,y) = (r\cos\phi, r\sin\phi)\)
by \(\theta\) degrees around the origin

\[ \begin{eqnarray*} \begin{pmatrix} x\\y \end{pmatrix} &\mapsto& \begin{pmatrix}r \cos\left(\phi+\theta\right) \\ r \sin\left(\phi+\theta\right)\end{pmatrix} \\[2mm] &=& \begin{pmatrix} r \cos\phi \cos\theta - r \sin\phi \sin\theta \\ r \cos\phi \sin\theta + r \sin\phi \cos\theta \end{pmatrix} \\[2mm] &=& \begin{pmatrix}\cos\theta \cdot x - \sin\theta \cdot y \\ \cos\theta \cdot y + \sin\theta \cdot x\end{pmatrix} \\[2mm] &=& \begin{bmatrix}\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta\end{bmatrix} \cdot \vector{x \\ y} \end{eqnarray*} \]

images/trafo-rotation-2.svg — rotation by \(\theta\) degrees

2D Rotation

Rotate object by \(\theta\) degrees
(around the origin!) \[ \vector{x\\y} \mapsto \matrix{\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta} \cdot \vector{x \\ y} \]

How to rotate/scale around object center?

Translate center to origin
Scale object
Rotate object
Translate center back

This can get quite messy!

Important Questions

How to efficiently combine several transformations?

Represent transformations as matrices!

Matrix Representation

images/trafo-scaling.svg scaling \[ \mathbf{S}\left(s_x, s_y\right) = \begin{bmatrix} s_x & 0 \\ 0 & s_y \end{bmatrix} \]

images/trafo-rotation.svg rotation \[ \mathbf{R}\left(\theta\right) = \begin{bmatrix}\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta\end{bmatrix} \]

images/trafo-translation.svg translation \[ \mathbf{T}\left(t_x, t_y\right) = \begin{bmatrix} ? & ? \\ ? & ?\end{bmatrix} \]

Which transformations can be written as matrices?

Linear Maps & Matrices

Assume a linear transformation \(L \colon \R^n \to \R^n\)
- \(L(\mathbf{a}+\mathbf{b}) = L(\mathbf{a}) + L(\mathbf{b})\)
- \(L(\alpha \, \mathbf{a}) = \alpha \, L(\mathbf{a})\)
Point \(\vec{x}=\trans{(x_1, \ldots, x_n)}\) can be written as \[\mathbf{x} = x_1 \mathbf{e}_1 + x_2 \mathbf{e}_2 + \ldots + x_n \mathbf{e}_n\]

Linear Maps & Matrices

Exploit linearity of \(L\) \[ \begin{eqnarray*} L\left(\mathbf{x}\right) &=& L\left(x_1 \mathbf{e}_1 + x_2 \mathbf{e}_2 + \ldots + x_n \mathbf{e}_n\right) \\[2mm] &=& x_1 \, L\left(\mathbf{e}_1\right) + x_2 \, L\left(\mathbf{e}_2\right) + \ldots + x_n \, L\left( \mathbf{e}_n\right) \\[2mm] &=& \underbrace{\begin{bmatrix} L\left(\mathbf{e}_1\right) ,\; L\left(\mathbf{e}_2\right) ,\; \ldots ,\; L\left(\mathbf{e}_n\right)\end{bmatrix}}_{=:\mat{L}} \cdot \begin{pmatrix}x_1 \\ \vdots \\ x_n\end{pmatrix} \;=\; \mathbf{L}\,\mathbf{x} \end{eqnarray*} \]
Every linear transformation \(L \colon \R^n \to \R^n\) can be written as a unique \((n \times n)\) matrix \(\mat{L}\) whose columns are the images of the basis vectors \(\left\{ \vec{e}_1, \ldots, \vec{e}_n \right\}\).

VERY useful fact! 👍 VERY-VERY useful! 😍

Linear vs. Affine Transformations

Every linear transformation has to preserve the origin
- \(L(\vec{0}) = \mat{L} \cdot \vec{0} = \vec{0}\)
Translation is not a linear mapping
- \(T(0,0) = (t_x, t_y)\)
Translation is an affine transformation
- affine mapping = linear mapping + translation
- \(\vector{x \\ y} \mapsto \matrix{a & b \\ c & d} \cdot \vector{x \\ y} + \vector{t_x \\ t_y} = \mat{L}\vec{x} + \vec{t}\)

But we REALLY want to represent translations as matrices!

Homogeneous Coordinates

Extend cartesian coordiantes \((x,y)\) to homogeneous coordinates \((x,y,w)\)
- Points are represented by \(\trans{(x,y,1)}\)
- Vectors are represented by \(\trans{(x,y,0)}\)
Only homogeneous coordinates with \(w \in \{0,1\}\) are easy to interpret
- vector + vector = vector
- point - point = vector
- point + vector = point
- point + point = ??
Only affine combinations of points \(\vec{x}_i\) make sense
- \(\sum_i \alpha_i \vec{x}_i\) with \(\sum_i \alpha_i = 1\) (and \(\sum_i \alpha_i = 0\))

Homogeneous Coordinates in 2D

Points
- Each homogeneous vector of the form \(k\cdot (x_1, x_2, x_3)^\top\) with \(k, x_3 \not= 0\) represents the same 2D point \((x_1/x_3, x_2/x_3)^\top\)
- Each homogeneous vector of the form \((x_1, x_2, 0)^\top\) represents the 2D vector \((x_1, x_2)^\top\)
Lines
- Each homogeneous vector of the form \(k\cdot (a, b, c)^\top\) with \(k \not= 0\) represents the same 2D line \(a\cdot x + b\cdot y + c = 0\)
Incidence of points and lines
- A point with homogenous vector \(\vec{p}=(x_1, x_2, x_3)^\top\) lies on the line with homogeneous vector \(\vec{l}=(a,b,c)^\top\) iff \(\langle \vec{p},\vec{l}\rangle = 0\)

Intersection of two lines in 2D

Two lines with homogenous vectors \(\vec{l}_1\) and \(\vec{l}_2\) intersect in a point with homogeneous coordinate vector \(\vec{p} = \vec{l}_1 \times \vec{l}_2 = [\vec{l}_1]_\times \vec{l}_2\)

Line given by two points in 2D

The line given by two points with homogenous vectors \(\vec{p}_1\) and \(\vec{p}_2\) is given by the homogeneous coordinate vector \(\vec{l} = \vec{p}_1 \times \vec{p}_2 = [\vec{p}_1]_\times \vec{p}_2\)

Homogeneous Coordinates

Matrix representation of translations \[ \vector{x \\ y} + \vector{t_x \\ t_y} \quad\longleftrightarrow\quad \matrix{ 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1} \cdot \vector{x \\ y \\ 1} \]
Matrix representation of arbitrary affine transformation \[ \matrix{a & b \\ c & d} \cdot \vector{x \\ y} + \vector{t_x \\ t_y} \quad\longleftrightarrow\quad \matrix{ a & b & t_x \\ c & d & t_y \\ 0 & 0 & 1} \cdot \vector{x \\ y \\ 1} \]

Matrix Representation

images/trafo-scaling.svg scaling \[ \matrix{ s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1 } \]

images/trafo-rotation.svg rotation \[ \matrix{\cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1} \]

images/trafo-translation.svg translation \[ \matrix{ 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1} \]

Columns of matrix are images of basis vectors!

Concatenation of Transformations

Apply sequence of affine transformations \(\mat{A}_1, \ldots, \mat{A}_k\)
Concatenate transformations by matrix multiplication \[ A_k\left(\ldots A_2\left(A_1\left(\mathbf{x}\right)\right)\right) \;=\; \underbrace{\mathbf{A}_k \cdots \mathbf{A}_2 \cdot \mathbf{A}_1}_{\mathbf{M}} \cdot \mathbf{x} \]
Precompute matrix \(\mathbf{M}\) and apply it to all (=many!) object vertices.

Very important for performance!

Ordering of Matrix Multiplication

First rotation, then translation
First translation, then rotation

How to rotate/scale around object center?

Translate center to origin
Scale object
Rotate object
Translate center back

What is the matrix representation?

Matrix Representation?

Important Questions

What is preserved by affine transformations?
What is preserved by orthogonal transformations?

Affine Transformations

Any point \(\vec{C}\) on a line is an affine combination \[(1-\alpha)\vec{A} + \alpha\vec{B}\] of its endpoints \(\vec{A}\) and \(\vec{B}\).
Affine transformation \(\mat{M}\) preserves affine combinations \[ \mat{M}\left((1-\alpha)\vec{A} + \alpha\vec{B}\right) \;=\; (1-\alpha)\mat{M}\left(\vec{A}\right) + \alpha\mat{M}\left(\vec{B}\right) \]
Straight lines stay straight lines

Orthogonal Transformations

A matrix \(\mat{M}\) is orthogonal iff…
- …its columns are orthonormal vectors
- …its rows are orthonormal vectors
- …its inverse is its transposed: \(\mat{M}^{-1} = \trans{\mat{M}}\)
Orthogonal matrices / mappings…
- …preserve angles and lengths
- …can only be rotations or reflections
- …have determinant +1 or -1

Quiz

Quiz: Transformations

Which matrix represents the 2D translation \(\vector{x\\y} \mapsto \vector{x+a \\ y+b}\)?

\(\matrix{ 1 & 0 & a \\ 0 & 1 & b \\ 0 & 0 & 1 }\)
- Yes, exactly.
\(\matrix{ a & 0 & 0 \\ 0 & b & 0 \\ 0 & 0 & 1 }\)
- No, this is scaling matrix.
\(\matrix{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ a & b & 1 }\)
- No, this is some strange transformation.
\(\matrix{ 0 & 0 & a \\ 0 & 0 & b \\ 0 & 0 & 1 }\)
- No, this maps any \((x,y)\) to \((a,b)\)

Quiz: Transformations

Which matrix computes the
transformation on the right?

\(\mat{T}\left(2, 1\right) \cdot \mat{S} \cdot \mat{R}\)
- Yes, this scales/rotates around the bottom-left corner and then translates the object
\(\mat{T}\left(2, 2\right) \cdot \mat{S} \cdot \mat{R} \cdot \mat{T}\left(-\frac{1}{2}, -\frac{1}{2} \right)\)
- Yes, this translates the center to the origin, scales/rotates, and then moves it to the final position
\(\mat{R} \cdot \mat{S} \cdot \mat{T}\left(\frac{3}{2}, \frac{3}{2} \right)\)
- No.
\(\mat{T}\left(-\frac{1}{2}, -\frac{1}{2} \right) \cdot \mat{R} \cdot \mat{S} \cdot \mat{T}\left(2, 2\right)\)
- No, this is the wrong order of transformations

Quiz: Lines and Points in 2D

Give the homogenous vector for line through the points \(\vec{x}=(1,2)^\top\) and \(\vec{y}=(3,4)^\top\).

\((1, -1, 1)^\top\)
- Yes
\((1, 2, 3)^\top\)
- No, this is nonsens.
\((2, 3, 4)^\top\)
- No, this is nonsens.
\((-2, 2, -2)^\top\)
- Yes

Quiz: Lines and Points in 2D

Give the homogenous vector for the intersection of the lines \(x-y+1=0\) and \(x-y-1=0\).

\((2, 2, 0)^\top\)
- Yes
\((1, 2, 3)^\top\)
- No, this is nonsens.
\((1, 1, 0)^\top\)
- Yes
\((-2, 2, -2)^\top\)
- No, this is nonsens.