Notes.tex

\documentclass[11pt,fleqn]{article}

%% This first part is the document header, which you don't need to edit.
%% Scroll down to \begin{document} 

\usepackage[latin1]{inputenc}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}

\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\begin{document}
\begin{center}
    {\Huge
        Computer Graphics Notes % e.g. Problem sheet 1
    }\\
    Ethan Cheng % e.g. Clive Newstead, Saturday 27th June 2015
\end{center}

\begin{abstract} \noindent
    Computer Graphics Programming, taught by Jon-Alf Dyrland-Weaver
\end{abstract}

\tableofcontents

\newpage
\section{Feb. 3, 2016 - Image File Formats}
We will be choosing an easy-to-work-with file format for images we're generating...
because this a graphics course. We will be making graphics. That are images. Yes.

\subsection{Compressed vs Uncompressed}
\begin{itemize}
    \item Compressed
        \begin{itemize}
            \item Performs an algorithm on an uncompressed image to reduce file size
            \item Smaller
            \item Often less information
        \end{itemize}
    \item Uncompressed
        \begin{itemize}
            \item Full map of pixel values
            \item Raw data
        \end{itemize}
\end{itemize}

\subsubsection{Compressed Image Formats}
\begin{itemize}
    \item png
    \item gif
    \item jpeg/jpg
\end{itemize}

\subsubsection{Uncompressed Image Formats}
\begin{itemize}
    \item bmp (Bitmap)
    \item tiff
    \item svg
    \item raw
\end{itemize}

\subsection{Lossy vs Lossless}
\begin{itemize}
    \item Lossy
        \begin{itemize}
            \item Compression algorithms lose some of the original information
        \end{itemize}
    \item Lossless
        \begin{itemize}
            \item Contains all the original information
        \end{itemize}
\end{itemize}

All \textbf{uncompressed} image formats are lossless. Duh. \textbf{JPEG} files are
lossy compressed. However, \textbf{PNG} files are lossless compressed.

\subsection{Run Length Encoding}
We can very easily make a lossless compression algorithm:
\begin{verbatim}
12B: GGGGGYYYRRRR
6B:  5G3Y4R
\end{verbatim}

However, this is a bad compression algorithm for real-life images (i.e. from a
camera), since adjacent pixels will almost NEVER be the same. This is, however, what
the PNG format uses, and is used for flat, ``minimalist'' computer generated images.

\subsection{Raster vs Vector}
\begin{itemize}
    \item Raster
        \begin{itemize}
            \item Image is represented as a grid of pixels
        \end{itemize}
    \item Vector
        \begin{itemize}
            \item Image is represented as a list of drawing instructions
            \item Scale well
            \item SVG stands for ``Scalable Vector Graphics''
        \end{itemize}
\end{itemize}

\subsection{So... what are we using? netpbm!}
\texttt{netpbm} is a very simple, raster, lossless, uncompressed format. It is
extremely simple: space separated values of triplet integers from [0,255].

\newpage
\section{Feb. 4, 2016 - Yay! NetPBM!}

\subsection{NetPBM File Format}

NetPBM files are \texttt{.ppm}, plaintext files, interpretted as images.

\subsubsection{File Header}
\begin{itemize}
    \item File Header : \texttt{P3}
    \item \texttt{XRES} : x-resolution as an integer value of pixels
    \item \texttt{YRES} : y-resolution as an integer value of pixels
    \item \texttt{MAX\_COLOR\_VALUE} : Maximum color value of a pixel
\end{itemize}

\subsubsection{File Data}
\begin{itemize}
    \item $R_n$ : ASCII representation of red value of pixel $n$ (i.e. 255)
    \item $G_n$ : ASCII representation of green value of pixel $n$ (i.e. 255)
    \item $B_n$ : ASCII representation of blue value of pixel $n$ (i.e. 255)
\end{itemize}

These values can be separated by \textbf{any} type of whitespace:
\begin{itemize}
    \item space
    \item tab
    \item newline
\end{itemize}

Here is a sample file: \texttt{yellow.ppm} (a 5x5 pixel square of yellow):

\begin{verbatim}
P3
5 5
255 255 0 255 255 0 255 255 0 255 255 0 255 255 0
255 255 0 255 255 0 255 255 0 255 255 0 255 255 0
255 255 0 255 255 0 255 255 0 255 255 0 255 255 0
255 255 0 255 255 0 255 255 0 255 255 0 255 255 0
255 255 0 255 255 0 255 255 0 255 255 0 255 255 0
\end{verbatim}

