【文档说明】计算机图形学-课件.ppt，共(79)页，732.506 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77506.html

以下为本文档部分文字说明：

1余敦辉湖北大学数计学院计算机图形学2第五章基本图形生成算法光栅扫描图形系统的结构光柵扫描特点：*数据量大－快的要求*显示的离散化－准的要求*独立的图形显示处理器－快速，实时硬件处理的扫描转换CPU系统总线显示处理器系统

存储器显示处理器存储器帧缓存视频控制器I/O设备监视器3第五章基本图形生成算法图形显示处理器(加速引擎)任务：进行扫描转换(ScanConversion)扫描转换：将应用程序给出的图形定义数字化为一组像素强度值，并放到帧

缓存器扫描转换的工作内容：－基本图形的生成－字符的生成－填充、裁剪－线型的处理－彩色处理－某些变换和管理4第五章基本图形生成算法坐标系统为描述对象、构造场景或完成图形变换，需要不同的坐标系！1.建模坐标系－定义对象2.世界坐标系－定义对象与外界环境的关系3.

设备坐标系－定义图形显示的位置、大小4.规范化坐标－为保证互换性（与设备无关）而定义的辅助坐标5第五章基本图形生成算法坐标系统建模坐标ModelingCoordinateLocalCoordinateMasterCoordinate世

界坐标WorldCoordinate绘图仪其它输出设备设备坐标DeviceCoordinateScreenCoordinate111规范化坐标NormalizedCoordinate6第五章基本图形生成算法5.1直

线的扫描转换光栅扫描显示下画直线存在的问题：(1)显示速度问题：例：分辨率：1024×768，24Bit彩色，帧存容量：1024×768×3＝2,359,296Byte刷新率85Hz:85×2,359

,296＝200,540,160(Byte/S)存储器读出时间：~5nS(2)显示质量问题：阶梯状线的粗细不一线的亮度差异7第五章基本图形生成算法5.1直线的扫描转换直线的绘制要求：1.直线要直2.直线的端点要准确，即无定向性和断裂情况3.直线的亮度、色泽要均匀4.画

线的速度要快5.要求直线具有不同的色泽、亮度、线型等解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。8第五章基本图形生成算法5.1直线的扫描转换5.1.1数值微分法(DDA法)直线的微分方程：DDA算法原理

：2)-(511yyyxxxiiiiε=1/max(|△x|,|△y|)ε△xxiyxyixi+1yi+1ε△y图5-2DDA算法原理9第五章基本图形生成算法5.1直线的扫描转换5.1.1数值微分法(DDA法)max(|△x|,|△y|)=|△x|，即|

k|≤1的情况：max(|△x|,|△y|)=|△y|，此时|k|≥1：111111iiiiiiiiyyyyyyykxxyxxxx11111kyyxyy

yyxxxxxxxiiiiiiii10第五章基本图形生成算法5.1直线的扫描转换5.1.1数值微分法(DDA法)注意：round(x)=(int)(x+0.5)图5-3DDA算法生成直线段(xi,yi)(xi+1,r

ound(yi+k))(round(xi+1/k),yi+1)11第五章基本图形生成算法5.1直线的扫描转换5.1.1数值微分法(DDA法)VoidDDAline(intx0,inty0,intx1,inty1){intdx,dy,eps1,k;f

loatx,y,xIncre,yIncre;dx=x1-x0;dy=y1-y0;x=x0;y=y0;If(abs(dx)>abs(dy))eps1=abs(dx);elseeps1=abs(dy);xIncre=(f

loat)dy/(float)eps1;yIncre=(float)dy/(float)eps1;for(k=0;k<=eps1;k++){putpixel((int)(x+0.5),(int)(y+0.5));x+=xI

ncre;y+=yIncre;}}12第五章基本图形生成算法5.1直线的扫描转换5.1.1数值微分法(DDA法)特点：增量算法直观、易实现缺点：浮点运算、取整－－》废时，且不利于硬件实现。不利于用硬件实现。13第五章基本图形生成算法5.

1直线的扫描转换5.1.2中点画线法算法5.1.2中点画线法算法原理：假定直线斜率K<1，且已确定点亮象素点P（Xp,Yp）M为中点，Q为交点现需确定下一个点亮的象素。显然可得出如下结论：若M在Q的下方，选Pu，否则选Pd14第五章基本图形

生成算法5.1直线的扫描转换5.1.2中点画线法算法算法实现：假设直线的起点、终点分别为：（X0,Y0),(X1,Y1)该直线方程可表示为：F(x,y)=a*x+b*y+c（1）其中：a=Y0-Y1,b=X1-X0,c

