【計算機圖形學】基本圖形（元）生成技術

第4章基本圖形（元）生成技術

提綱：

1.直線生成技術；

2.圓與橢圓生成技術

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

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

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

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

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

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

稱為圖形的掃描轉換或光柵化，也叫圖形的生成

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

信息，結合圖形生成算法，計算出要顯示的中間

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

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

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

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

形。

?圖形掃描轉換一般分為兩個步驟：先確

定有關像素，再用圖形的顏色或其它屬

性對象素進行某種寫操作。后者通常是

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

掃描轉換的主要任務就是確定最佳逼近

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

■本章主要討論基本圖形的掃描轉換問題,

包括：

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

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

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

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

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

圖元＞圖素等）的生成技術是最基本的

‘任何復雜的圖形都是由基本圖形組成的

基本圖形生成的質量直接影響該圖形系

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

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

繪圖的精確性。

4.1直線圖形的生成技術

?在數(shù)學上，兩個坐標點可以確定出一條

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

數(shù)個點構成的。在光柵圖形顯示器上顯

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

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

該直線的一組像素點來表示，這就是直

線的掃描轉換。

?在繪制斜線時，有些點不一定正好落在

像素點上，直線掃描轉換算法必須確定

哪一個像素點來顯示，從而形成“梯形

線”。當顯示器分辯率很高時，仍可以

生成高質量的直線。

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

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

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

一個像素寬的直線，生成直線算法的函

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

4.1.1數(shù)值微分法

1.原理

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

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

A(xO,yO),B(xl,yl)是直線的端點坐標，首先計算

出直線的斜率

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

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

當|k|sl時，讓x每步增加1,y最多增加1,

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

像素位置為(x9round(y))。設當前點為

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

九1=kxi+1+B

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

=%+k

即當x每遞增1時，y遞增斜率k。

當lkl>l時，應當讓y每步遞增1,這時x最多

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

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

當前點為(為4)，則下一個像素yi+i=乂+1

，則

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

=Xj+l/k

即當y每遞增1時，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;//實現(xiàn)四舍五入

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

(

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

x=x+dx;

y=y+dy;

)

4.1.2中點畫線法

中點畫線算法示意圖

L原理:

?設點前百為PKyJ」只考慮直線斜率在

?0、1之間時，若直線在x方向上增加一個

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

?下一個像點只可能是P1((Xj+1,y)或

P2((xi+15yi+1)o

?在以M表示P1和P2的中點，即

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

?又設Q是理想直線與x=xi+1的交點，

?當M在Q的下方，則取P2為下一個像素；

否則，取P1為下一個像素位置。

2.遞推公式和算法

［假設直線的起之和終點分別為(xO5yO)

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

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

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

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

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

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

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

■判斷中點M在Q的上方，還是

在下方，只要將中點坐標

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

中，并判斷它的符號。構造判

別式

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

?當ckO時，表示M在直線的下方，則取P2為下

一點；當d>0時，表示M在直線的上方，則取

P1為下一點；當d=0時，表示M在直線中，取

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

遞推式子

?(X)當d>=0時，取P1為下一個像素點，

欲判斷再下一個像素，應計算

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

c=d+a

?即d的增量△d=a

?(2)當dvO時，取P2為下一個像素點，欲

判斷再下一個像素，應計算

?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,并且計算下一點的d值

)

else

x++;

d+=deltal;〃取Pl,并且計算下一點的d值

)

putpixel(x,y,color);

)

備由于在整個算法中只考慮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);

中點畫線法示圖

4.1.3Bresenham國線算法

?1.算法原理

?Bresenham算法是計算機圖形學領域中使用

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

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

如下：

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

想直線最近的像素來進行支線的掃描轉換的。

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

按直線從起點到終點的順序計算直線與各垂直

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

最近的像素。

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

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

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

要檢查一個誤差項的符號，就可以確定

該列所求的像素。

2.遞推公式

?設直線的起始點為(xO,yO)，終點為

(x15y1),貝U直線的斜率

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

?考慮OWkW1的情況。

?在起始點(xO,yO),誤差項初值d=0;

?確定下一個像素點時，當x遞增1時，誤差項

?d的值增加一個斜率k的值，即

?d=d+k

Bresenham算法示圖

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

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

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

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

?(2)當記0時,取(x+1,y+1),>e=e-1；

?當evO時，取(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;

}

}

程序改進：

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

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

需要用到誤差項e的符號，所以可以作如

下替換：

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

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

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

即可。

算法舉例：

?設直線的起點為（0,0）,終點為（5,

3）,按Bresenham算法計算并確定個

像素點位置。

?計算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;

?程序結束。

