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

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

4.1.1、DDA算法

4.1.2、中點(diǎn)畫線法

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

4.2.1、中點(diǎn)算法

4.2.2、Bresenham畫圓算法

4.2.3、生成圓弧的正負(fù)法4.3、橢圓弧生成算法

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

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

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

已知直線L兩端點(diǎn)位P0(x0,y0),P1(x1,y1)4.1直線段的掃描轉(zhuǎn)換算法即可以通過x方向的增量Δx，計(jì)算y的增量Δy來生成直線。當(dāng)?shù)?.1.1、數(shù)值微分法（ＤＤＡ）2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)9即：當(dāng)x方向每遞增1像素，y方向遞增k(即直線斜率)；每次通過上式計(jì)算出（xi，yi）取整后輸出顯示器。注意上述分析的算法僅適用于k≤1的情形。在這種情況下，x每增加1,y最多增加1。4.1直線段的掃描轉(zhuǎn)換算法當(dāng)?shù)?.1.1、數(shù)值微分法（ＤＤＡ）2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)10注：當(dāng)時(shí)，必須把x,y位置互換，即利用遞推式，y每增加1，x相應(yīng)增加。所以取和中較大者為步進(jìn)方向，如下圖x為步進(jìn)方向y為步進(jìn)方向4.1直線段的掃描轉(zhuǎn)換算法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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西安工程大學(xué)計(jì)算機(jī)圖形學(xué)13增量算法：在一個(gè)迭代算法中，如果每一步的x、y值是用前一步的值加上一個(gè)增量來獲得，則稱為增量算法。DDA算法就是一個(gè)增量算法。4.1直線段的掃描轉(zhuǎn)換算法該算法的優(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)行四舍五入后取整。4.1.1、數(shù)值微分法（ＤＤＡ）2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)144.1.2、中點(diǎn)畫線法原理：假定直線斜率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)亮的象素是P1還是P2。P=(xp,yp)QP2P14.1直線段的掃描轉(zhuǎn)換算法M2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)15我們以M和Q的關(guān)系來判斷取P1還是P2當(dāng)M在Q的下方->P2離直線更近更近->取P2。M在Q的上方->P1離直線更近更近->取P1M與Q重合，P1、P2任取一點(diǎn)。問題：如何判斷M與Q點(diǎn)的關(guān)系？P=(xp,yp)QP2P1M4.1直線段的掃描轉(zhuǎn)換算法4.1.2、中點(diǎn)畫線法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)16∴欲判斷中點(diǎn)M點(diǎn)是在Q點(diǎn)上方還是在Q點(diǎn)下方，只需把M代入F(x,y),并檢查它的符號(hào)。P=(xp,yp)QP2P1M4.1直線段的掃描轉(zhuǎn)換算法4.1.2、中點(diǎn)畫線法

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

c=x0y1-x1y02023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)17當(dāng)d=0，選P1或P2均可，約定取P1；P=(xp,yp)QP2P14.1直線段的掃描轉(zhuǎn)換算法4.1.2、中點(diǎn)畫線法構(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；能否采用增量算法呢？M2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)18情形1.若d0->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；

即d的增量為a,QP2P14.1直線段的掃描轉(zhuǎn)換算法P=(xp,yp)M4.1.2、中點(diǎn)畫線法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)19情形2.若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

；即d的增量為a＋bP=(xp,yp)QP2P14.1直線段的掃描轉(zhuǎn)換算法M4.1.2、中點(diǎn)畫線法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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

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

若d0

增量為2*a

若d<0

增量為2*(a+b)4.1.2、中點(diǎn)畫線法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)21012345321例：用中點(diǎn)畫線法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、中點(diǎn)畫線法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)22中點(diǎn)畫線法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西安工程大學(xué)計(jì)算機(jī)圖形學(xué)234.1.3、直線的Bresenham算法4.1直線段的掃描轉(zhuǎn)換算法

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

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

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

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

是否增1取決于如圖所示誤差項(xiàng)

d的值。因?yàn)橹本€的起始點(diǎn)在象素中心，所以誤差項(xiàng)

d的初值d0＝0

