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

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

2、两个方面：一是图元在窗口区域内外的判别，二是图形元素与窗口的求交。 裁剪可以对扫描转换之后的点阵图形在设备坐标系中进行，也可以在世界坐标系中对扫描转换之前的参数表示的图形进行。前者算法简单，但效率不高，因为无论图形落在窗口的内部还是外部，都要扫描转换，它一般适用于求交难度较大的图形。而后者主要应用于点、线、多边形等简单图元。由于世界坐标系一般为浮点坐标系，故有时也称世界坐标系中的裁剪为分析裁剪，它是大多数图形系统所采用的裁剪方法窗口：由用户坐标系定义的一个矩形区域；视口：由设备坐标系定义的一个矩形区域；当把用户坐标系中的图形在图形设备上输出时，可以定义适当的窗口和视口，使窗口的图形在视口内显示

3、，处于窗口外或视口外的图形则不被显示即称被裁剪掉。固定视口而改变窗口，就可以在视口中观察到用户描述的全部图形了视口HVLV(XV1，YV1)窗口HW(XW1，YW1)LW窗口与视口的关系用户坐标系设备坐标系裁剪算法有二维的和三维的，裁剪对象可以是规则形体，也可以是不规则形体，其裁剪算法有二维的和三维的，裁剪对象可以是规则形体，也可以是不规则形体，其裁剪算法可以用硬件实现，也可以用软件实现。裁剪算法可以用硬件实现，也可以用软件实现。在进行裁剪时，画面中对应于屏幕显示的那部分区域也即窗口，把其定义为矩形，在进行裁剪时，画面中对应于屏幕显示的那部分区域也即窗口，把其定义为矩形，由上、下、左、右四条边

4、围成，即：由上、下、左、右四条边围成，即：( (x xL L，y yB B) )，(x(xR R，y yH H) )。裁剪的实质就是决定图形裁剪的实质就是决定图形中哪些点、线段、文字、以及多边形在裁剪窗口之内，中哪些点、线段、文字、以及多边形在裁剪窗口之内，在窗口内的图形被保留显示，而窗口之外的画面被裁去。如图所示。在窗口内的图形被保留显示，而窗口之外的画面被裁去。如图所示。对于点对于点( (x x，y)y)，只要判别两对不等式：只要判别两对不等式：x xL L x x x xR R，y yB B y y y yH H若四个不等式均成立，则点在窗口矩形之内；否则，点在窗口矩形之外。其中若四个不

5、等式均成立，则点在窗口矩形之内；否则，点在窗口矩形之外。其中, ,等号等号表示点位于窗口的边界上。表示点位于窗口的边界上。Cohen-Sutherland算法有时也称为编码算法，该算法分为三个步骤：第一步：判别线段两端是否都落在窗口内，如果是，则线段完全可见；否则进入第二步第二步：判别线段是否为显然不可见，即线段的两端点均落在窗口某边所在直线的外侧，如果是，则裁剪结束；否则进入第三步第三步：求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，舍弃。对余下的另一段重新进行第一步、第二步判断，直至结束。整个裁剪过程可以看作一个递归过程。为了实现这个算法，首先用窗口四条边所在的直

6、线将整个二维平面分成9个区域，如图3-36。每个区域赋予一个四位的编码CtCbCrCl，其中各位编码的含义如下：其他当01maxyyCt其他当01minyyCb其他当01maxxxCr其他当01minxxCl如图是各个区的编码的十进制数。判断线段的一个端点是否在窗口内部，只需判断它的编码值是否为0。注意到编码中各个位的含义，当两个端点的编码的逻辑“与”非0时，它们必然落在窗口某边的外侧，也即线段为显然不可见的线段端点编码实例线段端点编码实例两个端点“逻辑与”操作的语义是两个“端点都怎么样”对既非完全可见，又非显然不可见的线段，如图3-38中的AD，需要进行求交运算。求交前实现要测试线段和窗口哪

