計算機圖形學（二）劃線算法

一、光栅系統繪制圖形的原理

1、光栅系統的圖元都是由像素點組成的

2、像素點的坐标值都是整數，是離散的，是以表示圖形時會出現鋸齒現象 

3、要繪制圖形元素，就必須計算出組成圖形元素的所有像素點的坐标值 

4、好的算法（計算所有像素的坐标值）不但速度快，還要盡可能的減小鋸齒的影響

二、劃線算法

1、要求：給出線段的兩個端點的坐标值，繪制出直線 

2、可以計算出斜率 m 和節距 b

三、DDA算法

1、如果斜率 m 小于 1 ，則水準方向每增加一個機關，垂直方向就增加 m 個機關，即

yk+1 =yk + m

計算結果要四舍五入，這樣就可快速計算出線段上所有像素點的坐标值

2、如果斜率 m 大于 1，則垂直方向每增加一個機關，水準方向就增加 1/m 個機關，即

xk+1 = xk + 1/m 

計算結果要四舍五入

3、區分 m 大于或者小于 1 是為了在變化率較小的方向上計算，可以減少鋸齒

4、DDA算法的特點

充分利用了光栅的特性

比直接利用直線公式計算速度快，

累加過程中涉及到浮點運算，仍然耗時，且有誤差

三、Bresenham  劃線算法

1、基本思想

劃線過程中，一個方向上的坐标總是加1，另一方向上的坐标要麼不變、要麼加1，能不能通過某種方法做出判斷，利用上述特性，進而避免浮點運算 

如上圖所示：起始點的坐标為（xi,yi），則下一點的坐标應該為（xi+1,y），這一點叫理論計算點

由于光栅系統的坐标是離散的，理論計算點不存在，是以我們隻能從理論計算點的上面或者下面，即（xi+1,yi）或者（xi+1,yi+1）兩個裡面選一個

道理很簡單， 這兩個那個離理論計算點更近，就選哪個。

如圖：我們可以計算 d2-d1，如果大于零，則上面的點誤差更大，選則下面的點；如果小于零，則選擇上面的點。

2、消除浮點運算：

pk= (delta)x  乘以  (d2-d1)

将 d2-d1 乘以 delta x 就可以消除 m ，進而避免浮點運算

3、遞推公式

 pk+1 = pk + 2delta(y) - 2delta(x) (yk+1 - yk)

其中 

yk+1 - yk 的值根據 pk 的符号，要麼為零（即 y 坐标不變），要麼為 1（即向上遞增一個坐标）

4、初始值 p0

p0 = 2delta(y) - delta(x) 

5、例題 

//==========================================

本文轉自左洸部落格園部落格，原文連結：http://www.cnblogs.com/myqiao/archive/2011/06/09/2076467.html，如需轉載請自行聯系原作者