遍插茱萸少一N
Intro
Geometry
Curves
有多種描述曲線的方式：顯式曲線 \(y=f(x)\)；隱式曲線 \(x^2+y^2=1\)；參數化曲線 \(\gamma(t)=(x(t),y(t))\)。
當然，最終畫出來的還是 折線 (polyline)。不過，我們還是希望儲存一條盡量光滑的曲線的。
可以使用一組控制點繪制曲線。有兩種方式：
- 插值 (interpolation)，要求曲線嚴格經過所有特定點。
- 近似 (approximation)，要求其靠近即可。
但插值方法更加不穩定，所以大家為了方便，都選用后者。
來點 Bézier 曲線！對于 \(n+1\) 個控制點 \(\b b_0,\dots,\b b_n\)，定義 Bézier 曲線為
其中 \(B_i^n(t)\) 是第 \(i\) 個 \(n\) 次 Bernstein 多項式
其構建方式也可以理解為，首先在所有 \([\b b_i,\b b_{i+1}]\) 上繪制 \(n\) 段 \(1\) 次 Bézier 曲線，得到 \(\b b^1_0(t),\dots,\b b^1_{n-1}(t)\)：\(\b b^1_i(t)=t\b b_i^0+(1-t)\b b_{i+1}^0\)。然后繼續以它們為控制點，再繼續畫 Bézier 曲線。
于是也可以用下述類組合數方式計算：
此外，使用其它的多項式基，也可以得到其它的控制曲線。它們統一被稱作 樣條 (splines)。
通用樣條公式 (General Spline Formulation)：有 \(Q(t)=\t G\cdot \t B\cdot \t T(t)\)，也即其為三個部分的直接相乘：
- \(\t G\)：Geometry。所有控制點坐標構成的矩陣。
- \(\t B\)：Spline Basis。描述了樣條曲線的數學特性。在 Bézier 曲線的場合，其是 Bernstein 多項式的系數；其它樣條函數使用不同的矩陣。
- \(\t T(t)\)：Power Basis。一般使用標準多項式基 \(\begin{bmatrix}1&t&t^2&\dots&t^n\end{bmatrix}\) 即可，單獨摘出來是為了清晰。有些小眾用法也會用 Legendre 多項式等，但一般沒人用。
Bézier 曲線因為其擁有的眾多良好性質，所以在一眾樣條曲線中格外受到青睞：
- 對起訖點的插值性：有 \(\b b(0)=\b b_0,\b b(1)=\b b_n\)。
- 對起訖線段的切性。特別地，在三次 Bézier 的場合，有 \(\b b'(0)=3(\b b_1-\b b_0),\b b'(1)=3(\b b_3-\b b_2)\)。
- 仿射變換性 (affine transformation property)：任何對曲線的變換都可以被換成對控制點的變換。
- 凸殼性 (convex hull property)：曲線完全落在控制點的凸殼內。
因為這些性質，我們不使用難以控制的高階 Bézier 曲線，而是使用更簡潔的 分段三次 Bézier 曲線 (piecewise cubic Bézier curve)。一個 \(n\) 段三次 Bézier 曲線有 \(n+1\) 個 節點 (knots) \(\b k_0,\dots,\b k_n\)，第 \(i\) 段曲線 \(\b b_i(t)\) 連接 \(\b k_{i-1}\) 和 \(\b k_i\)。每段曲線有四個控制點：
- \(\b p_{i,0}=\b k_{i-1}\)。
- \(\b p_{i,1}\)。
- \(\b p_{i,2}\)。
- \(\b p_{i,3}=\b k_i\)。
直接每一段嗯插，保證了曲線是 \(\s C^0\) 的。
因為起訖線段的切性，只要 \(\b p_{i,2},\b k_i,\b p_{i+1,1}\) 三點共線，即可保證曲線屬于某種 \(\s G^1\) 類。
如果要進一步保證曲線是 \(\s C^1\) 的，則由起訖點導數公式，還要保證 \(\b p_{i,2},\b k_i,\b p_{i+1,1}\) 三點等距，即保證曲線屬于 \(\s C^1\) 類。
此外，還能通過額外的約束保證曲線是 \(\scr C^2\) 的，但是比較復雜不做贅述。
Surface
至于面，我們一般使用參數化曲面，使用映射 \(f\) 把參數域 \(U\sub\R^2\) 映到真實空間上，其得到的點集 \(f(U)\) 即為該參數化得到的像集。
一個簡單的方法是 Bézier 曲面：有
相當于是 \(u,v\) 兩個方向的兩次近似。
3D Representations
無論是 Bézier 曲線還是曲面，都是比較 toy 的應用。真實在大規模表達 3D 場景時，都使用更加樸實的方法。這些方法大體分為兩類，即 柵格化形式 (rasterized form) 和 幾何形式 (geometric form)。
前者例如 多視角 (multiview) 方法，拍一堆照片，并嘗試重建物品?；蛘?景深圖 (depth map)，需要來自照相機的額外信息，但是仍然是圖片，且受到精度等限制，更別提還有透明物品這種重量級角色。還有 體積表示 (volumetric representation)，化成一堆小方塊表示，也是老古董了。
后者因為不依賴于任何 grid 表示，所以是絕對的主流。其有兩種最常見的模式，即點云和 mesh。
點云 (point cloud) 是最簡單的表示，有一堆無聯通性的點，有時還會加上表示朝向的 normal。加上朝向的點即被稱作 面元/點元 (surfel)。
如何獲得點云？可以直接掃描。當然也有其挑戰：噪聲；低分辨率；會出現與其它部分不相連的部分；有 遮擋 (occlusion)。當然也可以直接從已經存在的虛擬圖像上獲取。但是如何獲取呢？
- 關于表面積 i.i.d. 選取。容易實現，但是因為實際采樣點數有限，會出現不夠均勻的場景，而一旦不均勻，在應用方面就會有大問題。
- 因此實際上會選取一些有足夠保障的方法。例如，選取兩兩點間距盡量遠的采樣。這雖然是 NP-Hard 問題，但是存在足夠好的近似。
另一種方式是 mesh，使用分塊的線性表面（即平面）來表示一個表面。
首先，一堆首尾相連的點構成一個多邊形。平面 (planar) 多邊形要求所有點共面。簡單 (simple) 多邊形在此基礎上要求不自交。
一個 polygonal mesh 是一堆封閉、簡單的多邊形，其中兩兩多邊形的交是空、單點或線段（適用于 triangle meshes）。因此，可以使用 \(M=(V,E,F)\) 的方式來描述。
triangle mesh 即為所有面均為三角形的 mesh。其中的 \(V\sub\R^3,E\sube V\times V,F\sube V^3\)。
一個 manifold mesh 在此基礎上，要求每條邊與一個或兩個面相鄰（即，不能允許書軸——它同時與多個書頁相鄰），且與一個頂點相連的所有面形成一個 closed 或 open fan（即，這個頂點不能是一個割點）。
在此之上，更強的要求是 watertight manifold，顧名思義，其是一個「不漏水」的封閉或半封閉 manifold。有很多先進算法都有這種要求。
雖然 manifold mesh 很好，但是因為它比較苛刻，有時不得不使用被稱作 triangle soup 的方式，直接簡單粗暴地放一堆三角形，不做任何組織。這樣做是最簡單的方式，在不需要應用先進算法時，是有效果的。
此外，我們不希望 mesh 中各個三角形大小參差不齊，或是角度雜亂無章。這是因為過大的三角形影響插值：如顏色等信息儲存在頂點上，而一個面的信息完全依靠其周圍一圈頂點的插值，而面積太大了插值就會出誤差。可以通過 cleaning, repairing, remeshing 等方式優化 mesh 結構。
如何存儲一個表面？要存儲的信息包括幾何結構、topology、屬性（如朝向、顏色、材質）等。
一種方式是 Triangle List 格式：直接存儲所有面，每個面使用連續的三個點。但這顯然有很多冗余，有很多點在各種三角形中重復出現。
另一種是 Indexed Face Set 格式，分開儲存頂點坐標和三角形三頂點編號。傳統是以逆時針存儲三角形的頂點，以保證定向。
這兩種都是比較頂端的設計，其具體也有很多底層實現，對各種細節有不同的約定方法。
但是注意到，有 M?bius 帶這種神秘的不可定向曲面，因此定向也需要技巧。
Mesh Reconstruction
如何由點云建立 mesh？
一種思路是 explicit mesh reconstruction，選擇一個超參數 \(\rho\)，并且假設所有相鄰節點有足夠密度。然后，將三個點組成一個三角形，如果可以用一個 \(\rho\) 球同時過三點，并且不包括其它任何點。當然，這極度依賴 \(\rho\) 的選擇。
另一種思路是 implicit mesh reconstruction，估算一個 field function，然后提取等勢面。更詳細的過程將在下節課闡述。
此外，很多算法要求 mesh 是 watertight manifold。但是不管是人工搓的還是算法生成的，很多 mesh 都不滿足該條件。有一些高明的算法可以生成這種 manifold，但不在本課程教授范圍內。
Mesh Subdivision
給定一個低分辨率 mesh，有時我們會希望進行 upsampling，獲得更高精度的 mesh，也即 mesh subdivision。一種思路是 smoothness prior，即盡量讓高精度的場合更光滑（雖然有時這不是我們的目標——這是使用 smoothness 作為 prior 的必要代價！）。
一種稱作 Loop Subdivision 的方法，大體思想是將每個三角形在每條邊的中點處切開，切成四個小三角形。顯然，其僅適用于 triangle mesh。
- 對于每條邊，建立一個 odd vertice：
- 假設其被 \(ABC\) 和 \(ABD\) 兩個三角形共用，那么 \(AB\) 的新中點被設為 \(\dfrac38(A+B)+\dfrac18(C+D)\)。
- 否則，其處于 mesh 的邊界上，直接設為 \(\dfrac12(A+B)\)。
- 對于每個點，其被更新為 even vertice：
- 假設其所有相鄰面構成一個完整的角，則其更新為 \((1-n\cdot u)p_x+u\cdot\sum_{y\in\t{neighbour}}p_y\)，其中 \(x\) 是該節點，\(y\) 是其所有鄰居，\(n\) 是其度數，\(u\) 在 \(n=3\) 時為 \(\dfrac3{16}\)，其它時刻為 \(\dfrac3{8n}\)。這些神秘系數的設置似乎有巧思，但可以先 take for granted。
- 否則，則其同樣屬于 mesh 的邊界上。只保留邊界上第一個鄰居 \(p_a\) 和最后一個鄰居 \(p_b\)，中間的那些鄰居全都忽略，然后更新為 \(\dfrac34p_x+\dfrac18(p_a+p_b)\)。
- 每一輪更新時，都是從上一輪原有的點上更新，而不會從這一輪新增的點中更新。
Catmull-Clark Subdivision 是另一種方法，它為原本的每個面在所有頂點的幾何平均處新增一個 面點，為原本的每條邊在兩個端點和兩側面點共四個點的平均處新增一個 邊點，然后通過一些繁瑣的公式更新原始頂點的位置為 新頂點。新 mesh 中的頂點即為上述四類，而邊為新頂點到鄰邊邊點，以及面點到鄰邊邊點。可以發現，新圖中的每個面恰好包含這兩類邊各兩條，因此經歷一次迭代后，原本的不規則 mesh 將被轉化為嚴格 quad mesh 即所有面都是四邊形的 mesh。
這種方法對所謂的 奇異點 (extraordinary vertex)，即度數不等于 \(4\) 的頂點，有一些特殊的處理。但是，它證明了奇異點的數目在每次迭代中是不變的，且因為 mesh 不斷細化，其影響范圍會不斷縮小，因此是很優雅的。在迭代取極限后，新平面在絕大多數區域都是 \(\s C^2\) 連續的——除了奇異點，此處只有 \(\s C^1\) 連續性。
特別地，我們有時還需要有一些特定的邊緣不要被鈍化，例如桌角或劍刃。這些邊緣即為 尖銳折痕 (sharp creases)。上述算法均適用 sharp crease，只需要讓邊點不會受到兩側面的影響，直接取兩相鄰點的嚴格中點即可。
還有一些神秘神經網絡手法，不在本課程范圍內。
Mesh Simplification
既然有上采樣，就有下采樣。我們有時希望簡化 mesh。
一種手法是使用 edge collapsing：把一條邊的兩個點（或者進一步，一條折線上的多個點）合并為一個。但是這就有兩個問題：
- 選哪條邊合并？
- 合并完的新點放哪？
與一條邊的合并相關的有很多面，其中除了該邊相鄰的兩個面會直接沒掉，其它面都會重新綁定到新出現的那個上。那么一個自然的想法就是，合并的新點應該要讓這些面的「位移」最少。如何衡量位移？簡單粗暴地，直接取新點到所有原始面的距離平方和即可。這被稱作 Quadric Error Metrics。當然，也可以使用更沒有技術含量的平均點或中點等。
具體而言，假如一個平面是 \(ax+by+cz+d=0\)，則點 \((x,y,z)\) 到其的距離就直接是 \(ax+by+cz+d\)。于是令 \(p=(a,b,c,d),v=(x,y,z,1)\)，則平方和就是 \(v^T(p\cdot p^T)v\)。
如何求解 \(p\)？注意到 \((a,b,c)\) 其實就是平面的法向量。
第二個問題解決后，第一個問題就很容易了?？梢赃x擇所有邊的中點里面 QEM 最小的一條。但是更好的方法是不機械地強制使用中點，而是解最優化問題得到最優點。效果很好。
還有一些神秘神經網絡手法，不在本課程范圍內。
Mesh Deformation
有了 3D representation，我們第一件想干的事是什么？顯然是與它作為整體進行一些交互！這些交互可以是主動的，例如拉扯；也可以是被動的，比如說物理模擬等。交互前后，mesh 的形狀會有改變，這就是 mesh deformation。
希望有一些自動化的方式來處理 deformation。于是可以定義一個 deformation energy，雖然叫 energy 但其其實是一個過程量，對于每一種 deformation 獨立定義。我們希望剛性的旋轉、平移等不改變之，但是非剛性的拉伸、彎折改變之。這樣 deformation 即可變為一個最優化問題。
一個方法是定義 local deformation energy 為
這個 energy 針對一個頂點 \(v_i\) 及其全體相鄰點 \(v_j\)，而 \(v_i',v_j'\) 是 deformation 后的新頂點。\(R_i\) 是旋轉矩陣，用來處理旋轉：如果兩個圖形旋轉等價，那么必然存在一個 \(R_i\) 能復現旋轉；而 \(v_i-v_j\) 用來處理平移。因此，在剛體運動下，該能量為零。
然而，拉伸會導致間距變大，彎折會導致旋轉無法被復現，這兩種情況下該能量都會上升。
直接加和所有頂點處的能量，得到 total deformation energy。在 deformation 中最小化這個值，就是所謂的 As-Rigid-As-Possible (ARAP) deformation。在這種策略下，使用最少的輸入信息即可復原整個形變。
Volume Deformation
以上是 mesh 進行 deformation 的方法。如果是整個體積的形變呢？有一個 free-form deformation 的算法。
它定義了一個 形變場 (deformation field)，并將所有點在這個場里過一遍。如何求形變場呢？可以只在頂點處定義形變量，然后中間的部分使用 Bézier 曲線插出來。模型師只需要拉動頂點，提供形變量即可。
使用三維 Bézier
Implicit Representation
之前我們描述曲面的方式是顯式的，即 \((u,v)\to(x,y,z)\) 的映射。它可以很好地處理采樣等，但是如果要判定一個點是在閉合曲面內部還是外部，就會比較困難。
因此另一種方式是隱式的：定義一個 \(f(x,y,z)\) 的函數，然后令 \(f(x,y,z)=0\) 處即為曲面。此時采樣困難但判定內外簡單（因為函數的連續性，可以人為操作該函數使得函數小于零處即為體積內部）。
但是隱式描述對于復雜曲面會比較棘手。可以將其定義為多個簡單體積的交并補，使用 Boolean 代數方式實現。還有一種方式是 distance function，即記錄空間中所有點到曲面的最小距離，然后取兩個曲面的并就是取 min。有一些更加 smooth 的 distance，其可以實現類似于「引力形變」等效果。
當然更多的時候封閉形式的 \(f(x,y,z)\) 還是太復雜了?？梢灾苯忧蟹志W格然后記錄每個格中的值，然后通過插值得到光滑的曲面。這就是 level set methods。
Transformation
如何描述兩個 3D 物體的朝向？這需要兩個信息：「相對位置」和「朝向」。
如果要計算之，就需要處理變換關系。
變換可以用 \(x\mapsto f(x)\) 描述。
2D Linear Transformation
我們更喜歡滿足 \(f(x+y)=f(x)+f(y),f(ax)=af(x)\) 的線性變換。先考慮 2D 的場合。
拉伸是線性的，且允許不同方向的不同比例拉伸。其通過對角矩陣描述。
旋轉是線性的。同時是等距的。
平移不是線性的。但是是等距的。
鏡像是線性的。同時是等距的。但是不是剛體的。在現實世界中無法達成——除非你使用鏡子。
剪切 (shearing) 變換，即所有點按照正比于與某個軸的距離形變，是線性的。
剛體變換是保持朝向的等距變換，也即平移和旋轉的組合。
在沒有平移時，變換可以簡單使用矩陣乘法描述。但有了平移怎么辦？
所以我們要考慮 homogeneous coordinates (in 2D)。對于點 \((x,y)\)，其對應為 \(3\)-向量 \([x,y,1]^T\)，而 \([x,y,w]^T\) 會被還原為 \((x/w,y/w)\)。
那么包括平移在內的上述所有變換都變成了 \(3\times3\) 矩陣乘法。
類比：一維的仿射（也即線段平移）其實是二維的剪切。
3D Linear Transformation
2D 的場合，2D-H 足以描述一切我們喜歡的變換。3D-H 的場合仍然可以，但是冗余有點多了。
2D 旋轉可以只用一個變量 \(\theta\) 描述，換句話說只有一個自由度。但是 3D 旋轉有 3 個自由度。進一步，\(n\)-D 旋轉集合是 \(\t{SO}(n)=\cur{R\in\R^{n\times n},RR^T=I}\)，即全體正交變換集合。
不存在 \(\t{SO}(2)\) 到 \((-1,1)^n\) 的可微雙射，也不存在 \(\t{SO}(3)\) 到 \((-1,1)^n\) 的。這意味著無法使用可微的參數化方式刻畫旋轉面。這意味著如果要實現神經網絡處理這些東西，需要一些特殊的設計。
3D Rotation Representation
一種方式是 euler angle 也即極坐標。有兩種：static（與某個固定坐標系相對）和 dynamic（坐標系是可變的）
關于主軸的旋轉可以簡單使用矩陣刻畫。那么任意旋轉可以寫成三軸旋轉矩陣的積。這玩意確實連續可微，但它不是雙射——一個方位可以由多種主軸旋轉方式得到。
此外，在某個角度達到某個特定值時，另外兩個角度的旋轉會變得等價，也就是說失去了一個自由度，這就是 gimbal lock。這會讓例如 GD 等方法出現問題，難以沿著正確的角度繼續下降。
另一種方式是 axis-angle。所有的三維旋轉都可以用一個單位向量轉軸 \(\hat\omega\) 和一個旋轉角 \(\theta\) 描述，二者之積 \(\vec\omega=\hat\omega\theta\) 也被稱作 rotation vector 或 exponential coordinate。
但這仍然存在非唯一的現象。例如，\((\hat\omega,\theta)\) 和 \((-\hat\omega,-\theta)\) 給出相同的旋轉。此外，\(\theta=0\) 時，\(\hat\omega\) 怎么選都一樣。當然，\(\theta\in(0,\pi]\) 時，方案還是唯一的。當然直接使用 exponential coordinate 可以解決這兩個問題，但仍然沒有解決 \(\theta=\pi\) 時的斷點問題。
通過 axis-angle 可以定義兩個旋轉方案的間距。具體而言，找到二者差后，解出其 \(\theta\) 即為二者間的旋轉角，也即其旋轉距離。
來點四元數。其是 \(q=w+xi+yj+zk\)，滿足 \(i^2=j^2=k^2=ijk=-1\) 和反交換律。
使用單位四元數表示旋轉（撤掉一個自由度）。將 \(\vec x\) 增廣到 \(x=(0,\vec x)\) 后，有 \(x'=qxq^{-1}\)，則旋轉的組合就是四元數的相乘。
四元數是好的：因為它只要存儲四個量而不是 \(3\times3\) 或 \(4\times4\) 矩陣，算起來也更容易。
此外，exponential coordinate 可以和四元數間簡單互換：有 \(q=[\cos(\theta/2),\sin(\theta/2)\hat\omega]\)。因此二者間存在緊密聯系。
通過 exponential coordinate 作為中繼，其也可以與常規 rotation 的矩陣形式互化。
不同的軟件使用不同的順序存儲四元數。
總結：
旋轉矩陣：求逆和復合都容易。
Euler Angle：都困難。
Angle-Axis：前者容易后者難。
四元數：都容易！所以大家都用四元數。
但是它們都不是也不可能是可微雙射。
Viewing Transformation
如果拍照，則涉及到多事物的變換：有景觀的變換即 model transformation，攝像頭的變換即 camera transformation，以及將 model 映到攝像頭的 projection transformation。
描述攝像頭需要三個量：攝像頭方位 \(\vec e\)、攝像頭角度 \(\hat g\)、攝像頭滾角 \(\hat t\)（決定了照片旋轉角）。
按照運動的相對性，可以讓攝像頭始終處于位于原點、\(\hat t\) 指向 Y，\(\hat g\) 指向 -Z 的方向，只需要讓 model 動即可。
Projection Transformation
將 3D 的圖像投影到 2D 的平面。有兩種方式：perspective projection，假設有一個攝像點，然后取了一個截面；orthographic projection，直接平行投影過去。
Orthographic Projection 很容易，因為我們在看 -Z 軸，所以直接把 Z 維度扔掉，全部投影在平面上即可。當然實際需要作一點 scaling（將其變成 canonical 的 \([-1,1]^3\) 視角）以及處理遮擋關系等。
有些庫（比如說 OpenGL）認為看 -Z 不直觀。所以它們使用了左手系。
Perspective 最常用。它把視野（它是一個梯臺）壓縮為長方體，然后作 orthographic projection。壓縮使用簡單（？）幾何推理即可，其是一個非線性變換，但是可以在 3D-H 中實現。
但是存在一個問題，就是當兩個平面真的貼的很近且離攝像機很遠時，就對精度要求很高。
Detailed Workflow
還是詳細點介紹渲染時的變換流程吧：
- modeling transformation，由 object space 變換到 world space。并非必須步驟——很多時候 object 已經以絕對坐標的形式存在于 world space 中了。是仿射變換。
- camera transformation，由 world space 變換到 camera space，攝像頭面向 -Z 方向。這意味著我們關心的東西是 X-Y 平面之下的東西。是仿射變換。
- projection transformation，由 camera space 變換到 canonical view volume 即 \([-1,1]^3\)，或稱 Normalized Device Coordinate (NDC)。分為 orthographic projection 和 perspective projection 兩種，前者是仿射的，后者不是。
- viewpoint transformation，把 \([-1,1]^3\) 拍扁到屏幕上。首先先把 X,Y 兩個軸拉伸到 \(w\times h\) 像素的平面上（這一步是是仿射的），然后再用 Z-Buffer 把所有東西疊一塊即可。
Orthographic Projection 就是把 \([l,r]\times[b,t]\times[-f,-n]\) 映到 \([-1,1]^3\)，公式也很簡單粗暴，就是
注意，手工驗算后可以發現，變換到 NDC 后，\(z\) 值越?。ㄔ浇咏?\(-1\)）則越靠近攝像機，這一點與 camera space 中不同。
Perspective Projection 先做了一步「擠壓」，認為：從原點出發畫射線，與 \(z=-n\) 和 \(z=-f\) 兩個平面的兩處交點，應該在 perspective 下具有相同的 \(z\) 坐標。可以使用以下方法做到這一點
對于 \((x,y,z,1)^\top\)，先左乘這個 \(M\)，然后再除以 \(w\) 作歸一化即可。然后就是再套一層 Orthographic 轉成 NDC。因為 Orthographic 是保 \(w\) 的線性變換，所以可以交換順序，直接一次性左乘 \(OM\) 然后再除以 \(w\)，于是有
這樣推出的 Perspective Projection 的實際感受野在 \(z=-n\) 處仍是 \([l,r]\times[b,t]\)，而在 \(z=-f\) 處會等比例擴大。
實際采用的 \(P\) 是它取反后的結果。首先這個矩陣前面乘以任何常數都是不影響最終結果的（因為最終都是要除以 \(w\) 的），所以兩種方式的效果相同。其次取反后的結果是在對 \(z>0\) 時的分析，可能更常見。
DL + ACG
令 \(S\) 為 shape，\(c\) 為 label 或 condition。
則 \(P(c\mid S)\) 是 shape analysis 的范疇：它在分析一個 shape 的性質，比如說分類、segmentation、景深估計等。
另一方面，\(P(S)\) 或 \(P(S\mid c)\) 是 shape synthesis 的范疇：它就是 (conditional) generation。
Multi-View CNN
如何作分類？直接拍一堆各種角度的照片然后丟進 CNN 開識即可。
3D CNN
另一種想法是把 3D model voxelization 化，也即放到 grid 里面（與 2D 的 pixel 相對）。有了 grid 之后就可以作 3D convolution。
但是問題是多了一維對復雜度的影響是極大的。但有一個好消息：隨著 resolution 的提高，occupied voxel 的比例會不斷下降，所以可以利用 voxel 的稀疏性，只存儲表面 voxel 然后作稀疏卷積。稀疏卷積只在原始有值處進行卷積，因此隨著層數加深，稀疏性不變。
還有一種想法是在不同地方使用不同精度的 voxel。例如在 3D 的場合，我們可以建 八分樹 (octree)，在例如桌子表面等光滑場景使用粗精度的 voxel。當然它實現起來有一些挑戰。
Point Cloud Based Methods
還有一種想法是直接接受 point cloud 作為輸入。我們的輸入是 \(n\) 個 \(d\) 維向量。
但是我們需要一個性質：即我們的神經網絡應該是 對稱 的，其與點云的輸入順序無關。
這不是我們 attention 嗎 但還是來點古早手法吧。
可以構造結構 \(f(x_1,\dots,x_n)=\gamma\circ g(h(x_1),\dots,h(x_n))\)，其中只有 \(g\) 是一個 symmetric operator（比如 sum 或 max），\(\gamma\) 和 \(h\) 都是任意神經網絡。則這個結構確實是 symmetric 的。
并且這個結構確實是有意義的：\(h\) 可以是把點轉成 one-hot 向量的 operator，那么 \(g\) 是 max 時，它就把 point cloud 轉成 voxelization 了。因此 \(g\) 完的東西確實可以反映原始圖像信息。
這就是樸素 PointNet。但是它顯然問題很大：比如說其沒有點的 local context；比如說其基于絕對坐標，對平移是敏感的，難以 generalize。
所以直接建一個 hierarchial 的結構，每次對鄰域使用 PointNet 結構即可。鄰域中也可以使用相對坐標，這樣就有了平移不變性。這就是 PointNet++。
……但它還是會受到旋轉影響的。
另一種想法是用我們 GNN。它使用 point cloud 的相鄰性建圖然后跑 GNN。此乃 Message-Passing GNN。
但有一個問題是這玩意沒有 sampling invariant——其受到在 point cloud 中采樣的影響。
另一種想法是直接使用點云密度進行處理。例如可以設計一些能在點云密度上工作的卷積核，或者使用 Monte Carlo 采樣等方法。
還有人試圖從 Fourier Analysis 也即 spectral domain 的角度展開分析。沒聽懂。
Single-View Conditioned 3D Modeling
如何只使用一張圖片建立 shape？顯然其事實上存在多種解釋方案（視錯覺），但視錯覺之所以是錯覺就是因為它們不常見，所以我們只需要在那些常見場合跑得好即可。
有人試圖使用 model-based fitting，即建立一些常見模型然后嘗試通過 transformation 令其與待識別圖像重合。還有人進一步使用 scene-based fitting，即將場景也建模。但顯然這是非常不靈活的。
所以現在大家都使用 data-driven modeling 了。
一種想法是首先先 predict depth 得到 2.5D 的景深圖，然后使用之輔助建模。
但問題是景深仍然存在不確定性，我們只能預測相對景深（因為近處的小物體和遠處的大物體看起來沒有區別）。
因此訓練景深圖時的 loss 不是 \(\|y-y^*\|\)，而是 \(\|\log y-\log y^*\|\)。
不過我們可以使用一些先驗知識，例如人的身高等。
Rendering
Screen
顯示屏是一個二維平面，一個二維的離散畫布，像素的大小即為分辨率。我們要將三角形的 mesh 繪制到屏幕上。
早期的顯示方式是陰極射線管 (Cathode Ray Tube)，放出大量電子，經過電磁場偏轉、加速后，擊打在屏幕上。
但是這個成像方式是模擬的，所以需要 Digital to Analog Convertors (DAC) 把數字量轉成模擬量，然后再提供給 CRT。
液晶顯示器 (Liquide Crystal Display) 則是數字的，數字量轉為模擬量的過程發生在每個像素。
Sampling
手機中的 RGB 像素是獨立的；筆記本上的像素邊緣亮度和中心亮度并不同；不過即便如此，我們還是把它當作一堆顏色均勻的小格子。
如何將三角形投影到像素格？只要檢查每個像素的中心是否處于三角形內部即可。這就是對 indicator function 的 sampling。但是如何高效地 evaluate 每個中心是否位于內部呢？
對于一條直線，可以用一個法向量 \(\v n\) 和一個基準點 \(\v p_0\) 描述?？梢杂?\((\v p-\v p_0)\cdot\v n>0\) 來判斷點 \(\v p\) 在直線的哪一側。作三次點積即可判定一個點是否位于內部。
另一種方式是用三次叉積。
但不管怎么說，我們都會判單點了。但我們顯然不是很希望對于整個平面上的所有點都進行判定（如果三角形很?。?，所以我們可以對三角形造一個 bounding box，只對 box 內部的點判定。進一步還可以作 hierarchical rasterization，跑四分樹，如果一個塊完全與三角形不交即可停止展開子樹——但是這樣做不一定更快。
Antialiasing
直接把 sampling 傳過去會導致 aliasing，即鋸齒狀的邊緣。這個術語其實來自于信號處理：高頻信號需要更高的采樣頻率才能貼合。
解決方案也很簡單：在 sample 前對三角形加個模糊，即可產生非純色的邊緣，鋸齒化的現象即減輕。模糊必須發生在采樣前（而非先采樣再模糊）。
還是得補課信號處理！
如果兩個高頻信號在同一個采樣率下是 indistinguishable 的，它們就互為 aliases (混疊)。
一個光滑的時域信號，其主要是低頻的，集中在 \(f=0\) 附近。
采樣頻率在時域上是一堆離散信號 \(P_\delta(kt)\) 。在 Fourier 后，其在頻域上同樣是一堆離散信號 \(P_\delta(kf)\)。
現在采樣了，就是倆玩意在時域上作點積，切換到頻域上就是卷積，即為一坨坨集中在 \(kf\) 附近的信號。如果 \(f\) 間間隔太小，則兩坨 \((k-1)f\) 和 \(kf\) 對應的信號就會混疊。
提高采樣頻率就會讓頻域上的周期拉長，\((k-1)f\) 和 \(kf\) 之間拉遠，混疊即減少。另一種方法是把高頻信號（劇烈的變化）篩掉，在時域上的影響就是模糊，對采樣結果的影響就是混疊減少。
所以模糊確實有助于減輕鋸齒化?。。?/p>
比如說，使用一個 1x1 的模糊，實現的結果就是一個 pixel 的輸出顏色，即為其被三角形覆蓋的面積。
但是算這個太麻煩了。簡單粗暴的做法是 supersampling，直接在一個 pixel 中作多個 sample，然后 pixel 的輸出為其中均值即可。
Z-Buffer
以上內容處理了如何將一個 2D 三角形 rasterize。但是 3D 的場合還有一個額外的 \(z\) 軸，每個 pixel 應該顯示 \(z\) 最小的三角形。
那么就直接為每個 pixel 分配一個 Z-buffer 儲存當前 \(z\) 值，渲染一個新三角形時，只在其對應的 \(z\) 值小于當前 Z-buffer 值時才更新。
Conclusion (Pseudo)
雖然以上很對，但是我們還需要渲染陰影。所以還不夠?。?！
Conclusion (Real)
這類問題可以歸結為從 源信號空間（如 mesh 或 texture）到 目標采樣空間 也即 screen 上的每一個 pixel 的映射。目標是「查詢」一個 pixel 對應了哪些東西。其有兩種理解方式：pixel 作為離散的一個「點」，被源空間中的另一個「點」所映射，該源點的信息即為 pixel 的信息；或者，pixel 作為連續的一個「方格」，被源空間中的一片形狀可能不規則的「區域」所映射，該區域中的平均信息即為整個 pixel 的信息。前者是最易于實現的，但我們的目標是后者。
rasterization 的源空間是 連續 的 NDC；texture rendering 的源空間則是 更高/低精度 的 texture map。后者的精度也不一而足——在靠近攝像頭處，其精度很可能低于 pixel 精度，而遠離處則恰恰相反。
假如源空間的精度低于 pixel 的精度，則此時是在做 upsampling，技巧包括「在源空間中，尋找離 pixel 投影點最近的源點也即 nearest neighbour filtering」或者「將投影點周圍臨近源點信息插值也即 bilinear filtering」等。裸的 mesh rasterization 一般沒有這種需求——因為其是連續的，源空間的精度一般總是高于 pixel 的精度。
假如查詢區域的精度高于 pixel 的精度，則此時是在作 downsampling。
- 簡單粗暴但低效的做法是 supersampling，通過進一步細分 pixel 為更小的單點，查詢它們的像點信息后，綜合作為當前點的信息。
- 像 NDC 這種「連續」的場合，直接對圖像進行預模糊即可。
- 像 texture map 這種「目標固定且預給出」的場合，可以直接預處理出來其上的求和數據結構，例如 mipmap（四分樹式數據結構）或 ripmap（mipmap 的升級版，允許以任意順序歸并整張圖）。在查詢時，找到當前 pixel 在 texture map 上的像區域，然后直接強行把它擬合到最接近的正方形（mipmap）或長方形（ripmap），并使用預處理的信息返回。
Shading
Reflection
光是如何在物體表面反射的？首先有 diffuse reflection「散射」：入射光會均勻地向所有方向發射，因此其顏色與視角無關。其可以被看做，「吸收光」然后「均勻發射」。
但是也需要計算接收到了多少光能?？梢允褂?Lambert's Cosine Law：吸收的能量與夾角的余弦值呈正比。
此外，點狀光源的場合，光強會與距離呈反比。所以總結為：\(L_d=k_d(I/r^2)\max(0,\v n\cdot\v l)\)，其中 \(k_d\) 表示光源的顏色。
另一種是鏡面反射，此時顏色與視角相關，在反射光路附近最強。
注意到「靠近鏡面反射點」與「half vector 接近法向量」是等價的。于是定義 \(\v h=(\v v+\v l)/\|\v v+\v l\|\)，則 \(L_s=k_s(I/r^2)\max(0,\v n\cdot\v h)^p\)，其中 \(p\) 是建模光如何集中于反射光路的參數。
最后還有一項環境光「ambient light」。以上三者加一塊即得 Blinn-Phong Reflection Model。
Frequency
上述分析指導我們如何對單點渲染。但是整個模型有很多點。有 flat shading，以 mesh 中每個三角形為單位渲染，三角形因為具有相同法向量所以近乎同色，對于光滑表面效果不好。有 Gouraud Shading，在頂點處渲染然后插值。還有 Phong Shading，對于每個像素分開來渲染。
如何獲取頂點處的法向量？可以直接對周邊一圈的面 normal 求平均即可。
Parametrization
不止有表面，還有紋理。紋理就要把 mesh 展開到 2D 平面上，便于藝術家繪制。Barycentric Parametrization 最小化展開過程中的形變，繪制會較為簡單。
當我們需要的結構存在大量重復時，我們可以使用 tilable parametrization，保證紋理 tile 在一塊沒問題。
Barycentric Coordinate
一個三角形 \(\triangle ABC\) 中的位置可以用三元組 \((\alpha,\beta,\gamma)\) 描述：有 \(p=\alpha A+\beta B+\gamma C\)。只要保證 \(\alpha+\beta+\gamma=1\) 且其非負，則其即為一個合法位置。容易實現二維坐標和 barycentric 坐標的互化。
除了坐標，顏色、紋理、法向量、深度……什么都可以平均。
Texture Magnification and Minification
紋理終究也是一個像素化的 2D 圖案，其中的每個像素稱作一個 texel「紋素」。有時其精度不夠，就需要做 upsampling。解決方案包括尋找最近 texel，或者做插值等。
但是 upsampling 終究是少數，更多場合是 mesh 的分辨率不足，需要做 downsampling。此時和 rendering 一樣，應用各種 antialiasing 技巧即可！
一個方式是 mipmap，在 texture 中不停做 range average 以降低分辨率，將結果存儲。然后如果要詢問 pixel 時，就找到該 pixel 對應的方格在 texture 中被映到哪里，然后根據該方格的大小調用對應的 mipmap 層結果即可。通過將相鄰兩層結果求平均，可以讓渲染更加光滑。
但是 mipmap 也有問題：遠處的 pixel 會對應一大塊區域，做了過多插值就會導致模糊。
這是 mipmap 的正方形視野導致的。可以行/列交替 average，然后就有矩形形狀的視野，效果更好。當然也存在一些不與坐標軸平行的視野，所以還有其它方法，但代價是效率降低。
Bump Map
有時我們需要一些微結構信息（例如橘子皮的微小凹坑）。如果通過 mesh 建模就太復雜了，可以直接在 texture 上記錄深度信息，提供微結構。更先進的 displacement mapping 甚至可以通過移除頂點以增強真實性。
Shadow
Shadow Map
一種思路是從光源出發求每一處的深度圖，如果某處被遮擋了，其即不會在深度圖上顯現；而如果其能被攝像機看到，其即為陰影。
但是這樣做會產生「hard shadow」，而實際的陰影是 soft 的。
Ray Tracing
所以需要光追！但是它很慢，所以只能離線渲染（而光柵化可以在線搞）。
Ray Casting
所以只能用次一等的 Ray Casting：從攝像頭發射射線，第一次碰到一個位置后，計算該處的 local shading（由光源決定），然后就不管之后的東西了。
Recursive Ray Tracing
基礎的光追。發射出的射線會計算 Refracted Rays 和 Reflected Rays，將所有交點處的 local shading 綜合。因為每過一次能量均會衰減，所以并不會無限遞歸下去。
Intersection
如何尋找射線與 mesh 的交點？對于每條射線都計算其與所有三角形的交點？這顯然很慢。能不能加速？
首先先提出一個高速的求交點方法。
- 列出平面方程，求出射線與平面交點，然后只需判定是否有射線位于三角形——或者更一般地，任意多邊形——內部。只需要隨便找一個平面（比如說 x-y 平面），把它投影上去，然后使用射線法判定交點是否位于其內部即可。
- 還是太慢！直接使用 \(\v o+t\v d=(1-b_1-b_2)\v A+b_1\v B+b_2\v C\) 然后解方程即可。
但我們還是不能接受 #pixel * #triangle * #bounces 的垃圾復雜度。
解決方案是把所有的 triangle（或更廣泛地，object——但并非指宏觀的物體，仍然指的是 mesh 中的各個面，但不局限于三角形）求 bounding box，若不與 bounding box 有交，則必不與三角形有交。
最常見的是 AABB，axis-aligned bounding box。但是這玩意在變換后不再與軸平行，因此若進行視角變換則要小心。
一種做法是使用固定的 grid 劃分，一條射線經過若干 grid，只需處理那些位于對應的塊內的 object。grid 中的 cell 數目也有講究，一個 heuristic 是 #cell = C*#objects，其中 C 在 3D 場合是 27。
另一種是我們 KDT。KDT 是對空間的劃分，每個葉子存儲一堆 object，一個 object 可以與多個葉子相交。
……但大家都不用 KDT 改用 Bounded Volume Hierarchy 了。它不斷將 object 集合分兩半，計算分出來的子集的 bounding box。兩個兒子的 BB 可以有交。分兩半的方式是長軸的中位數處折半，在剩下的元素數目小于某個閾值時停下來。
總結：KDT 是切空間，物體會被切兩半，但空間不交；BVH 是切集合，兩兒子的 BB 有交，但物體集合無交。
Radiant Energy
輻射通量是單位時間內通過某個面的能量，即 \(\Phi=\dot Q\)。單位是 lumen。
點光源的光照強度是單位立體角的輻射通量，即 \(I(\omega)=\dfrac{\d\Phi}{\d\omega}\)。單位是 candela。光照強度可以與方向有關。
- 圓周有 \(2\pi\) 的平面角。球周有 \(4\pi\) 的立體角。
各向同性的點光源有 \(I=\Phi/4\pi\)。
irradiance 輻照度，是單位面積的輻射通量，有 \(E=\dfrac{\d\Phi}{\d A}\)。單位是 lux。要求光線垂直射入目標表面，否則需要用 Lambert's Cosine Law 投影。
光線傳播中，intensity 不會衰減，但 irradiance 會衰減。
定義輻亮度 radiance 為單位立體角、單位投影面積功率
其中 \(A\cos\theta\) 表明是投影距離。輻亮度同樣不會衰減。
有 \(\d E=L\cos\theta\d\omega\)，\(\d I=L\d A\cos\theta\)。
從某個角度 \(\omega_i\) 的輻亮度會變成 \(\d A\) 接受的能量，然后再散射向其它方向。
其輸入的輻照度是 \(\d E(\omega_i)=L(\omega_i)\cos\theta_i\d\omega_i\)，向某個方向輸出的輻亮度是 \(\d L_r(\omega_r)\)，然后定義 bidirectional reflectance distribution function (BRDF) 是
積分可得能量守恒定律：
而實際輸出量為
光追就是用 Monte Carlo 估算這個積分！
浙公網安備 33010602011771號