=X0*Y1-X1*Y0当：F(Xt,Yt)=0→(Xt,Yt)在直线上F(Xt,Yt)<0→(Xt,Yt)在直线下方F(Xt,Yt)>0→(Xt,Yt)在直线上方15第五章基本图形生成算法5.1直线的扫描转换5.1.2中点画线法算法

xyF(x,y)>0F(x,y)=0F(x,y)<0图5-4直线将平面分为三个区域xyF(x,y)>0F(x,y)=0F(x,y)<016第五章基本图形生成算法5.1直线的扫描转换5.1.2中点画线法算法因此：

将中点M坐标代入（1）式，并判断其符号即可确定象素点的选取。构造如下判别式：d=F(M)=F(Xp+1,Yp+0.5)=a(Xp+1)+b(Yp+0.5)+c由上式可看出，d是x,y线性函数，可推导d的增量

公式)0()0(1dydyy17第五章基本图形生成算法5.1直线的扫描转换5.1.2中点画线法算法当d<0时，取象素Pu，此时再下一个象素的判别式为：d’=F(Xp+2,Yp+1.5)=a(Xp

+2)+b(Yp+1.5)+c=a(Xp+1)+b(Yp+0.5)+c+a+b=d+a+b;误差项的递推d<0：18第五章基本图形生成算法5.1直线的扫描转换5.1.2中点画线法算法当d>=0时，取象素Pd，此时再下一个象素的判别式为：d’=F(Xp+2,Y

p+0.5)=a(Xp+2)+b(Yp+0.5)+c=a(Xp+1)+b(Yp+0.5)+c+a=d+a;误差项的递推d≥0：19第五章基本图形生成算法5.1直线的扫描转换5.1.2中点画线法算法d的初始值可按下式计算：d0=F(X0+1,Y0+0.5)=a(

X0+1)+b(Y0+0.5)+c=F(X0,Y0)+a+0.5b=a+0.5b由于只用d的符号作判断，为了只包含整数运算,可取2d代替d，这样可得如下中点算法程序：20第五章基本图形生成算法5.1直线的扫描转换5.1.2中点画线法算法MidpointLine(X0,Y0,

X1,Y1,Color)intX0,Y0,X1,Y1,Color;{inta,b,d1,d2,d,x,y;a=Y0-Y1;b=X1-X0;d=a+a+b;d1=a+a;d2=a+b+a+b;x=X0;y=Y0;dr

awpixle(x,y,Color);while(x<X1){if(d<0){x++;y++;d+=d2;}21第五章基本图形生成算法5.1直线的扫描转换5.1.2中点画线法算法else{x++;d+=d1;}drawpixle(x,y,Color)

;}/*while*/}/*MidPointLine*/习题：按照中点划线算法，确定直线（0，0）（5，3）的点亮象素。列出计算过程，并列出所选象素坐标。22第五章基本图形生成算法5.1直线的扫描转换5.1.3Bresenham画线算法5.1.

3改进的Bresenham算法基本原理：(假定直线段的0≤k≤1)图5-8改进的Brensemham算法绘制直线的原理ddddkkkkk23第五章基本图形生成算法5.1直线的扫描转换5.1.3Brese

nham画线算法假定直线斜率,0<k<1,起点坐标为(x,y);下一个点亮象素可能是：(x+1,y)或(x+1,y+1)。这可通过d值的大小来确定:d=d+k,当d>1时d=d-1;当d<0.5取(x+1,y)，否则取(x+1,y+1)。

0.5)(d0.5)(d1111iiiiiyyyxx误差项的计算•d初=0，•每走一步：d=d+k•一旦y方向上走了一步，d=d-124第五章基本图形生成算法5.1直线的扫描转换5.1.3Bresenham画线算法算法步骤：1.输入直线的两端点P0(x0,y0)和

P1(x1,y1)。2.计算初始值△x、△y、d=0、x=x0、y=y0。3.绘制点(x,y)。4.d更新为d+k，判断d的符号。若d>0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复

步骤3和4。否则结束。25第五章基本图形生成算法5.1直线的扫描转换5.1.3Bresenham画线算法改进1：令e=d-0.50)(e0)(e1111iiiiiyyyxx•e初=-0.5，•

每走一步有e=e+k。•if(e>0)thene=e-126第五章基本图形生成算法5.1直线的扫描转换5.1.3Bresenham画线算法算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-0.5、x=x0、y=y0。3.绘

制点(x,y)。4.e更新为e+k，判断e的符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。27第五章基本图形生成算

法5.1直线的扫描转换5.1.3Bresenham画线算法改进2：用2e△x来替换ee初=-△x，每走一步有e=e+2△y。if(e>0)thene=e-2△x28第五章基本图形生成算法5.1直线的扫描转换5.1.3Bresenham画线算法算法步骤：1.输入直线

的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-△x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2△y，判断e的符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2△x；否则(x,y)更新为(x+1,y)。5.当直

线没有画完时，重复步骤3和4。否则结束。程序如下：BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx,y,dx,dy;floatk,e;inte;dx=x1-x0;dy=y1-y

0;k=dy/dx;e=-0.5;x=x0;y=y0;e=-dx;for(i=0;i<=dx;i++){drawpixel(x,y,color);x++;e=e+k;e1=e-0.5;e=e+2*dy;e1=e-dx;if(e1>0)

e=e-1;e=e-2*dx;if(e>=0)y++;}}Bresenham画线例直线端点为(20,10)和（30,18),用Bresenham法画线解：x＝10，y＝8，k=y/x=0.8，2y＝16，2x＝20e0＝－x＝－10画初始点(20,10),并根据判别式确定沿线段路径的

