---
# System prepended metadata

title: CG Fin (12/29)
tags: [CG]

---

# CG Fin (12/29)
###### tags: `CG`

---

[TOC]

---

:::info
- [x] 0929
- [x] 1006
- [x] 1013
- [x] 1020
- [x] 1027
- [x] 1110
- [x] 1124
- [x] 1201
- [x] 1208
- [x] 1215
- [ ] 1222
:::

---

## Foundations of Graphics

### Startup
- Skeleton code:
    - OpenGL
    - GLUT
- Open a window
    - Width, height, origin (upper left)
- Resolution of each pixel:
    - RGB Model:
        - 3 tracks: $(r, g, b)$
        - Each track: 1 byte (0 ~ 255)
        - Each pixel: 3 byte
    - Other models: HSV, RIY, ...

### Concepts of CG & CG Pipeline
- Def of Computer Graphics:
    > *Using the computer to create, encode, manipulate and display 2D & 3D data*
- Graphic Pipeline:
    - Geometric model: *create object*
        Animation: *create behavior*
        Texture on model: *colorful object*
    - Rendering: *manipulation*
    - Output device: *display*

### Creation
> *how to create synthetic object?*
- use a modeler
- 3D scan (MRI, CT Scan, 3D Scanner)
- math function

### Encoding
> *how to represent an object in the computer?*
- Point or Node:
    - $(x, y, z)$
- Line:
    - Parameter form of line:
        $\begin{cases}
        x = x_1 + t (x_2 - x_1) \\
        y = y_1 + t (y_2 - y_1) \\
        z = z_1 + t (z_2 - z_1) \\
        \end{cases},\ (0 < t < 1)$
- Polygon:
    - $(x_1, y_1, z_1), ..., (x_n, y_n, z_n)$
    - Always represent these vertices(nodes) in anti-clockwise order
- Circle:
    - Approximate line segments (very small)
    - Tessellation:
        - We present a circle by a polygon.
        - The polygon is with many edges.
        - Each edge is very small
    - Why: we need "polygon object" only
- 3D Polygonal Objects:
    - $<\#\ \text{verts}>, <\#\ \text{faces}>$
    - for each vert: $\begin{cases}
        x_1, y_1, z_1 \\
        ...
        \end{cases}$
    - for each face: $\begin{cases}
        <\#\ \text{verts on the face}>\ <\text{list of vert IDs}> \\
        ...
        \end{cases}$

### Modeling
- Solid modeling:
    - Using union, extraction of basic shapes to get a solid model
- Terrain modeling:
    - Height map
- Procedural modeling:
    - Used for water, smoke, fire, cloud, ...
- Volume modeling:
    - Used fir CT-Scan, MRI
    - Scanned by slice to get 3D shape
    - Voxel
        - for each voxel, we define its color or density to represent something
- Fractal modeling:
    - Used for mountain, water, leaves, skin, ...
    - Re-generation of shapes
    - E.g. as nearer, represent it by more triangles
- Warping or Morphing:
    - Change the shape smoothly into another shape

### Animation
> *Modeling behavior*
- Frame rate:
    - 1~3 fps: interaction
    - 10 fps: animation rate
    - 30 fps: real-time rate
        - Flicker-free: eye cannot distinguish frames
    - 60~70: movie rate
- Character animation:
    - Key frame animation:
        - Most frames(frames in-between) are generated by interpolating between the key frames
    - Physical-based animation:
        - it is all based on physical-model or math equation
        - particles, explosions, collision, firework, ...
    - Motion capture:
        - put sensors on body and capture the motion of body
    - IK (Inverse kinematics):
        - Based on constructs on the skeleton
        - Use the joint to recover the location of other parts


## 3D Rendering Concepts
### Mind Map
- 3D geometric modeling: *object*
    3D animation: *behavior*
    Texture synthesis: *2D images*
    Storage device: *JPG, BMP*
    Display device
- $\rightarrow$ 3D Rendering:
    > *To calculate the interaction between objects & lights in the scene to generate a final 2D image*
    - 2D line drawing
    - 2D circle drawing
    - Transformation (translation, rotation, scale)
    - Hidden surface removal
    - Lighting effect (shading)
    - Surface shading
    - Reflection
    - Texture mapping
    - Special effect

### Raster Display
- base on TV technology
- Scan line
- 640 x 480 pixels
- size of each pixel:
    - B/W: 1 bit/pixel
    - Gray scale: 8 bit/pixel
        - 0: dark, 255: white
    - Color image: 24 bit/pixel
        - 2^24^ colors
- Total size: (640 x 480 x 3) bytes
- Advantages:
    - Low cost
    - Regular refresh
    - Display any objects
- Disadvantages:
    - Aliasing (jagged)
- How to solve aliasing?
    - Scan converting lines
    - Midpoint line drawing algorithm


## 2D Raster Drawing
### Scan Converting Lines
- as close to the ideal line as possible
    as straight as possible
    as fast as possible
- E.g.
    - $0 < m\ (\text{slope}) < 1$
    - $y = mx + B,\ (m = \frac{y_2 - y_1}{x_2 - x_1})$
    - 
        ```cpp
        for(x : x_1 ~ x_2)
            y = mx + B;
            plot(x, round(y));  // round(y) == floor(y + 0.5)
        ```
- Incremental method:
    - $y_i = mx_i + B$
        $\Rightarrow y_{i+1} = mx_{i+1} + B = m(x_i + 1) + B = mx_i + B + m$
        $\Rightarrow y_{i+1} = y_i + m$
    - 
        ```cpp
        y = y_1;
        for(x : x_1 ~ x_2)
            plot(x, round(y));
            y += m
        ```
    - There might be some resolution problem for each step:
        - Accumulate errors

### Mid-point Line Drawing Algorithm
1. 
    - Line equation: $ax + by + c = 0$
    - $dx = x_2 - x_1,\ dy = y_2 - y_1$
    - $\frac{x - x_1}{dx} = \frac{y - y_1}{dy} \Rightarrow dx (y - y_1) = dy (x - x_1)$
    - $\begin{cases}
        a = dy = y_2 - y_1 \\
        b = -dx = x_1 - x_2 \\
        c = y_1 dx - x_1 dy = y_1 (x_2 - x_1) - x_1 (y_2 - y_1)
        \end{cases}$
2. 
    - $F(x, y) = ax + by + c$
    - plug $(x, y)$ into $F(x, y)$
    - $\begin{cases}
        F(x, y) < 0 &\Rightarrow (x, y) \text{ to the left of the line}  \\
        F(x, y) = 0 &\Rightarrow (x, y) \text{ on the line} \\
        F(x, y) > 0 &\Rightarrow (x, y) \text{ to the right of the line} 
        \end{cases}$
3. 
    - Pixel array
    - plug the mid-point $(x_p + 1, y_p + 0.5)$ into the line eq. to determine pixel above or below
    - $d_{old} = F(x_p + 1, y_p + 0.5)$
    - $\Rightarrow \begin{cases}
        d_{old} \le 0 &\Rightarrow\text{choose E} \\
        \text{else} &\Rightarrow\text{choose NE}
        \end{cases}$
    - $\Rightarrow \begin{cases}
        E &\Rightarrow d_{new} = F(x_p + 2, y_p + 0.5) = d_{old} + a \\
        NE &\Rightarrow d_{new} = F(x_p + 2, y_p + 1.5) = d_{old} + a + b
        \end{cases}$
4. 
    - What is the initial value of $d$?
        (assume the line starts from $(x_1, y_1),\ F(x_1, y_1) = 0$)
    - $\Rightarrow d_{init} = F(x_1 + 1, y_1 + 0.5) = (ax_1 + by_1 + c) + a + b/2$
        $\Rightarrow d_{init} = a + b/2$
5. 
    - 
        ```cpp
        x = x_1; y = y_1;
        a = y_2 - y_1;
        b = -(x_2 - x_1);
        d = a + b/2
        plot(x_1, y_1);
        for(x : x_1 ~ x_2)
            if(d <= 0) d += a;          // choose E
            else       d += a + b; y++; // choose NE
        ```
6. 
    - Other 7 situations:
        1. If $m > 1 \rightarrow$ swap $x1_a, y1_a$, and swap $x2_a, y2_a$
        2. If $x1_a > x2_a \rightarrow$ swap $x1_a, x2_a$, and swap $y1_a, y2_a$
- There might be some problem for mid-point algo.:
    - dash-line:
        - from left to right / right to left
    - line with $m = 1$ is darker
        line with $m = 0$ is brighter

### Scan Converting Circle
- Circle equation: $(x - x_c)^2 + (y - y_c)^2 - R^2 = 0$
- By one point $(x, y)$, we can derive the other 7 points:
    - $(x, y) \Rightarrow (y, x), (-y, x), (-x, y), (-x, -y), (-y, -x), (y, -x), (x, -y)$
- 
    ```cpp
    for(x : 0 ~ R)
        y = sqrt(R^2 - x^2);  // not efficient
        plot(x, round(y));
    ```

