计算机图形学(孙家广第三版)-第2章

第2章光栅图形学2.1直线段的扫描转换算法2.2圆弧的扫描转换算法2.3多边形的扫描转换与区域填充2.4字符2.5裁剪2.6反走样2.7消隐图形的扫描转换(光栅化）光栅扫描显示器可以看做一个像素的矩阵。在光栅显示器上显示图形，确定最佳逼近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转换或光栅化。•一维图形的扫描转换（光栅化）：不用考虑线宽，用一个像素宽度显示图形。•二维图形的光栅化：确定像素集，填色或图案。•任何图形的光栅化，必须显示在一个窗口内，否则不予显示。确定一个图形的哪些部分在窗口内，哪些在窗口外的过程称为裁剪。图形显示之前必须要经过扫描转换和裁剪两个步骤：•裁剪→扫描转换：最常用，节约计算时间；•扫描转换→裁剪：算法简单。二维裁剪扫描转换显示2.1直线段的扫描转换算法直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。三个常用算法：2.1.1数值微分法（DDA）2.1.2中点画线法2.1.3Bresenham算法。2.1.1数值微分(DDA)法BasicIdea：GivenastraightlineLovertwopointsP0(x0,y0),P1(x1,y1)y=kx+b直线斜率为0101xxyyk2.1.1数值微分(DDA)法BasicIdea：从x的左端点x0开始，向x右端点步进。步长=1(个象素)，计算相应的y坐标y=kx+B；取象素点(x,round(y))作为当前点的坐标。计算yi+1=kxi+1+B=k1xi+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地位互换例：画直线段p(0,0)--P1(5,2)xint(y+0.5)y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5注：网格点表示象素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;2.1.2中点画线法BasicIdeaIfcurrentpointis(xp,yp),thenthenextpointiseitherP1orP2.LetM=(xp+1,yp+0.5)bethecenterpointofP1andP2.QistheintersectionoflineLandx=xp+1.CompareQandM:IfMisbelowQ,P2isthenextpoint;Otherwise,P1isthenextpoint.•过(x0,y0),(x1,y1)两端点的直线段的隐式方程：F(x,y)=ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0•直线的正负划分性F(x,y)0F(x,y)0F(x,y)=0y0x直线上方的点：F(x,y)0直线下方的点：F(x,y)0Constructadiscriminativefunction:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c其中a=y0-y1,b=x1-x0,c=x0y1-x1y0Ifd0,MisbelowL(Q),P2isthenextpoint;Ifd0,MisaboveL(Q),P1isthenextpoint;Ifd=0,bothP1andP2areOK,(统一取P1）d是xp,yp的线性函数，因此可采用增量计算，提高运算效率。Ifforcurrentpoint,d0,thenP1,forthenextpoint:d1=F(M1)=a(xp+2)+b(yp+0.5)=d+a；增量为aIfforcurrentpoint,d0,thenP2,forthenextpoint:d2=F(M2)=a(xp+2)+b(yp+1.5)+c=d+a+b；增量为a＋b画线从(x0,y0)开始，d的初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b=a+0.5b。可以用2d代替d来摆脱小数，提高效率。令d0=2a+b,d1=2a,d2=2a+2b,我们有如下算法。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,color);while(xx1){if(d0){x++,y++,d+=d2;}else{x++,d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/例：用中点画线法P0(0,0)P1(5,2)a=y0-y1=-2,b=x1-x0=5d0=2a+b=1,d1=2a=-4,d2=2(a+b)=6ixiyid1001210-33213431-154252.1.3Bresenham算法BasicIdea过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。Letthelinebe：，wherek=dy/dx。∵直线的起始点在象素中心，∴d0＝0，d＝d＋k。一旦d≥1，d=d-1，这样保证d在0、1之间。当d≥0.5时，最接近于当前象素的右上方象素（xi＋1，yi＋1而当d0.5时，更接近于右方象素（xi＋1，yi）。为方便计算，令e＝d-0.5，e的初值为-0.5，增量为k。而当e0时，更接近于当e≥0时，取当前象素（xi，yi）的右上方象素（xi＋1，yi＋1）；右方象素（xi＋1，yi）。kyxxkyyiiiii)(11voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy;floatk,e;dx=x1-x0,dy=y1-y0,k=dy/dx;e=-0.5,x=x0,y=y0;for(i=0;idx;i++){drawpixel(x,y,color);x=x+1，e=e+k;if(e0){y++,e=e-1;}}}例：Line:P0(0,0),P1(5,2)k=dy/dx=0.4xye00-0.510-0.1210.331-0.3420.152-0.5012345321•可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：dx*e*2e'如何画一个中心在原点，半径为R的圆？2.2圆弧的扫描转换算法R圆的特征:八对称性。只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集中点画圆法考虑中心在原点，半径为R的第二个8分圆，构造判别式（圆方程）222)5.0()1()5.0,1()(RyxyxFMFdppppP=(xp,yp)P1P2M若d0,则取P1为下一象素，而且再下一象素的判别式为若d=0,则应取P2为下一象素，而且下一象素的判别式为第一个象素是（0,R），判别式d的初始值为32)5.0()2()5.0,2('222pppppxdRyxyxFd5)(2)5.1()2()5.1,2('222ppppppyxdRyxyxFdRRFd25.1)5.0,1(0算法过程MidPointCircle(intrintcolor){intx,y;floatd;x=0;y=r;d=1.25-r;circlepoints(x,y,color);//显示圆弧上的八个对称点while(x=y){if(d0)d+=2*x+3;else{d+=2*(x-y)+5;y--;}x++;circlepoints(x,y,color);}}为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。Howtomodify？2.3多边形的扫描转换与区域填充多边形有两种重要的表示方法：顶点表示和点阵表示。多边形的扫描转换:把多边形的顶点表示转换为点阵表示。区域可采用内点表示和边界表示两种表示形式。区域填充:指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。多边形分为凸多边形、凹多边形、含内环的多边形。2.3.1多边形的扫描转换扫描线算法BasicIdea：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。对于一条扫描线填充过程可以分为四个步骤：（1）求交（2）排序（3）配对（4）填色一个多边形与若干扫描线0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量△x。设该边的直线方程为：ax+by+c=0；若y＝yi，x=xi；则当y=yi+1时，其中为常数;)(111abxcybaxiiiiabx数据结构新边表（NET）：存放在该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中活性边表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中结点内容x：当前扫描线与边的交点坐标△x：从当前扫描线到下一条扫描线间x的增量ymax：该边所交的最高扫描线号ymax扫描线与多边形的顶点或边界相交时，必须正确的交点的取舍。只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。123P1P2P3P4算法过程voidpolyfill(polygon,color)intcolor;多边形polygon;{for(各条扫描线i){初始化新边表头指针NET[i]；把ymin=i的边放进边表NET[i];}y=最低扫描线号；初始化活性边表AET为空；for(各条扫描线i){把新边表NET[i]中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；遍历AET表，把配对交点区间(左闭右开)上的象素(x,y)，用drawpixel(x,y,color)改写象素颜色值；遍历AET表，把ymax=i的结点从AET表中删除，并把ymaxi结点的x值递增x；若允许多边形的边自相交，则用冒泡排序法对AET表重新排序；}}/*polyfill*/边界标志算法基本思想：帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。使用一个布尔量inside来指示当前点是否在多边形内的状态。算法过程voidedgemark_fill(polydef,color)多边形定义polydef；intcolor;{对多边形polydef每条边进行直线扫描转换；inside=FALSE;for(每条与多边形polydef相交的扫描线y)for(扫描线上每个象素x){if(象素x被打上边标志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background);}}用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个