【計(jì)算機(jī)圖形學(xué)】基本圖形（元）生成技術(shù)

第4章基本圖形（元）生成技術(shù)

提綱：

1.直線生成技術(shù)；

2.圓與橢圓生成技術(shù)

?我們知道，光柵圖形顯示器是一個(gè)像素矩陣，如

分辨率為640X480,每個(gè)像素可以用一種或多種

顏色顯&會別稱為單色顯示器或彩色顯示器。

在光柵顯示器上顯示加何一種圖形，實(shí)際上都

是具有一種或多種顏色的像素的集合。確定一個(gè)

像素集合及其顏色，用于顯示一個(gè)圖形的過程，

稱為圖形的掃描轉(zhuǎn)換或光柵化，也叫圖形的生成

實(shí)際上，圖形生成是根據(jù)圖形的幾何信息和屬性

信息，結(jié)合圖形生成算法，計(jì)算出要顯示的中間

像素，而不像圖像生成是保存了圖像的每一像素

點(diǎn)的信息。所以，基本圖形的生成，首先要根據(jù)

基本圖形的特征找出它的幾何信息，然后根據(jù)一

定的生成算法實(shí)時(shí)地在顯示器上顯示出完整的圖

形。

?圖形掃描轉(zhuǎn)換一般分為兩個(gè)步驟：先確

定有關(guān)像素，再用圖形的顏色或其它屬

性對象素進(jìn)行某種寫操作。后者通常是

通過調(diào)用設(shè)備驅(qū)動程序來實(shí)現(xiàn)的。所以

掃描轉(zhuǎn)換的主要任務(wù)就是確定最佳逼近

于圖形的像素集的生成算法。

■本章主要討論基本圖形的掃描轉(zhuǎn)換問題,

包括：

?（1）一維直線、圓、橢圓的生成；

?（2）二維圖形（多邊形）的填充；

?（3）字符的表示和輸入輸出；

?（4）圖形的裁剪和反走樣技術(shù)；

?在一個(gè)圖形系統(tǒng)中，基本圖形（也稱為

圖元＞圖素等）的生成技術(shù)是最基本的

‘任何復(fù)雜的圖形都是由基本圖形組成的

基本圖形生成的質(zhì)量直接影響該圖形系

統(tǒng)繪圖的質(zhì)量。所以，需要設(shè)計(jì)出精確

的基本圖形生成算法，以確保圖形系統(tǒng)

繪圖的精確性。

4.1直線圖形的生成技術(shù)

?在數(shù)學(xué)上，兩個(gè)坐標(biāo)點(diǎn)可以確定出一條

直線，理想的直線是沒有寬度的，由無

數(shù)個(gè)點(diǎn)構(gòu)成的。在光柵圖形顯示器上顯

示一條直線時(shí)，只能在顯示器給定的有

限像素組成的矩陣中，確定最佳逼近于

該直線的一組像素點(diǎn)來表示，這就是直

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

?在繪制斜線時(shí)，有些點(diǎn)不一定正好落在

像素點(diǎn)上，直線掃描轉(zhuǎn)換算法必須確定

哪一個(gè)像素點(diǎn)來顯示，從而形成“梯形

線”。當(dāng)顯示器分辯率很高時(shí)，仍可以

生成高質(zhì)量的直線。

?本節(jié)主要介紹三種創(chuàng)用的直線生成算法,

即數(shù)值微分法(DDA)、中點(diǎn)畫線法和

Bresenham算法。這三種算法都是只考慮

一個(gè)像素寬的直線，生成直線算法的函

數(shù)形式如下：Line(xO,yO,xl,yl,color);

4.1.1數(shù)值微分法

1.原理

數(shù)值微分法(DDA,DigitalDifferentialAnalysis

)是根據(jù)數(shù)學(xué)上直線的微分方程來設(shè)計(jì)的。設(shè)

A(xO,yO),B(xl,yl)是直線的端點(diǎn)坐標(biāo)，首先計(jì)算

出直線的斜率

k=dy/dx=Ay/Ax=(yl-yO)/(xl-xO)

直線方程為：y=kx+B晟x=l/k.y+T

當(dāng)|k|sl時(shí)，讓x每步增加1,y最多增加1,

然后用四舍五入的方法來確定直線上的

像素位置為(x9round(y))。設(shè)當(dāng)前點(diǎn)為

(毛,牛),則下一個(gè)像素J]=%+1,則

九1=kxi+1+B

=k(Xj+l)+B=(kXj+B)+k

=%+k

即當(dāng)x每遞增1時(shí)，y遞增斜率k。

當(dāng)lkl>l時(shí)，應(yīng)當(dāng)讓y每步遞增1,這時(shí)x最多

增加1,然后然后用四舍五入的方法來確

定直線上的像素位置為(round(x),y)。設(shè)

當(dāng)前點(diǎn)為(為4)，則下一個(gè)像素yi+i=乂+1

，則

=l/k.(yi+l)+T=(l/k+T)+l/k

=Xj+l/k

即當(dāng)y每遞增1時(shí)，x遞增斜率1/k。

DDALine(xO,yO,xl,yl,color)

intxO,yO,xl,yl,color;

intlength,i;

floatx,y,dx,dy;

length=abs(x1-xO);

ifabs(y1-yO)>length

length=abs(y1-yO);

dx=(xl-xO)/length;

dy=(y1-yO)/length;

x=x0+0.5;y=y0+0.5;//實(shí)現(xiàn)四舍五入

for(i=1;i<=length;i++)

(

putpixel(int(x),int(y),color);

x=x+dx;

y=y+dy;

)

4.1.2中點(diǎn)畫線法

中點(diǎn)畫線算法示意圖

L原理:

?設(shè)點(diǎn)前百為PKyJ」只考慮直線斜率在

