《計(jì)算機(jī)圖形學(xué)》課件第三章

第三章基本圖形生成技術(shù)

3.1直線的生成算法3.2圓的生成算法3.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充3.4字符的生成3.5基本圖元的輸出屬性3.6光柵圖形的反走樣充區(qū)域、字符串等基本幾何結(jié)構(gòu)，本章將討論這些基本幾何結(jié)構(gòu)的設(shè)備級(jí)算法。對(duì)此，假定物體的位置直接以整數(shù)坐標(biāo)給出，像素位置按照掃描線行數(shù)和列數(shù)指定，其編址方案如圖3.1所示。掃描線從屏幕底部由零開始編號(hào)，像素列則沿每條掃描線從左至右由零開始編號(hào)，每個(gè)像素區(qū)域由左下角的整數(shù)網(wǎng)格坐標(biāo)來指定。圖3.1光柵顯示器編址為了將對(duì)應(yīng)于沿掃描線y的列x的位置上指定顏色裝入幀緩沖器，我們假設(shè)有以下形式的底層函數(shù)：

setPixel(x，y，c)

有時(shí)也要求能提取當(dāng)前幀緩沖器某個(gè)特定位置的亮度值（顏色值），為此我們假設(shè)有下述的底層函數(shù)：

getPixel(x，y)

3.1直線的生成算法

由于光柵圖形顯示器可看做是由離散的可發(fā)光像素組成的矩陣，因此，很難將一點(diǎn)和另一點(diǎn)直接連成直線，我們將確定像素最佳逼近直線的過程稱為光柵化。顯然，水平線、垂直線以及45°線的光柵化比較簡單，而其他方向直線的光柵化則較為困難。3.1.1畫直線的一般要求

首先假設(shè)為兩狀態(tài)顯示，即每個(gè)像素點(diǎn)非黑即白，于是將屏幕上的像素點(diǎn)設(shè)置成黑色或者白色就可以顯示出一幅圖像來，除過水平線和垂直線之外，所有的直線都將顯示出“鋸齒”或“階梯狀”效果。給定直線段的端點(diǎn)整數(shù)坐標(biāo)后，光柵圖形顯示器畫直線的一般要求有以下三點(diǎn)：

（1）直線是直的、光滑的，且具有精確的起點(diǎn)和

終點(diǎn)。

光柵圖形顯示器采用逼近的思想來生成直線的特性決定了它難以生成完美的直線，也不能保證直線精確地通過指定的起點(diǎn)和終點(diǎn)，這些使得所畫的直線呈現(xiàn)階梯狀或鋸齒狀。這一點(diǎn)可通過使用高分辨率顯示器來改善。（2）與直線段的顯示順序無關(guān)，所顯示的亮度沿直線不變，且與直線的長度和方向無關(guān)。首先，直線段的起點(diǎn)和終點(diǎn)只是數(shù)學(xué)上的一個(gè)叫法，生成的直線與哪個(gè)端點(diǎn)被定義為起點(diǎn)，哪個(gè)端點(diǎn)被定義為終點(diǎn)無關(guān)，也即與生成直線的順序無關(guān)。另外，一個(gè)明顯的事實(shí)是只有水平線、垂直線和45°線的亮度線段是沿直線段不變的，而其他方向直線的亮度由于光柵化導(dǎo)致其結(jié)果是不均勻的。即使對(duì)于上述的特殊情形，直線的亮度也與其方向有關(guān)。如圖3.2所示，45°線上像素間距大于垂直線和水平線上的像素間距，這使垂直線和水平線比45°線較亮。圖3.2垂直線與45°線上像素點(diǎn)分布假設(shè)圖中像素點(diǎn)的亮度值為I，則垂直線上單位長度的亮度值為I，而45°線上單位長度的亮度值為。為了使不同長度和方向的直線具有相同亮度，需要進(jìn)行開方運(yùn)算，這使得運(yùn)算速度變慢。一般采用折中方法，即只計(jì)算線段長度的近似值，利用整數(shù)運(yùn)算減少計(jì)算量以及用硬件實(shí)現(xiàn)運(yùn)算等。3.1.2直線的DDA算法

實(shí)現(xiàn)直線光柵化最簡單的方法就是解直線的微分方程。設(shè)直線的起點(diǎn)坐標(biāo)為(xs，ys)，終點(diǎn)坐標(biāo)為(xe，ye)，那么該直線的微分方程是：(3.1)(3.２)其解為或式中，(xi，yi)是直線上某一點(diǎn)的坐標(biāo)值。式（3.1）和（3.2）表示所求直線y值和x值的逐次遞歸關(guān)系，遞歸的初值為直線的起點(diǎn)(xs，ys)。DDA(DigitalDifferentialAnalyzer)算法即數(shù)字微分分析算法就是基于式（3.1）或（3.2）對(duì)直線進(jìn)行光柵化的算法。在一個(gè)坐標(biāo)軸上以單位間隔對(duì)直線采樣，以此決定另一個(gè)坐標(biāo)軸上最靠近直線的對(duì)應(yīng)整數(shù)值。首先考慮具有非負(fù)斜率的直線，當(dāng)m≤1時(shí)，在單位

x間隔(Δx=1)取樣并計(jì)算每個(gè)連續(xù)的y值：

yi+1=yi+m

(3.3)

由于m可以是介于0與1之間的任意實(shí)數(shù)，所以計(jì)算出的y值顯示在光柵顯示器上時(shí)應(yīng)先取整。

當(dāng)m>1時(shí)，則將x和y交換，即在單位y間隔(Δy=1)取樣并計(jì)算每個(gè)連續(xù)的x值：

xi+1=xi+m－1

(3.4)當(dāng)直線的斜率為負(fù)時(shí)，如果－1≤m≤0，那么，Δx=－1，并且

yi+1=yi－m

(3.5)

當(dāng)m<－1時(shí)，則Δy=－1，且

xi+1=xi－m－1

(3.6)

總結(jié)起來也可以將問題簡化為：當(dāng)|m|≤1時(shí)，令

xs<xe，則Δx=1，yi+1=yi+m；當(dāng)|m|>1時(shí)，令ys<ye，

則Δy=1，xi+1=xi+m－1。

DDA算法的C語言程序?qū)崿F(xiàn)如下：

#include<stdio.h>

#include<graphics.h>

voidline_DDA(intxs，intys，intxe，intye，intc)

