\documentclass[a4paper,11pt]{article}

% Definitions for the document
\def \Course {Interactive Computer Graphics }
\def \LectureNo {1}
% 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: Three Dimensional graphics: Projections and Transformations}

\subsection*{Device Independence}
\begin{wrapfigure}{r}{105mm}
  \vspace{-5mm}
  \begin{center}
     \includegraphics[width=103mm]{Figures/Graphics3DNormalisation.jpg} 
  \end{center}
  \vspace{-5mm}
  \caption{Normalisation transformation}
  \vspace{-3mm}
  \label{fig:Normalisation}
\end{wrapfigure}
We will start with a brief discussion of two dimensional drawing primitives. At the lowest level of an operating system we have device dependent graphics methods such as:\\
\indent	SetPixel(XCoord,YCoord,Colour);\\
\indent	DrawLine(xs,ys,xf,yf);\\
which draw objects using pixel coordinates. However it is clearly desirable that we create any graphics application in a device independent way.  If we can do this then we can re-size a picture, or transport it to 
a different operating system and it will fit exactly in the window where we place it.  Many graphics APIs provide this facility, and it is a straightforward matter to implement it using a world coordinate system. This defines the coordinate values to be applied to the window on the screen where the graphics image will be drawn. Typically it will use a method of the kind:\\
\indent	SetWindowCoords(Wxmin,Wymin,Wxmax,Wymax);\\
WXMin etc are real numbers whose units are application dependent. If the application is to produce a visualisation of a house then the units could be meters, and if it is to draw accurate molecular models the units will be $\mu m$. The application program uses drawing primitives that work in these units, and converts the numeric values to pixels just before the image is rendered on the screen. This makes it easy to transport it to other systems or to upgrade it when new graphics hardware becomes available. There may be other device characteristics that need to be accounted for to achieve complete device independence, for example aspect ratios.

In order to implement a world coordinate system we need to be able to translate between world coordinates and the device or pixel coordinates.  However, we do not necessarily know what the pixel coordinates of a window are, since the user can move and resize it without the program knowing. The first stage is therefore to find out what the pixel coordinates of a window are, which is done using an enquiry procedure of the kind:\\
\indent	GetWindowPixelCoords(Dxmin, Dymin, Dxmax, Dymax)\\
In the Windows API this procedure is called GetClientRect. Having established both the world and device coordinate systems, it is possible to define a normalisation process to compute the pixel coordinates from the world coordinates. This is done by simple ratios as shown in Figure \ref{fig:Normalisation} . For the X direction:
\begin{equation}
\nonumber
\indent	\frac{(X_w-W_{xmin})}{(W_{xmax}-W_{xmin})}  =  \frac{(X_d - D_{xmin})}{(D_{xmax}-D_{xmin})}\\
\end{equation}
Rearranging, and applying the same idea to the Y direction yields a pair of simple linear equations equations:
\begin{center}
 $X_d = A X_w + B$\\
 $Y_d = C Y_w + D$\\
\end{center}
where the four constants $A$,$B$,$C$ and $D$ define the normalisation between the world coordinate system and the window pixel coordinates. Whenever a window is re-sized it is necessary to re-calculate the constants
$A$,$B$,$C$ and $D$.