?0、1之間時(shí)，若直線在x方向上增加一個(gè)

?單位，則在y方向上增量只能在0、1之間。

?下一個(gè)像點(diǎn)只可能是P1((Xj+1,y)或

P2((xi+15yi+1)o

?在以M表示P1和P2的中點(diǎn)，即

M((Xj+1,yj+0.5)。

?又設(shè)Q是理想直線與x=xi+1的交點(diǎn)，

?當(dāng)M在Q的下方，則取P2為下一個(gè)像素；

否則，取P1為下一個(gè)像素位置。

2.遞推公式和算法

［假設(shè)直線的起之和終點(diǎn)分別為(xO5yO)

和(x1,y1),則直線方程為：

?F(x5y)=ax+by+c=O即(y-

yO)/(x-xO)=(y1-yO)/(x1-xO)

?其中，a=yO-y15b=x1-xO5c=xOy1-x1yO□

?對于直線中的點(diǎn)，則有F(x,y)=O;對于直

線上方的點(diǎn)，則有F(x,y)>0;對于直線下

方的點(diǎn)，則有F(x,y)vO。

■判斷中點(diǎn)M在Q的上方，還是

在下方，只要將中點(diǎn)坐標(biāo)

M(xi+1用+0.5)代入F(x,y)方程

中，并判斷它的符號。構(gòu)造判

別式

?d=F(M)=F(Xj+1,yj+0.5)=a((xs+1)+b(yj+0.5)+c

?當(dāng)ckO時(shí)，表示M在直線的下方，則取P2為下

一點(diǎn)；當(dāng)d>0時(shí)，表示M在直線的上方，則取

P1為下一點(diǎn)；當(dāng)d=0時(shí)，表示M在直線中，取

P1或P2均可，我們約定取P1。

遞推式子

?(X)當(dāng)d>=0時(shí)，取P1為下一個(gè)像素點(diǎn)，

欲判斷再下一個(gè)像素，應(yīng)計(jì)算

?d1=F(M1)=F((xi+2,yi+0.5)=a(xi+2)+b(yi+0.5)+

c=d+a

?即d的增量△d=a

?(2)當(dāng)dvO時(shí)，取P2為下一個(gè)像素點(diǎn)，欲

判斷再下一個(gè)像素，應(yīng)計(jì)算

?d2=F(M2)=F((xi+25yi+1.5)=a(xi+2)+b(yi+1.5)+

c=d+a+b

?即d的增量△d=a+b

MidPointLine(xO,yO,xl,yl,color)

intxO,yO,xl,yl,color;

inta,b,deltal,delta2,d,x,y;

a=yO-yl;b=xl-xO;

d=a+0.5*b;deltal=a;delta2=a+b;

x=xO;y=yO;

putpixel(x,y,color);

while(x<xl)

if(d<0)

x++;y++;

d+=delta2;〃取P2,并且計(jì)算下一點(diǎn)的d值

)

else

x++;

d+=deltal;〃取Pl,并且計(jì)算下一點(diǎn)的d值

)

putpixel(x,y,color);

)

備由于在整個(gè)算法中只考慮d的符號，而且

d的增量都是整數(shù)，只是起初值包含小數(shù),

因此，在算法中可以用2d代替d,從而去

掉小數(shù)。

?d0'=2d0=2a+b

?dr=2d1=2(d+a)=2d+2a,即Ad=2a

5

?d2=2d2=2(d+a+b)=2d+2a+2b5

?即△d=2(a+b)

?因此，算法中第3行可以替換為

?d=2*a+b;delta1=2*a;delta2=2*(a+b);

中點(diǎn)畫線法示圖

4.1.3Bresenham國線算法

?1.算法原理

?Bresenham算法是計(jì)算機(jī)圖形學(xué)領(lǐng)域中使用

最廣泛的直線生成技術(shù)。該算法適合于光柵圖

形顯示器、數(shù)字化儀設(shè)計(jì)等設(shè)備，其原理描述

如下：

?Bresenham也是通過在每列像素中確定與理

想直線最近的像素來進(jìn)行支線的掃描轉(zhuǎn)換的。

通過各行、各列像素中心構(gòu)造一組虛擬網(wǎng)格線,

按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直

網(wǎng)格線的交點(diǎn)，然后確定該列像素中與此交點(diǎn)

最近的像素。

?Bresenham算法與DDA算法類似，只是

不再采用四舍五入的辦法，而是巧妙地

采用了增量計(jì)算，使得對于每一列，只

要檢查一個(gè)誤差項(xiàng)的符號，就可以確定

該列所求的像素。

2.遞推公式

?設(shè)直線的起始點(diǎn)為(xO,yO)，終點(diǎn)為

(x15y1),貝U直線的斜率

?k=Ay/Ax=(yl-yO)/(xl-xO)

?考慮OWkW1的情況。

?在起始點(diǎn)(xO,yO),誤差項(xiàng)初值d=0;

?確定下一個(gè)像素點(diǎn)時(shí)，當(dāng)x遞增1時(shí)，誤差項(xiàng)

?d的值增加一個(gè)斜率k的值，即

?d=d+k

Bresenham算法示圖

?(1)當(dāng)企0.5時(shí)，取(x+1,y+1),>d=d-1；

*2)?Wdv0.5時(shí)，取(x+1,y)，誤差d值不變;

?令誤差e=d-0.5,則有

?(1)e=e+k,并且誤差e的初值，e=-0.5;

?(2)當(dāng)記0時(shí),取(x+1,y+1),>e=e-1；

?當(dāng)evO時(shí)，取(x+1,y)，誤差e值不變；

程序描述

?Bresenham_line(xOjyO5x1,y1,color)

?intx05y0,x1,y1,color;

int兄y,dx；dy,i：

floatk,e;

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

k=dy/dx;

e=-0.5;x=xO;y=yO;

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;

}

}

