【文档说明】计算机图形学直线、圆、椭圆的生成讲解课件.ppt，共(55)页，544.209 KB，由小橙橙上传

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

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

计算机图形学直线、圆、椭圆的生成讲解图形显示前需要：扫描转换+裁剪●裁剪---〉扫描转换：最常用，节约计算时间。●扫描转换---〉裁剪：算法简单；本章内容扫描转换直线段DDA算法中点画线法Bresenham画线算法圆弧、椭圆弧扫描转换中点算法内接正多边形迫近法

等面积正多边形逼近法生成圆弧的正负法9/3/2022•浙江大学计算机图形学直线段的扫描转换算法直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。数值微分法（ＤＤＡ）假定直线的起点、终点

分别为：（x0,y0),(x1,y1)，且都为整数。(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)栅格交点表示象素点位置。。。。数值微分(DDA)法基本思想已知过端点P0(x0,y0),P

1(x1,y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。0101xxyyk)(,;10yroundxbkxystepxxxxxx令数值微分(DDA)法计算yi+1=kxi+1+b=kxi+b+kx=yi+kx当

x=1;yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k≤1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换数值微分(DDA)法增量算法：在一

个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。数值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)intx；

floatdx,dy,y,k;dx,=x1-x0,dy=y1-y0;k=dy/dx,y=y0;for(x=x0;xx1,x++)drawpixel(x,int(y+0.5),color);y=y+k;数值微分(DDA)法例：

