圖形學 畫線算法

• 0.原始
• 1.數值微分法（DDA ）畫線法
• 2.中點畫線法
• 3.Bresenham 畫線法

0.原始

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

k = y 1 − y 0 x 1 − x 0 k=\frac{y_1-y_0}{x_1-x_0} k=x1​−x0​y1​−y0​​

假 設 x 已 知 ， 即 從 x 的 起 點 x 0 開 始 ， 沿 x 方 向 前 進 一 個 像 素 （ 步 長 等 于 1 ） ， 可 以 計 算 出 對 應 的 y 值 假設x已知，即從x的起點x_0開始，沿x方向前進一個像素（步長等于1），可以計算出對應的y值 假設x已知，即從x的起點x0​開始，沿x方向前進一個像素（步長等于1），可以計算出對應的y值

由于像素的坐标是整數，是以y值還要進行取整處理

直接向下取整誤差大： p ( 1.7 , 0.8 ) → 取 整 p ( 1 , 0 ) p(1.7,0.8)\overset{取整}{\rightarrow}p(1,0) p(1.7,0.8)→取整p(1,0)

四舍五入取整誤差小： p ( 1.7 , 0.8 ) → + 0.5 p ( 2..2 , 1.3 ) → + 0.5 p ( 2 , 1 ) p(1.7,0.8)\overset{+0.5}{\rightarrow}p(2..2,1.3)\overset{+0.5}{\rightarrow}p(2,1) p(1.7,0.8)→+0.5p(2..2,1.3)→+0.5p(2,1)

1.數值微分法（DDA ）畫線法

使用增量思想，将乘法減少，隻剩下加法

y i = k x i + b y_i=kx_i+b yi​=kxi​+b

y i + 1 = k x i + 1 + b y_{i+1}=kx_{i+1}+b yi+1​=kxi+1​+b

y i + 1 = k ( x 1 + 1 ) + b y_{i+1}=k(x_1+1)+b yi+1​=k(x1​+1)+b

y i + 1 = k x 1 + b + k y_{i+1}=kx_1+b+k yi+1​=kx1​+b+k

y i + 1 = y 1 + k y_{i+1}=y_1+k yi+1​=y1​+k

目前的y值等于前一步的y值加上斜率k

斜率小于等于0時，可以使用y方向，如果斜率大于1，則需要使用x方向遞增，否則會出現距離很大的離散點

2.中點畫線法

改進效率，将浮點運算變為整數加法

F ( x , y ) = A x + B y + C = 0 F(x,y)=Ax+By+C=0 F(x,y)=Ax+By+C=0

• 對 于 直 線 上 的 點 F ( x , y ) = 0 對于直線上的點 F(x,y)=0 對于直線上的點F(x,y)=0
• 對 于 直 線 上 方 的 點 F ( x , y ) > 0 對于直線上方的點 F(x,y)>0 對于直線上方的點F(x,y)>0
• 對 于 直 線 下 方 的 點 F ( x , y ) < 0 對于直線下方的點 F(x,y)<0 對于直線下方的點F(x,y)<0

假定： 0 ≤ ∣ k ∣ ≤ 1 0 \leq |k| \leq1 0≤∣k∣≤1。是以，每次x方向上加1，y方向上加1或不變需要判斷

y 方 向 上 y i 與 y i + 1 的 中 點 為 y m y方向上y_i與y_{i+1}的中點為y_m y方向上yi​與yi+1​的中點為ym​

d i = F ( x m , y m ) d_i=F(x_m,y_m) di​=F(xm​,ym​)

d i = A x m + B y m + C d_i=Ax_m+By_m+C di​=Axm​+Bym​+C

d i = A ( x i + 1 ) + B ( y i + 0.5 ) + C d_i=A(x_i+1)+B(y_i+0.5)+C di​=A(xi​+1)+B(yi​+0.5)+C

• 當 d < 0 時 ： 中 點 在 下 方 ， 說 明 應 取 上 方 的 點 當d<0時：中點在下方，說明應取上方的點 當d<0時：中點在下方，說明應取上方的點
• 當 d > 0 時 ： 中 點 在 上 方 ， 說 明 應 取 下 方 的 點 當d>0時：中點在上方，說明應取下方的點 當d>0時：中點在上方，說明應取下方的點

引進增量思想

