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