Transformation of 2D Shapes
An Introduction
|
Prof. David Bernstein
James Madison University
|
|
Computer Science Department
|
bernstdh@jmu.edu
|
Motivation
- What We Have:
- Methods for representing triangles and
convex polygons in 2D
- What We Need:
- The ability to transform these shapes in
various ways
An Instructive Shape - The Unit Square
- Visualization:
- As a Matrix:
- \(\left[ \begin{array}{r r r r}
0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1\end{array}\right]\)
- Remember that, in code, it is sometimes more
convenient to use the transpose (in which each vertex
is a row, not a column)
2D Transformations in General
- Our Objective:
- Operate on the \(2 \times n\) matrix
representation of a shape
- Get back a \(2 \times n\) matrix
representation
- Operations that Satisfy this Condition:
- Multiplication by a scalar
- Addition of a \(2 \times n\) matrix
- Pre-multiplication by a \(2 \times 2\) matrix
Scaling
- A Uniform Scaling:
- Scaling Each Dimension Independently:
- Multiply by a matrix of the form
\(\left[ \begin{array}{r r}
\alpha & 0 \\
0 & \beta\end{array}\right]\)
Scaling (cont.)
- An Example:
- \(
\left[ \begin{array}{r r}
2 & 0 \\
0 & 0.5\end{array}\right]
\left[ \begin{array}{r r r r}
0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1\end{array}\right]
=
\left[ \begin{array}{r r r r}
0 & 2 & 2 & 0 \\
0 & 0 & 0.5 & 0.5\end{array}\right]
\)
- Visualization:
Scaling (cont.)
- Be Careful:
- \(
\left[ \begin{array}{r r }
2 & 0 \\
0 & 0.5\end{array}\right]
\left[ \begin{array}{r r r r}
0.5 & 1.5 & 1.5 & 0.5 \\
0.5 & 0.5 & 1.5 & 1.5\end{array}\right]
=
\left[ \begin{array}{r r r r}
1 & 3 & 3 & 1 \\
0.25 & 0.25 & 0.75 & 0.75\end{array}\right]
\)
- Visualization:
Reflection
- Around the \(x\)-Axis:
- \(
\left[ \begin{array}{r r}
1 & 0 \\
0 & -1\end{array}\right]
\)
- Visualization:
Reflection (cont.)
- Around the \(y\)-Axis:
- \(
\left[ \begin{array}{r r}
-1 & 0 \\
0 & 1\end{array}\right]
\)
- Visualization:
Reflection (cont.)
- Around the Line \(x = -y\):
-
\(\left[ \begin{array}{r r}
0 & -1 \\
-1 & 0\end{array}\right]\)
- Visualization:
Reflection (cont.)
- Be Careful:
- It looks like reflections do not change
the area
- It looks like reflections are scalings
- In Fact:
- They can change the sign of the area
- In general, reflections are not scalings (they are Householder
transformations)
Shears
- Along the \(x\)-Axis:
- \(
\left[ \begin{array}{r r}
1 & d_{1} \\
0 & 1\end{array}\right]
\)
- Visualization:
Shears (cont.)
- Along the \(y\)-Axis:
- \(
\left[ \begin{array}{r r}
1 & 0 \\
d_{2} & 1\end{array}\right]
\)
- Visualization:
Shears (cont.)
- One Use of Shears:
- Note:
- Shears do not change the area
Rotation
- An Interesting Transformation Matrix:
- \(
\left[ \begin{array}{r r}
0 & -1 \\
1 & 0\end{array}\right]
\left[ \begin{array}{r r r r}
0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1\end{array}\right]
=
\left[ \begin{array}{r r r r}
0 & 0 & -1 & -1 \\
0 & 1 & 1 & 0\end{array}\right]
\)
- Visualization:
Rotation (cont.)
- Some Intuition:
- What We Need:
- \(
\left[ \begin{array}{r}
\cos \theta \\ \sin \theta \end{array}\right] = \bs{R}
\left[ \begin{array}{r r}
1 \\ 0\end{array}\right]
\)
\(
\left[ \begin{array}{r}
-\sin \theta \\ \cos \theta\end{array}\right] = \bs{R}
\left[ \begin{array}{r}0 \\ 1\end{array}\right]
\)
- The Transformation Matrix that Satisfies these Conditions:
- \(
\bs{R} = \left[ \begin{array}{r r}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta\end{array}\right]
\)
Rotation (cont.)
- Be Careful:
- These rotations are around the origin
- Note:
- Rotations do not change the area
Translation
- Defined:
- Moving a shape without changing its orientation
- Operation:
- Add a value to the components of each point
Combining Transformations
- An Important Observation:
- Some transformations can be combined by
multiplying the transformation matrixes
- An Unfortunate Observation:
- Scaling, reflection, shears and rotation all involve
matrix multiplication
- Translation involves vector addition
Homogeneous Coordinates
- Recall:
- The homogeneous form of a line is the set of points
that satisfy:
- \(h_{1}p_{1} + h_{2}p_{2} + 1 = 0\)
- An Observation:
- If we add a third coordinate to each point we
can write this as:
- \(
\left[ \begin{array}{r}
h_{1} \\ h_{2} \\ 1\end{array}\right] \cdot
\left[ \begin{array}{r}
p_{1} \\ p_{2} \\ 1\end{array}\right] =
\left[ \begin{array}{r}
0 \\ 0 \\ 0\end{array}\right]
\)
- The Homogeneous Coordinate System:
- Every point \([p_{1} \quad p_{2}]\) in Cartesian
coordinates corresponds to a point
\([p_{1} \quad p_{2} \quad 1]\) in homogeneous coordinates
Translation in Homogeneous Coordinates
- An Observation:
- \(
\left[ \begin{array}{r r r}
1 & 0 & \tau_{1} \\
0 & 1 & \tau_{2} \\
0 & 0 & 1\end{array}\right]
\left[ \begin{array}{r}
p_{1} \\
p_{2} \\
1 \end{array}\right] =
\left[ \begin{array}{r}
p_{1}+\tau_{1} \\
p_{2}+\tau_{2} \\
1 \end{array}\right]
\)
- Interpretation:
- In homogeneous coordinates, we can translate a point
using matrix multiplication
Translation in Homogeneous Coordinates (cont.)
- Translation Matrix:
- \(
\bs{T} =
\left[ \begin{array}{r r r}
1 & 0 & \tau_{1} \\
0 & 1 & \tau_{2} \\
0 & 0 & 1\end{array}\right]
\)
- Inverse Translation Matrix:
- \(
\bs{T}^{-1} =
\left[ \begin{array}{r r r}
1 & 0 & -\tau_{1} \\
0 & 1 & -\tau_{2} \\
0 & 0 & 1\end{array}\right]
\)
Scaling in Homogeneous Coordinates
- Scaling Matrix:
- \(
\bs{S} =
\left[ \begin{array}{r r r}
\sigma_{1} & 0 & 0 \\
0 & \sigma_{2} & 0 \\
0 & 0 & 1\end{array}\right]
\)
- Inverse Scaling Matrix:
- \(
\bs{S}^{-1} =
\left[ \begin{array}{r r r}
1 / \sigma_{1} & 0 & 0 \\
0 & 1/ \sigma_{2} & 0 \\
0 & 0 & 1\end{array}\right]
\)
Shears in Homogeneous Coordinates
- Along the \(x\)-Axis:
- \(
\left[ \begin{array}{r r r}
1 & d_{1} & 0 \\
0 & 1 & 0 \\
0 & 0 & 1\end{array}\right]
\)
- Along the \(y\)-Axis:
- \(
\left[ \begin{array}{r r r}
1 & 0 & 0 \\
d_{2} & 1 & 0 \\
0 & 0 & 1\end{array}\right]
\)
Rotation in Homogeneous Coordinates
- Rotation Matrix (Around the Origin):
- \(
\bs{R} =
\left[ \begin{array}{r r r}
\cos \theta & -\sin \theta & 0 \\
\sin \theta & \cos \theta & 0 \\
0 & 0 & 1\end{array}\right]
\)
- Inverse Rotation Matrix:
- Use the negative of the angle
Rotation in Homogeneous Coordinates (cont.)
- Rotation Around a Point:
- Translate the center of rotation to the origin,
rotate, translate back
- The Result:
- \(
\left[ \begin{array}{r r r}
1 & 0 & -x \\
0 & 1 & -y \\
0 & 0 & 1\end{array}\right]
\left[ \begin{array}{r r r}
\cos \theta & -\sin \theta & 0 \\
\sin \theta & \cos \theta & 0 \\
0 & 0 & 1\end{array}\right]
\left[ \begin{array}{r r r}
1 & 0 & x \\
0 & 1 & y \\
0 & 0 & 1\end{array}\right]
=
\left[ \begin{array}{r r r}
\cos \theta & -\sin \theta & -x(\cos \theta -1) + y \sin \theta \\
\sin \theta & \cos \theta & -x \sin \theta - y(\cos \theta -1) \\
0 & 0 & 1\end{array}\right]
\)
Reflection in Homogeneous Coordinates
- Around the \(x\)-Axis:
- \(
\left[ \begin{array}{r r r}
1 & 0 & 0 \\
0 & -1 & 0 \\
0 & 0 & 1\end{array}\right]
\)
- Around the \(y\)-Axis:
- \(
\left[ \begin{array}{r r r}
-1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1\end{array}\right]
\)
Combining Transformations in Homogeneous Coordinates
- An Important Observation:
- Different transformations can be combined by
multiplying the transformation matrixes
- Efficiency:
- It is generally more efficient to combine the
transformations
There's Always More to Learn