直線、圓、橢圓的生成省名師優(yōu)質(zhì)課賽課獲獎(jiǎng)?wù)n件市賽課百校聯(lián)賽優(yōu)質(zhì)課一等獎(jiǎng)?wù)n件

第三章直線、圓、橢圓生成算法圖形掃描轉(zhuǎn)換（光柵化）：確定一個(gè)像素集合，用于顯示一個(gè)圖形過(guò)程。步驟以下：1、確定相關(guān)像素2、用圖形顏色或其它屬性，對(duì)像素進(jìn)行寫(xiě)操作。對(duì)一維圖形，不考慮線寬，則用一個(gè)像素寬直線來(lái)顯示圖形。二維圖形光柵化，即區(qū)域填充：確定像素集，填色或圖案。任何圖形光柵化，必須顯示在一個(gè)窗口內(nèi)，不然不予顯示。即確定一個(gè)圖形哪些部分在窗口內(nèi)，哪些在窗口外，即裁剪。 1/899/12/20231西安工程大學(xué)計(jì)算機(jī)圖形學(xué)圖形顯示前需要：掃描轉(zhuǎn)換+裁剪●裁剪---〉掃描轉(zhuǎn)換：最慣用，節(jié)約計(jì)算時(shí)間。●掃描轉(zhuǎn)換---〉裁剪：算法簡(jiǎn)單；2/899/12/20232西安工程大學(xué)計(jì)算機(jī)圖形學(xué)本章內(nèi)容掃描轉(zhuǎn)換直線段

DDA算法中點(diǎn)畫(huà)線法Bresenham畫(huà)線算法圓弧、橢圓弧掃描轉(zhuǎn)換

中點(diǎn)算法內(nèi)接正多邊形迫近法等面積正多邊形迫近法生成圓弧正負(fù)法

3/899/12/20233西安工程大學(xué)計(jì)算機(jī)圖形學(xué)

在數(shù)學(xué)上，理想直線是沒(méi)有寬度，是由無(wú)數(shù)個(gè)在它上面點(diǎn)組成集合。直線能夠向一個(gè)方向及其相反方向無(wú)限延長(zhǎng)。在圖形學(xué)中研究對(duì)象是直線段，它是一條含有一個(gè)Pixel或多個(gè)Pixel寬直線段。圖形顯示器是由一個(gè)個(gè)排列有序像素組成，劃分像素點(diǎn)越多分辨率就越高。比如640X480顯示器，分成640X480個(gè)網(wǎng)格，網(wǎng)格單元視為像素，一條線段就是由一些連續(xù)可見(jiàn)像素所組成，以下列圖所表示：直線段掃描轉(zhuǎn)換算法4/899/12/20234西安工程大學(xué)計(jì)算機(jī)圖形學(xué)由上圖可知：畫(huà)一條直線實(shí)際上就是依據(jù)一系列計(jì)算出來(lái)并與該直線靠近像素繪制。Line:P0(0,0)——P1(5,2)0143215234各行各列像素中心組成一組虛擬網(wǎng)格線像素單元5/899/12/20235西安工程大學(xué)計(jì)算機(jī)圖形學(xué)直線掃描轉(zhuǎn)換:確定最正確迫近于該直線一組象素，而且按掃描線次序，對(duì)這些象素進(jìn)行寫(xiě)操作。直線段是最基本圖形，所以直線段生成質(zhì)量好壞與速度快慢將直接影響整個(gè)圖形生成質(zhì)量和速度。三個(gè)慣用算法：數(shù)值微分法（DDA）中點(diǎn)畫(huà)線法Bresenham算法。6/899/12/20236西安工程大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)值微分法（ＤＤＡ）

假定直線起點(diǎn)、終點(diǎn)分別為：（x0,y0),(x1,y1)，且都為整數(shù)。

柵格交點(diǎn)表示象素點(diǎn)位置(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)。。。。7/899/12/20237西安工程大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)值微分(DDA)法基本思想已知過(guò)端點(diǎn)P0(x0,y0),P1(x1,y1)直線段Ly=kx+b直線斜率為這種方法直觀，但效率太低，因?yàn)槊恳徊叫枰淮胃↑c(diǎn)乘法和一次舍入運(yùn)算。

8/899/12/20238西安工程大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)值微分(DDA)法計(jì)算yi+1=kxi+1+b

