第三章 二維圖形的生成-直線和圓

2023/2/5西安工程大學計算機圖形學1第四章、二維圖形的生成和變換4.1、直線段的掃描轉(zhuǎn)換算法

4.1.1、DDA算法

4.1.2、中點畫線法

4.1.3、Bresenham畫線算法4.2、圓弧掃描轉(zhuǎn)換算法

4.2.1、中點算法

4.2.2、Bresenham畫圓算法

4.2.3、生成圓弧的正負法4.3、橢圓弧生成算法

2023/2/5西安工程大學計算機圖形學2對一維圖形，不考慮線寬，則用一個像素寬的直線來顯示圖形。二維圖形的光柵化，即區(qū)域的填充：確定像素集，填色或圖案。任何圖形的光柵化，必須顯示在一個窗口內(nèi)，否則不予顯示。即確定一個圖形的哪些部分在窗口內(nèi)，哪些在窗口外，即裁剪。 圖形的掃描轉(zhuǎn)換（光柵化）：確定一個像素集合，用于顯示一個圖形的過程。步驟如下：1、確定有關像素2、用圖形的顏色或其它屬性，對像素進行寫操作2023/2/5西安工程大學計算機圖形學3圖形顯示前需要：掃描轉(zhuǎn)換+裁剪裁剪---〉掃描轉(zhuǎn)換：最常用，節(jié)約計算時間。掃描轉(zhuǎn)換---〉裁剪：算法簡單；2023/2/5西安工程大學計算機圖形學4圖形顯示器是由一個個排列有序的像素構(gòu)成，劃分的像素點越多分辨率就越高。例如640X480的顯示器，分成640X480個網(wǎng)格，網(wǎng)格單元視為像素，一條線段就是由一些連續(xù)可見的像素所組成，如下圖所示：4.1直線段的掃描轉(zhuǎn)換算法在數(shù)學上，理想的直線是沒有寬度的，是由無數(shù)個在它上面的點構(gòu)成的集合。直線可以向一個方向及其相反的方向無限延長。在圖形學中研究的對象是直線段，它是一條具有一個Pixel或多個Pixel寬的直線段。2023/2/5西安工程大學計算機圖形學5由上圖可知：畫一條直線實際上就是根據(jù)一系列計算出來并與該直線靠近的像素繪制的。Line:P0(0,0)——P1(5,2)0143215234各行各列像素中心構(gòu)成的一組虛擬網(wǎng)格線像素單元4.1直線段的掃描轉(zhuǎn)換算法0123456701234562023/2/5西安工程大學計算機圖形學6直線的掃描轉(zhuǎn)換:確定最佳逼近于該直線的一組象素，并且按掃描線順序，對這些象素進行寫操作。直線段是最基本的圖形，因此直線段生成的質(zhì)量好壞與速度快慢將直接影響整個圖形生成的質(zhì)量和速度。三個常用算法：數(shù)值微分法（DDA）中點畫線法Bresenham算法。4.1直線段的掃描轉(zhuǎn)換算法2023/2/5西安工程大學計算機圖形學74.1.1、數(shù)值微分法（ＤＤＡ）

假定直線的起點、終點分別為:(x0,y0),(x1,y1)，且都為整數(shù)。

柵格交點表示象素點位置(Xi+1,Yi+k)(Xi,Yi)●4.1直線段的掃描轉(zhuǎn)換算法●●●●●2023/2/5西安工程大學計算機圖形學8基本思想

