计算机图形学chap5-基本图形生成算法

计算机图形学基础华东理工大学计算机系·谢晓玲2如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。第五章基本图形生成算法3图形生成的概念直线段的扫描转换圆的扫描转换多边形的扫描转换与区域填充属性处理反走样技术在OpenGL中绘制图形第五章基本图形生成算法4图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。图5.1用象素点集逼近直线图形生成的概念55.1直线的扫描转换线画图元的扫描转换计算出落在线段上或充分靠近它的一串像素，并以此像素集近似代替连续直线在屏幕上显示的过程。直线的绘制要求（1）直线要直；（2）直线的端点要准确，无定向性无断裂；（3）直线的亮度、色泽要均匀；（4）画线的速度要快；（5）具有不同的色泽、亮度、线型等。6直线的扫描转换解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。数值微分法（DigitalDifferentialAnalyzer,DDA）中点Bresenhan算法改进的Bresenhan算法数值微分法数值微分法即DDA(DigitalDifferentialAnalyzer)算法，是根据直线的微分方程来计算Δx或Δy生成直线的扫描转换算法。在一个坐标轴上以单位间隔对线段取样,以决定另一个坐标轴方向上最靠近理想线段的整数值。数值微分法的本质，是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。数值微分法(DDA法)8数值微分法(DDA法)11yyyxxxiiii直线的微分方程：kxxyyΔxΔydxdy0101ε=1/max(|△x|,|△y|)ε△xxiyxyixi+1yi+1ε△y图5.2DDA算法原理max(|△x|,|△y|)=|△x|，即|k|≤1的情况：max(|△x|,|△y|)=|△y|，此时|k|≥1：11111kyyxyyyyxxxxxxxiiiiiiii111111iiiiiiiiyyyyyyykxxyxxxx数值微分法步骤：给定：两个端点P0(x0,y0)和P1(x1,y1)，则：dx=(x1-x0)；dy=(y1-y0);根据|dx|、|dy|，哪个大，哪个为步长参数：①当|dx||dy|，即|m|1时，若x0x1，即直线从左到右，则x=1，y=m若x0x1，即直线从右到左，则x=-1，y=-m②当|dx|≤|dy|，即|m|≥1时，若x0x1，即直线从左到右，则y=1，x=1/m若x0x1，即直线从右到左，则y=-1，x=-1/m数值微分法(DDA法)voidDDA_Line(intx0,inty0,intx1,inty1,intcolor)inti；floatdx,dy,length,x,y;if(fabs(x1-x0)=fabs(y1-y0))length=fabs(x1-x0);elselength=fabs(y1-y0);dx=(x1-x0)/length;dy=(y1-y0)/length;i=1;x=x0;y=y0;while(i=length){PutPixel(int(x+0.5),int(y+0.5),color);x=x+dx;y=y+dy;i++;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扫描转换举例:线段P0(0,0)和P1(5,2)的DDA方法扫描转换。12增量算法：加法+取整直观、易实现x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现。数值微分法(DDA法)——特点13中点Bresenham算法算法原理：根据直线的斜率确定或选择变量在x或y方向上每次递增一个单位，而另一方向的增量为1或0，它取决于实际直线与相邻象素点的距离，这一距离称为误差项。14中点Bresenham算法直线的方程,0),(0101xxyyxykbkxyyxF其中xyF(x,y)0F(x,y)=0F(x,y)0xyF(x,y)0F(x,y)=0F(x,y)0图5.4直线将平面分为三个区域Pu(xi+1,yi+1)M(xi+1,yi+1/2)P(xi,yi)Pd(xi+1,yi)Q假定0≤k≤1，即0≤Δy/Δx≤1，x是最大位移方向，则每次x加1，若M在Q下放，y加1（取Pu)；若M在Q上放，取y加0（取Pd)。图5.5Brensemham算法生成直线的原理判别式：)1(5.0)5.0,1(),(bxkyyxFyxFdiiiiMM则有：)0()0(1111dydyyxxiiiiiPu(xi+1,yi+1)M(xi+1,yi+1/2)P(xi,yi)Pd(xi+1,yi)Q图5.5Brensemham算法生成直线的原理d的意义：d=F(xM,yM)=F(xi+1,yi+0.5)=yi+0.5-k(xi+1)-b=yi+0.5-[k(xi+1)+b]=yM-yQ这里：yQ=k(xi+1)+b、yM=yi+0.5Pu(xi+1,yi+1)M(xi+1,yi+1/2)P(xi,yi)Pd(xi+1,yi)QQMQMQMyydyydyyd000图5.5Brensemham算法生成直线的原理d0(xi,yi)(xi+1,yi+0.5)(xi+2,yi+1.5)误差项的递推（d10）bxkyyxFdiiii)2(5.1)5.1,2(2kdkbxkydii11)1(5.012bxkyyxFdiiii)1(5.0)5.0,1(1图5.6误差项递推(a)误差项的递推（d1≥0）bxkyyxFdiiii)2(5.0)5.0,2(2d=0(xi,yi)(xi+1,yi+0.5)(xi+2,yi+0.5)bxkyyxFdiiii)1(5.0)5.0,1(1kdkbxkydii12)1(5.0图5.6误差项递推(b)20初始值d的计算kkbkxybxkyyxFd5.05.0)1(5.0)5.0,1(0000000(x0,y0)(x0+1,y0+0.5)中点Bresenham算法图5.9计算初值21改进：用2d△x代替d,令D＝2d△x则：中点Bresenham算法——改进yDikdixxdiDi+1D③dyxDiyxxdikdixxdiDi+1D②dyxkxxd①D2)(220，则取(xi+1,yi)022222)1(220，则取(xi+1,yi+1)02)5.0(220022输入直线的两端点P0(x0,y0)和P1(x1,y1)。计算初始值△x、△y、D=△x-2△y、x=x0、y=y0。绘制点(x,y)。判断D的符号。若D0，则(x,y)更新为(x+1,y+1)，D更新为D+2△x-2△y；否则(x,y)更新为(x+1,y),D更新为D-2△y。当直线没有画完时，重复上一步骤，否则结束。0≤K≤1时Bresenham算法程序演示中点Bresenham算法——算法步骤例：已知：P0（0,0)P1（5,2)dy=y1-y0=2,dx=x1-x0=5d0=dx-2dy=1,令：d1=2dy=4,d2=2(dx-dy)=6i(xi,yi)di(xi+1,yi+1)di+10(0,0)1(1,0)di-d1=-31(1,0)-3(2,1)di+d2=32(2,1)3(3,1)di-d1=-13(3,1)-1(4,2)di+d2=54(4,2)5(5,2)012345321中点Bresenham算法思考讨论：斜率不同时：以上讨论的是0≤k≤1的情况，即0＜△y＜△x的情况；若是0＜△x＜△y（即k≥1）的情况，则需将x和y的位置交换。方向不同时：若△y＜0，将算法中的y＝y＋1换成y＝y－1；若△x＜0，将算法中的x＝x＋1换成x＝x－1。中点Bresenham算法25改进的Bresenham算法假定直线段的0≤k≤111111kyyxyyyyxxxxxxxiiiiiiiiddddkkkkk图5.8改进的Brensemham算法绘制直线的原理d：交点与网格线之间的误差改进的Bresenham算法270.5)(d0.5)(d1111iiiiiyyyxx误差项的计算d初=0，每走一步：d=d+k一旦y方向上走了一步，d=d-1改进的Bresenham算法——原理改进1：令e=d-0.50)(e0)(e1111iiiiiyyyxx•e初=-0.5，•每走一步有e=e+k。•if(e0)thene=e-1;y++0.5)(d0.5)(d1111iiiiiyyyxx误差项的计算•d初=0，•每走一步：d=d+k•if(d0.5)thend=d-1;y++;仍然存在小数和除法计算k。改进2：用E=2e△x来替换e•e初=-0.5•每走一步有e=e+k•if(e0)thene=e-1;y++;•E初=-0.5*2△x=-△x•每走一步有E=(e+k)*2△x=E+2△y•if(e0)thenE=(e-1)*2△x=E-2△x;y++;301.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-△x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2△y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2△x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。改进的Bresenham算法——算法步骤例：已知：P0（0,0)P1（5,2)dy=y1-y0=2,dx=x1-x0=5e0=-dx=-5,令：2dy=4,2dx=10i(xi,yi)eie+2dy(xi+1,yi+1)e-2dx0(0,0)-5-1(1,0)1(1,0)-13(2,1)-72(2,1)-7-3(3,1)3(3,1)-31(4,2)-94(4,2)-9-5(5,2)012345321改进的Bresenham算法325.2圆的扫描转换为了方便起见，只考虑圆心中心在原点、半径为整数R的圆x2+y2=R2。图5.9八分法画圆Voidcirput(intx0,inty0,intx,inty,intcolor){PutPixel(x0+x,y0+y,color);PutPixel(x0+y,y0+x,color);PutPixel(x0+y,y0-x,color);PutPixel(x0+x,y0-y,color);PutPixel(x0-x,y0-y,color);PutPixel(x0-y,y0-x,color);PutPixel(x0-y,y0+x,color);PutPixel(x0-x,y0+y,color);}(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)(x,y)yy=-xy=x34解决问题：只要扫描转换八分之一圆弧（从(0,R)顺时针到(R/2,R/2)），就可以求出整个圆弧的象素集。圆的扫描转换图5.101/8圆弧yy=xxR(0,R)(R/2,R/2)35圆的扫描转换简单方程生成圆弧中点Br