=kxi+b+k

x =yi+k

x

當(dāng)

x=1;

yi+1=

yi+k

即：當(dāng)x每遞增1，y遞增k(即直線斜率)；注意上述分析算法僅適合用于

k

≤1情形。在這種情況下，x每增加1,y最多增加1。9/899/12/20239西安工程大學(xué)計(jì)算機(jī)圖形學(xué)注：當(dāng)時(shí)，必須把x,y位置交換，即利用遞推式，y每增加1，x對(duì)應(yīng)增加。所以取和中較大者為步進(jìn)方向，以下列圖自然明白。，，x為步進(jìn)方向y為步進(jìn)方向10/899/12/202310西安工程大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)值微分(DDA)法增量算法：在一個(gè)迭代算法中，假如每一步x、y值是用前一步值加上一個(gè)增量來(lái)取得，則稱(chēng)為增量算法。DDA算法就是一個(gè)增量算法。11/899/12/202311西安工程大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)

intx； floatdx,dy,y,k; dx,=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;x

x1,x++)

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

12/899/12/202312西安工程大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)值微分(DDA)法例：畫(huà)直線段P0(0,0)--P1(5,2)xint(y+0.5) y+0.50 0 0+0.51 0 0.4+0.52 1 0.8+0.5 3 1 1.2+0.54 2 1.6+0.55 2 2.0+0.5012345321Line:P0(0,0)--P1(5,2)13/899/12/202313西安工程大學(xué)計(jì)算機(jī)圖形學(xué)數(shù)值微分(DDA)法該算法優(yōu)點(diǎn)是繪制實(shí)數(shù)直線效果好，誤差小。缺點(diǎn)是實(shí)現(xiàn)較復(fù)雜，不利于硬件實(shí)現(xiàn)。該算法包括到實(shí)數(shù)乘除法運(yùn)算，y與k必須用浮點(diǎn)數(shù)表示，而且每一步都要對(duì)y進(jìn)行四舍五入后取整。14/899/12/202314西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)線法原理：假定直線斜率0<K<1，且已確定點(diǎn)亮象素點(diǎn)P（Xp

,Yp

）,則下一個(gè)與直線最靠近像素只能是P1點(diǎn)或P2點(diǎn)。設(shè)M為中點(diǎn)，Q為交點(diǎn)現(xiàn)需確定下一個(gè)點(diǎn)亮象素。P=(xp,yp)QP2P115/899/12/202315西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)線法當(dāng)M在Q下方->P2離直線更近更近->取P2。M在Q上方->P1離直線更近更近->取P1M與Q重合，P1、P2任取一點(diǎn)。問(wèn)題：怎樣判斷M與Q點(diǎn)關(guān)系？P=(xp,yp)QP2P1M16/899/12/202316西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)線法假設(shè)直線方程為：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常識(shí)知：∴欲判斷中點(diǎn)M點(diǎn)是在Q點(diǎn)上方還是在Q點(diǎn)下方，只需把M代入F(x,y),并檢驗(yàn)它符號(hào)。P=(xp,yp)QP2P1M17/899/12/202317西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)線法結(jié)構(gòu)判別式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c當(dāng)d<0，M在直線(Q點(diǎn))下方，取右上方P2；當(dāng)d>0，M在直線(Q點(diǎn))上方，取右方P1；當(dāng)d=0，選P1或P2均可，約定取P1；能否采取增量算法呢？P=(xp,yp)QP2P118/899/12/202318西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)線法若d

0->M在直線上方->取P1;此時(shí)再下一個(gè)象素判別式為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；增量為aP=(xp,yp)QP2P119/899/12/202319西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)線法若d<0->M在直線下方->取P2;此時(shí)再下一個(gè)象素判別式為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；增量為a＋bP=(xp,yp)QP2P120/899/12/202320西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)線法畫(huà)線從(x0,y0)開(kāi)始，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因?yàn)橹挥胐符號(hào)作判斷，為了只包含整數(shù)運(yùn)算,能夠用2d代替d來(lái)擺脫小數(shù)，提升效率。21/899/12/202321西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)線法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*/22/899/12/202322西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)線法例：用中點(diǎn)畫(huà)線法P0(0,0)P1(5,2)a=y0-y1=-2b=x1-x0=5d0=2a+b=1d1=2a=-4d2=2(a+b)=6i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5