画直线段P0(0,0)--P1(5,2)xint(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5012345321Line:P0(0,0)--P1(5,2)数值微分(DDA)法缺点：在此算

法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。中点画线法原理：假定直线斜率0<K<1，且已确定点亮象素点P（Xp,Yp）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点现需确定下一个点亮的象

素。P=(xp,yp)QP2P1中点画线法当M在Q的下方->P2离直线更近更近->取P2。M在Q的上方->P1离直线更近更近->取P1M与Q重合，P1、P2任取一点。问题：如何判断M与Q点的关系？P=(xp,yp)QP2P1中点画线法假设直线方程为：ax+by+c=0其中a=y0

-y1,b=x1-x0,c=x0y1-x1y0由常识知：∴欲判断中点M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。点在直线下方点在直线上方点在直线上面0,0,

0,yxFyxFyxFP=(xp,yp)QP2P1中点画线法构造判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d<0，M在直线(Q点)下方，取右上方P2；当d>0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约

定取P1；能否采用增量算法呢？P=(xp,yp)QP2P1中点画线法若d0->M在直线上方->取P1;此时再下一个象素的判别式为d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+a；增量为aP

=(xp,yp)QP2P1中点画线法若d<0->M在直线下方->取P2;此时再下一个象素的判别式为d2=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；增量为a＋bP=(xp,yp)QP2P1中点画

线法画线从(x0,y0)开始，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来摆脱小数，提高效率。中

点画线法voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,c

olor);while(x<x1){if(d<0){x++;y++;d+=d2;}else{x++;d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/中点画线法例：用中点画线法P0(

0,0)P1(5,2)a=y0-y1=-2b=x1-x0=5d0=2a+b=1d1=2a=-4d2=2(a+b)=6ixiyid1001210-33213431-15425012345321JackElton

BresenhamBresenham算法最初是为数字绘图仪提出，但同样适用于CRT光栅显示器。9/3/2022•浙江大学计算机图形学Bresenham画线算法在直线生成的算法中Bresenham算法是最有效的算法之一。令k=Δy

/Δx，就0≤k≤1的情况来说明Bresenham算法。由DDA算法可知：yi+1=yi+k(1)由于k不一定是整数，由此式求出的yi也不一定是整数，因此要用坐标为（xi,yir）的象素来表示直线上的点，其中yir表示最靠近yi的整数。Bresenham画线算法设图

中xi列上已用（xi,yir）作为表示直线的点，又设B点是直线上的点，其坐标为（xi+1,yi+1），显然下一个表示直线的点（xi+1,yi+1,r）只能从图中的C或者D点中去选。设A为CD边的中点。若B在A点上面则应取D点作为（xi+1,yi+1,r），否则应取C点。xiXi+

1Yi,rYi+1,rCDBAε(x)的几何意义为能确定B在A点上面或下面，令ε(xi+1)=yi+1-yir-0.5(2)若B在A的下面，则有ε(xi+1)<0，反之，则ε(xi+1)>0。由图可知yi+1,r=yir+1，若

ε(xi+1)≥0(3)yi+1,r=yir，若ε(xi+1)≤0Bresenham画线算法由式（2）和式（3）可得到ε(xi+2)=yi+2-yi+1,r-0.5=yi+1+k-yi+1,r-0.5（4）yi+1-yir-0

.5+k-1,当ε(xi+1)≥0yi+1-yir-0.5+k,当ε(xi+1)≤0ε(xi+2)=ε(xi+1)+k-1,当ε(xi+1)≥0ε(xi+2)=ε(xi+1)+k,当ε(xi+1)≤0由式（1）和

式（2）可得到ε(x2)=k-0.5(5)程序如下：BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx,y,dx,dy;floatk,e;inte;dx=x1-x0;dy=y1-y0;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画线算法圆的扫描转换算法下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。假设圆的方程为：X2+Y2=R2圆弧扫描算法X2+Y2=R2Y=Sqrt(R2-X

2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须取整。缺点：浮点运算，开方，取整，不均匀。yx角度DDA法x=x0+Rcosy=y0+Rsindx=-Rsinddy=Rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn+dx=xn-Rsind=x

n-(yn-y0)dyn+1=yn+dy=yn+Rcosd=yn+(xn-x0)d显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。圆的扫描转换圆的扫描转换是在屏幕像素点阵中确定最佳逼近于理想圆的像

素点集的过程。圆的绘制可以使用简单方程画圆算法或极坐标画圆算法，但这些算法涉及开方运算或三角运算，效率很低。主要讲解仅包含加减运算的顺时针绘制1/8圆的中点Bresenham算法原理，根据对称性可以绘制整圆。yOx圆的扫描转换yO

x圆的扫描转换9/3/2022•浙江大学计算机图形学中点画圆法利用圆的对称性，只须讨论1/8圆。第二个8分圆P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。MP1P2P（Xp，Yp）中点画圆法构造函数：F（X，Y）=X2+Y2-R2；则F（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)MP1P2中点画圆法有如下结论：F（M）<0->M在圆内->取P1F（M）>=0->M在圆外->取P2为此，可采用如下判别式：MP1P2中点画

圆法d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若d<0,则P1为下一个象素，那么再下一个象素的判别式为：d1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.

5)2-R2=d+2xp+3即d的增量为2xp+3.P1MP2中点画圆法若d>=0,则P2为下一个象素，那么再下一个象素的判别式为：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+（2xp+3）+（-2yp+2）即d的增量为2(xp-yp)+5.d的初值:d0

=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-RMP1P2中点画圆法MidpointCircle(intr,intcolor){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--;}}}中点画圆法为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。使用e=d-0.2

5代替de0=1-R中点画圆法上述算法能否再改进呢？注意到d的增量是x,y的线性函数，每当x递增1，则d的增量递增Δx=2每当y递减1，则d的增量递增Δy=2Δx初始值=3；Δy初始值=-2r+2见173页算法。Bresenh

am画圆算法现在从A点开始向右下方逐点来寻找弧AB要用的点。如图中点Pi-1是已选中的一个表示圆弧上的点，根据弧AB的走向，下一个点应该从Hi或者Li中选择。显然应选离AB最近的点作为显示弧AB的点。假设圆的半径为R，显然，当xhi2+yhi2-R2≥R2-(xli2+yl

i2)时，应该取Li。否则取Hi。令di=xhi2+yhi2+xli2+yli2-2R2显然，当di≥0时应该取Li。否则，取Hi。Pi-1HiLi应取Hi还是取LiBresenham画圆算法剩下的问题是如何快

速的计算di。设图中Pi-1的坐标为(xi-1,yi-1)，则Hi和Li的坐标为(xi,yi-1)和(xi,yi-1-1)di=xi2+yi-12+xi2+(yi-1-1)2-2R2=2xi2+2yi-12-2yi-1-2R2di+1=(xi+1)2+yi2+(xi+1)2+(yi-1)2-