后续像素位置如下表：ie’i(xi+1,yi+1)06(21,11)12(22,12)2-2(23,12)314(24,13)410(25,14)56(26,15)62(27,16)7-2(28,16)814(29,17)910(20,18)29212223242526202827101

817161513141211193031第五章基本图形生成算法5.2圆的扫描转换5.2.1圆的对称性利用八分圆的对称性特点，可以简化圆的扫描转换算法。如果圆的圆心在原点，则可以由其中某个八分圆的圆周上的某点（x，y）计算出其他七个八分圆圆周上对应的点的坐标。由此可构造相应算法，由图中阴

影的圆周复制生成整个圆周。32第五章基本图形生成算法5.2圆的扫描转换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,

-x,value);drawpixel(-y,-x,value);}33第五章基本图形生成算法5.2圆的扫描转换5.2.2角度DDA画圆算法1、角度DDA法若已知圆的方程：x=x0+Rcosy=y0+Rsindx=-Rsinddy=Rcosdxn+1=xn+dx

yn+1=yn+dyxn+1=xn-(yn-y0)dyn+1=yn+(xn-x0)d34第五章基本图形生成算法5.2圆的扫描转换5.2.2角度DDA画圆算法角增量(弧度)的选取：d＝/(n-1)n越大，点越多，速度越慢。所以在不同的

精度下，对于不同的半径给定不同的d：使max(|Δx|，|Δy|)≤1因：Δx=-(yn–y0)dΔy=(xn–x0)d即max(|(yn–y0)d|，|(xn–x0)d|)≤1又因为|yn–y0|，|xn–x0|最大是R所以：R|d|≤1|

