【计算机图形学】基本图形（元）生成技术

第4章基本图形（元）生成技术

提纲：

1.直线生成技术；

2.圆与椭圆生成技术

•我们知道，光栅图形显示器是一个像素矩阵，如

分辨率为640X480,每个像素可以用一种或多种

颜色显&会别称为单色显示器或彩色显示器。

在光栅显示器上显示加何一种图形，实际上都

是具有一种或多种颜色的像素的集合。确定一个

像素集合及其颜色，用于显示一个图形的过程，

称为图形的扫描转换或光栅化，也叫图形的生成

实际上，图形生成是根据图形的几何信息和属性

信息，结合图形生成算法，计算出要显示的中间

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

点的信息。所以，基本图形的生成，首先要根据

基本图形的特征找出它的几何信息，然后根据一

定的生成算法实时地在显示器上显示出完整的图

形。

•图形扫描转换一般分为两个步骤：先确

定有关像素，再用图形的颜色或其它属

性对象素进行某种写操作。后者通常是

通过调用设备驱动程序来实现的。所以

扫描转换的主要任务就是确定最佳逼近

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

■本章主要讨论基本图形的扫描转换问题,

包括：

•（1）一维直线、圆、椭圆的生成；

•（2）二维图形（多边形）的填充；

•（3）字符的表示和输入输出；

•（4）图形的裁剪和反走样技术；

•在一个图形系统中，基本图形（也称为

图元＞图素等）的生成技术是最基本的

‘任何复杂的图形都是由基本图形组成的

基本图形生成的质量直接影响该图形系

统绘图的质量。所以，需要设计出精确

的基本图形生成算法，以确保图形系统

绘图的精确性。

4.1直线图形的生成技术

•在数学上，两个坐标点可以确定出一条

直线，理想的直线是没有宽度的，由无

数个点构成的。在光栅图形显示器上显

示一条直线时，只能在显示器给定的有

限像素组成的矩阵中，确定最佳逼近于

该直线的一组像素点来表示，这就是直

线的扫描转换。

•在绘制斜线时，有些点不一定正好落在

像素点上，直线扫描转换算法必须确定

哪一个像素点来显示，从而形成“梯形

线”。当显示器分辩率很高时，仍可以

生成高质量的直线。

•本节主要介绍三种创用的直线生成算法,

即数值微分法(DDA)、中点画线法和

Bresenham算法。这三种算法都是只考虑

一个像素宽的直线，生成直线算法的函

数形式如下：Line(xO,yO,xl,yl,color);

4.1.1数值微分法

1.原理

数值微分法(DDA,DigitalDifferentialAnalysis

)是根据数学上直线的微分方程来设计的。设

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;//实现四舍五入

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的增量都是整数，只是起初值包含小数,

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

掉小数。

•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算法是计算机图形学领域中使用

最广泛的直线生成技术。该算法适合于光栅图

形显示器、数字化仪设计等设备，其原理描述

如下：

•Bresenham也是通过在每列像素中确定与理

想直线最近的像素来进行支线的扫描转换的。

通过各行、各列像素中心构造一组虚拟网格线,

按直线从起点到终点的顺序计算直线与各垂直

网格线的交点，然后确定该列像素中与此交点

最近的像素。

•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在每次号掣丽时得到都是小数，为了

便于硬件计算，取掉小数。由于算法只

需要用到误差项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程序实现与上机实践（一）

•实验目的：利用VisualC++实现三种直线生成

算法，验证算法的正确性；

•实验任务：

•1.理解三种直线生成算法思想，写出实现程

序；

•2.添加鼠标功能，实现交互式画直线程序；

•3.将10个像差作为步距单位，编出

Bresenham算法的示例。

实验步骤：

・任务一：实现DDA画线程序

•实验步骤：

•1.建立一个DDALine的工程文件；

•2.添加ddaline。成员函数

•方法：在工作区中选择CLASSVIEW类窗

口，右击CDDAIineView类,选择“add

memberfunction…”，定义如卞的成员