\subsection*{Graphical Input}
The most important input device is the mouse, which records the distance moved in the $X$ and $Y$ directions. In the simplest form it provides at least three pieces of information: the $x$ distance moved, the $y$ distance moved and the button status. The mouse causes an interrupt every time it is moved, and it is up to the system software to keep track of the changes. Note that the mouse is not connected with the screen in any way. Either the operating system or the application program must achieve the connection by drawing the visible marker. The operating system must share control of the mouse with the application, since it needs to act on mouse actions that take place outside the graphics window. For instance, processing a menu bar or launching a different application. It therefore traps all mouse events (ie changes in position or buttons) and informs the program whenever an event has taken place using a "callback procedure".  The application program must, after every action carried out, return to the callback procedure (or event loop) to determine whether any mouse action (or other event such as a keystroke) has occurred. The callback is the main program part of any application, and, in simplified pseudo code, looks like this:
\begin{tabbing}
\indent \= \textbf{while} (executing) \textbf{do} \\
\> \{ \= \textbf{if} (menu event) ProcessMenuRequest(); \\
\>\>  \textbf{if} (mouse event) \\
\>\>  \{	\= GetMouseCoordinates(); \\
\>\>\>     GetMouseButtons(); \\
\>\>\>     PerformMouseProcess(); \\
\>\>  \}\\
\>\>  \textbf{if} (window resize event) RedrawGraphics(); \\
\> \} \\
\end{tabbing}
The procedure ProcessMenuRequest  will be used to launch all the normal actions, such as save and open and quit, together with all the application specific requests. The procedures GetMouseCoordinates and PerformMouseProcess  will be used by the application writer to create whatever effect is wanted, for example, moving an object with the mouse. This may well involve re-drawing the graphics. If the window is re-sized then the whole picture will be re-drawn.

\subsection*{3-Dimensional Objects Bounded by Planar Polygons (Facets)}
Most graphical scenes are made up of planar facets. Each facet is an ordered set of 3D vertices, lying on one plane, which form a closed polygon. The data describing a facet are of two types. First, there is the numerical data which is a list of 3D points, ($3 \times N$ numbers for $N$ points), and secondly, there is the topological data which describes how points are connected to form edges and facets. 

\subsection*{Projections of Wire-Frame Models}
\begin{wrapfigure}{r}{95mm}
  \vspace{-15mm}
  \begin{center}
     \includegraphics[width=90mm]{Figures/Graphics3DPlanarProjection.jpg} 
  \end{center}
  \vspace{-5mm}
  \caption{Planar Projection}
  \vspace{-5mm}
  \label{fig:PlanarProjection}
\end{wrapfigure}
Since the display device is only 2D, we have to define a transformation from the 3D space to the 2D surface of the display device. This transformation is called a projection. In general, projections transform an $n$-dimensional space into an $m$-dimensional space where $m<n$.  Projection of an object onto a surface is done by selecting a viewpoint and then defining projectors or lines which join each vertex of the object to the viewpoint. The projected vertices are placed where the projectors intersect the projection surface as shown in Figure \ref{fig:PlanarProjection}. 

The most common (and simplest) projections used for viewing 3D scenes use planes for the projection surface and straight lines for projectors. These are called planar geometric projections. A rectangular window can be defined defined on the plane of projection which can be mapped into the device window as described above. Once all the vertices of an object have been projected it can be rendered. An easy way to do this is drawing all the projected edges. This is called a wire-frame representation. Note that for such rendering the topological information only specifies which points are joined by edges. For other forms of rendering we also need to define the object faces. 

There are two common classes of planar geometric projections. Parallel projections use parallel projectors, perspective projections use projectors which pass through one single point called the viewpoint. In order to minimise confusion in dealing with a general projection problem, we can standardise the plane of projection by making it always parallel to the $z=0$ plane, (the plane which contains the $x$ and $y$ axis). This does not limit the generality of our discussion because if the required projection plane is not parallel to the $z=0$ plane then we can use a coordinate transformations in 3D and make so. We will see shortly how to do this. We shall restrict the viewed objects to be in the positive half space $(z > 0)$, therefore the projectors starting at the vertices will always run in the negative $z$ direction.

\subsection*{Parallel Projections}
\begin{wrapfigure}{r}{55mm}
  \vspace{-15mm}
  \begin{center}
     \includegraphics[width=50mm]{Figures/Graphics3DOrthographicProjections.jpg} 
  \end{center}
  \vspace{-5mm}
  \caption{Orthographic Projections}
  \vspace{-20mm}
  \label{fig:OrthographicProjections}
