第03章2基于光栅扫描转换的二维图元生成算法

计算机图形学第3章基于光栅扫描的二维图元生成算法第二部分3.6裁剪在许多应用中，面对一张大的画面，或者是由于实际需要，或者是显示屏幕有限，常要求在一个矩形区域内指定要显示的部分画面。这种用来指定图形显示内容的矩形区域称为裁剪窗口。窗口内的图形被显示出来了，而窗口之外的图形则被裁剪掉。从图形的显示过程知道，任何图形在显示之前都要经过裁剪工作。因此图形的裁剪和图形的变换一样，直接影响图形系统的效率。裁剪的方法很多，效率的高低常与计算机图形硬件水平及图形复杂程度有关，要根据实际情况来选择合适的裁剪算法3.6裁剪裁剪的基本目的是判断这个图形元素是否落在窗口区域之内，如落在区域之内则进一步求出位于区域之内的部分。因此裁剪处理的基础有两个方面：一是图元在窗口区域内外的判别，二是图形元素与窗口的求交。

裁剪可以对扫描转换之后的点阵图形在设备坐标系中进行，也可以在世界坐标系中对扫描转换之前的参数表示的图形进行。前者算法简单，但效率不高，因为无论图形落在窗口的内部还是外部，都要扫描转换，它一般适用于求交难度较大的图形。而后者主要应用于点、线、多边形等简单图元。由于世界坐标系一般为浮点坐标系，故有时也称世界坐标系中的裁剪为分析裁剪，它是大多数图形系统所采用的裁剪方法3.6.1窗口视口变换窗口：由用户坐标系定义的一个矩形区域；视口：由设备坐标系定义的一个矩形区域；当把用户坐标系中的图形在图形设备上输出时，可以定义适当的窗口和视口，使窗口的图形在视口内显示，处于窗口外或视口外的图形则不被显示即称被裁剪掉。固定视口而改变窗口，就可以在视口中观察到用户描述的全部图形了视口HVLV(XV1，YV1)窗口HW(XW1，YW1)LW窗口与视口的关系用户坐标系设备坐标系3.6.2线段裁剪裁剪算法有二维的和三维的，裁剪对象可以是规则形体，也可以是不规则形体，其裁剪算法可以用硬件实现，也可以用软件实现。在进行裁剪时，画面中对应于屏幕显示的那部分区域也即窗口，把其定义为矩形，由上、下、左、右四条边围成，即：(xL，yB)，(xR，yH)。裁剪的实质就是决定图形中哪些点、线段、文字、以及多边形在裁剪窗口之内，在窗口内的图形被保留显示，而窗口之外的画面被裁去。如图所示。对于点(x，y)，只要判别两对不等式：xLxxR， yByyH若四个不等式均成立，则点在窗口矩形之内；否则，点在窗口矩形之外。其中,等号表示点位于窗口的边界上。1.Cohen-Sutherland算法Cohen-Sutherland算法有时也称为编码算法，该算法分为三个步骤：第一步：判别线段两端是否都落在窗口内，如果是，则线段完全可见；否则进入第二步第二步：判别线段是否为显然不可见，即线段的两端点均落在窗口某边所在直线的外侧，如果是，则裁剪结束；否则进入第三步第三步：求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，舍弃。对余下的另一段重新进行第一步、第二步判断，直至结束。1.Cohen-Sutherland算法整个裁剪过程可以看作一个递归过程。为了实现这个算法，首先用窗口四条边所在的直线将整个二维平面分成9个区域，如图3-36。每个区域赋予一个四位的编码CtCbCrCl，其中各位编码的含义如下：1.Cohen-Sutherland算法如图是各个区的编码的十进制数。判断线段的一个端点是否在窗口内部，只需判断它的编码值是否为0。注意到编码中各个位的含义，当两个端点的编码的逻辑“与”非0时，它们必然落在窗口某边的外侧，也即线段为显然不可见的1.Cohen-Sutherland算法线段端点编码实例两个端点“逻辑与”操作的语义是两个“端点都怎么样”1.Cohen-Sutherland算法对既非完全可见，又非显然不可见的线段，如图3-38中的AD，需要进行求交运算。求交前实现要测试线段和窗口哪条边所在直线有交，这只要判断线段两端点编码中各位的值即可。如图中的AD，D点编码中的Cl=1，而A点编码中的Cl=0，则知道AD和窗口的左边所在直线有交。在程序中，求交测试的顺序是固定的。不妨假定求交测试的顺序为窗口的左边、上边、右边、下边。按照这个顺序，线段EJ和窗口四边被求出的交点顺序为F、I、H、G。从而在Cohen-Sutherland裁剪算法中，最坏的情况下，一条线段在裁剪时需要求交四次1.Cohen-Sutherland算法intLineClip(CPoint&posBeg,CPoint&posEnd,CRectrect){ intaccept,done; charc0,c1,code; intx0,y0,x1,y1,x,y; doublem; accept=0;//线段可见标志

done=0;//裁剪完成标志

x0=m_posBeg.x; y0=m_posBeg.y; x1=m_posEnd.x; y1=m_posEnd.y; c0=GetCSCode(x0,y0,rect);//返回线段起点的编码

c1=GetCSCode(x1,y1,rect);//返回线段终点的编码1.Cohen-Sutherland算法while(!done){ if(!c0&&!c1){//线段完全可见 posBeg.x=x0; posBeg.y=y0; posEnd.x=x1; posEnd.y=y1; accept=1; done=1; }elseif(c0&c1){//线段完全不可见 posBeg.x=0; posBeg.y=0; posEnd.x=0; posEnd.y=0; accept=0; done=1;}1.Cohen-Sutherland算法

else{//处理非完全可见又非显然不可见的情况 if(c0){//首点不可见。Code=首点 code=c0;（code指向不可见的那一方） } else{//首点可见，code=终点 code=c1; } if(code&0x01){//线段与窗口的左边有交

x=rect.left; m=(double)(y1-y0)/(double)(x1-x0); y=y0+(int)((x-x0)*m); } elseif(code&0x08){//线段与窗口的上边有交 y=rect.top; m=(double)(x1-x0)/(double)(y1-y0); x=x0+(int)((y-y0)*m); }1.Cohen-Sutherland算法elseif(code&0x02){//线段与窗口的右边有交 x=rect.right; m=(double)(y1-y0)/(double)(x1-x0); y=y0+(int)((x-x0)*m); } elseif(code&0x04){//线段与窗口的下边有交 y=rect.bottom; m=(double)(x1-x0)/(double)(y1-y0);

x=x0+(int)((y-y0)*m);

}1.Cohen-Sutherland算法if(code==c0){ x0=x; y0=y; c0=GetCSCode(x0,y0,rect); } else{ x1=x; y1=y; c1=GetCSCode(x1,y1,rect);

}}}returnaccept;}1.Cohen-Sutherland算法CharGetCSCode(intx,inty,CRectrt){ charcode=0; if(x<rt.left)//编码为***1,最后一位置1 code=code|0x01; else//编码为***0，最后一位置0 code=code&0xfe;

if(x>rt.right)//编码为**1* code=code|0x02; else//编码为**0* code=code&0xfd;1.Cohen-Sutherland算法if(y<rt.bottom)//编码为*1** code=code|0x04;else//编码为*0** code=code&0xfb;if(y>rt.top)//编码为1*** code=code|0x08;else//编码为0*** code=code&0xf7;returncode;}2.中点分割算法在图中的b线段，检查端点编码可知它既不是完全可见段，也不是完全不可见段，则在中点Pm1处将b分为二段，两段的情况仍然相同。先不考虑P1Pm1，在Pm2处将Pm1P2分为二段从图中可见，Pm1Pm2完全可见，而Pm2P2部分可见。这样处理的结果将导致线段的可见部分被划分成一系列的可见小段然后再逐段画出，显然效率降低。2.中点分割算法求P1最远可见点的算法：1)

若P2在窗口内，则P2就是离P1最远的可见点，结束该算法，否则进行下一步;2)

