\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{epsfig}

%\textheight= 8in
%\textwidth=8in
\parindent =0pt
%\voffset = -1 in
%\hoffset= -1 in
\parindent = 0pt
\parskip = 6pt
\tolerance = 10000

\newcommand{\aaa}{\ensuremath{\mathbf{a}}}
\newcommand{\ee}{\ensuremath{\mathbf{e}}}
\newcommand{\vv}{\ensuremath{\mathbf{v}}}
\newcommand{\uu}{\ensuremath{\mathbf{u}}}
\newcommand{\ww}{\ensuremath{\mathbf{w}}}
\newcommand{\xx}{\ensuremath{\mathbf{x}}}
\newcommand{\rr}{\ensuremath{\mathbf{r}}}
\newcommand{\pp}{\ensuremath{\mathbf{p}}}
\newcommand{\oo}{\ensuremath{\mathbf{o}}}
\newcommand{\sss}{\ensuremath{\mathbf{s}}}
% ===========================================================

\title{2D Transformations\\ Introduction to Computer Graphics \\ Arizona State University}

\author{Gerald Farin}
\date{\today}



\begin{document}


\maketitle


\section{Introduction}\label{sec:intro}

When you see computer graphics images moving, spinning, or changing shape, you are
seeing an implementation of 2D or 3D transformations. Let's focus on 2D here; once
you understand 2D, 3D is simple!

2D transformations can be posed as the following problem.

{\em Given}: $\vv$ in the $[\ee_1, \ee_2]$-coordinate system, where
$\vv = v_1\ee_1 + v_2\ee_2$.

{\em Find}: $\hat{\vv}$ in the $[\aaa_1, \aaa_2]$-coordinate system, where
  $\hat{\vv} = \hat{v}_1\aaa_1 + \hat{v}_2\aaa_2$.

The geometry of this problem is illustrated in Figure \ref{fig:linearmap}. Another
name for a 2D transformation is a {\em 2D linear map}. The purpose of this write-up
is to define  2D linear maps.

\begin{figure}
    \begin{center}\epsfig{file=figures/linearmap.ps, height = 3 in}\end{center}
    \caption{Elements defining a linear map: $[\ee_1, \ee_2]\rightarrow [\aaa_1, \aaa_2]$.}
  \label{fig:linearmap}
\end{figure}

Notation: the elements of $\aaa_1 = \begin{bmatrix} a_{11}\\a_{21}\end{bmatrix}$
and $\aaa_2 = \begin{bmatrix} a_{12}\\a_{22}\end{bmatrix}$.

To define the 2D transformation that takes $\vv$ to $\hat{\vv}$,
notice that in addition we want:
\begin{equation}
\ee_1 \rightarrow \aaa_1 \quad {\rm and} \quad \ee_2 \rightarrow \aaa_2.
   \label{eq:mapdef}
\end{equation}
This mapping will be defined as a $2\times 2$ matrix, and it is easy to see that
$$
\begin{bmatrix} a_{11}\\a_{21}\end{bmatrix} =
\begin{bmatrix} a_{11} & a_{12}\\a_{21} & a_{22}\end{bmatrix}
\begin{bmatrix} 1\\0\end{bmatrix}
\quad\textrm{and}\quad
\begin{bmatrix} a_{12}\\a_{22}\end{bmatrix} =
\begin{bmatrix} a_{11} & a_{12}\\a_{21} & a_{22}\end{bmatrix}
\begin{bmatrix} 0\\1\end{bmatrix}
$$
A short-hand way to write these maps:
$$
\aaa_1 = [\aaa_1, \aaa_2]\ee_1  \quad\textrm{and}\quad
\aaa_2 = [\aaa_1, \aaa_2]\ee_2.
$$
We'll  write matrices in terms of their column vectors
frequently during this course.

Therefore, the vector $\vv$ is mapped to $\hat{\vv}$ by
\begin{equation}
\begin{split}
\hat{\vv} &= \begin{bmatrix} a_{11} & a_{12}\\ a_{21} & a_{22}\end{bmatrix}\vv \\
     &= [\aaa_1, \aaa_2]\vv \\
     &= A\vv \\