d|≤1/R绝对值表示画圆弧有顺时针和逆时针之别，为精度计，取|d|＝1/(R+1)35第五章基本图形生成算法5.2圆的扫描转换5.2.2角度DDA画圆算法算法：Arc－dda（xc，yc，r，a1，a2，color）intxc，yc

，r，color；doublea1，a2；{inti,steps,x,y；doubleda,radin;da=1/(r＋1）；radin＝a2-a1;steps=radin/da;x=r*cos(a1);y=r*Sin(a1);for(i=0;i≤steps;i++){drawpixel

(x+xc,y+yc,color);x=x–y*da;y=y+x*da;}}36第五章基本图形生成算法5.2圆的扫描转换5.2.3中点画圆法利用圆的对称性，只须讨论1/8圆(第一象限中的第二个八分圆)。解决问题：yy=x图5-101/8圆弧xR37第五

章基本图形生成算法5.2圆的扫描转换5.2.3中点画圆法基本原理：假设P（Xp+1，Yp）为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。38第五章基本图形生成算法

5.2圆的扫描转换5.2.3中点画圆法2)推导过程：①构造一函数：F（X，Y）=X2+Y2-R2F（X，Y）=0（X，Y）在圆上；F（X，Y）<0（X，Y）在圆内；F（X，Y）>0（X，Y）在圆外。M为P1、P2间的中点，M=(Xp+1,Yp-0.5)

有如下结论：F（M）<0取P1F（M）>=0取P239第五章基本图形生成算法5.2圆的扫描转换5.2.3中点画圆法②构造判别式d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若d<0,则P1为下一个象素，那么再下一个

象素的判别式为：d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3即d的增量为2xp+3.40第五章基本图形生成算法5.2圆的扫描转换5.2.3中点画圆法③计算d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R若d>=0,则P

2为下一个象素，那么再下一个象素的判别式为：d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+2(xp-yp)+5即d的增量为2(xp-yp)+5.41第五章基本图形生成算法5.2圆的扫描转换5.2.3中点画圆法算法步骤：1.输入圆的半径R。2.计算初始值

d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d≤0，则先将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。否

则结束。42第五章基本图形生成算法5.2圆的扫描转换5.2.3中点画圆法MidpointCircle(r,color)intr,color;{intx,y;floatd;x=0;y=r;d=1.25-r

;drawpixel(x,y,color);while(x<y){if(d<0){d+=2*x+3;x++；}else{d+=2*(x-y)+5;x++;y--;}}}43第五章基本图形生成算法5.2圆的扫描转换5.2.3中点画圆法改进1

：用d-0.25代替d算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d≤0，则先将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。否则结束。令e＝d－0.25e＝1－R则d<0e<－0.25而e为整数，则e<－0.25等价于e<0。再将e仍用d来表示44第五章基本图形生成算法5.2圆的扫描转换5.2.

3中点画圆法改进2：因判别式d的增量是x，y的线性函数。每当x递增1，d递增Δx＝2；每当y递增1，d递减Δy＝2；由于初始象素为（0，r），所以Δx的初值为3，Δy的初值为－2r＋2。再注意到乘2运算可以改用加法实现，至此我们可写出不含乘法，仅用整数实现的中点画

圆算法。45第五章基本图形生成算法5.2圆的扫描转换5.2.3中点画圆法MidpointCircle(r,color)intr,color;{intx,y，deltax，deltay，d;x=0;y=r;d=1-r;deltax=3;deltay=2-r-r;drawpixel(x,y,co

lor);while(x<y){if(d<0){d+=deltax;deltax+=2;x++；}else{d+=(deltax+deltay);deltax+=2;deltay+=2;x++;y--;}}}46例题：画第一象限中，半径R＝10，圆心在原点的圆弧解：起点为(x0,y0

)＝(0,10)e0＝1－R＝－9；(x1,y1)＝(1,10)e1＝e0＋2x0+3＝－6；(x2,y2)＝(2,10)e2＝e1＋2x1+3＝－1；(x3,y3)＝(3,10)e3＝e2＋2x2+3＝6；(x4,y4)＝(4,9)e4＝e3＋2(x3－y3)+

