電腦圖形學提綱

2020 年 5 月 27 日
筆記
電腦圖形學

電腦圖形學提綱

註：本程式碼為偽程式碼，部分風格依據 python

掃描轉換演算法

直線

DDA演算法

當斜率絕對值小於1時

def LineDDA(x0: int, y0: int, x1: int, y1: int):
    
    m = (y1-y0)/(x1-x0)	# y增量
    
    x = x0
    y = float(y0)+0.5	# 始點
    
    for x in range(x0, x1):
        putPixel(x, int(y))
        y += m

中點畫線法

令 \(f(x, y)=Ax+By+C\) ，則

f > 0，則位於直線上方
f = 0，則位於直線
f < 0，則位於直線下方

計算 \(f (x+1, y+0.5)\) ，若 < 0 則取 (x+1, y+1)，若 > 0 則取 (x+1, y)

若取 (x+1, y+1)，則 \(f\) 增量為 \(f (x+2, y+1.5)-f (x+1, y+0.5)=A+B\)
若取 (x+1, y)，則 \(f\) 增量為 \(f (x+2, y+0.5)-f (x+1, y+0.5)=A\)

初始值為 d = (x₀+1, y₀+0.5) ，後隨節點更新加上增量

def MidPointLine(x0: int, y0: int, x1: int, y1: int):
    dx = x1-x0
    dy = y1-y0
    
    d = dx-2*dy		# 初始值
    incrE = -2*dy	# (x+1, y)增量
    incrNE = 2*(dx-dy)	# (x+1, y+1)增量
    
    y = y0
    for x in range(x0, x1):
        putPixel(x, y)
        
        if d > 0:
            d += incrE
        else:
        	d += incrNE
            y += 1

Bresenham 演算法

按照增量計算下一點，即

累計的 \(\Delta y+k>0.5\)，則向上畫點，\(\Delta y\) – – += k
累計的 \(\Delta y+k\leq0.5\)，則向上畫點，\(\Delta y\) += k

初始 \(\Delta y\) = – 0.5，然後同時乘\(\Delta x\)，有

def BresenhamLine(int x0,int y0,int x1,int y1):
    dx = x1-x0
    dy = y1-y0
    
    d = -dx
    
    y = y0
    for x in range(x0, x1):
        putPixel(x, y)
        
        x += 1
        d += 2*dy
        
        if d >= 0:
            y += 1
            d -= 2*dx

圓形

中點畫圓法

圓是1 / 8 對稱的圖形，所以只需要會繪製 1 / 8，判斷 1 / 2 點在圓內還是圓外

def MidPointCircle(r: int):
    x=0
    y=r		# 從最上方點開始向左繪製
    
    d=1-r
    
    putPixel(x,y)
    while x < y:
        if d < 0:
            d += 2*x+3
            x += 1
        else:
        	d += 2*(x-y)+5
            x += 1
            y -= 1
        putPixel(x,y)

Bresenham 畫圓演算法

繪製1 / 4的圓，與上同理，為一步一步的遞推判斷

def BresenhamCircle(r: int):
    x = 0
    y = r
    
    delta = 2*(1-r)
    
    while y >= 0:		# 判斷點移動方向
        putPixel(x,y)
        if delta < 0:		# 右中方向
            delta1 = 2*(delta+y)-1
            if delta1 <= 0:
                direction=1
            else:
                direction=2
        else if delta > 0:	# 右下方向
            delta2 = 2*(delta-x)-1
            if delta2 <= 0:
                direction=2
            else:
                direction=3
        else:
            direction=2
        
        switch direction:	# 移動後更新值
            case 1:			# 右方
                x++;
                delta += 2*x+1
                break
            case 2:			# 右下方
                x++; y--;
                delta += 2*(x-y+1)
                break
            case 3:			# 下方
                y--;
                delta += (-2*y+1)
                break

橢圓

導數為1的點為 \((x_p, y_p)\)