2R2=2xi2+4xi+2yi2-2yi-2R2+3Pi-1HiLi应取Hi还是取LiBresenham画圆算法当di<0时->取Hi->yi=yi-1，则di+1=di+4xi-1+6当di≥0时->取Li->yi=yi-1-1，则di+1

=di+4(xi-1-yi-1)+10易知x0=0，y0=R,x1=x0+1因此d0=12+y02+12+(y0-1)2-2R2=3-2y0=3-2RPi-1HiLi应取Hi还是取Li生成圆弧的正负法原理：设圆的方程为F(x,y)=X2+Y2-R2=0;假设求得Pi

的坐标为(xi,yi)；则当Pi在圆内时->F(xi,yi)<0->向右->向圆外Pi在圆外时->F(xi,yi)>0->向下->向圆内生成圆弧的正负法即求得Pi点后选择下一个象素点Pi+1的规则为：当F(xi,yi)≤0取xi+1=xi

+1，yi+1=yi;当F(xi,yi)＞0取xi+1=xi，yi+1=yi-1;这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi)时正时负，故称正负法。快速计算的关键是F(xi,yi)的计算，能否采用增量算法？生成圆弧的正负法若F(xi,yi)已知，计算F(xi+1,yi+1)可

分两种情况：1、F(xi,yi)≤0->xi+1=xi+1，yi+1=yi;->F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2->=(xi+1)2+yi2-R2=F(xi,yi)+2xi+12、F(xi,yi)＞0->xi+1=

xi，yi+1=yi-1;->F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2->=xi2+(yi–1)2-R2=F(xi,yi)-2yi+13、初始值：略生成圆弧的多边形逼近法圆的内接正多边形迫近

法圆的等面积正多边形迫近法圆的内接正多边形逼近法思想：当一个正多边形的边数足够多时，该多边形可以和圆无限接近。即因此，在允许的误差范围内，可以用正多边形代替圆。设内接正n边形的顶点为Pi(xi,yi

),Pi的幅角为i,每一条边对应的圆心角为a，则有xi=Rcosiyi=Rsini圆边正内接多边形）nn(lim圆的内接正多边形逼近法内接正n边形代替圆计算多边形各顶点的递推公式Xi+1Rcos(a+i)=Yi

+1Rsin(a+i)Xi+1cosa-sinaXi=Yi+1sinacosaYi因为:a是常数，sina，cosa只在开始时计算一次所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。圆的等面积正多

边形逼近法当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。为了使近似代替圆的正多边形和圆之间在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。圆

的等面积正多边形逼近法步骤：求多边形径长，从而求所有顶点坐标值由逼近误差值，确定边所对应的圆心角α椭圆的扫描转换F(x,y)=b2x2+a2y2-a2b2=0椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分

界点。椭圆上一点处的法向：N(x,y)=(F)'xi+(F)'yj=2b2xi+2a2yj在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1M2在当前中点处，法向量（2b2(Xp+1)，2a2(Y

p-0.5))的y分量比x分量大,即：b2(Xp+1)<a2(Yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分椭圆的中点画法与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的

值，由判别式的符号确定更近的点先讨论椭圆弧的上部分设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5)d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b2根据d1的符号来决定下一像素是取正

右方的那个，还是右上方的那个。若d1＜0，中点在椭圆内，取正右方象素，判别式更新为：d1'=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)d1的增量为b2(2Xp+3)当d1≥0，中点在椭圆外，取右下方象素，更新判别式：

d1'=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)d1的增量为b2(2Xp+3)+a2(-2Yp+2)d1的初始条件：椭圆弧起点为(0，b)；第一个中点为(1,b-0.5)初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)转入

下一部分，下一象素可能是正下方或右下方，此时判别式要初始化。d2=F(Xp+0.5,Yp-1)=b2(Xp+0.5)2+a2(Yp-1)2-a2b2若d2<0,取右下方像素，则d2'=F(Xp+1.5,Yp-2)=d2+b2(2Xp+2)+a2(-2Yp+3)若d2>

=0,取正下方像素，则d2'=F(Xp+0.5,Yp-2)=d2+a2(-2Yp+3)下半部分弧的终止条件为y=0程序：MidpointEllipe(a,b,color)inta,b,color;{intx,y;f

loatd1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);putpixel(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--;}putpixel(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--;}putpixel(x,y,color);}}