计算机图形学2

光栅显示器上显示的图形，称之为光栅图形。光栅显示器可以看作是一个象素矩阵，在光栅显示器上显示的任何一个图形，实际上都是往帧缓存寄存器的相应填入描述颜色和灰度的象素的集合。由于对一个具体的光栅显示器来说，象素个数是有限的，象素的颜色和灰度等级也是有限的，象素是有大小的，所以光栅图形只是近似的实际图形。如何使光栅图形最完美地逼近实际图形，便是本章要研究的内容。确定最佳逼近图形的象素集合，并用指定的颜色和灰度设置象素的过程称为图形的扫描转换或光栅化。图5-1用一系列的象素点来逼近直线图形的扫描转换（光栅化）分为二个步骤：1、确定有关像素2、用图形的颜色或其它属性，对像素进行写操作。对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充。确定像素集，填色或图案。任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。图形显示前需要：扫描转换+裁剪数学上的直线是没有宽度、由无数个点构成的集合。直线的绘制要求：•1.直线要直•2.直线的端点要准确，即无定向性和断裂情况•3.直线的亮度、色泽要均匀•4.画线的速度要快•5.要求直线具有不同的色泽、亮度、线型等2.1.1直线DDA算法(DigitalDifferentialAnalyser)假设直线的起点坐标为P1(x1,y1)，终点坐标为P2(x2,y2)x方向的增量为△x＝x2－x1；y方向上增量为△y＝y2－y1直线的斜率为k＝△y／△x当△x＞△y时，让x从x1到x2变化，每步递增1，那么，x的变化可以表示为xi+1＝xi＋1y的变化可以表示为yi+1＝yi＋k2.1.1直线DDA算法(DigitalDifferentialAnalyser)用上式可求得图中直线P1P2和y向网格线的交点，但显示时要用舍入,找到最靠近交点处的象素点耒表示。当△x△y时，让y递增1，x作相应变化。综合考虑，按照从(x1,y1)到(x2,y2)方向不同，分8个象限(图2.1)。对于方向在第1a象限内的直线而言，取增量值Dx=1，Dy=m。对于方向在第1b象限内的直线而言，取增量值Dy=1，Dx=1/m。2.1.1直线DDA算法（续）图2.1直线方向的8个象限象限dxdy?DxDy1atrue1m1bfalse1/m12atrue-1m2bfalse-1/m13atrue-1-m3bfalse-1/m-14atrue1-m4bfalse1/m-1表2.18个象限中的坐标增量值研究表中的数据，可以发现两个规律。⒈当dxdy时Dx=1，Dy=m否则Dx=1/m，Dy=1⒉Dx、Dy的符号与dx、dy的符号相同。2.1.1直线DDA算法（续）算法描述如下：dda_line(xa,ya,xb,yb,c)intxa,ya,xb,yb,c;{floatdelta_x,delta_y,x,y;intdx,dy,steps,k;dx=xbxa;dy=ybya;if(abs(dx)abs(dy))steps=abs(dx);elsesteps=abs(dy);delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)steps;2.1.1直线DDA算法（续）x=xa;y=ya;set_pixel(x,y,c);for(k=1;k=steps;k++){x+=delta_x;y+=delta_y;set_pixel((int)(x+0.5),（int)(y+0.5),c);}}使用DDA算法，每生成一条直线做两次除法，画线中每一点做两次加法。因此，用DDA法生成直线的速度是相当快的。数值微分(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)2.1.2直线Bresenham算法设直线从起点(x1,y1)到终点(x2,y2)。直线可表示为方程y=mx+b，其中b=y1-m*x1,m=（y2-y1)/(x2-x1)=dy/dx;此处的讨论先将直线方向限于1a象限,在这种情况下，当直线光栅化时，x每次都增加1个单元，即xi+1=xi+1,而y的相应增加值应当小于1。为了光栅化，yi+1只可能选择图中两种位置之一。2.1.2直线Bresenham算法(续）yi+1的位置选择yi+1=yi或者yi+1=yi+1，选择的原则是看精确值y与yi及yi+1的距离d1及d2的大小而定。计算公式为y=m(xi+1)+b(2.1)d1=yyi(2.2)d2=yi+1y(2.3)如果d1d20，则yi+1=yi+1，否则yi+1=yi。将式(2.1)、(2.2)、(2.3)代入d1d2，再用dx乘等式两边，并以Pi=(d1d2)dx代入上述等式，得Pi=2xidy2yidx+2dy+(2b1)dx(2.4)d1d2是用以判断符号的误差。由于在1a象限，dx总大于0，所以Pi仍旧可以用作判断符号的误差。Pi+1为Pi+1=2xi+1dy2yi+1dx+2dy+(2b1)dx=2xidy+2dy2(yi+1yi)dx-2yidx+2dy+(2b1)dx=Pi+2dy2(yi+1yi)dx(2.5)2.1.2直线Bresenham算法2.1.2直线Bresenham算法(续）求误差的初值P1，可将x1、y1和b代入式(2.4)中的xi、yi而得到P1=2dydx综述上面的推导，第1a象限内的直线Bresenham算法思想如下：⒈画点(x1,y1)，dx=x2x1，dy=y2y1，计算误差初值P1=2dydx，i=1；⒉求直线的下一点位置xi+1=xi+1如果Pi0，则yi+1=yi+1，否则yi+1=yi；⒊画点(xi+1,yi+1)；⒋求下一个误差Pi+1，如果Pi0，则Pi+1=Pi+2dy2dx，否则Pi+1=Pi+2dy；⒌i=i+1；如果idx+1则转步骤2；否则结束操作。2.1.2直线Bresenham算法(续）Bresenham算法的优点如下：⒈不必计算直线的斜率，因此不做除法。⒉不用浮点数，只用整数。⒊只做整数加减运算和乘2运算，而乘2运算可以用移位操作实现。Bresenham算法的运算速度很快，并适于用硬件实现。讨论：以上讨论的是0＜△y＜△x的情况，对于适用所有8个方向的直线(图2.1)的生成算法，则要考虑以判断条件|dx||dy|为分支，并分别将2a、3a象限的直线和3b、4b象限的直线变换到1a、4a和2b、1b象限方向去，以实现程序处理的简洁。2.1.2直线Bresenham算法圆的特征:圆被定义为到给定中心位置(xc,yc)距离为r的点集。圆心位于原点的圆有四条对称轴x=0,y=0,x=y和x=-y。若已知圆弧上一点(x,y),可以得到其关于四条对称轴的其它7个点，这种性质称为圆的八对称性。2.2.1基础知识不失一般性，我们可以假设圆心（xc,yc）就在原点。否则只需要把求到的圆上的点（x,y）作一下平移变换即可。x’=x+xc,y’=y+yc便可得到圆心在（x,y）的圆上的点（x’,y’）。要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集。显示圆弧上的八个对称点的算法：voidCirclePoints(intx,inty,intcolor){set_pixel(x,y,color);set_pixel(y,x,color);set_pixel(-x,y,color);set_pixel(y,-x,color);set_pixel(x,-y,color);set_pixel(-y,x,color);set_pixel(-x,-y,color);set_pixel(-y,-x,color);}2.2.1基础知识给出圆心坐标(xc,yc)和半径r，逐点画出一个圆周的公式有下列两种：⒈直角坐标法(xxc)2+(yyc)2=r2由上式导出：cc22()yyrxx当xxc从r到r作加1递增时，就可以求出对应的圆周点的y坐标。但是这样求出的圆周上的点是不均匀的，xxc越大，对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆不美观。2.2.1基础知识(续）⒉极坐标法x=xc+r·cosθ，y=yc+r·sinθ当θ从0到π作递增时，由此式便可求出圆周上均匀分布的360个点的(x,y)坐标。dx=-Rsinddy=Rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn+dx=xn-Rsind=xn-(yn-y0)dyn+1=yn+dy=yn+Rcosd=yn+(xn-x0)d显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。2.2.2圆的Bresenham算法设圆的半径为r。先考虑圆心在(0,0)，并从x=0、y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束。即有xi+1=xi+1相应的yi+1则在两种可能中选择：yi+1=yi或者yi+1=yi1选择的原则是考察精确值y是靠近yi还是靠近yi1(图2.4)，图2.4y的位置2.2.2圆的Bresenham算法(续）计算式为y2=r2(xi+1)2d1=yi2y2=yi2r2+(xi+1)2d2=y2(yi1)2=r2(xi+1)2(yi1)2令pi=d1d2，并代入d1、d2，则有pi=2(xi+1)2+yi2+(yi1)22r2(2.6)pi称为误差。如果pi0则yi+1=yi，否则yi+1=yi1。pi的递归式为pi+1=pi+4xi+6+2(yi2+1yi2)2(yi+1yi)(2.7)pi的初值由式(2.6)代入xi=0，yi=r而得p1=32r(2.8)根据上面的推导，圆周生成算法思想如下：⒈求误差初值，p1=32r，i=1，画点(0,r)；⒉求下一个光栅位置，其中xi+1=xi+1，如果pi0则yi+1=yi，否则yi+1=yi1；⒊画点(xi+1,yi+1)；⒋计算下一个误差，如果pi0则pi+1=pi+4xi+6，否则pi+1=pi+4(xiyi)+10；⒌i=i+1，如果x=y则结束，否则返回步骤2。2.2.2圆的Bresenham算法2.2.2圆的Bresenham算法(续）程序实现如下：circle(xc,yc,radius,c)intxc,yc,radius,c;{intx,y,p;x=0;y=radius;p=32*radius；while(xy){plot_circle_points(xc,yc,x,y,c);if(p0)p=p+4*x+6;else{p=p+4*(xy)+10;y=1;}x+=1;}if(x==y)plot_circle_points(xc,yc,x,y,c);}2.2.2圆的Bresenham算法(续）plot_circle_points(xc,yc,x,y,c)intxc,yc,x,y,c;{set_pixel(xc+x,yc+y,c);set_pixel(xcx,yc+y,c);set_pixel(xc+x,ycy,c);set_pixel(xcx,ycy,c);set_pixel(xc+y,yc+x,c);set_pixel(xcy,yc+x,c);set_pixel(xc+y,ycx,c);set_pixel(xcy,ycx,c);}2.3.1基础知识区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示：用多