《二维裁剪课件》由会员分享，可在线阅读，更多相关《二维裁剪课件（74页珍藏版）》请在金锄头文库上搜索。
1、第6章 二维裁剪,在许多应用问题中，面对一张大的画面，或者是由于实际需要，或者是显示屏幕有限，常要求开一个矩形区域指定要显示的部分画面，这种用来指定图形显示内容的矩形区域称为裁剪窗口。 窗口内的图形被显示出来了，而窗口之外的图形则被裁剪掉。从图形的显示过程知道，任何图形在显示之前都要经过裁剪工作。因此图形的裁剪和图形的变换一样，直接影响图形系统的效率。裁剪的方法很多，效率的高低常与计算机图形硬件水平及图形复杂程度有关，要根据实际情况来选择合适的裁剪算法。 裁剪的基本目的是判断这个图形元素是否落在窗口区域之内，如落在区域之内则进一步求出位于区域内的部分。因此裁剪处理的基础有两个方面：一是图元在窗
2、口区域内外的判别，二是图形元素与窗口的求交。,裁剪可以对扫：描转换之后的点阵图形在设备坐标系中进行，也可以在世界坐标系中对扫描转换之前的参数表示的图形进行。 前者算法简单，但效率不高，因为无论图形落在窗口的内部还是外部，都要扫描转换，它一般适用于求交难度较大的图形。而后者主要应用于点、线、多边形等简单图元。由于世界坐标系一般为浮点坐标系，故有时也称世界坐标系中的裁剪为分析裁剪，它是大多数图形系统所采用的裁剪方法。 本章主要介绍三种简单字二维图元即直线段、多边形、符裁剪的基本方法。,61 直线段裁剪,直线段裁剪算法相对来说比较简单，但它非常重要，是复杂图元裁剪的基础；因为在大多数图形系统中，复杂
3、的高次曲线都是用折线段来近似逼近的，从而其裁剪问题也可以化为直线段的裁剪问题。 本节中，我们假定裁剪窗口为矩形窗口，其左、右、上、下各边分别为x=xmin,xxmax，yymax，y=ymin，待裁剪的线段为P0(x0,y0)P1(x1,y1),在讨论具体的算法时不再重述。 待裁剪线段和窗口的关系有如下三种： (1)线段完全可见，即P0和P1均在窗口内，如图61中的AB，这时接受(显示)该线段。 (2)显然不可见，即和都落在窗口某条边所在直线的外侧。如图61中的EF，这时拒绝该线段。,(3)线段至少有一端点在 窗口之外，但非显然不可见。 如图61中的CD，GH，IJ， 此时需进一步求交以确定线
4、 段是否有可见部分并求出可 见部分。 为了提高裁剪效率，算法设计一般可从下面两方面做出考虑： 一是快速判别情况1和2； 二是在情况3中，设法减少求交的次数和每次求交时所需的计算量。,611 点裁剪 在讨论线段裁剪之前，先看看简单的点裁剪问题，它是线段裁剪以及后面的多边形裁的基础。如果矩形裁剪窗口的左、右边的横坐标和上、下边的纵坐标如前文所述，那么点 (x，y)在窗口内的充分必要条件是： xminxxmax，yminyymax 如果上面四个不等式中任何一个不满足，则(x，y)点位于窗口之外。 对于任意多边形窗口，需要根据第4章提到的点在多边形区域内外的判别方法进行判别。,612 直接求交算法 裁
5、剪一条直线段，只需考虑它的两个端点关于矩形窗口的关系就可以了。 如果两个端点都在窗口内部(如图61中的AB)，那么线段完全可见。 如果一个端点在窗口内，一个端点在窗口外：(如图6.1中的CD)，则线段与窗口的边有一个交点，交点与窗口内的端点间的连线即为该线段的可见部分。 如果两端点都在窗口外部，则线段与窗口可能不相交(如图61中的EF，IJ)，也有可能相交(如图61中的GH)，需要进一步计算以确定它们是否相交。 根据以上分析，一个裁剪线段的简单方法的框图如图62所示(当待裁剪线段平行于窗口的边时，情况很简单，这里假定它们不平行于窗口的边。),为了求直线段与窗口的边的交点，我们将线段写成参数形式
6、。例如 的参数方程为： 矩阵窗口下边的参数方程为： 和窗口下边的交点满足方程组： 求解方程组得到交点所对应的参数对 ，只有当 0，1且 0，1时， 所对应的交点才 是有效交点，即真正落在PoP1和窗口边上而不是它们的延长线上。,613 CohenSutherland算法 CohenSutherland裁剪算法有时也称为编码算法。该算法分为三个步骤： 第一步判别线段两端是否都落在窗口内，如果是，则线段完全可见；否则进入第二步，判别线段是否为显然不可见，即线段的两端点均落在窗口某边所在直线的外侧，如果是，则裁剪结束；否则进行第三步，求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不
7、可见，丢弃。对余下的另一段重新进行第一步、第二步判断，直至结束。整个裁剪的过程可以看作一个递归的过程。 为了实现这个算法，首先用窗口四条边所在的直线(见图63)将整个二维平面分成9个区域，每个区域赋予一个四位的编码 ，其中各位编码的含义如下：,然后确定线段的两个端点的编码，端点的编码即为它所在区域的编码。这样判断端点是否在窗口内部，只需判断它的编码值是否为0。注意到编码中各个位的含义，当两个端点的编码的逻辑“与”非0时，它们必然均落在窗口某边的外侧，亦即线段为显然不可见的。例如图61中的线段EF和IJ，E和F的编码分别是0001和1001，它们的与为0001，不为0，从而EF显然不可见。I和J
8、的编码分别是0100和0010，它们的与为0，从而IJ不是显然不可见的。 对既非完全可见、又非显然不可见的线段，如图64中的AD，需要求交。求交前先要测试线段和窗口哪条边所在直线有交，这只要判断线段两端点编码中各位的值即可。如图64中的AD，D点编码中的 而A点编码中的 ，则知道AD和窗口的左边所在的直线有交。在程序中，求交测试的顺序是固定的。不妨假定求交测试的顺序为窗口的左边、上边、右边、下边。按照这个顺序，图64中线段EF和窗口,四边被求出的交点顺序为F，I，H，G。从而在CohenSutherland裁剪算法中，最坏的情况下，一条线段在裁剪时需要求交4次 。,程序61给出了CohenSu
9、therland裁剪算法，其中设计了一个数据结构：Outcode用来记录端点的编码。Outeode中的all元素用来判断是否该端点的编码中4位全是0。算法的运行过程是这样的：先用函数CompOutcode计算线段两端点的编码,然后按如上方法判断线段是否为完全可见或显然不可见，如果不是，则确定位于窗口之外的端点，并根据该端点的编码值确定它位于窗口哪条边的外侧，求出线段和该边的交点。以交点为分界，将位于该边外侧的部分线段丢弃，以交点为新的端点，计算其编码重复上述过程。 例如，图64中的线段AD，A点的编码为0000，D点的编码为1001，AD既非完全可见亦非显然不可见。于是程序中确定出D点为落于窗
10、口之外的点，它的编码值表明它在窗口左边和上边的外侧。但根据我们假定的测试顺序，AD先与左边求交，交点为：C，CD段为显然不可见部分，丢弃。以C点为新的端点，计算其编码为1000。以AC代替AD重复上面过程，求出AC与上边的交点B，AB即为AD的可见部分。程序运行结束。,程序6.1 ChoenSutherland线段裁剪算法 typedefstruct unsigned all； unsigned left，right，top，bottom； OutCode； void COhenSutherlandLineClip(float x0,float y0，float xl， flout y1，Re
11、ctangle *rect) * P0(x0，y0)P1(x1，y1)为待裁剪线段* * rect为裁剪窗口* void CompOutCode(float，float，Rectangle*，OutCode*)； *用于计算端点的编码* boolean accept，done；,OutCOde outCOde0，outCOdel; OutCOde *outCOdeOut； float x，y； acceptFALSE； doneFALSE; CompOutCode(x0，y0，rect， else if(yymin), outCode一bottom=1； outCddeall+1； outCo
12、de一rightoutCodeleft=0； if(x(float)rect一xmax) outCoderight1； outCode一all+1： ,else if(xxmin) outCode一left=1； outCodeall+=1; *end of CompOutCode( )*,614 NichollLeeNicholl算法 NichollLeeNicholl裁剪方法的基本想法是通过对二维平面的更详细划分，消除CohenSutherland算法中线段在被裁剪时需多次求交的情况。这种改进使得NichollLeeNicholl算法的效率在某些场合更优于CohenSutherland算法
13、。 假定待裁剪线段P0P1为非完全可见且非显然不可见的，矩形裁剪窗口如前文所述，记其四个角点分别为PLT，PTR，PRB和PBL，则NichollLeeNicholl算法可分为以下几个步骤。 第一步，窗口四边所在的直线将二维平面划分成9个区域，对区域编号如图65所示，确定P0所在的区域。不失一般性，我们只考虑P0落在区域0，4，5的情况如图66所示。如果P0落在其它区域，总可以先通过简单的二维变换(如旋转变换、对称变换等)使之落于这三个区域内当裁剪结束后，再通过逆变换将裁剪结果变换回去。,第二步，从P0点向窗口的四个角点发出射线，这四条射线和窗口的四条边所在的直线一起将二维平面划分为更多的小区
14、域。 当P0落在区域0时，平面被划分成4个有意义的区域L，T，R，B，如图67(a)所示。此时P1的位置(属于哪个区域)决定了PoP1和窗口边的相交关系。例如，若P1属于区域L，则PoP1只和窗口的左边相交，以此类推。 当P0落在区域5时，平面被划分为4个有意义的区域：L，LT，LR，LB，如图67(b)所示。此时，若P1属于区,域LT，则PoP1只和窗口的左边、上边相交，其它类似。若P1不属于L，LT，LR，LB中的任何一个，则表示PoP1完全不可见。 当P0落在区域4时，又分为两种情况，如图67(c)，(d)。在(c)中，P0点落于窗口对角线的下部，此时，平面被划分为5个有意义的区域L，T
15、，TR，LR，LB。当P1属于区域TR时，PoPl和窗口上边、右边相交，其余类同。在(d)中，P0点落于,窗口对角线的上部，此时，平面被划分为L，T，TR，TB，LB 5个区域，PoP1与窗口边的相交关系与(c)的情况类同。 第三步，确定P1所在区域。根据窗口四边的坐标值以及PoP1和各射线的斜率可确定P1所在的区域。例如在图67(a)中，P1属于区域R的充要条件为,其中slope( )指的是该线段的斜率。 第四步，求交点，确定PoP1的可见部分。 优缺点： NichollLeeNicholl算法是直线段裁剪算法中效率较高的一个，但由于它较多地利用二维空间及矩形窗口的具体特点，所以该算法不易推
16、广到三维裁剪或裁剪窗口为任意多边形的情况。 615 中点分割算法 中点分割算法可分为两个平行的过程，即从P0点出发找出距P0最近的可见点，如图68中的A点，和从P1点出发找出距P1最近的可见点，如图6.8中的B点。这两个最近可见点,之间的连线AB即为原线段PoP1的可见部分。假设有一质点从P0出发向P1方向运动，则该点从A点进入窗口区域，从B点离开窗口区域。,从P0(P1)出发找最近可见点的办法是采用中点分割方法。先求出P0P1的中点Pm,若PoPm不是显然不可见的,并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；否则,取PmP1代替P0P1，再对新的P0Pl求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常