程序改進(jìn)：

L在每次號掣麗時(shí)得到都是小數(shù)，為了

便于硬件計(jì)算，取掉小數(shù)。由于算法只

需要用到誤差項(xiàng)e的符號，所以可以作如

下替換：

?設(shè)e'=2e=2(d?0.5)=2d?1,BPe=e72

?誤差e，的初值e?=-1,

?e=e+k替換為e72=e72+k5即2k

即可。

算法舉例：

?設(shè)直線的起點(diǎn)為（0,0）,終點(diǎn)為（5,

3）,按Bresenham算法計(jì)算并確定個(gè)

像素點(diǎn)位置。

?計(jì)算dx=5,dy=3,k=3/5=0.6,誤差e=-0.5;

?x=0,y=0

?(1)i=0:輸出像素(0,0)

x=1;e=e+k=-U：5+0,6=0.1>0,則有

y=y+1=13e=e-1=0.1-1=-09

?(2)i=1:輸出像素(1,1)

?x=2,e=e+k=-0.9+0.6=-0.3<0,貝

有y和e不變，BPy=15e=-0.3;

?(3)i=2:輸出像素(2,1)

?x=3,e=e+k=-0.3+0.6=0,3>0,貝U有

y=y+1=2,e=e-1=0.3-1=-0.7;

?(4)i=3:輸出像素(3,2)

有y和e不變,即y=2,e=-0.1;

?(5)i=4:輸出像素(4,2)

?x=5,e=e+k=-0.1+0.6=0.5>0,貝ll有

y=y+1=3,e=e-1=0.5-1=-0.5;

?(6)i=5:輸出像素(5,3)

?x=6,e=e+k=-0.5+0.6=。.1^^,貝口有

y=y+1=4,e=e-1=0.1-1=-0.9;

?程序結(jié)束。

4.1.4程序?qū)崿F(xiàn)與上機(jī)實(shí)踐（一）

?實(shí)驗(yàn)?zāi)康模豪肰isualC++實(shí)現(xiàn)三種直線生成

算法，驗(yàn)證算法的正確性；

?實(shí)驗(yàn)任務(wù)：

?1.理解三種直線生成算法思想，寫出實(shí)現(xiàn)程

序；

?2.添加鼠標(biāo)功能，實(shí)現(xiàn)交互式畫直線程序；

?3.將10個(gè)像差作為步距單位，編出

Bresenham算法的示例。

實(shí)驗(yàn)步驟：

?任務(wù)一：實(shí)現(xiàn)DDA畫線程序

?實(shí)驗(yàn)步驟：

?1.建立一個(gè)DDALine的工程文件；

?2.添加ddaline。成員函數(shù)

?方法：在工作區(qū)中選擇CLASSVIEW類窗

口，右擊CDDAIineView類,選擇“add

memberfunction…”，定義如卞的成員

函數(shù)：

?voidddaline(CDC*pDCJntxOJnt

yOJntx!Jnty!,COLORREFcolor);

編寫自定義的成員函數(shù)ddaline()程序

voidCDDALineView::ddaline(CDC*pDC,int

xO,intyO,intx1,inty1,COLORREFcolor)

?{

?intlength,!;

?floatx,y,dx,dy;

?length=abs(x1-x0);

?if(abs(y1-y0)>length)

?length=abs(y1-y0);

?dx=(x1-x0)/length;

?dy=(y1-y0)/length;

?x=x0+0.5;y=y0+0.5;

for(i=1;i<=length;i++)

(

pDC->SetPixel((int)x,(int)y,color);

x=x+dx;y=y+dy;

)

)

4.編寫OnDraw()函數(shù)

?voidCDDALineView::OnDraw(CDC*pDC)

?CDDALineDoc*pDoc=GetDocument();

?ASSERT_VALID(pDoc);

?//TODO:adddrawcodefornativedata

here

■

ddaline(pDC,100,100,400,100,RGB(255,0,0)

)；

■

ddaline(pDC,400,100,400,400,RGB0255Q)

)；

ddaline(pDC,400,400,100,400,RGB(0,0,255)

)；

■

ddaline(pDC,100,100,400,400,RGB(255,0,2

55));

■

ddaline(pDC,100,400,400,100,RGB(0,255,2

55));}

?}

?5.編譯、調(diào)試和運(yùn)行程序，查看程序結(jié)

果。

任務(wù)二、放大10倍后，算法演示程序

?先畫出(100,100)至I」(600,400)大

小為10的網(wǎng)格，然后從(100,100)以

10為單位，計(jì)算出直線上各個(gè)像素位置

?步驟：

?1.建立DDA2Line工程；

?2.在OnDraw()函數(shù)中畫出網(wǎng)格，并調(diào)

用DDA2Line()函數(shù)

?voidCDDA2LineView::OnDraw(CDC*

pDC)

?CDDA2LineDoc*pDoc

GetDocument();

?ASSERT_VALID(pDoc);

?//TODO:adddrawcodefornative

datahere

?//畫網(wǎng)格

Lintghgj;

?//畫橫線

fM

?pDC->TextOut(90590；(1005100));

?pDC->MoveTo(100,100);

?for(gj=100;gj<=400;gj=gj+10)

?(

?pDC->MoveTo(1005gj);

?pDC->LineTo(6005gj);

?}

〃畫豎線

pDC^>MoveTo(100,100);

for(gi=100;gi<=600;gi=gi+10)

(

pDC->MoveTo(gi,100);

pDC->LineTo(gi5400);

}

fM

pDC->TextOut(5905410；(6005400));

?//畫出像素點(diǎn)

?DDA2line(pDC,100J00,600,400,RG

B(255,0,0));

