第3章圖元掃描轉換3.1實驗內容簡述和實驗目標3.2掃描轉換直線段(DDA)3.3基于Bresenham算法繪制直線段3.4基于Bresenham算法繪制圓3.5課外拓展性實驗

3.1實驗內容簡述和實驗目標

基本實驗內容包括：掃描轉換直線段、基于Bresenham算法繪制直線段、基于Bresenham算法繪制圓。

完成本實驗后，讀者能夠：

(1)描述光柵化的原因和原理(布魯姆知識模型：記憶和理解)；

(2)列舉常見的光柵化繪制現象(布魯姆知識模型：理解)；

(3)復述DDA、中點、Bresenham算法流程(布魯姆知識模型：記憶)；

(4)推導DDA、中點、Bresenham算法繪制二次曲線的遞推公式，并能夠算法化(布魯姆知識模型：理解和應用)；

(5)基于OpenGL，采用中點、Bresenham算法編程繪制二次曲線(布魯姆知識模型：應用)；

(6)檢查并發現圖元光柵化繪制效果存在的問題，判斷原因，找出對策并改善(布魯姆知識模型：應用、分析、評價)。

3.2掃描轉換直線段(DDA)

給定直線方程y

=k

×x

+b上兩點(x0，y0)和(x1，y1)，繪制上述兩點之間的直線段。

(3.1)

對應算法步驟為：

(1)輸入直線段的兩端點p0(x0，y0)和p1(x1，y1)。

(2)計算公式(3.1)中的初始值k。

(3)令直線段上的點為(xf，yf)，初始為(x0，y0)。

(4)當xf

<=x1時，迭代以下兩步驟，否則結束

①將(xf，yf)取整為(xi，yi)，并進行繪制。

②計算直線段上的下一點，即xf

=xf

+1，并根據公式(3.1)計算下一點的yf。

1.關鍵函數代碼實現

2.案例效果

用DDA方法繪制一條直線段，直線段的兩端點如圖3-1(a)所示，坐標分別為(-200，-200)和(200，200)，最終效果如圖3-1(b)所示。

圖3-1用DDA方法繪制直線段

3.3基于Bresenham算法繪制直線段

假設當前像素點坐標為(xi，yi,r)，且當前直線段的斜率小于等于1，則逼近直線段的下一個像素點坐標(xi+1，yi+1,r)的具體取值規則如下：xi+1=xi

+1；yi+1,r的值由公式(3.2)給出。這里，di為yi+1,r取值的判別公式，由其決定下一像素點為(xi+1，yi,r)還是(xi+1，yi,r

+1)。此處，令di=yi+1–yi,r

–0.5，其中yi+1為當前直線段與x

=xi+1相交時的真實y坐標。

為此，當di≥0時，說明當前直線段的下一實際交點(xi+1，yi+1)離(xi+1，yi,r

+1)更近，即yi+1,r更適合為yi,r

+1；否則，yi+1,r更適合取值yi,r。同時，判別式的遞推公式為di+1

=yi+2

–yi+1,r

–0.5=yi+1

+k

–yi+1,r

–0.5，也取決于yi+1,r的取值，如公式(3.3)所示。此處，k為當前直線段的斜率(dy

÷dx)，為此，di的初始值為k–0.5。

為了提高算法的效率，對上述公式實施整數計算。為此，對判別式乘以2?×?dx，此時公式(3.3)更新為公式(3.4)，且初始di為2

×dy

–dx。

(3.4)

對應算法步驟如下：

(1)輸入直線的兩端點p0(x0，y0)和p1(x1，y1)。

(2)計算初始值dy，dx，d。

(3)繪制點(xf，yf)，初始值為(x0，y0)。

(4)判斷d的符號。若d>=0，則下一個(x，y)更新為(x

+1，y

+1)，同時將d更新為d

+?2?×?(dy

-

dx)；否則，將下一個(x，y)更新為(x+1，y)，d更新為d

+?2?×?dy。

(5)當xf

<x1時，迭代步驟(3)和(4)。否則結束。

1.關鍵函數代碼實現

2.案例效果

用Bresenham算法繪制一條直線段，直線段的兩端點如圖3-2(a)所示，坐標分別為(0，0)和(100，100)，最終效果如圖3-2(b)所示。

圖3-2用Bresenham算法繪制直線段

3.4基于Bresenham算法繪制圓

基于Bresenham算法繪制圓的算法的主要步驟如下：

(1)輸入圓的半徑r，默認圓心為(0，0)。

(2)計算初始值x、y，判別式d?=?3-2r。

(3)根據圓的對稱性繪制點(x，y)，(-x，y)，(x，-y)，(-x，-y)，(y，x)，(-y，x)，(y，-x)，(-y，-x)。

(4)根據d的符號確定下一點y的取值。如果d＞0，則下一個(x，y)更新為(x+1，y-1)，同時將判別式d更新為d+4(x-y)+10；否則下一個(x，y)更新為(x+1，y)，將判別式d更新為d+4x+6。

(5)迭代步驟(3)和(4)，直至圓繪制結束。

1.關鍵函數代碼實現

2.案例效果

用Bresenham算法繪制一個圓心在(0，0)、半徑為200