計算機(jī)圖形學(xué)課件

計算機(jī)圖形考1

余敦群

湖北大學(xué)教計學(xué)院

第五章基本圖形生成算法

光柵掃描圖形系統(tǒng)的結(jié)構(gòu)2

光柵掃描特點(diǎn)：

*數(shù)據(jù)量大

*顯示的離散化

*獨(dú)立的圖形顯示處理器

第五章基本圖形生成算法

圖形顯示處理器(加速引擎)3

任務(wù)：進(jìn)行掃描轉(zhuǎn)換(ScanConversion)

掃描轉(zhuǎn)換：將應(yīng)用程序給出的圖形定義數(shù)字化為一組像

素強(qiáng)度值，并放到幀緩存器

.掃描轉(zhuǎn)換的工作內(nèi)容：

-基本圖形的生成

-字符的生成

-填充、裁剪

-線型的處理

-彩色處理

-某些變換和管理

第五章基本圖形生成算法

坐標(biāo)系統(tǒng)4

為描述對象、構(gòu)造場景或完成圖形變換，需要

不同的坐標(biāo)系！

1.建模坐標(biāo)系一定義對象

2.世界坐標(biāo)系定義對象與外界環(huán)境的關(guān)系

3.設(shè)備坐標(biāo)系一定義圖形顯示的位置、大小

4.規(guī)范化坐標(biāo)-為保證互換性（與設(shè)備無

關(guān)）而定義的輔助坐標(biāo)

第五章基本圖形生成算法

坐標(biāo)系統(tǒng)5

ModelingCoordinate

LocalCoordinateNormalizedDeviceCoordinate

MasterCoordinateWorldCoordinateCoordinateScreenCoordinate

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換

光柵掃描顯示下畫直線存在的問題：

(1)顯示速度問題：

例：分辨率：1024x768,24Bit彩色，

幀存容量：1024x768x3=2,359,296Byte

刷新車85Hz:85x2,359,296=200,540,160(Byte/S)

存儲器讀出時間：?5ns

(2)顯示質(zhì)量問題：

■階梯狀

■線的粗細(xì)不

■線的亮度差異

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換7

直線的繪制要求：

1.直線要直

2.直線的端點(diǎn)要準(zhǔn)確，即無定向性和斷裂情況

3.直線的亮度、色澤要均勻

4.畫線的速度要快

5.要求直線具有不同的色澤、亮度、線型等

解決的問題：

給定直線兩端點(diǎn)P。(x0,y0)和Pi(xpy),畫出該直線o

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換8

5.1.1數(shù)值微分法（DDA法）

直線的微分方程：

DDA算法原理：

y

X,=X+￡?△X

I4-1Z

X

￡=l/max(|Ax|,|Ay|)圖5-2DDA算法原理

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換9

5.1.1數(shù)值微分法（DDA法）

max(|Ax|9|Ay|)=|Ax|,即|k0的情況:

i

9+1=%+￡?△%=壬+----4=J±1

△x

1

+￡+

yi+i=yi-=yi--------Ay=y.±k

Ax

max(|Ax|z|Ay|)=|Ay|,此時|k|ZL

ii

X,=X+￡-AX=X+?△X=X±-

Z+1III

Ayk

1

匕+]=匕+￡?AJ=匕+----?Ay=y7.±i

△y

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換10

5.1.1數(shù)值微分法（DDA法）

注意：round(x)=(int)(x+0.5)

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換11

5.1.1數(shù)值微分法（DDA法）

VoidDDAIine(intxOJntyO,intx1,inty1)

(

intdx,dy,eps1,k;

floatx,y,xlncre,ylncre;

dx=x1-x0;dy=y1-y0;

x=xO;y=yO;

If(abs(dx)>abs(dy))eps1=abs(dx);

elseeps1=abs(dy);

xlncre=(float)dy/(float)eps1;

ylncre=(float)dy/(float)eps1;

for(k=0;k<=eps1;k++){

putpixel((int)(x+0,5),(int)(y+0.5));

x+=xlncre;

y+=ylncre;

)

)

第五章基本圖形生成算法

直線的掃描轉(zhuǎn)換

5.112

5.1.1數(shù)值微分法（DDA法）

特點(diǎn)：

增量算法■!

缺點(diǎn)：