\end{split}
\end{equation}

The matrix A is called a {\em linear map}.
Linear maps operate on vectors. (However, you will see them applied to points which
are bound to a coordinate origin.)


\section{Determinants and Area}

Vectors $[\ee_1, \ee_2]$  define a parallelogram (unit square) with area one.
Vectors $[\aaa_1, \aaa_2]$  define a parallelogram  with area
$$
|A| = \begin{vmatrix} a_{11} & a_{12}\\ a_{21} & a_{22}\end{vmatrix}
= a_{11}a_{22} - a_{12}a_{21},
$$
where $|A|$ is called the {\em determinant} of matrix $A$.
In other words, $A$ maps the unit square to a parallelogram of area $|A|$.
\begin{itemize}
\item $|A| = 1$: no area change
\item $0 < |A| <1$: shrink
\item $|A| > 1$: expand
\item $|A| < 0$: change orientation
\end{itemize}

Handy relation: $|AB| = |A||B|$.

\section{2D Linear Maps}

All linear maps are composed of the following basic maps: scale, rotate, shear, projection.


{\bf Scale}:
\begin{enumerate}
\item Scale uniformly:
$\hat{\vv} = \begin{bmatrix} s & 0 \\ 0 & s \end{bmatrix}\vv$.
See Figure \ref{fig:uniformscale}. $|A| = s^2$.

\begin{figure}
    \begin{center}
    \epsfig{file=figures/Scale.ps, height = 3 in}
    \end{center}
    \caption{Uniform scale:
    ${\hat{\vv}}= \begin{bmatrix} 1/2 & 0 \\ 0 & 1/2
    \end{bmatrix}\vv.
    $}
  \label{fig:uniformscale}
\end{figure}


\item Scale non-uniformly:
$\hat{\vv} = \begin{bmatrix} s_1 & 0 \\ 0 & s_2 \end{bmatrix}\vv$.
See Figure \ref{fig:nonuniformscale}. $|A| = s_1s_2$.

\begin{figure}
\begin{center}
    \epsfig{file=figures/Scale1.ps, height = 3 in}
    \end{center}
    \caption{Non-uniform scale: $\hat{\vv} = \begin{bmatrix} 1/2 & 0 \\ 0 & 3/2 \end{bmatrix}\vv$.}

    \label{fig:nonuniformscale}
\end{figure}

\end{enumerate}


{\bf Reflections}:

Here are some examples of reflection matrices. A reflection will have $|A| = -1$

\begin{enumerate}
\item Reflections about the $\ee_1$-axis:
$\hat{\vv} = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\vv$.
See Figure \ref{fig:reflectionx}. $|A| = -1$.



\begin{figure}
\begin{center}
    \epsfig{file=figures/Reflectx.ps, height = 3 in}\end{center}
    \caption{Reflection about the $\ee_1$-axis
$\hat{\vv} = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\vv$.}

    \label{fig:reflectionx}
\end{figure}




\item Reflection about the line $x_1=x_2$:
$\hat{\vv} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\vv$.
See Figure \ref{fig:reflectionxy}. $|A| = -1$.

\begin{figure}
\begin{center}
    \epsfig{file=figures/Reflover.ps, height = 3 in}\end{center}
    \caption{Reflection about the line $x_1=x_2$:
$\hat{\vv} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\vv$.}

    \label{fig:reflectionxy}
\end{figure}



\end{enumerate}



{\bf Rotation}:

A rotation of $\alpha^\circ$ is achieved by
$$
\hat{\vv} = \begin{bmatrix} \cos(\alpha^\circ) & -\sin(\alpha^\circ) \\ \sin(\alpha^\circ) & \cos(\alpha^\circ) \end{bmatrix}\vv.
$$
Rotations of positive degrees ($\alpha > 0$) result in a counterclockwise rotation. A rotation does not change areas, that is, $|A|= \cos^2(\alpha^\circ) + \sin^2(\alpha^\circ)=1$. Additionally, a rotation is a {\em rigid body motion} because the shape of an object is not changed by a rotation.