7、条边所在直线有交，这只要判断线段两端点编码中各位的值即可。如图中的AD，D点编码中的Cl=1，而A点编码中的Cl=0，则知道AD和窗口的左边所在直线有交。在程序中，求交测试的顺序是固定的。不妨假定求交测试的顺序为窗口的左边、上边、右边、下边。按照这个顺序，线段EJ和窗口四边被求出的交点顺序为F、I、H、G。从而在Cohen-Sutherland裁剪算法中，最坏的情况下，一条线段在裁剪时需要求交四次int LineClip(CPoint &posBeg, CPoint &posEnd, CRect rect)int accept,done;char c0,c1,code;int

8、x0,y0,x1,y1,x,y;double m;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);/返回线段终点的编码 while(!done) if(!c0 & !c1)/线段完全可见 posBeg.x=x0;posBeg.y=y0; posEnd.x=x1;posEnd.y=y1; accept=1; done=1; else if(c0&a

9、mp;c1)/线段完全不可见 posBeg.x=0;posBeg.y=0; posEnd.x=0;posEnd.y=0; accept=0; done=1; else/处理非完全可见又非显然不可见的情况 if(c0)/首点不可见。Code=首点 code=c0;（code指向不可见的那一方） else/首点可见，code=终点 code=c1; if(code&0 x01)/线段与窗口的左边有交 x=rect.left; m=(double)(y1-y0)/(double)(x1-x0); y=y0+(int)(x-x0)*m); else if(code&0 x08)/线段与

10、窗口的上边有交 y=rect.top; m=(double)(x1-x0)/(double)(y1-y0); x=x0+(int)(y-y0)*m); else if(code&0 x02)/线段与窗口的右边有交 x=rect.right; m=(double)(y1-y0)/(double)(x1-x0); y=y0+(int)(x-x0)*m); else if(code&0 x04)/线段与窗口的下边有交 y=rect.bottom; m=(double)(x1-x0)/(double)(y1-y0); x=x0+(int)(y-y0)*m); if(code=c0) x

11、0=x;y0=y; c0=GetCSCode(x0,y0,rect); else x1=x;y1=y; c1=GetCSCode(x1,y1,rect); return accept;Char GetCSCode(int x, int y, CRect rt)char code=0;if(xrt.right)/编码为*1*code=code|0 x02;else/编码为*0*code=code&0 xfd; if(yrt.top)/编码为1*code=code|0 x08; else/编码为0*code=code&0 xf7; return code;在图中的b线段，检查端点编

12、码可知它既不是完全可见段，也不是完全不可见段，则在中点Pm1处将b分为二段，两段的情况仍然相同。先不考虑P1Pm1，在Pm2处将Pm1P2分为二段从图中可见，Pm1Pm2完全可见，而Pm2P2部分可见。这样处理的结果将导致线段的可见部分被划分成一系列的可见小段然后再逐段画出，显然效率降低。求P1最远可见点的算法：1) 若P2在窗口内，则P2就是离P1最远的可见点，结束该算法，否则进行下一步;2) 若P1P2为完全不可见，则结束该算法， 否则进行下一步；3) 取P1P2中点Pm，若Pm点在窗口内部，则处理PmP2线段来寻找P1的最远可见点，即用Pm代替P1，执行2，否则P2用Pm代替，执行2。直

13、到Pm与线段端点的距离达到分辩率精度为止。在光栅显示系统中，常常需要显示输出具有连续色彩的图形区域，图形区域一般由多边形构成，这时就需要处理多边形区域的裁剪问题了。通常有一种错觉，认为只要把多边形的每条边用对直线段的裁剪方法裁剪后，就完成了对多边形的裁剪，其实不然。在图形学中，多边形定义了一个封闭的二维区域，裁剪结果也应该是一个封闭的多边形区域。多边形裁剪有其自身的特殊性，这种特殊性表现在：第一，多边形的边被裁剪后一般就不再封闭了，需要用窗口边界的适当部分来封闭它，如何确定这部分的边界？如图第二，一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？如图Sutherland-Ho