5＝－3；(x5,y5)＝(5,9)e5＝e4＋2x4+3＝8；(x6,y6)＝(6,8)e6＝e5＋2(x5－y5)+5＝5；(x7,y7)＝(7,7)91234560871987645321010若

ei<0,－>ei＋1＝ei+2xi+3ei>=0,－>ei＋1＝ei+2(xi－yi)+547第五章基本图形生成算法5.2圆的扫描转换5.2.3Bresenham画圆法5.2.3.Bresenham画圆算法为讨论方便，仅考虑圆心在原点，半径为R的第一象限上的一段圆弧。且取（0，R）为

起点，按顺时针方向绘制该1/4圆弧。48第五章基本图形生成算法5.2圆的扫描转换5.2.3Bresenham画圆法原理：如图1-3所示，从当前点亮象素出发，按顺时针方向生成圆时，最佳逼近该圆的下一个象素只可能为H、D、V三象素之一。H、D、V中距圆周边界距离最小者，即为所求的象素点。49第五章基

本图形生成算法5.2圆的扫描转换5.2.3Bresenham画圆法算法：H、D、V三点到圆心的距离平方与圆的半径平方差，即为H、D、V到圆弧距离的一种度量：H=(x+1)2+y2-R2;D=(x+1)2+(y-1)2-R2;V=x2+(y-1)2-R2;50第五章基本图形生成算法5.2圆的扫

描转换5.2.3Bresenham画圆法为了根据这些度量值可确定最佳象素点，首先，将H、D、V与理想圆弧的关系进行分类。存在以下五种情况：1）H、D、V全在圆内；2）H在圆外，D、V在圆内；3）D在圆上，H在圆外，V在圆内；4）H、D在圆外，V在圆内；5）H、

D、V全在圆外。与Bresenham画线算法一样，按照上述不同类型，找出误差度量的递推公式，然后判别它的正、负性即可确定最佳逼近的象素点。51第五章基本图形生成算法5.2圆的扫描转换5.2.3Bresenham画圆法当D<0,只可能为1或2种情况

。为了确定是H还是D，可用如下判别式：δHD=|H|-|D|δHD≤0则应选H，否则选D。52第五章基本图形生成算法5.2圆的扫描转换5.2.3Bresenham画圆法对于第2种情况：δHD=H+D=(x+1)2+y2-R2+(x+1)2+(y-1)2-R2=2D+2y-1对于第1种情况

：∵y是x的单调递减函数∴H为下一点亮象素。另，此时H<0和D<0H+D=2D+2y-1<0综上两种情况可得如下结论：在D＜0时，若2（D+y)-1≤0，则取H，否则取D53第五章基本图形生成算法5.2圆的扫描转换5.2.3Bresenham画圆

法当D＞0,只可能有4、5两种情况。且最佳象素点为D或V，可用如下判别式：δDV=|D|-|V|δDV≤0则应选D，否则选V。对于第4种情况：δDV=D+V（D＞0，V＜0）=(x+1)2+(y-1)2-R2+(x)2+(y-1)2-R2=2(D-x

)-1对于第5种情况：D,V都在圆外，显然V为所选象素。注意：∵D＞0，V＞0∴D+V=2(D-x)-1＞054第五章基本图形生成算法5.2圆的扫描转换5.2.3Bresenham画圆法综上两种情况可得如下结论：在D＞0时，若2（D-x)-1≤0，则取

D，否则取V当D=0此时D是最佳象素。总结上述分析结果：当D＞0，若2(D-x)-1＞0，取V，否则取D当D＜0，若2(D+y)-1≤0，取H，否则取D当D=0，取D。55第五章基本图形生成算法5.2圆的扫描转换5