Rotate $45^\circ$:
$\hat{\vv} = \begin{bmatrix} \cos(45^\circ) & -\sin(45^\circ) \\ \sin(45^\circ) & \cos(45^\circ) \end{bmatrix}\vv$.
See Figure \ref{fig:rotate}.

\begin{figure}
\begin{center}
    \epsfig{file=figures/Rotate.ps, height = 3 in}\end{center}
    \caption{Rotate $45^\circ$:
$\hat{\vv} = \begin{bmatrix} \cos(45^\circ) & -\sin(45^\circ) \\ \sin(45^\circ) & \cos(45^\circ) \end{bmatrix}\vv$.}

    \label{fig:rotate}
\end{figure}





{\bf Shear}:

We can shear in either or both axes.

Shear in the $\ee_1$ direction
$\hat{\vv} = \begin{bmatrix} 1 & 0.5 \\ 0 & 1 \end{bmatrix}\vv$.
See Figure \ref{fig:shear}. $|A| = 1$. (Notice that the parallelogram maintains
a base and height of one!)

\begin{figure}
\begin{center}
    \epsfig{file=figures/Shearx.ps, height = 3 in}\end{center}
    \caption{Shear in the $\ee_1$ direction
$\hat{\vv} = \begin{bmatrix} 1 & 0.5 \\ 0 & 1 \end{bmatrix}\vv$.}

    \label{fig:shear}
\end{figure}


{\bf Projections}:

All vectors are projected onto a projection line. The angle of incidence with the projection line characterizes the projection, as illustrated in Figure \ref{fig:projections}, and enumerate below.
\begin{enumerate}
\item Parallel: All vectors have the same angle of incidence with the projection line.
\begin{enumerate}
\item Orthographic - angle of incidence is ninety-degrees to the projection line.
$$
A=\begin{bmatrix} 1 & 0 \\ 0 & 0\end{bmatrix}
$$
\item Oblique - arbitrary angle to the projection line
$$
A=\begin{bmatrix} -1 & 0 \\ 1 & 0\end{bmatrix}
$$
\end{enumerate}

\item General projections do not necessarily project all vectors with the same angle of incidence with the projection line. The general form:
$$
A=\begin{bmatrix} \aaa_1 & c\aaa_1\end{bmatrix}.
$$
The columns are {\em linearly dependent}. The number of
linearly independent columns is the {\em rank} of a matrix. Here: rank equals one.
\end{enumerate}
The determinant of a projection matrix: $|A| = 0$ since our unit square is squished to a line.

\begin{figure}
   \begin{center}
    \epsfig{file=figures/projections.ps, height = 3 in}
    \end{center}
    \caption{Projections are characterized by their angle of incidence with the projection line. Left: orthographic, Middle: oblique, Right: general.}

\label{fig:projections}
\end{figure}


\section{Properties of Linear Maps}

A linear map,  $\hat{\vv} = A\vv$,
\begin{itemize}
\item Maps vectors $\rightarrow$ vectors
\item Preserves linear combinations of vectors. Suppose we have
$$
{\bf w} = \alpha {\bf u} + \beta {\bf v}
$$
Apply the linear map:
$$
\hat{\vv} = A\vv \qquad \hat{\uu} = A\uu \qquad \hat{\ww} = A\ww
$$
And the relationship still holds:
$$
\hat{\ww} = \alpha \hat{\uu} + \beta \hat{\vv}
$$
\end{itemize}

\section{Matrix Multiplication}

Matrix operations are not commutative: $AB \ne BA$ in general.
For example,
rotate$\times$reflect  $\ne$ reflect$\times$rotate.
See Figure \ref{fig:commutenot}.

However, rotations {\em in 2D} do commute: $R_\alpha R_\beta = R_\beta R_\alpha$. Additionally, $R_\alpha R_\beta = R_{\alpha + \beta}$.

\begin{figure}
\begin{center}
    \epsfig{file=figures/Nocomm.ps, height = 4 in}\end{center}
    \caption{Matrix operations are not commutative. Top right:
${\rm rotate}(-120^\circ)\times {\rm reflect}({\rm about}\  x)$. This is not the same
as the bottom right:
${\rm reflect}({\rm about}\  x)\times {\rm rotate}(-120^\circ)$.}

