第3章生成算法.docx
- 文档编号:18487504
- 上传时间:2023-08-18
- 格式:DOCX
- 页数:17
- 大小:68.90KB
第3章生成算法.docx
《第3章生成算法.docx》由会员分享,可在线阅读,更多相关《第3章生成算法.docx(17页珍藏版)》请在冰点文库上搜索。
第3章生成算法
第三章基本图形生成算法(书P107)
本章讲直线、圆弧的生成及多边形填充的算法。
一.概念
◆基本图形元素:
指构成图形的基本元素,例如:
点、直线、圆弧等。
◆象素:
屏幕上的光点,它是最小的屏幕显示单位,其大小取决于显示器的尺寸和分辨率。
用坐标表示。
◆生成图形:
确定最佳逼近于图形的象素,用图形颜色对象素进行写操作。
这称为图形的扫描转换。
◆生成直线的质量要求:
①直线要直。
②直线的端点要准确,即无定向性和断裂情况。
③直线的亮度、色泽均匀。
④画线的速度要快。
二.直线生成算法
下面介绍画一个象素宽的直线的三种常用算法:
1.数值微分法(DDA)
所谓DDA法就是先计算出直线的斜率K=
(其中Δy=y1-y0,Δx=x1-x0,而(x0,y0)和(x1,y1)分别是直线的起点和终点),然后从直线的起点开始,确定最佳逼近于直线的y坐标,让x从起点到终点变化,x每递增1,计算对应的y坐标。
令y=kx+b,当xi+1=xi+Δx时yi+1=kxi+1+b
=k(xi+Δx)+b
=kxi+Δxk+b
=kxi+b+Δxk
=yi+Δxk=yi+k
算法如下:
DDAline(x0,y0,x1,y1,color)
intx0,y0,x1,y1,color;
{intx;
floatdx,dy,k,y;
dx=x1-x0;
dy=y1-y0;
k=dy/dx;注意+0.5
y=y0;
for(x=x0;x<=x1;x++)
{putpixel(x,(int)(y+0.5),color);y=y+k;}网格的交点表示象素
}
注意上述算法仅适用于│k│<=1的情况,见程序linedda.c。
若│k│>1,必须把x,y的角色互换,y每增加1,x相应增加1/k。
书P108的算法(DDA.c)综合了各种情况。
2.中点画线法
先看下图所示例子:
若直线在x方向上增加一个单位,则y方向上的增量只能是0或1。
如图中假设P与直线最接近的象素已确定,其坐标为(xp,yp),那么下一个与直线最近的象素只能是P1(xp+1¸yp)或P2(xp+1¸yp+1)两者之一。
用M表示P1与P2的中点,即M=(xi+1¸yi+0.5)。
若M在直线上方,则取P1;否则取P2。
这就是中点画线法的基本原理。
下面讨论中点画线法的实现。
设直线的起点和终点分别为(x0,y0)和(x1,y1),则直线方程为:
F(x,y)=y-kx-b=0其中,k为斜率,b为截距。
对于直线上的点F(x,y)=0;对于直线上方的点F(x,y)>0;对于直线下方的点F(x,y)<0。
因此要判断上图中Q(直线与垂直线的交点)在中点M的上方还是下方,只要把M代入F(x,y),并判断它的符号。
即
F(M)=F(xi+1,yi+0.5)=yi+0.5–k(xi+1)–b,
当F(M)<0时,M在直线的下方(即在Q的下方),故应取右上方的P2作为下一个象素。
而当F(M)>0时,则应取正右方的P1作为下一个象素。
当F(M)=0时,二者一样合适,可任选一个。
算法如下:
MidpointLine(x0,y0,x1,y1,color)
intx0,y0,x1,y1,color;
{intx,y;floatmid,k,b;
k=(y1-y0)/(x1-x0);b=y0-k*x0;
x=x0;y=y0;
putpixel(x,y,color);
do
{mid=y+0.5–k*(x+1)-b;
if(mid<0)y++;
x++;
putpixel(x,y,color);
}while(x } 注: 0<=k<=1。 为提高运算效率,可计算出mid的递推关系式,推导过程如下: 在mid>=0的情况下,取正右方象素P1,欲判断再下一个象素应取那个,递推关系式为: F(xi+2,yi+0.5)=yi+0.5-k(xi+2)-b =yi+0.5-k(xi+1)-b-k; =mid-k; 在mid<0的情况下,则取右上方象素P2,要判断再下一个象素,则要计算 F(xi+2,yi+1.5)=yi+1.5-k(xi+2)-b =yi+0.5-k(xi+1)-b+1-k =mid+1-k; F(M)的初始值为: F(x0+1,y0+0.5)=y0+0.5-k(x0+1)-b =y0-kx0-b+0.5-k =F(x0,y0)+0.5-k=0.5-k 由于(x0,y0)在直线上,故F(x0,y0)=0。 这样算法改为: MidpointLine(x0,y0,x1,y1,color) intx0,y0,x1,y1,color; {intx,y,mid,dx,dy,d_up,d_down; dy=y1-y0;dx=x1-x0; mid=dx-2*dy;/*mid应该为0.5-k,为了摆脱实数运算扩大2dx倍*/ d_up=2*dx-2*dy;d_down=-2*dy;/*注意扩大了2dx倍*/ x=x0;y=y0; while(x<=x1) {putpixel(x,y,color); x++; if(mid<0){y++;mid=mid+d_up;} elsemid=mid+d_down; } } 作业1: 用中点画线法光栅化一条连接两点(0,0)和(5,3)的一条直线。 3.Bresenham画线算法 Bresenham也是通过在每列象素中确定与理想直线最近的象素来进行画线的。 该算法是最为流行的画线方法,它将直线方程转换成一个迭代过程。 与中点画线法类似,只是判中点的方法不同。 如下图所示,只要判直线与垂线的交点到网格线的距离d,当d>0.5往右上方走一步(当xi+1=xi+1时,yi+1=yi+1);当d<0.5时,往正右方走一步(当xi+1=xi+1时,yi+1=yi)。 从上图可得: 为计算方便,令e=d-0.5,所以有: 初始的e0=-0.5. 即有: 这种方法比中点画线法简单。 算法如下: BrsenhamLine(x0,y0,x1,y1,color) intx0,y0,x1,y1,color; {intx,y,dx,dy,i; floatk,e; dx=x1-x0;dy=y1-y0; k=dy/dx;e=-0.5; x=x0;y=y0; for(i=0;i<=dx;i++) {putpixel(x,y,color); x++;e=e+k; if(e>0) {y++;e=e-1;} } } 此算法适用于0<=k<=1。 此算法中用到除法,改进后见P113。 作业2: 从键盘输入封闭多边形的端点坐标(任意斜率),试分别采用中点画线算法和Bresenham算法画出该多边形。 (上机实现) 三.圆的生成算法 画圆的方法很多。 在本节中,主要讨论三种生成圆的算法 一般方法有: 直角坐标法: 根据圆的方程x2+y2=R2来生成,如xi+1=xi+1,y=(int)( +0.5)。 极坐标法: 用圆的极坐标方程(参数方程) 圆x2+y2=R2的参数方程为: x=R*cosθ y=R*sinθ0<=θ<=360 #include #include #definepi3.14159 main() {intdriver,mode,x,y,maxx,maxy,r=60; floatt; driver=DETECT; initgraph(&driver,&mode,""); maxx=getmaxx(); maxy=getmaxy(); line(0,maxy/2,maxx,maxy/2); line(maxx/2,0,maxx/2,maxy); for(t=0;t<=2*pi;t+=0.01) {x=maxx/2+r*cos(t); y=maxy/2+r*sin(t); if(t==0)moveto(x,y); lineto(x,y); } getch(); closegraph();} 1.绘圆的正负法 设所要画的圆的圆心在(a,b),半径为R,则圆的方程为: F(x,y)=(x-a)2+(y-b)2-R2=0,当点(x,y)在圆内时,F(x,y)<0;当点(x,y)在圆外时,F(x,y)>0。 现以画第一四分之一圆弧(第一象限)为例说明正负画圆算法。 设Pi(xi,yj)是已求得的象素点,那么找下一个点Pi+1的原则为: 当F(xi,yj)<=0时,取xi+1=xi+1,yi+1=yi 当F(xi,yj)>0时,取xi+1=xi,yi+1=yi–1 F(xi,yj)<0说明Pi在圆内,要向右走一步得Pi+1,即向圆外方向走去;F(xi,yj)>0,说明Pi在圆外,要向下走一步得Pi+1,即向圆内方向走去。 向圆内或圆外走是取决于F(x,y)的正负,因此称为正负法。 设F(xi,yj)的值已经算出,在计算F(xi+1,yj+1)时有下列两种情况: 当F(xi,yj)<=0时, F(xi+1,yj+1)=F(xi+1,yj)=(xi+1-a)2+(yi-b)2–R2 =(xi-a)2+(yi-b)2–R2+2(xi-a)+1=F(xi,yj)+2(xi-a)+1 当F(xi,yj)>0时, F(xi+1,yj+1)=F(xi,yj-1)=(xi-a)2+(yi-1-b)2–R2 =(xi-a)2+(yi-b)2–R2-2(yi-b)+1=F(xi,yj)-2(yi-b)+1 具体算法如下: PMcircle(a,b,r,color) inta,b,r,color; {intx,y,f; x=a,y=b+r;f=0; while(x<=a+r) {putpixel(x,y,color); if(f<=0){f+=2*(x-a)+1;x++;} else{f=f-2*(y-b)+1;y--;} } } 见程序circle1.c 下面只讨论圆的中心在坐标的原点(0,0),半径为整数R的圆,圆的方程为x2+y2=R2。 对于中心不在原点的圆如圆心在(xc,yc),可以通过平移,化为中心在原点的圆,在对中心在原点的圆进行生成时把所得的象素坐标再加上一个位移量即得所求不在原点的圆的象素坐标。 2.中点画圆法 这里在画圆时,若能生成8分圆,那么圆的其它部分可通过一系列的简单反射变换得到。 见下图: 这里我们讨论从(0,R)到(R/ ,R/ )顺时针地确定最佳逼近该圆弧的象素序列。 假设P(xp,yp)是圆上的点,那么P的下一个象素只能是正右方的P1(xp+1,yp)或右下方的P2(xp+1,yp-1)两者之一。 构造函数: F(x,y)=x2+y2-R2 对于圆上的点F(x,y)=0 对于圆外的点F(x,y)>0 对于圆内的点F(x,y)<0 设M是P1和P2的中点,即 M=(xp+1,yp-0.5),当 F(M)<0,M在圆内,则取P1为下一个象素 F(M)>=0,M在圆外,则取P2为下一个象素 下面构造递推式: 令d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2 若d<0,则F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2 =(xp+1+1)2+(yp-0.5)2-R2 =(xp+1)2+2(xp+1)+1+(yp-0.5)2-R2 =d+2xp+3 所以沿正右方向,d的增量为2xp+3。 若d>=0,则F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2 =d+2(xp-yp)+5 所以沿右下方向,d的增量为2(xp-yp)+5。 下面给出按顺时针方向生成第二个8分圆的算法,初始点是(0,R),递推式d的初始值为: d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R MidpointCircle(intr,intcolor) {intx,y;floatd; x=0;y=r;d=1.25-r; putpixel(x,y,color) while(x { if(d<0)d=d+2*x+3; else{d=d+2*(x-y)+5;y--;} x++; putpixel(x,y,color); } } 3.Bresenham画圆法 这里考虑圆心在原点,半径为R的第二个8分圆。 取(0,R)为起点,按顺时针方向生成圆。 在生成圆时,为了最佳逼近该圆,下一个象素的取法有二种可能的选择: 正右方象素H,右下方象素L Pi-1(xi-1,yi-1)正右Hi(xi,yi) 右下Li(xi,yi) H点和L点到圆弧的距离分别为: ∆H=(xi-1+1)2+yi-12-R2 ∆L=(xi-1+1)2+(yi-1-1)2-R2 令di=∆H+∆L 当di<0时,则H更靠近圆,取H。 当di>0时,则L更靠近圆,取L。 下面给出di+1、di的递推公式 起点(0,R),则初值为: d1=(0+1)2+R2-R2+(0+1)2+(R-1)2-R2=3-2R di=(xi-1+1)2+yi-12-R2+(xi-1+1)2+(yi-1-1)2-R2 =2(xi-1+1)2+2yi-12-2yi-1-2R2+1 当di<0,取H时: di+1=(xi-1+2)2+yi-12-R2+(xi-1+2)2+(yi-1-1)2-R2 =(xi-1+1+1)2+yi-12-R2+(xi-1+1+1)2+(yi-1-1)2-R2 =2(xi-1+1)2+2yi-12-2yi-1-2R2+1+4(xi-1+1)+2 =di+4(xi-1+1)+2=di+4xi-1+6 当di>0,取L时: di+1=(xi-1+2)2+(yi-1-1)2-R2+(xi-1+2)2+(yi-1-2)2-R2 =di+4(xi-1-yi-1)+10 voidbresenhamarc(intr,intcolor) {intx,y,d; x=0;y=r; d=3-2*r; while(x<=y) {putpixel(x,y,color); if(d<0)d=d+4*x+6; else{d=d+4*(x-y)+10;y--;} x++; } } 作业3: 分别用正负法、中点法和Bresenham算法画三个同心整圆。 (上机实现) 若考虑圆心在原点,半径为R的第一个4分圆。 则下一个象素的取法有三种可能的选择: 正右方象素,右下方象素和正下方象素。 分别记为H、D和V (x,y)正右H(x+1,y) 正下V(x.,y-1)右下D(x+1,y-1) 上述三点到圆心的距离平方与圆弧上一点到圆心的距离平方之差为: ∆H=(x+1)2+y2-R2 ∆D=(x+1)2+(y-1)2-R2 ∆V=x2+(y-1)2-R2 (1)若∆D<0(D在圆内),则最佳逼近圆弧的象素只可能是H或D。 为了确定H和D哪个更近接近于圆弧,令: δHD=│∆H│-│∆D│=│(x+1)2+y2-R2│-│(x+1)2+(y-1)2-R2│ 若δHD<0,则H更靠近圆,取H; 若δHD>0,则取D; 若δHD=0,则二者均可取,设取H。 下面计算δHD: (a)当∆H>=0(H在圆外)时,而∆D<0,所以有 δHD=(x+1)2+y2-R2+(x+1)2+(y-1)2-R2 =2∆D+2y-1 故可根据2∆D+2y-1的符号判断取H或D。 (b)当∆H<0(H在圆内)时,而在这段圆弧上y是x的单调递减函数,所以只能取H为下一个象素。 又由于∆H<0且∆D<0,因此∆H+∆D<0,而2∆D+2y-1<0正好表示取H,所以不重新计算δHD来判断取H。 若要计算δHD也可以,δHD=-((x+1)2+y2-R2)+(x+1)2+(y-1)2-R2=1-2y, 而0 本算法是采用2∆D+2y-1来判断。 可见在∆D<0的情况下,若2∆D+2y-1<=0,则取H为下一个象素;否则应取D为下一个象素。 (2)若∆D>0(D在圆外),则则最佳逼近圆弧的象素只可能是D或V。 计算δDV。 令: δDV=│∆D│-│∆V│=│(x+1)2+(y-1)2-R2│-│x2+(y-1)2-R2│ 如果δDV<0,即圆到D距离较小,这是应取D为下一个象素。 如果∆V>0,则应取V。 ∆V=0,二者均可取,约定取D。 同样的,计算δDV: (a)先考虑∆V<0的情况,由于∆D>0,所以有: δDV=│∆D│-│∆V│=(x+1)2+(y-1)2-R2+x2+(y-1)2-R2 =2(∆D-x)-1 (b)当∆V>0(V在圆外)时,显然应取V为下一个象素。 这时∆D>0且∆V>0,因此可用2(∆D-x)-1>0来一同判断。 可见,在∆D>0情况下,若2(∆D-x)-1<=0,取D;否则应取V为下一个象素。 (3)当∆D=0(D在圆上),故取D。 归纳上述情形,可得计算下一个象素的算法: 当∆D<0时,若δHD<=0,则取H,否则取D; 当∆D>0时,若δDV<=0,则取D,否则取V; 当∆D=0时,则取D。 由于δHD,δDV均可由∆D推算出来的,先计算∆D的初值: ∆D=(x+1)2+(y-1)2-R2=(0+1)2+(R-1)2-R2=2-2R=2(1-R) 再求∆D的递推式: 首先考虑下一个象素为H的情况,对于H,其坐标(x+1,y)=(x′,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′+1 再考虑下一个象素为D的情况,D的坐标为(x+1,y-1)=(x′,y′),其误差项为: ∆D′=((x+1)+1)2+((y-1)-1)2-R2 =∆D+2(x+1)-2(y-1)+2=∆D+2x′-2y′+2 对于V,其坐标(x,y-1)=(x′,y′),其误差项为: ∆D′=(x+1)2+((y-1)-1)2-R2 =∆D-2(y-1)+1=∆D-2y′+1 Bresenham画圆算法如下: Bresenham_Circle(intr,intcolor) {intx,y,delta,delta1,delta2,direction; x=0;y=r; delta=2*(1-r); while(y>=0) {putpixel(x,y,color); if(delta<0)/*∆D<0*/ {delta1=2*(delta+y)-1; if(delta1<=0)direction=1;/*取H*/ elsedirection=2;/*取D*/ } elseif(delta>0)/*∆D>0*/ {delta2=2*(delta-x)-1; if(delta2<=0)direction=2;/*取D*/ elsedirection=3;/*取V*/ } elsedirection=2;/*∆D=0,取D*/ switch(direction) {case1: x++;delta=delta+2*x+1;break; case2: x++;y--;delta=delta+2*(x-y+1);break; case3: y--;delta=delta+(-2*y+1);break; } }/*whileend*/ }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 生成 算法