\end{wrapfigure}
In a parallel projection all the projectors have the same direction $\Vector{d}$, and the viewpoint can be considered to be at infinity. For a vertex $\Vector{V}=[V_x, V_y, V_z]$ the projector is defined by the parametric line equation: \\
\indent \indent $\Vector{P}  =   \Vector{V}  + \mu \Vector{d}$\\
In orthographic  projection the projectors are perpendicular to the projection plane, which we usually define as $z=0$. In this case the projectors are in the direction of the $z$ axis and:
\begin{tabbing}
\indent \indent	\= $\Vector{d} = [0,0,-1]$ \\	
and so \>	$P_x = V_x$	\\
and	\>$P_y = V_y$
\end{tabbing}
which means that the $x$ and $y$ co-ordinates of the projected vertex are equal to the $x$ and $y$ co-ordinates 
of the vertex itself and no calculations are necessary. Some examples of a wireframe cube drawn in orthographic projection are shown in Figure \ref{fig:OrthographicProjections}. 

If the projectors are not perpendicular to the plane of projection then the projection is called oblique. The projected vertex intersects the $z=0$ plane where the $z$ component of the $\Vector{P}$ vector is equal to zero, therefore:
\begin{tabbing}
\indent \indent \= $P_z = 0 = V_z + \mu d_z$ \\
so              \> $\mu = - V_z/d_z $ \\
and we can use this value of $\mu$ to compute: \\
                \> $P_x = V_x + \mu d_x  =  V_x - d_xV_z/d_z$ \\
and             \> $P_y = V_y + \mu d_y  =  V_y - d_yV_z/d_z$
\end{tabbing}
These projections are similar to the orthographic projection with one or other of the dimensions scaled. They are not often used in practice.

\subsection*{Perspective Projections}
In perspective projection, all the rays pass through one point in space, the centre of projection as shown in figure 2. If the centre of projection is behind the plane of projection then the orientation of the image is the same as the 3D object. By contrast, in a pin hole camera it is inverted. To calculate perspective projections we adopt a canonical form in which the centre of projection is at the origin, and the projection plane is placed at a constant $z$ value, $z=f$. This canonical form is illustrated in Figure \ref{fig:CanonicalProjection}. The projection of a 3D point onto the $z=f$ plane is calculated as follows. If we are projecting the point $\Vector{V}$ then the projector has equation:  
\begin{tabbing}
\indent \indent \= $\Vector{P} = \mu \Vector{V}$ \\
Since the projection plane has equation $z=f$, it follows that, at the point of intersection:   \\
                \> $f = \mu V_z$ \\
If we write $\mu_p = f/ V_z$ for the intersection point on the plane of projection then: \\
                \> $P_x = \mu_p V_x = fV_x/V_z$ \\ 
and             \> $P_y = \mu_p V_y = fV_y/V_z$ 
\end{tabbing}

The factor $\mu_p$ is called the foreshortening factor, because the further away an object is, the larger $V_z$ and the smaller is its image. Some examples of the perspective projection of a cube are shown in figure \ref{fig:PerspectiveProjections}.
\begin{figure}[ht]
\begin{minipage}[b]{0.55\linewidth}
\centering
\includegraphics[height=55mm]{Figures/Graphics3DCanonicalProjection.jpg}
\caption{Canonical form for perspective projection}
\label{fig:CanonicalProjection}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.4\linewidth}
\centering
\includegraphics[height=55mm]{Figures/Graphics3DPerspectiveProjections.jpg}
\caption{Perspective projection of a cube}
\label{fig:PerspectiveProjections}
\end{minipage}
\end{figure}