### Mid-point Circle Drawing Algorithm
1. 
    - Circle eq.: $x^2 + y^2 - R^2 = 0$
    - $d = F(x, y) = x^2 + y^2 - R^2$
    - $\begin{cases}
        F(x, y) < 0 &\Rightarrow (x, y) \text{ lies inside the circle} \\
        F(x, y) = 0 &\Rightarrow (x, y) \text{ lies on the circle} \\
        F(x, y) > 0 &\Rightarrow (x, y) \text{ lies outside the circle}
        \end{cases}$
2. 
    - Pixel array
    - $d_{old} = F(x_p + 1, y_p - 0.5)$
    - $\Rightarrow \begin{cases}
        d_{old} < 0 &\Rightarrow\text{choose E} \\
        \text{else} &\Rightarrow\text{choose SE}
        \end{cases}$
    - $\Rightarrow \begin{cases}
        E &\Rightarrow d_{new} &= F(x_p + 2, y_p - 0.5) = d_{old} + 2x_p + 3 \\
        &&= d_{old} + incE \\
        SE &\Rightarrow d_{new} &= F(x_p + 2, y_p - 1.5) = d_{old} + 2(x_p - y_p) + 5 \\
        &&= d_{old} + incSE
        \end{cases}$
3. 
    - $\begin{cases}
        incE_{old} &= 2x + 3 \\
        incSE_{old} &= 2(x - y) + 5
        \end{cases}$
    - $\Rightarrow \begin{cases}
        E &\Rightarrow incE_{new} &= 2(x + 1) + 3 &= incE_{old} + 2 \\
        &\Rightarrow incSE_{new} &= 2((x + 1) - y) + 5 &= incSE_{old} + 2 \\
        SE &\Rightarrow incE_{new} &= 2(x + 1) + 3 &= incE_{old} + 2 \\
        &\Rightarrow incSE_{new} &= 2((x + 1) - (y-1)) + 5 &= incSE_{old} + 4
        \end{cases}$ 
4. 
    - Initial point: $(0, R)$ *(upper point of the circle)*
    - Initial mid-point: $(1, R - 0.5)$ *(to bottom left)*
    - $\Rightarrow d_{init} = F(1, R - 0.5) = 1.25 - R$
    - $\Rightarrow \begin{cases}
        incE_{init} &= 2 \times 0 + 3 &= 3 \\
        incSE_{init} &= 2(0 - R) + 5 &= -2R + 5
        \end{cases}$
5. 
    - Final version:
        ```cpp
        x = 0; y = R;
        d = (1 - R);  // ~= (5/4 - R)
        incE = 3; incSE = -2 * R + 5;
        plot(x, y);
        while(x < y)
            if(d < 0) d += incE;  x++;         // choose E
                      incE += 2;  incSE += 2;
            else      d += incSE; x++; y--;    // choose SE
                      incE += 2;  incSE += 4; 
            plot(x, y);
        ```
6. 
    - *(Optional)* To erase the situation of floating-point problem:
        ```cpp
        x = 0; y = R;
        d = d_init - 0.25 = (1.25 - R) - 0.25 = 1 - R;
        plot(x, y);
        while(x < y)
            if(d < -0.25) d += 2 * x + 3;        // choose E
                          x++;
            else          d += 2 * (x - y) + 5;  // choose SE
                          x++; y--;
            plot(x, y);
        ```

### Scan Converting Polygon
- To fill a polygon
- E.g. a square $(x_1, y_1) \rightarrow (x_2, y_2)$
    ```cpp
    for(y : y_1 ~ y_2) for(x : x_1 ~ x_2) plot(x, y);
    ```
- Problem:
    - From view of "Point", there is no overlapping
    - From view of "Pixel", there is overlapping
- Solution:
    1. Plot the "left" pixels. Do not plot the "right" pixels.
    2. Plot the "bottom" pixels. Do not plot the "top" pixels.
    - There will be no overlapping.
- Types of polygon:
    - Convex polygon
    - Concave polygon
    - Self-intersecting
    - Polygons with holes
        - Outside edges: in order of "counter-clockwise"
        - Inside edges: in order of "clockwise"
- Polygon scan conversion:
    ```cpp
    for(each scanline)
        for(each edge of the polygon)
            find x-intersections of scanline with edge
        sort the x-intersections by increasing x-value
        fill in pairs of intersection points using the odd-parity rule
    ```
- The Odd-parity Rule:
    - Status: $\begin{cases}
        \text{Even} &\rightarrow \text{No color} \\
        \text{Odd} &\rightarrow \text{Color}
        \end{cases}$