\newpage
\section{Feb. 5 - 10, 2016 - Bresenham's Line Algorithm}

\subsection{Computer Graphics Basics: The Octal Cartesian Plane}
In math, we usually split the Cartesian Plane into \textbf{quadrants}, along
intervals of $90^{\circ}$, going radially.

In computer graphics, it is much easier to subdivide the quadrants into
\textbf{octants}, along intervals of $45^{\circ}$, going radially.

\subsection{Computer Graphics Basics: Lines with Pixels}
In computer graphics, drawing a straight line is a bit strange. Because pixels are
integer values, we don't care about floating point numbers. This is why graphics
cards exist: they are processors that only operate with integers, and are well
optimized and fast.

What about drawing the line? We can come up with a few ideas:

\begin{enumerate}
    \item Pick a random point, and those that are on the line, we keep it
    \item Calculate the ``delta'' value of $x$ and $y$ based on the slope of the
        line, given by the two endpoints
    \item Using some forms of the line equations from math
    \item Some combination with some clever optimizations of the 3
\end{enumerate}

\newpage
\subsection{Plotting a line without floats}
We have our standard line equation in point--slope form. We can manipulate this to
\textbf{not} use division, which prevents floating point numbers
\begin{align*}
    y &= mx + b \\
    y &= \frac{\Delta y}{\Delta x} x + b \\
    y \Delta x &= x \Delta y + b \Delta x \\
    0 &= x \Delta y - y \Delta x + b \Delta x \\
    A &= \Delta y \\
    B &= -\Delta x \\
    C &= b \Delta x \\
    0 &= Ax + By + C = f(x, y)
\end{align*}

We end up with our standard line equation from math, which deals strictly with
INTEGER VALUES, since $x$ and $y$ are pixel values, which are integers.

We can simply evaluate $f(x,y)$, and if the result equals $0$, then $(x,y)$ is on the
line.

Let's split up the 8 octants when we consider with pixels when we use our function
$F(x,y)$

Note that we can split this into cases!

\[
    f(x,y) = Ax + By + C =
    \begin{cases}
        = 0 \rightarrow (x,y) \text{  is on the line} \\
        < 0 \rightarrow (x,y) \text{  is above the line} \\
        > 0 \rightarrow (x,y) \text{  is below the line} \\
    \end{cases}
\]

We can get the relations with the line using $B = -\Delta x$.

From this piece-wise evaluation: we only have 2 options when we plot a point from one
endpoint to another:

\begin{enumerate}
    \item $(x + 1, y + 1)$
    \item $(x + 1, y)$
\end{enumerate}

\newpage

Rather than looking at both of those, we can instead look at the midpoint $(x + 1, y
+ \frac{1}{2})$.

This gives us the following relation:

$
f(x + 1, y + \frac{1}{2}) =
\begin{cases}
    < 0 \rightarrow \text{ midpoint is above the line. Draw the lower pixel: } (x + 1, y) \\
    0 \rightarrow \text{ midpoint is on the line. Draw either pixel} \\
    > 0 \rightarrow \text{ midpoint is below the line. Draw the higher pixel: } (x + 1, y + 1)
\end{cases}
$

\subsection{Algorithm Pseudocode}

We now have our algorithm, so we can write a crude version in pseudocode, drawing a
line from $(x_0, y_0 \rightarrow (x_1, y_1)$.

\begin{verbatim}
1 : // Check if we are in quadrant I
2 : @assert(0 < m and m < 1)
3 : x = x0
4 : y = y0
5 : while (x <= x1)
6 :     plot(x, y)
7 :     // Calculate the delta using given function f()
8 :     d = f(x + 1, y + (1 / 2))
9 :     if (d > 0)
10:         y = y + 1
11:     x = x + 1
\end{verbatim}

However, on line 8, we are recalculating $d$ every single iteration of the loop. We
can bring it out of the loop. We can set the initial value:

\begin{align*}
    d &= f(x_0 + 1, y_0 + \frac{1}{2}) \\
      &= A(x_0 + 1) + B(y_0 + \frac{1}{2}) + C \\
      &= Ax_0 + A + By_0 + \frac{1}{2}B + C \\
      &= (Ax_0 + By_0 + C) + A + \frac{1}{2}B \\
      &= f(x_0, y_0) + A + \frac{1}{2}B \\
    \Delta d &= A + \frac{1}{2}B
\end{align*}

From this, we can improve our pseudocode:

\begin{verbatim}
1 : // Check if we are in quadrant I
2 : @assert(0 < m and m < 1)
3 : x = x0
4 : y = y0
5 : d = A + B / 2
6 : while (x <= x1)
7 :     plot(x, y)
8 :     if (d > 0)
9 :         y = y + 1
10:     x = x + 1
11:     d = f(x + 1, y + (1 / 2))
\end{verbatim}

This isn't very helpful, since we are still calling \verb|f()| every single
iteration. Let us make a table:

\begin{table}[!htpb]
    \centering
    \label{bresenham1}
    \begin{tabular}{c|c}
        $d < 0$ & $d > 0$ \\ \hline \\
        $x \rightarrow x + 1$, $y \rightarrow y$ & $x \rightarrow x + 1$, $y
        \rightarrow y + 1$ \\
        \texttt{f(x+1, y)} & \texttt{f(x+1, y+1)} \\
        \texttt{d = d + A} & \texttt{d = d + A + B}
    \end{tabular}
\end{table}

This let's us reduce calculating $f()$ to a simple addition.

\begin{verbatim}
1 : // Check if we are in quadrant I
2 : @assert(0 < m and m < 1)
3 : x = x0
4 : y = y0
5 : d = A + B / 2
6 : while (x <= x1)
7 :     plot(x, y)
8 :     if (d > 0)
9 :         y = y + 1
10:         d = d + B
10:     x = x + 1
11:     d = d + A
\end{verbatim}

There is one more flaw: we are dividing by 2 on line 5. We can get rid of this by
doing the following:

\begin{align*}
    d &= A + \frac{1}{2}B \\
    2d &= 2A + B \\
\end{align*}

This gives us $2d$ instead of $d$. We can change our incrementor statements:

\begin{align*}
    d &= d + A &&\rightarrow 2d &&&= 2d + 2A \\
    d &= d + A + B &&\rightarrow 2d &&&= 2d + 2A + 2B
\end{align*}

We can patch our implementation:

\begin{verbatim}
1 : // Check if we are in quadrant I
2 : @assert(0 < m and m < 1)
3 : x = x0
4 : y = y0
5:  A = y1 - y0
6:  B = -(x1 - x0)
7 : d = 2A + B
8 : while (x <= x1)
9 :     plot(x, y)
10:     if (d > 0)
11:         y = y + 1
12:         d = d + 2B
13:     x = x + 1
14:     d = d + 2A
\end{verbatim}

This gives us a valid algorithm for octant 1. Let us extend this to octant 2:

\subsubsection{Extending the algorithm to other quadrants}
We now have a new rule for $m$: $1 < m$. Like in octant 1, where we had:

\begin{enumerate}
    \item $(x + 1, y + 1)$
    \item $(x + 1, y)$
\end{enumerate}

In octant 2, we have:

\begin{enumerate}
    \item $(x, y + 1)$
    \item $(x + 1, y + 1)$
\end{enumerate}

This gives us a midpoint of $(x + \frac{1}{2}, y + 1)$, giving us an initial point of
$f(x_0 + \frac{1}{2}, y_0 + 1))$, and $d = \frac{1}{2}A + B$.

Using this, we can adapt our algorithm to octant 2:

\begin{verbatim}
1 : // Check if we are in quadrant I
2 : @assert(0 < m and m < 1)
3 : x = x0
4 : y = y0
5:  A = y1 - y0
6:  B = -(x1 - x0)
7 : d = A + 2B
8 : while (y <= y1)
9 :     plot(x, y)
10:     if (d < 0)
11:         x = x + 1
12:         d = d + 2A
13:     y = y + 1
14:     d = d + 2B
\end{verbatim}

Octants 5 and 6 are the same as 1 and 2! Likewise, Octants 3 and 4 are the same as 7
and 8, albeit going between the pairs of pairs requires flipping the signs.

In Octant 8, we have

\begin{enumerate}
    \item $(x + 1, y - 1)$
    \item $(x + 1, y)$
\end{enumerate}

This gives us a midpoint of $(x + 1, y - \frac{1}{2})$, giving us an initial point of
$f(x_0 + 1, y - \frac{1}{2}))$, and $d = \frac{1}{2}A + B$.