浮點(diǎn)運(yùn)算、取整一一》廢時，且不利于硬件實現(xiàn)。

不利于用硬件實現(xiàn)

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換

5.1.2中點(diǎn)畫線法算法

5.1.2中點(diǎn)畫線法算法

原理：

假定直線斜率KvL且已確定

點(diǎn)亮象素點(diǎn)P(Xp,Yp)

M為中點(diǎn)，Q為交點(diǎn)

現(xiàn)需確定下一個點(diǎn)亮的象素。

圖5-5Brensemham算法生成直線的原理

顯然可得出如下結(jié)論：若M在Q的下方，選Pu,否則選Pd

k______________________________________________________)

第五章基本圖形生成算法

直線的掃描轉(zhuǎn)換

5.114

5.1.2中點(diǎn)畫線法算法

算法實現(xiàn)：

假設(shè)直線的起點(diǎn)、終點(diǎn)分別為：(XO,YO),(X1,Y1)

該直線方程可表示為：.

F(x,y)=a*x+b*y+c(1)

其中：a=YO-Yl,b=XLXO,c=XO*Yl-Xl*YO

當(dāng)：F(Xt,Yt)=0一(Xt,Yt)在直線上

F(Xt,Yt)v0一(Xt,Yt)在直線下方

F(Xt9Yt)>0T(Xt,Yt)在直線上方

第五章基本圖形生成算法

圖5-4直線將平面分為三個區(qū)域

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換16

5.1.2中點(diǎn)畫線法算法

因此：將中點(diǎn)M坐標(biāo)代入(

1)式，并判斷其符號即

可確定象素點(diǎn)的選取。構(gòu)

造如下判別式：

d=F(M)

=F(Xp+l,Yp+0.5)

=a(Xp+l)+b(Yp+0.5)+c

由上式可看出，d是x,y線

性函數(shù)，可推導(dǎo)d的增量

公式

歹=<

[y(d>o)

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換

5.1.2中點(diǎn)畫線法算法

誤差項的遞推

d<0：

h_____________

9

當(dāng)d〈0時，取象素Pu,此時

Pu(X1+2,yi+1.5)

_______J______

再下一個象素的判別式為：9Q

(

F=F(Xp+2,Yp+L5)(Xi+1,yi+o..5)

=a(Xp+2)+b(Yp+1.5)+c(xi?yi)p：

=a(Xp+l)+b(Yp+0.5)+c+a+b

=d+a+b;d<0

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換18

5.1.2中點(diǎn)畫線法算法

誤差項的遞推

d>0：

當(dāng)d>=0時，取象素Pd,此

_____P_u41_____

時再下一個象素的判別式「xi+2：yi+0.5)

))1

%：(Xi+1,yi+o.；

—：_0_：_o-----(

T=F(Xp+29Yp+0.5)(Xi,yi)Pd

=a(Xp+2)+b(Yp+0.5)+c

=a(Xp+l)+b(Yp+0.5)+c+ad)>=0

=d+a;

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換19

5.1.2中點(diǎn)畫線法算法

d的初始值可按下式計算：

dO=F(X0+l,Y0+0.5)

=a(X0+l)+b(Y0+0.5)+c

=F(X0,Y0)+a+0.5b

=a+0.5b

由于只用d的符號作判斷，為了只包含整數(shù)運(yùn)算,

可取2d代替d,這樣可得如下中點(diǎn)算法程序：

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換20

5.1.2中點(diǎn)畫線法算法

MidpointLine(X0,Y0,XI,Yl,Color)

intX0,Y0,XI,Yl,Color;

(

inta,b,dl,d2,d,x,y;

a=Y0-Yl;b=Xl-X0;

d=a+a+b;

dl=a+a;

d2=a+b+a+b;

x=X0;y=Y0;

drawpixle(x,y,Color);

while(x<Xl){

if(d<0){

x++;y++;

d+=d2;

}

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換21

5.1.2中點(diǎn)畫線法算法

else{

x++;

d+=dl;

}

drawpixle(x,y,Color);

}/*while*/

}/*MidPointLine*/

按照中點(diǎn)劃線算法，確定直線(0,0)(5,3)的點(diǎn)

亮象素。列出計算過程，并列出所選象素坐標(biāo)。

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換22

5.1.3Bresenham畫線算法

5.1.3改進(jìn)的Bresenham算法

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換23

5.1.3Bresenham畫線算法

假定直線斜率,O〈kvl,起點(diǎn)坐壬+i=/+1

標(biāo)為(x,y);3+18>0.5)