?}

3.添加DDA2Line()成員函數(shù)

?方法：在工作區(qū)中選擇CLASSVIEW類

窗口，右擊CDDAIineView類，選擇

“addmemberfunction…”，定義如下

的成員函數(shù)：

?voidDDA2Line(CDC*pDCJntxOJnt

yOJntx!Jnty15COLORREFcolor);

4.編寫DDA2Line()函數(shù)

?voidCDDA2LineView::DDA2line(CDC*pDC,intxO,

intyO,intx15inty15COLORREFcolor)

?{

?intlength5i,tx5ty;

?floatx5y5dx5dy;

?length=abs(x1-x0);

?if(abs(y1-yO)>length)

?Iength=abs(y1-yO);

dx=(fIoat)(x1-xO)/length;

dy=(fIoat)(y1-yO)/length;

//chartbuf[20];

,,,

//sprintf(tbuf/dx5dy=%f3%f5dx3dy);

//AfxMessageBox(tbuf);

x=xO;^=yO;

for(i=0;i<=length;i=i+10)

(

tx=(int)((x+5)/10)*10;

ty=(int)((y+5)/10)*10;

pDC->SetPixel(tx,ty,color);

pDC->Ellipse(tx-5,ty-55tx+5,ty+5);

x=x+dx*10;y=y+dy*10;

)

}

?5.調(diào)試、運(yùn)行程序

住務(wù)三二加入鼠標(biāo)功能，實(shí)現(xiàn)

?第一步：建立DDAMouseLine工程文件；

?第二步：向視圖類中添加自定義的成員變量

?用鼠標(biāo)右鍵單擊視圖類，選擇“Add

MemberVariable…”,添加下面三個(gè)成員變量。

?proctected:

?CPointm_p1;〃起點(diǎn)

?CPointm_p2;〃終點(diǎn)

?intmjst;//區(qū)別，mJst=0,表示直線

起點(diǎn)，

//mist=1,表示直線終點(diǎn)

?第三步：向視圖類中添加自定義的成員函數(shù)原

型：

Lpublic:

?voidDDAMouseLine(CDC*pDC,int

xO,intyO,intx1,inty1,COLORREFcolor);

?第四步：在視圖類CPP文件的構(gòu)造函數(shù)中初始

化成員變量。

?視圖類的構(gòu)造函數(shù)名與該視圖類的名字相

同。在視圖類中選擇構(gòu)造函數(shù)，如：

CDDAMouseLineView(),用鼠標(biāo)左鍵雙擊，

輸入下面程序代碼：

?CDDAMouseLineView::CDDAMouseLineVi

ew()

?(

?//TODO:addconstructioncodehere

?m_p1.x=0;m_p1.y=0;//起點(diǎn)

?m_p2.x=0;m_p2.y=0;〃終點(diǎn)

?m_ist=0;//0,第1點(diǎn)；1,第2點(diǎn)；

?}

第五步：在視圖類的OnDraw()

函數(shù)中加入下列代碼，實(shí)現(xiàn)視

?voidCMouseSpringView::OnDraw(CDC*pDC)

?(

?CMouseSpringDoc*pDoc=GetDocument();

?ASSERT_VALID(pDoc);

?//TODO:adddrawcodefornativedatahere

?pDC-

>SelectStockObject(NULL_BRUSH);

?DDAMouseLine(pDC,mpl.x.mpl.y.mp2.x,

m_p2.y,RGB(255,0,0));一一一

?〃調(diào)用自定義的成員函數(shù),用鼠標(biāo)畫直線

?}

第六步：向視圖類中添加鼠標(biāo)、

OnLButtonDown()函數(shù)消息響應(yīng)函數(shù)，

并輸入鼠標(biāo)處理程序代碼。

?voidCMouseSpringView::OnLButtonDown(UINTnFlags,

CPointpoint)

?(

?//TODO:Addyourmessagehandlercodehereand/or

calldefault

?CDC*pDC=GetDC();

?pDC->SelectStockObject(NULL_BRUSH);

?if(!mjst)//是起點(diǎn)

?(

?m_p1=m_p2=point;〃紀(jì)錄第一次單擊鼠標(biāo)位置，

定圓心

?m_ist++;

?}

?else

?(

?m_p2=point;〃記錄第二次單擊鼠標(biāo)的位置，定終

占的占

八、、MJ八、、

?mJst-;〃為新繪圖作準(zhǔn)備

DDAMouseLine(pDC.mpl.x.mpl.y.mp2.x,mp2.y.R

GB(255,0,0));//繪制新直線一一一一

?}

?ReleaseDC(pDC);//釋放設(shè)備環(huán)境

?CView::OnLButtonDown(nFlags,point);

?}

第七步：添加成員函數(shù)的程序代碼

?voidCDDAMouseLineView::DDAMouseLine(CDC*pDC,intxO,int

yO,intx1,inty1,COLORREFcolor)

?intlength,1;

?floatx,y,dx,dy;

?length=abs(x1-x0);

?if(abs(y1-y0)>length)

?Iength=abs(y1-yO);

?dx=(float)(x1-xO)/length;

?dy=(fIoat)(y1-yO)/length;

?x=x0+0.5;y=y0+0.5;

?for(i=1;i<=length;i++)

?{

?pDC->SetPixel((int)x,(int)y,color);

?x=x+dx;y=y+dy;

?}

?//pDC->MoveTo(xO,yO);

?//pDC->LineTo(x1sy1);

?}

第八步：編譯運(yùn)行程序，驗(yàn)證運(yùn)行結(jié)果。

?程序改進(jìn)，添加橡皮筋繪圖技術(shù)，實(shí)現(xiàn)交互式

畫直線。

'?向視圖類中添加鼠標(biāo)0nMouseMove()函數(shù)