若P1P2为完全不可见，则结束该算法，否则进行下一步；3)

取P1P2中点Pm，若Pm点在窗口内部，则处理PmP2线段来寻找P1的最远可见点，即用Pm代替P1，执行2，否则P2用Pm代替，执行2。直到Pm与线段端点的距离达到分辩率精度为止。3.6.3多边形裁剪在光栅显示系统中，常常需要显示输出具有连续色彩的图形区域，图形区域一般由多边形构成，这时就需要处理多边形区域的裁剪问题了。通常有一种错觉，认为只要把多边形的每条边用对直线段的裁剪方法裁剪后，就完成了对多边形的裁剪，其实不然。在图形学中，多边形定义了一个封闭的二维区域，裁剪结果也应该是一个封闭的多边形区域。多边形裁剪有其自身的特殊性，这种特殊性表现在：第一，多边形的边被裁剪后一般就不再封闭了，需要用窗口边界的适当部分来封闭它，如何确定这部分的边界？如图3.6.3多边形裁剪第二，一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？如图1.Sutherland-Hodgman逐次裁剪算法Sutherland-Hodgman多边形裁剪算法采用了分割处理的策略，将多边形关于矩形窗口的裁剪分割为多边形关于窗口四边所在直线的裁剪。所以该算法有时也称为逐边裁剪算法。多边形关于窗口四边的裁剪是相继进行的，不妨假定裁剪顺序为左边、上边、右边，下边，那么原多边形关于窗口左边的裁剪结果多边形作为关于上边裁剪的输入多边形，…。裁剪过程是一个流水线过程，如图1.Sutherland-Hodgman逐次裁剪算法假设当前处理的多边形的边为SP，顶点S在上一轮处理过了。在情况1中，SP完全落在裁剪边的内侧(半空间之内)，将P输出到结果多边形顶点表中；在情况2中，P点在外侧不可见，而交点