匕+i=<

下一個點(diǎn)亮象素可能是：［兀(d<0.5)

(x+l,y)或(x+l,y+l)。這可

通過d值的大小來確定：

誤差項的計算

d=d+k,當(dāng)d>l時d=d-l;

?d初=0,

當(dāng)d<0.5取(x+l,y),否則取

?每走一步：d=d+k

(x+l,y+l)o

?方向上走了三”>

d=d-l

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換24

5.1.3Bresenham畫線算法

算法步驟：

1.輸入直線的兩端點(diǎn)Po(X0,y0)和P[(X],y1)。

2.計算初始值A(chǔ)x、Ay>d=0>x=x0>y=y0o

.繪制點(diǎn)o

4.d更新為d+k,判斷d的符號。若d>0.5,則(x,y)更新為

(x+l,y+l),同時將d更新為d?1；否則(x,y)更新為(x+1,y)。

5.當(dāng)直線沒有畫完時，重復(fù)步驟3和4。否則結(jié)束。

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換25

5.1.3Bresenham畫線算法

x,=x+1

Z+1Z

改進(jìn)1：令e=d-0.5<'兒.+1(e>0)

兀+i=<

〔兀（e<。）

?e初=?0.5,

?每走一步有e=e+ko

?if(e>0)thene=e-l

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換26

5.1.3Bresenham畫線算法

算法步驟為：

L輸入直線的兩端點(diǎn)Po(Xo，y。)和Pi(Xi，yJ。

2.計算初始值△、、Ay>^e=-O.57^x=xo>y=y0o

3.繪制點(diǎn)(x,y)o

4.e更新坦判斷e的符號。若e>0,則(x,y)更新為

(x+Ly+1),同時將e更畿棗三￡)否則(x,y)更新為(x+l,y)。

5.當(dāng)直線沒有畫完時，重復(fù)步驟3和4。否則結(jié)束。

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換27

5.1.3Bresenham畫線算法

改進(jìn)2：用2eZ\x來替換e

€初="Ax,

每走一步有e=e+2△y。

if(e>0)thene=e-2Ax

第五章基本圖形生成算法

5.1直線的掃描轉(zhuǎn)換28

5.1.3Bresenham畫線算法

算法步驟：

1.輸入直線的兩端點(diǎn)Po(Xo，y°)和Pi(Xi洶)o

2.計算初始值△*、N、《21)x=x0、y=y0o

3.繪制點(diǎn)(x,y)o

4.e更新為阡涇“判斷e的符號。若e>0,則(x,y)更新為

(x+Ly+1),同時將e更新為日入“否則(x,y)更新為(x+l,y)。

5.當(dāng)直線沒有畫完時，重復(fù)步驟3和4。否則結(jié)束。

程序如下:BresenhamLine(xO,yO,xl,yl,color)

intxO,yO,xl,yl,color;

(

intx,y,dx,dy;

floatk,e;

dx=xl-xO;

dy=yi-yO；

k=dy/dx;

e=-0.5;x=x0;y=yO;e=-dx;

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

drawpixel(x,y,color);

x++;e=e+k;el=e-0.5;e=e+2*dy;el=e-dx;

if(el>0)e=e-1;e=e-2*dx;

if(e>=0)y++;

)

)

Bresenham圓線例

直線端點(diǎn)為(20,10)和(30,18),用Bresenham法畫線

解：Ax=10,Ay=8,=Ay/Ax=0.8,2Ay=16,2Ax=20

分=-Ax=—10

畫初始點(diǎn)(20,10),并根據(jù)判別式確定沿線段路徑的后續(xù)像素位置如下表:

ie'ti+1)

19

06(21,11)

12(22,12)■

2-2(23,12)?

314(24,13)??

410(25,14)?

56(26,15)

62(27,16)?

12??

7-2(28,16)11

814(29,17)?

10.

910(20,18)2021222324252627282930

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換31

5.2.1圓的對稱性

利用八分圓的對稱性特點(diǎn)

,可以簡化圓的掃描轉(zhuǎn)

換算法。

如果圓的圓心在原點(diǎn)，則

可以由其中某個八分圓

的圓周上的某點(diǎn)（x,y