14、dgman多边形裁剪算法采用了分割处理的策略，将多边形关于矩形窗口的裁剪分割为多边形关于窗口四边所在直线的裁剪。所以该算法有时也称为逐边裁剪算法。多边形关于窗口四边的裁剪是相继进行的，不妨假定裁剪顺序为左边、上边、右边，下边，那么原多边形关于窗口左边的裁剪结果多边形作为关于上边裁剪的输入多边形，。裁剪过程是一个流水线过程，如图假设当前处理的多边形的边为SP，顶点S在上一轮处理过了。在情况1中，SP完全落在裁剪边的内侧(半空间之内)，将P输出到结果多边形顶点表中；在情况2中，P点在外侧不可见，而交点 i 应输出；在情况3中，SP完全在外侧，没有输出；在情况4中，交点i和P点都是结果多边形的顶点，

15、按顺序先输出i再输出P。从上面分析知道，裁剪结果多边形的顶点由两部分构成，一部分是落在裁剪边内侧的原多边形顶点，一部分是多边形的边与裁剪边的交点。只要将这两部分顶点按一定的顺序连接起来就得到了裁剪结果多边形BOOL SHPolygonClip(int &k, CPoint *p, CRect rect)const int maxVertics=100;/ 最大顶点数目int i;CPoint pb,pe;int m=m_nVertics;CPoint *a=new CPointmaxVertics;for(i=0;im;i+) ai=m_pHeadi;/裁剪左边pb.x=rect.le

16、ft;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); /裁剪右边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

17、;Clip(m,a,pb,pe);k=m;for(i=0;ik;i+)pi=ai;delete a;return TRUE;/按边裁剪多边形，返回被某边裁剪后的结果多边形顶点数组Void Clip(int &m, CPoint *a, CPoint pb, CPoint pe)const int maxVertics=100;/ 最大顶点数目int i,k;CPoint p0;CPoint s,p;/线段SP的起点与终点CPoint* b=new CPointmaxVertics;/存放结果临时顶点数组k=0;/开始时，结果多边形的顶点数为0s=am-1;/从多边形的第n个顶点开始 f

