《計算機圖形學(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è)備級算法。對此，假定物體的位置直接以整數(shù)坐標(biāo)給出，像素位置按照掃描線行數(shù)和列數(shù)指定，其編址方案如圖3.1所示。掃描線從屏幕底部由零開始編號，像素列則沿每條掃描線從左至右由零開始編號，每個像素區(qū)域由左下角的整數(shù)網(wǎng)格坐標(biāo)來指定。圖3.1光柵顯示器編址為了將對應(yīng)于沿掃描線y的列x的位置上指定顏色裝入幀緩沖器，我們假設(shè)有以下形式的底層函數(shù)：

setPixel(x，y，c)

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

getPixel(x，y)

3.1直線的生成算法

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

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

（1）直線是直的、光滑的，且具有精確的起點和

終點。

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

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

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

yi+1=yi+m

(3.3)

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

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

xi+1=xi+m－1

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

yi+1=yi－m

(3.5)

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

xi+1=xi－m－1

(3.6)

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

xs<xe，則Δx=1，yi+1=yi+m；當(dāng)|m|>1時，令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)；

}

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

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

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

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

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

進行增量運算得到下一個像素點(xi+1，yi+1)，而不必進

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

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

b=ye－mxe

由于0≤m≤1，所以當(dāng)直線光柵化時，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)的符號。因為令Pi=(d1(xi+1)－d2(xi+1))dx，則有為了有效地計算決策函數(shù)Pi，我們需要建立一個關(guān)于

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

標(biāo)(xs，ys)代入Pi的表達式中，并注意到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)兩點的直線段的離散化結(jié)果，其結(jié)果如圖3.4所示。

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

(1)不計算直線的斜率，因此不做除法運算。

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

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

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

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

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

置初值P=4dy－dx。于是每一次增量測試以是否P<0確定是否使用圖案1，即選擇像素點：(xi+1，yi)，(xi+2，yi)。如果P大于或等于0，則必須在圖案2和圖案3之間做出選擇。這是一個簡單的測試：當(dāng)P<2dy時選取圖案2，即選擇像素點：(xi+1，yi)，(xi+2，yi+1)。否則，選取像素點：(xi+1，yi+1)，(xi+2，yi+1)。為了有效地計算判定函數(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；

}

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

3.2圓的生成算法

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

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

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

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

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

這種方法計算圓周上的點又涉及到三角運算，同樣增加了計算量。3.2.1生成圓的Bresenham算法

Bresenham算法是畫圓的最有效的算法之一。不失一般性，設(shè)要畫圓的圓心在坐標(biāo)原點(0，0)，半徑為R。我們這里來討論第一象限的上半部的八分之一圓弧的生成過程，即圖3.6中的圓弧AB。如果要生成整圓，只需在顯示圓弧AB上任一點(x，y)的同時，顯示圓周上的另外七個點(x，－y)，(－x，y)，(－x，－y)，(y，x)，(y，－x)，(－y，x)和(－y，－x)。圖3.6圓的對稱性現(xiàn)在，從點(0，R)開始順時針生成八分之一圓周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)原點為圓心，Rs為半徑做圓弧S，上式表明點(xi+1，yi)和(xi+1，yi－1)到圓弧S的距離是相等的。因此，S可作為分界線。當(dāng)圓在S上方時，應(yīng)選yi+1=yi；當(dāng)圓在S下方時，應(yīng)選yi+1=yi－1(圖3.7)。下面建立判斷圓是在S上方或下方的決策函數(shù)。

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

數(shù)di。

已知x1=0，y1=R，所以因為所以基于上述推導(dǎo)，生成圓的Bresenham算法的步驟如下：

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

Step4算法結(jié)束。

下面給出利用Bresenham算法畫圓心為O(0，0)，半徑為R=10的八分之一圓弧離散化結(jié)果，如圖3.8所示。圖3.8Bresenham算法畫圓實例生成圓的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畫圓中點算法3.2.2生成圓的中點算法

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

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

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

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給出利用中點算法畫圓心為O(0，0)，半徑為R=10的八分之一圓弧數(shù)值結(jié)果。

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

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

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

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

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

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

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

尋找Pi+1(xi+1，yi+1)的原則是：當(dāng)Fcircle(xi，yi)≤0時，xi+1=xi+1，yi+1=yi；當(dāng)Fcircle(xi，yi)>0時，xi+1=xi，yi+1=yi－1。因此，由Pi(xi，yi)和Fcircle(xi，yi)求Fcircle(xi+1，yi+1)的遞推公式為顯示初值點為(xc，yc+R)取在圓周上，則決策函數(shù)的初值為Fcircle=0。下面是基于上述遞推公式設(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個頂點是Pi(xi，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.逐點判斷算法

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

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

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

3.掃描線算法

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

設(shè)多邊形P的頂點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時，屏幕上位于

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

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

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

所示。

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

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

2）掃描線的連貫性

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

xei1，xei2，…，xeil

(3.17)

是掃描線y=e與P的邊界各交點橫坐標(biāo)的遞增序列，稱為交點序列。那么，由區(qū)域的連貫性可知，交點序列具有下列性質(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上的交點序列為

xdj1，xdj2，…，xdjh

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

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

4）奇點處理

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

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

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

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

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

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

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

yi0，yi1，…，yin

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

xdj1，xdj2，…，xdjh

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

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

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

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

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

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

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

，

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

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

6）算法步驟

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

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

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

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

（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é)點的數(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é)點*/

{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