\label{fig:commutenot}
\end{figure}

\section{Affine Maps}

Modeling transformations include translations. This is where affine maps come in,  and affine maps give us a tools for applying transformations to points.

Suppose we have a point $\xx$ in the $[\ee_1,\ee_2]$-system, and we would like to find
the corresponding point $\hat{\xx}$ in a system defined by a point $\pp$ and $[\aaa_1,\aaa_2]$. This is illustrated in Figure \ref{fig:affinemap}.

\begin{figure}
\begin{center}
    \epsfig{file=figures/affinemap.ps, height = 3 in}\end{center}
    \caption{Affine map: defines the transformation of a point $\xx$ in the $[\ee_1,\ee_2]$ system to a point $\hat{\xx}$ in the system defined by $\pp$ and $[\aaa_1,\aaa_2]$.}

\label{fig:affinemap}
\end{figure}


We need to apply a linear map to the vector $(\xx-\oo)$ to find the corresponding vector in the
$[\aaa_1, \aaa_2]$ system, and then translate the geometry by $\pp$, or in other words,
\begin{equation*}
\begin{split}
  \hat{\xx} &= \pp + A(\xx-\oo)  \\
            &= \pp + A\xx
\end{split}
\end{equation*}
Thus an affine map is a translation plus a linear map.
As mentioned in Section \ref{sec:intro}, it can appear that we apply a linear
map to a point, but actually we are applying the linear map to the  vector formed by the
point and the origin.

Affine maps have the following properties.
\begin{enumerate}
\item A point is mapped to a point.
\item The ratio of three collinear points is preserved. For example, suppose points $\rr$, $\sss$, and $\xx$ are collinear and ${\rm ratio}(\rr,\xx,\sss)=\alpha : \beta$. Apply an affine map to these points, resulting in points $\hat{\rr}$, $\hat{\sss}$, and $\hat{\xx}$, then these points are collinear and ${\rm ratio}(\hat{\rr},\hat{\xx},\hat{\sss})=\alpha : \beta$. See Figure \ref{fig:ratiospreserve}.
\item Parallel lines are mapped to parallel lines.
\end{enumerate}

\begin{figure}
\begin{center}
    \epsfig{file=figures/ratiospreserve.ps, height = 3 in}\end{center}
    \caption{Affine maps preserve the ratio of three collinear points.}
\label{fig:ratiospreserve}

\end{figure}


Translations (along with rotations) are {\em rigid body motions} -- they transform the geometry without deforming it.

{\bf Exercise}:
As practice in constructing affine maps, try creating the affine map (by defining $A$ and $\pp$) that takes the
$\oo, [\ee_1,\ee_2]$ local coordinates to the global coordinates defined by the
target box ${\bf g}_{min}, {\bf g}_{max}$.

{\bf Problem}: Given  points $\rr$ and  $\xx$, rotate $\xx$ $d$ degrees about $\rr$. This geometry is illustrated in Figure \ref{fig:rotateabout}.

This is a problem that arises frequently in computer graphics. A constructive approach
is necessary as $\aaa_1$ and $\aaa_2$ are not given directly. One way to think about it: Translate $\rr$ and $\xx$ to the origin, rotate, and then translate the geometry back to its original position, or in other words,
\begin{equation*}
\begin{split}
  \hat{\xx} &= \rr + A(\xx - \rr)\\
            &= \rr + \begin{bmatrix} \cos(d^\circ) & -\sin(d^\circ) \\ \sin(d^\circ) & \cos(d^\circ)\end{bmatrix}(\xx - \rr).
\end{split}
\end{equation*}

\begin{figure}
\begin{center}
    \epsfig{file=figures/rotateabout.ps, height = 3 in}\end{center}
    \caption{Problem: Rotate point $\xx$ $d^\circ$ about the point $\rr$, resulting in point $\hat{\xx}$. Here: $d=90^\circ$.}

\label{fig:rotateabout}
\end{figure}

\vspace{36pt}


\small{Figures extracted from
{\bf The Geometry Toolbox  for Graphics and Modeling}
Gerald Farin and Dianne Hansford
AK Peters, 2nd edition, 2004}




\end{document}
