计算机图形学课件

计算机图形考1

余敦群

湖北大学教计学院

第五章基本图形生成算法

光栅扫描图形系统的结构2

光栅扫描特点：

*数据量大

*显示的离散化

*独立的图形显示处理器

第五章基本图形生成算法

图形显示处理器(加速引擎)3

任务：进行扫描转换(ScanConversion)

扫描转换：将应用程序给出的图形定义数字化为一组像

素强度值，并放到帧缓存器

.扫描转换的工作内容：

-基本图形的生成

-字符的生成

-填充、裁剪

-线型的处理

-彩色处理

-某些变换和管理

第五章基本图形生成算法

坐标系统4

为描述对象、构造场景或完成图形变换，需要

不同的坐标系！

1.建模坐标系一定义对象

2.世界坐标系定义对象与外界环境的关系

3.设备坐标系一定义图形显示的位置、大小

4.规范化坐标-为保证互换性（与设备无

关）而定义的辅助坐标

第五章基本图形生成算法

坐标系统5

ModelingCoordinate

LocalCoordinateNormalizedDeviceCoordinate

MasterCoordinateWorldCoordinateCoordinateScreenCoordinate

第五章基本图形生成算法

5.1直线的扫描转换

光栅扫描显示下画直线存在的问题：

(1)显示速度问题：

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

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

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

存储器读出时间：〜5ns

(2)显示质量问题：

■阶梯状

■线的粗细不

■线的亮度差异

第五章基本图形生成算法

5.1直线的扫描转换7

直线的绘制要求：

1.直线要直

2.直线的端点要准确，即无定向性和断裂情况

3.直线的亮度、色泽要均匀

4.画线的速度要快

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

解决的问题：

给定直线两端点P。(x0,y0)和Pi(xpy),画出该直线o

第五章基本图形生成算法

5.1直线的扫描转换8

5.1.1数值微分法（DDA法）

直线的微分方程：

DDA算法原理：

y

X,=X+£•△X

I4-1Z

X

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

第五章基本图形生成算法

5.1直线的扫描转换9

5.1.1数值微分法（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直线的扫描转换10

5.1.1数值微分法（DDA法）

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

第五章基本图形生成算法

5.1直线的扫描转换11

5.1.1数值微分法（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;

)

)

第五章基本图形生成算法

直线的扫描转换

5.112

5.1.1数值微分法（DDA法）

特点：

增量算法■!

缺点：

浮点运算、取整一一》废时，且不利于硬件实现。

不利于用硬件实现

第五章基本图形生成算法

5.1直线的扫描转换

5.1.2中点画线法算法

5.1.2中点画线法算法

原理：

假定直线斜率KvL且已确定

点亮象素点P(Xp,Yp)

M为中点，Q为交点

现需确定下一个点亮的象素。

图5-5Brensemham算法生成直线的原理

显然可得出如下结论：若M在Q的下方，选Pu,否则选Pd

k______________________________________________________)

第五章基本图形生成算法

直线的扫描转换

5.114

5.1.2中点画线法算法

算法实现：

假设直线的起点、终点分别为：(XO,YO),(X1,Y1)

该直线方程可表示为：.

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

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

当：F(Xt,Yt)=0一(Xt,Yt)在直线上

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

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

第五章基本图形生成算法

图5-4直线将平面分为三个区域

第五章基本图形生成算法

5.1直线的扫描转换16

5.1.2中点画线法算法

因此：将中点M坐标代入(

1)式，并判断其符号即

可确定象素点的选取。构

造如下判别式：

d=F(M)

=F(Xp+l,Yp+0.5)

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

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

性函数，可推导d的增量

公式

歹=<

[y(d>o)

第五章基本图形生成算法

5.1直线的扫描转换

5.1.2中点画线法算法

误差项的递推

d<0：

h_____________

9

当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直线的扫描转换18

5.1.2中点画线法算法

误差项的递推

d>0：

当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直线的扫描转换19

5.1.2中点画线法算法

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的符号作判断，为了只包含整数运算,

可取2d代替d,这样可得如下中点算法程序：

第五章基本图形生成算法

5.1直线的扫描转换20

5.1.2中点画线法算法

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直线的扫描转换21

5.1.2中点画线法算法

else{

x++;

d+=dl;

}

drawpixle(x,y,Color);

}/*while*/

}/*MidPointLine*/

按照中点划线算法，确定直线(0,0)(5,3)的点

亮象素。列出计算过程，并列出所选象素坐标。

第五章基本图形生成算法

5.1直线的扫描转换22

5.1.3Bresenham画线算法

5.1.3改进的Bresenham算法

第五章基本图形生成算法

5.1直线的扫描转换23

5.1.3Bresenham画线算法

假定直线斜率,O〈kvl,起点坐壬+i=/+1

标为(x,y);3+18>0.5)

匕+i=<

下一个点亮象素可能是：［兀(d<0.5)

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

通过d值的大小来确定：

误差项的计算

d=d+k,当d>l时d=d-l;

•d初=0,

当d<0.5取(x+l,y),否则取

•每走一步：d=d+k