{

inti，x=xs，y=ys；

floatxIncrement，yIncrement，steps，dx=xe-xs，

dy=ye-ys；

steps=abs(dx)；

if(abs(dy)>abs(dx))steps=abs(dy)；

xIncrement=dx/steps；

yIncrement=dy/steps；

setPixel(x，y，c)；

for(i=1；i<=steps；i++)

{

x+=xIncrement；

y+=yIncrement；

setPixel(x，y，c)；

}

}算法將直線兩個(gè)端點(diǎn)的像素位置作為輸入，其過程可概括為：將端點(diǎn)位置的水平和垂直差賦給參數(shù)dx和dy，兩者中絕對(duì)值大者決定參數(shù)steps的值。從像素位置(xs，ys)

開始，確定沿直線生成下一個(gè)像素位置每步的所需偏移量，并循環(huán)上述過程steps次。

如果dx的絕對(duì)值大于dy的絕對(duì)值，那么x方向和y方向的增量分別為±1和±m(xù)；如果dy的絕對(duì)值大于dx的絕對(duì)值，那么y向和x方向的增量分別為±1和±m(xù)－1。3.1.3直線的Bresenham算法

DDA算法原理簡單、有效，利用顯示器的光柵特性，消除了直線方程中求點(diǎn)的乘法運(yùn)算，在x，y兩個(gè)方向使用合理的增量沿直線逐步求出各像素的位置。然而，浮點(diǎn)增量的連續(xù)迭加中取整誤差的累積會(huì)使長線段所計(jì)算的像素位置偏離實(shí)際線段，而且程序中的取整操作和浮點(diǎn)運(yùn)算仍然十分耗時(shí)。為此，這里我們討論生成直線的Bresenham算法。

Bresenham于1965年提出了一個(gè)只使用整數(shù)運(yùn)算的經(jīng)典算法（通常稱為Bresenham算法）。作為生成直線的最有效的算法之一，該算法根據(jù)前一個(gè)已計(jì)算的像素點(diǎn)(xi，yi)

進(jìn)行增量運(yùn)算得到下一個(gè)像素點(diǎn)(xi+1，yi+1)，而不必進(jìn)

行取整操作。該算法也可擴(kuò)充其浮點(diǎn)數(shù)功能以處理端點(diǎn)坐標(biāo)是任意實(shí)數(shù)的直線。為了說明算法原理，我們首先考慮斜率非負(fù)且不超過

1的直線的光柵化過程。設(shè)直線的起點(diǎn)和終點(diǎn)坐標(biāo)分別為(xs，ys)和(xe，ye)，則直線的方程為y=mx+b，其中

b=ye－mxe

由于0≤m≤1，所以當(dāng)直線光柵化時(shí)，x每次都增

加1，即xi+1=xi+1，而y的相應(yīng)增加值為m。為了光柵化，yi+1只能選擇yi或yi+1(圖3.3)。選擇的原則是看精確的y值與

yi及yi+1的距離d1和d2的大小。圖3.3縱坐標(biāo)的位置選擇由于

所以，如果d1(xi+1)－d2(xi+1)>0，則yi+1=yi+1，否則，yi+1=yi。因此，算法的關(guān)鍵在于如何簡便地求d1(xi+1)－d2(xi+1)的符號(hào)。因?yàn)榱頟i=(d1(xi+1)－d2(xi+1))dx，則有為了有效地計(jì)算決策函數(shù)Pi，我們需要建立一個(gè)關(guān)于

Pi的遞推公式。由Pi的定義可知為了確定決策函數(shù)Pi的初值P1，只需將直線的起點(diǎn)坐

標(biāo)(xs，ys)代入Pi的表達(dá)式中，并注意到0≤m≤1的假設(shè)，則有

P1=2dy－dx

綜上所述，滿足條件0≤m≤1的直線的Bresnham算法的步驟如下：

Step1初始化：

dx=xe－xs，dy=ye－ys，x=xs，

y=ys，P=2dy－dx；

Step3算法結(jié)束。

Brsenham算法的程序?qū)崿F(xiàn)如下：

#include<stdio.h>

#include<graphics.h>

voidline_BRES(intxs，intys，intxe，intye，intc){

intdx=xe-xs，dy=ye-ys，x=xs，y=ys；

inttwoDX=2*dx，twoDY=2*dy，P=2*dy-dx；

setPixel(x，y，Color)；

while(x<xe){

if(P>0){y++；P-=twoDX；}

x++；

P+=twoDY；

setPixel(x，y，c)；

}

}下面給出利用Bresenham算法畫連接P0(0，0)和P1(5，2)兩點(diǎn)的直線段的離散化結(jié)果，其結(jié)果如圖3.4所示。

上面討論的只是0≤m≤1的情形，考慮到xy平面各種八分和四分區(qū)域間的對(duì)稱性，可以知道Bresenham算法對(duì)于任意斜率的直線具有通用性。對(duì)于斜率為正且大于1的直線，即dy>dx>0，只要變換x和y的地位，即沿y方向以單位步長步進(jìn)并計(jì)算最接近直線的x值；若dy<0或dx<0，那么程序中的操作y++或x++則變成y－－或x－－。圖3.4Bresenham算法實(shí)例一般情況下，任意直線的Bresenham算法為：

#include<stdio.h>

#include<graphics.h>

voidBRES_line(intxs，intys，intxe，intye，intc)

{

intdx=abs(xe-xs)，dy=abs(ye-ys)，i，x=xs，y=ys；inttwoDX=2*dx，twoDY=2*dy，P=2*dy-dx；

ints1，s2，interchange=0，temp；

if(xe-xs>=0)

s1=1；

else

s1=-1；

if(ye-ys>=0)

s2=1；

else

s2=-1；

if(dy>dx)/*按照直線的斜率交換dx和dy*/

{

temp=dx；

dx=dy；

dy=temp；

interchange=1；

}

for(i=0；i<=dx；i++)

{

setPixel(x，y，c)；

if(P>0)

{if(interchange)

x+=s1；

else

{y+=s2；

P-=twoDX；

}

}

if(interchange)

y+=s2；

else

x+=s1；

P+=twoDY；

}

}

Bresenham算法的優(yōu)點(diǎn)有：

(1)不計(jì)算直線的斜率，因此不做除法運(yùn)算。

（2）不用浮點(diǎn)數(shù)，只用整數(shù)。

（3）只做整數(shù)的加法和減法運(yùn)算，而乘2運(yùn)算可以用移位操作實(shí)現(xiàn)。