）計算出其他七個八分

圓圓周上對應(yīng)的點(diǎn)的坐

標(biāo)。

由此可構(gòu)造相應(yīng)算法，由

圖中陰影的圓周復(fù)制生

成整個圓周。

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換32

5.2.1圓的對稱性

算法如下：

intCircle_Points(x,y,value)

intx,y,value;

{drawpixel(x,y,value);

drawpixel(x,-y,value);

drawpixel(-x,y,value);

drawpixel(-x,-y,value);

drawpixel(y,x,value);

drawpixel(-y,x,value);

drawpixel(y,value);

drawpixel(-y,value);

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換33

5.2.2角度DDA畫圓算法

1、角度DDA法

若已知圓的方程：x+y=R

下=Xo+Rcos0

iy=y0+Rsin0

jdx=-Rsin0d0

[dy=Rcos0d0

jXn+1=xn+dx

iyn+i=yn+dy

(xn+i=xn-(yn-yo)d0

iyn+i=yn+(xn-xo)d0

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換34

5.2.2角度DDA畫圓算法

角增量0(弧度)的選?。篸e=e/(n-l)

n越大，點(diǎn)越多，速度越慢。所以在不同的精度下，對于不

同的半徑給定不同的de：

使max(|Ax|,|Ay|)<1

因：Ax=-(yn-yO)d0

Ay=(xn-xO)d0

即max(|(yn-yO)dO\,|(xn-xO)d0|)<1

又因為|yn-yO|,|xn-xO|最大是R

所以：R|dO|<1^>|de|<l/R

絕對值表示畫圓弧有順時針和逆時針之別，

為精度計，取|d0|=1/(R+1)

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換35

5.2.2角度DDA畫圓算法

算法：

Arc-dda(xc,yc,r,al,a2,color)

intxc,yc,r,color；

doubleal,a2；

{inti,steps,x,y；

doubleda,radin;

da=l/(r+l)；

radin=a2-al;steps=radin/da;

x=r*cos(al);y=r*Sin(al);

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

{drawpixel(x+xc,y+yc,color);

x=x-y*da;y=y+x*da;

}

)

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換

5.2.3中點(diǎn)畫圓法

利用圓的對稱性，只須討論1/8圓（第一象限

中的第二個八分圓）。

解決問題：

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換

5.2.3中點(diǎn)畫圓法

基本原理：假設(shè)P(Xp+1,Yp)為當(dāng)前點(diǎn)亮象

素，那么，下一個點(diǎn)亮的象素可能是P1

(Xp+1,Yp)或P2(Xp+1,Yp+l)o

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換38

5.2.3中點(diǎn)畫圓法

2)推導(dǎo)過程：

①構(gòu)造一函數(shù)：

222

F(X,Y)=X+Y-R

F(X,Y)=0(X,Y)在圓上；

F(X,Y)<0(X,Y)在圓內(nèi)；

F(X,Y)>0(X,Y)在圓外。

M為Pl、P2間的中點(diǎn)，M=(Xp+l,Yp?0?5)

有如下結(jié)論：

F(M)<0取P1

F(M)>=0取P2

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換39

5.2.3中點(diǎn)畫圓法

②構(gòu)造判別式d=F(M)=F(xp+1,yp-0.5)

222

=(xp+1)+(yP-0.5)-R

若d<0,則Pl為下一個象素，那么再

下一個象素的判別式為：

pPl

yi-----<)----------cp---1i--------

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

222

=(x+2)+(y-0.5)-Ryii-----------()---4k---

ppP2

=d+2xp+3yi乙

即d的增量為2xp+3.

XiX：+1X：L+2

(a)d<=C)的情;兄

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換

5.2.3中點(diǎn)畫圓法

若d>=0,則P2為下一個象素，那

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

pPI

d=F(xp+2,yp-1.5)yi---------\bi-------J

222

=(xp+2)+(yp-1.5)-R

yii)P2，1----

=d+2(xp-yp)+5

即d的增量為2(xp?yp)+5.

yi41----

③計算d的初值：X：1Xi+lx:i+2

dO=F(l9R-0.5)(b)d>0儕J情況

=1+(R-0.5)2-R2

=1.25-R

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換41

5.2.3中點(diǎn)畫圓法

算法步驟：

L輸入圓的半徑R。