已知直線L兩端點位P0(x0,y0),P1(x1,y1)4.1直線段的掃描轉(zhuǎn)換算法即可以通過x方向的增量Δx，計算y的增量Δy來生成直線。當?shù)?.1.1、數(shù)值微分法（ＤＤＡ）2023/2/5西安工程大學計算機圖形學9即：當x方向每遞增1像素，y方向遞增k(即直線斜率)；每次通過上式計算出（xi，yi）取整后輸出顯示器。注意上述分析的算法僅適用于k≤1的情形。在這種情況下，x每增加1,y最多增加1。4.1直線段的掃描轉(zhuǎn)換算法當?shù)?.1.1、數(shù)值微分法（ＤＤＡ）2023/2/5西安工程大學計算機圖形學10注：當時，必須把x,y位置互換，即利用遞推式，y每增加1，x相應增加。所以取和中較大者為步進方向，如下圖x為步進方向y為步進方向4.1直線段的掃描轉(zhuǎn)換算法2023/2/5西安工程大學計算機圖形學11012345321Line:P0(0,0)--P1(5,2)例：畫直線段P0(0,0)--P1(5,2)k=0.4

xy+k四舍五入int（y+0.5)0 0 01 0.4 02 0.8 1 3 1.2 14 1.6 25 2 24.1直線段的掃描轉(zhuǎn)換算法4.1.1、數(shù)值微分法（ＤＤＡ）2023/2/5西安工程大學計算機圖形學12voidDDALine(intx0,inty0,intx1,inty1,intcolor)

intx；

floatdx,dy,y,k; dx=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;xx1,x++)

putpixel(x,int(y+0.5),color); y=y+k;

4.1直線段的掃描轉(zhuǎn)換算法4.1.1、數(shù)值微分法（ＤＤＡ）2023/2/5西安工程大學計算機圖形學13增量算法：在一個迭代算法中，如果每一步的x、y值是用前一步的值加上一個增量來獲得，則稱為增量算法。DDA算法就是一個增量算法。4.1直線段的掃描轉(zhuǎn)換算法該算法的優(yōu)點是繪制實數(shù)直線效果好，誤差小。缺點是實現(xiàn)較復雜，不利于硬件實現(xiàn)。該算法涉及到實數(shù)乘除法運算，y與k必須用浮點數(shù)表示，而且每一步都要對y進行四舍五入后取整。4.1.1、數(shù)值微分法（ＤＤＡ）2023/2/5西安工程大學計算機圖形學144.1.2、中點畫線法原理：假定直線斜率0<K<1，且已確定點亮象素點P（Xp,Yp

）,則下一個與直線最接近的像素只能是P1點或P2點。設M為中點，Q為交點現(xiàn)需確定下一個點亮的象素是P1還是P2。P=(xp,yp)QP2P14.1直線段的掃描轉(zhuǎn)換算法M2023/2/5西安工程大學計算機圖形學15我們以M和Q的關系來判斷取P1還是P2當M在Q的下方->P2離直線更近更近->取P2。M在Q的上方->P1離直線更近更近->取P1M與Q重合，P1、P2任取一點。問題：如何判斷M與Q點的關系？P=(xp,yp)QP2P1M4.1直線段的掃描轉(zhuǎn)換算法4.1.2、中點畫線法2023/2/5西安工程大學計算機圖形學16∴欲判斷中點M點是在Q點上方還是在Q點下方，只需把M代入F(x,y),并檢查它的符號。P=(xp,yp)QP2P1M4.1直線段的掃描轉(zhuǎn)換算法4.1.2、中點畫線法

假設直線方程為：ax+by+c=0其中a=y0-y1,b=x1-x0,

c=x0y1-x1y02023/2/5西安工程大學計算機圖形學17當d=0，選P1或P2均可，約定取P1；P=(xp,yp)QP2P14.1直線段的掃描轉(zhuǎn)換算法4.1.2、中點畫線法構(gòu)造判別式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c當d<0，M在直線(Q點)下方，取右上方P2

；當d>0，M在直線(Q點)上方，取右方P1；能否采用增量算法呢？M2023/2/5西安工程大學計算機圖形學18情形1.若d0->M在直線上方->取P1;

此時再下一個象素的判別式為

d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp

+1)+b(yp

+0.5)+c+a=d+a；

即d的增量為a,QP2P14.1直線段的掃描轉(zhuǎn)換算法P=(xp,yp)M4.1.2、中點畫線法2023/2/5西安工程大學計算機圖形學19情形2.若d<0->M在直線下方->取P2;