- Polygon Filling Rule:
    1. If x-intersection happens at a non-integer location
        - If this is a left edge
            - round-up to the first pixel on the scanline
        - If this is a right edge
            - round-down to the previous pixel on the scaline
    2. If x-intersection happens at an integer location
        - If this is a left edge
            - include this pixel
        - If this is a right edge
            - exclude this pixel
    3. If x-intersection happens at an integer location
        and the intersection is shared
        - If the intersection happens at the max-y of any edge
            - Do Not flip the parity
    4. If horizontal line
        - ignore them as far as parity flips are concerned
    - E.g.
        ![](https://i.imgur.com/0j0zpje.png =250x)
        ![](https://i.imgur.com/9aku4Bm.png =400x)
- Imperfect case:
    - Sliver: a kind of aliasing
        ![](https://i.imgur.com/BEXmOWY.png =300x)
        Nothing to be plotted


## 2D Clipping
### Point Clipping
- Clipping window: $(x_{min}, y_{min}) \rightarrow (x_{max}, y_{max})$
- $\begin{cases}
    (x \in (x_{min}, x_{max})) \land (y \in (y_{min}, y_{max})) &\Rightarrow \text{keep point } (x, y) \\
    \text{else} &\Rightarrow \text{reject point } (x, y)
    \end{cases}$

### Line Clipping: Cohen-Sutherland Algorithm
- 4-bit code: $(b1, b2, b3, b4) \Rightarrow \begin{cases}
    b1 = y > y_{max},\ &b2 = y < y_{min} \\
    b3 = x > x_{max},\ &b4 = x < x_{min}
    \end{cases}$
- How to do line clipping?
    $\Rightarrow \begin{cases}
    (code1 = 0000) \land (code2 = 0000) &\Rightarrow \text{trivially accept the line} \\
    (code1 \ne 0000) \land (code2 \ne 0000) &\Rightarrow \text{trivially reject the line} \\
    \text{else} &\Rightarrow \text{clip the line}
    \end{cases}$

### Polygon Clipping: Sutherland-Hodgmann 4-Pass Algorithm
- Rule:
    - Line: $s \rightarrow p$, intersection: $i$
    - for each edge: $\begin{cases}
        (s \in \text{Win}) \land (p \in \text{Win}) &\Rightarrow &p \\
        (s \in \text{Win}) \land (p \notin \text{Win}) &\Rightarrow &i \\
        (s \notin \text{Win}) \land (p \notin \text{Win}) &\Rightarrow &\varnothing \\
        (s \notin \text{Win}) \land (p \in \text{Win}) &\Rightarrow &i, p
        \end{cases}$


## Basic Linear Algebra
### Matrix
- $M_{n \times m} = \overbrace{\begin{bmatrix}
    & \dots &
    \end{bmatrix}}^\text{m columns}\}\ \scriptsize{\text{n rows}}$
- $A_{n \times m} + B_{n \times m} = C_{n \times m} \Rightarrow c_{ij} = a_{ij} + b_{ij}$
- $A_{n \times k} + B_{k \times m} = C_{n \times m} \Rightarrow c_{ij} = \sum\limits_{l=0}^{k}{a_{il} \times b_{lj}}$
- $n = m \Leftrightarrow \text{square matrix}$
- Identity matrix: $\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$
- $\exists M^{-1} \Leftrightarrow (n = m) \land (|M| \ne 0)$

### Vector
- Row Vector: $M_{1 \times m}$, Column Vector: $M_{n \times 1}$
- Directions:
    - $V = (v_x, v_y, v_z)$
    - $l_V = \sqrt{v_x^2 + v_y^2 + v_z^2}$
    - $N_V = \frac{V}{l_V} = (\frac{v_x}{l_V}, \frac{v_x}{l_V}, \frac{v_x}{l_V})$ (Unit Vector)
    - $l_{N_V} = 1$
    - $\text{Direction}(V) = \text{Direction}(N_V)$
- Dot Product:
    - $A \cdot B = |A| |B| \cos{\theta} = (a_x \times b_x,\ a_y \times b_y,\ a_z \times b_z)$
    - $\Rightarrow \cos{\theta} = \frac{A \cdot B}{|A||B|}$
    - $\Rightarrow \theta = \cos^{-1}{(\frac{A \cdot B}{|A||B|})}$
    - $\Rightarrow \begin{cases}
        A \cdot B > 0 &\Rightarrow& \theta < 90^\circ \\
        A \cdot B = 0 &\Rightarrow& \theta = 90^\circ \\
        A \cdot B < 0 &\Rightarrow& \theta > 90^\circ
        \end{cases}$
- Cross Product:
    - $A \times B = C = -B \times A$ (Right-hand Rule)
    - $\Rightarrow A \times B = (a_yb_z - a_zb_y,\ a_zb_x - a_xb_z,\ a_xb_y - a_yb_x)$
    - $|A \times B| = |A||B|\sin{\theta}$
- Projection:
    - Direction: $\vec{u}$
    - Length: $|A|\cos{\theta} = |A||\vec{u}|\cos{\theta} = A \cdot \vec{u}$
    - $A^\prime = (A \cdot \vec{u})\ \vec{u}$


## 2D Transformations
### Spaces
1. Object Space: *where objects are created*
2. World Space: *where the scene is created*
3. Image Space: *where the image is created*

### Naive Transformations
#### Naive Translation
- $\begin{cases}
    x^\prime = x + t_x \\
    y^\prime = y + t_y
    \end{cases}$
- $\Rightarrow P^\prime = T(t_x, t_y) + P,\ \left(
    P^\prime = (x^\prime, y^\prime),\
    P = (x, y),\
    T(t_x, t_y) = \begin{bmatrix} t_x \\ t_y \end{bmatrix} \right)$
- Only translate the two end-points and draws the line between two end-points

#### Naive Scaling
- $\begin{cases}
    x^\prime = s_x \times x \\
    y^\prime = s_y \times y
    \end{cases}$
- $\Rightarrow P^\prime = S(s_x, s_y) \times P,\ \left(
    P^\prime = (x^\prime, y^\prime),\
    P = (x, y),\
    S(s_x, s_y) = \begin{bmatrix} s_x & 0 \\ 0 & s_y \end{bmatrix} \right)$
- $\begin{cases}
    s_x = s_y &\Rightarrow \text{uniform scaling} \\
    s_x \ne s_y &\Rightarrow \text{differential scaling}
    \end{cases}$

#### Naive Rotation
- Rotate by $\theta$ counter-clockwise
- $\begin{cases}
    x= R\cos{\phi} \\
    y = R\sin{\phi}
    \end{cases}$
- $\begin{cases}
    x^\prime &= R\cos{(\phi + \theta)} = R\cos{\phi}\cos{\theta} - R\sin{\phi}\sin{\theta} \\
    &= x\cos{\theta} - y\sin{\theta} \\
    y^\prime &= R\sin{(\phi + \theta)} = R\cos{\phi}\sin{\theta} - R\sin{\phi}\cos{\theta} \\
    &= x\sin{\theta} - y\cos{\theta}
    \end{cases}$
- $\Rightarrow P^\prime = R(\theta) \times P,\ \left(
    P^\prime = (x^\prime, y^\prime),\
    P = (x, y),\
    R(\theta) = \begin{bmatrix} \cos{\theta} & -\sin{\theta} \\ \sin{\theta} & \cos{\theta} \end{bmatrix} \right)$

### 2D Homogeneous Coordinate (H.C.)
- Goal is to treat all transformation as multiplication ONLY
- Homogeneous Point (H.P.) is given by a triple $(x, y, w)$
- Corresponding Cartesian Point (C.P.) is given by $(\frac{x}{w}, \frac{y}{w}, 1)$
- Scalar multiples of a H.P. represents the same C.P.
    - E.g. $(2, 4, 2) \rightarrow (1, 2, 1),\ (4, 8, 4) \rightarrow (1, 2, 1)$
- At least one of the H.P. values must be non-zero
    - E.g. $(0, 0, 0)$ not allowed
- If $w = 0$, treat $(x, y)$ as a vector/direction instead of a point
- $\Rightarrow \text{C.P.: } (x, y) \rightarrow \text{H.P.: } (x, y, 1)$
    - Initial point (H.P.): $P = \begin{bmatrix} x \\ y \\ 1 \end{bmatrix},\ P^\prime = \begin{bmatrix} x^\prime \\ y^\prime \\ 1 \end{bmatrix}$
    - Naive transformation:
        $\begin{cases}
        \text{Translation}: &P^\prime = T(t_x, t_y) + P \\
        \text{Scaling}: &P^\prime = S(s_x, s_y) \times P \\
        \text{Rotation}: &P^\prime = R(\theta) \times P
        \end{cases}$
        - Not good. We need multiplication
    - Homogeneous transformations:
        $\begin{cases}
        \text{Translation}: &P^\prime = T(t_x, t_y) \times P \\
        \text{Scaling}: &P^\prime = S(s_x, s_y) \times P \\
        \text{Rotation}: &P^\prime = R(\theta) \times P
        \end{cases}$

### Homogeneous Transformations
#### Homogeneous Translation
- $T(t_x, t_y) = \begin{bmatrix}
    1 & 0 & t_x \\
    0 & 1 & t_y \\
    0 & 0 & 1
    \end{bmatrix}$
- $\Rightarrow P^\prime = T(t_x, t_y) \times P \Rightarrow \begin{bmatrix} x^\prime \\ y^\prime \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$

#### Homogeneous Scaling
- $S(s_x, s_y) = \begin{bmatrix}
    s_x & 0 & 0 \\
    0 & s_y & 0 \\
    0 & 0 & 1
    \end{bmatrix}$
- $\Rightarrow P^\prime = S(s_x, s_y) \times P \Rightarrow \begin{bmatrix} x^\prime \\ y^\prime \\ 1 \end{bmatrix} = \begin{bmatrix} s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$

#### Homogeneous Rotation
- $R(\theta) = \begin{bmatrix}
    \cos{\theta} & -\sin{\theta} & 0 \\
    \sin{\theta} & \cos{\theta} & 0 \\
    0 & 0 & 1
    \end{bmatrix}$ *(counter-clockwise)*
- $\Rightarrow P^\prime =R(\theta) \times P \Rightarrow \begin{bmatrix} x^\prime \\ y^\prime \\ 1 \end{bmatrix} = \begin{bmatrix} \cos{\theta} & -\sin{\theta} & 0 \\ \sin{\theta} & \cos{\theta} & 0 \\ 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$

### Composition / Concatenation of Matrices
1. $T(t_{x_2}, t_{y_2}) \times T(t_{x_1}, t_{y_1}) = T(t_{x_1} + t_{x_2},\ t_{y_1} + t_{y_2})$
2. $S(s_{x_2}, s_{y_2}) \times S(s_{x_1}, s_{y_1}) = S(s_{x_1} \times s_{x_2},\ s_{y_1} \times s_{y_2})$
3. $R(\theta_2) \times R(\theta_1) = R(\theta_1 + \theta_2)$

### Commutative Property of Matrices
- $M_1 \times M_2 \ne M_2 \times M_1$
    - E.g. $R(45^\circ) \times T(10, 0) \ne T(10, 0) \times R(45^\circ)$
- Tip: how to make it rotate by itself?
    - $M = T(x, y) \times R(\theta) \times T(-x, -y)$

### Orthogonal Matrices
- $R(\theta) = \begin{bmatrix} \cos{\theta} & -\sin{\theta} & 0 \\ \sin{\theta} & \cos{\theta} & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} V_1 \\ V_2 \\ (0, 0, 1) \end{bmatrix}$
- $\Rightarrow |V_1| = 1,\ |V_2| = 1,\ V_1 \cdot V_2 = 0,\ \theta = 90^\circ$
- $\Rightarrow R(\theta) \times V_1 = (1, 0, 0),\ R(\theta) \times V_2 = (0, 1, 0)$
- If $M$ is an orthogonal matrix (rows are orthogonal & unit), then $M^{-1} = M^T$
- $\Rightarrow R^{-1}(\theta) = R^T(\theta) = \begin{bmatrix} \cos{\theta} & \sin{\theta} & 0 \\ -\sin{\theta} & \cos{\theta} & 0 \\ 0 & 0 & 1 \end{bmatrix}$
- E.g.
    - Given $V_1 = (v_{1x}, v_{1y}, 0),\ V_2 = (v_{2x}, v_{2y}, 0),\ |V_1| = 1,\ |V_2| = 1,\ V_1 \cdot V_2 = 0$
    - Q1: What matrix could turn $V_1, V_2$ to axis $x,\ y$?
        - $\begin{bmatrix} v_{1x} & v_{1y} & 0 \\ v_{2x} & v_{2y} & 0 \\ 0 & 0 & 1 \end{bmatrix}$
    - Q2: What matrix could turn axis $x,\ y$ to $V_1, V_2$?
        - ${\begin{bmatrix} v_{1x} & v_{1y} & 0 \\ v_{2x} & v_{2y} & 0 \\ 0 & 0 & 1 \end{bmatrix}}^{-1} = {\begin{bmatrix} v_{1x} & v_{1y} & 0 \\ v_{2x} & v_{2y} & 0 \\ 0 & 0 & 1 \end{bmatrix}}^{T} = \begin{bmatrix} v_{1x} & v_{2x} & 0 \\ v_{1y} & v_{2y} & 0 \\ 0 & 0 & 1 \end{bmatrix}$

### Rigid Body Transformation & Affine Transformation
- Rigid Body Transformation *(no distortion of shape)*:
    - Preserve lengths of sides
    - Preserve internal angles
    - E.g. Rotation transformation, Translation transformation
        - Transformation matrices are orthogonal
- Affine Transformation:
    - Do not preserve lengths of sides
    - Do not preserve internal angles
    - Preserve parallelism of lines
    - E.g. Shearing: $Sh_x(sh_x) = \begin{bmatrix} 1 & sh_x & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$


## 2D Window to Viewport Mapping
### 2D Rendering Pipeline
1. Object Space
    - $\downarrow\ :$ 2D Transformation
        - $TM:$ Translation, Rotation, Scaling, Shearing
2. World Space
    - $\downarrow\ :$ Window to Viewport Mapping
        - $WVM:$ Window & Viewport Parameters
3. Screen Space
- $\Rightarrow M = WVM \times TM$

### Window to Viewport Mapping
- World Space:
    - Window of Camera: $(x_{w,min},\ y_{w,min}) \rightarrow (x_{w,max},\ y_{w,max})$
- Screen Space:
    - Viewport: $(x_{v,min},\ y_{v,min}) \rightarrow (x_{v,max},\ y_{v,max})$
- Aspect Ratio = Ration of the width to the height of the viewport
    $= (x_{v,max} - x_{v,min}) / (y_{v,max} - y_{v,min})$
- $\Rightarrow WVM = T(x_{v,min},\ y_{v,min}) \times S(A) \times T(-x_{w,min},\ -y_{w,min})$
    - $A: \begin{cases}
        s_x = (x_{v,max} - x_{v,min}) / (x_{w,max} - x_{w,min}) \\
        s_y = (y_{v,max} - y_{v,min}) / (y_{w,max} - y_{w,min})
        \end{cases}$


## 3D Transformations
### 3D Homogeneous Coordinate (H.C.)
- 4D homogeneous points: $(x, y, z, w)$
- To convert a H.P. $(x, y, z, w)$ to C.P. $(x/w, y/w, z/w, 1)$
- Whenever $w=0$ ,treat it as a vector / direction
- At least one of the coordinates must be non-zero, meaning that the H.P. $(0, 0, 0, 0)$ is not allowed
- Scalar multiples of a H.P. represent the same C.P.

### Homogeneous Transformations
#### Homogeneous Translation
- $T(t_x, t_y, t_z) = \begin{bmatrix}
    1 & 0 & 0 & t_x \\
    0 & 1 & 0 & t_y \\
    0 & 0 & 1 & t_z \\
    0 & 0 & 0 & 1
    \end{bmatrix}$
- $T^{-1}(t_x, t_y, t_z) = T(-t_x, -t_y, -t_z)$

#### Homogeneous Scaling
- $S(s_x, s_y, s_z) = \begin{bmatrix}
    s_x & 0 & 0 & 0 \\
    0 & s_y & 0 & 0 \\
    0 & 0 & s_z & 0 \\
    0 & 0 & 0 & 1
    \end{bmatrix}$
- $S^{-1}(s_x, s_y, s_z) = S(1/s_x, 1/s_y, 1/s_z)$

#### Homogeneous Rotation
- $R_x(\theta) = \begin{bmatrix}
    1 & 0 & 0 & 0 \\
    0 & \cos{\theta} & -\sin{\theta} & 0 \\
    0 & \sin{\theta} & \cos{\theta} & 0 \\
    0 & 0 & 0 & 1
    \end{bmatrix}$ *(counter-clockwise)*
- $R_y(\theta) = \begin{bmatrix}
    \cos{\theta} & 0 & \sin{\theta} & 0 \\
    0 & 1 & 0 & 0 \\
    -\sin{\theta} & 0 & \cos{\theta} & 0 \\
    0 & 0 & 0 & 1
    \end{bmatrix}$ *(counter-clockwise)*
- $R_z(\theta) = \begin{bmatrix}
    \cos{\theta} & -\sin{\theta} & 0 & 0 \\
    \sin{\theta} & \cos{\theta} & 0 & 0 \\
    0 & 0 & 1 & 0 \\
    0 & 0 & 0 & 1
    \end{bmatrix}$ *(counter-clockwise)*
- $R_x^{-1}(\theta) = R_x(-\theta) = R_x^T(\theta),$ for orthogonal matrix: $M^{-1} = M^T$
    $R_y^{-1}(\theta) = \dots,\ R_z^{-1}(\theta) = \dots$

### Orthogonal Matrices
- $R_x = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos{\theta} & -\sin{\theta} & 0 \\ 0 & \sin{\theta} & \cos{\theta} & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} - & V_1 & - & 0 \\ - & V_2 & - & 0 \\ - & V_3 & - & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$
- $\Rightarrow |V_1| = |V_2| = |V_3| = 1,\ V_1 \cdot V_2 = V_2 \cdot V_3 = V_1 \cdot V_3 = 0$
- $\Rightarrow R_x$ is an orthogonal matrix. The same for $R_y,\ R_z$
- Principles of orthogonal matrix:
    - The 3 vectors are of unit length
    - The 3 vectors are mutually perpendicular to each other
    - $M^{-1} = M^T$