(x+l,y+l)o

•方向上走了三”>

d=d-l

第五章基本图形生成算法

5.1直线的扫描转换24

5.1.3Bresenham画线算法

算法步骤：

1.输入直线的两端点Po(X0,y0)和P[(X],y1)。

2.计算初始值Ax、Ay>d=0>x=x0>y=y0o

.绘制点o

4.d更新为d+k,判断d的符号。若d>0.5,则(x,y)更新为

(x+l,y+l),同时将d更新为d・1；否则(x,y)更新为(x+1,y)。

5.当直线没有画完时，重复步骤3和4。否则结束。

第五章基本图形生成算法

5.1直线的扫描转换25

5.1.3Bresenham画线算法

x,=x+1

Z+1Z

改进1：令e=d-0.5<'儿.+1(e>0)

兀+i=<

〔兀（e<。）

•e初=・0.5,

•每走一步有e=e+ko

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

第五章基本图形生成算法

5.1直线的扫描转换26

5.1.3Bresenham画线算法

算法步骤为：

L输入直线的两端点Po(Xo，y。)和Pi(Xi，yJ。

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

3.绘制点(x,y)o

4.e更新坦判断e的符号。若e>0,则(x,y)更新为

(x+Ly+1),同时将e更畿枣三£)否则(x,y)更新为(x+l,y)。

5.当直线没有画完时，重复步骤3和4。否则结束。

第五章基本图形生成算法

5.1直线的扫描转换27

5.1.3Bresenham画线算法

改进2：用2eZ\x来替换e

€初="Ax,

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

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

第五章基本图形生成算法

5.1直线的扫描转换28

5.1.3Bresenham画线算法

算法步骤：

1.输入直线的两端点Po(Xo，y°)和Pi(Xi汹)o

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

3.绘制点(x,y)o

4.e更新为阡泾“判断e的符号。若e>0,则(x,y)更新为

(x+Ly+1),同时将e更新为日入“否则(x,y)更新为(x+l,y)。

5.当直线没有画完时，重复步骤3和4。否则结束。

程序如下: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圆线例

直线端点为(20,10)和(30,18),用Bresenham法画线

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

分=-Ax=—10

画初始点(20,10),并根据判别式确定沿线段路径的后续像素位置如下表:

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圆的扫描转换31

5.2.1圆的对称性

利用八分圆的对称性特点

,可以简化圆的扫描转

换算法。

如果圆的圆心在原点，则

可以由其中某个八分圆

的圆周上的某点（x,y

）计算出其他七个八分

圆圆周上对应的点的坐

标。

由此可构造相应算法，由

图中阴影的圆周复制生

成整个圆周。

第五章基本图形生成算法

5.2圆的扫描转换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圆的扫描转换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圆的扫描转换34

5.2.2角度DDA画圆算法

角增量0(弧度)的选取：de=e/(n-l)

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圆的扫描转换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圆的扫描转换

5.2.3中点画圆法

利用圆的对称性，只须讨论1/8圆（第一象限

中的第二个八分圆）。

解决问题：

第五章基本图形生成算法

5.2圆的扫描转换

5.2.3中点画圆法

基本原理：假设P(Xp+1,Yp)为当前点亮象

素，那么，下一个点亮的象素可能是P1

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

第五章基本图形生成算法

5.2圆的扫描转换38

5.2.3中点画圆法

2)推导过程：

①构造一函数：

222

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

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

F(X,Y)<0(X,Y)在圆内；

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

M为Pl、P2间的中点，M=(Xp+l,Yp・0・5)

有如下结论：

F(M)<0取P1

F(M)>=0取P2

第五章基本图形生成算法

5.2圆的扫描转换39

5.2.3中点画圆法

②构造判别式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圆的扫描转换

5.2.3中点画圆法

若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圆的扫描转换41

5.2.3中点画圆法

算法步骤：

L输入圆的半径R。

计算初始值、

2.251)x=0y=Ro

