# 現代計算機圖形學入門 - 闫令琪

[網址](https://sites.cs.ucsb.edu/~lingqi/teaching/games101.html)

留言區推薦的 rasterization render c++教程：[tinyrenderer](https://github.com/ssloy/tinyrenderer)

此筆記不完全照表定週次編排，依內容調整

## L1 Overview of Computer Graphic

## L2 Review of Linear Algebra

Dot 結果的正負可用來判斷兩個向量是否同向
Cross 結果的方向可用來判斷兩個向量的左右（右手定則）

## L3 Transform

位移沒辦法用矩陣乘法表示，所以多引入一個維度（點是1、向量是0），變成 Homogeneous Coordinate（齊次座標，啥翻譯）就可以了
注意這是先線性變換再平移，因為先乘除後加減

線性變換 + 平移 = Affine transformation（仿射變換）



同時保留了點跟向量的性質，但定義 W != 1 or 0 時，x y 要除以 W，也就是說點跟點相加的結果是中點

### L4 Transformation Cont.

### 3D transformation

就矩陣運算，至於旋轉：
沿著三軸旋轉的公式，旋轉預設都是逆時針
因為沿Y軸逆時針轉是Z轉到X，不是X轉到Z，跟其他兩軸相反，所以需要多加個負號

這三個就可以組成任意一種旋轉角度，但是還有一個更方便的 [Rodrigues’ Rotation Formula](https://en.wikipedia.org/wiki/Rodrigues%27_rotation_formula) 可以直接算出向量V在沿著任意一個單位向量k逆時針旋轉θ度的結果，推導不難，可看，但不知道公式怎麼套

### Viewing transformation

MVP：Model transformation -> View(camera) transformation -> Perspective transformation
就是 移動物體 -> 移動相機 -> 成像

約定成俗，相機都是在原點往-Z方向看，以Y軸為上方

總之就是把物體轉換到以相機為原點的座標系（不太確定接下來的轉換在幹嘛）就不用做 View transformation，都做 Model transformation 就好

那物體如何轉成相機的座標系？

相機有3個向量，位置 $\vec{e}$、看向 $\hat{g}$、上方 $\hat{t}$，另一個軸就是 $\hat g \times \hat t$

先把 位置 $\vec e$ 移到原點再旋轉

與其找出一個旋轉矩陣把任意的 $g$、$t$、$g \times t$ 對齊成$-z$、$y$、$x$，不如反過來把$-z$、$y$、$x$（就(1,0,0)那些）轉成 $g$、$t$、$g \times t$，再找逆矩陣就是了，而且因為旋轉是正交矩陣，所以 $R^{-1} = R^T$，很好找


### Perspective transformation

分為 Orthographic projection（正交）、Perspective projectio（透視）

#### Orthographic projection

理論上就直接捨棄 Z 軸，再平移、縮放XY到[-1, 1]（約定俗成）就行

但實際上不會直接捨棄 Z，而是一樣平移縮放到[-1, 1]（不知道為啥）

正交投影公式，n 是 near、f 是 far，n > f，因為是 -Z 方向


#### Perspective Projection

把 Frustum 擠成 Cuboid 再做正交投影就是了

那要怎麼擠呢？怎麼找出這個矩陣？

X、Y很簡單，就用Z的距離看相似三角形要縮放多少就好

但因為矩陣乘法沒辦法 X/Z、Y/Z，所以就用齊次座標多的那個維度 \*Z，反正根據定義這樣表示的點是一樣的（"$\Rightarrow$" 表示擠了以後）

得到半成品矩陣，長這樣

那 Z 要怎麼變呢？

第一直覺會覺得 Z 就不變，保持原樣就好，但因為我們剛剛 XY 在縮放的時候用同乘 Z 來做到除以Z的效果（矩陣最後一 row 不再是萬年 0,0,0,1），所以 Z 被動到了，而我們唯一的要求是 n 要還是 n、f 要還是 f （近平面、遠平面不動），中間的 Z 怎麼動都無所謂，所以就用這兩個 case 去求這個線性變換的矩陣剩下的部分應該長怎樣


解出

最後把擠成的箱體用正交變換，平移、縮放成原點的一個 2\*2 立方體就是了

## L5 Rasterization 1 (Triangles)

三角形的特別之處：最基本的多邊形，任何多邊形的可以分解為由三角形組成、空間中任三點連起來的三角形一定是平的（一個平面）

得到立方體以後，接下來就要把它轉換成平面顯示了

Rasterization：光柵化，就是把連續的圖案轉換成離散的像素點來顯示

三角形的話就是檢測（外積）像素點是否在三角形內部
不需要每個像素點都檢測（Sampling 採樣），三角形的 bounding box 就好

AABB：Axis-Aligned Bounding Box
Aliasing：連續轉離散時的失真

## L6 Rasterization 2 (Antialiasing and Z-Buffering)

- Sampling Artifacts：採樣會有一些瑕疵，這些瑕疵都是因為原信號變化的太快，採樣的速度太慢
- **Jaggies**：鋸齒狀，sampling in space
- **Moiré Patterns**：摩爾紋，undersampling images
- **Wagon Wheel Illusion**：輪子向後轉，sampling in time

### Antialiasing

- 中心思想是先把原信號模糊，讓他的邊界平滑些再採樣

這個模糊會用到 Fourier Transform

[傅立葉轉換](https://youtu.be/spUNpyF58BY?si=3YYtIqR4xCDEvTnn)：總之把時域(time domain)轉成頻域(frequency domain)，分析原本的信號是由哪些頻率組成
[圖像(2D)的傅立葉轉換](https://youtu.be/3gAZ0U66AEA?si=EO2CpDvJDXzjJWVr)：還是難想像2D是怎麼回事，反正也是把空域(spatial domain)轉成頻域

- **Convolution Theorem**
對時域做卷積 等於 頻域跟卷積核的頻域相乘，反之
對頻域做卷積 等於 時域跟卷積核的時域相乘
(神奇，信號處理的東西，看看就好)

- **Supersampling (MSAA)**
Multi-Sample AntiAliasing，多幾個採樣點，去逼近說這個圖案在真實採樣點裡佔了幾%面積

- Antialiasing Today
- No free lunch!
- What’s the cost of MSAA?
- Milestones (personal idea)
- FXAA (Fast Approximate AA)
- TAA (Temporal AA)
- Super resolution / super sampling
- From low resolution to high resolution
- Essentially still “not enough samples” problem
- DLSS (Deep Learning Super Sampling)

## L7 Shading 1 (Illumination, Shading and Graphics Pipeline)

### Z-buffering

(上節課沒講完，這節講)

兩個物體產生遮擋時要怎麼正確的畫呢？

#### Painter Algorithm

把三角形們根據與鏡頭的距離排序，但這方法要 O(n^2^)，而且有可能無解


#### Z-buffering

不以三角形為對象，也不排序，而是以像素為單位，藉由維護深度圖，找出最近的那個物體來畫
若n個三角形的各面積是常數值，那只需要 O(n)

++Implemented in hardware for all GPUs++ !

就是給物體根據材質上色

### Blinn-Phong Reflectance Model

一個簡易的 Shading model，分成三部分

- Diffuse：漫反射 $L_d = k_d \space \frac{I}{r^2} \space max(0, n \cdot l)$
- Specular：鏡面 $L_s = k_s \space \frac{I}{r^2} \space max(0, n \cdot \frac{v+l}{|v+l|})^p$
- Ambient：環境 $L_a = k_a I_a$

$L = L_d + L_s + L_a$

#### Diffuse

- ++Local++：不考慮物件的遮擋、陰影，只考慮當前這個點跟光源的互動
- ++Diffuse Reflection++：各點都是漫反射，也就是與觀察者視角無關，從哪看都一樣

不考慮觀察角度跟其他物件，那考慮什麼呢？
答案是點跟點光源的 ++角度++ 跟 ++距離++

反射光強度與 法向與光源夾角的餘弦 成正比 (都單位向量所以直接內積)
反射光強度與 點與點光源的距離平方 成反比 (因為是三維球體面積)


##### Lambertian (Diffuse) Shading

就這麼簡單，不過還要考慮點本身的材質 $k_d$，值為[0,1]，表示反射率，若為向量 (r,g,b) 則可呈現顏色

#### Specular

鏡面反射出來的光只有當觀察者在特定角度才會看到


入射角 = 反射角，但只要用 I、V 的角平分線(單位向量)判斷跟法向 n 接不接近就好了(內積)

其中 $p$ 用來控制允許在多大的角度看到反光，$p$ 愈大，觀察角度愈需要接近反射角才看的到，也就是愈完美的鏡面
通常設置在 100~200

#### Ambient

環境光直接簡化成常數量

## L8 Shading 2 (Shading, Pipeline and Texture Mapping)

### Shading Frequencies

有了 Shading Model，我們知道了要怎麼算出一個點的外貌，那要在哪些點上做計算呢？

- **Flat Shading**：Shade each triangle
每個三角形為單位，將整個三角形視為一樣的平面，三角形法向由兩邊外積得出
不適合平滑曲面
- **Gouraud shading**：Shade each vertex
以頂點為單位計算，先算頂點的法向(由相鄰三角形們依面積加權平均計算得出)，算出頂點的外貌後，三角形內部由三個頂點的計算結果插值(後面會講)得出
- **Phong shading**
以像素為單位計算，先由頂點的法向插值(後面會講)計算出三角形內部各像素的法向，再算各像素的外貌


### Graphics Pipeline (Real-time Rendering)

整個走一遍的流程，寫好在硬體(GPU)裡了

- **Vertex Processing**：Model, View, Projection transforms
- **Triangle Processing**：把點點連成三角形(應該是建模的時候就存在頂點的資訊，只是 MVP transform 以後再連起來)
- **Rasterization**：判斷採樣點是否在三角形裡
- **Fragment Processing**：Z-buffer
- **Framebuffer Operations**：阿哉

而 shading 則看著色頻率，如果是 Gouraud shading (頂點) 就可以在 Vertex Processing 的時候做；Phong shading (像素點) 則要等到 Fragment Processing 才能做

這 Pipeline 是寫在GPU裡的，但現代的 GPU 允許部分是可編程的，也就是說我們可以自己簡單寫一個 Shader，指定每個點要如何著色，然後GPU會幫你在每個點上(看你的 Shading Frequencies)平行運算

[Shader Toy](https://www.shadertoy.com/)：可以線上寫 shader 的平台

### Texture

材質貼圖其實就是紀錄各個點要套入 Shader 的參數，把uv圖點對點的map到模型上，三角形內部則用其他方法看要怎麼對應(之後會講)

u、v座標範圍慣例是[0,1]


## L9 Shading 3 (Texture Mapping cont.)

Gouraud shading 的 shading 參數、Phong shading 的法向、UV貼圖... 都會需要三角形內部用三個頂點去插值，那具體該怎麼做呢？

### Barycentric Coordinates

重心座標
三角形平面上任一點的座標都可以表示成三個頂點的線性組合，然後拿這係數插值就行
其中係數和要=1才會是這三角形所在的平面，>=0才會在三角形內部


那要怎麼找出給定任一點的重心座標(係數)？

用面積比例就行，而面積可以用向量cross求出
重心則是三者面積相等的情況

經過整理可得公式如下，其中只需求到兩個即可知道第三個，畢竟是2維的座標

但是！Barycentric Coordinates 不保證投影變換後會不變，也就是說，雖然是在同樣一個三角形裡的點，投影變換後，可能得出不一樣的重心座標（合理，畢竟是二維的，會被三維影響）
所以投影後要插值的話要回去找投影前的值

### Applying Textures

接著講如何將材質貼圖map到模型上，換句話說，模型要如何知道這個部分要去找材質貼圖上的什麼部分

但因為材質貼圖也是離散的、有限的，沒辦法完美的對應，所以要用一些方法

分成模型解析度 >貼圖、<貼圖 兩部分討論

### Texture Magnification

貼圖解析度太低，模型上很多個點都對應到同一個 texel (texture 的 pixel)

直覺上會取最近的那個 texel，但就會一塊一塊的，所以會用 Bilinear Interpolation

#### Bilinear Interpolation

就是考慮周圍四個點，並做兩次線性插值，先做一次把四個值減少成兩個，再做一次變成一個，意義是讓解析度沒那麼高的貼圖也能有一個平滑的過渡

#### Bicubic Interpolation

老師沒細講，只說是考慮周圍16個點

### Texture Minification

模型解析度太低，無法呈現解析度高的貼圖（變化太快，產生alias）
一個 pixel 對應到太多 texel，只取一個會走樣

小孩子才做選擇，直接把 pixel 對應到的所有 texel 取平均就好
但要怎麼知道 pixel 對應到哪些 texel？（Point Query vs. (Avg.) Range Query，點查詢與範圍查詢，其實是算法的一個問題）

但要怎麼做知道一個 pixel 對應到哪些 texel，要？
如果跟之前一樣 supersampling，把一個 pixel 塞好多個採樣點，雖然會 work，但花費太高，而且遠處物體的一個 pixel 涵蓋愈多 texel，就需要更高的採樣頻率，所以我們需要其他方法來知道要取哪些 texel 的平均 (介紹兩個)

#### Mipmap

Allowing (fast, approx., square) range queries
預先計算好相鄰區域的平均（我覺得概念是預先算好較低解析度的貼圖，避免貼圖解析度太高）

需要多 Log$_2$邊長 張圖，但總共只需要多 $\frac{1}{3}$ 的容量！（等比級數就能算）

那要怎麼知道當前這個像素包含了多少 texel，應該去哪個程度的Mipmap取值呢？

不知道，不知道這邊微分怎麼算的，但總之就是取比較大的那個，然後用正方形近似

##### Trilinear filtering

D 算出來如果不是整數，就取 D 跟 D+1 兩張，兩張先各自用 Bilinear 插值（本來就要做 Bilinear，因為模型的點不會剛好映射在貼圖的點上），再根據 D 的值線性插值

##### 缺點

然而遠方會糊掉，為什麼？

因為 Mipmap 用盡量大的正方形去近似像素點在貼圖中的形狀，但如果實際上是長方形的話，D 就會太大，取到解析度太低的貼圖來用

#### Ripmap

Anisotropic filtering(AF) 各向異性過濾！
就是弄出 x y 兩個方向各自不同解析度的貼圖，就可以用長方形來近似了（對角線就是 Mipmaps），但 Diagonal footprints still a problem
而且內存開銷多三倍

PPT還有一個 summed area tables (SAT)，老師沒講到

#### EWA filtering

老師也沒細講這個，大概是用圓形去拼出不規則的 footprints

### Applications of textures

材質貼圖對GPU來說就是 memory + range query (filtering)，可以有各種不同的應用

- Environment lighting
- Store microgeometry
- Procedural textures
- Solid modeling
- Volume rendering

#### Environmental Lighting

##### Spherical Map

環境光貼圖可以用圓球形處理，好處是在render的時候給個角度就可以快速求出，壞處是記錄成矩形的時候會變形

##### Cube Map

拆成盒子，好處是變形比較少，壞處是給個角度還要算一下是在這六張圖的哪一個再去找值

#### Bump Mapping

這邊的 Bump Map 不是直接法向貼圖，而是紀錄表面位移量，再用這個位移量去算法向


至於法向怎麼算，用 u、v 兩個切線方向去算就好（叉積？？看起來不像，也不知道 local 是啥意思）

#### 3D Textures and Volume Rendering

好像就 3D 的 texture 吧

## L10 Geometry 1 (Introduction)

幾何形體的表示方式分成兩種，各有適用場景：
- **Implicit**：不說有哪些點，用式子表達
- **Explicit**：直接說有哪些點

### Implict

可以快速算出給定點是否在這表面內部；但是不直觀


不只是單純數學式子而已，有很多種延伸
- Algebraic surfaces
- Constructive solid geometry
- Level set methods
- Fractals

#### Constructive Solid Geometry

單純用式子很難表示複雜形體，所以可以用布林運算組合

#### Distance Functions

用 Distance Function 給出任意一點到表面的距離
可以漸變的 blend 表面（不是很懂）


#### Level Set Methods

水平集，概念跟 Distance Functions 一樣，只是用數學式子當距離函數很難表示一些複雜形狀，所以改用表格儲存實際數值，再插值出數值為0的地方
提供比較顯式的操作空間(像個 texture)
雖然顯式的指出了點到表面的距離，但還是算 implicit 的

#### Fractals

就分形、碎形，天知道怎麼搞

### Explicit

顯式的幾何表示法，包括但不限於：
- triangle meshes
- Bezier surfaces
- subdivision surfaces
- NURBS
- point clouds

不只是直接紀錄點而已，這種用二維紀錄點，再用式子 map 到三維的也算 Explicit
總之只有給一些點再套式子的都算


#### Point Cloud

最直接的，給一堆點，通常3D掃描出來是這個，再看要怎麼轉成 polygon


#### Polygon Mesh

Store vertices & polygons (often triangles or quads)
More complicated data structures
老熟了

##### Wavefront Object File (.obj)

Commonly used in Graphics research.
Just a text file that specifies vertices, normals, texture
coordinates and their connectivities

就是個 text file，**v** 表示空間座標，**vt** 表示材質座標(uv)，**vn** 表示點的法向，**f** 表示面(由點點們組成，a/b/c 表示這點由第幾個 v/vt/vn 組成)

## L11 Geometry 2 (Curves and Surfaces)

### Curve

#### Bézier Curve

可以有n個控制點，起點到終點的每個線段在比例t的地方畫一個點，就會形成 n-1 個點，再做一次就變 n-2 個點，直到最後只剩一個點，比例 t 從0跑到1的點組合起來就是一條曲線



可以發現係數是二項式展開，寫成下面這個 general form


貝式曲線有以下特性：
- **Interpolates endpoints**：起/終點 也會是曲線的 起/終點
- **Tangent to end segments**：曲線 起/終點 的切線方向會是 頭兩個/末兩個 點連成的方向
- **Affine transformation property**：控制點畫出的曲線做仿射變換 跟 控制點做仿射變換後畫出的曲線會是一樣的（畢竟這個畫曲線就是線性插值的感覺）
- **Convex hull property**：畫出來的曲線會在控制點的凸包內 e.g. 控制點共線的時候，bézier curve 是直線
（凸包是能包含所有點的最小凸多邊形）

#### Piecewise Bézier Curve

Higher-Order Bézier Curves 不好控制，牽一髮動全身

所以常用的是 Piecewise Cubic Bézier Curves，就是由一堆四個控制點的 Bézier curve 片段拼成

##### Continuity

C^0^ Continuity：上一段的終點跟下一段的起點相連
C^1^ Continuity：尾首相連，而且切線同方向、同大小


#### Other Curve

其他還有

- Spline
- B-splines
- NURBS

...等，各種曲線

### Surfaces

#### Bézier Surface

每一片都是4x4的控制點，沿著 x 做出 Bézier Curve，再沿著 y 做
然後再把每一片拼起來，但片跟片之間要怎麼拼的滑順無縫又是別的課題


## L12 Geometry 3

網格操作：

- Mesh subdivision
- Mesh simplification
- Mesh regularization


### Mesh Subdivision

upsampling，網格細分，那要怎麼新增點呢

#### Loop Subdivision

Common subdivision rule for ++triangle meshes++
First, create more triangles (vertices)
Second, tune their positions
Loop 是人名，跟迴圈無關

首先是新增點，就是三角形各邊中點，把一個三角形切成四個

接著是調整位置

新頂點是上下左右的舊頂點們按著魔法比例加權
$\rm new = \frac38(A+B) + \frac18(C + D)$


舊頂點是原位置跟鄰居位置按更魔法的比例加權


完成！


#### Catmull-Clark Subdivision

General Mesh，不只適用三角形

一樣是 加點 $\rightarrow$ 調位置

不管幾邊形，在 ++邊的中點++、++面中間++ 加點
degree：點點連出去的邊數

妙的是，只要做過一次 Catmull-Clark Subdivision，全部都會變四邊形，而 Extraordinary vertex 的數目也不會再增加

調位置一樣是魔法公式


### Mesh Simplification

簡化但不失真

#### edge collapsing

把邊併成一個點，但要挑哪個邊併才能維持大致形狀？

##### Quadric Error Metrics


用這方法找出每個邊坍縮後應該要把點放在哪個位置最好，然後找出 quadric error 最小的邊來坍縮，但因為坍縮完以後會動到其他點，鄰邊要重算、重排序，所以可以用 min heap 來存

### Shadows

rasterization 要怎麼算出陰影呢？


#### Shadow Mapping

Key idea：the points NOT in shadow must be seen **both** by the ++light++ and by the ++camera++
也就是說，只要有個點無法被相機或光源看到，就會是陰影

1. 從光源的位置做光柵化，但不著色，而是把各點深度紀錄成一張 Depth image
2. 相機做光柵化，並把看到的像素投影回光源，總之就是去光源的 Depth image 看這方向上距離光源最近的距離是多少
3. 如果點到光源的實際距離跟 Depth map 上的值不一樣就是陰影


缺點：

- Hard shadows (point lights only)：僅適用點光源，如果光源有體積，會處理不了半影區的部分
- Quality depends on shadow map resolution (general problem with image-based techniques)
- Involves equality comparison of floating point depth values means issues of scale, bias, tolerance


## L13 Ray Tracing 1 (Whitted-Style Ray Tracing)

Ray Casting：就相機每個像素射一條線看有沒有撞到光源

### Recursive (Whitted-Style) Ray Tracing

撞撞撞，再加起來，但是只考慮鏡面反射的情況，遇到漫反射的表面就停止，所以無法處理 glossy 的材質


### Ray-Surface Intersection

要怎麼判斷射線是否跟物體相撞？

首先射線用 ++起點++ + ++方向++ 來定義

從o點出發，經過時間t後，會在r(t)這個位置

#### Ray Intersection With Implicit Surface

物體是隱式的話，用數學判斷，直接把射線代入物體表面的方程式找交點


#### Ray Intersection With Triangle Mesh

判斷射線與物體是否相交的能力，除了光追會需要用到外，也可以用來判斷一個點是否在某物體內部，只要這個點任意一個方向的射線與物體的相交次數為偶數，則此點在物體外；反之奇數則在物體內部

有不同方法可以判斷射線是否與三角形相交，其中一個是

先找出射線與三角形所在平面的交點，再判斷焦點是否在三角形內

找焦點就把射線方程代入平面的點法式
判斷焦點是否在三角形內可以用外積之類的

另外一種方式是

##### Möller Trumbore Algorithm

找到射線在三點平面上的重心座標，再判斷三個係數是否都 >0
三個未知數、三條等式（因為是三維的點），直接用克拉瑪公式求解，bang

### Accelerating Ray-Surface Intersection

但如果只是跟場景中的每個三角形都求交再找最近(t最小)的那個，計算量超大( #pixels * #traingles (* #bounces))，所以要想辦法優化

先用 Bounding Box 判斷，如果射線連 Bounding Box 都沒撞到就不用去跟這個 object 求交了

常用的是 Axis-Aligned Bounding Box (AABB)，就是沒有旋轉，橫直豎平的箱子

 

AABB 由三組對面組成
只要射線不是跟面平行，我們都可以找出射線跟其中一組對面的交點，$\rm t_{min}$是進入，$\rm t_{max}$是離開

若要找射線與此 AABB 的交點，就把三組對面交點求出，並且

$\rm t_{enter} = max\{t_{min}\}$、$\rm t_{exit} = min\{t_{max}\}$

因為在箱子內的線段是，++皆進入了三組對面++ 到 ++離開了任一組對面++

考慮一些 case

- $\rm t_{enter} < t_{exit}$：射線在箱子內待了一陣子，兩者相交
- $\rm t_{exit} < 0$：箱子在鏡頭背面
- $\rm t_{exit} \ge 0$、$t_{enter} < 0$：相機在物體內部

$\Rightarrow$ 射線與 AABB 相交 iff ==$\rm \; t_{enter} < t_{exit}\;$ && $\; t_{exit} \ge 0$==

#### Why AABB

那為什麼要用AABB，而不用隨便三組對面組成的box，更能精準包含 object？
$\Rightarrow$ 因為求交簡單。

## L14 Ray Tracing 2 (Acceleration & Radiometry)

### Acceleration

現在已經可以用 AABB 來省略與 bounding box 不相交時的計算，接下來要說的是，當光線與 bounding box 相交時，如何加速與盒子內物體的求交（靜態場景）

- Uniform grids
- Spatial partitions
- Object Partitions

#### Uniform grids

在 bounding box 裡又分成許多格子，紀錄物體表面是否與這格子相交（因為是靜態的，做一次就可以給各條光線用，但不知道盒子怎麼與物體求交）

再判斷光線路徑上的格子是否包含物體，有交再跟物體求交
（怎麼感覺就是 AABB 裡的 AABB）


但如此一來加速程度就跟格子的解析度有關，如果格子太細，會花太多時間跟盒子求交，如果格子太大，又要花時間跟物體求交

 

而且若場景中物體分布不均，就會有一堆相鄰的空白格子，還有優化的空間


#### Spatial partitions

核心想法：將空間劃分成不同子空間(格子)，如果子空間內沒有物體就不需要再繼續劃分下去，藉此提高檢索時的效率；或是已經切太細了就不繼續切。

- **Oct-Tree**：八叉樹(三維的時候)，沿xyz各切一刀，將一個空間分成8個子空間，缺點是n維就會變2^n^叉樹
- **KD-Tree**：輪流沿著xyz切(可避免切的太細長)，每次都將一個空間切為2個子空間，所以永遠都是 binary tree
- **BST-Tree**：用物體分空間，一樣是二叉樹，但不是橫平豎直的所以求交較慢，而且高維會不好切


##### KD-Tree

k dimension tree

1. **建樹**：沿著x或y或z(輪流)，看要在哪切一刀。符合中止條件就在葉節點儲存物件資訊(Leaf nodes store list of objects)，否則就繼續切，並指向小孩節點(No objects are stored in internal nodes)
2. **遍歷**：從樹頂(表示整體空間)開始，如果光線與該空間相交，就遍歷左右小孩，若遍歷至葉節點就，與該葉節點的所有物體求交


#### Object Partitions

前面兩種是直接切空間，另外也可以用物體來分開空間

##### Bounding Volume Hierarchy (BVH)


為了讓分割出來的空間分布比較平均：

- 選最長的那軸分割
- 位置在中位數的那個物體來分(O(n)的事，類似quick sort)
- 當節點包含過少物體時不再切割（為啥，怕樹太深嗎?）

結構：

- **Internal** nodes store：
- Bounding box
- Children: pointers to child nodes
- **Leaf** nodes store：
- Bounding box
- List of objects

蘇~~坡愛~~豆扣

#### Spatial vs Object Partitions

- **Spatial Partition**
- 切出的空間不會重疊
- 物體可能被分在不同空間，甚至可能空間中不包含物體的點，但包含物體表面(小盒子插在三角形中間)
- **Object Partition**
- 切出的空間可能重疊
- 物體只會屬於其中一個子集
 $\;\;\;\;\;\;\;$ 

### Basic radiometry (輻射度量學)

為了更正確地呈現畫面，來學一點光線的東東

| 英文 | 中文 | 符號 | 定義 | 單位 | 意義 |
| --- | --- | --- | ---- | --- | --- |
| **Energy** | 能量 | $Q$ | | $\rm J$ | 總能量，圖學少用 |
| **Flux** | 通量 | $\Phi$ | $\frac{dQ}{dt}$ | $\rm W$、$\rm lm$(流明) | 單位時間內由光源發出的總能量 |
| **Intensity** | 強度 | $I(\omega)$ | $\frac{d\Phi}{d\omega}$ | $\rm \frac{W}{sr}$、$\rm \frac{lm}{sr}$($\rm cd$ 燭光) | 單位立體角內的輻射通量 |
| **Irradiance** | 照度 | $E$ | $\frac{d\Phi}{dA}$ | $\rm \frac{W}{m^2}$ | 單位面積上接收到的輻射通量 |
| **Radiance** | 輻射 | $L(p,\omega)$ | $\frac{d^2\Phi(p,\omega)}{d\omega \ dA\ \rm{cos(\theta)}}$、$\frac{dI(p,\omega)}{dA\ \rm{cos(\theta)}}$ | | 單位面積在某個角度上，單位立體角的輻射通量，可以是射出或接收 |

 $\quad$ 

#### 單位立體角 (Steradian, sr)

平面上的角度(rad)是 $\frac{l}{r}$
而立體角(sr)是 $\Omega=\frac{A}{r^2}$
 

## L15 Ray Tracing 3 (Light Transport & Global Illumination)

### Bidirectional Reflectance Distribution Function (BRDF)

光線打到表面上的一個點後，可能會往各種方向彈
BRDF就是一個函數 ( $f$ )，能描述從 $\omega_i$ 來的光有多少比例彈向 $\omega_r$
因此把各個會反彈到相機接收到的角度的光線加起來就是那點應該的長相
(cos是因為要轉成等效的垂直入射光)


可以發現上面這 Reflection Equation 左右都有 $L$，就是說，一個點反射的光線 $L_r$ 可能貢獻另一個點的入射光 $L_i$

再考慮物體本身的自發光( $n \cdot \omega_i$ 就是 $\cos\theta_i$ )：

點光源的話把離散的各個加總就好

面光源則視為無數個點光源，並遞迴考慮其他物體反射過來的光

再經過某種高級數學，甚麼轉換成算子啥的，賓果把拉蹦

## L16 Ray Tracing 4 (Monte Carlo Path Tracing)

### Monte Carlo Integration

蒙地卡羅積分

#### Why

一般我們在做定積分，求一個區段內的面積的時候，會先把式子積分回去，然後把 b、a 代進去相減，得到一個數字

但是要把式子積分回去可能很困難，所以用蒙地卡羅積分可以不需管式子是什麼，直接得到一個近似的面積


#### How

隨機取 a、b 間的一個 x，把 $f(x)$ 除以 採樣到 x 的機率，多取幾個然後平均起來就能近似定積分，式子如下：
（除以機率感覺像是因為機率很高的話就會常採樣到，所以加權要小一點？）

#### example

x 可以用各種不同的採樣方法，這邊舉一個例子，就是機率密度函數(Probability Density Function, PDF)是常數的情況，也就是 a、b 間任何一點被取到的機率都一樣，都是 $\frac{1}{b-a}$
那積分就會近似這個

### Path Tracing

#### Why

Whitted-Style Ray Tracing 用入射角=反射角來射光線，遇到漫反射材質就當光線被吃掉，無法處理 glossy 的材質

#### How

所以要用符合真實情況的 Rendering equation 來做

但半球的積分要怎麼做？而且BRDF沒辦法積分成另一個式子（但老師還沒說BRDF到底長怎樣），所以就需要蒙地卡羅積分


這邊採用均勻的採樣方式，也就是PDF是常數，因為半球的立體角是 $\frac{2\pi r^2}{r^2} = 2\pi$，所以PDF $p(\omega_i) = \frac{1}{2\pi}$

打到光源的話就直接加，但如果是物體的話就要遞迴算下去


##### Problem 1

但每個遞迴(光線彈射)都要採N次樣，這樣會爆炸

為了不要指數爆炸，所以N只能是1，也就是一條光線走到底 $\Rightarrow$ **Path tracing**！

但這樣可想而知會很不對，所以一個 pixel 要多採樣幾次，再把結果平均（因為只是單純一開始多取幾個再平均，不是積分，所以不用除以PDF，應該吧。感覺就是把多採樣的部分移到前面，只有最一開始會做）




##### Problem 2

目前還沒有中止條件，遞迴會一直跑下去直到撞到光源，所以要讓它能停下來

但因為有些材質比較吸光，彈個兩三次就像沒有一樣；但有的材質就算彈射10次以後才打到它，也還是對周遭的光照影響很大，所以不能只單純限制遞迴深度(光線彈射次數)
彈3次 v.s 彈17次
 

###### Solution：Russian Roulette (RR)

每次要遞迴(彈射)的時候，就轉個俄羅斯輪盤，活著就遞迴下去，死了就不繼續彈，當作彈下去是 0，這樣就大概會停下來了

這個輪盤的機率 P 自己選，但是如果活著的話，要把遞迴後的得到的 $\rm L_o$ 除以 P，這樣期望值就會跟原本一樣（像NN的Drop out）



##### Problem 3

目前的算法已經對了，但沒什麼效率，因為隨機打射線的話，有很大機率這條path不會通向光源，那就浪費計算資源了


所以打到光源的部分就不要碰運氣用半球去積，把積分域改成光源（是這樣說嗎？），也就是直接把會打到光源(面光源)那部分的射線積起來，但一樣是在面光源上隨機取樣一個點的蒙地卡羅積分(PDF=1/A)
（但點光源就不好處理了，老師只說建議不如當作一個很小的面光源）

我們知道光源的位置，但要能積還需要把它轉換成原本立體角 $\omega$

蹦蹦蹦

所以說


再加上來自光源的射線要判斷中間會不會被阻擋，就完成了！

$\:\:$
$\:$


#### Things we haven’t covered / won’t cover

- Uniformly sampling the hemisphere
- How? And in general, how to sample any function (sampling)
- Monte Carlo integration allows arbitrary pdfs
- What's the best choice? (importance sampling)
- Do random numbers matter?
- Yes! (low discrepancy sequences)
- I can sample the hemisphere and the light
- Can I combine them? Yes! (multiple imp. sampling)
- The radiance of a pixel is the average of radiance on all paths passing through it
- Why? (pixel reconstruction filter)
- Is the radiance of a pixel the color of a pixel?
- No. (gamma correction, curves, color space)
- Asking again, is path tracing still “Introductory”?
- This time, yes. Fear the science, my friends.

## L17 Materials and Appearances

Material = BRDF

### Diffuse / Lambertian Material (BRDF)

反射光均勻四散在各個角度

假設入射光在各方向上也是均勻的，以及材質不吸收光，也就是入射能量=反射能量（不知道為什麼這兩個可以這樣假設）
那就如下圖的 Render Equation 所示，$L_o$、$L_i$ 與角度 $\omega$ 無關，為常數，且兩者可以消掉，得出 BRDF 為常數值 $\frac{1}{\pi}$
再引入一個 $\rho \in [0, 1]$（感覺是剛剛假設是1的反射率），如果是 RGB 的話就可以控制顏色

也就是說，漫反射材質的BRDF $f_r = \frac{\rho}{\pi}$


### Glossy Material (BRDF)

 

（阿怎麼沒講）

### Ideal Reflective / Refractive Material (BSDF)

有反射有折射

 

#### Perfect Specular Reflection

完美情況下入射能量=反射能量，所以我們需要的只有
給定一個平面與入射角，求反射角


因為入射角=反射角，且 $\omega$、 $\vec{n}$ 都是單位向量，可得
$\omega_o + \omega_i = \rm 2 \ cos\theta \ \vec{n} = 2(\omega_i \cdot \vec{n}) \ \vec{n}$
$\Rightarrow \omega_o = - \omega_i + 2(\omega_i \cdot \vec{n}) \ \vec{n}$

但這方法要算點乘，有個更簡單的辦法是先投影成局部坐標系，把 $\omega$ 拆成 $\theta$ (從z軸往下的角度)、$\phi$ (繞z軸轉的角度)
可以發現 $\theta_o = \theta_i$，而 $\phi_o$ 就是 $\phi_i$ + 180度，再投影回去就是了

#### Specular Refraction

首先是 $\theta$

**Snell’s Law**：$\eta_i \sin \theta_i = \eta_t \sin \theta_t$


注意根號內 $<0$ 的情況發生於 $\frac{\eta_i}{\eta_t} < 1$，此時折射不會發生，而是全反射

至於方位角 $\phi$，一樣是差180度


**Snell’s Window**：真假，看不到圓圈外的東西喔，酷ㄟ

#### Fresnel Reflection

又叫做 Fresnel term，菲涅爾項，就是斜斜的時候比較多反射


++絕緣體++($\eta=1.5$) v.s ++導體++，看紅色的就好，其他是偏振
（阿？光學性質還跟導不導電有關喔:O）
 

Fresnel Term，反射與折射的比例 ，正確公式要考慮偏振再平均

但太複雜了，用一個近似的曲線就好 (Schlick’s approximation)

### Microfacet Material BRDF

#### Microfacet Theory

宏觀看來的粗糙表面，其實是由微觀上凹凸不平的光滑鏡面(microfacets)構成

#### Microfacet BRDF

那這複雜的表面結構該怎麼實現呢？關鍵在於法向的分佈


只有法向跟相機與光源的半程向量一致的微表面會把光反射過去
- **f(i,o)**：BRDF
- **F(i,h)**：決定多少光會反射
- **G(i,o,h)**：微表面的凹凸會遮擋彼此，入射光愈平行表面(grazing incidence)，遮擋愈多，反射愈少
- **D(h)**：查詢有多少微表面的法向跟h一致
- 分母：結構變什麼的，跟推導時候的變換有關，沒細說



### Anisotropic Materials BRDF

之前講的材質都是
**Isotropic** (各向同性)，BRDF只與入射、反射的++角度差++相關
但有些材質是
**Anisotropic** (各向異性)，BRDF與入射、反射的++絕對角度++有關

 



### Properties of BRDFs

- **Non-negativity**：$f_r(\omega_i \rightarrow \omega_r) \ge 0$
- **Linearity**：可以拆成高光、漫反射之類的算完再加起來
- **Reciprocity principle**：光的可逆性 $f_r(\omega_i \rightarrow \omega_r) = f_r(\omega_r \rightarrow \omega_i)$
- **Energy conservation**：$\forall \omega_r \ \int_{H^2} f_r(\omega_i \rightarrow \omega_r) \ \cos\theta_i \ d\omega_i \ \le 1$
- if **Isotropic**：$f_r(\theta_i,\phi_i ; \theta_r, \phi_r) = f_r(\theta_i, \theta_r, |\phi_r - \phi_i|)$

### Measuring BRDFs

直接測量材質得到最真實、正確的BRDF



## L18 Advanced Topics in Rendering

### Advanced Light Transport

#### Biased vs. Unbiased Monte Carlo Estimators

Monte Carlo 有分成有偏跟無偏的，在圖學的話很好判斷，render 吃出來會糊就是有偏，noisy 但是有算的地方是對的就是無偏

- **Unbiased** light transport methods：不管用多少樣本，期望值都是正確的，比如說之前的蒙地卡羅積分（蛤？不是要採很多才會準嗎？）
- Bidirectional path tracing (BDPT)
- Metropolis light transport (MLT)
- **Biased** light transport methods：除上述以外的。另外如果採樣愈多，期望值會收斂到正解，那稱作 **consistent**
- Photon mapping
- Vertex connection and merging (VCM)

#### Bidirectional Path Tracing (BDPT)

無偏的

（怎麼連的阿）

下圖場景因為都是間接光打在漫反射材質，Path trace 隨機打不好彈到光源那，所以適合BDPT
（但不是可以對光源積分？）

#### Metropolis Light Transport (MLT)

無偏，Metropolis 是人名
A Markov Chain Monte Carlo (MCMC) application （跨無）

總之，隨機打不容易形成 path，這方法會根據已有的 path 去找出附近的其他 path，Very good at **locally** exploring difficult light paths


適合光的路徑很難的情況

但是不知道要多久才會收斂、算好一張圖

#### Photon Mapping

有偏，光子映射， Very good at handling Specular-Diffuse-Specular (SDS) paths and generating caustics


1. photon tracing：從光源打光子，反射折射彈來彈去，直到打到 diffuse 表面，就把光子記錄起來
2. photon collection (final gathering)：從相機打視線，也是彈來彈去，直到打到 diffuse 物體
3. local density estimation：愈多光子的區域就愈亮，所以要估計視線打到的地方光子密度是多少，做法是，取距離最近的 N 個光子，再除以它們占的面積（面積要算）

至於為甚麼密度要這樣估計，固定光子數量，再除以面積；而不是固定面積，找這裡面有多少光子，是因為面積愈小愈準確，用這方法才能在打很多光子的時候，使面積變很小，收斂到正解 (consistent)


#### Vertex Connection and Merging

（看不懂）

#### Instant Radiosity (IR)

Sometimes also called many-light approaches

從光源打出去，被打到的地方就當作是一個小光源，然後再 render



### Advanced Appearance Modeling

之前講的都是一層表面，來點不一樣的

#### Non-surface models

##### Participating Media

體積的、三維的，內部會與光作用
 

可以散射和吸收

Rendering


##### Hair Appearance


###### Kajiya-Kay Model

光線沿著圓錐區域和圓球區域散射（光線真的就是要打進去一根根的頭髮裡彈來彈去）

 

###### Marschner Model

把頭髮當成類似玻璃的圓柱體 (不懂為啥R比TRT斜)


###### Animal Fur

動物毛髮跟人不一樣


動物毛髮的髓質比較多


雙圓柱模型（不懂為什麼有的經過髓質會散射，有的不會）



##### Granular Material

顆粒狀的材質，很難算繪


#### Surface Models

##### Translucent Material：Subsurface Scattering

透光的材質


Violates a fundamental assumption of the BRDF，打到點P的光可能在點Q出來、點P發出的光可能是打到點Q的光貢獻的

###### BSSRDF

所以要對附近的面積積分

###### Dipole Approximation

但是可以用假裝在表面下有個光源來近似，實際上表面上也需要一個光源（阿災）



##### Cloth


有3種方法，都有人用，看場合

1. **Render as Surface**
但沒有固定規律的就無法了
2. **Render as Participating Media**
不把它當一塊布，而是當成類似雲的體積材質
把空間劃分成許多細小的格子，把格子內纖維的朝向、分布等，轉換成散射的參數，計算量很大
3. **Render as Actual Fibers**
幹下去

#### Detailed Appearance

我們想要細節
 

之前微表面模型的法線分布是簡單平滑的分布，不夠真實，所以用複雜(真實)的法線貼圖來搞

但這樣算圖要超久(蝸牛算了一個月)，因為單純直接用貼圖打光線的話，很難打出一條成功的 path
 

所以需要像之前一樣有一個分布，那就對當前像素照到的區塊，用某種魔法（感覺這魔法才是重點）得出它們的法線分布。也就是說，每個像素都有自己的 BRDF！



#### Wave Optics

好猛，算圖算出結構色


#### Procedural Appearance

不將材質記錄下來，而是用噪聲函數產生三維的材質，要用的時候直接輸入 (x,y,z) 查詢值，隨查隨用
（用 blender 老熟了）


## L19 Cameras, Lenses and Light Fields

Imaging = Synthesis + Capture

之前講了如何模擬出場景，這周講如何用相機捕捉畫面

為什麼 sensor 前一定要有透鏡呢？

因為感光元件紀錄的是 irradiance（單位面積接收的光通量），不是 radiance （單位面積在單位角上接收到的光通量），無法區分不同方位來的光 (不過有研究在做了)，如果直接把 sensor 放著，sensor 上的每個點都會接收到物體各點發出來的光，所有 pixel 的值都會差不多，所以需要透鏡來約束讓物體特定點的光只會打到 sensor 上的特定點


### Field of View (FOV)

視場、視野，下圖用針孔相機推得 FOV 與 focal length 的關係()，實際上針孔相機沒有焦點，所以把 focal length 定義成跟 sensor 的距離（天知道為啥這樣推出來的公式在透鏡相機上也成立）


可以發現 FOV 跟焦距和 sensor 大小都有關，FOV 說穿了就是一個角度數值，但一般我們在表示 FOV 時不是直接用角度，而是用固定 sensor 大小為 35mm 的底片時的焦距大小來表示

這個值愈小，表示視場愈大



手機很薄，焦距勢必很短，所以為了保有一定的 FOV，sensor 也要很小
（但這示意圖不是一般透鏡相機餒）


### Exposure

- Exposure = ++time++ x ++irradiance++
- time：由 shutter speed (快門速度) 控制
- irradiance：由 aperture (光圈)、focal length 控制
- 另外還有 ISO：將 sensor 接收到的值乘以一個數，ISO 200 只需要 ISO 100 一半的進光量

光圈愈大 (F-number 愈小)，景深愈明顯

快門速度愈慢，運動模糊愈多

ISO 太高會有噪點

#### Shutter Speed

因為實際相機上的快門開關是需要時間[移動](https://youtu.be/CmjeCchGRQo?si=nXNDd9NyN7CeWMWU&t=138)的，所以物體動作很快的話，就會跑掉


#### F-Number (F-Stop)

Written as F**N** or F/**N**. N is the f-number.

$N = \frac fD$
- $f$：焦距
- $D$：光圈的直徑

F-number 愈大，光圈直徑愈小，相片愈暗
寫作 F/N 是因為 F/N 可以得到光圈直徑

#### F-Stop vs Shutter Speed

為了維持一樣的曝光，快門速度愈快，F-number要愈小

快門速度快 $\rightarrow$ 運動模糊小
F-number 小 $\rightarrow$ 景深效果少（後面會說）

$\Rightarrow$ ++運動模糊++ 跟 ++景深效果++ 要取捨


### Thin Lens Approximation

真實的鏡頭組很複雜

我們簡化成一個理想的薄透鏡就好：
1. 平行光過焦點
2. 過焦點變平行光
3. 可以任意改變 focal length

那我們有這公式
(推導很簡單)

#### Defocus Blur

##### Circle of Confusion (CoC)

如果 sensor 不在物體成像平面上的話(沒對焦到)，物體上一個點的光線無法在 sensor 上再匯聚成一個點，而是會分散成一個圓 (CoC)

那要怎麼計算 CoC 的大小呢？用相似三角形就行


可以發現 CoC 的大小與光圈直徑成正比，也就是說，其餘條件不變的話，光圈直徑愈大就愈糊(景深)

##### Depth of Field (DOF)

因為感光元件也有一定的解析度，所以 CoC 只要小到一定程度就是可接受的

因此在物距一定範圍內的物體我們都視為能有清晰的成像，這個範圍就稱作 **Depth of Field (DOF)**


DOF 大小的計算如下

光圈直徑愈大，DOF 愈大

#### Ray Tracing Ideal Thin Lenses

先前捕捉畫面的方式都是從相機這個點打光線出去，其實就是默認了這個相機是針孔成像的相機

那該怎麼在電腦中呈現透過透鏡相機捕捉的畫面效果呢？總不會是真的建模出一個透鏡組吧

這邊講其中一個方法

1. 設定好你要的
- sensor size
- aperture size
- focal length
2. 選擇想對焦的距離(物距) $\rm z_o$
3. 根據透鏡公式計算出像距 $\rm z_i$

接著就是要從 sensor 上的各點打光線

4. 在透鏡平面上隨機選一個 x'' (Monte Carlo)

因為從像距平面上的 x' 打的光線經過透鏡後，一定都會通過物距平面的 x'''，所以只要找到 x'''，就可以從 x'' 打光線過去

5. 用通過透鏡中心的那條線找到 x'''
6. 從 x'' 打向 x'''
7. 打完收工


而如果物體不在對焦的平面上的話，那點發出的光就會四散在 CoC 內的各個像素，看起來就糊糊的

## L20 Color and Perception

### The Plenoptic Function (全光函數)

輸入觀察位置、方向、波長(顏色)、時間點，返回光的 intensity


（所以得到這個 function 的方法就真的是在空間中的一堆點上採樣喔？）
（阿為什麼突然講這個）

### Light Field (光場)

aka **Lumigraph**

如果可以把光線打到某個平面(布幕)上的情形全部記錄下來，再用布幕發出去，那就跟沒有布幕一樣
（就像某一集不可能的任務一樣）

 

光場其實就是全光函數的一小部分，反正就是這個平面上記錄了所有通過它的光的訊息

我們先不考慮波長和時間，單純想要一個 function 可以知道從任意位置看向任意角度會收到怎樣的光

這個四維(表面上的二維位置 u、v 和角度 $\theta$、$\phi$ )的 function 把一個物體的光線資訊都記錄在包圍盒的表面上，想形成畫面的話就用一個攝影機，去查各位置對應角度的光強度
（感覺就是把物體的光線資訊烘焙成貼圖嘛，只是多加了方向，所以是四維的貼圖）

除了用位置方向來描述一條射線外，也可以直接用兩個點來描述
也就是說光場函數可以用兩個平面來定義，把所有 (u,v)、(s,t) 對應的光線強度記錄下來
（感覺儲存量超大）

 

物體在右邊的話，
某個 (u,v) 上的所有值是整個物體的外貌，不同 (u,v) 是從不同位置看過去整個物體
某個 (s,t) 上的所有值是從各個角度看向物體某一小部分的外貌，不同 (s,t) 是不同小部分

#### Light Field Camera

除了在圖學上的應用外，實際上也真的有設備可以記錄光場

這是 Stanford 的 camera array （有不同位置了，那不同方向呢？還是說這是特殊相機）

甚至在 2012 年就有商業化的相機問世，不過公司在 2018 倒了
[效果超酷的](https://youtu.be/oldSwLCD6EM?si=BBWSZIEJ2m7BUoyZ)


原理是用微鏡片陣列之類的，很複雜就對了
反正就是它能夠在一個像素內紀錄 irradiance (各個角度)，而不是一般紀錄的 radiance


要用這樣的光場資訊形成一張相片就是靠軟體選擇要哪些點的哪些角度的光了，可以做到拍完照以後，再聚焦在不同的距離上，甚至可以在一定程度上改變相機的位置和角度，[效果超酷的](https://youtu.be/oldSwLCD6EM?si=xFDJAK5JdCx7XrWT)
但因為每個像素都要記錄各個方向的光線資訊，所以解析度自然無法太高

### Color

事實上不存在顏色這種東西，就只是不同波長的光，其他都是我們腦袋的想像


#### Spectral Power Distribution (SPD)

Describes distribution of energy by wavelength

不同的SPD是可以線性相加的

 

#### Biological Basis of Color

視桿細胞只看亮度
三種視錐細胞分別對不同波長的光敏感，產生顏色的感覺


##### Spectral Response of Human Cone Cells


事實上，不同人視網膜上的三種 Cones 分布情況也非常不一樣，12個人就有12種情形


#### Tristimulus Theory of Color

波長的光強度與響應函數相乘，再把各波長積分起來，得到刺激值
三個刺激值的和決定了腦子覺得這光是什麼顏色


#### Metamerism

異譜同色，不同的混和光有可能積分起來後結果都一樣，也就是說一個顏色可以由不同波長的光用不同方式混搭

下面這幾個積分起來都一樣

有了 metamers 的存在，才使得我們可以用有限數量的燈泡重現世界上的各種顏色

#### Color Reproduction / Matching

那要怎麼用三種顏色的燈泡表示各種顏色呢？
(這邊是加法顏色，不是顏料的減法顏色)

假設我們有三個燈泡，就看怎樣組合才可以跟測試的顏色 match


但也有無論如何都調不出來的情況 (比說用上了所有紅色還是不夠紅)
那就把測試的顏色加上我們的基色 (讓測試色藍綠一點，不要那麼紅)
然後把這個加上的當作負值

 

#### Color Space

##### CIE RGB

CIE 是一個管顏色的組織

經過大量實驗後，他們挑了三個波長的光作為基色


###### Color Reproduction with Matching Functions

曲線是各個波長的光在腦中的顏色，要怎麼用這三個基色組出來（注意縱軸不是比例、功率之類的，因為實際上要重現白光所需的RGB功率比不是1:1:1，所以搞了些單位，[具體看這](https://zhuanlan.zhihu.com/p/3277851231)）
公式是給定一個混和光，要怎麼用 RGB 重現

把 RGB 當作三個軸，可以畫出一條在空間中的曲線，曲線各點代表的是不同波長的光，以及對應的 RGB 值。
忽略 B 值可以得到一個平面的投影


我們可以發現 R 的部分有負值，因為我們不能打負的光，所以不可能重現出那個區段波長的顏色，事實上，給定任三個基色都沒辦法完整涵蓋人腦中的所有顏色

##### Standardized RGB (sRGB)

- 不是 RGB
- makes a particular monitor RGB standard
- other color devices simulate that monitor by calibration
- widely adopted today
- gamut (色域) is limited

##### CIE XYZ

之前 RGB 空間會導致有負數的情況發生，我們不想要這樣
為了能夠描述所有可見光顏色，CIE 人為的設定了一個色彩空間 XYZ，使得 X、Y、Z 的 color matching function 長這樣


因為沒有負數，所以用 XYZ 可以合成出人眼看到的所有顏色，然而事實上XYZ這三個基色是虛擬的，只存在數學上，不是任何一個單一波長的光（為了不要有負值所以搞出一個不存在的虛擬色？？）

而 RGB 要轉移到 XYZ 只需要乘一個矩陣就行（坐標系轉換的感覺。怎麼找到這矩陣的阿，數學的魔法）

其中特別的是，Y刺激值代表的是亮度
同強度不同波長的光在人眼中看起來亮度也不一樣，而這亮度也有一個 Luminous efficiency function

CIE 將 Y 的 matching function 設定成亮度 Response Curve 一樣，所以

$Y = \int I(\lambda) \cdot \overline y(\lambda) \ d\lambda$

給定一個混和光， $\overline y(\lambda)$ 積分起來就跟亮度一樣

#### CIE Chromaticity Diagram

Chromaticity：色度，用 XYZ 正規化後的值來定義 $\Rightarrow$

$x = \frac{X}{X + Y + Z}$
$y = \frac{y}{X + Y + Z}$
$z = \frac{z}{X + Y + Z}$

這樣的正規化過程中，就把亮度跟彩度拆開了，本來 $Y$ 是絕對的亮度值，現在 $y$ 只是彩度的一個分量。舉例來說，
- 一個 100 cd/m² 的綠光，和一個 10 cd/m² 的綠光
- 它們的 (x, y) 相同（因為色相/飽和度相同）。
- 但 Y 值差 10 倍（因為一個比較亮）。

另外因為 x+y+z = 1，所以用 $(x,y)$ 就夠了，$z$ 可以丟掉


#### Gamut

⾊域
Gamut is the set of chromaticities generated by a set of color primaries

Different color spaces represent different ranges of colors
So they have different gamuts
i.e. they cover different regions on the chromaticity diagram


#### Perceptually Organized Color Spaces

##### HSV

Hue-Saturation-Value


##### CIE LAB

aka L\*a\*b\*

亮度跟兩組互補色當軸


##### CMYK

之前都是加法的色彩空間，CMYK 是減法的，印刷業常用

其實 CMY 就夠了，多用一個 K 是因為如果每次用到黑色都要拿貴貴的彩色顏料來混太浪費了，直接用便宜黑色顏料就好


## L21 Animation

### Keyframe Animation

關鍵幀動畫的關鍵是插值



### Physical Simulation

用物理公式模擬出來的動畫
模擬跟外貌算繪是分開的

#### Mass Spring System

這邊介紹質點彈簧系統作為例子

  

理想彈簧沒長度


加個長度，力跟長度變化量成正比，並且考慮方向


但這樣彈簧會一直震盪停不下來，我們還需要加上彈簧本身的內部阻力

想法是，阻力要阻止物體運動，所以跟速度成正比，但是方向相反
（有些像磁鐵通過線圈時會減速）

只考慮相對速度，因為只有相對速度會改變彈簧長度

相對速度需要點乘 $\frac{b-a}{||b-a||}$，計算將速度投影在彈簧方向上的++大小++，因為垂直這方向的運動不影響彈簧長度 (b 繞 a 圓周運動)

再乘以一個 $-\frac{b-a}{||b-a||}$ 獲得方向
（點點是導數）

#### Structures from Springs

有了彈簧以後可以組成不同的結構


考慮一個網狀結構，用來模擬布料

這個結構無法對抗對角線上的力，還有彎折的力，因為這兩種情況下彈簧長度都不會改變 (彎折的部分想像以其中一排直的質點當軸對折)


所以多加幾條彈簧，紅線的彈力應該要小很多，因為布料很柔軟


（另外也可以用 FEM (Finite Element Method，有限元) 的方式做布料模擬，但老師說不好，而且沒細講）

#### Particle Systems

粒子系統

大 guys John

粒子需要考慮的力

- Attraction and repulsion forces
- Gravity, electromagnetism, ...
- Springs, propulsion, ...
- Damping forces
- Friction, air drag, viscosity, ...
- Collisions
- Walls, containers, fixed objects, ...
- Dynamic objects, character body parts, ...

除了星系演化、液體之類的，也可以拿來模擬鳥群（repulsion 是不想離別人太近）

### Forward Kinematics

正運動學，給定一系列的關節，經過一堆轉動以後，端點應該在哪裡

### Inverse Kinematics

給定端點位置，關節們應該怎麼動



雖然可以搞出解析解，但太難了，而且可能有多組解或無解的情況

 

所以通常不會這樣做，而是給定一個初始狀況然後用 gradient descent (or Newton’s method, or other optimization procedure) 看要怎麼移動到給定的方向

### Rigging

綁骨架，用一系列控制點去控制模型，像之前的 Bézier curve 一樣


可以用各種動作捕捉的技術


## L22 Animation (cont.)

接著講如何模擬單一粒子的運動

### Single Particle Simulation

假設一個粒子的運動受一個 velocity vector field (速度場) $v(x, t)$ 決定，給定位置與時間點就能知道粒子的速度是多少
（蛤？阿這速度場怎麼來的，為什麼是速度不是加速度，紀錄受力大小比較合理吧？）


而我們想知道的是粒子在時間 $t$ 時的位置，所以要解 ODE (Ordinary Differential Equation)

$\frac{dx}{dt} = \dot x = v(x, t)$

#### Euler's method

做法是就真的從初始狀態一步一步走過去，步長由 $\Delta t$ 控制

 

雖然這方法簡單又常用，但是 **inaccurate** 又 **unstable**

- **Inaccuracies**：
因為把時間離散化所以會有誤差，而且誤差會累積，走錯以後又走錯，模擬愈久差愈多。把步長 $\Delta t$ 改小可以改善
準度問題而已，有時可以接受
- **Instability**：
有些 case 就算把 $\Delta t$ 調小，模擬也無法收斂到正確的結果上
無法忽略，因為是整個大錯特錯

所以需要一些方法來解決 Instability，前三個是改良版的 Euler's method

- Midpoint method / Modified Euler：起終點速度取平均
- Adaptive step size：誤差太大時，自動縮小步長
- Implicit methods：用下一個時間點的速度 (困難)
- Position-based / Verlet integration

#### Midpoint method

1. 先用原本的 Euler's method 算出下一步去哪
2. 取中點，並看中點的速度
3. 用起點的位置跑中點的速度

（不用當前的速度走，而是偷看一下之後半步的速度，拿來現在用）
上面跟下面這個一樣（但我看不出哪裡一樣，上面是中點的速度，下面是速度的中點，不是不一樣嗎？）


而這個可以展開成下面這樣
總之要說的是，中點法其實就是泰勒展開多取到二階導數，所以比較準確


#### Adaptive Step Size

根據誤差大小去調整步長

用 step size T 算一遍，再用 T/2 算一遍，如果兩者差太多就把 T 除以 2，重複直到誤差在可接受範圍內

是個實用的技巧，但可能會需要很小的步長

 

#### Implicit Euler Method

沒搞懂


O(h^2^) 表示步長減少一半，error 變1/4


#### Runge-Kutta Families

Runge-Kutta 是一系列的方法

不懂，反正就經過一系列推導得來的神奇公式


#### Position-Based / Verlet Integration

- Idea:
- After modified Euler forward-step, constrain positions of particles to prevent divergent, unstable behavior
- Use constrained positions to calculate velocity
- Both of these ideas will dissipate energy, stabilize
- Pros / cons
- Fast and simple
- **Not physically based**, dissipates energy (error)

拿彈簧舉例就是如果彈簧被拉超過某個長度，就立刻讓彈簧恢復原本長度
中間涉及複雜的物理簡化過程

### Rigid Body Simulation

講完粒子模擬，接著來模擬剛體

Rigid Body $\Rightarrow$ 剛體 $\Rightarrow$ 不會發生形變 $\Rightarrow$ 整個物體都用同一種方式運動 $\Rightarrow$ 可以把物體視為一個粒子模擬，只是需要考慮其他旋轉之類的物理量


### Fluid Simulation

#### A Simple Position-Based Method

假設

- 液體由一堆剛體圓球組成
- 液體密度不變 (不可壓縮)

那只要有個地方的球球密度不對，我們就調整周遭球球的位置，讓密度回到原本的值，這樣就行了

為了要知道怎麼調整球球來讓密度改變，所以我們需要知道任何一顆球球的位置變動，會導致任何一處的密度如何變化，也就是 the gradient of the density anywhere w.r.t. each particle’s position
當密度改變時，用 gradient descent 來更新球球位置！


#### Lagrangian vs. Eulerian

兩種不同的方法，用來模擬一大堆東東

一個是把每個東東當主體，看它要怎麼動
一個是把空間分割成很多小格子，看格子裡隨著時間要發生什麼事


#### Material Point Method (MPM)

結合了 Lagrangian 跟 Eulerian

- **Lagrangian**: consider particles carrying material properties
- **Eulerian**: use a grid to do numerical integration
- **Interaction**: particles transfer properties to the grid, grid performs update, then interpolate back to particles

質點紀錄材質資訊，網格內看要發生什麼變化，再把資訊寫回質點內


## END