### Rigid Body Transformation & Affine Transformation
- Rigid Body Transformation:
    - Preserve the length of size
    - Preserve internal angles
- Affine Transformation:
    - Preserve parallelism of lines
    - E.g. Shearing: $Sh_{xy}(sh_x, sh_y) = \begin{bmatrix} 1 & 0 & sh_x & 0 \\ 0 & 1 & sh_y & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$


## 3D Viewing Transformation
### Transformations on Objects
- Point: $P^\prime = M \times P$
- Line: Transform the 2 end-points and connect the 2 end-points
- Polygon: Transform each vertex
- Plane:
    - Define a plane:
        1. Using 3 non-colinear points
        2. One point & a normal $N = (n_x, n_y, n_z)$ *(a vector perpendicular to the plane)*
        3. $Ax + By + Cz + D = 0$
            $\begin{cases}
            A = n_x,\ B = n_y,\ C = n_z \\
            D = \text{shortest distance from the origin to the plane}
            \end{cases}$

### General Rotation Matrix (GRM)
- Q1: Align a line $(x_1, y_1, z_1) \rightarrow (x_2, y_2, z_2)$ with z-axis?
    - $M = \underbrace{R_z(\delta) \times
        \underbrace{R_x(\phi) \times
        \underbrace{R_y(\theta) \times 
        \overbrace{T(-x_1, -y_2, -z_3)}
        ^\text{Bring 1 end-point to the origin}}
        _\text{Align vector in y-x plane}}
        _\text{Align vector with z-axis}}
        _\text{Rotate the vector by a required angle}$
    - Inverse back: $M^{-1} = T(x_1, y_2, z_3) \times R_y(-\theta) \times R_x(-\phi) \times R_z(-\delta)$
- Problems:
    - Too much computation
    - Not easy to make inverse *(go back to previous condition)*
- Solution:
    - Use General Rotation Matrix (GRM)
- General Rotation Matrix (GRM):
    - $V_1 = (v_{1x}, v_{1y}, v_{1z}),\ V_2 = (v_{2x}, v_{2y}, v_{2z}),\ V_3 = (v_{3x}, v_{3y}, v_{3z})$
    - $\Rightarrow |V_1| = |V_2| = |V_3| = 1,\ V_1 \cdot V_2 = V_2 \cdot V_3 = V_1 \cdot V_3 = 0$
    - Use GRM below to make $V_1, V_2, V_3$ align with $x, y, z$ respectively
        $\text{(General Rotation Matrix) } GRM = \begin{bmatrix}
        v_{1x} & v_{1y} & v_{1z} & 0 \\
        v_{2x} & v_{2y} & v_{2z} & 0 \\
        v_{3x} & v_{3y} & v_{3z} & 0 \\
        0 & 0 & 0 & 1
        \end{bmatrix}$
- Construct GRM:
    - $|V_z| = |V_T| = 1$
    - $\begin{cases}
        V_3 = V_z &\rightarrow \text{Align z-axis} \\
        V_1 = V_T \times V_3 &\rightarrow \text{Align x-axis} \\
        V_2 = V_3 \times V_1 &\rightarrow \text{Align y-axis}
        \end{cases}$
    - $GRM = \begin{bmatrix} - & V_1 & - & 0 \\ - & V_2 & - & 0 \\ - & V_3 & - & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

### 3D Viewing Transformation
- Transform from World Space to Eye Space
- In Eye Space:
    - The eye looks down the z-axis
    - The head is up-right