1消息響應(yīng)函數(shù)，并輸入鼠標(biāo)處理程序代碼。

?voidCDDAMouseLineView::OnMouseMove(UINT

nFlags,CPointpoint)

?{

?//TODO:Addyourmessagehandlercode

hereand/orcalldefault

?CDC*pDC=GetDC();

?intnDrawmode=pDC->SetROP2(R2_NOT);〃設(shè)

置異或繪圖模式，并保存原來繪圖模式一

?pDC->SelectStockObject(NULL_BRUSH);

^if(m_ist==1)

?CPointprePntjCurPnt;

?prePnt=m_p2;〃獲得鼠標(biāo)所在的前一位置

?curPnt=point;

?〃繪制橡皮筋線

DDAMouseLine(pDC,m_p1.x,m_p1.yjprePnt.XjprePnt.y,

RGB(255,0,0));一一

?//DrawCircle(pDC,m_bO,prePnt);〃用異或模式重

復(fù)畫圓，擦出所畫的圓

DDAMouseLine(pDC,m_p1.x,m_p1.yjCurPnt.XjCurPnt.y,

RGB(255,0,0));一一

?//DrawCircle(pDC,m_bO,curPnt);//用當(dāng)前位置作為圓周上的

點(diǎn)畫圓

?m_p2=point;

?}

?pDC->SetROP2(nDrawmode);〃恢復(fù)原繪圖模式

?ReleaseDC(pDC);〃釋放設(shè)備環(huán)境

CView::OnMouseMove(nFlags,point);

}

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

?4.2.1圓的掃描轉(zhuǎn)換

?為了講述原理方便，我們只考慮中心在

原點(diǎn)，半徑為R的圓，圓的方程為：

X2+Y2=R2o對于圓心不在原點(diǎn)的圓，可

以通過平移變換，化為中心在原點(diǎn)的圓,

再進(jìn)行掃描轉(zhuǎn)換。而對于顯示器坐標(biāo)原

點(diǎn)在左上角的情況，要根據(jù)圓的掃描轉(zhuǎn)

換原理進(jìn)行適當(dāng)?shù)男薷摹?/p>

?由于圓的對稱性，要掃描轉(zhuǎn)換生成

X2+Y2=R2的圓，只要能生成8分圓，那

么圓的其它部分可以通過對稱關(guān)系得到o

設(shè)圓上一點(diǎn)的坐標(biāo)為（x,y）,可得到其

它7個(gè)分圓上對應(yīng)的點(diǎn)（y,x）（y，?

x）、（x,?y）、（?x,?y）、（?y,?x）、

（■y,x）、（?x,y）,如圖4.2.1所示。因

此，只需討論8分圓的掃描轉(zhuǎn)換。

、中點(diǎn)畫圓法

?1.原理：考慮第二個(gè)8分圓，討論如何

從(0,R)(R/sqrt(2)5R/sqrt(2))順時(shí)

針地確定最佳逼近于該圓弧的像素序列。

如圖422所示，假設(shè)x坐標(biāo)為Xp的像素已

經(jīng)確定，為P(Xp,yJ,那么，下一個(gè)像素

只能是正右方向P1(x+1,yj或右下方的

P2(xp+1,yp-1)兩著：乙一。

?2.構(gòu)造函數(shù)

?F(x,y)=X2+Y2-R2

?存在下面關(guān)系：對于圓上的點(diǎn)，F(xiàn)(xy)=O；對

手圓外的點(diǎn)，F(xiàn)(x,y)>0；對于南內(nèi)5的點(diǎn)，

F(x,y)vO；

?假設(shè)M是P1和P2的中點(diǎn)，即M=(xD+15y-0.5)o

那么，

?(1)當(dāng)F(M)vO時(shí)，表示M在圓內(nèi)，應(yīng)取

P1作為下一個(gè)像素；

?(2)當(dāng)F(M)>0時(shí)，表示M在圓外，應(yīng)取

P2作為下一個(gè)像素；

?(3)當(dāng)F(M)=O時(shí)，表示M在圓上，取R

和P2均可，約定取「2作為下一像素；

?構(gòu)造判別式

■d=F(M)=F(xp+1,yp-0.5)=(xp+1)My-

0.5)2.R2

?若dvO,則應(yīng)取P1為下一像素，而且再下一

個(gè)像素的判別式為

22

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

=d+2xp+3

即△d=2x#3

圖422當(dāng)前像素與下一像素之間的關(guān)系

?若d三0,則應(yīng)取P2為下一像素，而且再下一個(gè)

像素的判別式為

產(chǎn)+(22

?d=F(xp+2,y-1.5)=(x+2yp-1.5)-R

=d+(2xp+3)+G2yp+2)=d+2(xp-yp)+5

?即△d=2(Xp?yp)+5

?初值：我們只考慮按順時(shí)針方向生成第二個(gè)8

分圓，因此第一個(gè)像素是(0,R),判別式d的

初值為：

222

?d0=F(1,R-0.5)=1+(R-0.5)-R=1.25-R

?3.算法描述

MidpointCircle(intr,intcolor)

intx,y;

floatd;

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

setpixel(x,y,color);

while(x<y)

(

if(d<0)

(

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

}

else

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

x++;y-;

}

Setpixel(x,y,color);

}/*while*/

}/*MidpointCiecle*/

?在算法描述中，使用了浮點(diǎn)數(shù)來表示判

別式d。為了簡化算法，擺脫浮點(diǎn)數(shù)，在

算法中全部使用整數(shù)，我們使用e=d?

0.25來代替d。則有：

?初值：d=1.25-R替換為e=1?R；

?判別式：d<0替換為ev?0.25。由于

e的處置為整數(shù)，而且在運(yùn)算過程中的增