\[\left\{
\begin{array}{}
x_p=\frac{a^2}{\sqrt{a^2+b^2}}\\
y_p=\frac{b^2}{\sqrt{a^2+b^2}}
\end{array}
\right.
\]

\((0,b)\)到 p：

d = f(1, b-0.5) = b**2 + (-b+0.25)*a**2
if d <= 0:			# 右
    d = d+(2*x+3)*b**2
else if d > 0:		# 右下
    d = d+(2*x+3)*b**2+(-2y+2)*a**2

p 到 \((a,0)\)：

d = f(x+0.5, y-1) = b**2*(x+0.5)**2+a**2*(y-1)**2-a**2*b**2
if d <= 0:			# 右下
    d = d+(-2*y+3)*a**2+(2x+2)*b**2
else if d > 0:		# 下
    d = d+(-2*y+3)*a**2

圖形裁剪

線段

Cohen-Sutherland 程式碼裁剪演算法

四位二進位碼錶示所在區域，四位分別為 [上下右左]

code1 = code2 = 0，在窗內
code1 & code2 != 0，在窗外
都不對，則取交點，分類討論

中點分割裁剪演算法

一直二分，直到到達交點

Liang－Barsky 演算法

	p	q
1	–\(\Delta\)x	\(x1-xl\)
2	\(\Delta\)x	\(xr-x1\)
3	–\(\Delta\)y	\(y1-yb\)
4	\(\Delta\)y	\(yt-y1\)

\(u_k=q_k / p_k\)

若\(\Delta x=0\)，則
- if q1<0 || q2<0
  - 不在窗口
- \(u_{max}=\max(0, u_k|pk<0)\)，k=3,4
- \(u_{min}=\min(1, u_k|pk>0)\)
- 轉後
若\(\Delta y=0\)，則
- if q3<0 || q4<0
  - 不在窗口
- \(u_{max}=\max(0, u_k|pk<0)\)，k=1,2
- \(u_{min}=\min(1, u_k|pk>0)\)
- 轉後
若都不滿足
- \(u_{max}=\max(0, u_k|pk<0)\)，k=1,2,3,4
- \(u_{min}=\min(1, u_k|pk>0)\)
- 轉後
後：
- if \(u_{max}>u_{min}\)
  - 不在窗口
- x = x1 + u · (x2-x1)，y = y1 + u · (y2-y1)，計算交點坐標，然後畫線

多邊形

Sutherland－Hodgman 逐邊裁剪法

逐個點判斷是否位於一側入棧，穿越時計算交點入棧

存在退化邊，可以使用顏色異或計算消除

邊界裁剪演算法

加入交點的窗點集，加入交點的多邊形點集，按同一旋轉方向排列，遇到交點就判斷是否跳轉。可能生成多個點集，一直到所有交點都遍歷。

內裁剪 / 外裁剪

即保留窗內 / 窗外內容

二維三維圖形變換

基本變換

二維變換

\(p’ = p·T\)

點形式：[[x, y, 1], …] ，1為放大倍率

變換矩陣形式：

平移

\[\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
T_x & T_y & 1
\end{bmatrix}
\]

比例

\[\begin{bmatrix}
s_x & 0 & 0 \\
0 & s_y & 0 \\
0 & 0 & 1
\end{bmatrix}
\]

旋轉

\[\begin{bmatrix}
\cos\theta & \sin\theta & 0 \\
-\sin\theta & \cos\theta & 0 \\
0 & 0 & 1
\end{bmatrix}
\]

對稱

對稱於y軸：\(\begin{bmatrix}
-1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}\)

對稱於x軸：\(\begin{bmatrix}
1 & 0 & 0 \\
0 & -1 & 0 \\
0 & 0 & 1
\end{bmatrix}\)

對稱於原點：\(\begin{bmatrix}
-1 & 0 & 0 \\
0 & -1 & 0 \\
0 & 0 & 1
\end{bmatrix}\)

