第二章光栅图形学-3.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息科学与技术学院 康宝生,*,计算机图形学,Northwest University,第二章 光栅图形学（,3,）,5/18/2026,1,信息科学与技术学院 康宝生,2.6,光栅图形的裁剪操作,识别图形在指定区域内或区域外的部分的过程称为,裁剪,，用于裁剪对象的区域称为裁剪窗口。,裁剪的应用包括：从定义的场景中抽取出用于观察的部分,；,在三维视图中标识可见面；防止线段或对象的边界混淆；用实体造型来创建对象；显示多窗口的环境；允许选择图形的部分进行拷贝、移动或删除等图形编辑操作。对于不同的应用，裁剪窗口可以是多边形或包含曲线边界的多边形，但以矩形窗口最为常见。,5/18/2026,2,信息科学与技术学院 康宝生,当裁剪操作在世界坐标系中进行时，只有窗口内的部分映射到输出设备坐标系中。若裁剪操作在设备坐标系或规范化设备坐标系中进行时，首先将世界坐标系中的图形映射到设备坐标系或规范化设备坐标系中，然后用视区边界裁剪。世界坐标系下的裁剪将落在窗口外的图形部分删除，从而不必将这些图形变换到设备坐标系中去。视区裁剪可通过合并观察和几何变换矩阵来减少计算量，但需要将所有的对象（包括在窗口之外的部分）变换到设备坐标系。,基,本的图形裁剪算法有：,5/18/2026,3,信息科学与技术学院 康宝生,点的裁剪；,直线段的裁剪；,多边形的裁剪；,曲线的裁剪；,字符的裁剪。,直线和多边形的裁剪是图形软件包中的标准部分。许多软件包中亦有曲线、拟合曲线、圆锥曲线的裁剪。另外，处理曲线物体的方法是把它们近似为直线段，然后用直线或多边形的裁剪算法进行裁剪。,5/18/2026,4,信息科学与技术学院 康宝生,2.6.1,点的裁剪,设裁剪窗口是一个由参数,x,L,，,x,R,，,y,B,和,y,T,所确定的矩形。如果点满足下列不等式：,x,L,x,x,R,y,B,y,y,T,则保存该点用于显示。如果这四个不等式中有任何一个不满足,，,则该点被裁剪。,虽,然点的裁剪不如直线和多边形的裁剪用的多，但是某些应用中还是需要点的裁剪。例如，点的裁剪可以用于粒子爆炸或海面泡沫的显示，它们是通过场景中分散的粒子建模。,5/18/2026,5,信息科学与技术学院 康宝生,2.6.2,直线段的裁剪,直,线段的裁剪过程包括几个部分：首先测试一个给定的线段，判断它是否完全落在裁剪窗口内。如果没有完全落在窗口内，再判断是否完全落在窗口外。最后，对既不能确定完全落在窗口内又不能确定完全落在窗口外的线段，计算它与一个或多个裁剪边界的交点。图,1,给出了线段和标准矩形裁剪窗口之间的各种关系。,5/18/2026,6,信息科学与技术学院 康宝生,我们,通过对线段的端点进行,“,内部外部,”,测试来处理线段。对于两个端点都在窗口内的,线段,(,如图,1,中的,P,1,P,2,),予以保,P,2,P,1,P,3,P,4,P,5,P,6,P,7,P,8,图,1.,直线段与裁剪窗口的关系,5/18/2026,7,信息科学与技术学院 康宝生,在该线段与裁剪边界求交时，可求得参数,u,值。若 ，则该线段不在该边界处进入窗口内。否则，线段穿过了裁剪区。该方法可用于各个裁剪边界，以便确定是否该线段的所有部分,存，两个端点都在同一条裁剪边界外的线段,(,如图,1,中的,P,3,P,4,),判断为落在窗口外，而其他贯穿一个或多个裁剪边界的线段需要计算多个交点。为了使计算量最小，需设计一个能有效地识别外部线段并减少求交运算的裁剪算法。,对,于端点为,P,i,=(,x,i,y,i,),i,=0,1,的线段，其参数方程为：,5/18/2026,8,信息科学与技术学院 康宝生,都显示。平行于窗口边界的线段作为特殊情况处理。,使,用参数测试的线段裁剪方法要进行大量的计算。目前已研究出了许多有效的线段裁剪算法，下面我们讨论几种主要的算法。一些算法是针对二维图形的，一些算法很容易移植到三维应用中。,1.,Sutherland,Cohen,算法,这是最早流行的直线段裁剪算法。该算法基于区域编码，通过初始测试来减少求交次数以加快线段裁剪的速度。,以裁剪窗口的四条边界将平面区域分为九个子区域，为每个子区域赋以相应的编码，称为,区域码,(,region code,),，每,个子,5/18/2026,9,信息科学与技术学院 康宝生,区域中的点采用同一编码。区域码的各位指出点关于裁剪窗口的四个相对坐标位置：左、右、下、上。将区域码各位从右到左编号，则坐标区域与各位的关系,如下,(,图,2,),：,图,2.,区域编码,y,y,T,y,B,x,L,x,R,x,0000,1000,0001,0100,0101,0110,1001,0010,1010,5/18/2026,10,信息科学与技术学院 康宝生,这里：位,1,：左；位,2,：右；位,3,：下；位,4,：上。任何位置赋值,1,，代表点落在相应的位置上，否则为,0,。,对,于要裁剪的线段的两个端点，根据所在区域确定其相应的编码。各位的值按以下两步确定：计算端点坐标和裁剪边界之间的差值；用各差值的符号位来设置区域码中相应的值。第一位为,x,-,x,L,的符号位，第二位,为,x,R,x,的符号位，第三位,为,y,-,y,B,的符号位，第四位,为,y,T,-,y,的,符号位。,一旦,确定了线段两端点的区域码，便可快速判断完全可见和完全不可见的线段。如果线段两端点的编码均为,0000,，则该线段完全可见；如果线段两端点的编码中同一位都为,1,则该线,5/18/2026,11,信息科学与技术学院 康宝生,线段完全不可见。如果上述判断不能定论，则需要进行线段与,窗口边界的求交计算。按照左、右、下、上的顺序用裁剪边界检查线段的端点，以确定应裁剪掉的线段部分。我们以图,3,中的线段为例说明,SutherlandCohen,算法,的处理过程。,5/18/2026,12,信息科学与技术学院 康宝生,图,3.,线段,P,0,P,1,的裁剪,P,0,P,1,对于线段,P,0,P,1,，,由下端点,P,0,开始，依次按左、右、下、上边界对,P,0,检查。发现,P,0,位于下边界的下方,然后求线段,P,0,P,1,5/18/2026,13,信息科学与技术学院 康宝生,与下边界的交点,P,0,，并舍弃线段,P,0,P,0,。对于端点,P,1,进行同样的检查，发现,P,1,位于左边界的左侧，求线段,P,0,P,1,与左边界的交点,P,1,。但,P,1,位于上边界之上，因此再求一次交点，计算得到,P,1,”,，并舍弃线段,P,1,P,1,”,，该线段的裁剪处理完毕。,在与裁剪边界的求交计算中，直线段采用截斜式方程。对于端点坐标为,P,i,=(,x,i,y,i,),i,=0,1,的直线，与垂直边界交点,y,坐标由下述公式计算：,其中，,x,值为,x,L,或,x,R,。,寻找与水平边界交点的,x,坐标的计算公式是：,5/18/2026,14,信息科学与技术学院 康宝生,x,=,x,0,+(,y,y,0,),(,x,1,x,0,)/(,y,1,y,0,),其中，,y,值为,y,B,或,y,T,。,下面给出,SutherlandCohen,直线段裁剪算法的程序实现，各端点的编码以字节存储，并按位操作处理。,算法,2.6.1 Sutherland-Cohen,裁剪算法,#define,LEFT 1,#define,RIGHT 2,#define,BOTTOM 4,#define,TOP 8,int,encode(float x,float y),5/18/2026,15,信息科学与技术学院 康宝生,int,c=0;,if,(x XR)c|=RIGHT;,if,(y YT)c|=TOP;,renturn,c;,void,SC_LineClip(x1,y1,x2,y2,XL,XR,YB,YT),float,x1,y1,x2,y2,XL,XR,YB,YT;/(x1,y1),、,(x2,y2),为线段端点坐标，其他四个参数定义窗口边界,int,code1,code2,code;,code1=encode(x1,y1);,code2=encode(x2,y2);,5/18/2026,16,信息科学与技术学院 康宝生,while,(code1!=0|code2!=0),if,(code1&code2!=0),return,;,if,(code1!=0)code=code1;,else,code=code2;,if,(LEFT&code!=0),/,点在窗口左边界左侧,x=XL;,y=y1+(y2,y1),*,(XL x1)/(x2 x1);,else if,(RIGHT&code!=0),/,点在窗口右边界右侧,x=XR;,y=y1+(y2 y1)*(XR x1)/(x2 x1);,else if,(BOTTOM&code!=0),/,点在窗口下边界下方,5/18/2026,17,信息科学与技术学院 康宝生,y=YB;,x=x1+(x2,x1),*,(YB y1)/(y2 y1);,else if,(TOP&code!=0),/,点在窗口上边界上方,y=YT;,x=x1+(x2 x1),*,(YT y1)/(y2 y1);,if,(code=code1),x1=x;y1=y;code1=encode(x,y);,else,x2=x;y2=y;code2=encode(x,y);,displayline,(x1,y1,x2,y2);,5/18/2026,18,信息科学与技术学院 康宝生,2.,中点分割裁剪算法,与,Sutherland-Cohen,算法一样，中点分割裁剪算法首先对线段端点进行编码，并据此把线段与窗口的关系分为三种情况：全在窗口内、完全不在窗口内、线段与窗口相交。对前两种情况作一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点，即从点,P,0,出发找出距,P,0,最近的可见点,A,，并从点,P,1,出发找出距,P,1,最近的可见点,B,，两个可见点之间的连线即为线段,P,0,P,1,的可见部分，如图所示。,采用中点分割方法从,P,0,出发找最近可见点：先求出,P,0,P,1,的中点,P,m,。若,P,0,P,m,不是显然不可见的，并且,P,0,P,1,在窗口中有可,5/18/2026,19,信息科学与技术学院 康宝生,见部分，则,距,P,0,最近的可见点一定落在,P,0,P,m,上，故用,P,0,P,m,代替,P,0,P,1,；否则用,P,m,P,1,代替,P,0,P,1,；再对新的,P,0,P,1,求中点,P,m,。重复上述过程，直到,P,m,P,1,的长度小于给定的控制常数为止。求距,P,1,最近的可见点过程一样，只要把,P,0,和,P,1,交换即可。由于该算法的主要计算过程只用到加法和除,2,运算，所以特别适合硬件实现，同时也适合于并行计算。求,距,P,0,最近的可见点的框图,P,0,P,1,P,m,A,B,5/18/2026,20,信息科学与技术学院 康宝生,如下。,P,0,可见否,P,0,P,1,显然不,可见,P,m,=,(,P,0,+,P,1,)/2,|,P,m,P,1,|,e,?,P,0,P,m,显然不,可见,P,0,=,P,m,P,1,=,P,m,A,=,P,m,A,=,P,0,原线段完全不,可见,exit,exit,exit,Y,N,N,N,N,Y,Y,Y,5/18/2026,21,信息科学与技术学院 康宝生,3.,梁友栋,Barsky,算法,该算法基于线段的参数方程的分析，通过减少计算交点的次数，使其速度较之,SutherlandCohen,算法更快。,端点为,P,i,=(,x,i,y,i,),i,=0,1,的线段，其参数方程为：,其中,D,x,=(,x,1,x,0,),，,D,y,=(,y,1,y,0,),。直线段,P,0,P,1,上点的裁剪条件是：,5/18/2026,22,信息科学与技术学院 康宝生,任何平行裁剪边界之一的直线满足条件,P,i,=0,，,若还满足,Q,i,0,，,则线段完全在边界外，舍弃该线段。若,Q,i,0,，,则线段平行于裁剪边界并在窗口内，需用另外一组边界进行检查,。,这四个不等式可以表示为,其中，,P,i,Q,i,定义如下,：,5/18/2026,23,信息科学与技术学院 康宝生,当,P,i,0,时，线段从裁剪边界延长线内部延伸到外部。当,P,i,0,时，线段与边界,i,的延长线的交点参数为：,对于每条线段，可计算出参数,u,1,、,u,2,，它们定义了在窗口内部的线段部分。,u,1,的值由线段从外到内遇到的,边界,(,P,i,0),所,决定。计算：,则：,若,u,1,u,2,，则线段完全落在裁剪窗口之外，舍弃；若,u,1,u,2,，则线段可见部分的两端点由参数,u,1,、,u,2,计算而得。,梁友栋,Barsky,算法程序描述如下。线段与边界交点的参数初始化为,u,1,=0,，,u,2,=1,。,计算出各个裁剪边界的,P,、,Q,值，函数,ClipTest,用,P,、,Q,来判断是否舍弃线段还是改变交点的参数。当,P,0,时，参数,r,用于,5/18/2026,25,信息科学与技术学院 康宝生,更新,u,2,。当,P=,0,且,Q,0,时，舍弃该线段。,P,、,Q,的四个值经过测试后，该线段未被舍弃，则裁剪线段的端点由参数,u,1,、,u,2,的值决定。,算,法,2.6.2,梁友栋,-,Barsky,裁剪算法,boolean,ClipTest(float,p,float q,float*u1,float*u2),float,r;,if,(p *u2),return,FALSE;,else if,(r *u1),*u1=r;,return,TRUE;,5/18/2026,26,信息科学与技术学院 康宝生,else if,(p 0.0),r=q/p;,if,(r,*,u1),return,FALSE;,else if,(r,*,u2),*,u2=r;,return,TRUE;,else if,(q 0.0),return,FALSE;,void,LB_LineClip,(x1,y1,x2,y2,XL,XR,YB,YT),float,x1,y1,x2,y2,XL,XR,YB,YT;,float,u1=0.0,u2=1.0,dx,=x2 x1,dy,=y2 y1;,if,(,ClipTest,(,dx,x1 XL,&u1,&u2),5/18/2026,27,信息科学与技术学院 康宝生,if,(,ClipTest,(,dx,XR x1,&u1,&u2),if,(,ClipTest,(,dy,y1 YB,&u1,&u2),if,(,clipTest,(,dy,YT y1,&u1,&u2),if,(u2 0.0),x1=x1+u1*dx;y1=y1+u1*dy;,displayline,(x1,y1,x2,y2),return,;,5/18/2026,28,信息科学与技术学院 康宝生,梁友栋,-,Barsky,算法比,Sutherland-Cohen,算法更有效，因为需要计算的交点数目交少了。更新参数,u,1,、,u,2,仅仅需要一次除法；线段与窗口的交点仅计算一次，就计算出,u,1,、,u,2,的最后值。相比之下，即使一条完全落在裁剪窗口之外，,Sutherland-Cohen,算法也要对它反复求交点，而且每次求交都需要进行乘除法运算。,Sutherland-Cohen,算法和梁友栋,-,Barsky,算法都可以扩展为三维裁剪算法。,4.,Nicholl-Lee-Nicholl,算法,简称,NLN,算法,，,通过在裁剪窗口周围创建多个区域的途径,5/18/2026,29,信息科学与技术学院 康宝生,来避免对一条直线段的多次裁剪。,在,Sutherland-Cohen,算法中，在找到与裁剪边界的交点之前或完全舍弃该线段之前，必须对一条线段进行多次求交计算；而,NLN,算法在求交计算前进行更多的区域测试来减少求交计算。与梁友栋,-,Barsky,算法和,Sutherland-Cohen,算法相比，,NLN,算法的比较次数和除法次数减少了，但该算法仅适用于二维直线段的裁剪，而梁友栋,-,Barsky,算法和,Sutherland-Cohen,算法,可以很方便地推广到三维裁剪。,NLN,算法的执行分为两步：,5/18/2026,30,信息科学与技术学院 康宝生,（,1,）对于端点为,P,1,、,P,2,的线段，,首先决定,P,1,相对于裁剪窗口的九个区域的位置，我们这里仅考虑三个区域，如下图,所示。对于其他六个区域，可利用对称变换将其变为这三个区,域中的任何一个区域。,NLN,裁剪算法中线段端点,P,1,的三种位置,P,1,P,1,P,1,5/18/2026,31,信息科学与技术学院 康宝生,（,2,）,判断端点,P,2,相对于,P,1,的位置，,根据,P,1,的位置在平面上建立新的区域，新区域的边界是由,P,1,发出的穿过窗口角点的射线,，如下图,所示。,P,1,在窗口内,P,1,B,R,L,T,LB,LR,P,1,L,LT,L,L,P,1,在窗口左侧,5/18/2026,32,信息科学与技术学院 康宝生,如果,P,1,位于窗口内，,P,2,位于窗口外，我们设置四个裁剪区域：,L,、,T,、,R,和,B,。,根据点,P,2,所在区域，决定直线段和窗口边界的求交计算。如果,P,2,在窗口内，则为可见线段。,如果,P,1,位于窗口左边区域，则设定四个区域：,L,、,LT,、,LR,和,LB,。这四个区域决定了裁剪线段的惟一窗口边界。若,P,2,在,L,区域，则用左边界裁剪线段，且保存从交点到,P,2,之间的线段；若在,LT,区域，则保存左边界到上边界之间的线段；若不在这四个区域的任何一个中，则舍弃整个线段。,对于第三种情况，当,P,1,在窗口的左上方时,按照,P,1,相对于窗口左上角的位置,，,有两种可能（见下图）。,5/18/2026,33,信息科学与技术学院 康宝生,P,1,LB,TR,L,T,T,TB,P,1,LB,TR,L,T,L,LR,P,1,在窗口左上方时的裁剪区域,若,P,2,在区域,L,、,T,、,TR,、,TB,、,LR,或,LB,中，则决定了求交计算的惟一裁剪窗口边界，否则整个,线段被舍弃。,为了确定,P,2,在何区域，要比较该线段的斜率和裁剪区域边界的斜率。例如，如果在裁剪边界的左边,那么,P,2,LT,的条件,5/18/2026,34,信息科学与技术学院 康宝生,是,或者,若满足下列条件：,(,y,T,y,1,)(,x,2,x,1,)ClipBoundary0.x)/,裁剪边界为窗口下边界,if,(TestPt.y,=ClipBoundary0.y),return,TRUE;,if,(ClipBoundary1.x ClipBoundary0.x)/,裁剪边界为窗口上边界,if,(TestPt.y,ClipBoundary0.y)/,裁剪边界为窗口右边界,5/18/2026,42,信息科学与技术学院 康宝生,if,(TestPt.x,=ClipBoundary0.x),return,TRUE;,if,(ClipBoundary1.y=ClipBoundary0.x),return,TRUE;,return,FALSE;,void,Output(,Vertex,newVertex,int,*,outLength,Vertex,*,OutVertexArray,),(*,outLength,)+;,OutVertexArray,*,outLength,1.x=,newVertex.x,;,OutVertexArray,*,outLength,1.y=,newVertex.y,;,5/18/2026,43,信息科学与技术学院 康宝生,void,SutherlandHodgemanClip(,VertexArray,InVertexArray,VertexArray,OutVertexArray,Edge,ClipBoundary,int,inLength,int,*,outLength,),Vertex,S,P,ip,;,int,j;,*,outLength,=0;,S=,InVertexArrayinLength,1;/,从最后一个顶点开始,for,(j=0;j,inLength,;j+),P=,InVertexArrayj,;,if,(Inside(P,ClipBoundary,),if,(Inside(S,ClipBoundary,)/S,，,P,在窗口内,Output(P,outLength,OutVertexArray,);,5/18/2026,44,信息科学与技术学院 康宝生,else,/S,在窗口外，,P,在窗口内,Intersect(S,P,ClipBoundary,&,ip,);,Output(ip,outLrngth,OutVertexArray,);,Output(P,outLength,OutVertexArray,);,else if,(Inside(S,ClipBoundary,)/S,在窗口内，,P,在窗口外,Intersect(S,P,ClipBoundary,&,ip,);,Output(ip,outLength,OutVertexArray,);,/S,，,P,在窗口外是没有输出,S=P;/,转到下一对顶点继续运行,5/18/2026,45,信息科学与技术学院 康宝生,利用,Sutherland-Hodgeman,算法对凸多边形进行裁剪时可获得正确的裁剪结果，但是对凹多边形的裁剪将不能得到正确的结果，如下图所示，显示出一条多余的线段。这种情况在裁剪后的多边形有两个以上的分离部分时出现，因为只有一个输出顶点表，所以表中最后一个顶点总是与第一个顶点相连。,凹多边形的裁剪,裁剪前,多余的线段,裁剪后,5/18/2026,46,信息科学与技术学院 康宝生,为了正确地裁剪凹多边形，有以下几种方法，其一是将凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形；其二是修改,Sutherland,Hodgeman,算法，沿着任何一个裁剪窗口边界检查顶点表，正确地连接顶点对；第三种方法就是随后介绍,的,Weiler,Atherton,算法,。,凹多边形的判定与分解,在,xy,平面上判定和分解凹多边形的方法有两种。,（,1,）向量法。沿多边形的边界计算相邻边向量的叉乘可判定凹多边形。如果一些叉乘的,z,分量为正,另一些叉乘的,z,分量,5/18/2026,47,信息科学与技术学院 康宝生,为负，则该多边形必为凹多边形，否则为凸多边形。,例 分解凹多边形的向量法,给定一多边形，其边向量如下：,V,1,V,2,V,3,V,4,V,5,V,6,E,1,E,2,E,3,E,4,E,5,E,6,5/18/2026,48,信息科学与技术学院 康宝生,（,2,）,旋转法。沿多边形逆时针前进，将多边形顶点,V,k,平移到坐标原点,然后顺时针旋转多边形,使下一顶点,V,k,+1,在,x,轴上,.,因,(,E,2,E,3,),z,=,-,2 0,，我们沿,E,2,的延长线分解多边形，求其和多边形的交点，这样一个多边形分为两个,。由于这两个子多边形边向量的叉乘的,z,分量均为正，所以它们都是凸多边形。,V,1,V,2,V,3,V,4,V,5,E,1,E,2,E,3,E,4,E,5,V,1,V,3,V,2,E,2,E,3,E,1,5/18/2026,49,信息科学与技术学院 康宝生,如果下一顶点,V,k,+2,位于,x,轴下方，即,V,k,+2,y,0,，则该,多边形为凹多边形，沿,x,轴将多边形分解为两个子多边形。对两个子多边形重复进行凹多边形测试；否则，继续旋转在,x,轴上方的顶点，测试顶点的,y,坐标是否为负。下图说明了分解凹多边形的旋转法。,V,1,V,2,V,3,V,4,V,5,V,6,E,1,E,2,E,3,E,4,E,5,E,6,V,1,V,2,V,3,V,4,V,5,V,6,E,1,E,2,E,3,E,4,E,5,E,6,5/18/2026,50,信息科学与技术学院 康宝生,2.,Weiler,Atherton,多边形裁剪算法,Weiler,Atherton,算法基于修改多边形边界顶点的处理过程来获得凹多边形的正确裁剪。该算法开始是作为识别可见面的方法而提出的，因此可用于任意多边形窗口的裁剪。,算法的基本思想是：有时沿着多边形边的方向来处理顶点，有时沿着窗口的边界方向处理顶点。采用哪一条路径，要根据多边形处理方向（顺时针或逆时针）和当前处理的多边形顶点对是由内向外还是由外到内来决定。若顺时针处理顶点，则采用的规则是：,5/18/2026,51,信息科学与技术学院 康宝生,对由外到内的顶点对，沿多边形边界的方向；,对由内向外的顶点对，按顺时针沿窗口边界的方向。,下图给出了,Weiler,Atherton,算法的处理方向和被裁剪的多边形。,Weiler,Atherton,算法的进一步发展就是,Weiler,算法，用于窗口为任意多边形的多边形裁剪。,V,1,V,2,V,3,V,4,V,5,V,6,凹多边形,产生的分离多边形,I,1,V,2,V,3,I,2,I,3,V,5,I,4,5/18/2026,52,信息科学与技术学院 康宝生,2.6.4,字符的裁剪,字符的裁剪技术取决于字符的生成方法和具体应用，一般地，图形软件中包含了几种裁剪技术。,最简单的裁剪字符串的方法是全部保留和全部舍弃字符串，称为,串精度,裁剪。如果字符串的所有字符都在裁剪窗口内，就全部保留，否则舍弃整个字符串。,另一种处理方法是，与窗口边界有重叠的字符串是取舍整个字符，既全部保留或全部舍弃一个字符，称为,字符精度,裁剪。在这种方法中,每,一个字符的边界要与窗口比较，凡与窗口,5/18/2026,53,信息科学与技术学院 康宝生,边界有重叠或落在窗口之外的字符均舍弃。,最后一种方法是对各个字符本身裁剪，称为,笔画或像素,精,度,裁剪。当字符为轮廓字时，用线段裁剪方法进行；对位图（点阵）定义的字符而言，则通过比较字符网络中各个像素对裁剪边界的相对位置来裁剪。,5/18/2026,54,信息科学与技术学院 康宝生,STRING2,STRING1,待裁剪字符串,STRING2,串精度裁剪,STRING2,字符精度裁剪,RING1,STRING2,RING1,笔画精度裁剪,5/18/2026,55,信息科学与技术学院 康宝生,2.6.5,外部裁剪,前面讨论的仅仅是舍弃窗口外的图形部分，保留窗口内的图形部分的过程。然而，在许多应用中需要保留窗口外部的图形部分，而舍弃窗口内的图形部分，既外部裁剪。,外部裁剪的典型应用之一是多窗口系统。要正确地显示屏幕窗口，我们既需要内部裁剪又需要外部裁减。窗口内部的对象用内部裁剪，若有优先级更高的窗口覆盖在这些对象上，则对象用覆盖窗口进行外部裁剪。,外部裁剪也常用于有覆盖图形的情况。例如,在,广告或出版,5/18/2026,56,信息科学与技术学院 康宝生,应用中的页面布局设计或者为图形加上标签和设计图模。外部裁剪技术还可以将图形、图象、简图合成起来。这些应用通过外部裁剪为将它们插入一幅较大的图中提供空间。,凹多边形窗口的内部裁剪可通过外部裁剪来实现。下面以图图示的方式说明用凹多边形,V,1,V,2,V,3,V,4,V,5,裁剪线段,P,1,P,2,，,分为两步实现：,用凸多边形窗口,V,1,V,2,V,3,V,4,对,P,1,P,2,做内部裁剪，得到裁剪后的线段 ；,用凸多边形,V,1,V,5,V,4,对 做外部裁剪，得到线段,.,5/18/2026,57,信息科学与技术学院 康宝生,V,1,V,2,V,3,V,4,P,1,P,2,V,1,V,2,V,3,V,4,P,1,P,2,V,1,V,2,V,3,V,4,P,2,P,1,P,2,P,1,P,1,P,2,内部裁剪,外部裁剪,5/18/2026,58,信息科学与技术学院 康宝生,2.7,光栅图形的反走样,由于我们将物体上的坐标点数字化为离散的整数像素位置，因而光栅算法生成的图形显示具有锯齿形或台阶状的外观。这种由于低频采样不充分而造成的信息失真称为走样,(,aliasing,),。对此，可使用校正不充分采样过程的反走样,(,antialiasing,),方法来改善所显示的光栅图形外观。,增加光栅系统采样率的方法之一是简单地以较高分辨率显示对象。但即使用当前技术能达到的最高分辨率，锯齿形仍会在一定范围内出现,.,由于能将帧缓冲器做成多大并仍保持刷新率,5/18/2026,59,信息科学与技术学院 康宝生,在每秒,30,60,帧方面存在限制，而且要用连续参数精确地表示对象需要任意小的采样间隔。因此，除非硬件技术能发展到做成任意大的帧缓冲器，增加屏幕分辨率还不能完全解决走样问题。,对于能显示两级以上光亮度的光栅扫描系统，可以用反走样方法来修改像素亮度。通过适当改变沿图元边界的像素亮度，可光顺边界以减少锯齿现象。,一种直接的反走样方法是把屏幕看成比实际所具有的更细的网格来增加采样率，而后沿这种更细的网格使用采样点来确定每个屏幕像素的合适亮度等级。这种高分辨率计算,低,分辨率,5/18/2026,60,信息科学与技术学院 康宝生,显示的反走样技术称为过采样（,Supersampling,或后滤波，因为像素亮度是子像素亮度的组合,),。,代替过采样的另一种反走样方法是通过计算待显示像素在对象上的覆盖区域来确定像素亮度。计算覆盖区域的反走样方法称为区域采样（,Area Sampling,或前滤波，因为像素亮度作为一个整体来确定，而不要计算子像素亮度）。像素覆盖区域通过确定对象边界与单个像素边界的相交处而得到。,光栅对象也可将像素区域显示位置移动而实现反走样，这种技术称为像素移相。它通过与对象几何形状相关的电子束的,“,微定位,”,而作用。,5/18/2026,61,信息科学与技术学院 康宝生,2.7.1,直线段的过采样,直线段的过采样可以多种方法完成。对于直线段的灰度显示，可以把每个像素分成一定数目的子像素并统计沿线路径的子像素数目，而后将每个像素的亮度等级设置为正比于该子像素数目的值。例如，对下图的线段，每个像素区域被分割成九个子像素。,因为任何像素中可供选择的子像素最大数目为,3,，这种方法提供了零以上三种亮度设置。对于这个具体的例子,像素,20,21,22,10,11,12,5/18/2026,62,信息科学与技术学院 康宝生,(10,20),设置为最高亮度（级别,3,）；像素,(11,21),和,(12,21),被设置为次亮度,(,级别,2),；,(11,20),和,(12,22),被设置为零以上最低级别（级别,1,）,。,这样，线亮度分布在较大数目像素上,并且,通过在阶梯状台阶附近显示有些模糊的线路径使阶梯形状得到光顺。如果要用更多的亮度等级来反走样，就需要增加每个像素的采样位置数：,n,2,个子像素提供零,以上,n,个,亮度等级。,在前面的过采样例子中，我们考虑了有限尺寸的像素区域，但把线处理成具有零宽度的数学实体。实际上，显示的线具有约与像素等宽的宽度。如果考虑到线的有限宽度，则可通过将每个像素亮度设置成正比于在表示线区域的多边形内的子,5/18/2026,63,信息科学与技术学院 康宝生,像素数目来完成过采样。若子像素的左下角在多边形内，那么,可把此子像素当作在线内。这种过采样的一个好处是，每个像素可能的亮度等级数等于像素区域内子像素的总数。对上图的线段，可以通过对平行于线路径的多边形边界定位，来以有限宽度表示这样的线，如图所示，并且每个像素现在可设置成零以上九个亮度级别之一。,20,21,22,10,11,12,5/18/2026,64,信息科学与技术学院 康宝生,用有限宽线过采样的另一个优点是：总的线亮度分布在更多的像素上。同样，如果是彩色显示，我们也可将此方法扩充来将背景色考虑进去。一特定的线可能穿过许多不同的颜色区域，我们可对子像素亮度进行平均来得到像素颜色设置。例如，一特定像素区域内的五个子像素被确定在红线的边界内，而其余四个像素落在蓝色背景区域内，则可将该像素的颜色计算为：,Pixel_Color,=(5*RED+4*BLUE)/9,由过采样有限宽线得知,鉴别,内部子像素比简单地确定沿线,5/18/2026,65,信息科学与技术学院 康宝生,路径的子像素需要更多的计算。参照线路径定位线边界的计算也是复杂的，这种定位取决于线的斜率。,对于,45,0,线，线路径在多边形区域的中央；但无论是对水平线还是垂直线，都要求线路径是多边形的边界之一。对斜率,|,m,|,1,的线，数学线路径被定位在最接近于上面多边形边界。,2.7.2,像素加权掩模,过采样算法在实现时，经常给接近像素区域中心的子像素赋以更大的权值,因为,我们希望这些子像素在确定像素的整体亮,5/18/2026,66,信息科学与技术学院 康宝生,度中起更重要的作用。例如，对,3,3,的像素分割，采用的加权方案如下图所示。其中，中心子像素的权值是角子像素权值的,4,倍，是其他子像素权值的,2,倍，而后对九个子像素的每个网格所计算的亮度进行平均。,指定子像素的相对重要性的值数组称为子像素权的“掩模”。也可为较大的子像素网格建立类似的掩模。,1,2,1,2,2,1,4,2,1,33,子像素网格相对权值,5/18/2026,67,信息科学与技术学院 康宝生,2.7.3,直线段的区域采样,通过将每个像素亮度设置为正比于像素与有限宽线的重迭区域，可实现对直线的区域采样。将线看成长方形，而在两相邻垂直（或两相邻水平）屏幕网格线间的线区域为四边形，像素的重迭区域就可通过确定在垂直列（或水平行）中每个像素覆盖多少个四边形而计算出。在线边界内子像素的总数近似等于覆盖区域，并且这种判断通过采用更细子像素网格而得到提高。对于彩色显示，则计算被不同颜色区域覆盖的像素区域，最后的像素颜色看作为各覆盖区域的平均颜色。,5/18/2026,68,信息科学与技术学院 康宝生,2.7.4,过滤技术,直线反走样更精确的方法是过滤技术。这种方法类似于应用像素加权掩模，只是现在假想一个连续的加权曲面（或过滤函数）覆盖像素。常用的过滤函数有立方体、圆锥和高斯曲面。应用过滤函数的方法类似于应用加权掩模，但现在是将曲面积分来得到加权的平均亮度。为减少计算量，通常用查表法来求整数值。,5/18/2026,69,信息科学与技术学院 康宝生,2.7.5,多边形区域边界的反走样,直线段的反走样概念也可用于多边形区域的边界以消除其锯齿形外观。多边形区域边界的反走样方法，是以像素区域覆盖率为基础来确定每个边界位置处的像素亮度。具体说，当某像素与多边形区域相交时，求出两者相交区域的面积，然后以此面积值来决定该像素的颜色值或灰度值。,计算一个像素与多边形区域相交区域的面积是很费时间的事。为了提高多边形反走样算法的速度，,Pitteway,和,Watkinson,将画直线的,Bresenham,算法发展成多边形的反走样,5/18/2026,70,信息科学与技术学院 康宝生,算法。为了简单起见，假定多边形一边的方程是：,且多边形位于该边的右面,(,见图,),。用,Bresenham,算法画直线时，每一步要计算判定函数,P,i,以确定表示直线的像素点,(,x,i,y,i,),，由,P,i,的几何意义可知，,P,i,越大，像素和多边形相交区域的面积越大，反之亦然。因而可用,P,i,确定像素点,(,x,i,y,i,),灰度值,。,多边形位于线段右侧,5/18/2026,71,信息科学与技术学院 康宝生,不难证明,令,则易知,0,d,i,1,。由于反映了,P,i,的大小，故可直接用于确定像素点,(,x,i,y,i,),的灰度值。那么，用,代替画直线的,Bresenham,算法中的判定函数,P,，,即可得到多边形反走样算法的程序。,5/18/2026,72,信息科学与