GAMES101 - Overview of Computer Graphics

Lecturer: Lingqi Yan

Lecture Videos | Course Site | HW Site

Linear Algebra (Lec. 2)

Cross Product

• Check whether a point $P$$P$ is on the left side of the line $\overrightarrow{AB}$$\vec{AB}$: $\overrightarrow{AB}\times \overrightarrow{AP}>0$$\vec{AB} \times \vec{AP} > 0$ (left); $\overrightarrow{AB}\times \overrightarrow{AP}<0$$\vec{AB} \times \vec{AP} < 0$ (right)

• Check whether a point $P$$P$ is in a triangle $\Delta ABC$$ΔABC$ or not: $\overrightarrow{AB}\times \overrightarrow{AP}>0$$\vec{AB} \times \vec{AP} > 0$ & $\overrightarrow{BC}\times \overrightarrow{BP}>0$$\vec{BC} \times \vec{BP} > 0$ & $\overrightarrow{CA}\times \overrightarrow{CP}>0$$\vec{CA} \times \vec{CP} > 0$ (inside)

  (Corner case: $\times$$\times$ product = 0, should be defined)

Matrices

Product can be operated: $A\cdot B=(M\times N)(N\times P)$$A \cdot B = (M\times N) (N\times P)$ (OK)

• Dot Product: $\begin{array}{c}\overrightarrow{a}\cdot \overrightarrow{b}={\overrightarrow{a}}^T\overrightarrow{b}=\left(\begin{array}{ccc}{x}_a& y_a& z_a\end{array}\right)\cdot \left(\begin{array}{c}{x}_b\\ y_b\\ z_b\end{array}\right)=\left(\begin{array}{ccc}{x}_a{x}_b& y_a{y}_b& z_a{z}_b\end{array}\right)\end{array}$$\vec{a} \cdot \vec{b} = \vec{a}^T \vec{b} = \begin{pmatrix} x_a & y_a & z_a\end{pmatrix} \cdot \begin{pmatrix} x_b \\ y_b \\ z_b\end{pmatrix} = \begin{pmatrix} x_ax_b & y_ay_b & z_az_b\end{pmatrix}$
• Cross Product: $\begin{array}{c}\overrightarrow{a}\times \overrightarrow{b}=A^{\ast }b=\left(\begin{array}{ccc}0& -z_a& y_a\\ z_a& 0& -x_a\\ -y_a& x_a& 0\end{array}\right)\left(\begin{array}{c}{x}_b\\ y_b\\ z_b\end{array}\right)\end{array}$$\vec{a} \times \vec{b} = A^* b =\begin{pmatrix} 0 & -z_a & y_a \\ z_a & 0 & -x_a \\ -y_a & x_a & 0\end{pmatrix} \begin{pmatrix} x_b \\ y_b \\ z_b\end{pmatrix}$

Transformation (Lec. 3-4)

Transformation

1. Scale Matrix: Ratio s:

   

   $$\begin{array}{c}{x}^{\prime }=sx;y^{\prime }=sy\iff \left[\begin{array}{c}{x}^{\prime }\\ y^{\prime }\end{array}\right]=\left[\begin{array}{cc}{s}_x& 0\\ 0& s_y\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]\end{array}$$

2. Reflection Matrix:

   

   $$\begin{array}{c}\{\begin{array}{}{x}^{\prime }=-x\\ y^{\prime }=y\end{array}\iff \left[\begin{array}{c}{x}^{\prime }\\ y^{\prime }\end{array}\right]=\left[\begin{array}{cc}-1& 0\\ 0& 1\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]\end{array}$$

3. Shear Matrix:

   

   $$\left[\begin{array}{c}{x}^{\prime }\\ y^{\prime }\end{array}\right]=\left[\begin{array}{cc}1& a\\ 0& 1\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]$$

4. Rotate (2D) around (0, 0), counter-clock

   

   $$\begin{array}{c}{R}_{\theta }=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]\end{array}$$

5. Translation (Not linear transformation)

   

   $$\begin{array}{c}\{\begin{array}{}{x}^{\prime }=x+t_x\\ y^{\prime }=y+t_y\end{array}\iff \left[\begin{array}{c}{x}^{\prime }\\ y^{\prime }\end{array}\right]=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]+\left[\begin{array}{c}{t}_x\\ t_y\end{array}\right]\end{array}$$

Homogeneous Coordinates

(Add a third coordinate - w-coordinate)

• 2D point = (x, y, 1)^T

• 2D vector = (x, y, 0)^T （平移不变性：Direction and magnitude only）

  $\begin{array}{c}\Rightarrow \left(\begin{array}{c}{x}^{\prime }\\ y^{\prime }\\ w^{\prime }\end{array}\right)=\left(\begin{array}{ccc}1& 0& t_x\\ 0& 1& t_y\\ 0& 0& 1\end{array}\right)\left(\begin{array}{c}x\\ y\\ 1\end{array}\right)=\left(\begin{array}{c}x+t_x\\ y+t_y\\ 1\end{array}\right)\end{array}$$\Rightarrow \begin{pmatrix} x' \\ y' \\ w'\end{pmatrix} = \begin{pmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1\end{pmatrix}\begin{pmatrix} x \\ y \\ 1\end{pmatrix} = \begin{pmatrix} x+t_x \\ y+t_y \\ 1\end{pmatrix}$ In homog. coord. $\left(\begin{array}{c}x\\ y\\ w\end{array}\right)$$\begin{pmatrix} x \\ y \\ w\end{pmatrix}$ in 2-D point: $\left(\begin{array}{c}x/w\\ y/w\\ 1\end{array}\right)(w\ne 1)$$\begin{pmatrix} x/w \\ y/w \\ 1\end{pmatrix} (w\neq 1)$

• Vector + Vector = Vector (0 + 0)

  Point - Point = Vector (1 - 1)

  Point + Vector = Point (0 + 1)

  Point + Point = ?? (1 + 1) (Actually, Mid point)

Affine Transformation

仿射

Affine map = linear map + translation

$\begin{array}{c}\Rightarrow \left(\begin{array}{c}{x}^{\prime }\\ y^{\prime }\\ 1\end{array}\right)=\left(\begin{array}{ccc}a& b& t_x\\ c& d& t_y\\ 0& 0& 1\end{array}\right)\left(\begin{array}{c}x\\ y\\ 1\end{array}\right)\end{array}$$\Rightarrow \begin{pmatrix} x' \\ y' \\ 1\end{pmatrix} = \begin{pmatrix} a & b & t_x \\ c & d & t_y \\ 0 & 0 & 1\end{pmatrix}\begin{pmatrix} x \\ y \\ 1\end{pmatrix}$ Dimension rises (costs)