函数：

•voidddaline(CDC*pDCJntxOJnt

yOJntx!Jnty!,COLORREFcolor);

编写自定义的成员函数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()函数

•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.编译、调试和运行程序，查看程序结

果。

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

•先画出(100,100)至I」(600,400)大

小为10的网格，然后从(100,100)以

10为单位，计算出直线上各个像素位置

•步骤：

•1.建立DDA2Line工程；

•2.在OnDraw()函数中画出网格，并调

用DDA2Line()函数

•voidCDDA2LineView::OnDraw(CDC*

pDC)

•CDDA2LineDoc*pDoc

GetDocument();

•ASSERT_VALID(pDoc);

•//TODO:adddrawcodefornative

datahere

•//画网格

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()成员函数

•方法：在工作区中选择CLASSVIEW类

窗口，右击CDDAIineView类，选择

“addmemberfunction…”，定义如下

的成员函数：

•voidDDA2Line(CDC*pDCJntxOJnt

yOJntx!Jnty15COLORREFcolor);

4.编写DDA2Line()函数

•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.调试、运行程序

住务三二加入鼠标功能，实现

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

•第二步：向视图类中添加自定义的成员变量

•用鼠标右键单击视图类，选择“Add

MemberVariable…”,添加下面三个成员变量。

•proctected:

•CPointm_p1;〃起点

•CPointm_p2;〃终点

•intmjst;//区别，mJst=0,表示直线

起点，

//mist=1,表示直线终点

•第三步：向视图类中添加自定义的成员函数原

型：

Lpublic:

•voidDDAMouseLine(CDC*pDC,int

xO,intyO,intx1,inty1,COLORREFcolor);

•第四步：在视图类CPP文件的构造函数中初始

化成员变量。

•视图类的构造函数名与该视图类的名字相

同。在视图类中选择构造函数，如：

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

函数中加入下列代码，实现视

•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));一一一

•〃调用自定义的成员函数,用鼠标画直线

•}

第六步：向视图类中添加鼠标、

OnLButtonDown()函数消息响应函数，

并输入鼠标处理程序代码。

•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);//释放设备环境

•CView::OnLButtonDown(nFlags,point);

•}

第七步：添加成员函数的程序代码

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

•}

第八步：编译运行程序，验证运行结果。

・程序改进，添加橡皮筋绘图技术，实现交互式

画直线。

'•向视图类中添加鼠标0nMouseMove()函数

1消息响应函数，并输入鼠标处理程序代码。

•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);〃释放设备环境

CView::OnMouseMove(nFlags,point);

}

4.2圆与椭圆的扫描转换

•4.2.1圆的扫描转换

•为了讲述原理方便，我们只考虑中心在

原点，半径为R的圆，圆的方程为：

X2+Y2=R2o对于圆心不在原点的圆，可

以通过平移变换，化为中心在原点的圆,

再进行扫描转换。而对于显示器坐标原

点在左上角的情况，要根据圆的扫描转

换原理进行适当的修改。

•由于圆的对称性，要扫描转换生成

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的像素已