\section{Feb. 23 - 24, 2016 - Matrix Math Review}

In order to implement a different method of representing a picture, we have to review
some matrix math:

\subsection{Scalar Multiplcation}

\[
    s \cdot
    \begin{bmatrix}
        a & b \\
        c & d
    \end{bmatrix}
    =
    \begin{bmatrix}
        sa & sb \\
        sc & sd
    \end{bmatrix}
\]

Simple!

\subsection{Matrix Multiplication}

Now let's move on to something harder. Matrix Multiplication must satisfy some
requirements:

Given $M_0 M_1$
\begin{itemize}
    \item $M_0 M_1 \neq M_1 M_0$
    \item The number of columns of $M_0$ must equal the number of rows in $M_1$
\end{itemize}

For instance,
\[
    \begin{bmatrix}
        a & b & c
    \end{bmatrix}
\]
has the shape $1 \times 3$. If this matrix is $M_0$, $M_1$ must have the shape $3
\times n$. For instance:

\[
    \begin{bmatrix}
        1 \\
        2 \\
        3
    \end{bmatrix}
\]

If we multiply these, we will get:

\[
    \begin{bmatrix}
        a & b & c
    \end{bmatrix} \cdot
    \begin{bmatrix}
        1 \\
        2 \\
        3
    \end{bmatrix}
    =
    \begin{bmatrix}
        1a + 2b + 3c
    \end{bmatrix}
\]

From this we see: if $M_0$ is a matrix of shape $a \times b$ and $M_1$ is a matrix of
shape $b \times c$, $M_0 \cdot M_1$ has the shape $a \times c$.

To find the $(x \times y)$th element is the product of the $x$th row of $M_0$ and the
$y$th row of $M_1$.

For practice:

\[
    \begin{bmatrix}
        a & b & c \\
        d & e & f \\
        g & h & i
    \end{bmatrix} \cdot
    \begin{bmatrix}
        1 & 4 \\
        2 & 5 \\
        3 & 6
    \end{bmatrix}
    =
    \begin{bmatrix}
        1a + 2b + 3c & 4a + 5b + 6c \\
        1d + 2e + 3f & 4d + 5e + 6f \\
        1g + 2h + 3i & 4g + 5h + 6i
    \end{bmatrix}
\]

\subsection{Multiplicative Identity Matrix}

There is a Multiplicative Identity Matrix that can have a variable shape, but must
satisfy the following conditions:

\begin{itemize}
    \item Square shape (number of rows is equal to number of columns)
    \item Diagonal values (items (n,n) for $0 \leq n \leq $Number of rows) are all 1
    \item All other values are 0
\end{itemize}

\subsection{Transforming Matrices}

\subsubsection{Scaling}

We can apply this to a simple scaling algorithm:
\[
    \begin{bmatrix}
        a & 0 & 0 & 0 \\
        0 & b & 0 & 0 \\
        0 & 0 & c & 0 \\
        0 & 0 & 0 & 1
    \end{bmatrix} \cdot
    \begin{bmatrix}
        x \\
        y \\
        z \\
        1
    \end{bmatrix} =
    \begin{bmatrix}
        ax \\
        by \\
        cz \\
        1
    \end{bmatrix}
\]

This scales the $x$, $y$, and $z$ dimensions by factors of $a$, $b$, and $c$
respectively.

\subsubsection{Translating}