（4）運(yùn)算速度快，便于硬件實(shí)現(xiàn)。通過對(duì)Bresenham算法進(jìn)一步優(yōu)化，減少算法中確定像素點(diǎn)的判定次數(shù)，即可得到增強(qiáng)的Bresenham算法——雙步算法，該改進(jìn)是由Wu和Rokne于1987年給出的。

Bresenham算法采用整數(shù)運(yùn)算，由點(diǎn)(xi，yi)計(jì)算出(xi+1，yi+1)，算法首先確定線段的斜率，再繼續(xù)在每一步中，通過判定函數(shù)在兩個(gè)可選的像素點(diǎn)中選出一個(gè)。雙步算法則在每一步都通過判定函數(shù)求得一對(duì)像素點(diǎn)而不只是一個(gè)像素點(diǎn)，如此繼續(xù)直至到達(dá)線段的終點(diǎn)。對(duì)當(dāng)前求得的像素點(diǎn)來說，隨后可能出現(xiàn)的一對(duì)像素點(diǎn)只有圖3.5所示的四種情況。圖3.5雙步算法中像素點(diǎn)的選擇

Wu證明對(duì)于一條線段，圖案1和圖案4不會(huì)同時(shí)出現(xiàn)。當(dāng)線段斜率大于1/2，圖案1不會(huì)出現(xiàn)；當(dāng)斜率小于1/2時(shí)，圖案4不會(huì)出現(xiàn)。因此，通過測(cè)試斜率，選擇將限定于1、2、3或2、3、4三種圖案中的一個(gè)。下面考察當(dāng)斜率在0到1/2之間的情形，此時(shí)可能出現(xiàn)的圖案是圖案1、圖案2和圖案3。為了確定像素點(diǎn)對(duì)，我們需要在圖案1、圖案2、圖案3中做出決定。判定變量P

置初值P=4dy－dx。于是每一次增量測(cè)試以是否P<0確定是否使用圖案1，即選擇像素點(diǎn)：(xi+1，yi)，(xi+2，yi)。如果P大于或等于0，則必須在圖案2和圖案3之間做出選擇。這是一個(gè)簡單的測(cè)試：當(dāng)P<2dy時(shí)選取圖案2，即選擇像素點(diǎn)：(xi+1，yi)，(xi+2，yi+1)。否則，選取像素點(diǎn)：(xi+1，yi+1)，(xi+2，yi+1)。為了有效地計(jì)算判定函數(shù)，同樣需要建立關(guān)于P的遞推公式：雙步算法的參考代碼如下：

voidline_DoubleStep(intxs，intys，intxe，intye，intColor)

{/*設(shè)0≤m≤1/2*/

intdx=xe-xs，dy=ye-ys，current_x=xs，y=ys；intincr_1=4*dy，incr_2=4*dy-2*dx，

P=4*dy-dx，cond=2*dy；

setPixel(current_x，y，Color)；

while(current_x<xe){

if(d<0){

setPixel(current_x+1，y，Color)；

setPixel(current_x+2，y，Color)；

P+=incr_1；

}

elseif(d<cond){

setPixel(current_x+1，y，Color)；

setPixel(current_x+2，y+1，Color)；

P+=incr_2；y++；

}

else{

setPixel(current_x+1，y+1，Color)；

setPixel(current_x+2，y+1，Color)；

P+=incr_2；y++；

}

current_x+=2；

}

}此外，還有利用中點(diǎn)法則進(jìn)行直線繪制的中點(diǎn)算法，其與Bresenham算法的區(qū)別在于構(gòu)造判定函數(shù)方法的不同。盡管如此，中點(diǎn)算法與Bresenham算法最終推導(dǎo)得到的判定函數(shù)遞推公式和初值表達(dá)形式卻是完全相同的。中點(diǎn)法是由Pitteway于1967年提出的，VanAken和另外的一些研究人員于1984年對(duì)其進(jìn)行了一些改進(jìn)。在生成直線的過程中，需另外考慮直線端點(diǎn)的順序問題，即畫一條從(xs，ys)到(xe，ye)的直線是否和畫一條從(xe，ye)到(xs，ys)的直線能夠生成相同的像素序列。從數(shù)學(xué)的角度來講，畫出的線應(yīng)該與線的端點(diǎn)順序無關(guān)。出現(xiàn)像素選擇依賴于線的方向的惟一情況是線正好穿過兩像素中間而決策函數(shù)是0。此時(shí)，從左向右掃描時(shí)會(huì)選擇當(dāng)前像素右側(cè)的像素，根據(jù)對(duì)稱性，如果是從右向左掃描，則選擇的是當(dāng)前像素左側(cè)的像素，而這樣選擇的像素就比從左向右掃描時(shí)所選擇的相應(yīng)像素在y方向上高出一個(gè)單位。因此，在從右向左掃描時(shí)，當(dāng)決策函數(shù)為0時(shí)應(yīng)該調(diào)整為選擇當(dāng)前像素左下位置的像素。

3.2圓的生成算法

圓是最基本的圖形之一，許多種場合都能用到它。因此，圖形軟件包都包含有生成圓和圓弧的程序，故生成圓的算法也很多。

圓心在(xc，yc)，半徑為R的圓的方程是

(x－xc)2+(y－yc)2=R2

顯然，利用該方程沿x軸從xc－R到xc+R以單位步長步進(jìn)計(jì)算出對(duì)應(yīng)的y值，即可得到圓周上每點(diǎn)的y值：但這并非是最好的算法。該算法每步包含了大量的計(jì)算，且所畫像素沿圓周分布不均勻。另外，|x－xc|越大，對(duì)應(yīng)生成圓周上的點(diǎn)之間的弧長也就越大。我們可以在圓的斜率絕對(duì)值大于1后，交換x和y來調(diào)整間距。這樣一來增加了所需的計(jì)算量和處理過程。另一種消除不等間距的方法是使用圓的極坐標(biāo)方程：

x=xc+Rcosθ，y=yc+Rsinθ

這種方法計(jì)算圓周上的點(diǎn)又涉及到三角運(yùn)算，同樣增加了計(jì)算量。3.2.1生成圓的Bresenham算法