此時再下一個象素的判別式為

d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp

+1)+b(yp+0.5)+c+a+b=d+a+b

；即d的增量為a＋bP=(xp,yp)QP2P14.1直線段的掃描轉(zhuǎn)換算法M4.1.2、中點畫線法2023/2/5西安工程大學計算機圖形學20

畫線從(x0,y0)開始，d的初值

d0=F(x0+1,y0+0.5)=a(x0

+1)+b(y0+0.5)+c=F(x0,y0)+a+0.5b=a+0.5b

由于只用d

的符號作判斷，為了只包含整數(shù)運算,可以用2d代替d來擺脫小數(shù)，提高效率。4.1直線段的掃描轉(zhuǎn)換算法即d0＝2*a+b

若d0

增量為2*a

若d<0

增量為2*(a+b)4.1.2、中點畫線法2023/2/5西安工程大學計算機圖形學21012345321例：用中點畫線法P0(0,0)

P1(5,2)

a=y0-y1=-2b=x1-x0=5

d0=2a+b=1

d1=2a=-4d2=2(a+b)=6

i

xi

yi

d

1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5

4.1直線段的掃描轉(zhuǎn)換算法4.1.2、中點畫線法2023/2/5西安工程大學計算機圖形學22中點畫線法voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x<x1){if(d<0){x++;y++;d+=d2;}else{x++;d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/4.1直線段的掃描轉(zhuǎn)換算法2023/2/5西安工程大學計算機圖形學234.1.3、直線的Bresenham算法4.1直線段的掃描轉(zhuǎn)換算法

算法原理：過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后確定該列象素中與此交點最近的象素。該算法的巧妙之處在于采用增量計算，使得對于每一列，只要檢查一個誤差項的符號，就可以確定該列的所求象素。2023/2/5西安工程大學計算機圖形學24

為了討論方便，我們假定直線的斜率在0~1之間，其它情況類似處理如右圖所示，設直線方程為其中k=dy/dx。

假設當前象素已經(jīng)確定為(xi,yi)那么下一個象素的列坐標為xi＋1，而行坐標要么不變?yōu)閥i，要么遞增1為yi＋1。

yx4.1直線段的掃描轉(zhuǎn)換算法4.1.3、直線的Bresenham算法則有2023/2/5西安工程大學計算機圖形學25

是否增1取決于如圖所示誤差項

d的值。因為直線的起始點在象素中心，所以誤差項

d的初值d0＝0

因為x每增加1，d的值相應遞增直線的斜率值

k，即d＝d＋k。1、當d≥0.5時，直線與xi＋1列垂直網(wǎng)格交點最接近的象素為右上方象素（xi+1，yi＋1）；2、當d<0.5時，更接近直線的為正右方象素（xi＋1，yi）。

4.1直線段的掃描轉(zhuǎn)換算法注：一旦y方向上走一步，d=d-1。2023/2/5西安工程大學計算機圖形學26為方便計算，令e＝d－0.5，e的初值為－0.5，增量為

k。結(jié)論：1.

d的初值d0＝0，d＝d＋k；2.當

d≥0.5時，下一個像素取為，右上方象素（xi+1，yi＋1）；3.當

d<0.5時，下一個像素取為

正右方象素（xi＋1，yi）。

2.當e<0時，更接近于正右方像素點（xi＋1，yi）。

圖-1

Bresenham算法誤差項的幾何含義}dy}d}d

x}d4.1直線段的掃描轉(zhuǎn)換算法

1.當e≥0時，取當前像素（xi，yi）的右上方像素點（xi＋1，yi＋1）；注：同前面一樣，y方向上走一步，e=e-1。