因?yàn)閤每增加1，d的值相應(yīng)遞增直線的斜率值

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

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

k。結(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}d4.1直線段的掃描轉(zhuǎn)換算法

1.當(dāng)e≥0時(shí)，取當(dāng)前像素（xi，yi）的右上方像素點(diǎn)（xi＋1，yi＋1）；注：同前面一樣，y方向上走一步，e=e-1。

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

舉例1:用Bresenham方法掃描轉(zhuǎn)換連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段。斜率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è)像素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西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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àn)橐坏﹜方向上走一步，就減去1。沒有擺脫浮點(diǎn)數(shù)計(jì)算2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)30

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

改進(jìn)的Bresenham畫線算法程序：4.1直線段的掃描轉(zhuǎn)換算法遞增量初始量原先即2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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西安工程大學(xué)計(jì)算機(jī)圖形學(xué)32Bresenham算法的優(yōu)點(diǎn)是：1、不必計(jì)算直線之斜率，因此不做除法；2、不用浮點(diǎn)數(shù)，只用整數(shù)；3、只做整數(shù)加減法和乘2運(yùn)算，而乘2運(yùn)算可以用硬件移位實(shí)現(xiàn)。Bresenham算法速度很快，并適于用硬件實(shí)現(xiàn)。4.1直線段的掃描轉(zhuǎn)換算法4.1.3、直線的Bresenham算法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)33(1)上述算法只對(duì)斜率在0~1之間的直線段生成適合，

當(dāng)直線的斜率大于1時(shí)，算法應(yīng)該如何改進(jìn)?MaxxMaxy(0,0)(50,20)MaxyMaxx(0,0)(50,20)}d

}d

}d

}d

注意：此時(shí)d或e的增量為幾點(diǎn)討論和思考4.1直線段的掃描轉(zhuǎn)換算法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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西安工程大學(xué)計(jì)算機(jī)圖形學(xué)35(3)根據(jù)上述的思想，我們?nèi)绾螌⑺惴〝U(kuò)展到，任一八分圓坐標(biāo)空間圖，從而形成一般Bresenham算法？

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

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

X2+Y2=R2

若圓心不在原點(diǎn)可以通過坐標(biāo)變換畫出任意位置的圓。2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)374.2.1圓弧掃描算法

X2+Y2=R2

Y=Sqrt(R2-X2)在一定范圍內(nèi)，每給定一X值，可得一Y值。當(dāng)X取整數(shù)時(shí)，Y須取整。缺點(diǎn)：浮點(diǎn)運(yùn)算，開方，取整，不均勻。yx2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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值后，即可以增量方式獲得圓周上的坐標(biāo)，然后取整可得象素坐標(biāo)。但要采用浮點(diǎn)運(yùn)算、乘法運(yùn)算、取整運(yùn)算。圓的極坐標(biāo)方程x=x0+Rcos

y=y0+Rsin求微分dx=－

Rsind

dy=Rcosd記

xn+1－xn

＝dx

yn+1－yn

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

－1)。MP1P2P（Xp

，Yp

）利用圓的對(duì)稱性，只須討論1/8圓。XYY=XY=-X2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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）在圓外。設(shè)M為P1、P2間的中點(diǎn)，M=(Xp+1,Yp-0.5)MP1P24.2.3中點(diǎn)畫圓法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)41有如下結(jié)論：

F(M)<0

M在圓內(nèi)

取P1

F(M)>=0M在圓外

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

MP1P2P(xp,yp)4.2.3中點(diǎn)畫圓法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)42

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.MP1P2P(xp,yp)4.2.3中點(diǎn)畫圓法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)43

若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

即：d0=1.25-RMP1P2P2P(xp,yp)4.2.3中點(diǎn)畫圓法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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中點(diǎn)畫圓法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)45為了進(jìn)一步提高算法的效率，可以將上面的算法中的浮點(diǎn)數(shù)改寫成整數(shù)，將乘法運(yùn)算改成加法運(yùn)算，即僅用整數(shù)實(shí)現(xiàn)中點(diǎn)畫圓法。使用e=d-0.25代替de0=1-R4.2.3中點(diǎn)畫圓法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)46上述算法能否再改進(jìn)呢？注意到d

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

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

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