Bresenham算法是畫圓的最有效的算法之一。不失一般性，設(shè)要畫圓的圓心在坐標(biāo)原點(diǎn)(0，0)，半徑為R。我們這里來討論第一象限的上半部的八分之一圓弧的生成過程，即圖3.6中的圓弧AB。如果要生成整圓，只需在顯示圓弧AB上任一點(diǎn)(x，y)的同時(shí)，顯示圓周上的另外七個(gè)點(diǎn)(x，－y)，(－x，y)，(－x，－y)，(y，x)，(y，－x)，(－y，x)和(－y，－x)。圖3.6圓的對(duì)稱性現(xiàn)在，從點(diǎn)(0，R)開始順時(shí)針生成八分之一圓周AB。在這種情況下，x每步增加1，即xi+1=xi+1，相應(yīng)的yi+1則有兩種選擇：yi+1=yi或yi－1。選擇的原則是考察精確值y是靠近yi還是靠近yi－1(圖3.7)。圖3.7yi+1的選擇準(zhǔn)則設(shè)Rs滿足方程：那么，以坐標(biāo)原點(diǎn)為圓心，Rs為半徑做圓弧S，上式表明點(diǎn)(xi+1，yi)和(xi+1，yi－1)到圓弧S的距離是相等的。因此，S可作為分界線。當(dāng)圓在S上方時(shí)，應(yīng)選yi+1=yi；當(dāng)圓在S下方時(shí)，應(yīng)選yi+1=yi－1(圖3.7)。下面建立判斷圓是在S上方或下方的決策函數(shù)。

令顯然，di是R的遞減函數(shù)。當(dāng)R=Rs時(shí)，di=0；當(dāng)R>Rs時(shí)，圓在S的上方，此時(shí)di<0；當(dāng)R<Rs時(shí)，圓在S的下方，此時(shí)di>0。由此，我們得到?jīng)Q策函數(shù)di。若di<0，則yi+1=yi；否則，yi+1=yi－1。接下來的問題是如何快速地計(jì)算決策函

數(shù)di。

已知x1=0，y1=R，所以因?yàn)樗曰谏鲜鐾茖?dǎo)，生成圓的Bresenham算法的步驟如下：

Step3若x=y，畫像素點(diǎn)(x，y)；

Step4算法結(jié)束。

下面給出利用Bresenham算法畫圓心為O(0，0)，半徑為R=10的八分之一圓弧離散化結(jié)果，如圖3.8所示。圖3.8Bresenham算法畫圓實(shí)例生成圓的Bresenham算法程序如下：

#include<stdio.h>

#include<graphics.h>

voidCircle_BRES(intxc，intyc，intRadius，intc){intx=0，y=Radius，d=3-2*Radius；

while(x<y)

{Plot_Circle_Point(xc，yc，x，y，c)；

If(d>=0)

{d+=4-4*y；

y--；

}

d+=4*x+6；

x++；

}

if(x==y)

Plot_Circle_Point(xc，yc，x，y，c)；

}子函數(shù)Plot_Circle_Point(xc，yc，x，y，c)的程序代碼如下：

voidPlot_Circle_Point(intxc，intyc，intx，inty，intc)

{

setPixel(xc+x，yc+y，c)；

setPixel(xc+x，yc-y，c)；

setPixel(xc-x，yc+y，c)；

setPixel(xc-x，yc-y，c)；

setPixel(xc+y，yc+x，c)；

setPixel(xc+y，yc-x，c)；

setPixel(xc-y，yc+x，c)；

setPixel(xc-y，yc-x，c)；

}圖3.9畫圓中點(diǎn)算法3.2.2生成圓的中點(diǎn)算法

Bresenham算法是畫圓的最有效的算法之一，其效率要高于基于圓的隱式方程和極坐標(biāo)方程的算法。對(duì)于圓心坐標(biāo)和半徑為整數(shù)的情況，運(yùn)用中點(diǎn)準(zhǔn)則可建立一個(gè)類似的算法，它能產(chǎn)生相同的一組優(yōu)化的像素。這里仍然考慮第一象限的上半部的八分之一圓弧的生成過程，并利用圓的對(duì)稱性畫出圓上其余的所有點(diǎn)。與畫直線的中點(diǎn)算法相似，這里所用的方法是：在2個(gè)像素之間的中點(diǎn)處給出一判定函數(shù)，并據(jù)此在2個(gè)像素中選擇最靠近圓的那個(gè)像素。如圖3.9所示，設(shè)函數(shù)F(x，y)=x2+y2－R2。對(duì)于圓上的點(diǎn)，此函數(shù)的值為0；對(duì)于圓內(nèi)的點(diǎn)，函數(shù)值為負(fù)；對(duì)于圓外的點(diǎn)，函數(shù)值則是正的。這樣，如果像素E和SE的中點(diǎn)M在圓外，則SE更靠近圓。相反，如果中點(diǎn)在圓內(nèi),則E更靠近圓。與畫直線類似，我們選擇像素的依據(jù)是判定函數(shù)d的值，即函數(shù)F(x，y)在中點(diǎn)處的值：如果di<0，就選擇像素E，并將當(dāng)前中點(diǎn)的x坐標(biāo)增加一個(gè)單位來得到下一個(gè)中點(diǎn)，從而得到：顯然，di+1=di+(2xi+3)，可得增量：ΔE=2xi+3。

如果di≥0，就選擇像素SE，而下一個(gè)中點(diǎn)是將當(dāng)前中點(diǎn)的x坐標(biāo)增加一個(gè)單位，y坐標(biāo)減少一個(gè)單位，從而得到：最后還需要確定判定函數(shù)d的初值。由于限定該算法處理的圓的半徑為整數(shù)，并只畫八分之一圓弧，因此，圓的起始像素是(0，R)，而下一個(gè)中點(diǎn)的位置是(1，

R－1/2)，因此實(shí)現(xiàn)該算法的程序結(jié)構(gòu)與畫直線的算法很相似：

voidCircle_Midpoint(intradius，intColor)

{

intx，y；

floatd；

x=0；y=radius；d=5.0/4-radius；

Plot_Circle_Point(0，0，x，y，Color)；

while(x<y){

if(d<0){d+=x*2.0+3；}

else{d+=(x-y)*2.0+5；y--；}

x++；

PlotCirclePoint(0，0，x，y，Color)；

}

}上述算法的不足是由于判定函數(shù)d的初值是浮點(diǎn)數(shù)，因此算法必須做浮點(diǎn)數(shù)的算術(shù)運(yùn)算。我們希望有一個(gè)效率更高的且只進(jìn)行整數(shù)運(yùn)算的算法。為此，定義一個(gè)新的判定函數(shù)：h=d－1/4。這樣在初始化時(shí)，h=1－R，而條件d<0變成了h<－1/4。由于h的初值是整數(shù)，且其相應(yīng)的增量也是整數(shù)，因此可將條件h<－1/4改為h<0。這樣算法就變成了關(guān)于h的只進(jìn)行整數(shù)運(yùn)算的形式。為了與畫直線算法保持一致性，仍然用d表示決策函數(shù)。改進(jìn)后的算法如下所示：