01234532123/899/12/202323西安工程大學(xué)計(jì)算機(jī)圖形學(xué)本算法由Bresenham在1965年提出，Bresenham算法是計(jì)算機(jī)圖形學(xué)領(lǐng)域使用最廣泛直線掃描轉(zhuǎn)換算法。該方法類(lèi)似于中點(diǎn)法，由誤差項(xiàng)符號(hào)決定下一個(gè)象素取右邊點(diǎn)還是右上點(diǎn)。算法原理：過(guò)各行各列象素中心結(jié)構(gòu)一組虛擬網(wǎng)格線。按直線從起點(diǎn)到終點(diǎn)次序計(jì)算直線與各垂直網(wǎng)格線交點(diǎn)，然后確定該列象素中與此交點(diǎn)最近象素。該算法巧妙之處于于采取增量計(jì)算，使得對(duì)于每一列，只要檢驗(yàn)一個(gè)誤差項(xiàng)符號(hào)，就能夠確定該列所求象素。

}dy}dx}d直線Bresenham算法

24/899/12/202324西安工程大學(xué)計(jì)算機(jī)圖形學(xué)1.Bresenham算法實(shí)現(xiàn)為了討論方便，我們先以第一個(gè)八分圓直線為例，即假定直線斜率在0~1之間，其它情況類(lèi)似處理。如右圖-1所表示，設(shè)直線方程為其中k=dy/dx。

假設(shè)x列象素已經(jīng)確定為xi，其行坐標(biāo)為yi。那么下一個(gè)象素列坐標(biāo)為xi＋1，而行坐標(biāo)要么不變?yōu)閥i，要么遞增1為yi＋1。

}dy}d}d

x}d圖-125/899/12/202325西安工程大學(xué)計(jì)算機(jī)圖形學(xué)是否增1取決于如圖所表示誤差項(xiàng)d值。因?yàn)橹本€起始點(diǎn)在象素中心，所以誤差項(xiàng)d初值d0＝0

因?yàn)閄下標(biāo)每增加1，d值對(duì)應(yīng)遞增直線斜率值k，即d＝d＋k。一旦d≥1，就把它減去1，這么確保d在0、1之間。

1.

當(dāng)d≥0.5時(shí)，直線與xi＋1列垂直網(wǎng)格交點(diǎn)最靠近于當(dāng)前象素（xi，yi）右上方象素（xi+1，yi＋1）；2.

當(dāng)d<0.5時(shí)，更靠近于正右方象素（xi＋1，yi）。

圖-1

Bresenham算法誤差項(xiàng)幾何含義}dy}d}d

x}d26/899/12/202326西安工程大學(xué)計(jì)算機(jī)圖形學(xué)為方便計(jì)算，令e＝d－0.5，e初值為－0.5，增量為k。1.當(dāng)e≥0時(shí)，取當(dāng)前象素（xi，yi）右上方象素點(diǎn)（xi＋1，yi＋1）；結(jié)論：1.

d初值d0＝0，d＝d＋k；2.當(dāng)d≥0.5時(shí)，下一個(gè)像素取為右上方象素（xi+1，yi＋1）；3.當(dāng)d<0.5時(shí)，下一個(gè)像素取為正右方象素（xi＋1，yi）。

2.當(dāng)e<0時(shí)，更靠近于正右方象素點(diǎn)（xi＋1，yi）。

圖-1

Bresenham算法誤差項(xiàng)幾何含義}dy}d}d

x}d27/899/12/202327西安工程大學(xué)計(jì)算機(jī)圖形學(xué)Bresenham畫(huà)線算法參考程序(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;}

}}因?yàn)橐坏ヾ≥1，就減去1，一樣一旦e≥0，也減去1。28/899/12/202328西安工程大學(xué)計(jì)算機(jī)圖形學(xué)

舉例1:用Bresenham方法掃描轉(zhuǎn)換連接兩點(diǎn)P0（0,0）和P1（5,2）直線段。0.5-0.552-0.90.142-0.3-0.331-0.70.321-0.1-0.110-0.5-0.500

e判斷前判斷后