計算初始值、

2.251)x=0y=Ro

3.繪制點(diǎn)(x,y逆其W分圓中的另外七個對稱點(diǎn)。

4.判斷d的符號。若dWO,則先將d更新式叵吟

再將(X,y)更新為(x+1,y)；否則先日才更新4

(x-y再將(x,y)更新為(x+1,y-1)。

5.當(dāng)x〈y時，重復(fù)步驟3和4。否則結(jié)束。

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換42

5.2.3中點(diǎn)畫圓法

MidpointCircle(r,color)

intr,color;

{

intx,y;

floatd;

x=0;y=r;d=1.25-r;else

drawpixel(x,y,color);

while(x<y)d+=2*(x-y)+5;

{x++;y-;

if(d<0)

(

d+=2*x+3;x++；

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換43

5.2.3中點(diǎn)畫圓法

改進(jìn)1：用d-O.25代替d^e=d-0,25=>e=1-R

隹?■:土取貝Ud<0e<—0.25

舁/玄少麻：而e為整數(shù)，則e<—0.25等價

1.輸入圓的半徑R。于e<0o再將e仍用d來表示

2.計算初始喳E)x=0、y=Ro

3.繪制點(diǎn)(x,y)及其在八分圓中的另外七個對稱點(diǎn)。

4.判斷d的符號。函三Q則先將d更新為d+2x+3,再

將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-

y)+5,再將(x,y)更新為(x+1,y-1)。

5.當(dāng)x<y時，重復(fù)步驟3和4。否則結(jié)束。

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換44

5.2.3中點(diǎn)畫圓法

改進(jìn)2：因判別式d的增量是x,y的線性函數(shù)。

每當(dāng)x遞增1,d遞增Ax=2；

每當(dāng)y遞增1,d遞減Ay=2；

由于初始象素為（0,r）,所以Ax的初

值為3,Ay的初值為一2r+2。再注意到乘2運(yùn)

算可以改用加法實現(xiàn)，至此我們可寫出不含乘

法，僅用整數(shù)實現(xiàn)的中點(diǎn)畫圓算法。

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換45

5.2.3中點(diǎn)畫圓法

MidpointCircle(r,color)if(d<0)

intr,color;(

d+=deltax;

(

deltax+=2;x++；

intx,y,deltax,deltay,d;

)

x=0;y=r;d=l-r;else

deltax=3;deltay=2-r-r;(

drawpixel(x,y,color);d+=(deltax+deltay);

while(x<y)deltax+=2;deltay+=2;

x++;y-;

例題：畫第一象限中，半徑R=10,圓心在原點(diǎn)的圓弧

46

III

1---A-

解:起點(diǎn)為(x0,y0)=(0,10)9

8___L

e0=—R=-%(x19y1)=(l,10)

7---r

e1=e。+2x°+3=-6；(x,y)=(2,10)

226___L

e2=ej+2xj+3=-1；(x3,y3)=(3,10)5---r

4---L

e3=e2+2X2+3=6；(x4,y4)=(4,9)(

3II

TTT

------rI-

e=e+2(X-y)+5=-3；(x,y)=(5,9)I

4333552-4++

「一一「I-

I

-

111

；一

e5=e4+2x4+3=8(x6,y6)=(6,8)___L-

-

e=e+2(X5—y)+5=5；(x,y)=(7,7)

655770

123456

若e<09->ei+1=G+2Q+3

e>=09->ei+1=%+2(Xf~yt)+5

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換47

5.2.3Bresenham畫圓法

5.2.3.Bresenham圓圓算法

為討論方便，僅考慮圓心在原點(diǎn)，半徑為R的第一象限

上的一段圓弧。且?。?,R）為起點(diǎn)，按順時針方向

繪制該1/4圓弧。

V(x,y-1)D(x+1,y-1)

Figure2

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換48

5.2.3Bresenham畫圓法

原理：

如圖1?3所示,從當(dāng)前點(diǎn)

亮象素出發(fā)，按順時針

方向生成圓時，最佳逼

近該圓的下三個象素只

可能為H、D、V三象素

之一。H、D、V中距圓

周邊界距離最小者，即

為所求的象素點(diǎn)。

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換49

5.2.3Bresenham畫圓法

算法：

H、D、V三點(diǎn)到圓心的距離平方與圓的半徑平

方差，即為H、D、V到圓弧距離的一種度量：

222

AH=(x+1)+y-R；

222-----

AD=(X+1)+(y-1)-R;了

222

Av=x+(y-1)-R;(X,y)]—匚3

------?——OH

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換50

5.2.3Bresenham畫圓法

為了根據(jù)這些度量值可確定最佳象素

點(diǎn)，首先，將H、D、V與理想圓

弧的關(guān)系進(jìn)行分類。

存在以下五種情況：

1)H、D、V全在圓內(nèi)；

2)H在圓外，D、V在圓內(nèi)；Figure3

3)D在圓上，H在圓外，V在圓內(nèi)；

4)H、D在圓外，V在圓內(nèi)；

5)H、D、V全在圓外。