voidCircle_Midpoint_Integer(intradius，intColor)

{

intx，y，d；

x=0；y=radius；d=1-radius；

Plot_Circle_Point(0，0，x，y，Color)；

while(x<y){

if(d<0){d+=x*2+3；}

else{d+=(x-y)*2+5；y--；}

x++；

Plot_Circle_Point(0，0，x，y，Color)；

}

}圖3.10給出利用中點(diǎn)算法畫圓心為O(0，0)，半徑為R=10的八分之一圓弧數(shù)值結(jié)果。

對(duì)上述增量計(jì)算方法進(jìn)一步拓展可改善畫圓的中點(diǎn)算法效率。由于任意一個(gè)多項(xiàng)式都可以按增量方式進(jìn)行計(jì)算，即利用了差分算法。差分的基本思想是計(jì)算函數(shù)在其相鄰兩個(gè)點(diǎn)上的值以及這兩個(gè)值的差。對(duì)于中點(diǎn)畫圓算法，在當(dāng)前的迭代中，如果選擇了E，則估值點(diǎn)從(xi，yi)變化到(xi+1，yi)。顯然，在點(diǎn)

(xi，yi)處的一階差分為ΔEold=2xi+3。因此，在點(diǎn)(xi+1，yi)處的一階差分為ΔEnew=2(xi+1)+3，其二階差分為ΔEnew－ΔEold=2。類似地，在點(diǎn)(xi，yi)處，ΔSEold=2xi－2yi+5；在點(diǎn)(xi+1，yi)處，ΔSEnew=2(xi+1)－2yi+5，因此二階差分為ΔSEnew－ΔSEold=2。如果在當(dāng)前的循環(huán)中選擇了SE，則估值點(diǎn)從(xi，yi)變化到(xi+1，yi－1)。因此，在點(diǎn)(xi+1，yi－1)處的一階差

分為ΔEnew=2(xi+1)+3，而二階差分為ΔEnew－ΔEold=2。

同樣，在點(diǎn)(xi+1，yi－1)處，ΔSEnew=2(xi+1)－2(yi－1)

+5，而相應(yīng)的二階差分ΔSEnew－ΔSEold=4。于是，改進(jìn)后的算法包括以下幾個(gè)步驟：①根據(jù)上次循環(huán)所計(jì)算的判定函數(shù)d的值的符號(hào)選擇一個(gè)像素；②運(yùn)用上次循環(huán)所計(jì)算的相關(guān)ΔE或ΔSE對(duì)判定函數(shù)d的值進(jìn)行修改；③根據(jù)像素的移動(dòng)情況，用前面計(jì)算的差分常量修改ΔE或ΔSE；④移動(dòng)像素。差分ΔE或ΔSE使用起始像素進(jìn)行初始化。改進(jìn)后的程序如下所示：

voidCircle_Midpoint_Difference(intradius，intColor)

{

intx，y，d，deltaE，deltaSE；

x=0；y=radius；d=1-radius；deltaE=3；deltaSE=5-radius*2；

PlotCirclePoint(0，0，x，y，Color)；

while(x<y){

if(d<0){

d+=deltaE；deltaE+=2；deltaSE+=2；

}

else{

d+=deltaSE；deltaE+=2；deltaSE+=4；y--；}

x++；

Plot_Circle_Point(0，0，x，y，Color)；

}

}3.2.3生成圓的正負(fù)法

設(shè)要繪制的圓的圓心在(xc，yc)，半徑為R，令

Fcircle(x，y)=(x－xc)2+(y－yc)2－R2

則圓將平面分為三個(gè)區(qū)域：我們以第一象限的四分之一圓弧為例，說明正負(fù)法的原理。取P0(x0，y0)=(xc，yc+R)，求得點(diǎn)Pi(xi，yi)后，

尋找Pi+1(xi+1，yi+1)的原則是：當(dāng)Fcircle(xi，yi)≤0時(shí)，xi+1=xi+1，yi+1=yi；當(dāng)Fcircle(xi，yi)>0時(shí)，xi+1=xi，yi+1=yi－1。因此，由Pi(xi，yi)和Fcircle(xi，yi)求Fcircle(xi+1，yi+1)的遞推公式為顯示初值點(diǎn)為(xc，yc+R)取在圓周上，則決策函數(shù)的初值為Fcircle=0。下面是基于上述遞推公式設(shè)計(jì)的生成圓的實(shí)現(xiàn)程序：

#include<stdio.h>

#include<graphics>

voidCircle_PNM(intxCenter，intyCenter，int

Radius，intc)

{

intx=xCenter，y=yCenter+Radius；

intf=0；

while(y>yCenter)

{

setPixle(x，y，c)；

if(f>0)

{

f+=2*(yCenter-y)+1；

y--；

}

else

{

f+=2*(x-xCenter)+1；

x++；

}

}

if(y==yCenter)setPixel(x，y，c)

}3.2.4生成圓的多邊形逼近法

方法1（基于圓的極坐標(biāo)表示）:

設(shè)圓的內(nèi)接多邊形的第i個(gè)頂點(diǎn)是Pi(xi，

yi)，CPi的幅角是θi，則：設(shè)多邊形每條邊所對(duì)應(yīng)的圓心角為α，那么下一個(gè)頂點(diǎn)Pi+1(xi+1，yi+1)的坐標(biāo)是：采用矩陣表示，則有式（3.7）可用于高速繪圖機(jī)繪圖。用兩個(gè)微處理器作管道式處理，前一個(gè)計(jì)算正多邊形的頂點(diǎn)，后一個(gè)只生成直線。如果不考慮繪圖機(jī)筆架運(yùn)動(dòng)的加速度的限制，繪制半徑為R的圓幾乎和繪一條長為2πR的直線花的時(shí)間同樣。該方法亦可用于橢圓內(nèi)接多邊形的計(jì)算。設(shè)橢圓的長短半軸分別為a和b，中心點(diǎn)坐標(biāo)為C(xc，yc)，對(duì)稱軸平行于坐標(biāo)軸，則該橢圓的參數(shù)方程是

x－xc=acosθ，y－yc=bsinθ

設(shè)橢圓的內(nèi)接多邊形的第i個(gè)頂點(diǎn)為Pi(xi，yi)，CPi的幅角是θi，其中：

xi－xc=acosθi，yi－yc=bsinθi

那么，第i+1個(gè)頂點(diǎn)Pi+1(xi+1，yi+1)的坐標(biāo)滿足：