4.1.4程序實現(xiàn)與上機實踐（一）

?實驗目的：利用VisualC++實現(xiàn)三種直線生成

算法，驗證算法的正確性；

?實驗任務：

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

序；

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

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

Bresenham算法的示例。

實驗步驟：

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

?實驗步驟：

?1.建立一個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)試和運行程序，查看程序結

果。

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

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

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

10為單位，計算出直線上各個像素位置

?步驟：

?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));

?//畫出像素點

?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)試、運行程序

住務三二加入鼠標功能，實現(xiàn)

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

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

?用鼠標右鍵單擊視圖類，選擇“Add

MemberVariable…”,添加下面三個成員變量。

?proctected:

?CPointm_p1;〃起點

?CPointm_p2;〃終點

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

起點，

//mist=1,表示直線終點

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

型：

Lpublic:

?voidDDAMouseLine(CDC*pDC,int

xO,intyO,intx1,inty1,COLORREFcolor);

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

化成員變量。

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

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

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

輸入下面程序代碼：

?CDDAMouseLineView::CDDAMouseLineVi

ew()

?(

?//TODO:addconstructioncodehere

?m_p1.x=0;m_p1.y=0;//起點

?m_p2.x=0;m_p2.y=0;〃終點

?m_ist=0;//0,第1點；1,第2點；

?}

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

函數(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ù),用鼠標畫直線

?}

第六步：向視圖類中添加鼠標、

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

并輸入鼠標處理程序代碼。

?voidCMouseSpringView::OnLButtonDown(UINTnFlags,

CPointpoint)

?(

?//TODO:Addyourmessagehandlercodehereand/or

calldefault

?CDC*pDC=GetDC();

?pDC->SelectStockObject(NULL_BRUSH);

?if(!mjst)//是起點

?(

?m_p1=m_p2=point;〃紀錄第一次單擊鼠標位置，

定圓心

?m_ist++;

?}

?else

?(

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

占的占

八、、MJ八、、

?mJst-;〃為新繪圖作準備

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

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

?}

?ReleaseDC(pDC);//釋放設備環(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);

?}

第八步：編譯運行程序，驗證運行結果。

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

畫直線。

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

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

?voidCDDAMouseLineView::OnMouseMove(UINT

nFlags,CPointpoint)

?{

?//TODO:Addyourmessagehandlercode

hereand/orcalldefault

?CDC*pDC=GetDC();

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

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

?pDC->SelectStockObject(NULL_BRUSH);

^if(m_ist==1)

?CPointprePntjCurPnt;

?prePnt=m_p2;〃獲得鼠標所在的前一位置

?curPnt=point;

?〃繪制橡皮筋線

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

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

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

復畫圓，擦出所畫的圓

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

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

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

點畫圓

?m_p2=point;

?}

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

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

CView::OnMouseMove(nFlags,point);

}

4.2圓與橢圓的掃描轉換

?4.2.1圓的掃描轉換

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

原點，半徑為R的圓，圓的方程為：

X2+Y2=R2o對于圓心不在原點的圓，可

以通過平移變換，化為中心在原點的圓,

再進行掃描轉換。而對于顯示器坐標原

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

換原理進行適當?shù)男薷摹?/p>

?由于圓的對稱性，要掃描轉換生成

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

么圓的其它部分可以通過對稱關系得到o

設圓上一點的坐標為（x,y）,可得到其

它7個分圓上對應的點（y,x）（y，?

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

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

此，只需討論8分圓的掃描轉換。

、中點畫圓法

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

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

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

如圖422所示，假設x坐標為Xp的像素已

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

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

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

?2.構造函數(shù)

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

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

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

F(x,y)vO；

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

那么，

?(1)當F(M)vO時，表示M在圓內(nèi)，應取

P1作為下一個像素；

?(2)當F(M)>0時，表示M在圓外，應取

P2作為下一個像素；

?(3)當F(M)=O時，表示M在圓上，取R

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

?構造判別式

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

0.5)2.R2

?若dvO,則應取P1為下一像素，而且再下一

個像素的判別式為

22

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

=d+2xp+3

即△d=2x#3

圖422當前像素與下一像素之間的關系

?若d三0,則應取P2為下一像素，而且再下一個

像素的判別式為