算法步驟：1.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值△x、△y、e=-0.5、x=x0、y=y0。3.繪制點(x,y)。4.e更新為e+k，判斷e的符號。若e>0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-1；否則(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復步驟3和4。否則結(jié)束。2023/2/5西安工程大學計算機圖形學28

舉例1:用Bresenham方法掃描轉(zhuǎn)換連接兩點P0（0,0）和P1（5,2）的直線段。斜率K=2/5=0.4e0=-0.5e=d-0.5,d=d+k,k=dy/dx當e≥0時，取當前像素的右上方像素為下一個像素當e<0時，取當前像素的正右方像素為下一個像素4.1直線段的掃描轉(zhuǎn)換算法0143215234x e ye-10－0.5 0 1－0.1 0 20.3 1－0.73－0.3 1 40.1 2－0.95－0.5 2 2023/2/5西安工程大學計算機圖形學29Bresenham畫線算法參考程序

(0<k<1)：voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,i;floatdx,dy,k,e;dx=x1-x0,dy=y1-y0,k=dy/dx;e=-0.5,x=x0,y=y0;

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

{putpixel(x,y,color);

x=x+1，e=e+k;

if(e>=0){y++,e=e-1;}

}

}4.1直線段的掃描轉(zhuǎn)換算法因為一旦y方向上走一步，就減去1。沒有擺脫浮點數(shù)計算2023/2/5西安工程大學計算機圖形學30

上述bresenham算法在計算誤差項與直線斜率時用到小數(shù)與除法?？梢愿挠谜麛?shù)以避免除法。由于算法中只用到誤差項的符號，因此可作如下替換：

改進的Bresenham畫線算法程序：4.1直線段的掃描轉(zhuǎn)換算法遞增量初始量原先即2023/2/5西安工程大學計算機圖形學31voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy,e;dx=x1-x0;dy=y1-y0;

e=-dx;

x=x0;y=y0;for(i=0;i<=dx;i++){putpixel(x,y,color)x++;e=e+2*dy；

if(e>=0){y++;e=e-2*dx;}

}}2023/2/5西安工程大學計算機圖形學32Bresenham算法的優(yōu)點是：1、不必計算直線之斜率，因此不做除法；2、不用浮點數(shù)，只用整數(shù)；3、只做整數(shù)加減法和乘2運算，而乘2運算可以用硬件移位實現(xiàn)。Bresenham算法速度很快，并適于用硬件實現(xiàn)。4.1直線段的掃描轉(zhuǎn)換算法4.1.3、直線的Bresenham算法2023/2/5西安工程大學計算機圖形學33(1)上述算法只對斜率在0~1之間的直線段生成適合，

當直線的斜率大于1時，算法應該如何改進?MaxxMaxy(0,0)(50,20)MaxyMaxx(0,0)(50,20)}d

}d

}d

}d

注意：此時d或e的增量為幾點討論和思考4.1直線段的掃描轉(zhuǎn)換算法2023/2/5西安工程大學計算機圖形學34for(i=0;i<=dy;i++){putpixel(x,y,color);y=y+1;e=e+k1;if(e>=0){x=x+1;e=e-1;}}}(2)Bresenham畫線算法參考程序

(k>1)：Bresenham_line(intx0,inty0,intx1,inty1,intcolor){intx,i,y;floatdx,dy,k,k1,e;dx=x1-x0;dy=y1-y0;k=dy/dx;k1=1/k;e=-0.5;x=x0;y=y0;4.1直線段的掃描轉(zhuǎn)換算法2023/2/5西安工程大學計算機圖形學35(3)根據(jù)上述的思想，我們?nèi)绾螌⑺惴〝U展到，任一八分圓坐標空間圖，從而形成一般Bresenham算法？

如下圖：4.1直線段的掃描轉(zhuǎn)換算法(4)適用于任意斜率的Bresenham直線生成算法程序示例2023/2/5西安工程大學計算機圖形學364.2圓的掃描轉(zhuǎn)換算法

下面僅以圓心在原點、半徑R為整數(shù)的圓為例，討論圓的生成算法。假設圓的方程為：

X2+Y2=R2

若圓心不在原點可以通過坐標變換畫出任意位置的圓。2023/2/5西安工程大學計算機圖形學374.2.1圓弧掃描算法