- Eye Matrix $EM:$ World Space $\xrightarrow{EM}$ Eye Space
- Construct Eye Matrix: $EM$
    - Given:
        - Eye location: $ep$
        - COI (Center of interest): $coi$
        - Top point / Top vector: $T$
    - $\Rightarrow \begin{cases}
        V_3 = coi - ep \\
        V_1 = T \times V_3 \\
        V_2 = V_3 \times V_1
        \end{cases}
        \Rightarrow GRM(V_1, V_2, V_3)$
    - $\Rightarrow EM = \underbrace{S(-1, 1, 1)}_\text{Mirror} \times GRM(V_1, V_2, V_3) \times T(-ep)$


## 3D Projection Transform
### Parallel Projection
- ![](https://i.imgur.com/g6AigIS.png =350x)
- Projection plane (image): *after projection, z is gone*
- $\Rightarrow PM = \begin{bmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&0 \\ 0&0&0&1 \end{bmatrix}$

### Perspective Projection
1. y-z Plane:
    ![](https://i.imgur.com/zBl0Bk2.png =400x)
    - $\Rightarrow \begin{cases}
        z'' = D \\
        y'' = (\frac{y}{z})z'' = (\frac{y}{z})D \\
        -H \le y'' \le H
        \end{cases}
        \Rightarrow \begin{cases}
        z' = \frac{z''}{H} = \frac{D}{H} = \frac{1}{\tan{\theta_y}} \\
        y' = \frac{y''}{H} = (\frac{y}{z})\frac{D}{H} = (\frac{y}{z})\frac{1}{\tan{\theta_y}} \\
        -1 \le y' \le 1
        \end{cases}$
2. x-z Plane:
    ![](https://i.imgur.com/43rs2MI.png =350x)
    - $\Rightarrow \begin{cases}
        z'' = D \\
        x'' = (\frac{x}{z})z'' = (\frac{x}{z})D \\
        -W \le x'' \le W
        \end{cases}
        \Rightarrow \begin{cases}
        z' = \frac{z''}{W} = \frac{D}{W} = \frac{1}{\tan{\theta_x}} \\
        x' = \frac{x''}{W} = (\frac{x}{z})\frac{W}{H} = (\frac{x}{z})\frac{1}{\tan{\theta_x}} \\
        -1 \le x' \le 1
        \end{cases}$
3. Combine x-z plane and y-z plane *(Consider x as reference)*:
    - $\Rightarrow \begin{cases}
        x' = \frac{x}{z}\frac{1}{\tan{\theta_x}} \\
        y' = \frac{y}{z}\frac{1}{\tan{\theta_y}} = \frac{y}{z}\frac{D}{H} = \frac{y}{z}\frac{D}{W}\frac{W}{H} = \frac{y}{z}\frac{1}{\tan{\theta_x}}A_R,\ (A_R = \frac{W}{H}) \\
        z' = \frac{D}{W} = \frac{1}{\tan{\theta_x}}
    \end{cases}$
4. 
    - $\Rightarrow PM = \begin{bmatrix} 1&0&0&0 \\0& A_R &0&0 \\ 0&0&1&0 \\ 0&0& \tan{\theta_x} &0 \end{bmatrix} \\
        \Rightarrow \begin{bmatrix} x \\ A_Ry \\ z \\ z\tan{\theta_x} \end{bmatrix} = \begin{bmatrix} 1&0&0&0 \\0& A_R &0&0 \\ 0&0&1&0 \\ 0&0& \tan{\theta_x} &0 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}$
5. Perspective Divide:
    - $\Rightarrow \begin{bmatrix} x \\ A_Ry \\ z \\ z\tan{\theta_x} \end{bmatrix} \xrightarrow{\text{Perspective Divide}} \begin{bmatrix} \frac{x}{z\tan{\theta_x}} \\ \frac{A_Ry}{z\tan{\theta_x}} \\ \frac{1}{\tan{\theta_x}} \\ 1 \end{bmatrix} = \begin{bmatrix} x' \\ y' \\ z' \\ 1 \end{bmatrix}$
    - After perspective divide, the visible range: $-1 \le x',y' \le 1$
    - Clip everything outside the visible range
6. Hither Plane & Yon Plane:
    - Hither Plane: *very close*
    - Yon Plane: *very far way*
        - Beyond this plane, everything is ignored
    - Assume: $z' = A + \frac{B}{z}$
    - Boundary conditions (B.C.): $\begin{cases} z' = 0 \\ z = H \end{cases},\ \begin{cases} z' = 1 \\ z = y \end{cases}$
    - $\Rightarrow \begin{cases} 0 = A + \frac{B}{H} \\ 1 = A + \frac{B}{y} \end{cases} \Rightarrow \begin{cases} A = \frac{y}{y - H} \\ z = \frac{Hy}{H - y} \end{cases}$
    - $\Rightarrow z' = \frac{y}{y - H} + \frac{Hy}{H - y}\frac{1}{z}$ *(After perspective divide)*
    - $\Rightarrow z' = (\frac{y}{y - H} + \frac{Hy}{H - y}\frac{1}{z}) \times z\tan{\theta_x} \\ = \frac{y}{y - H}z\tan{\theta_x} + \frac{Hy}{H - y}\tan{\theta_x}$ *(Before perspective divide)*
7. Perspective Projection Matrix *(Final Version)*:
    - $\Rightarrow PM = \begin{bmatrix} 1&0&0&0 \\0& A_R &0&0 \\ 0&0& \frac{y}{y - H}\tan{\theta_x} & \frac{Hy}{H - y}\tan{\theta_x} \\ 0&0& \tan{\theta_x} &0 \end{bmatrix}$
    - After perspective divide, the visible range: $-1 \le x',y' \le 1,\ 0 \le z' \le 1$
    - Clip everything outside the visible range


## 3D Rendering Pipeline
$\begin{cases}
OS: &\text{Object Space} \\
WS: &\text{World Space} \\
ES: &\text{Eye Space} \\
PS: &\text{Projection Space} \\
IS: &\text{Image Space} \\
SS: &\text{Screen Space} \\
\end{cases}$
$\overset{3D}{OS}
\underset{\substack{\text{Translation,} \\ \text{Scaling,} \\ \text{Rotation}}}{\xrightarrow{TM}}
\overset{3D}{WS}
\underset{\substack{\text{Eye location,} \\ \text{COI,} \\ \text{Top vector}}}{\xrightarrow{EM}}
\overset{3D}{ES}
\underset{\substack{\text{Angle of view,} \\ \text{Aspect ratio}}}{\xrightarrow{PM}}
\overset{3D}{PS}
\underset{\substack{-1 \le x',y' \le 1, \\ 0 \le z' \le 1}}{\xrightarrow{\substack{\text{Perspective} \\ \text{divide}}}}
\overset{2D}{IS}
\underset{\substack{\text{Image height,} \\ \text{Image width}}}{\xrightarrow{WVM}}
\overset{2D}{SS}$


## 3D Clipping
### 2D Clipping: Image Space or Screen Space
- Case 1:
    - $\overline{(x_1, w_1),(x_2, w_2)} \xrightarrow{\text{Perspective divide}} \overline{(x_1', 1),(x_2', 1)}$
    - $w_1, w_2 > 1$
    - $\Rightarrow x_1 = x_1' \times w_1,\ x_2 = x_2' \times w_2$
    - $\Rightarrow$ No problem for this case
- Case 2:
    - $\overline{(x_1, w_1),(x_2, w_2)} \xrightarrow{\text{Perspective divide}} \overline{(x_1', 1),(x_2', 1)}$
    - We do not know whether the line if from the $w > 1$ side or the $w < 1$ side
    - $w_i < 0 \implies z < 0,\ (w = z\tan{\theta})$
        - the point is behind the eye
        - the point is invisible
    - $\Rightarrow$ We cannot distinguish if the view comes form the line behind the eye or in front od the eye
        $\Rightarrow$ Lost information of $z$ in 2D
        $\Rightarrow$ Clipping at Screen Space or Image Space is not a good idea
        $\Rightarrow$ It is better to clip before perspective divide

### 3D Clipping: World Space or Eye Space
- With equation of each plane, we can decide view volume and do clipping.
- The view volume is not a box (cuboid)

### 3D Clipping: Projection Space (Better Choice)
- Visible Range:
    $\xrightarrow{\text{Perspective divide}} \begin{cases} -1 \le \frac{x}{w} \le 1 \\ -1 \le \frac{y}{w} \le 1 \\ 0 \le \frac{z}{w} \le 1 \end{cases} \Rightarrow \overbrace{\begin{cases} w + x \ge 0,\ &w - x \ge 0 \\ w + y \ge 0,\ &w - y \ge 0 \\ z \ge 0,\ &w - z \ge 0 \end{cases}}^\text{6 plane equations}$
- Given point $(x, y, z, w)$, check if it satisfied 6 plane equations, to see if clipping is needed
    - $c_i = f_i(x, y, z, w) \Rightarrow \begin{cases} c_i \ge 0 &\Rightarrow& \text{visible} \\ \text{else} &\Rightarrow& \text{invisible} \end{cases}$
- E.g. $f_i(x, y, z, w) = w - x,\ \overline{SP}: S = (x_1, y_1, z_1, w_1), P = (x_2, y_2, z_2, w_2)$
    - $\Rightarrow c = w - x = 0,\ c_1 = w_2 - x_2,\ c_2 = w_2 - x_2$
    - $\Rightarrow \begin{cases} (c_1 < 0) \land (c_2 < 0) &\Rightarrow& \text{trivially reject the line} \\ (c_1 \ge 0) \land (c_2 \ge 0) &\Rightarrow& \text{keep the line for more intersection calc.} \\ \text{else} &\Rightarrow& \text{clip the line} \end{cases}$
    - $\Rightarrow \begin{cases} (c_1 \ge 0) \oplus (c_2 \ge 0) &\Rightarrow \text{keep the intersection point} \\ \text{then } (c_2 \ge 0) &\Rightarrow \text{keep the second point } (P) \end{cases}$
- How to do Clipping:
    - Goal: *find the intersection point and do the clipping*
    - $\Rightarrow \begin{cases} x = x_1 + t(x_2 - x_1) \\ y = y_1 + t(y_2 - y_1) \\ z = z_1 + t(z_2 - z_1) \\ w = w_1 + t(w_2 - w_1) \\ c = c_1 + t(c_2 - c_1),\ \text{(c also changes linearly)} \end{cases}$
    - Find intersection point $I_c = (x, y, z, w)$ at $c = 0$
    - $\Rightarrow 0 = c_1 + t(c_2 - c_1) \Rightarrow t = \frac{c_1}{c_1 - c_2}$
    - $\Rightarrow I_c = S + \frac{c_1}{c_1 - c_2} (P - S)$


## Basic Linear Algebra Utilities
### On-line Test
- Given: $P = (x, y),\ \overline{P_1P_2}: P_1 = (x_1, y_1),\ P_2 = (x_2, y_2)$
- $T_{1,2} = (x - x_1)(y_2 - y_1) - (x_2 - x_1)(y - y_1)$
- $\Rightarrow \begin{cases} T_{1,2} < 0 \Rightarrow P \text{ lies to the left of the line} \\ T_{1,2} = 0 \Rightarrow P \text{ lies on the line} \\ T_{1,2} > 0 \Rightarrow P \text{ lies to the right of the line} \end{cases}$

### Point Inside a Polygon Test
1. Convex Polygon:
    - If $P$ is left to each edge, then $P$ is inside the polygon
2. Concave Polygon:
    - Semi-infinite Line Test:
        - Scanline from $P$ to one direction
        - If number of intersections is odd $\Rightarrow P$ is inside
            If number of intersections is even $\Rightarrow P$ is outside
    - Angle Summation Test:
        - Sum all interval angles between $\overline{PV_i},\ \overline{PV_{i+1}}$
        - If $\sum{\theta_i} = 360^\circ \Rightarrow P$ is inside
            Else $\Rightarrow P$ is outside

### Normal Vector
1. Planar polygons:
    - Given 3 consecutive vertices of a polygon
    - $\overrightarrow{N} = \overrightarrow{V_1V_2} \times \overrightarrow{V_2V_3}$
2. Non-planar polygons $\Rightarrow$ Summation method:
    - $N = (n_x, n_y, n_z)$
    - $\Rightarrow \begin{cases} n_x = \sum_{i=1}^{n}{(y_i-y_j)(z_i+z_j)} \\ n_y = \sum_{i=1}^{n}{(z_i-z_j)(x_i+x_j)} \\ n_z = \sum_{i=1}^{n}{(x_i-x_j)(y_i+y_j)} \end{cases},\ \left(\substack{n = \text{number of vertices}, \\ j = (i + 1) \mod{n}}\right)$

### Plane Equation
1. 
    - Given:
        - Surface/Plane normal $N = (n_x, n_y, n_z)$
        - The perpendicular distance from the plane to the origin: $d$
    - $\Rightarrow F: n_xx + n_yy + n_zz - d = 0$
2. 
    - Given 3 points $V_1, V_2, V_3$ on the plane
    - $\Rightarrow N = (n_x + n_y + n_z) = \overrightarrow{V_1V_2} \times \overrightarrow{V_2V_3}$
    - $\Rightarrow F: n_x(x-x_i) + n_y(y-y_i) + n_z(z-z_i) = 0,\ (i = 1 \lor 2 \lor 3)$
    - $\Rightarrow F: n_xx + n_yy + n_zz - N \cdot V_i = 0,\ (i = 1 \lor 2 \lor 3)$

### Edge-edge Intersection
- $\overline{P_1P_2},\ \overline{P_3P_4}$
- Check if the line lies between each other's end-points
- $(T_{1,2}(P_3) \times T_{1,2}(P_4) < 0) \land (T_{3,4}(P_1) \times T_{3,4}(P_2) < 0)$
    $\Rightarrow$ there is and intersection for $\overline{P_1P_2},\ \overline{P_3P_4}$

### Perpendicular/Shortest Distance From a Point To a Line
- Given: $P,\ \overline{P_1P_2}$, the angle between $\overrightarrow{P_1P},\ \overrightarrow{P_2P} = \theta$
- $t = |\overrightarrow{P_1P}| \sin{\theta} = |\overrightarrow{P_1P}| \frac{|\overrightarrow{P_1P_2}|}{|\overrightarrow{P_1P_2}|}\sin{\theta} = \frac{|\overrightarrow{P_1P} \times \overrightarrow{P_1P_2}|}{|\overrightarrow{P_1P_2}|}$


## 3D Hidden Surface Removal
### Back Face Removal/Culling/Rejection
1. Do it in WS:
    - Eye vector: $\vec{E}$,\ Normal vector: $\vec{N}$
    - $\theta < 90^\circ\ \Rightarrow\ \cos{\theta} > 0\ \Rightarrow\ \vec{N} \cdot \vec{E} > 0$
    - $\Rightarrow \begin{cases} \theta < 90^\circ &\Rightarrow \text{Front Face (FF)} \\ \text{else} &\Rightarrow \text{Back Face (BF)} \end{cases}$
2. Do it in ES:
    - The eye vector looks down the z-axis
    - After perspective divide, distortion happened
    - $\vec{N} = (n_x, n_y, n_z)$
    - $\Rightarrow n_z \ge 0 \Rightarrow \text{Back Face (BF)}$

### Z-Buffer HSR (Hidden Surface Removal) Algorithm
- Do it in SS
- Z-buffer Algorithm Idea:
    1. Initialization:
        - all z-buffer set to infinity
        - all c-buffer set to the background color
    2. 1-st polygon:
        - for each pixel $(x, y)$ inside the polygon, find its z value by plane equation
        - replace the z value in z-buffer
        - replace the color of this pixel in c-buffer
    3. For 2-nd polygon to n-th polygon:
        - for each pixel $(x, y)$ inside the polygon, find its z value by plane equation
        - if current z-value $\le$ z-value in z-buffer
            - replace the z value in z-buffer
            - replace the color of this pixel in c-buffer
- Z-Buffer Algorithm:
    ```cpp
    for(y : 1 ~ height) for(x : 1 ~ width)
        zbuf[y][x] = INF;
        cbuf[y][x] = bg_color;
    for(poly : polygons)
        for(pixel [x, y] : poly)
            z = poly.depth(x, y);
            if(z < zbuf[y][x])
                zbuf[y][x] = z;
                cbuf[y][x] = poly.color(x, y);
    display(cbuf);
    ```
- How to find the z-value of pixel $(x, y)$?
    1. Planar polygon:
        - Figure out the plane equation: $Ax + By + Cz + D = 0$
        - For each pixel $(x, y)$ inside the polygon: $z_{x,y} = -\frac{Ax + By + D}{C}$
        - Use incremental method to find z-value of each pixel:
            $z_{x+1,y} = -\frac{A(x+1) + By + D}{C} = z_{x,y} - \frac{A}{C}$
    2. Non-planar polygon:
        - Use Bilinear Interpolation
        - Y-interpolation:
            ![](https://i.imgur.com/iHSFQhf.png =350x)
            - $y_a = y \Rightarrow \begin{cases} \frac{x_a - x_4}{x_3 - x_4} = \frac{y_a - y_4}{y_3 - y_4} \Rightarrow \text{find } x_a \\ \frac{z_a - z_4}{z_3 - z_4} = \frac{y_a - y_4}{y_3 - y_4} \Rightarrow \text{find } z_a \end{cases}$
            - $y_b = y \Rightarrow \begin{cases} \frac{x_b - x_4}{x_3 - x_4} = \frac{y_b - y_4}{y_3 - y_4} \Rightarrow \text{find } x_b \\ \frac{z_b - z_4}{z_3 - z_4} = \frac{y_b - y_4}{y_3 - y_4} \Rightarrow \text{find } z_b \end{cases}$
        - X-interpolation:
            ![](https://i.imgur.com/0JSBQkK.png =300x)
            - $x_i = x_a,\ ...,\ x_b, y_i = y \Rightarrow \frac{z_i - z_a}{z_b - z_a} = \frac{x_i - x_a}{x_b - x_a} \Rightarrow \text{find } z_i$


## 3D Lighting
### Ambient Lighting
- Background lighting:
    - Replacement of scattered light
    - Background light source
    - Does not have a position or direction
- $I_a \in [0,1]:$ Intensity/Brightness of ambient light source
- $K_a \in [0,1]:$ Coefficient of ambient reflectivity
- $\Rightarrow I_{\text{ambient}} = K_aI_a$

### Diffuse Lighting
- Point light source:
    - Has a position
    - No direction: *equally bright at all direction*
- Dull matte surface
- Surface looks equally from any viewing direction
- Intensity at a point depends on "Lamberts' Law":
    $\Rightarrow$ the $\cos$ of the angle between the light vector and the normal
- "Lamberts' Law":
    - Light source: point
    - $I_p \in [0,1]:$ Intensity of diffuse light source
    - $K_d \in [0,1]:$ Coefficient of diffuse reflectivity
    - $\vec{L}:$ Light vector, $\vec{N}:$ Normal vector
    - $\theta:$ Angle between $\vec{N},\vec{L}$
    - $\Rightarrow I_{\text{diffuse}} = K_dI_p\cos{\theta},\ (\theta \le 90^\circ)$
        - It does not consider the location of the eye, instead, it consider the position of the light source, which comes with "light vector"
- $|\vec{N}| = |\vec{L}| = 1 \Rightarrow \cos{\theta} = \vec{N} \cdot \vec{L}$
- $\Rightarrow I_{\text{diffuse}} = K_dI_p(\vec{N} \cdot \vec{L}),\ (|\vec{N}| = |\vec{L}| = 1,\ \vec{N} \cdot \vec{L} \ge 0)$
    - If $\vec{N} \cdot \vec{L} < 0 \Rightarrow \cos{\theta} < 0 \Rightarrow \theta > 90^\circ$
    - Object hides itself from the light source
    - $\rightarrow \text{Let } \vec{N} \cdot \vec{L} = 0\ \text{(Self-Occlusion)}$

### Advanced Lighting 1
#### Superpose The Effects By Ambient & Diffuse Light
- $I:$ Intensity received by viewer
- $\Rightarrow I = I_{\text{ambient}} + I_{\text{diffuse}} = K_aI_a + K_dI_p(\vec{N} \cdot \vec{L})$

#### Directional Light Source
- What if the light source is a "directional light source"?
    - like a very far away point light source, like the sun
    - $\vec{L_D}:$ liLit vector is the same for any point on the object
    - $\Rightarrow I = K_aI_a + K_dI_p(\vec{N} \cdot \vec{L_D})$
- Light source comparison:
    | | Ambient Light | Point Light | Directional Light |
    |:-:|:-:|:-:|:-:|
    | **Position** | :x: | :o: | :x: |
    | **Direction** | :x: | :x: | :o: |

#### Attenuation of Light Intensity by Distance:
- $I_p \xrightarrow{d} \text{Object}$
- Factor of Attenuation:
    $f_{att} = (a_0 + a_1d + a_2d^2)^{-1} \Rightarrow \begin{cases} a_0: \text{rate of constant attenuation} \\ a_1: \text{rate of linear attenuation} \\ a_2: \text{rate of quadratic attenuation} \end{cases}$
- $\Rightarrow I = K_aI_a + f_{att}K_dI_p(\vec{N} \cdot \vec{L})$

#### Colored Lights & Colored Objects
- Color of Lights: $I_p = (i_{pr}, i_{pg}, i_{pb})$
- Diffuse color of Objects: $O_d = (o_{dr}, o_{dg}, o_{db})$
- $\Rightarrow i_\lambda = (K_ai_{a\lambda} + f_{att}K_di_{p\lambda}(\vec{N} \cdot \vec{L}))\ o_{d\lambda},\ (\lambda = r, g, b)$

### Specular Lighting
- Simulate the effect of shiny objects
- Consider the color of the light source ($I_p$)
- Do not consider the object color ($O_d$)
- It is view dependent *(consider the location of Eye)*
    - On the path way of the perfect reflection $\Rightarrow$ intensity totally received
    - Not on the path way of the perfect reflection $\Rightarrow$ reduce received intensity
- Phong's Illumination Model *(for non-perfect reflection)*:
    - $\vec{V}:$ View vector, $\vec{L}:$ Light vector, $\vec{N}:$ Normal vector, $\vec{R}:$ Reflection vector
    - $\beta:$ angle between $\vec{V}, \vec{R}$
    - $n:$ Specular exponent
    - $\Rightarrow I \propto \cos^n{\beta}$
    - $K_s \in [0,1]:$ Coefficient of specular reflectivity
    - $\Rightarrow I_{\text{specular}} = K_sI_p\cos^n{\beta} = K_sI_p(\vec{R} \cdot \vec{V})^n,\ (|\vec{R}| = |\vec{V}| = 1,\ \vec{R} \cdot \vec{V} \ge 0)$
        - If $\vec{R} \cdot \vec{V} < 0 \Rightarrow \cos{\beta} < 0 \Rightarrow \beta > 90^\circ$
        - Neglect this term ($I_{\text{specular}} = 0$)

### Advanced Lighting 2
#### Superpose The Effects By Ambient & Diffuse & Specular Light
- $\Rightarrow i_\lambda = (K_ai_{a\lambda} + f_{att}K_di_{p\lambda}(\vec{N} \cdot \vec{L}))\ o_{d\lambda} + f_{att}K_si_{p\lambda}(\vec{R} \cdot \vec{V})^n$
    $\begin{cases} \lambda = r, g, b \\ K_a, K_d, K_s \in [0,1] \\ |\vec{N}| = |\vec{L}| = 1,\ \vec{N} \cdot \vec{L} \ge 0 \\ |\vec{R}| = |\vec{V}| = 1,\ \vec{R} \cdot \vec{V} \ge 0 \end{cases}$

#### How To Calculate $\vec{R}$
- $\vec{L}:$ Light vector, $\vec{N}:$ Normal vector, $\vec{R}:$ Reflection vector
- $\theta:$ angle between $\vec{L}, \vec{N}$ and $\vec{R}, \vec{N}$
- Project $\vec{L}$ to $\vec{N}$: $\vec{N'} = |\vec{L}|\cos{\theta}\vec{N} = (\vec{N} \cdot \vec{L}) \vec{N}$
- $\Rightarrow \vec{L} + \vec{S} = \vec{N'}\ \Rightarrow \vec{S} = \vec{N'} - \vec{L}$
- Also $\Rightarrow \vec{R} = \vec{N'} + \vec{S} = 2\vec{N'} - \vec{L} = 2(\vec{N} \cdot \vec{L}) \vec{N} - \vec{L}$

#### How To Calculate $(\vec{R} \cdot \vec{V})$: Half-way Method (Blinn-Phong Model)
![](https://i.imgur.com/bzOIoCE.png =250x)
- Find $\vec{H}$ which divides angle between $\vec{L}, \vec{V}$ into half
- $\vec{H} = \frac{\vec{L} + \vec{V}}{|\vec{L} + \vec{V}|}$
- $\alpha:$ angle between $\vec{N}, \vec{H}$
- $\Rightarrow \alpha \approx \beta \Rightarrow \cos^n{\alpha} \approx \cos^n{\beta}$
- $\Rightarrow (\vec{R} \cdot \vec{V})^n \approx (\vec{H} \cdot \vec{N})^n$

#### Spot Light Source
- $\vec{L}:$ Light vector, $\vec{L_D}:$ Light direction vector
- $\gamma:$ Spot angle, $\theta:$ Angle between $\vec{L}, \vec{L_D}$
- $\Rightarrow \begin{cases} \theta \le \gamma &\Rightarrow \text{inside} \rightarrow \text{illuminated} \\ \theta > \gamma &\Rightarrow \text{outside} \rightarrow \text{not-illuminated} \end{cases}$

#### Hot To Do Light Attenuation
- $I_p \xrightarrow{d} \text{Object} \xrightarrow{I_{dc\lambda}} i_{\lambda}$
- $\Rightarrow \begin{cases} \text{Distance attenuation}: &f_{att} = (a_0 + a_1d + a_2d^2)^{-1} \\ \text{Atmospher attenuation}: &i_\lambda' = S_0i_\lambda + (1-S_0)i_{dc\lambda} \end{cases}$
- $\Rightarrow \begin{cases} z < z_f &\Rightarrow S_0 = S_f \\ z \in [z_f, z_b] &\Rightarrow S_0 = \frac{S_b - S_f}{z_b - z_f}(z - z_f) + S_f \\ z > z_b &\Rightarrow S_0 = S_b \end{cases}$

### Multiple Light Sources
- $i_\lambda = \underbrace{(K_ai_{a\lambda})o_{d\lambda}}_\text{Ambient Light} + \underbrace{(\textstyle\sum_{l=1}^N{f_{att,l}K_di_{p\lambda,l}(\vec{N} \cdot \vec{L_l})}) o_{d\lambda}}_\text{Diffuse Light} + \underbrace{(\textstyle\sum_{l=1}^N{f_{att,l}K_si_{p\lambda,l}(\vec{R_l} \cdot \vec{V})^n})}_\text{Specular Light}$
- If $i_\lambda > 1$:
    - Clamp $\rightarrow$ force it to be $1$
    - Normalizing $\rightarrow$ find the max value of all pixels in all images

## 3D Shading
### Concepts
- Lighting: *Ambient light, diffuse light, specular light*
    - $\Rightarrow$ To illuminate a specific point in WS
    - $\Rightarrow$ Illumination is made in WS
        - find out $I\ (i_r, i_g, i_b)$
        - do it from point to point in WS
- Shading:
    - Figure out the color $(r, g, b)$ in SS from the results of illumination in WS.
    - SS: pixel based $\Rightarrow$ find  $(r, g, b)$ of each pixel
- Shading types:
    - Flat Shading
    - Gouraud Shading: *smooth shading*
    - Phong Shading: *smooth shading*

### Flat Shading (Constant Shading)
- Pick up a point on a polygon to illuminate
- Find the normal of the polygon
- Illuminate the point *(Using lighting model)*
    - $I\ (i_r, i_g, i_b):$ we assume the whole polygon is with this $I$
- Save the illumination color for the polygon

### Gouraud Shading (Color Interpolation Shading, Intensity Interpolation Shading)
1. In WS, illuminate each vertex of the object
    - Figure the position of each vertex in WS *(OS $\rightarrow$ WS)*
    - Figure the normal of each vertex in WS
        - $\Rightarrow$ Averaging the normals of all neighbor polygons
        - $\Rightarrow \vec{N} = \frac{\sum{\vec{N_i}}}{|\sum{\vec{N_i}}|}$
    - Make illumination of the vertex
2. In SS, during polygon filling, determine the color of each pixel inside the polygon.
    We use "interpolation technique" $\Rightarrow$ Bi-linear Interpolation
    ![](https://i.imgur.com/pm7NRN2.png =450x)
    1. Calculate the scan-line position:
        - $y_a = y \Rightarrow \begin{cases} \frac{x_a - x_3}{x_2 - x_3} = \frac{y_a - y_3}{y_2 - y_3} &\Rightarrow \text{find } x_a \\ \frac{r_a - r_3}{r_2 - r_3} = \frac{y_a - y_3}{y_2 - y_3} &\Rightarrow \text{find } r_a \\ \frac{g_a - g_3}{g_2 - g_3} = \frac{y_a - y_3}{y_2 - y_3} &\Rightarrow \text{find } g_a \\ \frac{b_a - b_3}{b_2 - b_3} = \frac{y_a - y_3}{y_2 - y_3} &\Rightarrow \text{find } b_a \end{cases}$
        - $y_b = y \Rightarrow \begin{cases} \frac{x_b - x_1}{x_2 - x_1} = \frac{y_b - y_1}{y_2 - y_1} &\Rightarrow \text{find } x_b \\ \frac{r_b - r_1}{r_2 - r_1} = \frac{y_b - y_1}{y_2 - y_1} &\Rightarrow \text{find } r_b \\ \frac{g_b - g_1}{g_2 - g_1} = \frac{y_b - y_1}{y_2 - y_1} &\Rightarrow \text{find } g_b \\ \frac{b_b - b_1}{b_2 - b_1} = \frac{y_b - y_1}{y_2 - y_1} &\Rightarrow \text{find } b_b \end{cases}$
    2. On scan-line y, any point $(x_i, y_i)$ between $(x_a, y_a), (x_b, y_b)$, we need to calculate its $(r_i, g_i, b_i)$:
        - $y_i = y,\ x_i\ (a < i < b) \Rightarrow \begin{cases} \frac{r_i - r_b}{r_a - r_b} = \frac{x_i - x_b}{x_a - x_b} &\Rightarrow \text{find } r_i \\ \frac{g_i - g_b}{g_a - g_b} = \frac{x_i - x_b}{x_a - x_b} &\Rightarrow \text{find } g_i \\ \frac{b_i - b_b}{b_a - b_b} = \frac{x_i - x_b}{x_a - x_b} &\Rightarrow \text{find } b_i \end{cases}$

### Phong Shading
- Transfer each pixel in SS back to WS and find out how it should be illuminated
1. In WS, for each vertex
    - Store its position
    - Calculate ots normal and store it
2. In SS, for any $(x, y)$
    - Figure out its normal in WS
        ![](https://i.imgur.com/7Y2uhpj.png =450x)
        1. $y_a = y_i \Rightarrow \begin{cases} \frac{x_a - x_3}{x_4 - x_3} = \frac{y_a - y_3}{y_4 - y_3} &\Rightarrow \text{find } x_a \\ \frac{n_{ax} - n_{3x}}{n_{4x} - n_{3x}} = \frac{y_a - y_3}{y_4 - y_3} &\Rightarrow \text{find } n_{ax} \\ \frac{n_{ay} - n_{3y}}{n_{4y} - n_{3y}} = \frac{y_a - y_3}{y_4 - y_3} &\Rightarrow \text{find } n_{ay} \\ \frac{n_{az} - n_{3z}}{n_{4z} - n_{3z}} = \frac{y_a - y_3}{y_4 - y_3} &\Rightarrow \text{find } n_{az} \end{cases}$
        2. $y_b = y_i \Rightarrow \begin{cases} \frac{x_b - x_3}{x_2 - x_3} = \frac{y_b - y_3}{y_2 - y_3} &\Rightarrow \text{find } x_b \\ \frac{n_{bx} - n_{3x}}{n_{2x} - n_{3x}} = \frac{y_b - y_3}{y_2 - y_3} &\Rightarrow \text{find } n_{bx} \\ \frac{n_{by} - n_{3y}}{n_{2y} - n_{3y}} = \frac{y_b - y_3}{y_2 - y_3} &\Rightarrow \text{find } n_{by} \\ \frac{n_{bz} - n_{3z}}{n_{2z} - n_{3z}} = \frac{y_b - y_3}{y_2 - y_3} &\Rightarrow \text{find } n_{bz} \end{cases}$
        3. For each $(x, y)$:
            $\Rightarrow \begin{cases} \frac{x - x_a}{x_b - x_a} = \frac{n_x - n_{ax}}{n_{bx} - n_{ax}} &\Rightarrow \text{find } n_x \\ \frac{x - x_a}{x_b - x_a} = \frac{n_y - n_{ay}}{n_{by} - n_{ay}} &\Rightarrow \text{find } n_y \\ \frac{x - x_a}{x_b - x_a} = \frac{n_z - n_{az}}{n_{bz} - n_{az}} &\Rightarrow \text{find } n_z \end{cases}$
    - Figure out its position $(x^{3D}, y^{3D}, x^{3D})$ in WS
        ![](https://i.imgur.com/wVk4nlW.png =700x)
        1. $y^{2D}_a = y, y^{2D}_b = y \Rightarrow x^{2D}_a = ?,\ x^{2D}_b = ?$
        2. $x^{2D}_a \Rightarrow x^{3D}_a = ?,\ y^{2D}_a \Rightarrow y^{3D}_a = ?,\ y^{2D}_a \Rightarrow z^{3D}_a = ?$
            $x^{2D}_b \Rightarrow x^{3D}_b = ?,\ y^{2D}_b \Rightarrow y^{3D}_b = ?,\ y^{2D}_b \Rightarrow z^{3D}_b = ?$
        3. On scan-line y, between $(x_a, y_a), (x_b, y_b)$, for each $(x^{2D}, y^{2D})$:
            $\Rightarrow x^{3D} = ?,\ y^{3D} = ?,\ z^{3D} = ?$
    - Illuminate it in WS
        - For each $(x, y)$ in SS:
        - Using $(x^{3D}, y^{3D},\ z^{3D}), (n_x, n_y, n_z)$ in WS
        - $\Rightarrow$ Calculate $I\ (i_r, i_g, i_b)$
    - Put it to $(x, y)$
        - Assign $I\ (i_r, i_g, i_b)$ to $(x, y)$ in SS


## Appendix
### Barycentric Interpolation
- $\alpha + \beta + \gamma = 1$
- $p_t = \alpha p_0 + \beta p_1 + \gamma p_2$


### Perspective Correct Barycentric Interpolation
- $w_t = (\frac{\alpha}{w_0} + \frac{\beta}{w_1} + \frac{\gamma}{w_2})^{-1}$
- $\begin{cases} \alpha' = \frac{w_t}{w_0}\alpha \\ \beta' = \frac{w_t}{w_1}\beta \\ \gamma' = \frac{w_t}{w_2}\gamma \end{cases}$