xy斜率K=2/5=0.4e0=-0.5e=d-0.5,d=d+k,k=dy/dx當(dāng)e≥0時(shí)，取當(dāng)前像素右上方像素為下一個(gè)像素當(dāng)e<0時(shí)，取當(dāng)前像素正右方像素為下一個(gè)像素0143215234Line:P0(0,0)—P1(5,2)29/899/12/202329西安工程大學(xué)計(jì)算機(jī)圖形學(xué)

舉例2：用Bresenham方法掃描轉(zhuǎn)換連接從點(diǎn)P0（0,0）到Pi（ix100,100）(i=1,2,3,4,5)直線段。程序：

#include"graphics.h"#include"stdio.h"#include"conio.h"main(){intBresenham_line();intgdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"D:\\TC");Bresenham_line(0,0,100,100,4);Bresenham_line(0,0,200,100,4);Bresenham_line(0,0,300,100,4);30/899/12/202330西安工程大學(xué)計(jì)算機(jī)圖形學(xué)Bresenham_line(0,0,400,100,4);Bresenham_line(0,0,500,100,4);getch();closegraph();}Bresenham_line(intx0,inty0,intx1,inty1,intcolor){intx,i,y;floatdx,dy,k,e;dx=x1-x0;dy=y1-y0;31/899/12/202331西安工程大學(xué)計(jì)算機(jī)圖形學(xué)

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=y+1;e=e-1;}}}運(yùn)行效果圖32/899/12/202332西安工程大學(xué)計(jì)算機(jī)圖形學(xué)voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy,e0;dx=x1-x0;dy=y1-y0;

e0=-dx;

x=x0;y=y0;