y = { y + 1 ( d < 0 ) y ( d ≥ 0 ) y=\left\{\begin{matrix} & y+1 &(d<0) \\ & y &(d\geq0) \end{matrix}\right. y={​y+1y​(d<0)(d≥0)​

d 0 = F ( x m 0 , y m 0 ) d_0=F(x_{m_0},y_{m_0}) d0​=F(xm0​​,ym0​​)

d 0 = F ( x 0 + 1 , y 0 + 0.5 ) d_0=F(x_0+1,y_0+0.5) d0​=F(x0​+1,y0​+0.5)

d 0 = A ( x 0 + 1 ) + B ( y 0 + 0.5 ) + C d_0=A(x_0+1)+B(y_0+0.5)+C d0​=A(x0​+1)+B(y0​+0.5)+C

d 0 = A x 0 + B y 0 + C + A + 0.5 B d_0=Ax_0+By_0+C+A+0.5B d0​=Ax0​+By0​+C+A+0.5B由于原點在直線上，

d 0 = A + 0.5 B d_0=A+0.5B d0​=A+0.5B

當 d < 0 時 當d<0時 當d<0時

d 1 = F ( x m 1 , y m 1 ) d_1=F(x_{m_1},y_{m_1}) d1​=F(xm1​​,ym1​​)

d 1 = F ( x i + 2 , y i + 1.5 ) d_1=F(x_i+2,y_i+1.5) d1​=F(xi​+2,yi​+1.5)

d 1 = A ( x i + 2 ) + B ( y i + 1.5 ) + C d_1=A(x_i+2)+B(y_i+1.5)+C d1​=A(xi​+2)+B(yi​+1.5)+C

d 1 = A ( x i + 1 ) + B ( y i + 0.5 ) + C + A + B d_1=A(x_i+1)+B(y_i+0.5)+C+A+B d1​=A(xi​+1)+B(yi​+0.5)+C+A+B

d 1 = d 0 + A + B d_1=d_0+A+B d1​=d0​+A+B

當 d ≥ 0 時 當d\geq0時 當d≥0時

d 1 = F ( x m 1 , y m 1 ) d_1=F(x_{m_1},y_{m_1}) d1​=F(xm1​​,ym1​​)

d 1 = F ( x i + 2 , y i + 1.5 ) d_1=F(x_i+2,y_i+1.5) d1​=F(xi​+2,yi​+1.5)

d 1 = A ( x i + 2 ) + B ( y i + 0.5 ) + C d_1=A(x_i+2)+B(y_i+0.5)+C d1​=A(xi​+2)+B(yi​+0.5)+C

d 1 = A ( x i + 1 ) + B ( y i + 0.5 ) + C + A d_1=A(x_i+1)+B(y_i+0.5)+C+A d1​=A(xi​+1)+B(yi​+0.5)+C+A

d 1 = d 0 + A d_1=d_0+A d1​=d0​+A

d n e w = { d o l d + A + B ( d o l d < 0 ) d o l d + A ( d o l d ≥ 0 ) d_{new}=\left\{\begin{matrix} & d_{old}+A+B &(d_{old}<0) \\ & d_{old}+A &(d_{old}\geq0) \end{matrix}\right. dnew​={​dold​+A+Bdold​+A​(dold​<0)(dold​≥0)​

d 0 = A + 0.5 B d_0=A+0.5B d0​=A+0.5B

A、B、C作為整數，則我們将2d代入，可以将浮點運算減去

3.Bresenham 畫線法

算法不僅可以解決畫直線問題，還能解決圓弧、抛物線甚至隻有曲線的光栅化問題

思想是通過各行、各列像素中心構造一組虛拟網格線，按照直線七點到終點的順序，計算直線與各垂直網格線的交點，然後根據誤差項的符号确定該列像素中與交點最近的像素。

假設每次x+1，y的遞增（減）量為0或者1，它取決于實際直線與最近光栅網格點的距離，這個距離的最大誤差為0.5。

k為斜率

d = d + k d=d+k d=d+k

一旦 d ≥ 1 ， 就 把 它 減 去 1 ， 保 證 d 的 相 對 性 ， 且 在 0 、 1 之 間 d\geq1，就把它減去1，保證d的相對性，且在0、1之間 d≥1，就把它減去1，保證d的相對性，且在0、1之間

{ x i + 1 = x i + 1 y i + 1 = { y i + 1 = y i + 1 ( d > 0.5 ) y i ( d ≤ 0.5 ) \left\{\begin{matrix} & x_{i+1}=x_i+1 &\\ & y_{i+1}=\left\{\begin{matrix} & y_{i+1}=y_i+1 &(d>0.5) \\ & y_{i} &(d\leq0.5) \end{matrix}\right. & \end{matrix}\right. ⎩⎨⎧​​xi+1​=xi​+1yi+1​={​yi+1​=yi​+1yi​​(d>0.5)(d≤0.5)​​​

令e=d-0.5

{ x i + 1 = x i + 1 y i + 1 = { y i + 1 = y i + 1 ( e > 0 ) y i ( e ≤ 0 ) \left\{\begin{matrix} & x_{i+1}=x_i+1 & \\ & y_{i+1}=\left\{\begin{matrix} & y_{i+1}=y_i+1 &(e>0) \\ & y_{i} &(e\leq0) \end{matrix}\right. & \end{matrix}\right. ⎩⎨⎧​​xi+1​=xi​+1yi+1​={​yi+1​=yi​+1yi​​(e>0)(e≤0)​​​

e>0，y方向遞增1；e<0，y方向不遞增

e=0時，可任選上下光栅點顯示

• e 0 = − 0.5 e_0=-0.5 e0​=−0.5
• 每走一步有e=e+k
• 如果e>0則e=e-1

由于算法中隻用到誤差項的符号，是以可以使用 e ∗ 2 ∗ △ x e*2* \bigtriangleup x e∗2∗△x來替換e

k = d y d x k=\frac{dy}{dx} k=dxdy​

• e 0 = − △ x e_0=- \bigtriangleup x e0​=−△x
• 每 走 一 步 有 e = e + 2 ∗ △ y 每走一步有e=e+2* \bigtriangleup y 每走一步有e=e+2∗△y
• 如 果 e > 0 則 e = e − 2 ∗ △ x 如果e>0則e=e-2* \bigtriangleup x 如果e>0則e=e−2∗△x