對稱於y=x：\(\begin{bmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{bmatrix}\)

對稱於y=-x：\(\begin{bmatrix}
0 & -1 & 0 \\
-1 & 0 & 0 \\
0 & 0 & 1
\end{bmatrix}\)

錯切

x = x + cy OR y = y + bx

三維變換

同理，只是最右端上方三個參數代表透視

複合變換

\(p’ = p·T_1·T_2· …\)

\[\begin{bmatrix}
x1 & y1 & 1
\end{bmatrix}
\begin{bmatrix}
a & b & p \\
c & d & q \\
l & m & s
\end{bmatrix}=
\begin{bmatrix}
ax1+cy1+l & bx1+dy1+m & px1+qy1+s
\end{bmatrix}
\]

三維圖形投影和消隱

視圖

主視圖

\(\begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}\)

側視圖

\(\begin{bmatrix}
0 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}\)

俯視圖

\(\begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}\)

透視投影

\(\begin{bmatrix}
1 & 0 & 0 & p\\
0 & 1 & 0 & q\\
0 & 0 & 1 & r\\
0 & 0 & 0 & 1
\end{bmatrix}\)

結果為\(\begin{bmatrix}
x & y & z & px+qy+rz+1
\end{bmatrix}\)

主滅點\(\begin{bmatrix}
1/p & 0 & 0 & 0
\end{bmatrix}\)同理有y,z滅點

消隱畫法

逆時針面向量與視線夾角

若投影到Z-X面上，可見條件為

\(\begin{bmatrix}
Z_A-Z_S & X_A-X_S\\
Z_B-Z_A & X_B-X_A
\end{bmatrix}>0\)

① 按照三表結構的形式建立描述立體模型的頂點表、環表和面表；
② 根據要生成立體圖形的種類（正等軸測投影），採用相應變換矩陣對立體的頂點進行坐標變換；
③ 按照面表中的指示地址從相應的環表中取出頂點序號，利用變換後的頂點坐標對立體的面逐一計算出每個面的E值，根據E的正負判別面的可見性；
④ 對於可見面，按照該面所對應的環表連點繪出多邊形的邊框。

曲線曲面

拋物線

Hermite 曲線

\(\begin{bmatrix}
2 & -2 & 1 & 1\\
-3 & 3 & -2 & -1\\
0 & 0 & 1 & 0\\
1 & 0 & 0 & 0
\end{bmatrix}\begin{bmatrix}
p_0\\p_1\\p’_0\\p’_1
\end{bmatrix}\)

Bezier曲線

分割遞歸演算法

\[B_{i,n}(t)=C^i_nt^i(1-t)^{n-i}\\
C(t)=\sum^n_{i=0}p_iB_{i,n}(t)
\]

\(C(0)=p_0\)

\(C(1)=p_n\)

曲線在兩端點處的 r 階導數只與 r＋1 個相臨點有關，而與更遠的點無關。
點次序顛倒，形狀不變

二次Bezier曲線

\[C(t)=
\begin{bmatrix}
t^2 & t & 1
\end{bmatrix}
\begin{bmatrix}
1 & -2 & 1\\
-2 & 2 & 0\\
1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
p_0\\p_1\\p_2
\end{bmatrix}
\]

三次的矩陣

\(\begin{bmatrix}
-1 & 3 & -3 & 1\\
3 & -6 & 3 & 0\\
-3 & 3 & 0 & 0\\
1 & 0 & 0 & 0
\end{bmatrix}\)

k次B樣條曲線

\[F_{i,n}(t)=\frac{1}{n!}\sum^{n-k}_{j=0}(-1)^jC^j_{n+1}(t+n-k-j)^{n}\\
C(t)=\sum^n_{k=0}p_{i+k}F_{i,n}(t)
\]

二次B樣條曲線，\(t\in [0,1]\)

\(\frac{1}{2}*\begin{bmatrix}
1 & -2 & 1\\
-2 & 2 & 0\\
1 & 1 & 0
\end{bmatrix}\)

三次B樣條曲線，\(t\in [0,1]\)

\(\frac{1}{6}*\begin{bmatrix}
-1 & 3 & -3 & 1\\
3 & -6 & 3 & 0\\
-3 & 0 & 3 & 0\\
1 & 4 & 1 & 0
\end{bmatrix}\)

Tags: 電腦圖形學