\documentclass[a4paper,11pt]{article}

% Definitions for the document
\def \Course {Interactive Computer Graphics }
\def \LectureNo {2}
% font definitions used in vector algebra
\newcommand{\Vector}[1]{\mathbf{#1}}
\newcommand{\UVector}[1]{\textbf{\em #1}}
\newcommand{\Matrix}[1]{\mathcal{#1}}
% standard layout for Duncan's lecture notes and tutorial material
\usepackage[margin=2cm, nohead]{geometry}
\usepackage{times}
\usepackage{wrapfig}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{amsfonts}
\pagestyle{fancy}
\fancyhead{}
\fancyfoot{}
\renewcommand{\footrulewidth}{0.4pt}
\renewcommand{\headrulewidth}{0pt}
\lfoot{\footnotesize{\Course Lecture  \LectureNo}}
\rfoot{\footnotesize{\thepage}}
% end of standard layout

\begin{document}

\section*{Lecture \LectureNo : Scene Transformation and Animation}

\subsection*{Flying Sequences}

% \begin{wrapfigure}{r}{105mm}
%   \vspace{-5mm}
%   \begin{center}
%      \includegraphics[width=103mm]{Figures/GraphicsFigure01_01.jpg} 
%   \end{center}
%   \vspace{-5mm}
%   \caption{Normalisation transformation}
%   \vspace{-3mm}
%   \label{fig:GraphicsFigure01_01}
% \end{wrapfigure}


We will now consider a most important subject, namely, scene transformation. In any viewer centered application, such as a flight simulator or a computer game, we need to view the scene from a moving position. As the viewpoint changes we transform all the coordinates of the scene such that the viewpoint is the origin and the view direction is the $z$ axis, before projecting and drawing the scene. Let us suppose that, in the coordinate system in which the scene is defined we wish to view it from the point $\Vector{C} = [C_x,C_y,C_z]$, 
looking along the direction $\UVector{d} = [d_x,d_y,d_z]$. The first step is to move the origin to $\Vector{C}$ 
for which we use the transformation matrix $\Matrix{A}$. \\
\begin{minipage}[]{9 cm}
 \includegraphics[width=89mm]{Figures/GraphicsTransformationsMatrixA.jpg}
\end{minipage} 
\hspace{1cm}
\begin{minipage}[]{6 cm}
$ \Matrix{A} = 
 \left[
  \begin{array}{ c c c c }
     1    & 0    & 0    & 0 \\
     0    & 1    & 0    & 0 \\
     0    & 0    & 1    & 0 \\
     -C_x & -C_y & -C_z & 1
  \end{array} \right] $ 
\end{minipage}\\
Following this, we wish to rotate about the $y$-axis so that $\Vector{d}$ lies in the plane $x=0$. 
Using the fact that $\Vector{d}$ is defined by the co-ordinates $[d_x d_y d_z]$ and using the notation 
$v^2 = d_x^2 + d_z^2$  this is done by matrix $\Matrix{B}$. \\
\begin{minipage}[]{5 cm}
 \includegraphics[width=49mm]{Figures/GraphicsTransformationsMatrixB.jpg}
\end{minipage} 
\hspace{1cm}
\begin{minipage}[]{4cm}
$
v = \sqrt{d_x^2 + d_z^2}
\newline
\newline
Cos\theta = d_z / v
\newline
\newline
Sin\theta = d_x/v
$
\end{minipage}
\begin{minipage}[]{5cm}
$
\Matrix{B} = 
 \left[
  \begin{array}{ c c c c }
     d_z/v  & 0    & d_x/v & 0 \\
     0      & 1    & 0     & 0 \\
     -d_x/v & 0    & d_z/v & 0 \\
     0      & 0    & 0     & 1
  \end{array} \right] 
$
\end{minipage}\\
Notice that we have avoided computing the $Cos$ and $Sin$ functions for this rotation by use of the direction cosine. To get the direction vector lying along the $z$ axis a further rotation is needed. This time it is about the $x$ axis using matrix $\Matrix{C}$. \\
\begin{minipage}[]{5 cm}
 \includegraphics[width=49mm]{Figures/GraphicsTransformationsMatrixC.jpg}
\end{minipage} 
\hspace{1cm}
\begin{minipage}[]{4cm}
$
v = \sqrt{d_x^2 + d_z^2}
\newline
\newline
Cos\phi = v/|d|
\newline
\newline
Sin\phi = d_y/|d|
$
\end{minipage}
\begin{minipage}[]{6cm}
$
\Matrix{C} = 
 \left[
  \begin{array}{ c c c c }
     1 & 0       & 0       & 0 \\
     0 & v/|d|   & d_y/|d| & 0 \\
     0 & -d_y/|d|& v/|d|   & 0 \\
     0 & 0       & 0       & 1
  \end{array} \right] 
$
\end{minipage}\\
Finally the transformation matrices are combined into one, and each point of the scene is transformed: \\
\indent	$\Matrix{T} = \Matrix{A} \cdot \Matrix{B} \cdot \Matrix{C}   $ \\
and so for all the points \\   
\indent	$\Vector{P_t} = \Vector{P} \cdot \Matrix{T}   $

\subsection*{Problems with verticals}
\begin{wrapfigure}{r}{80mm}
  \vspace{-35mm}
  \begin{center}
     \includegraphics[width=79mm]{Figures/GraphicsTransformationsInversion.jpg} 
  \end{center}
  \vspace{-5mm}
  \caption{Inversion of the Vertical}
  \vspace{-3mm}
  \label{fig:Inversion}
\end{wrapfigure}
The concept of ``vertical'' is missing from the above analysis, and needs attention since it is easy to invert the vertical. This will be easily observed in the trivial example of figure \ref{fig:Inversion}, where an arrow whose base is at [0,0,-l] is being observed from the origin. A transformation based on rotating about the $y$ axis first yields the correct solution. However, a transformation involving rotation about the $x$ axis first inverts the image.

\subsection*{Rotation about a general line}
A very similar problem to the viewer centered transformation concerns animation of objects in a fixed scene. Let us suppose that we want to rotate one sub-object about some line in the Cartesian space where the scene is defined. Let  the line be: $ \Vector{L} + \mu \Vector{d}$  where  $ \Vector{L} = [L_x,L_y,L_z]$ is the position vector of any point on the line and $ \Vector{d}$ is a unit direction vector along the line. We use a translation to move the origin so that it is on the line (matrix $\Matrix{A}$ but transforming the origin to $\Vector{L}$ rather than $ \Vector{C}$) followed by two rotations to make the $z$ axis coincident with the direction vector $ \Vector{d}$ (matrices $ \Matrix{B}$ and $ \Matrix{C}$). Now we can perform a rotation of the object about the $z$-axis using the standard rotation matrix $ \Matrix{R}_z$ defined previously. Finally we need to restore the coordinate system as it was, such that the viewpoint is the same as before. To do this we simply invert the transformation matrices $\Matrix{A}$ $\Matrix{B}$ and $\Matrix{C}$. As before we multiply all the individual transformation matrices together to make one matrix which is then applied to all the points. \\
\indent $\Matrix{T} = \Matrix{A} \cdot \Matrix{B} \cdot \Matrix{C} \cdot \Matrix{R}_z \cdot \Matrix{C}^{-1} \cdot \Matrix{B}^{-1}  \cdot \Matrix{A}^{-1}$  \\
and for all the points     $\Vector{P_t} = \Vector{P} \cdot \Matrix{T}$ 

Other object transformations for graphical animation are performed similarly. For example to make an object shrink we move the origin to its centre, perform a scaling and then restore the origin to its original position.

\subsection*{Projection by Matrix Multiplication}
If we use homogeneous co-ordinates then it is also possible to compute projection by multiplication by a projection matrix. Placing the centre of projection at the origin and using $z=f$ as the projection plane gives us matrix $\Matrix{M}_p$ for perspective projection. Matrix $\Matrix{M}_o$ is for orthographic projection: \\
\indent 
\begin{equation}
\nonumber
\Matrix{M}_p = 
 \left[
  \begin{array}{ c c c c }
     1 & 0 & 0 & 0 \\
     0 & 1 & 0 & 0 \\
     0 & 0 & 1 & 1/f \\
     0 & 0 & 0 & 0
  \end{array} \right] \indent
\Matrix{M}_o = 
 \left[
  \begin{array}{ c c c c }
     1 & 0 & 0 & 0 \\
     0 & 1 & 0 & 0 \\
     0 & 0 & 0 & 0 \\
     0 & 0 & 0 & 1
  \end{array} \right] 
\end{equation}
It is not immediately obvious that matrix $\Matrix{M}_p$ produces the correct perspective projection. Let us transform an arbitrary point $\Vector{V}$ with homogeneous co-ordinates $[x, y, z, 1]$ by using matrix multiplication. For the projected point $\Vector{P}$ we get:
\begin{equation}
\nonumber
\Vector{P} = \Vector{V} \cdot \Matrix{M}_p = [x, y, z, z/f]
\end{equation}
This point must be normalised into a Cartesian coordinate. To do this we divide the first three co-ordinates by the value of the fourth and we get:
\begin{equation}
\nonumber
\Vector{P_c} = [xf/z, yf/z, f, 1]
\end{equation}
which is the projected point. It is interesting to note that the projection matrix is obviously singular (it has a row of zeros) and, therefore, it has no inverse. This must be so because it is impossible to reconstruct a 3D object from its 2D projection without other information. Projection matrices can of course be combined with the other matrices. Indeed the popularity of the orthographic projection is that it simplifies the amount of calculations since the $z$ row and column fall to zero. Although a simplification applies when the perspective projection is used, there is also the need to normalise the resulting homogenous coordinates, and this adds to the computation time.

\subsection*{Homogenous coordinates}
We now take a second look at homogeneous coordinates, and their relation to vectors. Previously, we described the fourth ordinate as a scale factor, and ensured that, with the exception of the projection transformation, it was always normalised to 1.  As an alternative, we can consider the fourth ordinate as indicating a type as follows. Informally we acknowledge that a normal Cartesian coordinate is a special form of vector, which we call a position vector, and usually denote using bold face capital letters. Hence, we can say that a normalised homogenous coordinate is the same as a position vector. 
	
By contrast, if we consider a homogenous coordinate where the last ordinate is zero - $[x,y,z,0]$ - we find that we cannot normalise it in the usual way because of the divide by zero. So clearly a homogenous coordinate of this form cannot be directly associated with a point in Cartesian space. However, it still has a magnitude and direction, and hence we can consider it to be a direction vector. Thus homogenous coordinates fall into two classes, those with the final ordinate non-zero, which can be normalised into position vectors or points, and those with zero in the final ordinate which are direction vectors, or vectors in the pure sense of the word.

\begin{wrapfigure}{r}{60mm}
  \vspace{-5mm}
  \begin{center}
     \includegraphics[width=58mm]{Figures/GraphicsTransformationsLine.jpg} 
  \end{center}
  \vspace{-5mm}
  \caption{Definition of a straight line}
  \vspace{3mm}
  \label{fig:Line}
\end{wrapfigure}
Consider now how vector addition works with these definitions. If we add two direction vectors, we add the ordinates as before and we obtain a direction vector. ie:
\begin{equation}
\nonumber
[x_i,y_i,z_i,0] + [x_j,y_j,z_j,0] = [x_i+x_j, y_i+y_j, z_i+z_j,0]
\end{equation}
This is the normal vector addition rule which operates independently of Cartesian space. However, if we add a direction vector to a position vector we obtain a position vector or point:
\begin{equation}
\nonumber
[X_i,Y_i,Z_i,1] + [x_j,y_j,z_j,0] = [X_i+x_j, Y_i+y_j, Z_i+z_j,1]
\end{equation}
This is a nice result, because it ties in with our definition of a straight line in Cartesian space, which is the sum of a point and a scaled direction as shown in figure \ref{fig:Line}.

Now, consider a general affine transformation matrix. We ignore the possibility of doing perspective projection or shear, so that the last column will always be $[0,0,0,1]^T$, and the matrix will be of the form shown in figure \ref{fig:Matrix}, with the rows viewed as three direction vectors and a position vector.
\begin{figure}[h]
 \begin{center}
     \includegraphics[width=75mm]{Figures/GraphicsTransformationsMatrix.jpg} 
  \end{center}
  \vspace{-5mm}
  \caption{The structure of a space transformation matrix}
  \label{fig:Matrix}
\end{figure}

To see what the individual rows mean we consider the effect of the transformation in simple cases. 
For example take the unit vectors along the Cartesian axes eg $\UVector{i} = [1,0,0,0]$:
\begin{equation}
\nonumber
 [1,0,0,0]
 \left[
  \begin{array}{ c c c c }
     q_x & q_y & q_z & 0 \\
     r_x & r_y & r_z & 0 \\
     s_x & s_y & s_z & 0 \\
     C_x & C_y & C_z & 1
  \end{array} \right] = [q_x, q_y, q_z, 0]
\end{equation}
In other words the direction vector of the top row represents the direction in which the $x$ axis points after transformation, and similarly we find that $\UVector{j}= [0,1,0,0]$ will be transformed to direction $[r_x,r_y,r_z,0]$ and $\UVector{k} = [0,0,1,0]$ will be transformed to $[s_x,s_y,s_z,0]$. Similarly, we can see the effect of the bottom row by considering the transformation of the origin which has homogeneous coordinate $[0,0,0,1]$. This will be transformed to $[Cx,Cy,Cz,1]$.  
\begin{equation}
\nonumber
 [0,0,0,1]
 \left[
  \begin{array}{ c c c c }
     q_x & q_y & q_z & 0 \\
     r_x & r_y & r_z & 0 \\
     s_x & s_y & s_z & 0 \\
     C_x & C_y & C_z & 1
  \end{array} \right] = [C_x, C_y, C_z, 1]
  \end{equation}
  
Notice also that the zero in the last ordinate ensures that direction vectors will not be affected by the translation, whereas all position vectors will be moved by the same factor. Notice also that if we do not shear the object the three vectors $\Vector{q}$ $\Vector{r}$ and $\Vector{s}$ will remain orthogonal so that $\Vector{q}\cdot \Vector{r} = \Vector{r}\cdot \Vector{s} = \Vector{q} \cdot \Vector{s} = 0$. Unfortunately however, this analysis does not help us to determine the transformation matrix, though we will need it later in the course when we look at annimation. In general it would be more natural to assume that we know the vectors $\UVector{u}$,$\UVector{v}$, and $\UVector{w}$ which form the view centered coordinate system. To see how to write down a transformation matrix  from thses vectors we need to introduce the notion of the dot product as a projection onto a line. 
\begin{figure}
\begin{minipage}[]{8 cm}
 \includegraphics[width=49mm]{Figures/GraphicsTransformations2DDotProduct.jpg}
 \caption{The dot product as projection}
 \label{fig:2DDotProduct}
\end{minipage} 
\hspace{0.5 cm}
\begin{minipage}[]{8 cm}
 \includegraphics[width=49mm]{Figures/GraphicsTransformations2DDotProduct.jpg}
 \caption{Three dimensional point projection}
 \label{fig:3DDotProduct}
\end{minipage}
 \end{figure}
This is most readily seen in two dimensions as shown in Figure \ref{fig:2DDotProduct}.  By dropping perpendiculars from the point $\Vector{P}$ to the line defined by vector $\UVector{u}$ and vector $\UVector{v}$ we see that the distances from the origin are respectively $\Vector{P} \cdot \UVector{u}$ and $\Vector{P} \cdot \UVector{v}$. $\Vector{P} \cdot \UVector{u} = |\Vector{P}||\UVector{u}|Cos \theta = |\Vector{P}|Cos\theta$ since $\UVector{u}$ is a unit vector. Now, suppose that we wish to rotate the scene so that the new $x$ and $y$ axes were the $\UVector{u}$ and $\UVector{v}$ vectors, then the $x$ ordinate would be defined by $\Vector{P} \cdot \UVector{u}$ and the $y$ by $\Vector{P} \cdot \UVector{v}$.

The generalisation to three dimensions is shown in figure \ref{fig:3DDotProduct}, in which a point $\Vector{P}$ is transformed into the $(u,v,w)$ axis system, translated by vector $\Vector{C}$, is given by:
\begin{center}
$P^t_x = (\Vector{P} - \Vector{C}) \cdot \UVector{u}$ \\
$P^t_y = (\Vector{P} - \Vector{C}) \cdot \UVector{v}$ \\
$P^t_z = (\Vector{P} - \Vector{C}) \cdot \UVector{w}$ 
\end{center}
Expressing this as a transformation matrix we get:
\begin{equation}
\nonumber
 [P^t_x,P^t_y,P^t_z,1] = [P_x, P_y, P_z, 1]
 \left[
  \begin{array}{ c c c c }
     u_x & v_x & w_x & 0 \\
     u_y & v_y & w_y & 0 \\
     u_z & v_z & w_z & 0 \\
     -\Vector{C} \cdot \UVector{u} & -\Vector{C} \cdot \UVector{v} & -\Vector{C} \cdot \UVector{w} & 1
  \end{array} \right] 
\end{equation}
So now by maintaining values of $\UVector{u}$, $\UVector{v}$, $\UVector{w}$ and $\UVector{w}$ throughout an animation sequence, for example by adjusting their values in response to mouse or joystick commands, we can simply write down the correct scene transformation matrix for viewing the virtual world from the correct position.
 
Finally we will derive the matrix used for a view centered transformation with the viewer at point $\Vector{C}$ and looking in direction $\Vector{d}$ by finding the new axis system $\Vector{u}$, $\UVector{v}$, $\UVector{w}$, and then deducing the transformation matrix. The direction vector for viewing is $\Vector{d} = [d_x,d_y,d_z]$ and this must lie along the $\UVector{w}$ direction, so $\UVector{w} = \Vector{d}/|\Vector{d}|$. We first find any two vectors, $\Vector{p}$ and $\Vector{q}$,which have the same directions as $\Vector{u}$ and $\Vector{v}$, but do not necessarily have unit length. We can constrain the system to preserve horizontals and verticals in two ways:
(i) Vector $\Vector{p}$ will be in the direction of the new $x$-axis, so to preserve the horizontal, we choose: $p_y = 0$,
and (ii) Vector $\Vector{q}$ will be the new $y$ axis (vertical) and should have a positive $y$ component (so that the picture is not upside down) so we choose (arbitrarily): $q_y = 1$.
Substituting our constraints in the Cartesian components we get: \\
\indent	$\Vector{p} = [p_x,0,p_z]$	\indent and	\indent $\Vector{q} = [q_x,1,q_z]$ \\
Now we know that, in a left hand axis system: \\
\indent	$\UVector{k} = \UVector{i} \times \UVector{j}$	so therefore we can write:	$\Vector{d} = \Vector{p} \times \Vector{q}$ \\
since we have not as yet constrained the magnitude of $\Vector{p}$. Evaluating the cross product we get three Cartesian equations: \\
\indent	$d_x = p_y q_z - p_z q_y	\indent d_y = p_z q_x - p_x q_z \indent 	d_z = p_x q_y - p_y q_x$ \\
Substituting the values $p_y = 0$ and $q_y = 1$ these equations simplify to \\
\indent	$d_x = -p_z	\indent d_y = p_z q_x - p_x q_z \indent 	d_z = p_x$ \\
Thus we have solved for vector $\Vector{p} = [d_z,0,-d_x]$.
To solve for $\Vector{q}$ we need to express the condition that $\Vector{p}$ and $\Vector{q}$ are orthogonal and so have zero dot product, whence: \\
\indent $\Vector{p} \cdot \Vector{q} = d_z q_x + 0 - d_x q_z = 0$	\indent thus \indent $q_z = d_z q_x / d_x$ \\
and from the cross product already evaluated:	\\
\indent $d_y = p_z q_x - p_x q_z     =   - d_x q_x - d_z q_z     =   - d_x q_x - d_z^2 q_x/d_x $ \\
so \indent $q_x = -d_y d_x/(d_x^2 + d_z^2)$ \\
and	$\Vector{q} = (-d_yd_x/(d_x^2 + d_z^2), 1, d_yd_z/(d_x^2 + d_z^2))$ \\
finally  we have that:	$\UVector{u} = \Vector{p}/|\Vector{p}|$ \indent and \indent	$\UVector{v} = \Vector{q}/|\Vector{q}|$ \\ 
Thus we can deduce the whole of the transformation matrix. 


%\newpage
%\subsection*{Equations for the Slides Only}
%$
%[d_x, d_y, d_z] =
% \begin{array}{ | c c c | }
%     \UVector{i} & \UVector{j} & \UVector{k}  \\
%     p_x & 0 & p_z  \\
%     q_x & 1 & q_z 
%  \end{array}  \\
%$
%\indent $d_x = - p_z$ \\
%\indent $d_y = p_zq_x - p_x q_z$ \\
%\indent $d_z = p_x$ \\




\end{document}