3.绘制点(x,y逆其W分圆中的另外七个对称点。

4.判断d的符号。若dWO,则先将d更新式叵吟

再将(X,y)更新为(x+1,y)；否则先日才更新4

(x-y再将(x,y)更新为(x+1,y-1)。

5.当x〈y时，重复步骤3和4。否则结束。

第五章基本图形生成算法

5.2圆的扫描转换42

5.2.3中点画圆法

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圆的扫描转换43

5.2.3中点画圆法

改进1：用d-O.25代替d^e=d-0,25=>e=1-R

隹।■:土取贝Ud<0e<—0.25

舁/玄少麻：而e为整数，则e<—0.25等价

1.输入圆的半径R。于e<0o再将e仍用d来表示

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

3.绘制点(x,y)及其在八分圆中的另外七个对称点。

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.当x<y时，重复步骤3和4。否则结束。

第五章基本图形生成算法

5.2圆的扫描转换44

5.2.3中点画圆法

改进2：因判别式d的增量是x,y的线性函数。

每当x递增1,d递增Ax=2；

每当y递增1,d递减Ay=2；

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

值为3,Ay的初值为一2r+2。再注意到乘2运

算可以改用加法实现，至此我们可写出不含乘

法，仅用整数实现的中点画圆算法。

第五章基本图形生成算法

5.2圆的扫描转换45

5.2.3中点画圆法

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,圆心在原点的圆弧

46

III

1---A-

解:起点为(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圆的扫描转换47

5.2.3Bresenham画圆法

5.2.3.Bresenham圆圆算法

为讨论方便，仅考虑圆心在原点，半径为R的第一象限

上的一段圆弧。且取（0,R）为起点，按顺时针方向

绘制该1/4圆弧。

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

Figure2

第五章基本图形生成算法

5.2圆的扫描转换48

5.2.3Bresenham画圆法

原理：

如图1・3所示,从当前点

亮象素出发，按顺时针

方向生成圆时，最佳逼

近该圆的下三个象素只

可能为H、D、V三象素

之一。H、D、V中距圆

周边界距离最小者，即

为所求的象素点。

第五章基本图形生成算法

5.2圆的扫描转换49

5.2.3Bresenham画圆法

算法：

H、D、V三点到圆心的距离平方与圆的半径平

方差，即为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圆的扫描转换50

5.2.3Bresenham画圆法

为了根据这些度量值可确定最佳象素

点，首先，将H、D、V与理想圆

弧的关系进行分类。

存在以下五种情况：

1)H、D、V全在圆内；

2)H在圆外，D、V在圆内；Figure3

3)D在圆上，H在圆外，V在圆内；

4)H、D在圆外，V在圆内；

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

与Bresenham画线算法一样，按照上述不同类型

,找出误差度量的递推公式，然后判别它的正、

负性即可确定最佳逼近的象素点。

第五章基本图形生成算法

5.2圆的扫描转换51

5.2.3Bresenham画圆法

当AD<0,只可能为1或2种情况。为了确定是H

还是D,可用如下判别式：

=

8HD|AH|-|AD|

6HD<0则应选H,否则选D。

第五章基本图形生成算法

5.2圆的扫描转换52

5.2.3Bresenham画圆法

对于第2种情况：

SHD=AH+AD

2222

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

=2Ap+2y-1

对于第1种情况：

Vy是x的单调递减函数

・•.H为下一点亮象素。

另，止匕时AHvO和AD<0

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

综上两种情况可得如下结论：

在时，若2(A.+y)・lWO,则取H,

否则取力

第五章基本图形生成算法

5.2圆的扫描转换53

5.2.3Bresenham画圆法

当AD>0,只可能有4、5两种情况。且最佳象素

点为D或V,可用如下判别式：

SDV=|AD|-|Ay|

6DV<0则应选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圆的扫描转换54

5.2.3Bresenham画圆法

综上两种情况可得如下结论：

在AQ〉O时，若2则取D,

否则取V

当AD=0此时D是最佳象素。

总结上述分析结果：

当AD〉0，若2(AD-X)・1>0,取V,否则取D

当AD<0,若2(AD+y)」W0，取H,否则取D

当AD=0,取D。

第五章基本图形生成算法

5.2圆的扫描转换55

5.2.3Bresenham画圆法

关键的问题就是计算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圆的扫描转换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圆的扫描转换57

5.2.3Bresenham画圆法

有了上述AD的递推计算公式，还需计算出AD的

初值。

•.*圆弧的起点为(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椭圆的扫描转换60

图5-14长半轴为a,短半轴为b的标准椭圆

♦:♦对于椭圆上的点,有

F(x,y)=0；

222222

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

♦:♦对于椭圆外的点,F(x,y)>0；

♦:♦对于椭圆内的点,F(x,y)<0o

第五章基本图形生成算法

5.3椭圆的扫描转换61

解决问题:

第五章基本图形生成算法

5.3椭圆的扫描转换62

椭圆方程厂（》,y）=/J+°2y2一°2b2=。

x分量

图5-15第一象限的椭圆弧

分界点：法向量两分量相等的点，以弧上斜率为一1的点

第五章基本图形生成算法

5.3椭圆的扫描转换63

当前点P(Xj,yj)

候选点Pu(Xj+1,y()

Pd(Xj+1,yj-1)

中点(Xj+1,y-Q.5)

图5-16中点椭圆绘制算法的原理

引理57：若在当前中点,法向量的y分量比x分量大，即

2

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

则说明椭圆弧从上部分转入下部分。

第五章基本图形生成算法

5.3椭圆的扫描转换64

5.3.1椭圆的中点Bresenham算法

5.3.1椭圆的中点Bresenham算法

图5-16中点椭圆绘制算法的原理

先推导上半部分的椭圆绘制公式

再推导下半部分的椭绘制公式

第五章基本图形生成算法

5.3椭圆的扫描转换65

5.3.1椭圆的中点Bresenham算法

先推导上半部分的椭圆园绘制公式

判别式误差项的递推判别式的初值

第五章基本图形生成算法

5.3椭圆的扫描转换66

5.3.1椭圆的中点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椭圆的扫描转换67

5.3.1椭圆的中点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椭圆的扫描转换

5.3.1椭圆的中点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"：