課程鏈接：GAMES101-現(xiàn)代計(jì)算機(jī)圖形學(xué)入門-閆令琪
課程講師：閆令琪
本系列筆記為本人根據(jù)學(xué)習(xí)該門課程的筆記巾腕，僅分享出來供大家交流，希望大家多多支持GAMES相關(guān)講座及課程，如涉及侵權(quán)請(qǐng)聯(lián)系我刪除：albertlidesign@gmail.com
幾何的表示方法
幾何分為隱式幾何（Implicit geometry）和顯式幾何（Explicit geometry）。我們有不同的方式來表示不同的幾何窍侧。我們從隱式幾何表示開始。
Implicit Geometry
隱式幾何表示方法不會(huì)表達(dá)明確的點(diǎn)的位置转绷，而是去表達(dá)這些點(diǎn)滿足的關(guān)系伟件，也就是說，對(duì)于一些滿足一定關(guān)系的點(diǎn)议经，我們可以通過隱式幾何來確定它們所在的滿足一定關(guān)系的表面上斧账。舉個(gè)例子谴返，比如一個(gè)單位球，在三維空間中可以表示成咧织，即給出任何一個(gè)我們都可以判斷該點(diǎn)是否在定義的表面上嗓袱，因此它就是球的隱式表示。球的顯式表示方法习绢，最簡(jiǎn)單的就是將其拆成若干個(gè)三角形或四邊形網(wǎng)格渠抹。另外一個(gè)例子將這個(gè)概念推廣了，我們定義任何一個(gè)滿足的關(guān)系闪萄，那這個(gè)關(guān)系自然就是一個(gè)函數(shù)了梧却，也就是說，只要一個(gè)點(diǎn)滿足這個(gè)函數(shù)败去，那么我們就可以說這個(gè)點(diǎn)在這個(gè)表面上放航，因此球的例子可以改成。因此我們可以直接定義一個(gè)函數(shù)圆裕，只要能找到一個(gè)點(diǎn)的滿足這個(gè)函數(shù)广鳍，就認(rèn)為這個(gè)點(diǎn)在表面上，只要能找出所有滿足關(guān)系的點(diǎn)葫辐，我們就能把這個(gè)表面畫出來搜锰。如上圖所示，對(duì)于函數(shù)耿战，藍(lán)色區(qū)域?yàn)楹瘮?shù)值為負(fù)的區(qū)域，紅色區(qū)域?yàn)楹瘮?shù)值為正的區(qū)域焊傅，白色輪廓線就是的區(qū)域剂陡。
隱式幾何有好處也有壞處，例如狐胎，我們?nèi)绾握业搅畹狞c(diǎn)呢鸭栖？這是一個(gè)相對(duì)困難的事，也很難看出來握巢，我們將其結(jié)果繪出如上圖所示晕鹊，它其實(shí)是一個(gè)圓環(huán)，僅從函數(shù)來看很難看出它是一個(gè)圓環(huán)的結(jié)構(gòu)暴浦，也就是說隱式幾何的表示不直接溅话。
當(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á)出來匣吊。還有一種顯式的表達(dá)方法，聽起來不直觀寸潦，稱為通過參數(shù)映射的方法定義的表面色鸳。例如我們?cè)谄矫嫔隙x一個(gè)空間，上面任意一個(gè)點(diǎn)用表示见转，并且我們可以定義命雀，對(duì)于任何該空間中的點(diǎn)的坐標(biāo)都可以映射到對(duì)應(yīng)的三維空間中的點(diǎn)，也就是說可以定義一個(gè)函數(shù)斩箫，輸入的是
吏砂，輸出的是空間中的
，如果把所有的
都計(jì)算一遍乘客，就可以找到對(duì)應(yīng)空間中的表面狐血，例如下圖所示的馬鞍面。因此顯式表示方法易核，要么直接給出匈织，要么通過參數(shù)映射的方法來定義表面。
舉個(gè)例子牡直，缀匕，（因?yàn)槲覀兘o出了的對(duì)應(yīng)的具體表示方法，因此這是一種顯式表示方法）我們想求出在表面上的點(diǎn)碰逸。求出后會(huì)發(fā)現(xiàn)這是一個(gè)與之前的案例同樣的圓環(huán)乡小。可見饵史，隱式的表示方法并不容易想象出表面的實(shí)際樣子满钟，但是對(duì)于顯式的表示來說很容易。
但是胳喷，顯式表達(dá)中湃番，檢測(cè)點(diǎn)與表面的關(guān)系會(huì)相應(yīng)的變難，例如厌蔽，去判斷點(diǎn)與表面的位置關(guān)系就會(huì)變得很難牵辣。
因此，有些問題適合隱式的表示方法奴饮，有些問題適合顯式的表示方法纬向，沒有最好最完美的表示方法择浊，我們要根據(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)重問題就是不直觀，圓環(huán)的表達(dá)就已經(jīng)很不直觀了吃警，對(duì)于一個(gè)復(fù)雜形狀糕篇，想要表達(dá)出來就極其困難。
Constructive Solid Geometry(Implicit)
另外一種表示方法是CSG (Constructive Solid Geometry, Implicit) 表示方法酌心，它是通過基本幾何的基本運(yùn)算來定義新的幾何拌消，例如一個(gè)圓柱和球，做布爾運(yùn)算安券，通過幾何之間的求交集墩崩、叉積和并集就能得到新的較復(fù)雜的幾何，如下圖所示侯勉。這種操作得到了非常廣泛的應(yīng)用鹦筹，在不同的建模軟件中都支持這種方法，通過這種方法可以把簡(jiǎn)單的幾何變成復(fù)雜的幾何址貌，僅通過幾何之間的相互關(guān)系來得到铐拐，最后還可以寫成表達(dá)式，因此它仍然是隱式的方法芳誓。
Distance Functions(Implicit)
還有一種表示方法叫距離函數(shù) (Distance Functions, Implicit) 表示方法余舶。對(duì)于任何一個(gè)幾何，我們不去描述它的表面锹淌，而是去描述空間中的點(diǎn)到這個(gè)表面的最近距離，先看一個(gè)例子赠制，如下圖所示赂摆，當(dāng)兩個(gè)球逐漸靠近時(shí)，兩個(gè)球的形狀發(fā)生變化钟些，融合在了一起烟号，最終變成一個(gè)球，在這個(gè)過程中政恍，形狀和拓?fù)浣Y(jié)構(gòu)都發(fā)生了變化汪拥，這就是通過對(duì)幾何的距離函數(shù)做融合所形成的結(jié)果。
重申一下篙耗，距離函數(shù)是指迫筑，空間中的任何一個(gè)點(diǎn)到想要表達(dá)的表面的最近距離宪赶，這個(gè)距離可以是正的也可以是負(fù)的，即有向距離（Signed Distance）例如在表面外為正脯燃，表面內(nèi)為負(fù)搂妻，這樣空間中任何一個(gè)點(diǎn)都可以定義出一個(gè)值，把這兩個(gè)不同的物體的距離函數(shù)都算出來以后辕棚，就可以把兩個(gè)距離函數(shù)做一個(gè)融合欲主，再恢復(fù)出原來的物體，就可以做出融合的效果逝嚎。
舉個(gè)例子如上圖所示扁瓢，該例子就是對(duì)距離函數(shù)的應(yīng)用，在圖A和圖B中补君，是兩張不同的圖引几，我們認(rèn)為是表示某種幾何的邊界，假設(shè)一個(gè)物體赚哗，擋住了能看到的視口的她紫，另一個(gè)物體（假設(shè)是前一個(gè)物體經(jīng)過移動(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它們的邊界虑润。
通過距離函數(shù)成玫，我們可以表達(dá)出一些復(fù)雜的、圓滑的幾何，如下圖所示哭当。那么距離函數(shù)得到的函數(shù)猪腕，我們要如何把它恢復(fù)成表面呢？只需要把距離函數(shù)對(duì)應(yīng)為0的位置全找出來即可荣病。但是距離函數(shù)不太容易寫成一種解析的形式码撰，但是只要我們通過某種方法表示出來就可以了。
Level Set Methods(Implicit)
水平集方法(Level Set Methods, Implicit)和距離函數(shù)幾乎完全一樣个盆，僅僅是函數(shù)的表述是寫在格子上的脖岛，只需要找到在中間找到值為0的點(diǎn)，就能把這個(gè)函數(shù)描述出來颊亮，當(dāng)然也可以找到其他的曲線柴梆，例如通過得到另外一條曲線。
這個(gè)概念其實(shí)在地理上早已得到廣泛的應(yīng)用终惑，即等高線绍在，它就是為了描述一個(gè)函數(shù)在不同的位置有相同的值，在這里對(duì)于這樣一個(gè)例子來說很簡(jiǎn)單雹有。當(dāng)然水平集也可以定義在三維中的格子偿渡，而這就與我們前面說的紋理關(guān)聯(lián)上了，如果有一個(gè)三維的紋理表述的是人體不同位置的密度霸奕，那么我們?nèi)绾螐倪@些三維信息中提取表面呢溜宽？我們可以讓這個(gè)密度函數(shù)等于某個(gè)值，比如质帅，我們可以找出所有的點(diǎn)适揉，就能表示出一個(gè)表面，這就是水平集在三維空間中的運(yùn)用煤惩。
再比如水滴滴入水面造成水花的過程嫉嘀，我們?cè)撊绾稳ッ枋鏊@里也可以通過水平集的方法將水滴和水滴融合在一塊魄揉，并提出融合之后的表面的樣子剪侮。
Fractals(Implicit)
幾何還有一種特殊的描述方法，稱為分形（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ì)渲染來說是一個(gè)非常大的挑戰(zhàn)毡泻。
Implicit Representations - Pros & Cons
接著總結(jié)一下隱式表達(dá)的優(yōu)劣。好處有：描述容易（比如用一個(gè)函數(shù)）粘优，有利存儲(chǔ)仇味；有利查詢（判斷位置關(guān)系）；利于做光線求交（當(dāng)然對(duì)顯式來說也并不難）雹顺；對(duì)于簡(jiǎn)單的物體可以嚴(yán)格地描述出來丹墨，沒有采樣誤差；容易控制拓?fù)渥兓孺依ⅰ奶幘褪请y以描述復(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)云變得越來越稀疏犬性，就看不到物體的表面瞻离。所以如果想用點(diǎn)云來表示一個(gè)非常復(fù)雜的模型，就需要特別密集的點(diǎn)乒裆。當(dāng)然套利，理論上它可以表示任何類型的幾何，只要點(diǎn)足夠密即可。通常來說人們會(huì)做一些三維空間中的掃描肉迫，其輸出就是點(diǎn)云验辞，但這就會(huì)涉及到一個(gè)問題，給定足夠多的點(diǎn)云喊衫，如何把它們變成三角形面跌造，這里就有很多研究了。正常情況下族购，如果點(diǎn)云密度很低壳贪，自然而然就不太容易將其表達(dá)成表面，這也是為什么人們用點(diǎn)云去表示的情況不是特別多联四。
Polygon Mesh (Explicit)
在圖形學(xué)中撑碴，得到最廣泛應(yīng)用的就是多邊形面（通常是三角形或者四邊形），它非常易于表示朝墩，任何形狀都可以拆成很多很多小的三角形醉拓，如下圖所示，類似膠囊的幾何收苏，兩端三角形較密集亿卤，較規(guī)則，中間部分較稀疏鹿霸，較細(xì)長(zhǎng)排吴。不過顯然，使用三角形表達(dá)就自然涉及到一些連接關(guān)系懦鼠，這就相比于點(diǎn)云造成了一些困難钻哩，但也有更多的研究。重申一下肛冶，多邊形是圖形學(xué)中最廣泛運(yùn)用的圖形表示方法街氢。
這里既然提到了三角形面，就順便提一下我們平常如何表示三角形面形成物體的睦袖。如下圖所示珊肃，這是一種特定的文件格式，這一種文件可以存儲(chǔ)一個(gè)物體或一個(gè)場(chǎng)景馅笙，這種文件稱為The Wavefront Object File (.obj)伦乔，注意這里的文件雖然后綴是.obj但是和編譯時(shí)生成的.obj文件不是一回事醇坝。它其實(shí)是一個(gè)文本文件凭疮，這個(gè)文本文件里，只是把空間中的頂點(diǎn)坐標(biāo)铡俐、法線皿淋、紋理坐標(biāo)分開表示斥杜，然后再把它們組織起來虱颗。下圖所示示例，這個(gè)文件描述了一個(gè)立方體蔗喂，一個(gè)立方體總共有8個(gè)空間點(diǎn)，它們分別被用'v'表示的三個(gè)坐標(biāo)來表達(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)系泛鸟，也就是說哪三個(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è)法線缎脾。這樣一來我們就可以通過這種形式來定義一個(gè)網(wǎng)格了祝闻。
Curves
下面我們從曲線開始，來講解顯式表示的其他方法遗菠。我們從一個(gè)例子開始看联喘，如圖為一個(gè)動(dòng)畫，在動(dòng)畫中攝像機(jī)會(huì)在空間中沿著某一路徑運(yùn)動(dòng)辙纬，并且會(huì)改變它的朝向豁遭，這些曲線我們可以定義好它。不光是相機(jī)路徑贺拣，模型移動(dòng)的路徑也可以使用曲線來定義蓖谢。
除此之外捂蕴，使用曲線還可以定義一些字體，通過添加控制點(diǎn)的方法來定義曲線闪幽，這種曲線如果被無限放大啥辨，我們會(huì)看到任何地方都是光滑的，不會(huì)出現(xiàn)格子的情況盯腌，這就是我們接下來要說的貝塞爾曲線溉知，一種顯式的表示方法。
Bezier Curves
貝塞爾曲線的目的是用一系列控制點(diǎn)去定義某一條曲線腕够，這些控制點(diǎn)會(huì)定義這條曲線所滿足的一些性質(zhì)级乍，比如說從開始，并且沿著從
到
的方向?yàn)榍芯€向前走帚湘，同樣道理這個(gè)曲線會(huì)在
處結(jié)束玫荣，并且結(jié)束時(shí)，其切線一定是沿著
到
的方向向外的大诸。（圖中會(huì)發(fā)現(xiàn)切線的長(zhǎng)度也被定義了捅厂，即系數(shù)
，這里后面會(huì)做解釋）總之底挫，通過這四個(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)過中間的控制點(diǎn)官边，這取決于我們?nèi)绾味x它沸手，只定義曲線一定經(jīng)過控制點(diǎn)集中的起、止點(diǎn)注簿。
de Casteljau Algorithm
那么我們?cè)鯓硬拍墚嫵鲆粭l貝塞爾曲線呢契吉？我們可以用任意多個(gè)點(diǎn)（當(dāng)然數(shù)量大于等于2）去畫出一條貝塞爾曲線，這里用到的算法就是de Casteljau Algorithm诡渴。如下圖所示為一條由三個(gè)點(diǎn)形成的貝塞爾曲線捐晶，稱為二次貝塞爾曲線（quadratic Bezier）。
- 畫出這條曲線前妄辩，我們知道
決定了這條曲線從哪開始惑灵，
決定了它往哪個(gè)方向彎曲，
決定了曲線的終點(diǎn)眼耀。
- 我們假設(shè)這條曲線的起點(diǎn)為時(shí)刻
英支，它的中點(diǎn)為
，那么如果我們想畫出這條曲線哮伟，實(shí)際上就是求出這條曲線上的點(diǎn)在
中任意一個(gè)時(shí)刻
所處的位置干花。de Casteljau Algorithm就是告訴我們?cè)撊绾握页鲞@個(gè)點(diǎn)妄帘，它將畫出整個(gè)曲線的方法轉(zhuǎn)化成了找一個(gè)點(diǎ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">上也能找出位于
萎河，這樣一來我們就找到了三個(gè)點(diǎn)所形成的兩條線段上的兩個(gè)點(diǎn)荔泳。
- 那么如果我們把新得到的兩個(gè)點(diǎn)連起來，再去找這條線段
上位于
顯式表示要么是通過直接定義达舒，要么通過參數(shù)來表示值朋，這里的
同樣地，如果給定了4個(gè)點(diǎn)禽捆，用這4個(gè)點(diǎn)來定義一條貝塞爾曲線笙什，這條曲線必經(jīng)過和，那么我們?cè)撊绾萎嫵鏊啬览蓿考僭O(shè)找一個(gè)時(shí)間得湘，得到了，對(duì)于每條線段都能找到點(diǎn)顿仇，然后再連起來淘正，原本四個(gè)點(diǎn)三條線段摆马，連起來后變成了三個(gè)點(diǎn)兩條線段，同樣地鸿吆，再對(duì)這兩個(gè)點(diǎn)取的位置囤采，即可得到和，連起來后變成了兩個(gè)點(diǎn)一條線段惩淳，最后再取的位置蕉毯，得到，該點(diǎn)就是貝塞爾曲線在時(shí)的位置思犁〈海可見，算法每次遞歸激蹲，線段的數(shù)量和點(diǎn)的數(shù)量會(huì)減一棉磨，不斷遞歸下去，直到最后剩下一個(gè)點(diǎn)学辱。
Algebraic Formula
算法已經(jīng)解釋清楚乘瓤，但只是一個(gè)直觀形式的解釋，下面嘗試能否從直觀的解釋推出代數(shù)的形式策泣。貝塞爾曲線是由控制點(diǎn)和時(shí)間來決定的衙傀，因此它們之間一定有一種代數(shù)表示的方法。如下圖所示萨咕，我們?cè)诿績(jī)蓚€(gè)點(diǎn)之間尋找
的位置统抬，就相當(dāng)于在這兩個(gè)點(diǎn)之間做了線性插值，所以整個(gè)過程是不斷地進(jìn)行線性插值得到的點(diǎn)任洞。
因此我們可以將其顯式地寫出來蓄喇，例如二次貝塞爾曲線可以寫成：
展開后可以得到：
我們發(fā)現(xiàn)，給定時(shí)間交掏，其實(shí)是妆偏、和的組合，因此任意一個(gè)點(diǎn)必須要由控制點(diǎn)的坐標(biāo)來決定盅弛，并且與有關(guān)钱骂。我們令，則公式變成：
這就發(fā)現(xiàn)了貝塞爾曲線各項(xiàng)前面的系數(shù)其實(shí)就是的展開式挪鹏。例如三點(diǎn)二階的貝塞爾曲線见秽，各控制點(diǎn)的系數(shù)就是的展開式。
總結(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)蔗包。通過這樣一個(gè)性質(zhì)，我們完全可以不必限制控制點(diǎn)在平面內(nèi)慧邮，在空間中仍然可以得到貝塞爾曲線调限，只需要把控制點(diǎn)輸入成三維坐標(biāo)，同樣使用Bernstein多項(xiàng)式來插值即可误澳。
Bernstein多項(xiàng)式其實(shí)是對(duì)自己的多項(xiàng)式展開耻矮，這也是為什么如果我們把多項(xiàng)式中的系數(shù)加起來最后都等于
。
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)做仿射變換妙色，再重新繪制出來即可桅滋。因此不需要把曲線上每個(gè)點(diǎn)的位置都記錄下來。但是對(duì)于投影變換就不行了身辨。
- 凸包性質(zhì)丐谋，凸包是計(jì)算幾何的中的概念，該性質(zhì)是說煌珊，貝塞爾曲線上的任何一個(gè)點(diǎn)一定在幾個(gè)控制點(diǎn)形成的凸包內(nèi)号俐，例如四個(gè)點(diǎn)形成了一個(gè)四邊形，那么畫出來的曲線一定在這個(gè)四邊形內(nèi)定庵。
如下圖所示吏饿，凸包的概念為能夠包圍一系列給定頂點(diǎn)的最小的凸多邊形稱為凸包（Convex Hull）。一個(gè)直觀的比喻是蔬浙，假設(shè)有一塊板猪落，下圖中的黑點(diǎn)代表釘子，我們可以用橡皮筋拉開把這些釘子全部包住畴博，然后松手笨忌，最后橡皮筋會(huì)收縮在這些物體形成的外框，這個(gè)框就是凸包俱病。
Piecewise Bezier Curves
我們可以使用貝塞爾曲線官疲，但是它也有一定的問題袱结，這也是為什么我們要引入逐段的貝塞爾曲線（Piecewise Bezier Curves）。
我們來看一個(gè)例子袁余，當(dāng)時(shí)擎勘，也就是給定了
個(gè)點(diǎn)，我們就可以畫出一條貝塞爾曲線出來颖榜，如下圖所示棚饵，這條曲線能畫出來但是并不直觀，它變成了一條很平滑的曲線掩完，沒有控制點(diǎn)輸入時(shí)那么劇烈的變化噪漾。也就是說，當(dāng)控制點(diǎn)多的時(shí)候且蓬，這個(gè)曲線不容易控制欣硼，就得不到想要的形狀。
因此人們就想到恶阴，我們可以不用這么多控制點(diǎn)來定義一條貝塞爾曲線诈胜，可以使用多段貝塞爾曲線來定義，這樣每次只用很少的控制點(diǎn)冯事，最后再連起來焦匈，這樣就解決了問題。人們更傾向于每個(gè)控制點(diǎn)來定義一條貝塞爾曲線昵仅，也即是用Pievewise cubic Bezier來定義曲線缓熟。如圖所示，它是每個(gè)控制點(diǎn)定義的貝塞爾曲線拼接而成的摔笤，在發(fā)生劇烈變化的地方就是多段貝塞爾曲線的交點(diǎn)够滑，因?yàn)樨惾麪柷€一定經(jīng)過起點(diǎn)和終點(diǎn)。
圖中黑色點(diǎn)就是多段貝塞爾曲線的交點(diǎn)（起點(diǎn)和終點(diǎn)吕世，必須經(jīng)過的點(diǎn)）彰触，藍(lán)色點(diǎn)是控制點(diǎn)，本來應(yīng)該是所有控制點(diǎn)都連在一起的寞冯，軟件中給隱藏掉了中間兩點(diǎn)之間的連線渴析，這樣對(duì)于Pievewise cubic Bezier來說，一條貝塞爾曲線內(nèi)的控制點(diǎn)就可以當(dāng)成一個(gè)控制手柄吮龄，這正是Photoshop俭茧、Illustrator等軟件的鋼筆工具帶來的畫曲線的能力。那么怎么保證連起來的曲線是光滑的呢漓帚？在物理上母债，曲線光滑不光滑是看切線方向是否光滑，即導(dǎo)數(shù)要連續(xù)，不只是方向還有大小毡们，那么對(duì)于第一段曲線來說迅皇，終點(diǎn)的方向是由最后兩個(gè)點(diǎn)來定義的，對(duì)于第二段曲線來說衙熔，起點(diǎn)處的方向是由前兩個(gè)點(diǎn)來定義的登颓，因此只要第一條曲線的倒數(shù)第二個(gè)控制點(diǎn)和第二條曲線的第二個(gè)控制點(diǎn)共線并且到終點(diǎn)的距離相等，曲線就能光順地過渡红氯。
Continuity
如果給定兩段貝塞爾曲線框咙，都是由個(gè)控制點(diǎn)構(gòu)成，那么在幾何上兩個(gè)曲線都通過中間的黑點(diǎn)痢甘，圖中展示的是切線上的連續(xù)喇嘱，另外只要兩條曲線的終點(diǎn)和起點(diǎn)接觸的連續(xù)，就是幾何上的連續(xù)塞栅。
用數(shù)學(xué)來表示：
- 第一段的終點(diǎn)與第二段的起點(diǎn)相等者铜，稱為
連續(xù)，即
放椰。即幾何上作烟，只要兩曲線接上了，就達(dá)到了
- 交點(diǎn)左右的兩個(gè)控制點(diǎn)與交點(diǎn)共線并且到交點(diǎn)的距離相等時(shí)，稱為
連續(xù)藻烤，即
，即切線連續(xù)头滔。
再高階的導(dǎo)數(shù)怖亭，例如連續(xù)稱為曲率連續(xù)，高階的導(dǎo)數(shù)就對(duì)控制點(diǎn)有著更高的要求坤检。注意兴猩，切線連續(xù)看上去似乎已經(jīng)很好了，但是在制造業(yè)上來說早歇，往往有更高的要求倾芝，要保證
連續(xù)。
Other types of splines
簡(jiǎn)單再介紹一下箭跳，一個(gè)概念叫做樣條曲線（splines）晨另，一條連續(xù)的曲線是由一系列控制點(diǎn)控制的，它能夠滿足一定的連續(xù)性谱姓，與階數(shù)無關(guān)借尿。下圖為早期人們畫曲線時(shí)，會(huì)使用一根樹枝然后用一些工具將其固定住。簡(jiǎn)單來說路翻，一個(gè)可控的曲線就稱為樣條曲線狈癞。
B-splines
樣條曲線中，一種被廣泛應(yī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ì)上就很難操作了涨岁，也就是說拐袜，設(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í)的話可以訪問Prof.Shi-Min Hu的課程 https://www.bilibili.com/video/av66548502?from=search&seid=65256805876131485
Surface
曲面會(huì)比曲線稍微復(fù)雜一些，但是相對(duì)更好理解琐馆。首先规阀，我們把曲線的概念延伸到一個(gè)平面上，比如下圖中的貝塞爾曲面瘦麸，它是由若干個(gè)塊拼起來的谁撼，怎樣在拼起來的同時(shí)保證連續(xù)性是幾何上比較復(fù)雜的問題。
那么我們?nèi)绾螐呢惾麪柷€得到貝塞爾曲面呢滋饲？對(duì)于下圖所示的曲面厉碟，可以理解成由一個(gè)平面，施加一個(gè)向上的力屠缭，拖拽上去得到的結(jié)果箍鼓，它是由個(gè)控制點(diǎn)得到的，圖中的黑點(diǎn)可以理解為拖拽時(shí)施加力的作用點(diǎn)呵曹。
具體的實(shí)現(xiàn)方法就是在兩個(gè)方向上分別運(yùn)用貝塞爾曲線袄秩，首先在平面上定義個(gè)控制點(diǎn)，它有行列，先從行來看之剧，這四根曲線上的點(diǎn)在不同的時(shí)間有不同的位置郭卫，如果我們把這四個(gè)曲線上的控制點(diǎn)，認(rèn)為是另外一個(gè)方向的貝塞爾曲線的控制點(diǎn)背稼，我們就可以畫出這條貝塞爾曲線贰军，在這根線不斷地掃掠地過程中就可以得到一個(gè)曲面。通過這種方式我們可以定義非常復(fù)雜的曲面蟹肘。
在一維對(duì)曲線的控制時(shí)词疼，我們使用的是時(shí)間，在曲面中帘腹，有兩個(gè)方向的曲線贰盗，所以我們使用。
因此阳欲，我們也可以通過來找到曲面上的點(diǎn)舵盈。貝塞爾曲面是顯式表示就是因?yàn)樗峭ㄟ^參數(shù)映射來實(shí)現(xiàn)的。
如果需要更多了解Surface球化，可以訪問Prof.Shi-Min Hu的課程 https://www.bilibili.com/video/av66548502?from=search&seid=65256805876131485
Mesh
一般來說秽晚，描述面最普遍的方法還是采用網(wǎng)格。既然我們用三角形來描述模型筒愚，那我們就需要了解一些關(guān)于網(wǎng)格的操作赴蝇，例如 Subdivision （用更多的三角形來得到更光滑的模型），Simplification（減少網(wǎng)格面巢掺，以節(jié)省存儲(chǔ)量）句伶，Regularization（使三角形都接近于正三角形）。
首先我們從最基本的操作Subdivision（細(xì)分）開始陆淀，即如何增加三角形的數(shù)量熄阻，把用三角形表示的曲面更加光滑。如上圖所示倔约，三角形數(shù)量很少的時(shí)候看上去就會(huì)棱角分明，我們希望能夠變得更加光滑坝初，對(duì)于現(xiàn)在的顯卡來說浸剩，三角形的數(shù)量已經(jīng)不是很大的問題了，這樣一來鳄袍，如果有一個(gè)模型绢要，我們希望它的細(xì)節(jié)能夠更豐富，我們就可以引入更多的三角形拗小，就好像將一個(gè)圖形提高它的分辨率以豐富它的細(xì)節(jié)重罪。
第二個(gè)操作就是Simplification（簡(jiǎn)化），如上圖所示，如果有一個(gè)網(wǎng)格過于復(fù)雜了剿配，它在渲染中位于遠(yuǎn)處不需要這么多網(wǎng)格搅幅，我們就可以用更少的網(wǎng)格來表示。問題在于我們刪除部分網(wǎng)格面后如何保持一些基本的連接關(guān)系呼胚，例如牛角的面減少后并不會(huì)使這個(gè)牛角出現(xiàn)破損或者斷掉茄唐，因此需要有一系列方法來指導(dǎo)這一算法。
第三個(gè)操作就是Regularization（正則化）蝇更，三角形有大有小沪编，形狀不一雏搂，在渲染的時(shí)候會(huì)造成各種各樣的不便椎工，通常應(yīng)對(duì)這種情況會(huì)對(duì)模型進(jìn)行這一操作蚤认，使三角形更接近于正三角形蝌数。
Subdivision
我們從細(xì)分開始說救氯，之前在說位移貼圖的時(shí)候就提到過細(xì)分秧倾，我們可以在物體表面應(yīng)用貼圖咨油，這個(gè)貼圖表示了頂點(diǎn)的位置移動(dòng)量进栽，即通過貼圖定義了一個(gè)高度場(chǎng)克胳，我們可以將不同的高度應(yīng)用到不同的頂點(diǎn)上以實(shí)現(xiàn)頂點(diǎn)被移動(dòng)過的模型平绩，但是這要求網(wǎng)格的面數(shù)非常多才能趕上紋理本身要求的頻率。我們當(dāng)時(shí)提到了需要做細(xì)分漠另，甚至動(dòng)態(tài)的細(xì)分捏雌，那么細(xì)分怎么實(shí)現(xiàn)呢？首先我們可以看到笆搓，細(xì)分不止是引入了更多的三角形性湿，它還讓三角形的位置發(fā)生了變化使模型變得更加光滑，因此我們說的細(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ū)分開溜嗜，分為新頂點(diǎn)和老頂點(diǎn)，新的頂點(diǎn)就是我們?cè)谶吷先〉闹悬c(diǎn)架谎，老的頂點(diǎn)就是原本三角形的頂點(diǎn)炸宵，Loop細(xì)分就是對(duì)兩種頂點(diǎn)分別采用不同的規(guī)則來改變它們的位置。
BTW: 圖形學(xué)中有很多命名的方法狐树，這里的Loop不是指“循環(huán)”焙压，而是這個(gè)算法的創(chuàng)始人的family name。
增加三角形的過程很簡(jiǎn)單抑钟，那么下面就是如何把老的頂點(diǎn)和新的頂點(diǎn)分別移動(dòng)來使模型變得更加光滑涯曲。
我們先看怎么更新新的頂點(diǎn)的位置，即邊的中點(diǎn)在塔。如下圖所示幻件，我們來看這個(gè)白色頂點(diǎn)，首先它肯定在一條邊上蛔溃，然后只要這條邊表示的不是模型的邊界那么它一定會(huì)被兩個(gè)三角形共享绰沥，我們將兩個(gè)三角形共享的邊上的頂點(diǎn)分別稱為，把不共享的兩個(gè)頂點(diǎn)稱為贺待，那么Loop細(xì)分定義的規(guī)則中徽曲，這個(gè)白點(diǎn)的位置要變?yōu)椋@其實(shí)就是一種簡(jiǎn)單的加權(quán)平均麸塞，即離點(diǎn)近一些的貢獻(xiàn)更大一些秃臣，而貢獻(xiàn)相對(duì)較小，這樣一個(gè)新的頂點(diǎn)的位置是周圍幾個(gè)點(diǎn)的位置的平均哪工，這就起到了一個(gè)平滑的作用奥此。
對(duì)于老的頂點(diǎn)，如下圖所示雁比，對(duì)于白色頂點(diǎn)有6個(gè)三角形拼在一起稚虎，為了更新老的頂點(diǎn)的位置，我們需要將它與它相鄰的老頂點(diǎn)關(guān)聯(lián)起來偎捎。Loop定義了一個(gè)規(guī)則是它采取一部分周圍頂點(diǎn)的位置蠢终，接著它還會(huì)部分地保留自己的位置。我們定義一下頂點(diǎn)的度茴她，在圖論中寻拂，頂點(diǎn)所連接的邊的數(shù)量就稱為頂點(diǎn)的度，也即是說這里白色頂點(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ì)更高。
通過這樣的方法晶姊，我們就能得到如下圖所示結(jié)果扒接，每一個(gè)三角形被拆成了四個(gè)小三角形，并且頂點(diǎn)的位置都經(jīng)過了細(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ì)分矾利。我們先來定義一些概念，我們稱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)連起來让网，這樣左上角的一個(gè)四變形變成了四個(gè)四邊形，三角形就細(xì)分成了三個(gè)四邊形师痕。分析一下會(huì)發(fā)現(xiàn)溃睹，經(jīng)過了一次細(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ì)分出來要和原本的三條邊相連，推廣一下也就是說吹缔，只要在非四邊形面內(nèi)新增點(diǎn)做細(xì)分商佑，由于該點(diǎn)要和每條邊相連，因此必定產(chǎn)生奇異點(diǎn)厢塘，和幾條邊相連茶没，其度就為幾肌幽。此外，我們還發(fā)現(xiàn)抓半，經(jīng)過這樣一次細(xì)分之后喂急，所有非四邊形面全部都消失了，因?yàn)槿切伪环殖闪巳齻€(gè)四邊形笛求。因此廊移，這樣的細(xì)分會(huì)在每一個(gè)非四邊形面上引入一個(gè)奇異點(diǎn)，并且會(huì)將這些非四邊形面轉(zhuǎn)換為四邊形面探入。那么如果我們?cè)僮黾?xì)分操作狡孔，所有的面都已經(jīng)是四邊形面了，也就是說奇異點(diǎn)數(shù)不會(huì)再增加了新症，這也告訴了我們步氏，Catmull-Clark Subdivision會(huì)在第一次細(xì)分后，增加了非四邊形面的數(shù)量個(gè)奇異點(diǎn)徒爹，之后不再增加荚醒。
例如我們?cè)僮鲆淮渭?xì)分，由于所有面都已經(jīng)是四邊形了隆嗅，因此奇異點(diǎn)數(shù)量不增加界阁。大家會(huì)看到在細(xì)分的過程中，點(diǎn)會(huì)發(fā)生位置變化胖喳，并且變得越來越光滑泡躯。
關(guān)于頂點(diǎn)更新規(guī)則，它對(duì)于面的中心點(diǎn)丽焊、邊的中心點(diǎn)及原始頂點(diǎn)會(huì)有不同的更新規(guī)則较剃，其具體規(guī)則如圖所示，定義看上去很復(fù)雜技健，實(shí)際仍然是圖像的模糊操作沒有什么特別大的區(qū)別写穴，簡(jiǎn)單來說就是一個(gè)加權(quán)平均的規(guī)則。
通過Catmull-Clark Subdivision可以產(chǎn)生各種各樣細(xì)分的結(jié)果雌贱。Loop細(xì)分只能用于三角形面啊送，Catmull-Clark可以用于各種不同的面。注意下圖中四邊形細(xì)分結(jié)果不對(duì)稱是因?yàn)槎x了折痕（Crease）欣孤。
Simplification
下面開始講解如何進(jìn)行簡(jiǎn)化操作馋没。這一算法的目標(biāo)是在保持整體形態(tài)不發(fā)生劇烈變化的前提下減少三角形的數(shù)量，以方便其他算法提升性能降传。例如下圖所示篷朵，如果這個(gè)骷髏模型距離攝像機(jī)鏡頭非常遠(yuǎn)，我們看不到很多細(xì)節(jié)婆排，就沒有必要使用30,000個(gè)三角形去表示它声旺，使用3,000個(gè)甚至300個(gè)就足以控硼，這可以大幅度減少計(jì)算量，因此在不同的情況下會(huì)我們要選擇不同復(fù)雜程度的幾何模型艾少，以提高程序的效率。這個(gè)算法和我們之前提到過的Mipmap有關(guān)翼悴，層次結(jié)構(gòu)的幾何和層次結(jié)構(gòu)的圖像是相似的缚够，只不過幾何更難去實(shí)現(xiàn)，它要求更多的平滑過渡鹦赎，避免突變谍椅。
這里提供某一種方法，叫做邊坍縮（Edge collaping）古话，即將邊變成一個(gè)點(diǎn)雏吭。
Simplification問題的關(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ì)過于扁平圓滑。接著人們引入了一種誤差的度量傻谁，稱為二次誤差度量（Quadric Error Metrics）孝治，即將這個(gè)點(diǎn)放在某一位置時(shí)最小化二次誤差。二次誤差在機(jī)器學(xué)習(xí)中和L2距離非常相似审磁，新的頂點(diǎn)與和它相關(guān)聯(lián)的面的各頂點(diǎn)的距離的平方和谈飒，我們要讓這個(gè)值達(dá)到最小，因此這就是一個(gè)非常清晰的優(yōu)化過程态蒂。
有了這樣的二次度量杭措，我們就可以在坍縮任意一條邊之后，都把坍縮后的頂點(diǎn)移動(dòng)至一個(gè)二次誤差度量最小的位置吃媒。這樣瓤介，可以假設(shè)每一條邊都計(jì)算出坍縮后對(duì)應(yīng)的誤差，然后將這些誤差最小的邊開始進(jìn)行坍縮赘那。但是要注意刑桑，如果我們坍縮了一條邊為頂點(diǎn)，那么這條邊所連接的其他邊會(huì)相應(yīng)地變長(zhǎng)募舟，如上圖所示祠斧，因此坍縮后，坍縮邊周圍的邊會(huì)受到影響拱礁，其二次度量誤差也會(huì)發(fā)生變化琢锋。因此辕漂，在坍縮完最小的二次度量誤差后，要對(duì)其影響到的邊做更新吴超，因此需要某一種數(shù)據(jù)結(jié)構(gòu)钉嘹，能夠保證取到最小值后可以動(dòng)態(tài)地以最小的代價(jià)來更新受影響的元素，這個(gè)數(shù)據(jù)結(jié)構(gòu)就叫做優(yōu)先隊(duì)列鲸阻，或者叫堆跋涣。
簡(jiǎn)單而言，具體步驟如下：
- 對(duì)于每一條邊鸟悴，打上一個(gè)分?jǐn)?shù)陈辱，這個(gè)分?jǐn)?shù)就是它坍縮后的二次度量誤差
- 取最小誤差的邊，做坍縮
-
更新受影響的邊的二次度量誤差
再來反思這一方法细诸，我們其實(shí)是在不斷地通過找局部最優(yōu)解的方法來找全局最優(yōu)解沛贪，這種方法其實(shí)是一個(gè)典型的貪心算法。