與Bresenham畫線算法一樣，按照上述不同類型

,找出誤差度量的遞推公式，然后判別它的正、

負(fù)性即可確定最佳逼近的象素點(diǎn)。

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換51

5.2.3Bresenham畫圓法

當(dāng)AD<0,只可能為1或2種情況。為了確定是H

還是D,可用如下判別式：

=

8HD|AH|-|AD|

6HD<0則應(yīng)選H,否則選D。

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換52

5.2.3Bresenham畫圓法

對于第2種情況：

SHD=AH+AD

2222

=(x+1)+y-R+(x+l)+(y-l)-R

=2Ap+2y-1

對于第1種情況：

Vy是x的單調(diào)遞減函數(shù)

??.H為下一點(diǎn)亮象素。

另，止匕時AHvO和AD<0

△H+Ap=2AJ)+2y-1v0

綜上兩種情況可得如下結(jié)論：

在時，若2(A.+y)?lWO,則取H,

否則取力

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換53

5.2.3Bresenham畫圓法

當(dāng)AD>0,只可能有4、5兩種情況。且最佳象素

點(diǎn)為D或V,可用如下判別式：

SDV=|AD|-|Ay|

6DV<0則應(yīng)選D,否則選V。

對于第4種情況：

6DV=AD+Ay(AD>0,Ay<0)

222222

=(x+l)+(y-1)-R+(x)+(y-1)-R

=2(AD-x)-1----?