4.2.4Bresenham畫圓算法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)49

這三個(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全在圓外；

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

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

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

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

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

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

：

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

當(dāng)時(shí)，若，即,則取H，否則取D

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

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

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

的符號(hào)，判斷取D或V

時(shí),取D;當(dāng)時(shí)取V2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)58(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)12354對(duì)于情形5，D、V都在圓外，顯然取V為下一個(gè)像素。此時(shí)

，所以

可見,在

時(shí)，當(dāng)時(shí),取D為下一像素，否則應(yīng)取V為下一像素。由上述討論可知：2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)59情況（三）：此時(shí)

D恰好在圓上，故應(yīng)取

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

歸納上述3種情況的討論，可得計(jì)算下一個(gè)像素的算法：1、當(dāng)

時(shí)，若，則取D，否則取V；2、當(dāng)

時(shí)，若，則取H，否則取D；3、當(dāng)時(shí)，取D。2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)61(x,y)(x+2,y-1)(x＋1,y-1)(x+2,y)

下面討論的增量算法。1、若下一像素取的是HH坐標(biāo)為：其誤差項(xiàng)H(x+1,y)2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)62(x,y)(x+2,y-1)(x＋1,y-2)(x+2,y－2)2、若下一像素取的是DD坐標(biāo)為：D(x+1,y－1)其誤差項(xiàng)2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)63(x,y)(x+1,y-1)(x,y-2)(x+1,y－2)3、若下一像素取的是VV坐標(biāo)為：V(x,y－1)其誤差項(xiàng)2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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西安工程大學(xué)計(jì)算機(jī)圖形學(xué)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西安工程大學(xué)計(jì)算機(jī)圖形學(xué)66Bresenham畫圓算法

現(xiàn)在從(0,R)點(diǎn)開始向右下方逐點(diǎn)來尋找圓弧上的點(diǎn)。如圖中點(diǎn)Pi是已選中的一個(gè)表示圓弧上的點(diǎn)，根據(jù)圓弧的走向，下一個(gè)點(diǎn)應(yīng)該從Hi或者Li中選擇。顯然應(yīng)選離圓弧最近的點(diǎn)作為顯示圓弧的點(diǎn)。PiHiLi假設(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。2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)67di=(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)

，則PiHiLi

下步就是如何快速的計(jì)算di。設(shè)圖中Pi的坐標(biāo)(xi,yi)則Hi和Li的坐標(biāo)為(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西安工程大學(xué)計(jì)算機(jī)圖形學(xué)68當(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)+10PiHiLi

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

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

=3-2y0=3-2RBresenham畫圓算法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)69生成圓弧的正負(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->向右->向圓外當(dāng)Pi在圓外時(shí)->F(xi,yi)>0->向下->向圓內(nèi)2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)70即求得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ù)，故稱正負(fù)法?？焖儆?jì)算的關(guān)鍵是F(xi,yi)的計(jì)算，能否采用增量算法？生成圓弧的正負(fù)法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)71若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、初始值：略生成圓弧的正負(fù)法2023/2/5西安工程大學(xué)計(jì)算機(jī)圖形學(xué)724.3橢圓的掃描轉(zhuǎn)換F(x,y)=b2x2+a2y2-a2b2=0橢圓的對(duì)稱性，只考慮第一象限橢圓弧生成，分上下兩部分，以切線斜率為-1的點(diǎn)作為分界點(diǎn).也就是法向量中x和y分量相等的點(diǎn).橢圓上一點(diǎn)處的法向：

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

j =2b2

x

i+2a2

y

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

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

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

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

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

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

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

若d1≥0，中點(diǎn)在橢圓外，取右下方象素，判別式更新為：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)換再討論橢圓弧的下部分

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

d2=F(Xp+0.5,Yp-1)=b2(Xp+0.5)2+a2(Yp-1)2-a2b24.3橢圓的掃描轉(zhuǎn)換若d2＜0，中點(diǎn)在橢圓內(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，中點(diǎn)在橢圓外，取正下方象素，判別式更新為：

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