xi+1－xc=acos（θi+α），yi+1－yc=bsin（θi+α）

由此可得(3.8)(3.9)上式便是計(jì)算橢圓的內(nèi)接多邊形頂點(diǎn)的遞推公式。如果對(duì)由式（3.8）生成的橢圓作旋轉(zhuǎn)β角或縮放變換，則要分別用變換矩陣如果兩個(gè)變換同時(shí)都做，則變換矩陣為這兩個(gè)矩陣的乘積T=TR·TS。這時(shí)，只要用TMT－1代替式（3.8）中的M，便可得到變換后的橢圓內(nèi)接多邊形的頂點(diǎn)坐標(biāo)。在第五章中可以看到式（3.8）可由式（3.7）經(jīng)過縮放變換求得。(3.11)圖3.11式（3.10)的幾何意義式（3.11）還可以寫成更一般的形式：(3.12)其中k為常數(shù)。當(dāng)k>1時(shí)，由其求出的點(diǎn)列{(xi，yi)}位于一支雙曲線上。因而，式（3.12）可用于雙曲線的繪制。3.2.5多邊形逼近算法穩(wěn)定性分析

這里對(duì)遞推公式（3.7）作關(guān)于初始誤差的穩(wěn)定性分析。設(shè)在初始真值(x0，y0)上附加誤差E0=(ex，ey)，此真值則變成為有誤差的初值，即：在求解過程中，假設(shè)計(jì)算是精確的，因而假設(shè)真值(xi，yi)也滿足式（3.7），即可令則有其中，矩陣它的特征值為λ1=cosα+isinα，λ2=cosα－isinα，所以存在二階方陣U，使得UAU－1為對(duì)角陣，則：(3.14)利用遞推公式（3.7）求圓的內(nèi)接多邊形的頂點(diǎn)時(shí)，為了減少計(jì)算工作量，可以以近似的方式計(jì)算三角函數(shù)cosα和sinα。例如，用Taylor級(jí)數(shù)的前n項(xiàng)來代替，cosα≈1，sinα≈α，這樣近似后式（3.7）則成為：也可近似用這樣則有：這兩種方法均不能精確地求出圓內(nèi)接多邊形的頂點(diǎn)，α取得越小，誤差就越小。3.2.6生成橢圓的正負(fù)法

下面我們僅討論橢圓曲線的生成問題。

這種方法不失一般性，我們假定橢圓的中心在坐標(biāo)原點(diǎn)，長半軸為a，短半軸為b，則橢圓的方程是：令Fellipse(x，y)=b2x2+a2y2－a2b2，則該函數(shù)具有以下

特性：因此，將函數(shù)Fellipse(x，y)作為正負(fù)法的決策函數(shù)。已知當(dāng)前一個(gè)像素點(diǎn)(xi，yi)，下一個(gè)像素點(diǎn)(xi+1，yi+1)的選擇依照決策函數(shù)，其規(guī)則如下：從(x1，y1)=(0，b)開始，依次對(duì)橢圓進(jìn)行采樣，繪制四分之一橢圓。顯然

Fellipse(x1，y1)=0

即是決策函數(shù)的初值。為了快速求出決策函數(shù)值，我們建立決策函數(shù)的遞推公式。

由于

Fellipse(xi+1，yi+1)=b2xi2+1+a2y2i+1－a2b2

分兩種情況予以討論。3.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充

3.3.1多邊形的掃描轉(zhuǎn)換

1.什么是多邊形的掃描轉(zhuǎn)換

在光柵圖像表示方法中，像素是構(gòu)成圖像的基本單位，如圖3.12。圖3.12圖像的表示對(duì)于給定的圖像，可以將它光柵化為一系列像素點(diǎn)的集合來表示，稱之為光柵圖形表示方法。當(dāng)然也可以用矢量圖形表示方法來表示同一圖像，在矢量圖形表示方法中，頂點(diǎn)和線是構(gòu)成圖像的兩個(gè)主要要素，這里的線包括直線和曲線，通常它們都有顯式的數(shù)學(xué)表達(dá)形式。一般情況下，這些線可以是曲線段，或者由Bézier曲線等復(fù)雜曲線構(gòu)成，但更多情況下是由直線段構(gòu)成的。因?yàn)榍€可以在特定誤差范圍內(nèi)由一系列直線段逼近得到，這種情形下矢量圖形的基本構(gòu)成單位就變?yōu)槎噙呅瘟?。在?jì)算機(jī)圖形學(xué)中，多邊形有兩種表示方法：頂點(diǎn)表示和點(diǎn)陣表示。頂點(diǎn)表示是用多邊形的頂點(diǎn)序列來刻畫多邊形。這種方法直觀、幾何意義強(qiáng)、占用內(nèi)存少、使用普遍。但由于它沒有明確指出哪些像素點(diǎn)在多邊形內(nèi)，故不能直接用于面著色。

點(diǎn)陣表示是用位于多邊形內(nèi)的像素點(diǎn)的集合來刻畫多邊形。這種方法雖然失去了許多重要的幾何信息，但便于運(yùn)用幀緩沖器表示圖形，是面著色所需要的圖形表示形式。光柵圖形系統(tǒng)的基本問題之一就是掃描轉(zhuǎn)換，根據(jù)圖像的表示方法它可以分為兩種情況。一種是光柵化過程，也就是將由圍線構(gòu)成的圖像轉(zhuǎn)換為由像素點(diǎn)構(gòu)成的光柵圖像，或者填充圍線內(nèi)部的區(qū)域，即區(qū)域填充。另一種是矢量化過程，包括將光柵圖形表示為矢量圖形，或者對(duì)圖像

進(jìn)行分割并檢測(cè)其中的圍線等。這一小節(jié)主要討論多邊形的掃描轉(zhuǎn)換，即把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)像素點(diǎn)，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色。

2.逐點(diǎn)判斷算法

實(shí)現(xiàn)多邊形的掃描轉(zhuǎn)換最簡單的方法就是逐點(diǎn)判斷，即逐個(gè)像素判斷，以確定它們是否在多邊形內(nèi)，從而給出位于多邊形內(nèi)的像素集合。

確定一個(gè)點(diǎn)是否在多邊形內(nèi)一般用累計(jì)交點(diǎn)的方法。若從一點(diǎn)發(fā)出的射線與多邊形邊界的交點(diǎn)數(shù)目為奇數(shù)，則該點(diǎn)位于多邊形內(nèi)，否則該點(diǎn)位于多邊形外。設(shè)P=p0p1…pnp0為一給定的多邊形，序列p0p1…pnp0是多邊形的頂點(diǎn)表示。設(shè)inside(P，x，y)是驗(yàn)證點(diǎn)(x，y)是否在多邊形P內(nèi)的布爾函數(shù)。當(dāng)從(x，y)到(+∞，y)的射線與

