課程鏈接：GAMES101-現(xiàn)代計算機圖形學入門-閆令琪
課程講師：閆令琪
本系列筆記為本人根據(jù)學習該門課程的筆記，僅分享出來供大家交流，希望大家多多支持GAMES相關講座及課程，如涉及侵權請聯(lián)系我刪除：albertlidesign@gmail.com
幾何的表示方法
幾何分為隱式幾何（Implicit geometry）和顯式幾何（Explicit geometry）。我們有不同的方式來表示不同的幾何。我們從隱式幾何表示開始。
Implicit Geometry
隱式幾何表示方法不會表達明確的點的位置，而是去表達這些點滿足的關系，也就是說，對于一些滿足一定關系的點，我們可以通過隱式幾何來確定它們所在的滿足一定關系的表面上。舉個例子，比如一個單位球，在三維空間中可以表示成，即給出任何一個我們都可以判斷該點是否在定義的表面上，因此它就是球的隱式表示。球的顯式表示方法，最簡單的就是將其拆成若干個三角形或四邊形網(wǎng)格。另外一個例子將這個概念推廣了，我們定義任何一個滿足的關系，那這個關系自然就是一個函數(shù)了，也就是說，只要一個點滿足這個函數(shù)，那么我們就可以說這個點在這個表面上，因此球的例子可以改成。因此我們可以直接定義一個函數(shù)，只要能找到一個點的滿足這個函數(shù)，就認為這個點在表面上，只要能找出所有滿足關系的點，我們就能把這個表面畫出來。如上圖所示，對于函數(shù)，藍色區(qū)域為函數(shù)值為負的區(qū)域，紅色區(qū)域為函數(shù)值為正的區(qū)域，白色輪廓線就是的區(qū)域。
隱式幾何有好處也有壞處，例如，我們?nèi)绾握业搅畹狞c呢？這是一個相對困難的事，也很難看出來，我們將其結(jié)果繪出如上圖所示，它其實是一個圓環(huán)，僅從函數(shù)來看很難看出它是一個圓環(huán)的結(jié)構(gòu)，也就是說隱式幾何的表示不直接。
當然隱式幾何也有好處，它判斷一個點與表面的關系非常容易，只需要將點代入到函數(shù)中，根據(jù)結(jié)果的正負值即可判斷該點在表面內(nèi)、在表面上還是在表面外。例如，我們判斷點與表面的位置關系，將其代如得，因此可知該點在表面內(nèi)。
Explicit Geometry
相對地，圖形學還有顯式幾何表達，比如之前我們用到的三角形，就是真的將表面顯式地表達出來。還有一種顯式的表達方法，聽起來不直觀，稱為通過參數(shù)映射的方法定義的表面。例如我們在平面上定義一個空間，上面任意一個點用表示，并且我們可以定義，對于任何該空間中的點的坐標都可以映射到對應的三維空間中的點，也就是說可以定義一個函數(shù)，輸入的是
，輸出的是空間中的
，如果把所有的
都計算一遍，就可以找到對應空間中的表面，例如下圖所示的馬鞍面。因此顯式表示方法，要么直接給出，要么通過參數(shù)映射的方法來定義表面。
舉個例子，，（因為我們給出了的對應的具體表示方法，因此這是一種顯式表示方法）我們想求出在表面上的點。求出后會發(fā)現(xiàn)這是一個與之前的案例同樣的圓環(huán)?？梢?，隱式的表示方法并不容易想象出表面的實際樣子，但是對于顯式的表示來說很容易。
但是，顯式表達中，檢測點與表面的關系會相應的變難，例如，去判斷點與表面的位置關系就會變得很難。
因此，有些問題適合隱式的表示方法，有些問題適合顯式的表示方法，沒有最好最完美的表示方法，我們要根據(jù)需要去選擇。Best Representation Depends on the Task!
"I hate meshes. I cannot believe how hard this is. Geometry is hard." -- David Baraff (Senior Research Scientist, Pixar Animation Studios)
Implicit Representations in Computer Graphics
隱式的表示方法還有很多，在這里再介紹幾種。
Algebric Surfaces(Implicit)
最簡單最直接的是Algebric Surfaces(Implicit)，即使用數(shù)學公式去表示表面。前面提到，數(shù)學公式表示曲面的嚴重問題就是不直觀，圓環(huán)的表達就已經(jīng)很不直觀了，對于一個復雜形狀，想要表達出來就極其困難。
Constructive Solid Geometry(Implicit)
另外一種表示方法是CSG (Constructive Solid Geometry, Implicit) 表示方法，它是通過基本幾何的基本運算來定義新的幾何，例如一個圓柱和球，做布爾運算，通過幾何之間的求交集、叉積和并集就能得到新的較復雜的幾何，如下圖所示。這種操作得到了非常廣泛的應用，在不同的建模軟件中都支持這種方法，通過這種方法可以把簡單的幾何變成復雜的幾何，僅通過幾何之間的相互關系來得到，最后還可以寫成表達式，因此它仍然是隱式的方法。
Distance Functions(Implicit)
還有一種表示方法叫距離函數(shù) (Distance Functions, Implicit) 表示方法。對于任何一個幾何，我們不去描述它的表面，而是去描述空間中的點到這個表面的最近距離，先看一個例子，如下圖所示，當兩個球逐漸靠近時，兩個球的形狀發(fā)生變化，融合在了一起，最終變成一個球，在這個過程中，形狀和拓撲結(jié)構(gòu)都發(fā)生了變化，這就是通過對幾何的距離函數(shù)做融合所形成的結(jié)果。
重申一下，距離函數(shù)是指，空間中的任何一個點到想要表達的表面的最近距離，這個距離可以是正的也可以是負的，即有向距離（Signed Distance）例如在表面外為正，表面內(nèi)為負，這樣空間中任何一個點都可以定義出一個值，把這兩個不同的物體的距離函數(shù)都算出來以后，就可以把兩個距離函數(shù)做一個融合，再恢復出原來的物體，就可以做出融合的效果。
舉個例子如上圖所示，該例子就是對距離函數(shù)的應用，在圖A和圖B中，是兩張不同的圖，我們認為是表示某種幾何的邊界，假設一個物體，擋住了能看到的視口的，另一個物體（假設是前一個物體經(jīng)過移動后）擋住了視口的，如果我們要求從視口A到視口B的中間狀態(tài)，要想做簡單的線性的融合，得到的圖左邊為A，中間為B，右邊為白色。這就是兩張圖做簡單線性Blend的結(jié)果，它并不能表述運動信息，我們希望得到的是左邊一般是黑的右邊一半是白的，那么怎樣才能得到正確的結(jié)果呢？我們要先對空間中的所有點求圖A的有向距離，即圖A的邊界為0，求點到這個邊界的最短距離，越靠近邊就越接近0，然后再對圖B做相同的計算，這兩張圖的結(jié)果會是漸變的圖，最后我們將這兩張圖做一個Blend的操作，就能離可得到上圖右下方的結(jié)果。如果我們把它恢復成原本對應的形狀，Blend它們的SDF就等于是在Blend它們的邊界。
通過距離函數(shù)，我們可以表達出一些復雜的、圓滑的幾何，如下圖所示。那么距離函數(shù)得到的函數(shù)，我們要如何把它恢復成表面呢？只需要把距離函數(shù)對應為0的位置全找出來即可。但是距離函數(shù)不太容易寫成一種解析的形式，但是只要我們通過某種方法表示出來就可以了。
Level Set Methods(Implicit)
水平集方法(Level Set Methods, Implicit)和距離函數(shù)幾乎完全一樣，僅僅是函數(shù)的表述是寫在格子上的，只需要找到在中間找到值為0的點，就能把這個函數(shù)描述出來，當然也可以找到其他的曲線，例如通過得到另外一條曲線。
這個概念其實在地理上早已得到廣泛的應用，即等高線，它就是為了描述一個函數(shù)在不同的位置有相同的值，在這里對于這樣一個例子來說很簡單。當然水平集也可以定義在三維中的格子，而這就與我們前面說的紋理關聯(lián)上了，如果有一個三維的紋理表述的是人體不同位置的密度，那么我們?nèi)绾螐倪@些三維信息中提取表面呢？我們可以讓這個密度函數(shù)等于某個值，比如，我們可以找出所有的點，就能表示出一個表面，這就是水平集在三維空間中的運用。
再比如水滴滴入水面造成水花的過程，我們該如何去描述它，這里也可以通過水平集的方法將水滴和水滴融合在一塊，并提出融合之后的表面的樣子。
Fractals(Implicit)
幾何還有一種特殊的描述方法，稱為分形（Fractals）。分形就是自相似的意思，即自己的一個部分和整體非常相似，在計算中和遞歸一個道理。例如雪花如果放大看會發(fā)現(xiàn)每一個六邊形邊都會有更小的六邊形，即不斷地自我重復所形成的形狀。下圖中中間的圖是一種西蘭花，仔細觀察會發(fā)現(xiàn)它有很多凸起，如果放大去看會發(fā)現(xiàn)每一個凸起里又有很多更小的凸起，所以它是一個自帶分形的植物，它是自然界中分形的例子。它在渲染中會引起強烈的走樣，因為變化頻率太高了，因此這樣的幾何對渲染來說是一個非常大的挑戰(zhàn)。
Implicit Representations - Pros & Cons
接著總結(jié)一下隱式表達的優(yōu)劣。好處有：描述容易（比如用一個函數(shù)），有利存儲；有利查詢（判斷位置關系）；利于做光線求交（當然對顯式來說也并不難）；對于簡單的物體可以嚴格地描述出來，沒有采樣誤差；容易控制拓撲變化等。壞處就是難以描述復雜形狀的幾何。這也是為什么我們還需要顯式的表達。
Explicit Representations in Computer Graphics
顯式表達也有很多種方法，例如三角形表達、貝塞爾曲面、細分曲面、NURBS、點云等。
Point Cloud (Explicit)
最簡單的顯式幾何表示方法是點云，點云的表示不考慮表面，全部都表示成點，只要點足夠多，自然而然就看不到點與點之間縫隙，圖像上就能看到一個表面。表示一個點很容易，用就夠了，點云就是一個點的列表，例如下圖右側(cè)，雕塑的上半部分點云的密度非常大，因此就能看到物體的表面，隨著點云變得越來越稀疏，就看不到物體的表面。所以如果想用點云來表示一個非常復雜的模型，就需要特別密集的點。當然，理論上它可以表示任何類型的幾何，只要點足夠密即可。通常來說人們會做一些三維空間中的掃描，其輸出就是點云，但這就會涉及到一個問題，給定足夠多的點云，如何把它們變成三角形面，這里就有很多研究了。正常情況下，如果點云密度很低，自然而然就不太容易將其表達成表面，這也是為什么人們用點云去表示的情況不是特別多。
Polygon Mesh (Explicit)
在圖形學中，得到最廣泛應用的就是多邊形面（通常是三角形或者四邊形），它非常易于表示，任何形狀都可以拆成很多很多小的三角形，如下圖所示，類似膠囊的幾何，兩端三角形較密集，較規(guī)則，中間部分較稀疏，較細長。不過顯然，使用三角形表達就自然涉及到一些連接關系，這就相比于點云造成了一些困難，但也有更多的研究。重申一下，多邊形是圖形學中最廣泛運用的圖形表示方法。
這里既然提到了三角形面，就順便提一下我們平常如何表示三角形面形成物體的。如下圖所示，這是一種特定的文件格式，這一種文件可以存儲一個物體或一個場景，這種文件稱為The Wavefront Object File (.obj)，注意這里的文件雖然后綴是.obj但是和編譯時生成的.obj文件不是一回事。它其實是一個文本文件，這個文本文件里，只是把空間中的頂點坐標、法線、紋理坐標分開表示，然后再把它們組織起來。下圖所示示例，這個文件描述了一個立方體，一個立方體總共有8個空間點，它們分別被用'v'表示的三個坐標來表達，也就是左圖中的第3-10行。然后，一個立方體有6個面，所以它只有6種不同的法線，因此文件同樣定義了6種不同的法線，為右圖的第27-34行，這里有8行是因為在自動建模中有冗余的地方，比如29行和30行不考慮數(shù)值精度的時候其實是一回事，其實只定義了6個法線。再然后，它定義了24個紋理坐標（一個面有4個點），為左圖第12-25行，當然這里也有冗余，其實不用定義這么多。最后，這個文件定義了它們之間的連接關系，也就是說哪三個點形成了一個三角形，用'f'(face)表示，每一個數(shù)值的含義是為 v / vt / vn的索引，比如第36行的含義是：使用第5個頂點、第1個頂點和第4個頂點構(gòu)造一個三角形，并且這三個頂點分別用第1個、第2個和第3個紋理坐標，并且都使用第1個法線。這樣一來我們就可以通過這種形式來定義一個網(wǎng)格了。
Curves
下面我們從曲線開始，來講解顯式表示的其他方法。我們從一個例子開始看，如圖為一個動畫，在動畫中攝像機會在空間中沿著某一路徑運動，并且會改變它的朝向，這些曲線我們可以定義好它。不光是相機路徑，模型移動的路徑也可以使用曲線來定義。
除此之外，使用曲線還可以定義一些字體，通過添加控制點的方法來定義曲線，這種曲線如果被無限放大，我們會看到任何地方都是光滑的，不會出現(xiàn)格子的情況，這就是我們接下來要說的貝塞爾曲線，一種顯式的表示方法。
Bezier Curves
貝塞爾曲線的目的是用一系列控制點去定義某一條曲線，這些控制點會定義這條曲線所滿足的一些性質(zhì)，比如說從開始，并且沿著從
到
的方向為切線向前走，同樣道理這個曲線會在
處結(jié)束，并且結(jié)束時，其切線一定是沿著
到
的方向向外的。（圖中會發(fā)現(xiàn)切線的長度也被定義了，即系數(shù)
，這里后面會做解釋）總之，通過這四個點，我們可以定義曲線的起始點和終點一定為
和
，并且起始方向和結(jié)束方向為
和
，這樣就會得到一條唯一的曲線。當然，曲線并不一定經(jīng)過中間的控制點，這取決于我們?nèi)绾味x它，只定義曲線一定經(jīng)過控制點集中的起、止點。
de Casteljau Algorithm
那么我們怎樣才能畫出一條貝塞爾曲線呢？我們可以用任意多個點（當然數(shù)量大于等于2）去畫出一條貝塞爾曲線，這里用到的算法就是de Casteljau Algorithm。如下圖所示為一條由三個點形成的貝塞爾曲線，稱為二次貝塞爾曲線（quadratic Bezier）。
- 畫出這條曲線前，我們知道
決定了這條曲線從哪開始，
決定了它往哪個方向彎曲，
決定了曲線的終點。
- 我們假設這條曲線的起點為時刻
，它的中點為
，那么如果我們想畫出這條曲線，實際上就是求出這條曲線上的點在
中任意一個時刻
所處的位置。de Casteljau Algorithm就是告訴我們該如何找出這個點，它將畫出整個曲線的方法轉(zhuǎn)化成了找一個點的問題。
如上圖所示，三個點形成了兩條線段和
，假設方向也是輸入順序。假設給定了時間
，
，
，那么我們就找出線段
。同樣道理，我們在
，這樣一來我們就找到了三個點所形成的兩條線段上的兩個點。
- 那么如果我們把新得到的兩個點連起來，再去找這條線段
上位于
顯式表示要么是通過直接定義，要么通過參數(shù)來表示，這里的
同樣地，如果給定了4個點，用這4個點來定義一條貝塞爾曲線，這條曲線必經(jīng)過和，那么我們該如何畫出它呢？假設找一個時間，得到了，對于每條線段都能找到點，然后再連起來，原本四個點三條線段，連起來后變成了三個點兩條線段，同樣地，再對這兩個點取的位置，即可得到和，連起來后變成了兩個點一條線段，最后再取的位置，得到，該點就是貝塞爾曲線在時的位置。可見，算法每次遞歸，線段的數(shù)量和點的數(shù)量會減一，不斷遞歸下去，直到最后剩下一個點。
Algebraic Formula
算法已經(jīng)解釋清楚，但只是一個直觀形式的解釋，下面嘗試能否從直觀的解釋推出代數(shù)的形式。貝塞爾曲線是由控制點和時間來決定的，因此它們之間一定有一種代數(shù)表示的方法。如下圖所示，我們在每兩個點之間尋找
的位置，就相當于在這兩個點之間做了線性插值，所以整個過程是不斷地進行線性插值得到的點。
因此我們可以將其顯式地寫出來，例如二次貝塞爾曲線可以寫成：
展開后可以得到：
我們發(fā)現(xiàn)，給定時間，其實是、和的組合，因此任意一個點必須要由控制點的坐標來決定，并且與有關。我們令，則公式變成：
這就發(fā)現(xiàn)了貝塞爾曲線各項前面的系數(shù)其實就是的展開式。例如三點二階的貝塞爾曲線，各控制點的系數(shù)就是的展開式。
總結(jié)歸納，給定個控制點，我們可以得到一個
階的貝塞爾曲線，它在任意時間
都是給定控制點的線性組合，它組合的系數(shù)是一個跟時間有關的多項式，這個多項式叫做Bernstein多項式（其實就是一個描述二項分布的多項式）。
最后簡化一下，任意階數(shù)的貝塞爾曲線的控制點的系數(shù)是由Bernstein多項式給定的，然后貝塞爾曲線是這些控制點與對應控制點系數(shù)的加權。通過這樣一個性質(zhì)，我們完全可以不必限制控制點在平面內(nèi)，在空間中仍然可以得到貝塞爾曲線，只需要把控制點輸入成三維坐標，同樣使用Bernstein多項式來插值即可。
Bernstein多項式其實是對自己的多項式展開，這也是為什么如果我們把多項式中的系數(shù)加起來最后都等于
。
Properties of Bezier Curves
貝塞爾曲線有很多不錯的性質(zhì)：
- 規(guī)定了起點和終點，例如
- 對于三次貝塞爾曲線（Cubic Bezier），它的起始位置的切線一定是
，終點位置的切線為
，如果控制點數(shù)不是
，那么系數(shù)就不是
了。
- 仿射變換下有一個好性質(zhì)，如果要對一條貝塞爾曲線做仿射變換，只需要對它的控制點做仿射變換，再重新繪制出來即可。因此不需要把曲線上每個點的位置都記錄下來。但是對于投影變換就不行了。
- 凸包性質(zhì)，凸包是計算幾何的中的概念，該性質(zhì)是說，貝塞爾曲線上的任何一個點一定在幾個控制點形成的凸包內(nèi)，例如四個點形成了一個四邊形，那么畫出來的曲線一定在這個四邊形內(nèi)。
如下圖所示，凸包的概念為能夠包圍一系列給定頂點的最小的凸多邊形稱為凸包（Convex Hull）。一個直觀的比喻是，假設有一塊板，下圖中的黑點代表釘子，我們可以用橡皮筋拉開把這些釘子全部包住，然后松手，最后橡皮筋會收縮在這些物體形成的外框，這個框就是凸包。
Piecewise Bezier Curves
我們可以使用貝塞爾曲線，但是它也有一定的問題，這也是為什么我們要引入逐段的貝塞爾曲線（Piecewise Bezier Curves）。
我們來看一個例子，當時，也就是給定了
個點，我們就可以畫出一條貝塞爾曲線出來，如下圖所示，這條曲線能畫出來但是并不直觀，它變成了一條很平滑的曲線，沒有控制點輸入時那么劇烈的變化。也就是說，當控制點多的時候，這個曲線不容易控制，就得不到想要的形狀。
因此人們就想到，我們可以不用這么多控制點來定義一條貝塞爾曲線，可以使用多段貝塞爾曲線來定義，這樣每次只用很少的控制點，最后再連起來，這樣就解決了問題。人們更傾向于每個控制點來定義一條貝塞爾曲線，也即是用Pievewise cubic Bezier來定義曲線。如圖所示，它是每個控制點定義的貝塞爾曲線拼接而成的，在發(fā)生劇烈變化的地方就是多段貝塞爾曲線的交點，因為貝塞爾曲線一定經(jīng)過起點和終點。
圖中黑色點就是多段貝塞爾曲線的交點（起點和終點，必須經(jīng)過的點），藍色點是控制點，本來應該是所有控制點都連在一起的，軟件中給隱藏掉了中間兩點之間的連線，這樣對于Pievewise cubic Bezier來說，一條貝塞爾曲線內(nèi)的控制點就可以當成一個控制手柄，這正是Photoshop、Illustrator等軟件的鋼筆工具帶來的畫曲線的能力。那么怎么保證連起來的曲線是光滑的呢？在物理上，曲線光滑不光滑是看切線方向是否光滑，即導數(shù)要連續(xù)，不只是方向還有大小，那么對于第一段曲線來說，終點的方向是由最后兩個點來定義的，對于第二段曲線來說，起點處的方向是由前兩個點來定義的，因此只要第一條曲線的倒數(shù)第二個控制點和第二條曲線的第二個控制點共線并且到終點的距離相等，曲線就能光順地過渡。
Continuity
如果給定兩段貝塞爾曲線，都是由個控制點構(gòu)成，那么在幾何上兩個曲線都通過中間的黑點，圖中展示的是切線上的連續(xù)，另外只要兩條曲線的終點和起點接觸的連續(xù)，就是幾何上的連續(xù)。
用數(shù)學來表示：
- 第一段的終點與第二段的起點相等，稱為
連續(xù)，即
。即幾何上，只要兩曲線接上了，就達到了
- 交點左右的兩個控制點與交點共線并且到交點的距離相等時，稱為
連續(xù)，即
，即切線連續(xù)。
再高階的導數(shù)，例如連續(xù)稱為曲率連續(xù)，高階的導數(shù)就對控制點有著更高的要求。注意，切線連續(xù)看上去似乎已經(jīng)很好了，但是在制造業(yè)上來說，往往有更高的要求，要保證
連續(xù)。
Other types of splines
簡單再介紹一下，一個概念叫做樣條曲線（splines），一條連續(xù)的曲線是由一系列控制點控制的，它能夠滿足一定的連續(xù)性，與階數(shù)無關。下圖為早期人們畫曲線時，會使用一根樹枝然后用一些工具將其固定住。簡單來說，一個可控的曲線就稱為樣條曲線。
B-splines
樣條曲線中，一種被廣泛應用的曲線稱為B樣條曲線（B-splines, basis splines），即基函數(shù)樣條，它是對貝塞爾曲線的一種擴展，它比貝塞爾曲線的能力更強。比如前面當時的貝塞爾曲線，改變一個點時，整個曲線都會發(fā)生變化，而在設計上這樣的性質(zhì)往往不能被接受，比如在曲線中絕大部分點都調(diào)整到了一個精確的位置，只有一處需要做更改，那么如果動了這一個點，整個曲線都要改，設計上就很難操作了，也就是說，設計師需要有一種性質(zhì)叫做局部性，即改變一個點時，這個點所影響的其他點的范圍。分段貝塞爾曲線就具有局部性，B-splines就是一種不需要分段的可以控制局部點的樣條曲線。關于B樣條曲線和NURBS（非均勻有理B樣條）的知識可能是圖形學中最復雜的部分，如果有興趣深入學習的話可以訪問Prof.Shi-Min Hu的課程 https://www.bilibili.com/video/av66548502?from=search&seid=65256805876131485
Surface
曲面會比曲線稍微復雜一些，但是相對更好理解。首先，我們把曲線的概念延伸到一個平面上，比如下圖中的貝塞爾曲面，它是由若干個塊拼起來的，怎樣在拼起來的同時保證連續(xù)性是幾何上比較復雜的問題。
那么我們?nèi)绾螐呢惾麪柷€得到貝塞爾曲面呢？對于下圖所示的曲面，可以理解成由一個平面，施加一個向上的力，拖拽上去得到的結(jié)果，它是由個控制點得到的，圖中的黑點可以理解為拖拽時施加力的作用點。
具體的實現(xiàn)方法就是在兩個方向上分別運用貝塞爾曲線，首先在平面上定義個控制點，它有行列，先從行來看，這四根曲線上的點在不同的時間有不同的位置，如果我們把這四個曲線上的控制點，認為是另外一個方向的貝塞爾曲線的控制點，我們就可以畫出這條貝塞爾曲線，在這根線不斷地掃掠地過程中就可以得到一個曲面。通過這種方式我們可以定義非常復雜的曲面。
在一維對曲線的控制時，我們使用的是時間，在曲面中，有兩個方向的曲線，所以我們使用。
因此，我們也可以通過來找到曲面上的點。貝塞爾曲面是顯式表示就是因為它是通過參數(shù)映射來實現(xiàn)的。
如果需要更多了解Surface，可以訪問Prof.Shi-Min Hu的課程 https://www.bilibili.com/video/av66548502?from=search&seid=65256805876131485
Mesh
一般來說，描述面最普遍的方法還是采用網(wǎng)格。既然我們用三角形來描述模型，那我們就需要了解一些關于網(wǎng)格的操作，例如 Subdivision （用更多的三角形來得到更光滑的模型），Simplification（減少網(wǎng)格面，以節(jié)省存儲量），Regularization（使三角形都接近于正三角形）。
首先我們從最基本的操作Subdivision（細分）開始，即如何增加三角形的數(shù)量，把用三角形表示的曲面更加光滑。如上圖所示，三角形數(shù)量很少的時候看上去就會棱角分明，我們希望能夠變得更加光滑，對于現(xiàn)在的顯卡來說，三角形的數(shù)量已經(jīng)不是很大的問題了，這樣一來，如果有一個模型，我們希望它的細節(jié)能夠更豐富，我們就可以引入更多的三角形，就好像將一個圖形提高它的分辨率以豐富它的細節(jié)。
第二個操作就是Simplification（簡化），如上圖所示，如果有一個網(wǎng)格過于復雜了，它在渲染中位于遠處不需要這么多網(wǎng)格，我們就可以用更少的網(wǎng)格來表示。問題在于我們刪除部分網(wǎng)格面后如何保持一些基本的連接關系，例如牛角的面減少后并不會使這個牛角出現(xiàn)破損或者斷掉，因此需要有一系列方法來指導這一算法。
第三個操作就是Regularization（正則化），三角形有大有小，形狀不一，在渲染的時候會造成各種各樣的不便，通常應對這種情況會對模型進行這一操作，使三角形更接近于正三角形。
Subdivision
我們從細分開始說，之前在說位移貼圖的時候就提到過細分，我們可以在物體表面應用貼圖，這個貼圖表示了頂點的位置移動量，即通過貼圖定義了一個高度場，我們可以將不同的高度應用到不同的頂點上以實現(xiàn)頂點被移動過的模型，但是這要求網(wǎng)格的面數(shù)非常多才能趕上紋理本身要求的頻率。我們當時提到了需要做細分，甚至動態(tài)的細分，那么細分怎么實現(xiàn)呢？首先我們可以看到，細分不止是引入了更多的三角形，它還讓三角形的位置發(fā)生了變化使模型變得更加光滑，因此我們說的細分其實是兩步操作：增加三角形，變光滑。如下圖所示
Loop Subdivision
我們以Loop Subdivision算法為例，這個細分分為兩步操作，第一增多三角形數(shù)量，給定一個三角形，連接三條邊的中點，即可得到中間一個三角形，而該三角形又把原本的三角形分成了三個部分，這樣一步算法就把原本的一個三角形分成了四個三角形。第二步，我們需要調(diào)整三角形的位置，其實是調(diào)整頂點的位置，特別對于Loop細分，我們會把三角形的頂點區(qū)分開，分為新頂點和老頂點，新的頂點就是我們在邊上取的中點，老的頂點就是原本三角形的頂點，Loop細分就是對兩種頂點分別采用不同的規(guī)則來改變它們的位置。
BTW: 圖形學中有很多命名的方法，這里的Loop不是指“循環(huán)”，而是這個算法的創(chuàng)始人的family name。
增加三角形的過程很簡單，那么下面就是如何把老的頂點和新的頂點分別移動來使模型變得更加光滑。
我們先看怎么更新新的頂點的位置，即邊的中點。如下圖所示，我們來看這個白色頂點，首先它肯定在一條邊上，然后只要這條邊表示的不是模型的邊界那么它一定會被兩個三角形共享，我們將兩個三角形共享的邊上的頂點分別稱為，把不共享的兩個頂點稱為，那么Loop細分定義的規(guī)則中，這個白點的位置要變?yōu)椋@其實就是一種簡單的加權平均，即離點近一些的貢獻更大一些，而貢獻相對較小，這樣一個新的頂點的位置是周圍幾個點的位置的平均，這就起到了一個平滑的作用。
對于老的頂點，如下圖所示，對于白色頂點有6個三角形拼在一起，為了更新老的頂點的位置，我們需要將它與它相鄰的老頂點關聯(lián)起來。Loop定義了一個規(guī)則是它采取一部分周圍頂點的位置，接著它還會部分地保留自己的位置。我們定義一下頂點的度，在圖論中，頂點所連接的邊的數(shù)量就稱為頂點的度，也即是說這里白色頂點連接了6條邊，即。此外我們再定義一個權重數(shù)，因此這個白點的位置應該更新至。如果一個頂點連接了很多三角形，那它的會更受它的相鄰頂點的影響，如果它只連接了兩個三角形，那么意味著這個頂點非常重要，自身的權重會更高。
通過這樣的方法，我們就能得到如下圖所示結(jié)果，每一個三角形被拆成了四個小三角形，并且頂點的位置都經(jīng)過了細微調(diào)整，使模型變得光滑。因此Loop細分做了兩個工作：先細分，再光滑。
Catmull-Clark Subdivision (General Mesh)
Catmull-Clark Subdivision是Catmull（2020圖靈獎得主）與Clark共同發(fā)明的算法。我們之所以提及這個算法是因為Loop細分只能對三角形網(wǎng)格進行操作，下圖網(wǎng)格中既有三角形又有四邊形的一般網(wǎng)格情況，就需要使用Catmull-Clark細分。我們先來定義一些概念，我們稱Quad face為四邊形面，而非四邊形面當然就是Non-quad face，例如圖中的兩個三角形面。接著我們定義，頂點的度不為的為奇異點（Extraodinary vertex）。
Catmull-Clark Subdivision是既在每一條邊取中點，也在每一張面上取中點，并且把邊上的中點和面上的中點連起來，這樣左上角的一個四變形變成了四個四邊形，三角形就細分成了三個四邊形。分析一下會發(fā)現(xiàn)，經(jīng)過了一次細分后，非奇異點的頂點仍然是非奇異點，原本的兩個度為的奇異點仍然是奇異點，并且在三角形面上新增的點都變成了新的奇異點，因此細分一個三角形會產(chǎn)生一個度為的新的奇異點，這樣就有了四個奇異點。新的奇異點產(chǎn)生是因為三角形細分出來要和原本的三條邊相連，推廣一下也就是說，只要在非四邊形面內(nèi)新增點做細分，由于該點要和每條邊相連，因此必定產(chǎn)生奇異點，和幾條邊相連，其度就為幾。此外，我們還發(fā)現(xiàn)，經(jīng)過這樣一次細分之后，所有非四邊形面全部都消失了，因為三角形被分成了三個四邊形。因此，這樣的細分會在每一個非四邊形面上引入一個奇異點，并且會將這些非四邊形面轉(zhuǎn)換為四邊形面。那么如果我們再做細分操作，所有的面都已經(jīng)是四邊形面了，也就是說奇異點數(shù)不會再增加了，這也告訴了我們，Catmull-Clark Subdivision會在第一次細分后，增加了非四邊形面的數(shù)量個奇異點，之后不再增加。
例如我們再做一次細分，由于所有面都已經(jīng)是四邊形了，因此奇異點數(shù)量不增加。大家會看到在細分的過程中，點會發(fā)生位置變化，并且變得越來越光滑。
關于頂點更新規(guī)則，它對于面的中心點、邊的中心點及原始頂點會有不同的更新規(guī)則，其具體規(guī)則如圖所示，定義看上去很復雜，實際仍然是圖像的模糊操作沒有什么特別大的區(qū)別，簡單來說就是一個加權平均的規(guī)則。
通過Catmull-Clark Subdivision可以產(chǎn)生各種各樣細分的結(jié)果。Loop細分只能用于三角形面，Catmull-Clark可以用于各種不同的面。注意下圖中四邊形細分結(jié)果不對稱是因為定義了折痕（Crease）。
Simplification
下面開始講解如何進行簡化操作。這一算法的目標是在保持整體形態(tài)不發(fā)生劇烈變化的前提下減少三角形的數(shù)量，以方便其他算法提升性能。例如下圖所示，如果這個骷髏模型距離攝像機鏡頭非常遠，我們看不到很多細節(jié)，就沒有必要使用30,000個三角形去表示它，使用3,000個甚至300個就足以，這可以大幅度減少計算量，因此在不同的情況下會我們要選擇不同復雜程度的幾何模型，以提高程序的效率。這個算法和我們之前提到過的Mipmap有關，層次結(jié)構(gòu)的幾何和層次結(jié)構(gòu)的圖像是相似的，只不過幾何更難去實現(xiàn)，它要求更多的平滑過渡，避免突變。
這里提供某一種方法，叫做邊坍縮（Edge collaping），即將邊變成一個點。
Simplification問題的關鍵在于“要坍縮哪些邊”？下圖中左側(cè)網(wǎng)格，我們把中間三個頂點都替換成一個頂點，但是我們應該把這個頂點放在什么位置才能保證藍色網(wǎng)格和灰色網(wǎng)格基本保證輪廓形狀一致呢？左圖中體現(xiàn)出做放在平均位置的結(jié)果，顯然結(jié)果是不對的，結(jié)果會過于扁平圓滑。接著人們引入了一種誤差的度量，稱為二次誤差度量（Quadric Error Metrics），即將這個點放在某一位置時最小化二次誤差。二次誤差在機器學習中和L2距離非常相似，新的頂點與和它相關聯(lián)的面的各頂點的距離的平方和，我們要讓這個值達到最小，因此這就是一個非常清晰的優(yōu)化過程。
有了這樣的二次度量，我們就可以在坍縮任意一條邊之后，都把坍縮后的頂點移動至一個二次誤差度量最小的位置。這樣，可以假設每一條邊都計算出坍縮后對應的誤差，然后將這些誤差最小的邊開始進行坍縮。但是要注意，如果我們坍縮了一條邊為頂點，那么這條邊所連接的其他邊會相應地變長，如上圖所示，因此坍縮后，坍縮邊周圍的邊會受到影響，其二次度量誤差也會發(fā)生變化。因此，在坍縮完最小的二次度量誤差后，要對其影響到的邊做更新，因此需要某一種數(shù)據(jù)結(jié)構(gòu)，能夠保證取到最小值后可以動態(tài)地以最小的代價來更新受影響的元素，這個數(shù)據(jù)結(jié)構(gòu)就叫做優(yōu)先隊列，或者叫堆。
簡單而言，具體步驟如下：
- 對于每一條邊，打上一個分數(shù)，這個分數(shù)就是它坍縮后的二次度量誤差
- 取最小誤差的邊，做坍縮
-
更新受影響的邊的二次度量誤差
再來反思這一方法，我們其實是在不斷地通過找局部最優(yōu)解的方法來找全局最優(yōu)解，這種方法其實是一個典型的貪心算法。