18、or(i=0;im;i+)p=ai;if(IsInsideRectangle(p,pb,pe)/点p在边(pb,pe)的内侧 if(IsInsideRectangle(s,pb,pe)/情况1Output(p,k,b); else/情况4p0=Intersect(s,p,pb,pe);Output(p0,k,b);Output(p,k,b); else if(IsInsideRectangle(s,pb,pe)/情况2 p0=Intersect(s,p,pb,pe); Output(p0,k,b);/情况3没有输出s=p; m=k; for(i=0;ipb.x)/裁剪边为窗口的下边if(p.y

19、=pb.y) return 1;else if(pe.xpb.x)/裁剪边为窗口的上边if(p.ypb.y)/裁减边为窗口的右边if(p.x=pb.x) return 1;else if(pe.y=pb.x) return 1;return 0;/将顶点p加入到多边形顶点序列中去void Output(CPoint p, int &k, CPoint *a)ak.x=p.x;ak.y=p.y;k+;/求多边形的边SP与裁剪边(pb,pe)的交点CPoint Intersect(CPoint s, CPoint p, CPoint pb, CPoint pe)CPoint p0;doub

20、le m;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);return p0;用Sutherland-Hodgman算法对多边形裁剪有时会出现问题，比如上述算法就没有考虑裁剪成两个分离多边形的情况，而只是简单地将所有顶点连接，没有得到正确的分离的多边形。为了解决这个问题，在用窗口的一条

21、边对多边形进行裁剪时要设置一个记录，把多边形的边和窗口的边相交的交点都记录下来，并对交点进行排序，把交点两两配对（交点的个数必为偶数）。如果只有两个交点，则多边形经裁剪后仍为一个多边形，如果有4个交点，则多边形经裁剪后成为两个多边形，以此类推SutherlandSutherlandHodgemanHodgeman算法解决了裁算法解决了裁剪窗口为凸多边形窗口的问题，但一些剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。边形窗口）的裁剪。Weiler-AthertonWeiler-Atherton多边形裁剪算法正是满足这种要求

22、的算多边形裁剪算法正是满足这种要求的算法法在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的，凹的在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的，凹的，甚至是带有内环的，甚至是带有内环的裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称：1、被裁剪多边形为主多边形，记为A；2、裁剪窗口为裁剪多边形，记为B。主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域：1、AB（交：属于A且属于B）；2、AB（差：属于A不属于B）；3、BA（差：属于B不属于A）；4、AB (并：属于A或属于B，取反；即：不属于A且不属于B)。 内裁剪即通常意义上的“裁剪”，取图元位于窗口之内的部分，

23、结果为AB。外裁剪取图元位于窗口之外的部分，结果为AB。观察右图不难发现裁剪结果区域的边界由和两部分构成，并且在交点处边界发生，即由被裁剪多边形的边界转至裁剪窗口的边界，或者反之。由于多边形构成一个封闭的区域，所以，如果被裁剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类：一类称“”点，即被裁剪多边形由此点进入裁剪窗口，如图中a、c、e；一类称“”点，即被裁剪多边形由此点离开裁剪窗口，如图中b、d、f。WeilerWeilerAthertonAtherton任意多边形裁剪算任意多边形裁剪算法思想：法思想：算法从被裁剪多边形的一个入点开始算法从被裁剪多边形的一个入点开始，碰到入点，沿着

24、被裁剪多边形按顺时针，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点序列；方向搜集顶点序列；而当遇到出点时，则沿着裁剪窗口按而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。顺时针方向搜集顶点序列。由于可能存在分裂的多边形，因此算由于可能存在分裂的多边形，因此算法要考虑：将搜集过的入点的入点记号删法要考虑：将搜集过的入点的入点记号删去，以免重复跟踪。将所有的入点搜集完去，以免重复跟踪。将所有的入点搜集完毕后算法结束。毕后算法结束。1、顺时针输入被裁剪多边形顶点序列放入数组1中。2、顺时针输入裁剪窗口顶点序列放入数组2中。3、求出被裁剪多边形和裁剪窗口相交的所有交点，并给每个交点打上“入”

25、、“出”标记。然后将交点按顺序插入序列得到新的顶点序列，并放入数组3中；同样也将交点按顺序插入序列得到新的顶点序列，放入数组4中；4、初始化输出数组Q，令数组Q为空。接着从数组3中寻找“入”点。如果“入”点没找到，程序结束。5、如果找到“入”点，则将“入”点放入S中暂存。6、将“入”点录入到输出数组Q中。并从数组3中将该“入”点的“入”点标记删去。7、沿数组3顺序取顶点：如果顶点不是“出点”，则将顶点录入到输出数组Q中，流程转第7步。否则，流程转第8步。8、沿数组4顺序取顶点：如果顶点不是“入点”，则将顶点录入到输出数组Q中，流程转第8步。否则，流程转第9步。9、如果顶点不等于起始点S，流程转

26、第6步，继续跟踪数组3。否则，将数组Q输出；流程转第4步，寻找可能存在的分裂多边形。算法在第4步：满足“入”点没找到的条件时，算法结束。WeilerAtherton任意多边形裁剪算法特点：1. 裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。2. 可实现被裁剪多边形相对裁剪窗口的内裁或外裁，即保留窗口内的图形或保留窗口外的图形，因此在三维消隐中可以用来处理物体表面间的相互遮挡关系。3. 裁剪思想新颖，方法简洁，裁剪一次完成，与裁剪窗口的边数无关。当字符或文本整个不在窗口时，则不予显示。然而，当字符和文本部分在窗口内，部分在窗口外时，就提出了字符裁剪的问题。最简单的字符裁剪方法是把字符方框（即字

27、符掩膜）与窗口比较。若整个方框位于窗口内，则显示对应字符，否则不予显示。有些应用要求更准确的处理：即使字符只有一部分在窗口内，也要把这一部分显示出来。若字符为点阵型的，只要在把字符掩膜各位写入象素之前，先判断该位对应的象素是否在窗口内，若该位在窗口内则写，否则就不写。在字符为矢量型的情形，问题就更复杂一些。这时要对跨越窗口边界的笔划进行裁剪，裁去笔划伸到窗口外的部分，保留笔划在窗口内的部分，这个问题可以转化为线段的裁剪。在光栅显示器上显示图形时，直线段或图形边界或多或少会呈现锯齿状，原因是图形信号是连续的，而在光栅显示系统中，用来表示图形的却是一个个离散的像素。这种用离散的量来表示连续的量而引

28、起的失真，叫做走样。用于减少或消除走样的技术，称为反走样。常见的走样现象有三种：阶梯走样、细节走样、遗失走样。所谓阶梯走样是在扫描转换线段时，线段呈现阶梯形状；所谓细节走样是指图形在用象素显示时会发生变大变小的现象；而遗失走样则是对于过小的图形，用象素现有的分辨率无法显示的现象。常用的反走样方法分为两类 提高分辨率 区域采样 非加权区域采样 加权区域采样假设将显示器的水平和垂直分辨率都提高一倍，则同样长度的直线段穿过的扫描线条数增加了一倍，线段上的宽度减小了一倍。这样显示出的直线段看起来就平直光滑了一些，达到了减少走样的效果提高显示系统的分辨率可以减小走样的程度，方法也很简单，但付出的代价却非

29、常大。假设要将光栅显示器系统的水平、垂直分辨率提高一倍，则显示器的点距要减小一倍，帧缓存的容量要增加到原来的4倍，显示卡和显示器之间的传输带宽度也要增加到原来的4倍，而扫描转换同样大小的图元却要花费4倍的时间前面介绍的直线扫描转换算法做了两点假定： (1) 像素是数学上抽象的点，它的亮度由覆盖该点的图形的亮度所决定； (2) 直线段是数学上抽象的直线段，它的宽度为0。但实际上，象素不是一个点，而是一个个具有一定面积的小区域，该区域的形状依赖于光栅显示系统的硬件。直线段的宽度也不是0，在屏幕上显示的直线段的宽度至少为一象素。算法中所假定的条件和实际情况之间的差距是造成走样的原因之一，所以，为了减

30、少走样，必须改变直线段模型。非加权区域采样反混淆方法，归纳为如下几个步骤： (1) 将直线段看作具有一定宽度的狭长矩形； (2) 当直线段与象素有交时，求出两者相交区域的面积； (3) 根据相交区域的面积，确定该象素的亮度值（在矩形内占的面积越大，颜色越深）在非加权区域采用方法中，起关键作用的是直线段与象素相交区域的面积，如何计算这个面积呢？假设一条直线段的斜率为m，若规定它的显示宽度为一个象素，那么直线段与象素的相交情况有三种有时为了简化上述计算，可以通过下面的离散计算方法求出相交区域的近似面积，用这个近似的面积替代真实的面积来确定像素的显示灰度。求相交区域的近似面积的离散计算方法：(1)

31、将屏幕像素分割成n个更小的子像素；(2) 计算中心点落在直线段内的子像素的个数，记为k；(3) k/n为线段与像素相交区域面积的近似值。这样做的目的是为了简化计算，例如： n = 16, k = 3 近似面积 = 3/16为了实现反走样，可对图为了实现反走样，可对图形信号作含核的卷积，卷形信号作含核的卷积，卷积积分为：积积分为：c( )= h( x)y(x)dx其中其中h( x)是函数的卷积是函数的卷积核，核，y(x)是被卷积的函数是被卷积的函数，c( )是是h( x)和和y(x)的卷的卷积。积。- 例如卷积核如图所示。例如卷积核如图所示。然后将这一卷积核然后将这一卷积核h(x)，反射核反射核h(x)及平移核及平移核h( x)与卷积函与卷积函数数y=x相乘得结果如图。相乘得结果如图。卷积核、反射核及平移核的表卷积核、反射核及平移核的表达式为：达式为：h(x)y(x) 0,2-0.50.5-1211故有故有 c( )= h( x)y(x)dx0 1 = h( x)y(x)dx = h( x)y(x)dx1 2代入：代入：h( x)1 ，y(x)=x有有 c( )= (1) (x)dx= 2/2 0 1 = xdx = /2 (2 ) 1 2若若y(x)的斜率为的斜率为m，则结果为则结果为m 2/2及及m /2 (2 )