P的交點(diǎn)個(gè)數(shù)是奇數(shù)時(shí)，該函數(shù)取值1，否則取值0。設(shè)PolygonColor是多邊形P的顏色值，BackgroundColor為屏幕的背景色。

3.掃描線算法

1）區(qū)域的連貫性

設(shè)多邊形P的頂點(diǎn)pi=(xi，yi)，i=0，1，…，n的縱坐標(biāo)y的非遞增序列為：

yi0，yi1，…，yin

(3.15)

即

yik≥yik+1，0≤k≤n－1

(3.16)這樣，當(dāng)yik>yik+1，0≤k≤n－1時(shí)，屏幕上位于

y=yik和y=yik+1兩條掃描線之間的長方形區(qū)域（簡記為

{yik，yik+1}）被多邊形P的邊分割成若干個(gè)梯形（三角形

可看做一底邊長為0的梯形），它們具有以下性質(zhì)：（1）梯形的兩底邊分別在y=yik和y=yik+1兩條掃描線上，腰在多邊形P的邊上或在屏幕的邊界上，如圖3.13

所示。

（2）這些梯形可分為兩類：一類位于多邊形P的內(nèi)部，另一類位于多邊形P的外部。

（3）兩類梯形在長方形區(qū)域{yik，yik+1}內(nèi)相間排列，即相鄰的兩個(gè)梯形必有一個(gè)在P內(nèi)，另一個(gè)在P外。

2）掃描線的連貫性

設(shè)e為整數(shù)，且yi0≥e≥yin，若掃描線y=e與多邊形P的邊pi－1pi相交，其交點(diǎn)橫坐標(biāo)記為xei。設(shè)

xei1，xei2，…，xeil

(3.17)

是掃描線y=e與P的邊界各交點(diǎn)橫坐標(biāo)的遞增序列，稱為交點(diǎn)序列。那么，由區(qū)域的連貫性可知，交點(diǎn)序列具有下列性質(zhì)：（1）l是偶數(shù)。

（2）在該掃描線上，只有區(qū)段(xeik，xeik+1)，k=1，3，5，…，l－1，位于多邊形P內(nèi)，而其余區(qū)段在多邊形P外。

上述性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。

3）邊的連貫性

設(shè)d=e－1滿足條件yi0≥d≥yin，且位于掃描線y=d上的交點(diǎn)序列為

xdj1，xdj2，…，xdjh

(3.18)現(xiàn)考察交點(diǎn)序列（3.18）和（3.17）之間的關(guān)系。若

多邊形P的邊pr－1pr與掃描線y=e，y=d都相交，那么序列（3.17）和（3.18）中對(duì)應(yīng)元素xer，xdr滿足下列關(guān)系：(3.19)這樣，運(yùn)用公式（3.21）可直接由序列（3.18）求得序列（3.17）。

4）奇點(diǎn)處理

當(dāng)掃描線與多邊形P的邊界的交點(diǎn)是P的頂點(diǎn)時(shí)，則稱該交點(diǎn)為奇點(diǎn)。上述多邊形的三種形式的連貫性都是基于這樣的幾何事實(shí)：每一條掃描線與多邊形P的邊界的交點(diǎn)個(gè)數(shù)是偶數(shù)（包括零）。但是，如果把每一奇點(diǎn)簡單地記為一個(gè)交點(diǎn)，則交點(diǎn)個(gè)數(shù)可能出現(xiàn)奇數(shù)；同樣，若將每一奇點(diǎn)都簡單地記為兩個(gè)交點(diǎn)，亦會(huì)導(dǎo)致反常的結(jié)果。因此，奇點(diǎn)必須按不同的情況區(qū)別對(duì)待。多邊形P的頂點(diǎn)可分為兩類：極值點(diǎn)和非極值點(diǎn)。如果(yi－1－yi)(yi+1－yi)<0，則稱頂點(diǎn)pi(xi，yi)為P的非極值點(diǎn)，否則稱為P的極值點(diǎn)。

為了在算法中統(tǒng)一處理多邊形三種形式的連貫性，使每一條掃描線與P的邊界的交點(diǎn)個(gè)數(shù)保持為偶數(shù)，規(guī)定當(dāng)

奇點(diǎn)為P的極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。實(shí)際計(jì)算時(shí)，可在求交點(diǎn)以前，對(duì)多邊形頂點(diǎn)中的非極值點(diǎn)進(jìn)行預(yù)處理。即若Pi是非極值點(diǎn)，則將pi－1pi和pipi+1兩邊中位于掃描線y=yi上方的那條邊在Pi處沿縱向截

取一單位長，如圖3.14所示。這樣可保證掃描線y=yi只和

pi－1pi、pipi+1兩邊中的一邊相交，求得一個(gè)交點(diǎn)。圖3.14非極值點(diǎn)的預(yù)處理

5）掃描線算法的數(shù)據(jù)結(jié)構(gòu)

為了實(shí)現(xiàn)多邊形P的掃描轉(zhuǎn)換，首先對(duì)多邊形P的頂點(diǎn)的縱坐標(biāo)由大到小排序，得到一遞減序列：

yi0，yi1，…，yin

取d=yin，容易求得掃描線y=d上的交點(diǎn)序列：

xdj1，xdj2，…，xdjh

這一序列由位于掃描線y=d上的多邊形P的頂點(diǎn)組成。由上述序列開始即可根據(jù)多邊形的邊的連貫性和掃描

線的連貫性，按從下到上的順序求得各掃描線的交點(diǎn)序列，并確定各掃描線上位于多邊形P內(nèi)的區(qū)段，最后將多邊形P表示成點(diǎn)陣形式。此算法就是對(duì)多邊形作掃描轉(zhuǎn)換

的掃描線算法。邊的分類表ET和邊的活化鏈表AEL中的基本元素為多邊形的邊。邊結(jié)點(diǎn)的結(jié)構(gòu)如下：其中：ymax：邊的上端點(diǎn)y坐標(biāo)；

x：邊的下端點(diǎn)x坐標(biāo)，在AEL中表示邊與掃描線的交點(diǎn)x坐標(biāo)；

Δx：邊的斜率的倒數(shù)；