量也是整數(shù)，故e始終為整數(shù)，所以判別

式ev?0.25等價(jià)于evO；

?增量：d=d+2x+3改為e=e+2x+3;

?d=d+2(x-y)+5改為e=e+2(x-

y)+5

在算法中e仍用d來表示，算法描述如下

MidpointCircle(intr,intcolor)

(

intx,y,d;

x=0;y=r;d=1-r;

setpixel(x,y,color);

while(x<y)

(1

if(d<0)

(

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

}

else

(

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

x++;y-;

}

Setpixel(x,y,color);

}/*while*/

}/*MidpointCiecle*/

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

?中點(diǎn)畫圓法可以推廣到一般的二次曲線

的生成。下面介紹用中點(diǎn)生成法來生成

橢圓的算法。

?1.原理描述

?設(shè)橢圓的方程為：

?x2/a2+y2/b2=1或F(x,y)=b2x2+

a2y2-a2.b2=0

?其中，a為沿x軸方向的長半軸的長度，b

為沿y軸方向的長半軸的長度，a、b均為

整數(shù)。由于橢圓的對稱性，我們只考慮

第一象限橢圓弧的生成。在處理這段橢

圓弧時(shí)，我們進(jìn)一步把它分成兩部分，

上部分和下部分，以弧上斜率為的點(diǎn)

（即法向量兩個(gè)分量相等的點(diǎn)）作為分

界。如圖4.2.3所示。

圖4.2.3第一象限的橢圓弧

?由微積分知識，該橢圓上一點(diǎn)(x,y)處的法

向量為:

aFaF”

N(x,y)=----------1+-----------j=2b2由+2常亦

Axay^

?其中，i和j分別是沿x軸和y軸方向的單位向量。

從圖中可以看出，上部分法向量的y分量更大,

而在下部分法向量的x分量更大。因此，若在

22

當(dāng)前中點(diǎn)，法向量(2b(xD+1)52a(y-0.5))

的y分量比x分量大，即

22

2b(xp+1)<2a(yp-0.5)

?而在下一個(gè)中點(diǎn)，不等號改變方向，則說明橢

圓弧從上部分轉(zhuǎn)入下部分。

?與中點(diǎn)畫圓法類似，當(dāng)我們確定一個(gè)像素之后,

接著在兩個(gè)候選像素的中點(diǎn)計(jì)算一個(gè)判別式的

值，并根據(jù)判別式符號確定兩個(gè)候選像素哪個(gè)

離橢圓更近。下面討論算法的具體步驟。

?先看橢圓弧的上部分。假設(shè)橫坐標(biāo)為xp的像素

中與橢圓弧最接近者是(xp,yp),那么下一

對候選像素的中點(diǎn)是(x+1,y-0.5)o因此,

判別式為

2222

:Xp+1,y,O5)=b(Xp+1)+a(yp-0.5)-

?它的符號將決定下一個(gè)像素是取正右方的那個(gè)，

還是右下方的那個(gè)。

?若中點(diǎn)在橢圓內(nèi)，則應(yīng)取正右方的像素,

而且判別式應(yīng)更新為

222

?d/=F(x+2,yp-0.5)=b(xp+2)+a(yp-

0.5)2.a212PPP

2

?=dl+b(2xp+3)

?因此，往正右方向，判別式d的增量為b2

(2Xp+3)o

?而當(dāng)d〔NO,中點(diǎn)在橢圓之外，這時(shí)應(yīng)取右下

方的像素，并且更新判別式為

2

dF(x+2y15產(chǎn)b2n+2產(chǎn)+a(yp-

1.5)2?a2.心

22

?=dl+b(2xp+3)+a(-2yp+2)

?所以，沿右下方向，判別式d1的增量為：b2

(2xp+3)+a?(-2yp+2)o

?判別式4的初始條件，由于橢圓弧的起點(diǎn)為

(0,b),因此，第一個(gè)中點(diǎn)是(1,b?0,5),

對應(yīng)的判別式是：

22222

?d10=F(1,b-0.5)=b+a(b-0.5)-a.b

?=b2+a2(-b+0.25)

?在掃描轉(zhuǎn)換橢圓弧的上部分時(shí)，在每步迭代中,

必須通過計(jì)算和比較法向量的兩個(gè)分量來確定

何時(shí)從上部分轉(zhuǎn)入下部分。這是因?yàn)樵谙虏糠?

算法有所不同。

?在下部分，應(yīng)改為從正下方和右下方的兩個(gè)像

素中選擇下一個(gè)像素。在剛轉(zhuǎn)入下部分之時(shí)，

必須對下部分的中點(diǎn)判別式ci?進(jìn)行初始化。具

體地說，如果再上部分所選擇的最后一像素是

(Xp,y)，則下部分的中點(diǎn)判別式d2在

(x：+0&Dy-1)處計(jì)算。ci2在正下方向與右

下子向的增墓計(jì)算與上部分計(jì)算類似。下部分

弧的終止條件是y=0。

22

?當(dāng)d2Vo時(shí)，Ad2=b(2x+2)+a(-2y+3)

2

?當(dāng)cl2三。時(shí)，Ad2=a(-2y+3)

2.算法描述

?第一象限橢圓弧的掃描轉(zhuǎn)換中點(diǎn)算法描述如下

?MiddlepointEllipse(a,b,color)

?inta,b,color;

?{

?intx,y;

?floatd1,d2;

?x=0;y=b;

?d1=b*b+a*a*(-b+0.25);

?Setpixel(x,y,color);

While(b*b*(x+1)<a*a*(y-0.5))

(

if(d1<0)

d1+=b*b*(2*x+3);

x++;

)

else

(

d1+=(b*b*(2*x+3)+a*a*(-2*y+2));

x++;y-;

}

Setpixel(x,y,color);

}//上半部分