经确定，为P(Xp,yJ,那么，下一个像素

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

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

•2.构造函数

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

•存在下面关系：对于圆上的点，F(xy)=O；对

手圆外的点，F(x,y)>0；对于南内5的点，

F(x,y)vO；

•假设M是P1和P2的中点，即M=(xD+15y-0.5)o

那么，

•(1)当F(M)vO时，表示M在圆内，应取

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为下一像素，而且再下一个

像素的判别式为

产+(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*/

•在算法描述中，使用了浮点数来表示判

别式d。为了简化算法，摆脱浮点数，在

算法中全部使用整数，我们使用e=d・

0.25来代替d。则有：

•初值：d=1.25-R替换为e=1・R；

•判别式：d<0替换为ev・0.25。由于

e的处置为整数，而且在运算过程中的增

量也是整数，故e始终为整数，所以判别

式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均为

整数。由于椭圆的对称性，我们只考虑

第一象限椭圆弧的生成。在处理这段椭

圆弧时，我们进一步把它分成两部分，

上部分和下部分，以弧上斜率为的点

（即法向量两个分量相等的点）作为分

界。如图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)

•而在下一个中点，不等号改变方向，则说明椭

圆弧从上部分转入下部分。

•与中点画圆法类似，当我们确定一个像素之后,

接着在两个候选像素的中点计算一个判别式的

值，并根据判别式符号确定两个候选像素哪个

离椭圆更近。下面讨论算法的具体步骤。

•先看椭圆弧的上部分。假设横坐标为xp的像素

中与椭圆弧最接近者是(xp,yp),那么下一

对候选像素的中点是(x+1,y-0.5)o因此,

判别式为

2222

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

•它的符号将决定下一个像素是取正右方的那个，

还是右下方的那个。

•若中点在椭圆内，则应取正右方的像素,

而且判别式应更新为

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产b2n+2产+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程序实现与上机实践（二）

•一、实验目的

•编写圆和椭圆的扫描转换算法程序，验

证算法的正确性。

•二、实验任务

•1.编写中点画圆法的扫描转换程序，

考虑原点在（x。7。）处程序的改动；

•2.添加鼠标程序，实现交互式画圆；

•3.编写中点画椭圆法的扫描转换程序;

•添加鼠标程序，实现交互式画椭圆

、实验内容

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

}

・程序隹现步骤，

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

•(2)右击CMidPointCircleView类,

建立成员函数

•voidMidpointCircle(CDC*pDC,int

xOjinty05intr,COLORREFcolor)

•intCirPot(CDC*pDCJntxO,inty05

intx,inty5COLORREFcolor)

•(3)编写成员函数代码，程序如下：

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)函数，程序如下：

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：添加鼠标程序，实现交

•在任务1的基础上，完成下列步骤：

•(1)向视图类中添加自定义的成员变量

•用鼠标右键单击视图类，选择“AddMember

Variable…”，添加下面三个成员变量。

•proctected:

•intm_r;//半径

•CPointm_bO;//圆心

•CPointm_bR;〃圆上的点

•intm_ist;〃圆心与圆周上点的区别，m_ist=0,

表示鼠标左击点为圆心，

•//m_ist=1,表示鼠标左击点为圆周上的

八占、、

•二(2)在视图类CPP文件的构造函数中初始化

成员变量

•CMidPointCircleMouseView::CMidPointCir

cleMouseView()

•{

•//TODO:addconstructioncodehere

•m_bO.x=0;m_bO.y=0;〃圆心

•m_bR.x=0;m_bR.y=0;〃圆上的点

•m_ist=0;//圆心与圆上的点区别

•mr=0;〃圆的半径

•}

•(3)向视图类中添加自定义的成员函数原型:

•public:

intComputeRadius(CPointcenp5CPoint

ardp);

•添加成员函数的程序代码：

•intCMouseSpringView::ComputeRadius(CPoint

cenp,CPointardp)

•{

•intdx=cenp.x-ardp.x;

•intdy=cenp.y-ardp.y;

•//sqrt()函数的调用，在头文件中加入include

nmath.hH

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

•}

•(4)向视图类中添加两个鼠标消息响应函数,

并输入鼠标处理程序代码。

具体操作方法与鼠标示例1方法相同。一个

是OnLButtonDown。函数，另一个是

OnMouseMove()函数。程序如下：

•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);〃释放设备环境

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);〃释放设备环境

•CView::OnMouseMove(nFlags,point);

•}

任务3：编写中点画椭圆法的扫

撞转换程序

•程序实现步骤：

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

•⑵右击CMidPoint日liseView类，建立

成员函数

•voidMidpointEllise(CDC*pDC,int

xOjinty05inta,intb,COLORREF

color)

•(3)编写成员函数代码，程序如下：

•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。函数

voidCMidPointEllipseView::OnDraw(CDC*pDC)

(

CMidPointEllipseDoc*pDoc=GetDocument();

ASSERT_VA