圖形學演算法總結

直線生成演算法

數值微分法（DDA）

y = k x + b y = kx + b y=kx+b

x每增加1，y增量為k

|k|要小于1，大于則互換x，y

原因：防止畫出來的線太稀疏

中點畫線法

y = a x + b y + c y = ax + by +c y=ax+by+c

其中， a = y 0 ? y 1 ， b = x 1 ? x 0 a=y_0-y_1，b=x_1-x_0 a=y0??y1?，b=x1??x0?

我們每次都把中點(x+1,y+0.5)帶入方程，記結果為d，與0比較

• d≥0 中點在直線上方，取 （ x i ＋ 1 ， y i ） （x_i＋1，y_i） （xi?＋1，yi?）

  • d i + 1 = d i + a d_{i+1}=d_i+a di+1?=di?+a

• d<0 中點在直線下方，取 （ x i ＋ 1 ， y i ＋ 1 ） （x_i＋1，y_i＋1） （xi?＋1，yi?＋1）

  • d i + 1 = d i + a + b d_{i+1}=d_i+a+b di+1?=di?+a+b

其中，初始值 d 0 = a + 0.5 b d_0 = a+0.5b d0?=a+0.5b

可以用 2d 代替 d 來擺脫小數，提高效率，

Bresenham演算法

我們計算直線的斜率 k = d y d x k=\frac{dy}{dx} k=dxdy?

和DDA一樣，x每增加1，y增加k

于是，我們可以這樣算：

d 0 = 0 d_0=0 d0?=0 d i + 1 = d i + k d_{i+1} = d_i+k di+1?=di?+k

• d≥0.5 取 （ x i ＋ 1 ， y i ＋ 1 ） （x_i＋1，y_i＋1） （xi?＋1，yi?＋1）
• d<0.5 取 （ x i ＋ 1 ， y i ） （x_i＋1，y_i） （xi?＋1，yi?）

當 d≥1 的時候 d = d ? 1 d = d-1 d=d?1

當然，為了便于計算，可令 e = d ? 0.5 e = d-0.5 e=d?0.5

e 0 = ? 0.5 e_0=-0.5 e0?=?0.5 e i + 1 = e i + k e_{i+1} = e_i+k ei+1?=ei?+k

• e≥0 取 （ x i ＋ 1 ， y i ＋ 1 ） （x_i＋1，y_i＋1） （xi?＋1，yi?＋1）
• e<0 取 （ x i ＋ 1 ， y i ） （x_i＋1，y_i） （xi?＋1，yi?）

當 e≥0 的時候 e = e ? 1 e = e-1 e=e?1

圓弧生成演算法

中點Bresenham畫圓法

d = x 2 + y 2 ? R 2 d = x^2+y^2-R^2 d=x2+y2?R2

與前面類似 d 0 = 1.25 ? R d_0=1.25-R d0?=1.25?R

• d≥0 取 ( x i ＋ 1 ， y i ? 1 ) (x_i＋1，y_i-1) (xi?＋1，yi??1)
  • d i + 1 = d i + 2 ( x p ? y p ) + 5 d_{i+1}=d_i+2(x_p-y_p)+5 di+1?=di?+2(xp??yp?)+5
• d<0 取 ( x i ＋ 1 ， y i ) (x_i＋1，y_i) (xi?＋1，yi?)
  • d i + 1 = d i + + 2 x p + 3 d_{i+1}=d_i++2x_p+3 di+1?=di?++2xp?+3

為方便計算，使用e=d-0.25代替d

多邊形填充演算法

逐點判斷法

1）射線法

作射線求交點各數k

• k為奇數 點在多邊形內
• k為偶數 點在多邊形外

特殊情況：

2）累計角度法

與各頂點連線，形成有向角 θ i \theta_i θi?，然后作累加

• 結果為0 點在多邊形外
• 結果為±2 π \pi π 點在多邊形內

掃描線演算法(YX)