d2=sqr(b*(x+0.5))+sqr(a*(y-1))-sqr(a*b);

while(y>0)

(

if(d2<0)

{

d2+=b*b*(2*x+2)+a*a*(-2*y+3);

x++；y-；

}

else

(

d2+=a*a*(-2*y+3);

y??；

}

Setpixel(x,y,color);

}〃下半部分

}

423程序?qū)崿F(xiàn)與上機(jī)實(shí)踐（二）

?一、實(shí)驗(yàn)?zāi)康?/p>

?編寫圓和橢圓的掃描轉(zhuǎn)換算法程序，驗(yàn)

證算法的正確性。

?二、實(shí)驗(yàn)任務(wù)

?1.編寫中點(diǎn)畫圓法的掃描轉(zhuǎn)換程序，

考慮原點(diǎn)在（x。7。）處程序的改動；

?2.添加鼠標(biāo)程序，實(shí)現(xiàn)交互式畫圓；

?3.編寫中點(diǎn)畫橢圓法的掃描轉(zhuǎn)換程序;

?添加鼠標(biāo)程序，實(shí)現(xiàn)交互式畫橢圓

、實(shí)驗(yàn)內(nèi)容

a1.編寫中點(diǎn)畫圓法的掃描轉(zhuǎn)換程序，考慮原

點(diǎn)在(Xo,y。)處程序的改動;

?分析：考慮圓心不再原點(diǎn)，設(shè)圓心坐標(biāo)為

(xO,yO)。通過平移坐標(biāo)原點(diǎn)到圓心，則第

二個(gè)8分圓上一點(diǎn)p(x,y),其原始坐標(biāo)為

?x'=x+xO

?y9=y+yO

?即p\(xO+x,y+yO)

?即明(xO+x5y+yO)

?其它7個(gè)對稱點(diǎn)分別是：p，2

(xO+y5y+xO),(xO+y5yO-x),p%

x

(xO+x5yO-y),p\(xO?x,yO?y),p\(°-

y,yO?x),p)(xO-y5yO+x),p\(x0?

x,yO+y)

A

M

M

+

O

)X

0

'd

算法程序如下：

?MidpointCircle(intxOJntyOJntr,int

color)

?{

?intx5y;

?floatd;

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

?CirPot(x05y0,x5y5color);

?while(x<=y)

?if(d<0)

?(

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

?)

?else

?(

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

?x++;y“；

?)

CirPot(x05y05x5y5color);

}/*while*/

}/*MidpointCiecle*/、

intCirPot(intxO,intyO,intx,inty5intcolor)

(

Setpixel((xO+x)5(yO+y));

Setpixel((xO+y)5(yO+x));

Setpixel((xO+y),(yO-x));

Setpixel((xO+x)5(yO-y));

Setpixel((xO-x),(yO-y));

Setpixel((xO-y)5(yO-x));

Setpixel((xO-y)5(yO+x));

Setpixel((xO-x)5(yO+y));

}

?程序隹現(xiàn)步驟，

?(1)建立MidPointCircle工程文件;

?(2)右擊CMidPointCircleView類,

建立成員函數(shù)

?voidMidpointCircle(CDC*pDC,int

xOjinty05intr,COLORREFcolor)

?intCirPot(CDC*pDCJntxO,inty05

intx,inty5COLORREFcolor)

?(3)編寫成員函數(shù)代碼，程序如下：

void

CMidPointCircleView::MidpointCircle(CDC

*pDC5intxO,intyO,intr,COLORREFcolor)

?(

?intx,y;

?floatd;

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

?CirPot(pDC3x05y0,x3y3color);

while(x<=y)

(

(

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

}

else

(

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

x++;y-;

}

CirPot(pDC5x05y05x5y5color);

}/*while*/

)

?intCMidPointCircleView::CirPot(CDC*pDC,intxO,

intCOLORREFcolor)

?{

?pDC->SetPixel((xO+x)J(yO+y),color);

?pDC->SetPixel((xO+y)5(yO+x)5color);

?pDC->SetPixel((xO+y)5(yO-x)5color);

?pDC->SetPixel((xO+x)5(yO-y)5color);

?pDC->SetPixel((xO-x)5(yO-y)5color);

?pDC->SetPixel((xO-y)5(yO-x)5color);

?pDC->SetPixel((xO-y)5(yO+x)5color);

?pDC->SetPixel((xO-x)5(yO+y)5color);

?return0;

?}

C)(4)編寫OnDraw(CDC*pDC)函數(shù)，程序如下：

voidCMidPointCircleView::OnDraw(CDC*pDC)

?{

?CMidPointCircleDoc*pDoc=GetDocument();

?ASSERT_VALID(pDoc);

?//TODO:adddrawcodefornativedatahere

?MidpointCircle(pDC,100,100,10,

RGB(255,0,0));

MidpointCircle(pDC,500,300,60,

RGB(255,255,0));

?}

?(6)編譯、運(yùn)行程序，查看結(jié)果。

任務(wù)2：添加鼠標(biāo)程序，實(shí)現(xiàn)交

?在任務(wù)1的基礎(chǔ)上，完成下列步驟：

?(1)向視圖類中添加自定義的成員變量

?用鼠標(biāo)右鍵單擊視圖類，選擇“AddMember

Variable…”，添加下面三個(gè)成員變量。

?proctected:

?intm_r;//半徑

?CPointm_bO;//圓心

?CPointm_bR;〃圓上的點(diǎn)

?intm_ist;〃圓心與圓周上點(diǎn)的區(qū)別，m_ist=0,

表示鼠標(biāo)左擊點(diǎn)為圓心，

?//m_ist=1,表示鼠標(biāo)左擊點(diǎn)為圓周上的

八占、、