i应输出；在情况3中，SP完全在外侧，没有输出；在情况4中，交点i和P点都是结果多边形的顶点，按顺序先输出i再输出P。从上面分析知道，裁剪结果多边形的顶点由两部分构成，一部分是落在裁剪边内侧的原多边形顶点，一部分是多边形的边与裁剪边的交点。只要将这两部分顶点按一定的顺序连接起来就得到了裁剪结果多边形1.Sutherland-Hodgman逐次裁剪算法

左下右上BOOLSHPolygonClip(int&k,CPoint*p,CRect

rect){ constint

maxVertics=100; //最大顶点数目

int

i;

CPoint

pb,pe;

intm=m_nVertics;

CPoint*a=newCPoint[maxVertics]; for(i=0;i<m;i++)a[i]=m_pHead[i]; //裁剪左边

pb.x=rect.left; pb.y=rect.top;

pe.x=rect.left; pe.y=rect.bottom; Clip(m,a,pb,pe); //裁剪下边

pb.x=rect.left; pb.y=rect.bottom;

pe.x=rect.right; pe.y=rect.bottom;

Clip(m,a,pb,pe);1.Sutherland-Hodgman逐次裁剪算法 //裁剪右边 pb.x=rect.right; pb.y=rect.bottom; pe.x=rect.right; pe.y=rect.top; Clip(m,a,pb,pe);

//裁剪上边 pb.x=rect.right; pb.y=rect.top; pe.x=rect.left; pe.y=rect.top; Clip(m,a,pb,pe); k=m; for(i=0;i<k;i++) p[i]=a[i]; delete[]a; returnTRUE;}1.Sutherland-Hodgman逐次裁剪算法//按边裁剪多边形，返回被某边裁剪后的结果多边形顶点数组VoidClip(int&m,CPoint*a,CPointpb,CPointpe){ constintmaxVertics=100; //最大顶点数目 inti,k; CPointp0; CPoints,p;//线段SP的起点与终点 CPoint*b=newCPoint[maxVertics];//存放结果临时顶点数组

k=0;//开始时，结果多边形的顶点数为0 s=a[m-1];//从多边形的第n个顶点开始1.Sutherland-Hodgman逐次裁剪算法for(i=0;i<m;i++){ p=a[i]; if(IsInsideRectangle(p,pb,pe)){//点p在边(pb,pe)的内侧 if(IsInsideRectangle(s,pb,pe))//情况1 Output(p,k,b); else{//情况4 p0=Intersect(s,p,pb,pe); Output(p0,k,b); Output(p,k,b); } } elseif(IsInsideRectangle(s,pb,pe)){//情况2 p0=Intersect(s,p,pb,pe); Output(p0,k,b); }//情况3没有输出 s=p;}m=k;for(i=0;i<m;i++) a[i]=b[i];delete[]b;}1.Sutherland-Hodgman逐次裁剪算法//判断点p位于裁剪边的内侧还是外侧intIsInsideRectangle(CPointp,CPointpb,CPointpe){ if(pe.x>pb.x){//裁剪边为窗口的下边 if(p.y>=pb.y)return1; } elseif(pe.x<pb.x){//裁剪边为窗口的上边 if(p.y<=pb.y)return1; } elseif(pe.y>pb.y){//裁减边为窗口的右边 if(p.x<=pb.x)return1; } elseif(pe.y<pb.y){//裁减边为窗口的左边 if(p.x>=pb.x)return1; } return0;}1.Sutherland-Hodgman逐次裁剪算法//将顶点p加入到多边形顶点序列中去voidOutput(CPointp,int&k,CPoint*a){ a[k].x=p.x; a[k].y=p.y; k++;}1.Sutherland-Hodgman逐次裁剪算法//求多边形的边SP与裁剪边(pb,pe)的交点CPointIntersect(CPoints,CPointp,CPointpb,CPointpe){ CPointp0; doublem; if(pb.y==pe.y){//水平裁剪边 p0.y=pb.y; m=(double)(p.x-s.x)/(double)(p.y-s.y); p0.x=s.x+(int)((pb.y-s.y)*m); } else{//竖直裁剪边 p0.x=pb.x; m=(double)(p.y-s.y)/(double)(p.x-s.x); p0.y=s.y+(int)((pb.x-s.x)*m); } returnp0;}1.Sutherland-Hodgman逐次裁剪算法用Sutherland-Hodgman算法对多边形裁剪有时会出现问题，比如上述算法就没有考虑裁剪成两个分离多边形的情况，而只是简单地将所有顶点连接，没有得到正确的分离的多边形。为了解决这个问题，在用窗口的一条边对多边形进行裁剪时要设置一个记录，把多边形的边和窗口的边相交的交点都记录下来，并对交点进行排序，把交点两两配对（交点的个数必为偶数）。如果只有两个交点，则多边形经裁剪后仍为一个多边形，如果有4个交点，则多边形经裁剪后成为两个多边形，以此类推2.Weiler-Athenton算法Sutherland－Hodgeman算法解决了裁剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法2.Weiler-Athenton算法在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的，凹的，甚至是带有内环的裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称：1、被裁剪多边形为主多边形，记为A；2、裁剪窗口为裁剪多边形，记为B。主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域：1、A∩B（交：属于A且属于B）；2、A－B（差：属于A不属于B）；3、B－A（差：属于B不属于A）；4、A∪B(并：属于A或属于B，取反；即：不属于A且不属于B)。2.Weiler-Athenton算法内裁剪即通常意义上的“裁剪”，取图元位于窗口之内的部分，结果为A∩B。外裁剪取图元位于窗口之外的部分，结果为A－B。观察右图不难发现裁剪结果区域的边界由被裁剪多边形的部分边界和裁剪窗口的部分边界两部分构成，并且在交点处边界发生交替，即由被裁剪多边形的边界转至裁剪窗口的边界，或者反之。由于多边形构成一个封闭的区域，所以，如果被裁剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类：一类称“入”点，即被裁剪多边形由此点进入裁剪窗口，如图中a、c、e；一类称“出”点，即被裁剪多边形由此点离开裁剪窗口，如图中b、d、f。2.Weiler-Athenton算法Weiler－Atherton任意多边形裁剪算法思想：算法从被裁剪多边形的一个入点开始，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点序列；而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。由于可能存在分裂的多边形，因此算法要考虑：将搜集过的入点的入点记号删去，以免重复跟踪。将所有的入点搜集完毕后算法结束。2.Weiler-Athenton算法1、顺时针输入被裁剪多边形顶点序列Ⅰ放入数组1中。2、顺时针输入裁剪窗口顶点序列Ⅱ放入数组2中。3、求出被裁剪多边形和裁剪窗口相交的所有交点，并给每个交点打上“入”、“出”标记。然后将交点按顺序插入序列Ⅰ得到新的顶点序列Ⅲ，并放入数组3中；同样也将交点按顺序插入序列Ⅱ得到新的顶点序列Ⅳ，放入数组4中；4、初始化输出数组Q，令数组Q为空。接着从数组3中寻找“入”点。如果“入”点没找到，程序结束。5、如果找到“入”点，则将“入”点放入S中暂存。6、将“入”点录入到输出数组Q中。并从数组3中将该“入”点的“入”点标记删去。7、沿数组3顺序取顶点：如果顶点不是“出点”，则将顶点录入到输出数组Q中，流程转第7步。否则，流程转第8步。8、沿数组4顺序取顶点：如果顶点不是“入点”，则将顶点录入到输出数组Q中，流程转第8步。否则，流程转第9步。9、如果顶点不等于起始点S，流程转第6步，继续跟踪数组3。否则，将数组Q输出；流程转第4步，寻找可能存在的分裂多边形。算法在第4步：满足“入”点没找到的条件时，算法结束。2.Weiler-Athenton算法2.Weiler-Athenton算法2.Weiler-Athenton算法2.Weiler-Athenton算法Weiler－Atherton任意多边形裁剪算法特点：裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。可实现被裁剪多边形相对裁剪窗口的内裁或外裁，即保留窗口内的图形或保留窗口外的图形，因此在三维消隐中可以用来处理物体表面间的相互遮挡关系。裁剪思想新颖，方法简洁，裁剪一次完成，与裁剪窗口的边数无关。3.6.4字符裁剪当字符或文本整个不在窗口时，则不予显示。然而，当字符和文本部分在窗口内，部分在窗口外时，就提出了字符裁剪的问题。字符精度：最简单的字符裁剪方法是把字符方框（即字符掩膜）与窗口比较。若整个方框位于窗口内，则显示对应字符，否则不予显示。象素精度：有些应用要求更准确的处理：即使字符只有一部分在窗口内，也要把这一部分显示出来。若字符为点阵型的，只要在把字符掩膜各位写入象素之前，先判断该位对应的象素是否在窗口内，若该位在窗口内则写，否则就不写。笔划精度：在字符为矢量型的情形，问题就更复杂一些。这时要对跨越窗口边界的笔划进行裁剪，裁去笔划伸到窗口外的部分，保留笔划在窗口内的部分，这个问题可以转化为线段的裁剪。3.7反走样基础在光栅显示器上显示图形时，直线段或图形边界或多或少会呈现锯齿状，原因是图形信号是连续的，而在光栅显示系统中，用来表示图形的却是一个个离散的像素。这种用离散的量来表示连续的量而引起的失真，叫做走样。用于减少或消除走样的技术，称为反走样。常见的走样现象有三种：阶梯走样、细节走样、遗失走样。所谓阶梯走样是在扫描转换线段时，线段呈现阶梯形状；所谓细节走样是指图形在用象素显示时会发生变大变小的现象；而遗失走样则是对于过小的图形，用象素现有的分辨率无法显示的现象。3.7反走样基础常用的反走样方法分为两类提高分辨率区域采样非加权区域采样加权区域采样3.7.1提高分辨率假设将显示器的水平和垂直分辨率都提高一倍，则同样长度的直线段穿过的扫描线条数增加了一倍，线段上的宽度减小了一倍。这样显示出的直线段看起来就平直光滑了一些，达到了减少走样的效果提高显示系统的分辨率可以减小走样的程度，方法也很简单，但付出的代价却非常大。假设要将光栅显示器系统的水平、垂直分辨率提高一倍，则显示器的点距要减小一倍，帧缓存的容量要增加到原来的4倍，显示卡和显示器之间的传输带宽度也要增加到原来的4倍，而扫描转换同样大小的图元却要花费4倍的时间3.7.2简单的区域反走样算法前面介绍的直线扫描转换算法做了两点假定：(1)像素是数学上抽象的点，它的亮度由覆盖该点的图形的亮度所决定；(2)直线段是数学上抽象的直线段，它的宽度为0。但实际上，象素不是一个点，而是一个个具有一定面积的小区域，该区域的形状依赖于光栅显示系统的硬件。直线段的宽度也不是0，在屏幕上显示的直线段的宽度至少为一象素。算法中所假定的条件和实际情况之间的差距是造成走样的原因之一，所以，为了减少走样，必须改变直线段模型。3.7.2简单的区域反走样算法非加权区域采样反混淆方法，归纳为如下几个步骤：(1)将直线段看作具有一定宽度的狭长矩形；(2)当直线段与象素有交时，求出两者相交区域的面积；(3)根据相交区域的面积，确定该象素的亮度值（在矩形内占的面积越大，颜色越深）3.7.2简单的区域反走样算法在非加权区域采用方法中，起关键作用的是直线段与象素相交区域的面积，如何计算这个面积呢？假设一条直线段的斜率为m，若规定它的显示宽度为一个象素，那么直线段与象素的相交情况有三种3.7.2简单的区域反走样算法

3.7.2简单的区域反走样算法有时为了简化上述计算，可以通过下面的离散计算方法求出相交区域的近似面积，用这个近似的面积替代真实的面积来确定像素的显示灰度。求相交区域的近似面积的离散计算方法：(1)将屏幕像素分割成n个更小的子像素；(2)计算中心点落在直线段内的子像素的个数，记为k；(3)k/n为线段与像素相交区域面积的近似值。这样做的目的是为了简化计算，例如： n=16,k=3