.2.3Bresenham画圆法关键的问题就是计算D（见D的计算公式）采用增量法，获得D的计算公式。分三种情况：下一象素为H时,则H=(x’,y’)=(x+1,y)D’=((x+1)+1)2+(y-1)2-R2=(x+1)2+(y-1)2-R2+2(x+1)+1

=D+2(x+1)+1=D+2x’+156第五章基本图形生成算法5.2圆的扫描转换5.2.3Bresenham画圆法下一象素为D时D=(x’,y’)=(x+1,y-1)D=((x+1)+1)2+((y-1)-1)2-R2=(x+1)2+(y-1)2-R2+2(x+1)-2(y-

1)+1=D+2(x+1)-2(y-1)+2下一象素为V时V=(x’,y’)=(x,y-1)D=(x+1)2+((y-1)-1)2-R2=(x+1)2+(y-1)2-R2-2(y-1)+1=D-2(y-1)+157第五章基本图形生成算法5.2圆的扫描转换

5.2.3Bresenham画圆法有了上述D的递推计算公式，还需计算出D的初值。∵圆弧的起点为（0，R）∴D的初值为：D=(0+1)2+(R-1)2-R2=2(1-R)BresenhamCircle(r,color)intr,color;{intx,

y,delta,d1,d2,dirx=0;y=r;delta=2*(1-r)while(y>=0){drawpixel(x,y,color);if(delta<0){d1=2*(delta+y)-1;if(d1<=0)dir=1;elsedir=2;}elseif(delta>0){d2

=2*(delta-x)-1;if(d2<=0)dir=2;elsedir=3;}elsedir=2;switch(dir){case1:x++;delta+=2*x+1;break;case2:x++;Y--;delta+=2*(x-y+1)+1;break;case

3:y--;delta+=-2*y+1;break;}/*endofswitch*/}/*endofwhile*/}/*endofBresenhamCircle*/60第五章基本图形生成算法5.3椭圆的扫描转换baxy图5-14长半轴为a，短半轴为b的标准椭圆(

x,y)(x,-y)(-x,-y)(-x,y)0),(222222bayaxbyxF对于椭圆上的点，有F(x,y)=0；对于椭圆外的点，F(x,y)>0；对于椭圆内的点，F(x,y)<0。61第五章基

本图形生成算法5.3椭圆的扫描转换解决问题：yx(x,y)yy=-xy=xyy=x图5-101/8圆弧xR62第五章基本图形生成算法5.3椭圆的扫描转换上半部分下半部分二分量相等的法向量图5-15第一象限的椭圆弧yx法向量yjaxibjyF

ixFyxN2222),(y分量>x分量y分量<x分量y分量=x分量0),(222222bayaxbyxF椭圆方程分界点：法向量两分量相等的点，以弧上斜率为－1的点63第五章基本图形生成算法5.3椭圆的扫描转换

引理5-1：若在当前中点，法向量的y分量比x分量大，即)5.0()1(22iiyaxb而在下一个中点，不等号改变方向，则说明椭圆弧从上部分转入下部分。当前点P(xi,yi)候选点Pu(xi+1，yi)Pd(xi+1，yi-1)中

点(xi+1，yi-0.5)上半部分下半部分二分量相等的法向量图5-15第一象限的椭圆弧yx64第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法5.3.1椭圆的中点Bresenham算法先推导上半部分的椭圆绘制公式再推导下半部分的椭圆绘制公式65第五章基本图

形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法先推导上半部分的椭圆绘制公式判别式误差项的递推判别式的初值p(xi,yi)pu(xi+1,yi)pd(xi+1,yi-1)M(xi+1,yi-0.5)5-17上半部分椭圆弧的绘制原

理66第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法判别式2222221)5.0()1()5.0,1(bayaxbyxFdiiii若d1≤0，取Pu(xi+1,yi)若d1>0，取Pd(xi+1

,yi-1)p(xi,yi)pu(xi+1,yi)pd(xi+1,yi-1)M(xi+1,yi-0.5)5-17上半部分椭圆弧的绘制原理67第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点

Bresenham算法误差项的递推(a)d<=0的情况Pxiyi-2xi+1yiyi-1xi+2)x(bd)x(bba).(ya)(xbba).(ya)(xb).,yF(xdiiiiiiii32325015025022122222222222221

2222221)5.0()1()5.0,1(bayaxbyxFdiiii情况一：d1≤0：68第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法误差项的递推)22()32()22