?二(2)在視圖類CPP文件的構(gòu)造函數(shù)中初始化

成員變量

?CMidPointCircleMouseView::CMidPointCir

cleMouseView()

?{

?//TODO:addconstructioncodehere

?m_bO.x=0;m_bO.y=0;〃圓心

?m_bR.x=0;m_bR.y=0;〃圓上的點(diǎn)

?m_ist=0;//圓心與圓上的點(diǎn)區(qū)別

?mr=0;〃圓的半徑

?}

?(3)向視圖類中添加自定義的成員函數(shù)原型:

?public:

intComputeRadius(CPointcenp5CPoint

ardp);

?添加成員函數(shù)的程序代碼：

?intCMouseSpringView::ComputeRadius(CPoint

cenp,CPointardp)

?{

?intdx=cenp.x-ardp.x;

?intdy=cenp.y-ardp.y;

?//sqrt()函數(shù)的調(diào)用，在頭文件中加入include

nmath.hH

?return(int)sqrt(dx*dx+dy*dy);

?}

?(4)向視圖類中添加兩個(gè)鼠標(biāo)消息響應(yīng)函數(shù),

并輸入鼠標(biāo)處理程序代碼。

具體操作方法與鼠標(biāo)示例1方法相同。一個(gè)

是OnLButtonDown。函數(shù)，另一個(gè)是

OnMouseMove()函數(shù)。程序如下：

?void

CMidPointCircleMouseView::OnLButtonDown(UI

NTnFlags,CPointpoint)

?(

?//TODO:Addyourmessagehandlercode

hereand/orcalldefault

CDC*pDC=GetDC();

pDC->SelectStockObject(NULL_BRUSH);

if(!m_ist)〃繪制圓

m_bO=m_bR=point;〃紀(jì)錄第一次單擊鼠標(biāo)位置，

定圓心

m_ist++;

}

else

(

m_bR=point;〃記錄第二次單擊鼠標(biāo)的位置，定圓

周上的點(diǎn)一

〃為新繪圖作準(zhǔn)備

m_r=ComputeRadius(m_bO,m_bR);

MidpointCircle(pDC,m_b0.x,m_b0.y,m_r,RGB(255J0,0));

}

ReleaseDC(pDC);〃釋放設(shè)備環(huán)境

CView::OnLButtonDown(nFlags,point);

?voidCMidPointCircleMouseView::OnMouseMove(UINT

nFlags^CPointpoint)

?(

?//TODO:Addyourmessagehandlercodehereand/or

calldefault

?CDC*pDC=GetDC();

?intnDrawmode=pDC->SetROP2(R2_NOT);〃設(shè)置異或繪

圖模式，并保存原來繪圖模式一

?pDC->SelectStockObject(NULL_BRUSH);

?if(m_ist==1)

?{-

?CPointprePnt,curPnt;

?prePnt=m_bR;〃獲得鼠標(biāo)所在的前一位置

?curPnt=point;

?m_r=ComputeRadius(m_bO5prePnt);

MidpointCircle(pDC,m_bO.x,m_bO,y,m_r，RGB(255,0,0));〃用

異或模式重復(fù)畫圓，擦由所畫的扇_

?//DrawCircle(pDC,m_bO,prePnt);

?m_r=ComputeRadius(m_bO,curPnt);

?MidpointCircle(pDC,m_b0.xJm_b0.yJm_r,RGB(255,0,0));

〃用當(dāng)前位置作為圓周上的點(diǎn)li圓

?m_bR=point;

?}

?pDC->SetROP2(nDrawmode);//恢復(fù)原繪圖模式

?ReleaseDC(pDC);〃釋放設(shè)備環(huán)境

?CView::OnMouseMove(nFlags,point);

?}

任務(wù)3：編寫中點(diǎn)畫橢圓法的掃

撞轉(zhuǎn)換程序

?程序?qū)崿F(xiàn)步驟：

?(1)建立MidPointEHise工程文件；

?⑵右擊CMidPoint日liseView類，建立

成員函數(shù)

?voidMidpointEllise(CDC*pDC,int

xOjinty05inta,intb,COLORREF

color)

?(3)編寫成員函數(shù)代碼，程序如下：

?void

CMidPoint日lipseView::Midpoint日lise(CD

C，pDC；intxO,infyO,inta,intb,

COLORREFcolor)

?{

?intx,y;

?floatd1,d2;

?x=0;y=b;

?d1=b*b+a*a*(-b+0.25);

?pDC->SetPixel(x+xO,y+yO,color);

?while(b*b*(x+1)<a*a*(y-0.5))

if(d1<0)

(

d1+=b*b*(2*x+3);

x++;

}

else

(

d1+=(b*b*(2*x+3)+a*a*(-2*y+2));

x++;y-;

}

pDC->SetPixel(xO+x,yO+y,color);

pDC->SetPixel(xO+x,yO-y,color);

pDC>SetPixel(xO-x,yO+y,color);

pDC->SetPixel(xO-x,yO-y,color);

}//上半部分

d2=(b*(x+0.5))*(b*(x+0.5))+(a*(y-1))*(a*(y-1))-(a*b)*(a*b);

while(y>0)

if(d2<0)

d2+=b*b*(2*x+2)+a*a*(-2*y+3);

x++；y??；

}

else

d2+=a*a*(-2*y+3);

y”；

}

pDC，SetPixel(xO+x,yO+y,color);

pDC->SetPixel(xO+x,yO-y,color);

pDC->SetPixel(xO-x,yO+y,color);

pDC->SetPixel(xO-x,yO-y,color);

}〃下半部分

}

(4)編寫OnDraw。函數(shù)

voidCMidPointEllipseView::OnDraw(CDC*pDC)

(

CMidPointEllipseDoc*pDoc=GetDocument();

ASSERT_VA