將上一講的曲面內(nèi)容移到這一講

曲面

貝塞爾曲面

u方向上畫出四條貝塞爾曲線后，在這四個線上再取四個點，并認為這是個點是一組新的貝塞爾曲線的控制點，這些

點在空間內(nèi)向v方向掃描，便形成了貝塞爾曲面

動畫請見lecture11　55:14-56:07

求貝塞爾平面

幾何處理

曲面細分

Loop細分（渦輪平滑）

連接各邊中點，并重新改變各個頂點位置，從而創(chuàng)造出更多三角形面，使得表面更加光滑（命名并不是因為算法與循環(huán)有關(guān)，而是該算法創(chuàng)始人的名字叫l(wèi)oop）

該算法規(guī)定，一般情況下（不考慮邊緣情況）分為兩類頂點進行考慮--新頂點與舊頂點

舊頂點，需要由原頂點和周圍頂點位置共同確定

其中n為該頂點的度（依附于某個頂點的邊的條數(shù)--數(shù)據(jù)結(jié)構(gòu)），u為一個和n有關(guān)的數(shù)

Catmull-Clark 細分

loop細分有一個前提，即只適用于三角形網(wǎng)格，而對于非三角形網(wǎng)格的細分，就需要借助catmull-clark算法

該算法定義面分為兩種——四邊面和非四邊面，并定義度為4的頂點為非奇異點，其余點均為奇異點

Non-quad?face非四邊形面

具體做法是，對每個非四邊面都取其中的一個點（重心或者其他點），將其與該面的其他頂點分別連接，在這個過程中，會引入一個新的奇異點，并且在一次細分后，所有非四邊面都變?yōu)榱怂倪吤?，在后續(xù)的細分中，將不會引入新的奇異點（但也不會減少-見下圖）

對于細分后頂點位置的調(diào)整，先將頂點分為三大類

①新的在面上的點；②新的在邊上的點；③舊的點

如下計算：

loop細分與catmull-clark細分不同的處理效果：

可參考https://blog.csdn.net/McQueen_LT/article/details/106102609

網(wǎng)格簡化

邊坍縮

如何保證坍縮前后輪廓基本保持一致？ ——二次誤差（機器學(xué)習(xí)中的L2距離相似）

二次誤差度量：坍縮后的點和原本幾個邊（面）的距離的平方和最小

對每一條邊都先計算一下二次誤差，隨后從二次誤差最小的開始坍縮，由小到大

但這么做會引入一些問題：做一次坍縮后，其他邊也跟著變了，他們的二次誤差必須被重新計算

所以需要從二次度量誤差中選最小的，取完最小的之后，我們要對它們的二次誤差做一次更新，于是我們就要用到優(yōu)先隊列 / 堆這種數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)能讓我們能取得二次誤差最小值的同時也能動態(tài)更新其他受影響的元素

另外，這種通過對局部計算最優(yōu)解，試圖找到全局的最優(yōu)解，是一個典型的貪心算法

注：本節(jié)開始講了光線追蹤，放在下一筆記中