\subsection*{Space Transformations}
The introduction of canonical forms for perspective and orthographic projection simplifies their computation. However, in cases where we wish to move around a graphical scene and view if from any particular point, we must be able to transform the coordinates of the scene, such that the view direction is along the z axis and (for perspective projection) the viewpoint is at the origin. In general we would like to change the coordinates of every point in the scene, such that some chosen viewpoint $\Vector{C} = [C_x,C_y,C_z]$ is the origin and some view direction $\Vector{d} = [d_x,d_y,d_z]$ is the $Z$ axis. This new coordinate system in which the scene is to be defined is sometimes called the ``view centered'' coordinate system and is shown in Figure \ref{fig:ViewCentered}.

\begin{figure}[htp]
\centering
\includegraphics[width=120mm]{Figures/Graphics3DViewCentered.jpg}
\caption{View centered coordinate transformation}
\label{fig:ViewCentered}
\end{figure}
Frequently, we may also want to transform the points of a graphical scene for other purposes such as generation of special effects like rotating or shrinking objects. Transformations of this kind are achieved by multiplying every point of the scene by a transformation matrix. Unfortunately however, we cannot perform a general translation using normal Cartesian coordinates, and for that reason we now introduce a system called homogeneous 
coordinates.  Three dimensional points expressed in homogeneous form have a fourth ordinate: \\
\indent \indent $\Vector{P} = [p_x, p_y, p_z,s]$ \\
The fourth ordinate is a scale factor, and conversion to Cartesian form is achieved by dividing it into the other ordinates, so: \\
\indent \indent $[p_x, p_y, p_z,s]$  \indent   has Cartesian coordinate equivalent  \indent  $[p_x/s, p_y/s, p_z/s]$ \\ 
In most cases $s$ will be 1. The point of introducing homogenous coordinates is to allow us to translate the points of a scene by using matrix multiplication.
\begin{equation}
\nonumber
 [x,y,z,1] 
 \left[
  \begin{array}{ c c c c }
     1   & 0   & 0   & 0 \\
     0   & 1   & 0   & 0 \\
     0   & 0   & 1   & 0 \\
     t_x & t_y & t_z & 1
  \end{array} \right] = [x+t_x, y+t_y, x+t_z, 1]
\end{equation}
The matrix for scaling a graphical scene is also easily expressed in homogenous form:
\begin{equation}
\nonumber
 [x,y,z,1] 
 \left[
  \begin{array}{ c c c c }
     s_x & 0   & 0   & 0 \\
     0   & s_y & 0   & 0 \\
     0   & 0   & s_z & 0 \\
     0   & 0   & 0   & 1
  \end{array} \right] = [s_x x, s_y y, s_z z, 1]
\end{equation}
Notice that these two transformations are not commutative, and it is essential that they are carried out in the correct order. Figure \ref{fig:Order} illustrates the problem for a simple picture.

\begin{figure}[h]
\centering
\includegraphics[width=120mm]{Figures/Graphics3DOrder.jpg}
\caption{The importance of the order in which transfrmations are done}
\label{fig:Order}
\end{figure}

Rotation has to be treated differently since we need to specify an axis. The matrices for rotation about the three Cartesian axes are: 
\begin{center}
$
\Matrix{R}_x =
 \left[
  \begin{array}{ c c c c }
     1 & 0          & 0         & 0 \\
     0 & Cos\theta  & Sin\theta & 0 \\
     0 & -Sin\theta & Cos\theta & 0 \\
     0 & 0          & 0         & 1
  \end{array} \right]
\Matrix{R}_y =
 \left[
  \begin{array}{ c c c c }
     Cos\theta & 0 & -Sin\theta & 0 \\
     0         & 1 &  0         & 0 \\
     Sin\theta & 0 & Cos\theta  & 0 \\
     0         & 0 & 0          & 1
  \end{array} \right]
\Matrix{R}_z =
 \left[
  \begin{array}{ c c c c }
     Cos\theta  & Sin\theta & 0 & 0 \\
     -Sin\theta & Cos\theta & 0 & 0 \\
     0          & 0         & 1 & 0 \\
     0          & 0         & 0 & 1
  \end{array} \right]