X2+Y2=R2

Y=Sqrt(R2-X2)在一定范圍內(nèi)，每給定一X值，可得一Y值。當X取整數(shù)時，Y須取整。缺點：浮點運算，開方，取整，不均勻。yx2023/2/5西安工程大學計算機圖形學384.2.2角度DDA法

xn+1=x

n+dx=x

n－

Rsind=x

n－

(y

n－y0)d

y

n+1=y

n+dy=y

n+Rcosd=y

n+(xn－x0)d

給定圓上的初始值x1，y1及d值后，即可以增量方式獲得圓周上的坐標，然后取整可得象素坐標。但要采用浮點運算、乘法運算、取整運算。圓的極坐標方程x=x0+Rcos

y=y0+Rsin求微分dx=－

Rsind

dy=Rcosd記

xn+1－xn

＝dx

yn+1－yn

＝dy2023/2/5西安工程大學計算機圖形學394.2.3中點畫圓法第二個8分圓P為當前點亮象素，那么，下一個點亮的象素可能是P1(Xp+1，Yp)或P2(Xp+1，Yp

－1)。MP1P2P（Xp

，Yp

）利用圓的對稱性，只須討論1/8圓。XYY=XY=-X2023/2/5西安工程大學計算機圖形學40構(gòu)造判別函數(shù)：

F（X，Y）=X2+Y2-R2

；若

F（X，Y）=0

則（X，Y）在圓上；

F（X，Y）<0

則（X，Y）在圓內(nèi)；

F（X，Y）>0

則（X，Y）在圓外。設M為P1、P2間的中點，M=(Xp+1,Yp-0.5)MP1P24.2.3中點畫圓法2023/2/5西安工程大學計算機圖形學41有如下結(jié)論：

F(M)<0

M在圓內(nèi)

取P1

F(M)>=0M在圓外

取P2為此，可采用如下判別式：

MP1P2P(xp,yp)4.2.3中點畫圓法2023/2/5西安工程大學計算機圖形學42

d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若d<0,則P1

為下一個象素，那么再下一個象素的判別式為

d1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2

=d+2xp+3

即d

的增量為2xp+3.MP1P2P(xp,yp)4.2.3中點畫圓法2023/2/5西安工程大學計算機圖形學43

若d>=0,則P2

為下一個象素，那么再下一個象素的判別式為：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2

=d+（2xp+3）+（-2yp+2）即d

的增量為2(xp-yp)+5.

d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2

即：d0=1.25-RMP1P2P2P(xp,yp)4.2.3中點畫圓法2023/2/5西安工程大學計算機圖形學44MidpointCircle(intr,intcolor){intx,y;floatd;x=0;y=r;d=1.25-r;putpixel(x,y,color);

while(x<y)

{

if(d<0){d+=2*x+3;x++；}else{d+=2*(x-y)+5;x++;y--;}putpixel(x,y,color);}}4.2.3中點畫圓法2023/2/5西安工程大學計算機圖形學45為了進一步提高算法的效率，可以將上面的算法中的浮點數(shù)改寫成整數(shù)，將乘法運算改成加法運算，即僅用整數(shù)實現(xiàn)中點畫圓法。使用e=d-0.25代替de0=1-R4.2.3中點畫圓法2023/2/5西安工程大學計算機圖形學46上述算法能否再改進呢？注意到d

的增量是x,y的線性函數(shù)，每當x遞增1，則d的增量遞增Δx=2每當y遞減1，則d的增量遞增Δy=2Δx初始值=3；Δy初始值=-2R+24.2.3中點畫圓法2023/2/5西安工程大學計算機圖形學47

本節(jié)介紹另一種常用的畫圓算法Bresenham算法.不失一般性，考慮圓心在原點，半徑為R的四分之一圓。?。?，R）為起點，按順時針方向生成圓。如下圖所示：（0，R）YXOR第一個4分圓