Inverse Transformation

$M\to M^{-1}$$M\rightarrow M^{-1}$

Composite Transform

Transformation Ordering Matters

Notice that the matrices are applied right to left（无交换律 但有结合律）

e.g. $\begin{array}{c}{T}_{(1,0)}\cdot R_{45}\cdot \left(\begin{array}{c}{x}^{\prime }\\ y^{\prime }\\ 1\end{array}\right)\end{array}$$T_{(1,0)}\cdot R_{45} \cdot \begin{pmatrix} x' \\ y' \\ 1\end{pmatrix}$: $R_{45}\to T_{(1,0)}$$R_{45} \rightarrow T_{(1,0)}$; $\begin{array}{c}{A}_n(....(A_2(A_1(x)))=A_n\cdot ...\cdot A_2\cdot A_1\cdot \left(\begin{array}{c}{x}^{\prime }\\ y^{\prime }\\ 1\end{array}\right)\end{array}$$A_n(....(A_2(A_1(x))) = A_n \cdot ... \cdot A_2\cdot A_1\cdot \begin{pmatrix} x' \\ y' \\ 1\end{pmatrix}$

Pre-multiply n matrices to obtain a single matrix representing combined transform (for performance)

Example: (Decomposing)

Rotate around point C:

Representation: $T(c)\cdot R\cdot T(-c)$$T(c)\cdot R\cdot T(-c)$ (Move to the original point - rotate - move back (-c))

3D Transformation

• 3D point = (x, y, z, 1)^T

• 3D vector = (x, y, z, 0)^T

  ~ (x/w, y/w, z/w)

Homogeneous Coordinates

$\begin{array}{c}\Rightarrow \left(\begin{array}{c}{x}^{\prime }\\ y^{\prime }\\ z^{\prime }\\ 1\end{array}\right)=\left(\begin{array}{cccc}a& b& c& t_x\\ d& e& f& t_y\\ g& h& i& t_z\\ 0& 0& 0& 1\end{array}\right)\left(\begin{array}{c}x\\ y\\ z\\ 1\end{array}\right)\end{array}$$\Rightarrow \begin{pmatrix} x' \\ y' \\ z' \\1 \end{pmatrix} = \begin{pmatrix} a & b & c & t_x \\ d & e & f & t_y \\ g & h & i & t_z \\ 0 & 0 & 0 & 1\end{pmatrix}\begin{pmatrix} x \\ y \\ z \\ 1\end{pmatrix}$

Order: Linear transformation first, then translation（先线性变换，再平移）

Rotate around Axis

x-axis: $(\overrightarrow{y}\times \overrightarrow{z}=\overrightarrow{x})$$(\vec{y}\times\vec{z} = \vec{x})$ $\begin{array}{c}{R}_x(\alpha )=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& \cos \alpha & -\sin \alpha & 0\\ 0& \sin \alpha & \cos \alpha & 0\\ 0& 0& 0& 1\end{array}\right)\end{array}$$R_x(\alpha) = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos\alpha & -\sin\alpha & 0 \\ 0 & \sin\alpha & \cos\alpha & 0 \\ 0 & 0 & 0 & 1\end{pmatrix}$ z-axis: $(\overrightarrow{x}\times \overrightarrow{y}=\overrightarrow{z})$$(\vec{x}\times\vec{y} = \vec{z})$ $\begin{array}{c}{R}_z(\alpha )=\left(\begin{array}{cccc}\cos \alpha & -\sin \alpha & 0& 0\\ \sin \alpha & \cos \alpha & 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\end{array}$$R_z(\alpha) = \begin{pmatrix} \cos\alpha & -\sin\alpha & 0 & 0 \\\sin\alpha & \cos\alpha & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix}$

y-axis: $(\overrightarrow{z}\times \overrightarrow{x}=\overrightarrow{y})$$(\vec{z}\times\vec{x} = \vec{y})$ $\begin{array}{c}{R}_y(\alpha )=\left(\begin{array}{cccc}\cos \alpha & 0& \sin \alpha & 0\\ 0& 1& 0& 0\\ -\sin \alpha & 0& \cos \alpha & 0\\ 0& 0& 0& 1\end{array}\right)\end{array}$$R_y(\alpha) = \begin{pmatrix} \cos\alpha & 0 & \sin\alpha & 0 \\ 0 & 1 & 0 & 0 \\ -\sin\alpha & 0 & \cos\alpha & 0 \\ 0 & 0 & 0 & 1\end{pmatrix}$ （y 轴方向是相反的）

Compose any 3D Rotations from R_x, R_y, R_z

${\mathbf{R}}_{xyz}(\alpha ,\beta ,\gamma )={\mathbf{R}}_x(\alpha ){\mathbf{R}}_y(\beta ){\mathbf{R}}_z(\gamma )$$\bold{R}_{xyz}(\alpha, \beta, \gamma) = \bold{R}_x(\alpha)\bold{R}_y(\beta)\bold{R}_z(\gamma)$

• Rodrigues’ Rotation Formula: By angle $\alpha$$\alpha$ around axis n (Euler Angles)

  $$\begin{array}{c}\mathbf{R}(\mathbf{n},\alpha )=\cos \left(\alpha \right)\mathbf{I}+(1-\cos \left(\alpha \right))\mathbf{n}{\mathbf{n}}^T+\sin \left(\alpha \right)\underset{\mathbf{N}}{\underbrace{\left(\begin{array}{ccc}0& -n_z& n_y\\ n_z& 0& -n_x\\ -n_y& n_x& 0\end{array}\right)}}\end{array}$$

  

Viewing Transformations

View / Camera Transformation（视图变换）

MVP: Model-View Projection

(Model transformation: placing objects; View transformation: placing camera; Projection transformation)

Define camera first:

• Position: $\overrightarrow{e}$$\vec{e}$
• Look-at / gaze direction: $\overrightarrow{g}$$\vec{g}$
• Up direction: $\overrightarrow{t}$$\vec{t}$

Key Observation: If the camera and all objects move together, the “photo” will be the same => Transform to: the origin with up @ Y, look @ -Z

Transformation Matrix $M_{\mathrm{view}}$$M_{\mathrm{view}}$ in math: $M_{\mathrm{view}}=R_{\mathrm{view}}{T}_{\mathrm{view}}$$M_{\mathrm{view}} = R_{\mathrm{view}}T_{\mathrm{view}}$ (Transformed to a std. coordinate)

$\begin{array}{c}{T}_{\mathrm{view}}=\left[\begin{array}{cccc}1& 0& 0& -x_e\\ 0& 1& 0& -y_e\\ 0& 0& 1& -z_e\\ 0& 0& 0& 1\end{array}\right]\end{array}$$T_{\mathrm{view}} = \begin{bmatrix}1 & 0 & 0 & -x_e \\ 0 & 1 & 0 & -y_e \\ 0 & 0 & 1 & -z_e \\ 0 & 0 & 0 & 1 \end{bmatrix}$； $\begin{array}{c}{R}_{\text{view }}=\left[\begin{array}{cccc}{x}_{\hat{g}\times \hat{t}}& y_{\hat{g}\times \hat{t}}& z_{\hat{g}\times \hat{t}}& 0\\ x_t& y_t& z_t& 0\\ x_{-g}& y_{-g}& z_{-g}& 0\\ 0& 0& 0& 1\end{array}\right]\end{array}$$R_{\text {view }}=\left[\begin{array}{cccc}x_{\hat{g} \times \hat{t}} & y_{\hat{g} \times \hat{t}} & z_{\hat{g} \times \hat{t}} & 0 \\ x_{t} & y_{t} & z_{t} & 0 \\ x_{-g} & y_{-g} & z_{-g} & 0 \\ 0 & 0 & 0 & 1\end{array}\right]$

(Also known as model-view transformation)

Projection Transformation

Orthographic Projection

Camera @ 0, Up @ Y, Look @ -Z. Translate & Scale the resulting rectangle to [-1, 1]²

(Looking at / along -Z is making near and far not intuitive (n > f). OpenGL uses left hand coordinates)

In general, map a cuboid [l, r] x [b, t] x [f, n] to canonical cube [-1, 1]³

Transformation Matrix: $\begin{array}{c}{M}_{\text{ortho }}=\left[\begin{array}{cccc}\frac{2}{r-l}& 0& 0& 0\\ 0& \frac{2}{t-b}& 0& 0\\ 0& 0& \frac{2}{n-f}& 0\\ 0& 0& 0& 1\end{array}\right]\left[\begin{array}{cccc}1& 0& 0& -\frac{r+l}{2}\\ 0& 1& 0& -\frac{t+b}{2}\\ 0& 0& 1& -\frac{n+f}{2}\\ 0& 0& 0& 1\end{array}\right]\end{array}$$M_{\text {ortho }}=\left[\begin{array}{cccc}\frac{2}{r-l} & 0 & 0 & 0 \\ 0 & \frac{2}{t-b} & 0 & 0 \\ 0 & 0 & \frac{2}{n-f} & 0 \\ 0 & 0 & 0 & 1\end{array}\right]\left[\begin{array}{cccc}1 & 0 & 0 & -\frac{r+l}{2} \\ 0 & 1 & 0 & -\frac{t+b}{2} \\ 0 & 0 & 1 & -\frac{n+f}{2} \\ 0 & 0 & 0 & 1\end{array}\right]$ (Translate center 0; Scale 2)

Perspective Projection (Most common)

(Not parallel)

(Similar triangle $y^{\prime }=\frac{n}{z}y$$y' = \frac{n}{z} y$)

Process: Frustum（视锥）- (n - n, f - f) - Cuboid - Orthographic Proj. (M_o)

（近平面不变，远平面中心不变)

In homogeneous coordinates:

$\begin{array}{c}\left(\begin{array}{l}x\\ y\\ z\\ 1\end{array}\right)\Rightarrow \left(\begin{array}{c}nx/z\\ ny/z\\ \text{ unknown }\\ 1\end{array}\right)\begin{array}{c}\text{ mult. }\\ \text{ by z }\\ ==\end{array}\left(\begin{array}{c}nx\\ ny\\ \text{ still unknown }\\ z\end{array}\right)\end{array}$$\left(\begin{array}{l}x \\ y \\ z \\ 1\end{array}\right) \Rightarrow\left(\begin{array}{c}n x / z \\ n y / z \\ \text { unknown } \\ 1\end{array}\right) \begin{gathered}\text { mult. } \\ \text { by z } \\ ==\end{gathered}\left(\begin{array}{c}n x \\ n y \\ \text { still unknown } \\ z\end{array}\right)$; Replace z with n; $\begin{array}{c}{M}_{p\to o}=\left(\begin{array}{cccc}n& 0& 0& 0\\ 0& n& 0& 0\\ 0& 0& n+f& -nf\\ 0& 0& 1& 0\end{array}\right)\end{array}$$M_{p\rightarrow o} = \begin{pmatrix}n & 0 & 0 & 0 \\ 0 & n & 0 & 0 \\ 0 & 0 & n+f & -nf \\ 0 & 0 & 1 & 0 \end{pmatrix}$

$M_p=M_o\cdot M_{p\to o}$$M_p = M_o \cdot M_{p\rightarrow o}$

Vertical Field of View (fovY) (Assuming symmetry: l = -r; b = -t)

$\tan \frac{\text{fovY}}{2}=\frac{t}{|n|}$$\tan\frac{\text{fovY}}{2} = \frac{t}{|n|}$; $\text{Aspect}=\frac{r}{t}$$\text{Aspect} = \frac{r}{t}$

Rasterization (Lec. 5-7)

Rasterize

Rasterize = Draw onto the screen

Define Screen Space: Pixel: (0, 0) - (Width - 1, Height - 1)（均匀小方块）; Centered @ (x + 0.5, y + 0.5) (Irrelavent to z)

$\begin{array}{c}{M}_{\text{viewport}}=\left(\begin{array}{cccc}\frac{width}{2}& 0& 0& \frac{width}{2}\\ 0& \frac{height}{2}& 0& \frac{height}{2}\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\end{array}$$M_{\text{viewport}} = \begin{pmatrix} \frac{width}{2} & 0 & 0 & \frac{width}{2} \\ 0 & \frac{height}{2} & 0 & \frac{height}{2} \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$

Sampling (Approximate a Triangle)

Rasterization as 2D sampling

For triangles, each pixel is whether inside / outside should be checked.

xxxxxxxxxx
for (int x = 0; x < xmax; ++x)
    for (int y = 0; y < ymax; ++y)
        image[x][y] = inside(tri, x + 0.5, y + 0.5);

Evaluating inside(tri, x, y)

3 cross products: $\overrightarrow{AB}$$\vec{AB}$, $\overrightarrow{BC}$$\vec{BC}$, $\overrightarrow{CA}$$\vec{CA}$ (Same symbol = inside)

(Want: All required points (pixels) inside the triangle)

Edge cases: covered by both tri. 1 and 2: Not process / specific

Instead of checking all pixels on the screen, using incremental triangle traversal / a bouding box (AABB) can sometimes be faster

Suitable for thin and rotated triangles

Artifacts

(Error / Mistakes / Inaccuracies)

Jaggies (Too low sampling rate) / Noire / Wagon wheel effect (Signal changing too fast for sampling)

Idea: Blur - Sample

Frequency Domain

In freq. domain: $f=\frac{1}{T}$$f= \frac{1}{T}$

Fourier Transform:

(Higher freq. needs faster sampling. Or samples erroneously a low freq. signal)

Filtering: Getting rid of certain freq. contents (high / low / band / ...)

Filter out high freq. (Blur) - Low pass filter (e.g. Box function)

Theorem: Spatial domain · Filter (Convolution Kernel) = ...

$\downarrow$$\downarrow$ $\mathcal{F}$$\mathcal{F}$ $F(\omega )={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}f(x)e^{-2\pi i\omega x}dx$$F(\omega)=\int_{-\infty}^{\infty} f(x) e^{-2 \pi i \omega x} d x$ $\uparrow$$\uparrow$ Inverse Fourier Transform

Fourier domain $\times$$\times$ Fourier filter = ...

• Convolution（卷积）: （加权平均滤波器）Product in spatial domain = Convolution in frequency domain

  Wider Kernal = Lower Frequency (Blurer)

Sampling = Repeating Frequency Contents

• Aliasing = Mixing freq. contents (sampling too slow)

  

  Reduction: Increasing sampling rate; Antialiasing (Blur - Sample, Make F contents "narrower")

• Antialiasing = Limiting, then repeating

  

Solution: Convolve $f(x.y)$$f(x. y)$ by a 1-pixel box-blur & Sample pixel's center

Antialiasing Techniques

MSAA (Multisample Antialiasing)

By supersampling (same effects as blur, then sampling) (1 pixel -> 2x2 / 4x4 & Average)

Cost: Increase the computation work (4x4 = 16 times) - Key pixel distribution

FXAA (Fast Approximation AA)

后期处理降锯齿，使用边界

TAA (Temporal AA)

Use the previous one frame for AA

Super Resolution (DLSS - Deep Learning Supersampling)

Visibility / Occlusion

Z (Depth) Buffering

深度缓存

Point Algorithm（由远到近 - 不好处理相互重叠的关系）

Z-buffer: Frame buffer for color values; z-buffer for depth (Smaller z - closer (darker); Larger z - farther (lighter))

Algorithm during Rasterization

xxxxxxxxxx
for (each triangle T)
    for (each sample (x, y, z) in T)
        if (z < zbuffer[x, y])          // Closest sample so far （是否更新该像素，判断 z）
            framebuffer[x, y] = rgb;    // Update color
            zbuffer[x, y] = z;          // Update depth （相同的可更可不更 - 可能为抖动）
        else
            ;                         // Do nothing

Complexity: O(n)

For n triangles, only check. No other relativity.

Order doesn't matter

Supplement: Shadow Mapping

After Lec. 12

An image-space algorithm, widely used for early animations and every 3D video game

Key idea: The point not in shadow must be seen both by the light and the camera

Hard shadow: Use 0 & 1 only to represent in shadow or not

(between 0 and 1 -> soft shadow: by multiple light sources / source size)

Approaches

• Pass 1: Render from light (Rasterize the view with the light source)

  Depth image from light source

  

• Pass 2A: Render from eye

  Standard image with depth from eye

  

• Pass 2B: Project to light

  Project visible points in eye view back to light source

  Orange line: (Reprojected) depths match for light and eye. VISIBLE

  Red line: (Reprojected) depths from light and eye are not the same. BLOCKED!!

  

Problems with Shadow Maps

• Hard shadows (point lights only)
• Quality dep on shadow map resolution (gen problem with image-based techniques)
• Involves equality comparison of floating point depth values means issues of scales / bias / tolerance

Shading (Lec. 7-10)

Apply a material to an object

Shading Model (Blinn-Phong Reflectance Model)

Light reflected towards camera.

Viewer direction, v; Surface normal, n; Light direction, l (for each of many lights); Surface parameters (color, shininess, …)

Shading is local - No shadows will be generated

Diffuse Reflection

Light is scattered uniformly in all directions (Surface color is the same for all viewing direction)

Light Falloff (Beer Lambert's Law)

Lambertian (Diffuse) Shading

Shading independent of view direction

($L_d$$L_d$​ - diffusely reflected light; $k_d$$k_d$​ - diffuse coefficient (color), $k_d=0$$k_d = 0$: black (all absorbed), $1$$1$: white; $(I/r^2)$$(I/r^2)$​ - energy arrived at the shading point; $max(0,\mathbf{n}\cdot \mathbf{l})$$\max(0, \mathbf{n} \cdot \mathbf{l})$​ - energy received by the shading point​; irrelavent to $\hat{v}$$\hat{v}$)

Specular

Intensity depends on view direction (Bright near mirror reflection direction)

$\hat{v}$$\hat{v}$ closes to mirror direction - half vector near normal

$\mathbf{h}=\text{bisector}(\mathbf{v},\mathbf{l})=\frac{\mathbf{v}+\mathbf{l}}{||\mathbf{v}+\mathbf{l}||}$$\bold{h} = \text{bisector} (\bold{v},\bold{l}) = \frac{\bold{v}+\bold{l}}{||\bold{v}+\bold{l}||}$​ - 半程向量

($L_s$$L_s$​ - specularly reflected light; $k_s$$k_s$​ - specular coefficient; $p$$p$ - narrows the reflection lobe)

$p$$p$ 越大，反射高光面积越小；$k_s$$k_s$​ 越大，高光越明显

(Only use $\mathbf{R}$$\bold{R}$ and $\mathbf{l}$$\bold{l}$ (mirror) - Phong relax model)

Ambient

Not depend on anything

Fake approximation

$L_a=k_a{I}_a$$L_a = k_a I_a$​ ($L_a$$L_a$​ - reflected ambient light; $k_a$$k_a$ - ambient coefficient)

Summary

Shading Frequencies

(Face / Vertex / Pixel)

Shading Methods

• Shade each triangle (flat shading) - Not good for smooth surface
• Shade each vertex (Gouraud shading) - Interporate colors from vertices
• Shade each pixel (Phong shading) - Full shading model each pixel (Not the Blinn-Phong Reflectance Model)

Pre-Vertex Normal Vectors

Vertex normal - Average surrounding face normals $N_v=\frac{\sum _i{N}_i}{||\sum _i{N}_i||}$$N_v =\frac{\sum_i N_i}{||\sum_i N_i||}$

~ Barycentric interpolation of vertex normals (Need to normalize)

Graphics (Real-time Rendering) Pipeline

~ GPU

• Input: Model, View, Projection transforms
• Rasterization: Sampling triangle coverage
• Fragment Processing: Z-Buffering visibility test / Shading / Texture mapping

Texture Mapping

纹理映射 - UV ((u,v) coordinate) ($u,v\in [0,1]$$u, v \in [0, 1]$)

Barycentric Coordinates

Interpolation Access Triangles

Specific values @ vertices / smoothly varing across triangles

Barycentric Coordinates

A coordinate system for triangles $(\alpha ,\beta ,\gamma )$$(\alpha, \beta, \gamma)$​​​​ (every point could be represented in this form). Inside the triangle if all three coordinates are non-negative

The barycentric coordinate of $A$$A$​ is: $(\alpha ,\beta ,\gamma )=(1,0,0)$$(\alpha, \beta, \gamma) = (1, 0, 0)$​ ; $(x,y)=\alpha A+\beta B+\gamma C=A$$(x,y) = \alpha A + \beta B + \gamma C =A$​

$(x,y)=\alpha A+\beta B+\gamma C$$(x,y) = \alpha A + \beta B + \gamma C$ ; $\alpha +\beta +\gamma =1$$\alpha + \beta + \gamma = 1$ $\alpha \le 1,\beta \le 1,\gamma \le 1$$\alpha\leq 1,\, \beta\leq 1,\, \gamma \leq1$

Geometric viewpoint — proportional areas: $\alpha =\frac{A_A}{A_A+A_B+A_C}$$\alpha = \frac{A_A}{A_A+A_B+A_C}$​​​ ; $\beta =\frac{A_B}{A_A+A_B+A_C}$$\beta = \frac{A_B}{A_A+A_B+A_C}$​​​ ; $\gamma =\frac{A_C}{A_A+A_B+A_C}$$\gamma = \frac{A_C}{A_A+A_B+A_C}$​​​

Centroid: $(\alpha ,\beta ,\gamma )=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$$(\alpha, \beta, \gamma) = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ ; $(x,y)=\frac{1}{3}A+\frac{1}{3}B+\frac{1}{3}C$$(x,y) = \frac{1}{3}A + \frac{1}{3} B + \frac{1}{3} C$ $(A_A=A_B=A_C=\frac{1}{3})$$(A_A = A_B = A_C = \frac{1}{3})$​

Express any point:

Color interpolation for every point: linear interpolation $V=\alpha V_A+\beta V_B+\gamma V_C$$V = \alpha V_A + \beta V_B + \gamma V_C$ (could be any property)

Disadvantage: Not invariant under projection (depth matters)

(3D - Use 3D interpolation OK; 2D - rather than use projection)

Apply: Diffuse Color

xxxxxxxxxx
for each rasterized screen sample (x,y)     // Usually a pixel center
    (u,v) = evaluate texture coordinate at (x,y)    // Applying Barycentric coordinates
    texcolor = texture.sample(u,v);
    set sample’s color to texcolor;     // Usually diffuse kd (Blinn-Phong)

Texture Magnification (AA)

(used for insufficient resolution)

Texel: A pixel on a texture（纹理元素 / 纹素）

Easy Cases

• Nearest
• Bilinear (Interpolation) - Pretty good results at reasonable costs
• Bicubic (Interpolation) - Instead of 4 points (bilinear), using 16 (4x4) points for 1 lerp

Bilinear Magnification

• Linear Interpolation (1D): $\mathrm{lerp}(x,v_0,v_1)=v_0+x(v_1-v_0)$$\mathrm{lerp} (x, v_0, v_1) = v_0 +x(v_1 - v_0)$​
• Helper Lerps: $u_0=\text{lerp}(s,u_{00},u_{10})$$u_0 = \text{lerp}(s,u_{00}, u_{10})$ ; $u_1=\mathrm{lerp}(s,u_{01},u_{11})$$u_1 = \mathrm{lerp} (s, u_{01}, u_{11})$ (Horizontal)
• Final Vertical Lerp: $f(x,y)=\mathrm{lerp}(t,u_0,u_1)$$f(x, y) = \mathrm{lerp} (t, u_0, u_1)$​ (Vertical)

Lerp - Linear Interpolation

Hard Cases

Problem of point sampling textures

(can be solved by supersampling but costly)

Near: Jaggies (Minification / Downsampling for too high resolution) ; Far: Moire (Upsampling)

Mipmap

Allowing (fast, approx., square) range queries

(Image Pyramid) "Mip Hierachy": level = D

• Estimate texture footprint using texture coordinates of neighboring screen samples

  

• $$D={\log }_{2}LL=max(\sqrt{{\left(\frac{du}{dx}\right)}^2+{\left(\frac{dv}{dx}\right)}^2},\sqrt{{\left(\frac{du}{dy}\right)}^2+{\left(\frac{dv}{dy}\right)}^2})$$

  层查询 - 后者为选择较大 L 是近似（UV)

Near - range quires in low D level Mipmap; Far - high D level

If want more continuous results: interpolation between levels

Trilinear Interpolation

Linear interpolation (lerp) based on continuous D value

Limitations

In far and complex region - Overblur (box)

• Anisotropic filtering（各向异性过滤）: look up axis-aligned rectangular zones（长方形区域搜寻）, but still have problems in diagonal footprints - Ripmap (need graphics memory, doesn't need high flops x3)
• EWA filtering (Time computing costs): use multiple look ups / weighted average. able to handle irregular footprints

Applications of Textures

Environmental Map

• Environmental Map: 有光从各个方向进入眼睛，所有光都有对应，用纹理映射环境光

  不记录深度，都认为是无限远

• Environmental Lighting: 环境光记录于球面 - 渲染时展开

  • Spherical EM (Problem: Prone to distortion (top and bottom))

  • Cube Map: A vector maps to cube point along that direction (6 square texture maps) - Less distortion but need direction for face computations

    $(u,v)=(1,1)$$(u, v) = (1, 1)$, $x=y=z$$x = y = z$​; $(u,v)=(0,0)$$(u, v) = (0, 0)$, $x=-y=-z$$x = -y = -z$

    Right face has $x>|y|$$x > |y|$ and $x>|z|$$x > |z|$

Textures Affecting Shading

Bump / Normal Mapping

Adding surface details without adding more triangles (Perturb surface normal per pixel)

未改变几何 - 产生凹凸错觉

• Perturb the nromal (in flatland)

  • Original surface normal: $n(p)=(0,1)$$n(p) = (0,1)$

  • Derivative @ p: $p=c\cdot [h(p+1)-h(p)]$$p = c\cdot[h(p+1) - h(p)]$

  • Perturbed normal: $n(p)=(-dp,1)$$n(p) = (-dp, 1)$​.normalized()

    

• Perturb the normal (in 3D) (local coordinates)

  • Original surface normal: $n(p)=(0,0,1)$$n(p) = (0,0,1)$
  • Derivatives @ p: $-\frac{dp}{du}=c_1\cdot [h(\mathbf{u}+1)-h(\mathbf{u})]$$-\frac{dp}{du} = c_1 \cdot [h(\mathbf{u}+1) - h(\mathbf{u})]$ ; $-\frac{dp}{dv}=c_2\cdot [h(\mathbf{v}+1)-h(\mathbf{v})]$$-\frac{dp}{dv} = c_2 \cdot [h(\mathbf{v}+1) - h(\mathbf{v})]$​
  • Perturbed normal: $n=(-\frac{dp}{du},-\frac{dp}{dv},1)$$n = (-\frac{dp}{du}, -\frac{dp}{dv}, 1)$.normalized()

Displacement Mapping

Uses the same texture as in bumping mapping, but actually moves vertices

• 3D Procedural Noise + Solid Modeling
• Provide Precomputed Shading
• 3D Texture and Volume Rendering

Geometry (Lec. 10-12)

Representing Ways

• Implicit: algebraic surface / level sets（等高线法）/ constructive solid geometry (Boolean) / distance functions / fractal ...

  (Don’t tell exact positions,tell spe. relationships. e.g. sphere: $x^2+y^2+z^2=1$$x^2 + y^2 + z^2 = 1$, generally $f(x,y,z)=0$$f(x, y, z) = 0$)

  Hard for sampling but easy for test in / outside

  Distance functions:

  

  

  Level Set: (CT / MRI)

  

• Explicit: point cloud / polygon-mesh (.obj) / subdivision / NURBS / ...

  (Generally, $f:{\mathbb{R}}^2\to {\mathbb{R}}^3:(u,v)\to (x,y,z)$$f: \R^2 \rightarrow \R^3: (u, v) \rightarrow (x, y, z)$)

  Hard to test in / outside but easy to sample

Curves

Bézier Curves (Explicit)

• 3 pt. - quadratic Bézier

  Connect $b_0$$b_0$ - all $b_0^2$$b_0^2$ - $b_2$$b_2$​ (every $t$$t$ in $[0,1]$$[0,1]$)

  

• 4 pt. - cubic Bézier

  

(De Casteljau’s Algorithm)

Evaluating Bézier Curves

Algebraic Formula

Bernstein form of a Bézier curve of order n:

(${\mathbf{b}}^n$$\mathbf{b}^n$​​ - Bezier curve order n (vector polynomial degree n); ${\mathbf{b}}_j$$\mathbf{b}_j$​​ - Bezier control points (vector in ${\mathbb{R}}^N$$\R^N$​​); $B_j^n$$B_j^n$​ - Bernstein polynomial (scalar polynomial of degree n))

where Bernstein polynomials:

At anywhere, sum of $b_i^3=1$$b_i^3=1$.

B-Splines

Could be adjusted partially

For C² cont. -> NURBS (Non-Uniform Rational B-Splines)

Surfaces

• Bicubic Bézier: 4x4 array -> surface
• Mesh Operations: subdivision / simplification / regularization

Bézier Surfaces

Extend Bézier curves to surfaces

Bicubic Bézier Surface Patch (4x4 array of control points)

Evaluating Surface Position for Parameters (u,v)

For bicubic Bézier surface patch:

Input: 4x4 control points; Output: 2D surface parameterized by $(u,v)$$(u,v)$ in $[0,1{]}^2$$[0,1]^2$

Method: Separable 1D de Casteljau Algorithm

(u,v)-separable application of de Casteljau algorithm:

• Use de Casteljau to evaluate point u on each of the 4 curves in u -> gives 4 control points for “moving” the Bézier curve
• Use 1D de Casteljau to evaluate point v on the “moving” curve

Mesh Operations: Geometry Processing

Subdivision (Upsampling)

Increase resolution

Loop Subdivision

Only for triangle faces

Intro more triangle meshes: Split triangles -> Update old / new vertices differently (according to weights)

• For new vertices: Update to $\frac{3}{8}\cdot (A+B)+\frac{1}{8}\cdot (C+D)$$\frac{3}{8} \cdot (A+B) + \frac{1}{8}\cdot (C+D)$
• For old vertices (e.g. degree 6 vertices): Update to $(1-nu)\cdot \text{original\_position}+u\cdot \text{neighbor\_position\_sum}$$(1- nu) \cdot \text{original\_position} + u \cdot \text{neighbor\_position\_sum}$

Catmull-Clack Subdivision (General Mesh)

Can be used for various types of faces

After several steps of Catmull-Clack subdivision:

Vertex Updating Rules (Quad Mesh)

• Face Point: $f=\frac{1}{4}(v_1+v_2+v_3+v_4)$$f = \frac{1}{4} (v_1 + v_2 +v_3+ v_4)$
• Edge Point: $e=\frac{1}{4}(v_1+v_2+f_1+f_2)$$e = \frac{1}{4} (v_1 + v_2 + f_1+f_2)$
• Vertex Point: $v=\frac{1}{16}(f_1+f_2+f_3+f_4+2(m_1+m_2+m_3+m_4)+4p)$$v = \frac{1}{16} (f_1 + f_2 +f_3 +f_4 + 2(m_1 + m_2 + m_3 + m_4) + 4p)$

using the average to make it smoother => similar to the method of blur

Simplification (Downsampling)

Reduce the mesh amount to enhance performance

Edge Collapse

Quadric Error Metrics (geometric error introduced)

New vertex should minimize its sum of square distance (L2 distance) to previously related triangle planes

-> could cause error changes of other edges => dynamically update the other affected (prior queue / …)

=> Greedy algorithm for optimization (easy for flat, hard to curvature)

Regularization (Same #triangles)

Improve quality

Ray Tracing (Lec. 13-16)

Rasterization cannot handle global effects well (fast approximation with low quality, but real time). However, soft shadows / especially for light bounces more than once

Ray Tracing is usually off-line, accurate but very slow

Ray Tracing Basis

Light Rays

• Light travels in straight lines (not correct)
• Light rays do not “collide” with each other if they cross (still not correct)
• Light rays travel from the light sources to the eye (but the physics is invariant under path reversal - reciprocity)

Ray Casting

Pinhole Camera Model

• Generate an image by casting one ray per pixel

• Check for shadows by sending a ray to the light

  

Generating Eye Rays

Shading Pixels (Local Only)

Recursive (Whitted-Style) Ray Tracing

Ray can travel through some (transparent / semi-transparent) media, but need to consider the energy loss

Ray-Surface Intersection

Ray Equation

Ray is defined by its origin and a direction vector

($\mathbf{r}$$\vb{r}$ - point along ray’; $t$$t$ - time; $\mathbf{o}$$\vb{o}$ - origin; $\mathbf{d}$$\vb{d}$ - normalized direction)

Ray Intersection

With Sphere

Sphere: $\mathbf{p}:(\mathbf{p}-\mathbf{c}{)}^2-R=0$$\vb{p}:\ (\vb{p-c})^2 - {R} = 0$

=> Solve for the intersection: $(\mathbf{o}+t\mathbf{d}-\mathbf{c}{)}^2-R^2=0$$(\vb{o} + t\vb{d} - \vb{c})^2 - R^2 = 0$

for a second order equation: $a{t}^2+bt+c=0$$at^2 + bt + c =0$

where $a=\mathbf{d}\cdot \mathbf{d}$$a = \vb{d}\cdot \vb{d}$; $b=2(\mathbf{o}-\mathbf{c})\cdot \mathbf{d}$$b= 2(\vb{o-c})\cdot \vb{d}$; $c=(\mathbf{o}-\mathbf{c})\cdot (\mathbf{o}-\mathbf{c})-R^2$$c = \vb{(o-c)\cdot (o-c)} - R^2$; $t=(-b\pm \sqrt{b^2-4ac})/2a$$t = (-b\pm \sqrt{b^2 - 4ac})/2a$

With Implicit Surface

• General implicit surface: $\mathbf{p}:f(\mathbf{p})=0$$\vb{p}:\ f(\vb{p}) = 0$
• Substitute ray equation: $f(\mathbf{o}+t\mathbf{d})=0$$f(\vb{o} + t\vb{d}) = 0$

Solve for real, positive roots:

• Sphere: $x^2+y^2+z^2=1$$x^2 +y ^2 + z^2 = 1$
• Dohnut: $(R-\sqrt{x^2+y^2}{)}^2+z^2=r^2$$(R - \sqrt{x^2 + y^2})^2 + z^2 = r^2$
• 3D heart: $(x^2+9y^2/4+z^2-1{)}^3=x^2{z}^3+9y^2{z}^3/80$$(x^2 + 9y^2/4 + z^2 - 1)^3 = x^2z^3 + 9y^2z^3/80$

With Triangle Mesh

Idea: Just intersect ray with each triangle (too slow) => can have 0, 1 intersections (ignoring multiple intersections)

-> Triangle is a plane => Ray-plane intersection + Test if inside triangle

• Plane Equation: $\mathbf{p}:(\mathbf{p}-{\mathbf{p}}^{\prime })\cdot \mathbf{N}=0$$\vb{p}:\ \vb{(p-p')\cdot N} = 0$ (if $\mathbf{p}$$\vb{p}$ satisfies; it’s on the plane, ${\mathbf{p}}^{\prime }$$\vb{p}'$ - one point on the plane)

• Solve for intersection:

  Set $\mathbf{p}=\mathbf{r}(t)$$\vb{p = r}(t)$ and solve for $t$$t$

  $(\mathbf{p}-{\mathbf{p}}^{\prime })\cdot \mathbf{N}=(\mathbf{o}+t\mathbf{d}-{\mathbf{p}}^{\prime })\cdot \mathbf{N}=0$$(\vb{p-p'})\cdot \vb{N} = (\vb{o} + t\vb{d} - \vb{p'}) \cdot \vb{N}= 0$

  $t=\frac{({\mathbf{p}}^{\prime }-\mathbf{o})\cdot \mathbf{N}}{\mathbf{d}\cdot \mathbf{N}}$$t= \frac{(\vb{p'-o})\cdot \vb{N}}{\vb{d\cdot N}}$ ; Check if $0\le t<\mathrm{\infty }$$0\le t < \infty$

Möller Trumbore Algorithm (for triangle problem)

A faster approach, giving barycentric coordinate directly

$\mathbf{O}+t\mathbf{D}=(1-b_1-b_2){\mathbf{P}}_0+b_1{\mathbf{P}}_1+b_2{\mathbf{P}}_2$$\vb{O} + t\vb{D} = (1- b_1- b_2) \vb{P}_0 + b_1 \vb{P}_1 + b_2 \vb{P}_2$ (where $b_1,b_2,(1-b_1-b_2)$$b_1, b_2, (1-b_1-b_2)$ are barycentric coordinates)

RHS: represent any point in the plane (sum of the coefficients is 1)

Costs = 1 div, 27 mul, 17 add

Need to check if $t\in [0,\mathrm{\infty })$$t\in [0,\infty)$ & inside triangle as well ($b_1,b_2,(1-b_1-b_2)>0$$b_1, b_2, (1-b_1-b_2) >0$)

Accelerating Ray-Surface (Triangle) Intersection

Problem: Naive algorithm (for every triangle) = #pixels x #triangles (x #bounces) (very slow)

Bounding Volumes

• Object fully contained in the volume
• If not hit the volume, it doesn’t hit the object
• Test BVol first then test object if it hits

Ray-AABB (Box) Intersection

Understanding: Box is the intersection of 3 pairs of slabs

Specifically: Axis-Aligned Bounding Box (AABB)

2D example: Compute intersections with slabs and take intersection of $t_{min}/t_{max}$$t_{\min}/t_{\max}$ intervals

• Key ideas:

  • The ray enters the box only when it enters all pairs of slabs
  • The ray exits the box as long as it exits any pair of slabs

• For each pair, calculate the $t_{min}$$t_{\min}$ & $t_{max}$$t_{\max}$ (negative is OK)

• For the 3D box: $t_{\text{enter}}=max(t_{min})$$t_{\text{enter}} = \max(t_{\min})$ & $t_{\text{exit}}=min(t_{max})$$t_{\text{exit}} = \min(t_{\max})$

• Results:

  • If $t_{\text{enter}}<t_{\text{exit}}$$t_{\text{enter}}<t_{\text{exit}}$ => the ray stays a while in the box (must intersect)

    But ray is not a line (should check whether $t$$t$ is negative for physical correctness)

  • If $t_{\text{exit}}<0$$t_{\text{exit}}<0$ => Box is “behind” the ray - No intersection

  • If $t_{\text{exit}}>=0$$t_{\text{exit}} >= 0$ and $t_{\text{enter}}<0$$t_{\text{enter}} <0$ => Ray originally inside the box (have intersection)

• Summary: ray and AABB intersect iff: $t_{\text{enter}}<t_{\text{exit}}$$t_{\text{enter}}< t_{\text{exit}}$ && $t_{\text{exit}}>=0$$t_{\text{exit}}>=0$

• Why Axis-Aligned:

  Slab perpendicular to x-axis: $t=\frac{{\mathbf{p}}_x^{\prime }-{\mathbf{o}}_x}{{\mathbf{d}}_x}$$t = \frac{\vb{p}'_x - \vb{o}_x}{\vb{d}_x}$ (1 sub, 1 div)

  

Acceleration with AABBs

Uniform Spatial Partitions (Grids)

Uniform Grids

Preprocess - Build Acceleration Grid

1. Find bounding box
2. Create grid
3. Store each object in overlaping cells

Ray-Scene Intersection

Find the first intersection (with the object) first. If found that the ray passes through a box in which there’s an obj -> test if intersects with the obj (NOT necessary)

(Ray intersect with boxes - fast; with obj - slower)

Step through grid in ray traversal order (-> similar to the method of drawing a line in the rasterization pipeline)

For each cell: test intersection with all objects stored at that cell

Resolution

Acceleration effects: One cell - no speedup; Too many cells - Inefficiency due to extraneous grid traversal

Heuristic: #cell = C * #objs; where C ≈ 27 in 3D

Usage

• Work well on large collections of objects that are distributed evenly in size and space
• Fail in “Teapot in a stadium” problem (distributed not evenly, a lot of empty space)

Spatial Partitions

Discretize the Bounding Boxes (in 3D)

• Oct-Tree: Split the bounding boxes evenly (in 3D so 8 branches)

  Stopping criteria -> until empty boxes / sufficiently small

• KD-Tree: Always split the bounding box in different direction after another (horizontally or vertically, e.g., Horizontally first, then vertically, then horizontally again …; In 3D: x -> y -> z -> x -> …) => distribution almost evenly (Similar properties as binary-tree)

• BSP-Tree: Not suitable for higher orders

KD-Tree

KD-Tree Pre-processing

Actually in every branch, the split should be applied every time (in the following plot, only show one of the splitted branch)

Data Structure for KD-Trees

• Internal nodes store:

  • Split axis: x-, y-, z-axis
  • Split position: coordinate of split plane along axis
  • Children: pointers to child nodes
  • No obj are stored in internal nodes

• Leaf nodes store:

  • List of objs

Traversing a KD-Tree

For the outer box have intersection (internal node) -> consider the sub-nodes (split1)

In sub-nodes: Leaf 1 (LHS) & internal (RHS) both have intersections -> internal node splits -> … -> intersections found (after traversing all nodes)

When have intersection with a leaf node of the box, the ray should find intersection with all the objects in this node

Problem:

• In 3D, KD-Tree is complex and not easy to be written (especially when triangles intersects with the box but not inside the box, …)
• Some objects can be counted several times (appears in various of leaf nodes)

Object Partitioning & Bounding Volume Hierarchy (BVH)

According to objects other than space, very popular

Main Idea

Can introduce some spec. stopping criteria

Property: No triangle-box intersections / No obj appears in more than one boxes

Problem: Boxes can overlap -> more researches to split obj

Summary: Building BVHs

• Find bounding box
• Recursively split set of objects in 2 subsets
• Recompute the bounding box of the subsets
• Stop when necessary
• Store objects in each leaf nodes

Subdivide a node:

• Choose a dimension to split
• Heuristic #1: Always choose the longest axis in node
• Heuristic #2: Split node at location of median objects (amount balance) -> quick splitting

Termination criteria:

• Heuristic: node contains few elements (e.g, < 5)

BVH Traversal (Pseudo Code)

xxxxxxxxxx
Intersect(Ray ray, BVH node) {
    if (ray misses node.bbox) return;
    
    if (node is leaf node) 
        test intersection with all objs;
        return closest intersection;
    
    hit1 = Intersect(ray, node.child1);
    hit2 = Intersect(ray, node.child2); // recursive
    
    return the closer of hit1, hit2;
}

Radiometry

Measurement system and units for illumination

Accurately measure the spatial properties of light

Terms: Radiant flux（辐射通量）, intensity, irradiance（辐射照度）, radiance（辐射亮度）

-> Light emitted from a source (radiant intensity) / light falling on a surface (irradiance) / light traveling along a ray (radiance)

Perform lighting calculations in a physically correct manner

Radiant Energy and Flux (Power)

• Radiant energy is the energy of electromagnetic radiation. Measured in units of joules: $Q[\mathrm{J}=\mathrm{Joule}]$$Q\ [\mathrm{J = Joule}]$

• Radiant flux (power) is the energy emitted, reflected, transmitted or received per unit time: $\mathrm{\Phi }=\frac{\mathrm{d}Q}{\mathrm{d}t}[\mathrm{W}=\mathrm{Watt}][\mathrm{lm}=\mathrm{lumen}{]}^{\ast }$$\Phi = \frac{\mathrm{d}Q}{\mathrm{d}t}\ [\mathrm{W = Watt}]\ [\mathrm{lm = lumen}]^*$

  Flux - #photons flowing through a sensor in unit time