()32()5.0()1()5.1()2()5.1,2(221222222222222221iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd(b)d>0的情况Pxixi+2xi+1yi-1yiyi-22222221)5.0

()1()5.0,1(bayaxbyxFdiiii情况二：d1>0：69第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法上半部判别式的初始值：)25.0()5.0()5.0,1(

222222210babbababbFd初始点（0，b）候选点（1，b-1）（1，b）中点（1，b-0.5）70第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法再

来推导椭圆弧下半部分的绘制公式判别式误差项的递推判别式的初值71第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法判别式2222222)1()5.0()1,5.0(bayaxbyxFd

iiii若d2>0，取Pl(xi,yi-1)若d2≤0，取Pr(xi+1,yi-1)72第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法误差项的

递推)y(ad)y(aba)(ya)(xbba)(ya)(xb),yF(xdiiiiiiii323215.025.025.02222222222222222(a)d>0的情况Pxiyi-2xi+1yiyi-1xi+22222222)1()

5.0()1,5.0(bayaxbyxFdiiii第一种情况：d2>0：73第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法误差项的递推)32()22()32()22()1()5.0()2(

)5.1()2,5.1(222222222222222222iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd(b)d<=0的情况Pxixi+2xi+1yi-1yiyi-22222222)1()5.0(

)1,5.0(bayaxbyxFdiiii第二种情况：d2≤0：74第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法注意：上半部分的终止判别下半部分误差项的初值75第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bres

enham算法算法步骤：1.输入椭圆的长半轴a和短半轴b。2.计算初始值d=b2+a2(-b+0.25)、x=0、y=b。3.绘制点(x,y)及其在四分象限上的另外三个对称点。4.判断d的符号。若d≤0，则先将d更新为d+b2(2x+3)，再

将(x,y)更新为(x+1,y)；否则先将d更新为d+b2(2x+3)+a2(-2y+2)，再将(x,y)更新为(x+1,y-1)。5.当b2(x+1)<a2(y-0.5)时，重复步骤3和4。否则转到步骤6

。76第五章基本图形生成算法5.3椭圆的扫描转换5.3.1椭圆的中点Bresenham算法6.用上半部分计算的最后点(x,y)来计算下半部分中d的初值：222222)1()5.0(bayaxbd7.绘制点(x,y)及其在四分象限上的另外三个

对称点。8.判断d的符号。若d≤0，则先将d更新为b2(2xi+2)+a2(-2yi+3)，再将(x,y)更新为(x+1,y-1)；否则先将d更新为d+a2(-2yi+3)，再将(x,y)更新为(x,y-1)。9.当y>0时，重复步骤7和8。否则结束。MidpointEllipse(a，b

,color)inta，b,color;{intx,y；floatd1,d2；x=0;y=b;d1＝b*b+a*(-b+0.25);drawpixel(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--;}drawpixel(x,y,color);}d2＝sqr(b*(x+5)+a*(y-1)-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--;}drawpixel(x,y,color);}}79习题1.将中点画线方法推广，使之能画出任意斜率的直线2.用DDA法，

中点画线法和Bresenham算法画从(0,0)到(-10,-5)间的直线段3.写一个利用BRESENHAM算法，画任意斜率的直线段的程序。4.编写按逆时针方向生成中心在原点的第一个8分圆的中点画圆算法，导出递推公式5.推导用中点画圆算法画中

心在原点的第一象限椭圆弧的递推算法