產(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

?初值：我們只考慮按順時針方向生成第二個8

分圓，因此第一個像素是(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*/

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

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

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

0.25來代替d。則有：

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

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

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

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

式ev?0.25等價于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橢圓的掃描轉換

?中點畫圓法可以推廣到一般的二次曲線

的生成。下面介紹用中點生成法來生成

橢圓的算法。

?1.原理描述

?設橢圓的方程為：

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

a2y2-a2.b2=0

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

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

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

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

圓弧時，我們進一步把它分成兩部分，

上部分和下部分，以弧上斜率為的點

（即法向量兩個分量相等的點）作為分

界。如圖4.2.3所示。

圖4.2.3第一象限的橢圓弧

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

向量為:

aFaF”

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

Axay^

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

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

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

22

當前中點，法向量(2b(xD+1)52a(y-0.5))

的y分量比x分量大，即

22

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

?而在下一個中點，不等號改變方向，則說明橢

圓弧從上部分轉入下部分。

?與中點畫圓法類似，當我們確定一個像素之后,

接著在兩個候選像素的中點計算一個判別式的

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

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

?先看橢圓弧的上部分。假設橫坐標為xp的像素

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

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

判別式為

2222

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

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

還是右下方的那個。

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

而且判別式應更新為

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〔NO,中點在橢圓之外，這時應取右下

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

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的初始條件，由于橢圓弧的起點為

(0,b),因此，第一個中點是(1,b?0,5),

對應的判別式是：

22222

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

?=b2+a2(-b+0.25)

?在掃描轉換橢圓弧的上部分時，在每步迭代中,

必須通過計算和比較法向量的兩個分量來確定

何時從上部分轉入下部分。這是因為在下部分,

算法有所不同。

?在下部分，應改為從正下方和右下方的兩個像

素中選擇下一個像素。在剛轉入下部分之時，

必須對下部分的中點判別式ci?進行初始化。具

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

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

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

下子向的增墓計算與上部分計算類似。下部分

弧的終止條件是y=0。

22

?當d2Vo時，Ad2=b(2x+2)+a(-2y+3)

2

?當cl2三。時，Ad2=a(-2y+3)

2.算法描述

?第一象限橢圓弧的掃描轉換中點算法描述如下

?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程序實現(xiàn)與上機實踐（二）

?一、實驗目的

?編寫圓和橢圓的掃描轉換算法程序，驗

證算法的正確性。

?二、實驗任務

?1.編寫中點畫圓法的掃描轉換程序，

考慮原點在（x。7。）處程序的改動；

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

?3.編寫中點畫橢圓法的掃描轉換程序;

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

、實驗內(nèi)容

a1.編寫中點畫圓法的掃描轉換程序，考慮原

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

?分析：考慮圓心不再原點，設圓心坐標為

(xO,yO)。通過平移坐標原點到圓心，則第

二個8分圓上一點p(x,y),其原始坐標為

?x'=x+xO

?y9=y+yO

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

?即明(xO+x5y+yO)

?其它7個對稱點分別是：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)編譯、運行程序，查看結果。

任務2：添加鼠標程序，實現(xiàn)交

?在任務1的基礎上，完成下列步驟：

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

?用鼠標右鍵單擊視圖類，選擇“AddMember

Variable…”，添加下面三個成員變量。

?proctected:

?intm_r;//半徑

?CPointm_bO;//圓心

?CPointm_bR;〃圓上的點

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

表示鼠標左擊點為圓心，

?//m_ist=1,表示鼠標左擊點為圓周上的

八占、、

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

成員變量

?CMidPointCircleMouseView::CMidPointCir

cleMouseView()

?{

?//TODO:addconstructioncodehere

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

?m_bR.x=0;m_bR.y=0;〃圓上的點

?m_ist=0;//圓心與圓上的點區(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)向視圖類中添加兩個鼠標消息響應函數(shù),

并輸入鼠標處理程序代碼。

具體操作方法與鼠標示例1方法相同。一個

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

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;〃紀錄第一次單擊鼠標位置，

定圓心

m_ist++;

}

else

(

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

周上的點一

〃為新繪圖作準備

m_r=ComputeRadius(m_bO,m_bR);

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

}

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

CView::OnLButtonDown(nFlags,point);

?voidCMidPointCircleMouseView::OnMouseMove(UINT

nFlags^CPointpoint)

?(

?//TODO:Addyourmessagehandlercodehereand/or

calldefault

?CDC*pDC=GetDC();

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

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

?pDC->SelectStockObject(NULL_BRUSH);

?if(m_ist==1)

?{-

?CPointprePnt,curPnt;

?prePnt=m_bR;〃獲得鼠標所在的前一位置

?curPnt=point;

?m_r=ComputeRadius(m_bO5prePnt);

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

異或模式重復畫圓，擦由所畫的扇_

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

?m_r=ComputeRadius(m_bO,curPnt);

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

〃用當前位置作為圓周上的點li圓

?m_bR=point;

?}

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

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

?CView::OnMouseMove(nFlags,point);

?}

任務3：編寫中點畫橢圓法的掃

撞轉換程序

?程序實現(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