對于第5種情況：(x4

D,V都在圓外，顯然v為所選象素。上2

A>O,A>O

注意：vDVkXkpkn.

F，8Ure3

AAD+AV=2(AD-X)-1>0下「

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換54

5.2.3Bresenham畫圓法

綜上兩種情況可得如下結(jié)論：

在AQ〉O時，若2則取D,

否則取V

當(dāng)AD=0此時D是最佳象素。

總結(jié)上述分析結(jié)果：

當(dāng)AD〉0，若2(AD-X)?1>0,取V,否則取D

當(dāng)AD<0,若2(AD+y)」W0，取H,否則取D

當(dāng)AD=0,取D。

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換55

5.2.3Bresenham畫圓法

關(guān)鍵的問題就是計算AD(見An的計算公式)

采用增量法，獲得AD的計算公會。

分三種情況：HM

下一象素為H時，則—一

H=(x',y')=(x+l,y)

222

AD'=((x+l)+l)+(y-l)-R

222

=(x+l)+(y-1)-R+2(x+l)+1

=AD+2(X+1)+1

=AD+2x'+1

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換56

5.2.3Bresenham畫圓法

下一象素為D時

D=(x',y')=(x+l,y?l)

222

AD=((X+1)+1)+((y-l)-l)-R

222

=(x+l)+(y-1)-R+2(x+l)-2(y-l)+1

=AD+2(x+l)-2(y-l)+2

、1

下一象素為V時H

-2

V=(x\y5)=(x,y-1)

222

AD=(X+1)+((y-l)-l)-RDFigure3

222

=(X+1)+(y-1)-R-2(y-l)+1

=AD-2(y-l)+13

第五章基本圖形生成算法

5.2圓的掃描轉(zhuǎn)換57

5.2.3Bresenham畫圓法

有了上述AD的遞推計算公式，還需計算出AD的

初值。

?.*圓弧的起點(diǎn)為(0,R)

，AD的初值為：；一

222

AD=(0+1)+(R-I)-R

=2(1-R)

BresenhamCircle(r,color)

intr,color;

(

intx,y,delta,dl,d2,dir

x=0;y=r;

delta=2*(1-r)

while(y>=0){

drawpixel(x,y,color);

if(delta<0){

dl=2*(delta+y)-1;

if(dl<=0)dir=1;

elsedir=2;

)

elseif(delta>0){

d2=2*(delta-x)-l;

if(d2v=0)dir=2;

elsedir=3;

elsedir=2;

switch(dir){

caseX:

x++;

delta+=2*x+1;

break;

case2:

x++;Y—;

delta+=2*(x-y+1)+1;

break;

case3:

delta+=-2*y+1;

break;

}/*endofswitch*/

}/*endofwhile*/

}/*endofBresenhamCircle*/

第五章基本圖形生成算法

5.3橢圓的掃描轉(zhuǎn)換60

圖5-14長半軸為a,短半軸為b的標(biāo)準(zhǔn)橢圓

?:?對于橢圓上的點(diǎn),有

F(x,y)=0；

222222

F(x,y)=bx+ay—ab0

?:?對于橢圓外的點(diǎn),F(x,y)>0；

?:?對于橢圓內(nèi)的點(diǎn),F(x,y)<0o

第五章基本圖形生成算法

5.3橢圓的掃描轉(zhuǎn)換61

解決問題:

第五章基本圖形生成算法

5.3橢圓的掃描轉(zhuǎn)換62

橢圓方程廠（》,y）=/J+°2y2一°2b2=。

x分量

圖5-15第一象限的橢圓弧

分界點(diǎn)：法向量兩分量相等的點(diǎn)，以弧上斜率為一1的點(diǎn)

第五章基本圖形生成算法

5.3橢圓的掃描轉(zhuǎn)換63

當(dāng)前點(diǎn)P(Xj,yj)

候選點(diǎn)Pu(Xj+1,y()

Pd(Xj+1,yj-1)

中點(diǎn)(Xj+1,y-Q.5)

圖5-16中點(diǎn)橢圓繪制算法的原理

引理57：若在當(dāng)前中點(diǎn),法向量的y分量比x分量大，即

2

(x,+1)<a(y.-0.5)

則說明橢圓弧從上部分轉(zhuǎn)入下部分。

第五章基本圖形生成算法

5.3橢圓的掃描轉(zhuǎn)換64

5.3.1橢圓的中點(diǎn)Bresenham算法

5.3.1橢圓的中點(diǎn)Bresenham算法

圖5-16中點(diǎn)橢圓繪制算法的原理

先推導(dǎo)上半部分的橢圓繪制公式

再推導(dǎo)下半部分的橢繪制公式

第五章基本圖形生成算法

5.3橢圓的掃描轉(zhuǎn)換65

5.3.1橢圓的中點(diǎn)Bresenham算法

先推導(dǎo)上半部分的橢圓園繪制公式

判別式誤差項的遞推判別式的初值

第五章基本圖形生成算法

5.3橢圓的掃描轉(zhuǎn)換66

5.3.1橢圓的中點(diǎn)Bresenham算法

判別式

222222

d]=F{x,+l,yz.—0.5)=b(x+1)+a{y.-0.5)—ab

?:?若(1口0,取PG+la)

5-17上半部分橢圓弧的繪制原理

第五章基本圖形生成算法

5.3橢圓的掃描轉(zhuǎn)換67

5.3.1橢圓的中點(diǎn)Bresenham算法

誤差項的遞推P

yi---------?——?-------Q----------

222222

d1=F(X,+\,y.-0.5)=b(x.+1)+a()；-0.5)-ab---------------

yi-1------------------------<1——<1------

yi-2------------------------------------------------------

情況一：

xixi+1xi+2

d[W0：(a)d<=0的情況

222222

di=F(x,+2,、/—0.5)=b(x,+2)+a(y.—0.5)—ab

,2,,22,,22,2,2

=b(x.+\)++a(y.—0.5)—ab+b(2x.+3)

2

=d、+b(2x.+3)

第五章基本圖形生成算法

5.3橢圓的掃描轉(zhuǎn)換

5.3.1橢圓的中點(diǎn)Bresenham算法

誤差項的遞推yi_

■,2,22,22,2

7

d}-7(x.+l,j;.-0.5)=b(x.+1)+a(y.-0.5)-ab------

yi-1----------------9------Q

yi-2------------------------19-----

情況二:

xixi+1xi+2

d"：