e=-0.5；e0=-dx上述bresenham算法在計(jì)算誤差項(xiàng)與直線斜率時(shí)用到小數(shù)與除法。能夠改用整數(shù)以防止去法。因?yàn)樗惴ㄖ兄挥玫秸`差項(xiàng)符號(hào)，所以可作以下替換：

4.改進(jìn)Bresenham畫(huà)線算法程序：33/899/12/202333西安工程大學(xué)計(jì)算機(jī)圖形學(xué)Bresenham算法優(yōu)點(diǎn)是：1、無(wú)須計(jì)算直線之斜率，所以不做除法；2、不用浮點(diǎn)數(shù)，只用整數(shù)；3、只做整數(shù)加減法和乘2運(yùn)算，而乘2運(yùn)算能夠用硬件移位實(shí)現(xiàn)。Bresenham算法速度很快，并適于用硬件實(shí)現(xiàn)。for(i=0;i<=dx;i++)

{putpixel(x,y,color);

x++;e0=e0+2*dy;

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

}}說(shuō)明：1.因?yàn)閑0=2*e*dx且e=e+k,2*e*dx=2*e*dx+2*dx*k所以e0=e0+2*dy；2.同理有e=e-1改為:e0=e0-2*dx34/899/12/202334西安工程大學(xué)計(jì)算機(jī)圖形學(xué)(1)上述算法只對(duì)斜率在0~1之間直線段生成適合，當(dāng)直線斜率大于1時(shí)，算法應(yīng)該怎樣改進(jìn)?

圖-1屏幕坐標(biāo)系，逆時(shí)針旋轉(zhuǎn)90度MaxxMaxy(0,0)(50,20)圖-2直角坐標(biāo)系MaxyMaxx(0,0)(50,20)}d

}d

}d

}d

注意：此時(shí)d或e增量為5.幾點(diǎn)討論和思索35/899/12/202335西安工程大學(xué)計(jì)算機(jī)圖形學(xué)for(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畫(huà)線算法參考程序(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;36/899/12/202336西安工程大學(xué)計(jì)算機(jī)圖形學(xué)

舉例：用Bresenham方法掃描轉(zhuǎn)換連接從點(diǎn)P0（0,0）到Pi（100,ix100）(i=1,2,3,4,5)直線段。直線斜率K>1運(yùn)行效果圖37/899/12/202337西安工程大學(xué)計(jì)算機(jī)圖形學(xué)(3)依據(jù)上述思想，我們?cè)鯓訉⑺惴〝U(kuò)展到，任一八分圓坐標(biāo)空間圖，從而形成普通Bresenham算法？以下列圖：普通Bresenham算法判別條件x=x+1y=y+1x=x+1y=y-1x=x-1y=y-1x=x-1y=y+1y增1y增1y減1y減1x增1x增1x減1x減1x1,y138/899/12/202338西安工程大學(xué)計(jì)算機(jī)圖形學(xué)(4)適合用于全部八個(gè)方向Bresenham直線生成算法#include"graphics.h"#include"stdio.h"#include"conio.h"main(){intbresenham_line();intgdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"D:\\TC");bresenham_line(0,0,100,300,4);getch();closegraph();}39/899/12/202339西安工程大學(xué)計(jì)算機(jī)圖形學(xué)bresenham_line(x1,y1,x2,y2,c)intx1,y1,x2,y2,c;{intdx,dy;intx,y,p;intconst1,const2;intinc;inttmp;dx=x2-x1;dy=y2-y1;if(dx*dy>=0)/*準(zhǔn)備x或y單位遞變值。*/inc=1;elseinc=-1;40/899/12/202340西安工程大學(xué)計(jì)算機(jī)圖形學(xué)if(abs(dx)>abs(dy)){if(dx<0){tmp=x1;/*將2a,3a象限方向*/x1=x2;/*直線變換到1a,4a*/x2=tmp;tmp=y1;/*象限方向去*/y1=y2;dx=-dy;dy=-dy;}p=2*dy-dx;const1=2*dy;/*注意此時(shí)誤差*/const2=2*(dy-dy);/*改變參數(shù)取值.*/41/899/12/202341西安工程大學(xué)計(jì)算機(jī)圖形學(xué)x=x1;y=y1;putpixel(x,y,c);while(x<x2){x++;if(p<0)p+=const1;else{y+=inc;p+=const2;} putpixel(x,y,c);}}42/899/12/202342西安工程大學(xué)計(jì)算機(jī)圖形學(xué)else{if(dy<0){tmp=x1;/*將3b,4b象限方向*/x1=x2;/*直線變換到2b,1b*/x2=tmp;/*象限方向去.*/tmp=y1;y1=y2;dx=-dy;dy=-dy;}p=2*dx-dy;/*注意此時(shí)誤差*/const1=2*dx;/*改變參數(shù)取值.*/const2=2*(dx-dy);43/899/12/202343西安工程大學(xué)計(jì)算機(jī)圖形學(xué)x=x1;y=y1;putpixel(x,y,c);while(y<y2){y++;if(p<0)p+=const1;else{x+=inc;p+=const2; putpixel(x,y,c);} }}}44/899/12/202344西安工程大學(xué)計(jì)算機(jī)圖形學(xué)圓掃描轉(zhuǎn)換算法下面僅以圓心在原點(diǎn)、半徑R為整數(shù)圓為例，討論圓生成算法。假設(shè)圓方程為：X2+Y2=R245/899/12/202345西安工程大學(xué)計(jì)算機(jī)圖形學(xué)圓弧掃描算法X2+Y2=R2Y=Sqrt(R2-X2)在一定范圍內(nèi)，每給定一X值，可得一Y值。當(dāng)X取整數(shù)時(shí)，Y須取整。缺點(diǎn)：浮點(diǎn)運(yùn)算，開(kāi)方，取整，不均勻。yx46/899/12/202346西安工程大學(xué)計(jì)算機(jī)圖形學(xué)角度DDA法x=x0+Rcosy=y0+Rsindx=-Rsinddy=Rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn+dx=xn-Rsind=xn-(yn-y0)d

yn+1=yn+dy=yn+Rcosd=yn+(xn-x0)d

顯然，確定x,y初值及d

值后，即能夠增量方式取得圓周上坐標(biāo)，然后取整可得象素坐標(biāo)。但要采取浮點(diǎn)運(yùn)算、乘法運(yùn)算、取整運(yùn)算。47/899/12/202347西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)圓法利用圓對(duì)稱(chēng)性，只須討論1/8圓。第二個(gè)8分圓P為當(dāng)前點(diǎn)亮象素，那么，下一個(gè)點(diǎn)亮象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp－1)。MP1P2P（Xp，Yp）48/899/12/202348西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)圓法結(jié)構(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）在圓外。設(shè)M為P1、P2間中點(diǎn)，M=(Xp+1,Yp-0.5)MP1P249/899/12/202349西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)圓法有以下結(jié)論：F（M）<0->M在圓內(nèi)->取P1F（M）>=0->M在圓外->取P2為此，可采取以下判別式：

MP1P250/899/12/202350西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)圓法d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若d<0,則P1為下一個(gè)象素，那么再下一個(gè)象素判別式為：

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

=d+2xp+3即d增量為2xp+3.P1MP251/899/12/202351西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)圓法若d>=0,則P2為下一個(gè)象素，那么再下一個(gè)象素判別式為：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=1.25-RMP1P252/899/12/202352西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)圓法MidpointCircle(intr,intcolor){intx,y;floatd;x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(x<y){if(d<0){d+=2*x+3;x++}else{d+=2*(x-y)+5;x++;y--;}}}53/899/12/202353西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)圓法為了深入提升算法效率，能夠?qū)⑸厦嫠惴ㄖ懈↑c(diǎn)數(shù)改寫(xiě)成整數(shù)，將乘法運(yùn)算改成加法運(yùn)算，即僅用整數(shù)實(shí)現(xiàn)中點(diǎn)畫(huà)圓法。使用e=d-0.25代替de0=1-R54/899/12/202354西安工程大學(xué)計(jì)算機(jī)圖形學(xué)中點(diǎn)畫(huà)圓法上述算法能否再改進(jìn)呢？注意到d增量是x,y線性函數(shù)，每當(dāng)x遞增1，則d增量遞增Δx=2每當(dāng)y遞減1，則d增量遞增Δy=2Δx初始值=3；Δy初始值=-2r+255/899/12/202355西安工程大學(xué)計(jì)算機(jī)圖形學(xué)本節(jié)介紹另一個(gè)慣用畫(huà)圓算法：Bresenham算法。不失普通性，考慮圓心在原點(diǎn)，半徑為R第一4分圓。?。?，R）為起點(diǎn)，按順時(shí)針?lè)较蛏蓤A。以下列圖所表示：（0，R）YXOR第一個(gè)4分圓3.3.3圓Bresenham算法

56/899/12/202356西安工程大學(xué)計(jì)算機(jī)圖形學(xué)從這段圓弧任意一點(diǎn)出發(fā)，按順時(shí)針?lè)较蛏蓤A時(shí)，為了最正確迫近該圓，下一個(gè)像素取法只有三種可能選擇：正右方像素，右下方像素和正下方像素。分別記為H、D和V。以下列圖所表示：（0，R）YXOR第一個(gè)4分圓(x,y)H(x+1,y)V(x,y-1)D(x+1,y-1)第一個(gè)4分圓下一像素三個(gè)候選者57/899/12/202357西安工程大學(xué)計(jì)算機(jī)圖形學(xué)這三個(gè)像素中，與理想圓弧最近者為所求像素。理想圓弧與這三個(gè)候選點(diǎn)之間關(guān)系只有以下五種情形：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全在圓外； 58/899/12/202358西安工程大學(xué)計(jì)算機(jī)圖形學(xué)上述三點(diǎn)到圓心距離平方與圓弧上一點(diǎn)到圓心距離平方之差分別為：與Bresenham直線掃描算法一樣，在選最正確迫近該圓像素時(shí)，我們希望只判別誤差項(xiàng)符號(hào)。59/899/12/202359西安工程大學(xué)計(jì)算機(jī)圖形學(xué)情況（一）：假如,那么右下方像素D在圓內(nèi)，圓弧與候選點(diǎn)關(guān)系只可能是1與2情形。則這是最正確迫近圓弧像素只可能是H或D兩個(gè)像素之一。為了確定H和D哪個(gè)更靠近于圓弧,令60/899/12/202360西安工程大學(xué)計(jì)算機(jī)圖形學(xué)1.

若,則圓到正右方像素H距離小于圓到右下方像素D距離,此時(shí)應(yīng)取H為下一個(gè)像素。2.

若,則圓到右下方像素D距離較小,故應(yīng)取D為下一個(gè)像素。3.若,二者均可取，約定取正右方像素H。對(duì)于情形2，H總在圓外，D總在圓內(nèi)，所以所以能夠簡(jiǎn)化為故能夠依據(jù)符號(hào)，在情形2下判斷應(yīng)取H或D61/899/12/202361西安工程大學(xué)計(jì)算機(jī)圖形學(xué)由上述討論可知：當(dāng)時(shí)，若，即,則取H不然取D

對(duì)于情形1，H、D都在圓內(nèi)，而在這段圓弧上，y是x單調(diào)遞減函數(shù)，所以只能取H為下一個(gè)像素。且這時(shí)，所以有

與情形2判別條件一致。可見(jiàn)在情況下，若，則應(yīng)取H為下一像素，不然應(yīng)取D為下一像素62/899/12/202362西安工程大學(xué)計(jì)算機(jī)圖形學(xué)情況（二）：假如,那么右下方像素D在圓外，圓弧與候選點(diǎn)關(guān)系只可能是4與5情形。則這是最正確迫近圓弧像素只可能是D或V兩個(gè)像素之一。為了確定D和V哪個(gè)更靠近于圓弧,令63/899/12/202363西安工程大學(xué)計(jì)算機(jī)圖形學(xué)1當(dāng)，即時(shí)，應(yīng)取右下方像素D；2當(dāng)，即時(shí)，應(yīng)取正下方像素V；3當(dāng)時(shí)，二者均可取，我們約定取右下方像素DDVO64/899/12/202364西安工程大學(xué)計(jì)算機(jī)圖形學(xué)對(duì)于情形4，因?yàn)镈在圓外，V在圓內(nèi),所以則能夠簡(jiǎn)化為故能夠依據(jù)符號(hào)，在情形4下判斷應(yīng)取D或V從而時(shí),取D;當(dāng)時(shí)取V先考慮情形465/899/12/202365西安工程大學(xué)計(jì)算機(jī)圖形學(xué)再考慮情形5對(duì)于情形5，D、V都在圓外，顯然取V為下一個(gè)像素。且此時(shí)，所以

可見(jiàn),在時(shí)，當(dāng)時(shí),取D為下一像素，不然應(yīng)取V為下一像素。由上述討論可知：情況（三）：此時(shí)D恰好在圓上，故應(yīng)取D作為下一像素。66/899/12/202366西安工程大學(xué)計(jì)算機(jī)圖形學(xué)歸納上述3種情況討論，可得計(jì)算下一個(gè)像素算法：1當(dāng)時(shí)，若，則取D，不然取V；2當(dāng)時(shí)，若，則取H，不然取D；3當(dāng)時(shí)，取D。

67/899/12/202367西安工程大學(xué)計(jì)算機(jī)圖形學(xué)下面我們討論怎樣簡(jiǎn)化計(jì)算。與直線掃描算法類(lèi)似，采取增量算法。1.首先考慮下一個(gè)像素為H情況。對(duì)于像素H:其坐標(biāo)為其誤差項(xiàng)為68/899/12/202368西安工程大學(xué)計(jì)算機(jī)圖形學(xué)2.再考慮下一個(gè)像素為D情況。其坐標(biāo)與誤差項(xiàng)分別為69/899/12/202369西安工程大學(xué)計(jì)算機(jī)圖形學(xué)3.當(dāng)下一個(gè)像素為V情況。其坐標(biāo)與誤差項(xiàng)分別為70/899/12/202370西安工程大學(xué)計(jì)算機(jī)圖形學(xué)Bresenham畫(huà)圓算法參考程序（0，R）YXOR第一個(gè)4分圓Bresenham_Ciecle(intr,intcolor){intx,y,delta,delta1,delta2,direction;x=0;y=r;delta=2*(1-r);

△D初始值while(y>=0){putpixel(x,y,color);if(delta<0){delta1=2*(delta+y)－1;if(delta1<=0)direction=1;

elsedirection=2;

即選D}71/899/12/202371西安工程大學(xué)計(jì)算機(jī)圖形學(xué)elseif(delta>0){delta2=2*(delta-x)-1;if(delta2<=0)direction=2;elsedirection=3;}elsedirection=2;switch(direction){case1:x++;delta+=2*x+1;break;case2:x++;y--;delta+=2*(x-y+1);break;case3:y--;delta+=(-2*y+1);break;}/*switch*/}/*while*/}/*Bresenham_Ciecle*/72/899/12/202372西安工程大學(xué)計(jì)算機(jī)圖形學(xué)Bresenham畫(huà)圓算法現(xiàn)在從A點(diǎn)開(kāi)始向右下方逐點(diǎn)來(lái)尋找弧AB要用點(diǎn)。如圖中點(diǎn)Pi-1是已選中一個(gè)表示圓弧上點(diǎn)，依據(jù)弧AB走向，下一個(gè)點(diǎn)應(yīng)該從Hi或者Li中選擇。顯然應(yīng)選離AB最近點(diǎn)作為顯示弧AB點(diǎn)。假設(shè)圓半徑為R，顯然，當(dāng)xhi2+yhi2-R2≥R2-(xli2+yli2)時(shí)，應(yīng)該取Li。不然取Hi。令di=xhi2+yhi2+xli2+yli2-2R2顯然，當(dāng)di≥0時(shí)應(yīng)該取Li。不然，取Hi。Pi-1HiLi應(yīng)取Hi還是取Li73/899/12/202373西安工程大學(xué)計(jì)算機(jī)圖形學(xué)Bresenham畫(huà)圓算法剩下問(wèn)題是怎樣快速計(jì)算di。設(shè)圖中Pi坐標(biāo)為(xi,yi)，則Hi和Li坐標(biāo)為(xi+1,yi)和(xi＋1,yi-1)di=(xi+1)2+yi2+(xi+1)2+(yi-1)2

-2R2=2(xi+1)2+2yi2-2yi+1-2R2當(dāng)di<0時(shí)->取Hi(xi+1,yi)

，則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+6PiHiLi應(yīng)取Hi還是取Li74/899/12/202374西安工程大學(xué)計(jì)算機(jī)圖形學(xué)Bresenham畫(huà)圓算法當(dāng)di≥0時(shí)->取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)+10易知x0=0，y0=R,x1=x0+1所以d0=12+y02+12+(y0-1)2-2R2=3-2y0=3-2RPi-1HiLi應(yīng)取Hi還是取Li75/899/12/202375西安工程大學(xué)計(jì)算機(jī)圖形學(xué)生成圓弧正負(fù)法原理：

設(shè)圓方程為F(x,y)=X2+Y2-R2=0;假設(shè)求得Pi坐標(biāo)為(xi,yi)；則當(dāng)Pi在圓內(nèi)時(shí)->F(xi,yi)<0->向右->向圓外Pi在圓外時(shí)->F(xi,yi)>0->向下->向圓內(nèi)76/899/12/202376西安工程大學(xué)計(jì)算機(jī)圖形學(xué)生成圓弧正負(fù)法即求得Pi點(diǎn)后選擇下一個(gè)象素點(diǎn)Pi+1規(guī)則為：當(dāng)F(xi,yi)≤0取xi+1=xi+1，yi+1=yi;當(dāng)F(xi,yi)＞0取xi+1=xi，yi+1=yi-1;這么用于表示圓弧點(diǎn)均在圓弧附近，且使F(xi,yi)時(shí)正時(shí)負(fù)，故稱(chēng)正負(fù)法。快速計(jì)算關(guān)鍵是F(xi,yi)計(jì)算，能否采取增量算法？77/899/12/202377西安工程大學(xué)計(jì)算機(jī)圖形學(xué)生成圓弧正負(fù)法若F(xi,yi)已知，計(jì)算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、初始值：略78/899/12/202378西安工程大學(xué)計(jì)算機(jī)圖形學(xué)生成圓弧多邊形迫近法圓內(nèi)接正多邊形迫近法圓等面積正多邊形迫近法79/899/12/202379西安工程大學(xué)計(jì)算機(jī)圖形學(xué)圓內(nèi)接正多邊形迫近法思想：當(dāng)一個(gè)正多邊形邊數(shù)足夠多時(shí)，該多邊形能夠和圓無(wú)限靠近。即所以，在允許誤差范圍內(nèi)，能夠用正多邊形代替圓。設(shè)內(nèi)接正n邊形頂點(diǎn)為Pi(xi,yi),Pi幅角為

i,每一條邊對(duì)應(yīng)圓心角為a，則有xi=Rcos

iyi=Rsin

i80/899/12/202380西安工程大學(xué)計(jì)算機(jī)圖形學(xué)圓內(nèi)接正多邊形迫近法內(nèi)接正n邊形代替圓計(jì)算多邊形各頂點(diǎn)遞推公式Xi+1 Rcos(a+

i)

=Yi+1 Rsin(a+

i) Xi+1 cosa-sinaXi =Yi+1 sinacosaYi因?yàn)?a是常數(shù)，