# 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.
- Imperfect case:
- Sliver: a kind of aliasing
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
- 
- 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:
- $\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:
- $\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:
- $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:
- $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)
- 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
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
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
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}$
Sign in with Wallet
Connect another wallet