next：指向下一條邊的指針。邊的分類表ET是按邊的下端點(diǎn)縱坐標(biāo)y對(duì)非水平邊進(jìn)行分類的指針數(shù)組(Y桶分類)。下端點(diǎn)的縱坐標(biāo)y值等于i的邊歸入第i類，有多少條掃描線，就設(shè)多少類。同一類中，各邊按x值(x值相等時(shí)，按Δx的值)遞增的順序排列成行。例如，對(duì)于多邊形P=［p0p1…p6p0］=［(2，5)，

(2，10)，(9，6)，(16，11)，(16，4)，(12，2)，(7，2)，(2，5)］（圖3.15），其對(duì)應(yīng)的邊的分類表ET如圖3.16所示。這里已對(duì)非極值點(diǎn)p0

，

p4作了預(yù)處理，即

對(duì)邊e1、e4而言，下頂點(diǎn)的y坐標(biāo)分別為6和5，e6作為水平邊不參與分類。圖3.15多邊形P=［P0P1…P6P0圖3.16多邊形的邊分類表ET邊的活化鏈表AEL是由與當(dāng)前掃描線相交的所有多邊形的邊組成的一個(gè)鏈表。它記錄了多邊形沿掃描線的交點(diǎn)序列，并且根據(jù)邊的連貫性（式(3.19)）不斷地刷新交點(diǎn)序列。例如，圖3.15所給的多邊形對(duì)應(yīng)于不同掃描線，其AEL如圖3.17所示。圖3.17邊的分類表

6）算法步驟

建立了多邊形的分類表ET后，掃描線算法的實(shí)現(xiàn)步驟如下：

Step1(掃描線初始化)取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號(hào)。(對(duì)上述的多邊形，y=2)；

Step2(AEL初始化)將邊的活化鏈表AEL置為空表；Step3按從下到上的順序?qū)v坐標(biāo)值為y的掃描線執(zhí)行以下操作，直到邊的分類表ET和邊的活化鏈表AEL為空表為止。

（1）若邊的分類表ET中第y類元素非空，則將屬于該類的所有邊從ET中取出并插入到邊的活化鏈表AEL中。AET中的各邊按照x值(當(dāng)x值相等時(shí)，按Δx值)遞增的順序排序。（2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩配對(duì)。即第1、2邊為一對(duì)，第3、4邊為一對(duì)，依次類推。每一對(duì)邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)。依次對(duì)這些區(qū)段上的像素點(diǎn)按多邊形顏色著色。

（3）將邊的活化鏈表AEL中滿足條件ymax=y的邊刪去。（4）將邊的活化鏈表AEL中剩余的每一條邊的x域累加Δx，即x=x+Δx。

（5）將當(dāng)前掃描線的縱坐標(biāo)值y累加1，即y=y+1。

7）程序?qū)崿F(xiàn)

若采用C語言，那么邊結(jié)點(diǎn)的數(shù)據(jù)類型可說明如下：

structtEdge{

intyUpper；

floatxIntersect，dxPerScan；

structtEdge*next；

}Edge；

#include<stdio.h>

#inclide<graphics.h>

voidinsertEdge(Edge*list，Edge*edge)/*鏈表插入*/

{Edge*p，*q=list；

p=q->next；

while(p!=NULL)

{if(edge->xIntersect<p->xIntersect)

p=NULL；

else

{q=p；

p=p->next；

}

}

edge->next=q->next；

q->next=edge；

}

intyNext(intk，intcount，int*y)

/*求下一條非水平邊的y坐標(biāo)*/

{intj；

if((k+1)>(count-1))

j=0；

else

j=k+1；

while(y［k］==y［j］)

if((j+1)>(count-1))

j=0；

else

j++；

return(y［j］)；

}

voidmakeEdgeRecord(intxLower，intyLower，intxUpper，intyUpper，intyComp，

Edge*edge，Edge*edges［］)/*建立邊結(jié)點(diǎn)*/

{edge->dxPerScan=(float)(xUpper-xLower)/(yUpper-yLower)；

edge->yUpper=yUpper；

if(yLower>yComp)

{edge->yLower=yLower+1；

edge->xIntersect=xLower+edge->dxPerScan；

}

else

edge->xIntersect=xLower；

insertEdge(edges［yLower］，edge)；

}

voidbuildEdgeList(intcount，int*x，int*y，Edge*edges［］)/*建立邊表*/

{Edge*edge；

intx1，y1，x2，y2；

inti，yPrev=y［count-2］；

x1=x［count-1］；y1=y［count-1］；

for(i=0；i<count；i++)

{x2=x［i］；y2=y［i］；

if(y1!=y2)/*非水平邊*/

{edge=(Edge*)malloc(sizeof(Edge))；

if(y1<y2)

makeEdgeRecord(x2，y2，x1，y1，yNext(i，count，y)，edge，edges)；

else

makeEdgeRecord(x1，y1，x2，y2，yPrev，edge，edges)；

}

yPrev=y1；

x1=x2；y1=y2；

}

}

voidbuildActiveList(intscan，Edge*active，Edge*edges［］)/*建立活化鏈表*/

{Edge*p，*q；

p=edges［scan］->next；

while(p)

{q=p->next；

insertEdge(active，p)；

p=q；

}

}

voidfillScan(intscan，Edge*active)/*填充當(dāng)前掃描線*/{Edge*p1，*p2；

inti

p1=active->next；

while(p1)；

{p2=p1->next；

for(i=p1->xIntersect；i<p2->xIntersect；i++)

setPixel(i，scan，PolygonColor)；

p1=p2->next；

}

}

voiddeleteAfter(Edge*q)/*刪除已處理過的邊*/

{Edge*p=q->next；

q->next=p->next；

free(p)；

}

voidupdateActiveList(intscan，Edge*active)/*修改活化鏈表*/

{Edge*q=active，*p=active-next；

while(p)

if(scan>=p->yUpper)

{p=p->next；

deleteAfter(q)；

}

else

{p->xIntersect=p->xIntersect+p->dxPerScan；

q=p；

p=p->next；

}

}

voidresortActiveList(Edge*active)/*活化鏈表排序*/

{Edge*q，*p=active->next；

while(p)

{q=p->next；

insertEdge(active，p)；

p=q；

}

}

voidscanFillPolygon(intcount，int*x，int*y)/*多邊形掃描轉(zhuǎn)換*/

{Edge*edges［YMAX］，*active；

inti，scan；

for(i=0；i<YMAX；i++)

{edges［i］=(Edge*)malloc(sizeof(Edge))；

edges［i］->next=NULL；

}

buildEdg