To translate $(x,y,z)$ by $(a,b,c)$ WITHOUT adding the matrices (we want to keep
everything in terms of matrix multiplication.
\[
    \begin{bmatrix}
        1 & 0 & 0 & a \\
        0 & 1 & 0 & b \\
        0 & 0 & 1 & c \\
        0 & 0 & 0 & 1
    \end{bmatrix} \cdot
    \begin{bmatrix}
        x \\
        y \\
        z \\
        1
    \end{bmatrix} =
    \begin{bmatrix}
        x + a \\
        y + b \\
        z + c \\
        1
    \end{bmatrix}
\]

\subsubsection{Rotation}

To rotate a point $(x,y,z)$, we must supply a rotation axis and an angle.

Without loss of generality, let's rotate about he $z$ axis:

\begin{center}
    $(x,y,z) \rightarrow (?, ?, z)$
\end{center}

To find the two question marks, we must do some trig:
If we convert to polar, we have:
\begin{center}
    $x = r\cos(\phi)$ \\
    $y = r\sin(\phi)$
\end{center}

If we rotate an angle $\theta$, we rotate to:
\begin{center}
    $x_0 = r\cos(\phi + \theta)$ \\
    $y_0 = r\sin(\phi + \theta)$
\end{center}

Expanding this out with angle addition formulas, we have:

\begin{align*}
    x_0 &= r\cos(\phi + \theta) \\
        &= r\cos(\phi)\cos(\theta) - r\sin(\phi)\sin(\theta) \\
        &= x\cos(\theta) - y\sin(\theta)
\end{align*}

\begin{align*}
    y_0 &= r\sin(\phi + \theta) \\
        &= r\sin(\phi)\cos(\theta) + r\cos(\phi)\sin(\theta) \\
        &= y\cos(\theta) + x\sin(\theta)
\end{align*}

\section{Feb. 25, 2016 - Rotation Continued}

Now that we have our identities for rotation for the $z$ axis, we can convert it to
rotation about the $x$ and $y$ axis:

\begin{itemize}
    \item \textbf{x-axis} \\
        \[
            \begin{bmatrix}
                1 & 0 & 0 & 0 \\
                0 & \cos\theta & -\sin\theta & 0 \\
                0 & \sin\theta & \cos\theta & 0 \\
                0 & 0 & 0 & 1
            \end{bmatrix}
        \] \\
        $(x,y,z) \rightarrow (x, y\cos\theta - z\sin\theta, y\sin\theta + z\cos\theta)$

    \item \textbf{y-axis} \\
        \[
            \begin{bmatrix}
                \cos\theta & 0 & -\sin\theta & 0 \\
                0 & 1 & 0 & 0 \\
                \sin\theta & 0 & \cos\theta & 0 \\
                0 & 0 & 0 & 1
            \end{bmatrix}
        \]\\
        $(x,y,z) \rightarrow (x\cos\theta - z\sin\theta, y, x\sin\theta + z\cos\theta)$

    \item \textbf{z-axis} \\
        \[
            \begin{bmatrix}
                \cos\theta & -\sin\theta & 0 & 0 \\
                \sin\theta & \cos\theta & 0 & 0 \\
                0 & 0 & 1 & 0 \\
                0 & 0 & 0 & 1
            \end{bmatrix}
        \]\\
        $(x,y,z) \rightarrow (x\cos\theta - y\sin\theta, x\sin\theta + y\cos\theta, z)$
\end{itemize}

\subsection{Applying Transformations}

\textit{Note: The transformations we are doing are called} \textbf{affined
transformations}.


Let $E_0$ be our edge matrix, which we have added edges into. Let $T$ be our
translate matrix, $S$ be our scale matrix, and $R$ be our rotate matrix.

$
T \cdot E_0 = E_1 \text{ Translated} \\
S \cdot E_1 = E_2 \text{ Translated, then Scaled} \\
R \cdot E_2 = E_3 \text{ Translated, then Scaled, then Rotated}
$

Note that $E_3 = R \cdot S \cdot T \cdot E_0$. Matrix multiplication is not
commutative, but it \textbf{is} \textit{associative}! We can simply group the
transformations before applying them on $E_0$, which would improve efficiency.
Because our translation matrices are $4 \times 4$, but $E_0$ is $4 \times n$ where
$n$ is an arbitrary number, if $n$ is large, multiplying by a $4 \times n$ 3 times is
quite consuming.

$(R \cdot S \cdot T) \cdot E_0$ will only multiply by a $4 \times n$ once, saving
runtime and resources.

\section{Mar. 7, 2016 - Parametric Equations}

Given $x$ and $y$ equations, we can let $x$ and $y$ be equations of $t$ to create
parametric equations.

Given our line equation that takes $(x_0, y_0)$ to $(x_1, y_1)$, we can create
parametric equations:

\begin{align*}
    f(t) &= x_0 + t(\Delta x) \\
    g(t) &= y_0 + t(\Delta y)
\end{align*}

We can simply define parametrics for a circle and draw the circle with iterations of
a small amount to iterate $t$:

\begin{verbatim}
double x(double t) {
    return 25 * cos(2 * M_PI * t) + XRES / 2;
}

double y(double t) {
    return 25 * sin(2 * M_PI * t) + YRES / 2;
}

double step, x0, y0, x, y;

double CEILING = 1.0;

x0 = x(0);
y0 = y(0);

for (double t = step; t < CEILING; t += step) {
    x = x(t);
    y = y(t);

    draw_line(x0, y0, x, y);

    x0 = x;
    y0 = y;
}

\end{verbatim}

However, due to floating point imprecision, we should make \texttt{CEILING} a bit
higher than 1.0, so a value like $1.0001$.

\section{Mar. 8, 2016 - Splining}

\begin{center}
    Hermite Curves
\end{center}

Given $f(t) = at^3 + bt^2 + ct + d$, we can find its derivative $f^{'}(t) = 3at^2 +
2bt + c$. When $t = 0$, $f(t) = d$ and $f^{'}(t) = c$. When $t = 1$, $f(t) = a + b +
c + d$ and $f^{'}(t) = 3a + 2b + c$.

$
\begin{bmatrix}
    0 & 0 & 0 & 1 \\
    1 & 1 & 1 & 1 \\
    0 & 0 & 1 & 0 \\
    3 & 2 & 1 & 0
\end{bmatrix}
\times
\begin{bmatrix}
    a \\
    b \\
    c \\
    d
\end{bmatrix}
=
\begin{bmatrix}
    d \\
    a + b + c + d \\
    c \\
    3a + 2b + c
\end{bmatrix}
=
\begin{bmatrix}
    P_0 \\
    P_1 \\
    R_0 \\
    R_1
\end{bmatrix}
$ \\

To obtain
$
\begin{bmatrix}
    a \\
    b \\
    c \\
    d
\end{bmatrix}
$, We need the inverse matrix of
$
\begin{bmatrix}
    0 & 0 & 0 & 1 \\
    1 & 1 & 1 & 1 \\
    0 & 0 & 1 & 0 \\
    3 & 2 & 1 & 0
\end{bmatrix}
$
which just so happens to be:
$
\begin{bmatrix}
    2 & -2 & 1 & 1 \\
    -3 & 3 & -2 & -1 \\
    0 & 0 & 1 & 0 \\
    1 & 0 & 0 & 0
\end{bmatrix}
$

\subsection{Bezier Curves}

We need 4 endpoints! There are some cool animations on wikipedia that can explain: \\

\begin{center}
    \texttt{https://en.wikipedia.org/wiki/Bezier\_curve}.
\end{center}

\section{Mar. 10, 2016 - Bezier Curves Continued}

A linear Bezier Curve from $P_0$ to $P_1$ is denoted by the parametric equation
\begin{center}
    $P(t) = (1-t)P_0 + tP_1$
\end{center}

A quadratic Bezier Curve with 3 points $P_0$ to $P_2$, with $P_1$ doing the
``tugging'' is denoted by the parametric equation:
\begin{center}
    $R(t) = (1 - t)^2 P_0 + 2t(1 - t)P_1 + t^2 P_2$
\end{center}

A cubic Bezier Curve with 4 points $P_0$ to $P_3$, with $P_1$ and $P_2$ tugging, is
denoted by:
\begin{center}
    $Q(t) = (1 - t)^3 P_0 + 3t(1 - t)^2 P_1 + 3t^2(1 - t) P_2 + t^3 P_3$
\end{center}

\newpage

\section{Mar. 22, 2016 - 3 Dimensionality}

Now that we have lines, hermite curves, bezier curves, and circles, we want to be
able to generate pseudo-3D images with 2D representations.

\subsection{Spheres}

Let's make a sphere. As we know from Blender, there is the icosphere (formed by
triangles) and the UV sphere (formed by layers of circles).

$
\begin{bmatrix}
    1 & 0 & 0 & 0 \\
    0 & cos\phi & -sin\phi & 0 \\
    0 & sin\phi & cos\phi & 0 \\
    0 & 0 & 0 & 1
\end{bmatrix} \times
\begin{bmatrix}
    r\cos\theta \\
    r\sin\theta \\
    0 \\
    1
\end{bmatrix} =
\begin{cases}
    x = r\cos\theta \\
    y = r\sin\theta\cos\phi \\
    z = r\sin\theta\sin\phi
\end{cases}
$

We have $\theta$ as the circle creation, and $\phi$ as the angle of circle rotation.
We need to check ranges between 0 and $2\pi$ and between 0 and $\pi$ for both
$\theta$ and $\phi$.

Pseudocode for sphere points:

\begin{verbatim}
for p from 0.0 to 1.0:
for t from 0.0 to 1.0:
x = r * cos(pi * t)
z = r * sin(pi * t) cos(2 * pi * p)
z = r * sin(pi * t) sin(2 * pi * p)
\end{verbatim}

Now... onto the tastiest of shapes!

\subsection{The Torus. AKA The Tasty Donut}

If we think about it we can generate a torus by translating about the $y$ axis and
rotating in the $x$ axis. This allows to rotate the circle about an external point,
generating each ``sector'' or ``slice'' of the torus.

We can modify our original matrix operation to translate / rotate our circle to
generate a torus of radius $R$:

$
\begin{bmatrix}
    1 & 0 & 0 & 0 \\
    0 & cos\phi & -sin\phi & 0 \\
    0 & sin\phi & cos\phi & 0 \\
    0 & 0 & 0 & 1
\end{bmatrix} \times
\begin{bmatrix}
    r\cos\theta \\
    r\sin\theta + R \\
    0 \\
    1
\end{bmatrix} =
\begin{cases}
    x = r\cos\theta \\
    y = \cos\phi(r\sin\theta + R) \\
    z = \sin\phi(r\sin\theta + R)
\end{cases}
$

\section{Mar. 29, 2016 - Wireframe and Polygon Meshes}

From our code for adding spheres and tori, here:

\begin{verbatim}
addSphere(Double cx, Double cy, Double cz, Double radius) {
    double x, y, z;

    for (double p = 0; p < CEILING; p += STEP) {
        for (double t = 0; t < CEILING; t += STEP) {
            x = radius * cos(t * PI) + cx;
            y = radius * sin(t * PI) * cos(p * 2 * PI) + cy;
            z = radius * sin(t * PI) * sin(p * 2 * PI) + cz;
            addPoint(new Point((int) x, (int) y, (int) z));
        }
    }
}

addTorus(Double cx, Double cy, Double cz, Double r1, Double r2) {
    double x, y, z;

    for (float p = 0; p < CEILING; p += STEP) {
        for (float t = 0; t < CEILING; t += STEP) {
            x = r1 * cos(t * 2 * PI) + cx;
            y = cos(p * 2 * PI) * (r1 * sin(t * 2 * PI) + r2) + cy;
            z = sin(p * 2 * PI) * (r1 * sin(t * 2 * PI) + r2) + cz;
            addPoint(new Point((int) x, (int) y, (int) z));
        }
    }
}
\end{verbatim}

We see that the points that we insert are always a \textbf{set amount}. This means
for a sphere of radius 5, we may be plotting 4000 points, and eventually, it just
looks like a dot, destroying the 3D aspect.

We move onto wireframe and polygon meshes.

\subsection{Wireframe Meshes}

Wireframe meshes are 3D objects defined by the edges that connect the vertices or
points.

It uses the same edge matrix concepts that we have been dealing with throughout
previous assignments.

\subsection{Polygon Meshes}

Polygon meshes are 3D objects defined by the surfaces (typically triangles or
quadrilaterals, as we've seen in Blender) that cover the object.

However, we need to change our polygon mesh to use \textbf{polygon matrices} rather
than edge matrices.

This allows us to draw faces and surfaces, as well as remove hidden faces and
surfaces, which saves much computation later on down the line.

\subsection{Polygon Matrices}

Like we had with an edge matrix, where we stored 2 points (start and end), in a
polygon matrix of triangles, we store 3 points: the vertices of a triangle. We are
drawing \textbf{3} lines per polygon.

\begin{table}[!htpb]
    \centering
    \begin{tabular}{|c|c|}
        \hline
        Edge Matrix & Polygon Matrix \\ \hline
        \texttt{plot} & \texttt{plot} \\ \hline
        \texttt{drawLine} & \texttt{drawLine} \\ \hline
        \texttt{drawLines} & \texttt{drawPolygons} \\ \hline
        \texttt{addPoint} & \texttt{addPoint} \\ \hline
        \texttt{addEdge} & \texttt{addPolygon} \\ \hline
    \end{tabular}
\end{table}

\textbf{NOTE} that in \texttt{addPolygon}, we must add the 3 points in
COUNTERCLOCKWISE fashion.

\section{April 5, 2016: Backface Culling}

Backface culling is a technique to render only forward facing surfaces. The surface
normal, $\vec{N}$, is a vector perpendicular to a plane.

We can compare $\vec{N}$ to the view vector (camera view).

If we look towards an object, then $\vec{N}$ must point towards you. Thus, if the
angle between $\vec{N}$ and the view vector $\vec{V}$ is $\theta$, then $90 \leq
\theta \leq 270$ will create a front facing surface.

Thus, we must use the following algorithm:

\begin{enumerate}
    \item Calculate $\vec{N}$ \\
        \newline
        Cross product of 2 vectors that share endpoint and go in different
        directions:
        \begin{align*}
            \vec{N} &= \vec{A} \times \vec{B} \\
                    &= <A_yB_z - A_zB_y, A_zB_x - A_xB_z, A_xB_y - A_yB_x>
        \end{align*}
    \item Find $\theta$ between $\vec{N}$ and $\vec{V}$ \\
        \newline
        We can just use a default view vector: $\vec{V} = <0, 0, -1>$. We can use the
        formula:
        \begin{center}
            $\cos\theta = \frac{N_xV_x + N_yV_y + N_zV_z}{|\vec{N}||\vec{V}|}$
        \end{center}
    \item If $90 \leq \theta \leq 270$, draw the surface.
\end{enumerate}

\section{April 12, 2016: Relative Coordinate System}

Currently all of our objects are drawn with respect to the same origin / coordinate
system that is \textbf{global}. In a relative coordinate system!  Each object could
have its own origin / coordinate system.

We will be using a stack to store the coordinate systems. Our drawing framework will
be as follows:

\begin{enumerate}
    \item Transformations are applied to the current top of the stack
    \item The stack is pushed and popped as needed.
    \item Drawing pipeline:
        \begin{enumerate}
            \item Generate the points or polygons and add them to a matrix
            \item Multiply the points by the current stack top
            \item Draw the points to the screen
            \item Clear the point matrix
        \end{enumerate}
\end{enumerate}

\section{April 19 - 21, 2016: Compiler}

Using this stack structure requires a bit of a change in our parser. Our current
interpreter is too simple. We need... a \textit{compiler}.

The compilation process looks like this:

\begin{enumerate}
    \item Source code
    \item Compiler
        \begin{enumerate}
            \item Lexer
                \begin{itemize}
                    \item Performs lexical analysis
                    \item Knows the valid symbols of your language
                    \item Generate a list of the tokens in the source code
                    \item Given the following code: \\
                        \begin{verbatim}
                        int main() {
                            long x = 5 + 6;
                            printf("hi");
                            return 0;
                        }
                        \end{verbatim}
                        This will turn into a list of tokens (keywords):
                        \begin{verbatim}
                        int
                        IDENT main
                        (
                        )
                        {
                            long
                            IDENT x
                            =
                            5
                            +
                            6
                            ;
                        }

                        \end{verbatim}
                \end{itemize}
            \item Parser
                \begin{itemize}
                    \item Performs syntax analysis
                    \item Knows the grammar of your language
                    \item Generates a syntax tree
                \end{itemize}
            \item Semantic analyzer
                \begin{itemize}
                    \item Takes a syntax tree as input
                    \item Knows how to map tokens to operations or variables
                    \item Note that functions are variables! They are variables that
                        define a sequence of operations!
                    \item \texttt{return} is an operation!
                    \item Knows how to navigate the syntax tree
                    \item Has a symbol table to map things
                    \item List of operations in order to be performed
                    \item Outputs the operation list (pseudo machine code)
                \end{itemize}
            \item Optimizer
                \begin{itemize}
                    \item Magic :D
                \end{itemize}
            \item Code generator
                \begin{itemize}
                    \item Knows what the operations mean in assembly (machine code)
                    \item Generates the machine code program file
                \end{itemize}
        \end{enumerate}
    \item Machine Code
\end{enumerate}

Each step in a compiler has 3 things that it \textbf{must} have:
\begin{itemize}
    \item Input
    \item What must it know beforehand
    \item Output
\end{itemize}

So what are we going to use to compile??

\subsection{Our tools!}

\texttt{flex} - A command line utility to take source code and output a token
list.

\texttt{bison} - A parser and semantic analyzer

\texttt{sudo apt-get install flex bison}

And in the case of Java, \texttt{javacc}:

\begin{verbatim}
javacc - Parser generator for use with Java
javacc-doc - Documentation for the JavaCC Parser Generator
jtb - syntax tree builder and visitors generator for JavaCC
libjavacc-maven-plugin-java - maven plugin which uses JavaCC to process JavaCC
grammar files
\end{verbatim}

And our code generator? Well, we'll be writing that ourselves.

\newpage

\section{May 3 - 4, 2016: Animation}

The principle of animating a translation is to perform a certain percentage of the
translation successively. If we want to translate 400 pixels along the x axis, then
we can perform it in increments of 25\%, moving 100 pixels at a time.

We can use a potentiometer, I mean, a \textit{knob}, that indicates a
\textbf{factor}. We also need a function called \textbf{vary} that takes 4
parameters: the name of the knob, the start and end frames, and the start and end
values.

In order to implement these frames and knobs, we need to do the following process:
\begin{enumerate}
    \item Pass 1
        \begin{itemize}
            \item Check for animation commands (\texttt{frame}, \texttt{basename},
                \texttt{vary})
            \item Check for basic animatino command errors
                \begin{itemize}
                    \item Check if \texttt{vary} keeps within the bounds set by
                        \texttt{frame}
                    \item Check if \texttt{frame} exists if \texttt{vary} exists
                \end{itemize}
            \item Set the number of frames
            \item If \texttt{basename} is not set, then use a default value and alert
                the user.
        \end{itemize}
    \item Pass 2 (Only runs if Pass 1 finds animation commands)
        \begin{itemize}
            \item Calculate and store knob values
            \item Create an array / list where each index maps to a frame and
                contains a list of knob names and values for that frame
        \end{itemize}
        For example:
        \begin{verbatim}
        vary k 0 10 0 1
        vary x 3  6 1 0
        \end{verbatim}
        \begin{table}[!htpb]
            \centering
            \begin{tabular}{|c|c|c|}
                \hline
                Frame & k & x \\
                \hline
                0 & 0.0 & 1.0 \\
                \hline
                1 & 0.1 & 1.0 \\
                \hline
                2 & 0.2 & 1.0 \\
                \hline
                3 & 0.3 & 1.0 \\
                \hline
                4 & 0.4 & 0.67 \\
                \hline
                5 & 0.5 & 0.33 \\
                \hline
                6 & 0.6 & 0.0 \\
                \hline
                7 & 0.7 & 0.0 \\
                \hline
                8 & 0.8 & 0.0 \\
                \hline
                9 & 0.9 & 0.0 \\
                \hline
                10 & 1.0 & 0.0 \\
                \hline
            \end{tabular}
        \end{table}
    \item Pass 3
        \begin{itemize}
            \item If no animation code, draw a single image and exit.
            \item If there is animation code, for each frame:
                \begin{enumerate}
                    \item Set all knob values in symbol table based on the the list
                        from Pass 2
                    \item Go through all the drawing commands and apply knob values
                        when appropriate
                    \item Save the image as \texttt{basename + frame\_no}
                \end{enumerate}
        \end{itemize}
\end{enumerate}

\section{May 12, 2016 - Filling in shapes, and preparing for lighting!}

Now that we have a decent interpretter / scripting type language, it makes our lives
a lot easier to test, draw images, etc. Now, we can focus on improving our single
frame rendering now that we have a ton of overhead out of the way. One of the things
we need to do is to \textbf{fill} in polygons. There are a few ways to do this:

\begin{itemize}
    \item Flood fill
    \item Sweeping out the triangles with a ton of lines
    \item Using a bounding rectangle and checking each pixel
    \item Dilating triangles from size multiplier 1.0 to 0 and drawing each out
    \item and many many many more
\end{itemize}

Out of these ideas, we want the \textit{least memory intensive one}, as this is going
to a very common operation. Because our line algorithm is so optimized already, we
can use the ``sweeping lines'' idea, combined with a ``horizontal line'' flood fill,
known as the \textbf{scanline conversion}.

\subsection{Scanline Conversion}

Scanline conversion is where we start from a vertex, and draw vertical OR horizontal
lines in the direction of the other 2 vertices to fill in the triangle.

Some characteristics of scanline conversion:

\begin{itemize}
    \item Filling in a polygon with a series of horizontal or vertical lines
    \item Need to identify the top, bottom, and middle vertices for each polygon.
    \item We will denote B as the bottom vertex, M as the middle vertex, and T as the
        top vertex, using their $y$ axis coordinates
\end{itemize}

We have $(x_0 y_0)$ that is always on $\bar{BT}$, and $(x_1, y_1)$ that will either
be on $\bar{BM}$ or $\bar{MT}$.

The horizontal line will have $y_0 = y_1$, and will move upwards from $B$ to $T$.

\begin{enumerate}
    \item Our first line is $\bar{BB}$. Simply, \texttt{x0 = x1 = B.x} and \texttt{y0
        = y1 = B.y}
    \item Our second line goes from $(x_B + \Delta X_1, y_B + 1)$ to $(x_B + \Delta
        X_2, y_B + 1)$. \\
        \newline
        To find $\Delta X_1$, we know that the first point is on $\bar{BT}$. Using
        some simple coordinate geometry and the line equation, we can see: \\
        \begin{center}
            $\Delta X_1 = \frac{X_T - X_B}{Y_T - Y_B}$ \\
            $\Delta X_2 = \frac{X_M - X_B}{Y_M - Y_B}$ on $\bar{BM}$ \\
            $\Delta X_2 = \frac{X_T - X_M}{Y_T - Y_M}$ on $\bar{MT}$
        \end{center}
\end{enumerate}

However, these $\Delta$ values are floating point values. This is not very convenient
for us, since we want to use integers for pixel locations. Another issue is division
by 0. We will always have a ``true'' top point and a ``true'' bottom point, but the
middle point may lie on the same horizontal as $B$ or $T$, which causes the
denominator being 0. We could simple add checks beforehand, use division by 0 =
infinity, and division by infinity = 0 hackery, or any other such solution.
Preventing this is trivial.

\section{May 18, 2016 - Z Buffering}

Now that we are filling in faces, if we try multiple figures, some pixels might be
overwritten. We can solve this ``overlapping'' problem using the z-buffering
technique.

In Z Buffering, we track a 2D array with the same dimensions as our canvas. Each
index stores a floating point value that represents a Z coordinate. We should ONLY
draw things with greater Z coordinate values than those that currently exist. For
example, drawing in index (250, 150), if we first draw a green pixel with Z value 23,
it is drawn in index (250, 150) since there is nothing yet there. If we later try to
draw a blue pixel at index (250, 150) with a Z value of 8, 8 is less than 23 so we do
NOT draw it.

As such, we should use \texttt{Double.MIN\_VALUE} as default values, as this is the
least possible element in this Z buffer. To implement this in our current graphics
engine, we need to change our \texttt{plot} function, \texttt{draw\_line} and
\texttt{draw\_polygon} function. For example, if we need to draw faces, we should
pass that boolean as a parameter to plot, so plot can track a Z buffer. This also
requires passing a Z value to \texttt{draw\_line}. Anything else that uses
\texttt{draw\_line} will also need to be modified.

\section{May 23, 2016 - Modeling Real Lighting}

Colors are calculated by looking at:

\begin{enumerate}
    \item The reflective properties of each object
    \item The properties of the light hitting each object
\end{enumerate}

There is, of course, a standard lighting equation in computer graphics, derived after
many years of computer graphics research:

\begin{itemize}
    \item We want this equation to generate a 3 number color code value for each
        polygon / pixel.
    \item If you want a grayscale image, you only need to calculate the color once
        per polygon / pixel.
    \item If you want a color image, you must calculate each separate color value for
        red, gree, and blue for each polygon.
\end{itemize}

Let $I$ denote ``illumination''.

\begin{center}
    $I = I_{\text{ambient}} + I_{\text{diffuse}} + I_{\text{specular}}$
\end{center}

\textbf{Ambient}, \textbf{diffused}, and \textbf{specular} light are different kinds
of reflected light.

Ambient light is also known as \textit{background} light. Ambient light is more or
less evenly distributed (it hits all objects equally), and comes from all directions.

Another form of light source is \textbf{point light} or \textbf{spotlight} sources.
These are lights that come from a specific point and are focused onto a particular
area, being extremely intense in those areas, and extremely dim elsewhere. Their
strength is therefore determined by an objects position away from the source.
\textbf{Diffuse} lighting and \textbf{specular} lighting deals with point light
sources.

$I_{\text{ambient}}$: a combination of the color of ambient light and the amount and
color that the object reflects.

$I_{\text{diffuse}}$: Diffuse reflection reflects point lights back equally in all
directions. It is based on the locations of the light and the object.

$I_{\text{specular}}$: Comes from a point light source, and is reflected back at a
specific direction. Thus we need to worry about what angle we are looking at the
object as well.

\subsection{Representing Illumination in Code}

There are now 2 things that affect our code. \textbf{Quality of Light} and
\textbf{Reflective Properties}.

\subsubsection{Quality of Light}

For an ambient light, we will represent the quality of light (color value) as a
number between 0 and 255.

For a point light, we need to represent it as a color value and a 3 dimensional
point.

\subsubsection{Reflective Properties}

Represented as the percentage of light reflected back as constants:
$k_{\text{ambient}}$, $k_{\text{diffuse}}$, and $k_{\text{specular}}$.

This will also satisfy the relation:

\begin{center}
    $0 \leq k_a, k_d, k_s$ \\
    $k_a + k_d + k_s = 1$
\end{center}

\section{May 26, 2016: The Lighting Equation}

\begin{center}
    $I = I_{\text{ambient}} + I_{\text{diffuse}} + I_{\text{specular}}$
\end{center}

Ambient reflection requires us to have variables for:
\begin{itemize}
    \item Color value ($C_a$)
    \item Constant of ambient reflection ($K_a$)
\end{itemize}

\begin{center}
    $I_a = C_aK_a$
\end{center}

Diffuse reflection requires us to have variables for:
\begin{itemize}
    \item Color point source ($C_p$)
    \item Constant of diffuse reflection ($K_d$)
    \item The angle of incidence ($\theta$)
\end{itemize}

\begin{center}
    $I_d = C_pK_d\cos\theta$
\end{center}

In specular reflection, we have the vector of incoming light, the color of the point
source, and the view angle. We also have the constant of specularity $K_s$.

Note that $\vec{L}$ is the vector of incoming light, and $\vec{N}$ is the normal
vector. $\vec{L}\cdot\vec{N} = \|\vec{L}\|\|\vec{N}\|\cos\theta$

We will have to turn $\vec{L}$ and $\vec{N}$ into unit vectors via normalizing!

There is one more thing we need to keep track of: the view vector: $\vec{V}$. Let
$\alpha$ be the angle between $\vec{V}$ and the reflected ray $\vec{R}$. To find
$\vec{R}$. We can project $\vec{L}$ onto $\vec{N}$ and then use that to create
$\vec{R}$.

Note that $\vec{L}$ and $\vec{N}$ are \textit{normalized}. Therefore their magnitudes
are 1. We can use the relation:

\begin{center}
    $\vec{P} = \|\vec{N}\|\cos\theta = \|\vec{N}\|(\vec{L}\cdot\vec{N})$
\end{center}

Letting $\vec{S}$ be the perpendicular from $\vec{L}$ to $\vec{N}$, we know that
$\vec{S} = \vec{N} ( \vec{L} \cdot \vec{N} ) - \vec{L}$, which we can plug into
$\vec{R} = \vec{P} + \vec{S}$. Thus, $\vec{R} = 2 * \vec{P} - \vec{L}$.

Using the dot product of $\vec{V}$ and $\vec{R}$ to get the angle $\alpha$ between
them.

\begin{center}
    $I_s = C_pK_s\cos\alpha$
\end{center}

We can also raise the $\cos\alpha$ term to some power $n$ to tune the value.

\subsection{Issues with calculating color values}

Color values can become negative after it is computed! Basically turn everything less
than 0 into 0. If a color value is higher than 255, then make it 255.

\subsection{Shading Models}

\begin{itemize}
    \item Flat shading: Calculate $I$ once per polygon.
    \item Goroud shading: vertex normals for each polygon. Combine surface normals of
        all polygons that share a vertex
\end{itemize}

\section{May 31, 2016 - Shading models}

Gouraud, Goroud, whatever, shading involves:

\begin{itemize}
    \item Calculate $I$ once per vertex normal (normalized sum of the surface normals
        that share a vertex).
    \item Interpolate $I$ during scanline conversion and during drawing lines
\end{itemize}

In the Phong Shading model:

\begin{itemize}
    \item Calculate vertex normals
    \item Interpolate the normal in scanline conversion and drawline
    \item Recalculate $I$ for each PIXEL
\end{itemize}

\end{document}