4.2.4Bresenham畫圓算法2023/2/5西安工程大學計算機圖形學48從這段圓弧的任意一點出發(fā)，按順時針方向生成圓時，為了最佳逼近該圓，下一個像素的取法只有三種可能的選擇：正右方像素，右下方像素和正下方像素。分別記為H、D和V。如下圖所示：(x,y)H(x+1,y)V(x,y-1)D(x+1,y-1)第一個4分圓下一像素的三個候選者（0，R）YXOR第一個4分圓

4.2.4Bresenham畫圓算法2023/2/5西安工程大學計算機圖形學49

這三個像素中，與理想圓弧最近者為所求像素。理想圓弧與這三個候選點之間的關系只有下列五種情形：1.H、D、V全在圓內(nèi)；

2.H在圓外,D、V在圓內(nèi)；

3.D在圓上,H在圓外,V在圓內(nèi);4.H、D、在圓外，V在圓內(nèi)；

5.H、D、V全在圓外；

(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大學計算機圖形學50

上述三點到圓心的距離平方與圓弧上一點到圓心的距離平方之差分別為：

與Bresenham直線掃描算法一樣，在選最佳逼近該圓的像素時，我們希望只判別誤差項的符號。

我們以△D的符號分為三種情況討論。DVOH△H△D△V幾何解釋如右圖，它們可以表示H，D，V離圓弧的遠近。2023/2/5西安工程大學計算機圖形學51情況（一）：

為了確定H和D哪個更接近于圓弧,令如果

,那么右下方像素D在圓內(nèi)，圓弧與候選點的關系只可能是1或2的情形。則這時最佳逼近圓弧的像素只能是H或D兩個像素之一。(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大學計算機圖形學521.若,則圓到正右方像素H的距離小于圓到右下方像素D的距離,此時應取H為下一個像素。2.若,則圓到右下方像素D的距離較小,故應取D為下一個像素。3.若,兩者均可取，約定取正右方像素H。下面來計算的值，此時只會出現(xiàn)情形1或2。(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)12354故可根據(jù)的符號，判斷應取H還是D對于情形2，H在圓外，D在圓內(nèi)，因此所以可以簡化為：2023/2/5西安工程大學計算機圖形學53(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大學計算機圖形學54(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)12354對于情形1，H、D都在圓內(nèi)，而在這段圓弧上，y是x的單調(diào)遞減函數(shù)，所以只能取H為下一個像素。且這時，因此有

：

與情形2的判別條件一致?？梢娫诘那闆r下，若，則應取H為下一像素，否則應取D為下一像素由上述討論可知：

當時，若，即,則取H，否則取D

如果,那么右下方像素D在圓外，圓弧與候選點的關系只可能是4或5的情形。則這時最佳逼近圓弧的像素只能是V或D兩個像素之一。2023/2/5西安工程大學計算機圖形學55情況（二）：

為了確定V和D哪個更接近于圓弧,令(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大學計算機圖形學561，當

，即時，應取右下方像素D；2，當，即時，應取正下方像素V；3，當時，二者均可取，我們約定取右下方像素D下面來計算的值，此時只會出現(xiàn)情形4或5。(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大學計算機圖形學57(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)12354先考慮情形4：由于D在圓外，V在圓內(nèi),所以則可以簡化為故在時可以根據(jù)

的符號，判斷取D或V

時,取D;當時取V2023/2/5西安工程大學計算機圖形學58(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)12354對于情形5，D、V都在圓外，顯然取V為下一個像素。此時

，所以

可見,在

時，當時,取D為下一像素，否則應取V為下一像素。由上述討論可知：2023/2/5西安工程大學計算機圖形學59情況（三）：此時

D恰好在圓上，故應取

D作為下一像素。(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大學計算機圖形學60

歸納上述3種情況的討論，可得計算下一個像素的算法：1、當

時，若，則取D，否則取V；2、當

時，若，則取H，否則取D；3、當時，取D。2023/2/5西安工程大學計算機圖形學61(x,y)(x+2,y-1)(x＋1,y-1)(x+2,y)

下面討論的增量算法。1、若下一像素取的是HH坐標為：其誤差項H(x+1,y)2023/2/5西安工程大學計算機圖形學62(x,y)(x+2,y-1)(x＋1,y-2)(x+2,y－2)2、若下一像素取的是DD坐標為：D(x+1,y－1)其誤差項2023/2/5西安工程大學計算機圖形學63(x,y)(x+1,y-1)(x,y-2)(x+1,y－2)3、若下一像素取的是VV坐標為：V(x,y－1)其誤差項2023/2/5西安工程大學計算機圖形學64Bresenham_Ciecle(intr,intcolor){intx,y,deltaD,deltaHD,delta2,direction;x=0;y=R;deltaD=2*(1-R);//△D初始值while(y>=0){putpixel(x,y,color);if(deltaD<0){deltaHD=2*(deltaD+y)－1;if(deltaHD<=0)direction=1;//即選H

elsedirection=2;//即選D}Bresenham畫圓算法參考程序2023/2/5西安工程大學計算機圖形學65elseif(deltaD>0){deltaDV=2*(deltaD-x)-1;if(deltaDV<=0)direction=2;elsedirection=3;}elsedirection=2;switch(direction){case1:x++;deltaD+=2*x+1;break;case2:x++;y--;deltaD+=2*(x-y+1);break;case3:y--;deltaD+=(-2*y+1);break;}/*switch*/}/*while*/}/*Bresenham_Ciecle*/2023/2/5西安工程大學計算機圖形學66Bresenham畫圓算法

現(xiàn)在從(0,R)點開始向右下方逐點來尋找圓弧上的點。如圖中點Pi是已選中的一個表示圓弧上的點，根據(jù)圓弧的走向，下一個點應該從Hi或者Li中選擇。顯然應選離圓弧最近的點作為顯示圓弧的點。PiHiLi假設圓的半徑為R，顯然，當

xhi2+yhi2-R2≥R2-(xli2+yli2)時應該取Li。否則取Hi。令di=xhi2+yhi2+xli2+yli2–2R2

顯然，

當di≥0時應該取Li。否則，取Hi。2023/2/5西安工程大學計算機圖形學67di=(xi+1)2+yi2+(xi+1)2+(yi-1)2-2R2=2(xi+1)2+2yi2-2yi

+1-2R2當di<0時->取Hi(xi+1,yi)

，則PiHiLi

下步就是如何快速的計算di。設圖中Pi的坐標(xi,yi)則Hi和Li的坐標為(xi+1,yi)和(xi＋1,yi-1)di+1=(xi+1+1)2+yi2+(xi+1+1)2+(yi-1)2-2R2=2(xi+1)2+2yi2-2yi+1-2R2+4xi+6=di+4xi+6Bresenham畫圓算法2023/2/5西安工程大學計算機圖形學68當di≥0時->取Li(xi＋1,yi-1)

，則

di+1=(xi

+1+1)2+(yi-1)2+(xi+1+1)2+(yi-1-1)2-2R2=di+4(xi-yi)+10PiHiLi

易知x0=0，y0=R,x1=x0+1

因此d0=12+y02+12+(y0-1)2-2R2

=3-2y0=3-2RBresenham畫圓算法2023/2/5西安工程大學計算機圖形學69生成圓弧的正負法

原理：

設圓的方程為F(x,y)=X2+Y2-R2=0;

假設求得Pi的坐標為(xi,yi)；則當Pi在圓內(nèi)時->F(xi,yi)<0->向右->向圓外當Pi在圓外時->F(xi,yi)>0->向下->向圓內(nèi)2023/2/5西安工程大學計算機圖形學70即求得Pi點后選擇下一個象素點Pi+1的規(guī)則為：當F(xi,yi)≤0取xi+1=xi+1，yi+1=yi;

當F(xi,yi)＞0取xi+1=xi，yi+1=yi-1;

這樣用于表示圓弧的點均在圓弧附近，且使F(xi,yi)時正時負，故稱正負法?？焖儆嬎愕年P鍵是F(xi,yi)的計算，能否采用增量算法？生成圓弧的正負法2023/2/5西安工程大學計算機圖形學71若F(xi,yi)已知，計算F(xi+1,yi+1)可分兩種情況：1、F(xi,yi)≤0->xi+1=xi+1，yi+1=yi;->F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2

->=(xi+1)2+yi2

-R2=F(xi,yi)+2xi

+12、F(xi,yi)＞0->xi+1=xi，yi+1=yi-1;->F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2

->=xi2+(yi–1)2-R2=F(xi,yi)-2yi

+13、初始值：略生成圓弧的正負法2023/2/5西安工程大學計算機圖形學724.3橢圓的掃描轉(zhuǎn)換F(x,y)=b2x2+a2y2-a2b2=0橢圓的對稱性，只考慮第一象限橢圓弧生成，分上下兩部分，以切線斜率為-1的點作為分界點.也就是法向量中x和y分量相等的點.橢圓上一點處的法向：

N(x,y)=Fx'i+Fy'

j =2b2

x

i+2a2

y

j上半部分下半部分2023/2/5西安工程大學計算機圖形學73上半部分,法向量的y分量大。法向量兩分量相等在當前中點處，法向量（2b2(Xp+1)，2a2(Yp-0.5))的y分量比x分量大,即：b2(Xp+1)<a2(Yp-0.5),而在下一中點，不等式改變方向，則說明橢圓弧從上部分轉(zhuǎn)入下部分上半部分下半部分M1M2下半部分,法向量的x分量大4.3橢圓的掃描轉(zhuǎn)換2023/2/5西安工程大學計算機圖形學74先討論橢圓弧的上部分

設(Xp，Yp)已確定，則下一像素為:(Xp+1，Yp)或(Xp+1，Yp-1).為了選取下一像素將候選像素中點(Xp+1,Yp-0.5)帶入橢圓隱式方程判定符號.

d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b2

與圓弧中點算法類似：確定一個象素后，接著在兩個候選象素的中點計算一個判別式的值，由判別式的符號確定距離橢圓弧更近的點4.3橢圓的掃描轉(zhuǎn)換2023/2/5西安工程大學計算機圖形學75

根據(jù)d1的符號來決定是取正右方的(Xp+1，Yp)還是右下方(Xp+1，Yp-1).。

若d1＜0，中點在橢圓內(nèi)，取正右方象素，判別式更新為：

d1’=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)d1的增量為b2(2Xp+3).

若d1≥0，中點在橢圓外，取右下方象素，判別式更新為：d1'=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)d1的增量為b2(2Xp+3)+a2(-2Yp+2)4.3橢圓的掃描轉(zhuǎn)換再討論橢圓弧的下部分

設(Xp，Yp)已確定，則下一像素為:(Xp，Yp-1)或(Xp+1，Yp-1).為了選取下一像素將候選像素中點(Xp+0.5,Yp-1)帶入橢圓隱式方程判定符號.

d2=F(Xp+0.5,Yp-1)=b2(Xp+0.5)2+a2(Yp-1)2-a2b24.3橢圓的掃描轉(zhuǎn)換若d2＜0，中點在橢圓內(nèi)，取右下方象素，判別式更新為：

d2’=F(Xp+1.5,Yp-2)=d2+b2(2Xp+2)+a2(3-2Yp)d2的增量為b2(2Xp+2)+a2(3-2Yp).若d2>=0，中點在橢圓外，取正下方象素，判別式更新為：

d2’=F(Xp+0.5,Yp-2)=d2+a2(3-2Yp)d2的增量為a2(3-2Yp).4.3橢圓的掃描轉(zhuǎn)換d1的初始值：橢圓弧起點為(0，b)；第一個中點為(1,b-0.5).初始判別式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)轉(zhuǎn)入下部分，下一象素可能是正下方或右下方，此時判別式要初始化。假定上半部分最后一