$
\end{center}
Some care is required with the signs. The above formulation obeys the conventions of a left hand axis system. That is, if the positive $y$-axis is taken as vertical, and the positive $x$-axis horizontal to the right, the positive $z$-axis is into the page. In these cases, rotation is in a clockwise direction when viewed from the positive side of the axis, or vice versa, anti-clockwise when viewed from the negative side of the axis. The derivation of the $\Matrix{R}_z$ matrix is as follows: \\
\begin{minipage}[b]{12 cm}
\begin{tabular}{ r l }
$[x,y]$ & = $[\;rCos\phi \;,\; rSin\phi\;]$ \\
$[x_t, y_t]$ & $= [\;rCos(\phi+\theta) \;,\; rSin(\phi+\theta)\;]$ \\
 & $= [\;rCos\phi Cos\theta-rSin\phi Sin\theta \;,\; rCos\phi Sin\theta + rSin\phi Cos\theta\;]$ \\
 & $= [\;xCos\theta-ySin\theta \;,\; xSin\theta + yCos\theta\;]$ \\
 & $ = [x,y] 
 \left[
  \begin{array}{ c c }
     Cos\theta  & Sin\theta \\
     -Sin\theta & Cos\theta
  \end{array} \right] $
 \end{tabular} \\
\end{minipage}
\begin{minipage}[b]{4.5 cm}
   \includegraphics[width=45mm]{Figures/Graphics3DRotate.jpg} 
\end{minipage} \\
The others may be derived similarly. 

Inversions of the transformation matrices can be computed easily, without recourse to Gaussean elimination, by considering the meaning of each transformation. For scaling, we substitute $1/s_x$ for $s_x$, $1/s_y$ 
for $s_y$ and $1/s_z$ for $s_z$ to invert the matrix. 
\begin{center}
 $
 \left[
  \begin{array}{ c c c c }
     s_x & 0   & 0   & 0 \\
     0   & s_y & 0   & 0 \\
     0   & 0   & s_z & 0 \\
     0   & 0   & 0   & 1
  \end{array} \right] $has\;inversion$
 \left[
  \begin{array}{ c c c c }
     1/s_x & 0     & 0     & 0 \\
     0     & 1/s_y & 0     & 0 \\
     0     & 0     & 1/s_z & 0 \\
     0     & 0     & 0     & 1
  \end{array} \right] 
$
\end{center} 
For translation we substitute $-t_x$ for $t_x$, $-t_y$ for $t_y$ and $-t_z$ for $t_z$. 
\begin{center}
 $
 \left[
  \begin{array}{ c c c c }
     1   & 0   & 0   & 0 \\
     0   & 1   & 0   & 0 \\
     0   & 0   & 1   & 0 \\
     t_x & t_y & t_z & 1
  \end{array} \right] $has\;inversion$
 \left[
  \begin{array}{ c c c c }
     1    & 0    & 0    & 0 \\
     0    & 1    & 0    & 0 \\
     0    & 0    & 1    & 0 \\
     -t_x & -t_y & -t_z & 1
  \end{array} \right] 
$
\end{center}
For the rotation matrices we note that:
\begin{center}
 $Cos(-\theta) = Cos(\theta)$ and $Sin(-\theta) = -Sin(\theta)$
\end{center}
Hence to invert the matrix we simply change the sign of the $Sin$ terms, for example:
\begin{center}
 $
 \left[
  \begin{array}{ c c c c }
     Cos\theta  & Sin\theta & 0 & 0 \\
     -Sin\theta & Cos\theta & 0 & 0 \\
     0          & 0         & 1 & 0 \\
     0          & 0         & 0 & 1
  \end{array} \right] $has\;inversion$
 \left[
  \begin{array}{ c c c c }
     Cos\theta & -Sin\theta & 0 & 0 \\
     Sin\theta & Cos\theta  & 0 & 0 \\
     0         & 0          & 1 & 0 \\
     0         & 0          & 0 & 1
  \end{array} \right] 
$
\end{center}


\end{document}