舉個例子，6號掃描線與多邊形交點并按x值遞增排序為A,B,C,D

然后我們就開始配對，AB一對，CD一堆，并給AB和CD這兩個線段填色，

依此類推，就能給多邊形填完色，

改進的掃描線演算法（Y-X）

活性邊表： x x x △ x △x △x y m a x y_{max} ymax?

邊表桶：

特殊情況：

• 水平邊扔掉

• X為小數

  
  • (a)交點位于左邊上，向右取整
  • (b)交點位于右邊上，向左取整

• (x,e)落在像素上

  
  • (a)(x,e)位于左邊上，屬于多邊形
  • (b)(x,e)位于右邊上，不屬于多邊形

• 交點位多邊形的頂點（下閉上開）

  

  應該是指經過P1的點

  • (a) 算作1個交點
  • (b) 算作1個交點
  • ? 算作2個交點
  • (d) 算作0個交點

邊緣填充演算法

對多邊形上每一條非水平邊上的每個象素開始向右求余

改進后有柵欄填充演算法和邊界標志演算法

區域種子填充演算法

1）深度遞回的種子填充演算法(漫水法）

1. 種子入堆疊

2. 堆疊非空，轉3；堆疊空，結束

3. 堆疊頂元素出堆疊，如果它未填充則填充，然后找其他方向未填充的點，將其入堆疊，找完所有方向后（4聯通就是4個方向，8聯通就是8個方向），轉2

假設方向是上下左右，那么順序就是

1. 堆疊：H
2. 填色：H 堆疊： I F J
3. 填色：J 堆疊：I F K N
4. 填色：N 堆疊：I F K M
5. 填色：M 堆疊：I F K L
6. 填色：L 堆疊：I F K
7. 填色：K 堆疊：I F
8. 填色：F 堆疊：I D G
9. 填色：G 堆疊：I D E
10. 填色：E 堆疊：I D
11. 填色：D 堆疊：I C
12. 填色：C 堆疊：I B
13. 填色：B 堆疊：I A
14. 填色：A 堆疊：I
15. 填色：I

2）掃描線種子填充演算法

其實就是種子填充的改進版，減少了遞回次數

掃描線種子填充演算法

1. 初始化：堆疊置空，將種子點（x，y）入堆疊，

2. 出堆疊：若堆疊空則結束，否則取堆疊頂元素（x，y），以y作為當前掃描線，

3. 填充并確定種子點所在區段：從種子點（x，y）出發，沿當前掃描線向左、右兩個方向填充，直到非內部，分別標記區段的左、右端點坐標為xl和xr，

4. 并確定新的種子點：在區間[xl，xr]中檢查與當前掃描線y上、下相鄰的兩條掃描線上的象素，若存在非邊界、未填充的象素，則把每一區間的最右象素作為種子點壓入堆疊，回傳第（2）步，

1. 填充DFHJM
2. 上下搜尋
   1. DFHJM任意一個往下走填充EDIK
   2. N往上走填充M
   3. D往上走填充C
3. 上下搜尋
   1. M往上走填充L
   2. C往上走填充B
4. 上下搜尋
   1. B往上走填充A

反走樣

有兩個方式，一個是提高解析度，另一個是改進演算法，這里當然講演算法嘍

簡單區域采樣（非加權區域采樣）

根據面積改變亮度達到反走樣效果

面積計算（m是斜率，像素寬為1）

• 情況(1)(5)陰影面積為： D 2 2 m \frac{D^2}{2m} 2mD2?
• 情況(2)(4)陰影面積為： D ? m 2 D - \frac{m}{2} D?2m?
• 情況(3)陰影面積為： 1 ? D 2 m 1-\frac{D^2}{m} 1?mD2?

上述陰影面積是介于0-1之間的正數，用它乘以象素的最大灰度值，再取整，即可得到象素的顯示灰度值，

加權區域采樣

其實就是在非加權區域采樣的基礎上加了個權值來表示與中心距離，然后計算灰度的時候要考慮這個權值，

直線和多邊形裁剪

編碼裁剪

D 3 D 2 D 1 D 0 D_3D_2D_1D_0 D3?D2?D1?D0?分別表示是否上于上邊界，是否下于下邊界，是否右于右邊界，是否左于左邊界

• 是為1，否為0

• 若 P 1 P 2 P_1P_2 P1?P2?完全在視窗內(code1 || code2) = 0, 則“取”
• 若 P 1 P 2 P_1P_2 P1?P2?明顯在視窗外(code1 & code2) ≠ 0, 則“棄”
• 在交點處把線段分為兩段，其中一段完全在視窗外，可棄之，然后對另一段重復上述處理

中點分割裁剪

和編碼的區別在于最后一步，不是交點處分為兩段，而是中點處，然后不斷二分，把完全在視窗外的舍棄，直到精度滿足要求，

梁友棟-Barskey演算法

首先，我們將這個線段確定一個方向，然后將線段和視窗延長，得到四個交點，記為 r 1 , r 2 , r 3 , r 4 r1,r2,r3,r4 r1,r2,r3,r4（這也是它們的橫坐標）

這樣，我們得到兩個入邊和兩個出邊（PPT上叫始邊和終邊）

這樣我們要裁剪得到的線段的兩個端點的橫坐標 u 1 u 2 u_1u_2 u1?u2?就可以確定了

• u 1 = m a x ( 0 , x 入 邊 1 , x 入 邊 2 ) u1 = max(0, x_{入邊1},x_{入邊2}) u1=max(0,x入邊1?,x入邊2?)
• u 2 = m i n ( 1 , x 出 邊 1 , x 出 邊 2 ) u2 = min(1, x_{出邊1},x_{出邊2}) u2=min(1,x出邊1?,x出邊2?)

那么我們要如何確定入邊出邊呢？

每個交點的橫坐標為 r k = q k p k r_k = \frac{q_k}{p_k} rk?=pk?qk??

如果 p k ≠ 0 p_k \neq 0 pk??=0

• p k < 0 p_k<0 pk?<0 入邊
• p k > 0 p_k>0 pk?>0 出邊

多邊形逐邊裁剪演算法

多邊形的各條邊的兩端點S、P，它們與裁剪線的位置關系只有四種:

情況（1）僅輸出頂點P；

情況（2）輸出0個頂點

情況（3）輸出線段SP與裁剪線的交點 I

情況（4）輸出線段SP與裁剪線的交點 I 和終點 P

雙邊裁剪演算法

這個我還沒實踐過，所以直接粘貼下PPT，演算法思想的話，PPT上這個夠看了，

簡單來說，就是我們的裁剪視窗不再是矩形了，而是一個多邊形，

演算法思想

1. 計算主多邊形與裁剪多邊形的交點
2. 如果主多邊形與裁剪多邊形有交點，則交點成對出現，它們被分為如下兩類
   1. 進點：主多邊形邊界由此進入裁剪多邊形內
   2. 出點：主多邊形邊界由此離開裁剪多邊形區域
3. 跟蹤任意一個交點
4. 如果為進點，則跟蹤主多邊形邊界
5. 如果為出點，則跟蹤裁剪多邊形邊界
6. 任選一個沒有跟蹤過的交點，按上述程序重新搜索，直至所有交點跟蹤完畢
7. 如果該交點為進點，跟蹤主多邊形邊邊界；否則跟蹤裁剪多邊形邊界
8. 跟蹤多邊形邊界，每遇到多邊形頂點，將其輸出到結果多邊形頂點表中，直至遇到新的交點
9. 將該交點輸出到結果多邊形頂點表中，并通過連接該交點的雙向指標改變跟蹤方向（如果上一步跟蹤的是主多邊形邊界，現在改為跟蹤裁剪多邊形邊界；如果上一步跟蹤裁剪多邊形邊界，現在改為跟蹤主多邊形邊界）
10. 重復(4)、(5)直至回到起點

消隱

深度快取演算法（Z_Buffer演算法）

加入一個深度快取陣列z[m][n]來存最小深度值

加入一個幀快取陣列FB[m][n]來存像素點對應顏色值

每個像素點上放深度最小的多邊形的顏色

掃描線演算法

掃描線的交點把這條掃描線分成了若干個區間，每個區間上必然是同樣一種顏色

對于有重合的區間，如** a 6 a 7 a_6a_7 a6?a7?**這個區間，要么顯示F2的顏色，要么顯示F3的顏色，不會出現顏色的跳躍

如果把掃描線和多邊形的這些交點都求出來，對每個區間，只要判斷一個像素的要什么顏色，那么整個區間的顏色都解決了，這就是區間掃描線演算法的主要思想，

需要的資料結構有很多，比如多邊形y桶、有效多邊形表APT、邊Y桶、有效邊表AET，具體這些是啥，看PPT吧

多邊形區域排序演算法

在規則化影像空間中，將多邊形按深度Z值自小至大排序，用前面的可見多邊形去切割其后面的多邊形，使得最終每一個多邊形要么是完全可見，要么完全不可見，

曲線曲面

我這里寫得有點點亂，以后有空再修改吧，

Hermite曲線

Bezier曲線

P i P_i Pi?是控制點

有n個控制點，那么曲線的階數就是n-1，計算量巨大

Bezier曲線的性質

• 端點性質 曲線過兩端點且與端點相切
• 對稱性: 若保持n次Bezier曲線的頂點的位置不變，而把次序顛倒，則曲線保持不變
• 凸包性： 伯恩斯坦多項式各項之和為1，這意味著Bezier曲線各點均落在特征多邊形頂點構成的凸包之中
• 幾何不變性：曲線的形狀僅與特征多邊形個頂點的相對位置有關，而與坐標的選擇無關

B樣條曲線

這個圖是PPT上的，和我下面的有些許不同，但實際是一樣的，

這個圖是我要講的，下面就逐步來解釋

啥是B樣條曲線？

整條曲線用一個完整的表達形式，但內在的量是一段一段的，比如一堆的3次曲線拼過去，兩條之間滿足2次連續

怎么分段呢？

每一段的基函式怎么求？

de Boor-Cox遞推定義

只要是k階（k-1次）的B樣潭訓函式，構造一種遞推的公式，由0次構造1次，1次構造2次，2次構造3次…依次類推

B樣條函式定義區間 u ∈ [ u k ? 1 , u n + 1 ] u\in[u_{k-1},u_{n+1}] u∈[uk?1?,un+1?] 是怎么來的？

B樣條曲線的性質

• 端點性質與連續性
• 當t=0 或 t=1分別代入三次B樣條方程得：
  P ( 0 ) = 1 / 3 ? ( ( p i + p i + 2 ) / 2 + 2 p i + 1 ) P(0)=1/3*((p_i+p_{i+2})/2+2p_{i+1}) P(0)=1/3?((pi?+pi+2?)/2+2pi+1?)
  P ( 1 ) = 1 / 3 ? ( ( p i + 1 + p i + 3 ) / 2 + 2 p i + 2 ) P(1)=1/3*((p_{i+1}+p_{i+3})/2+2p_{i+2}) P(1)=1/3?((pi+1?+pi+3?)/2+2pi+2?)
  三次B樣條在連接處的一階導數、二階導數都是連續的，‘
• 區域性：改變一個控制點的位置，最多影響四個曲線段，由此三次B樣條具有改變控制點的位置就可以對B樣條區域修改曲線
• 擴展性：增加一個控制點就相應增加一段B樣條曲線，而原有曲線不受任何影響

圖形變換

平移變換

二維

三維

比例變換

二維

三維

旋轉變換

二維

三維

繞z軸旋轉

繞x軸旋轉

繞y軸旋轉

對稱變換

錯切變換

投影變換

正交平行投影

斜交投影

透視投影