图形裁剪算法.doc

图形裁剪算法研究本文由天空乐园郑州大学生兼职网整理分享 摘要 在用户坐标系中定义的图形往往是大而复杂的，而输出设备如显示屏幕的尺寸及其分辨率却是有限的，为了能够清晰地观察某一部分或对其进行某些绘图操作，就需要将所关心的这一局部区域的图形从整个图形中区分出来,这个区分指定区域内和区域外的图形过程称为裁剪，所指定的区域称为裁剪窗口。 裁剪通常是对用户坐标系中窗口边界进行裁剪，然后把窗口内的部分映射到视区中，也可以首先将用户坐标系的图形映射到设备坐标系或规范化设备坐标系中，然后用视区边界裁剪。关键词：矢量裁剪 多边形裁剪 圆裁剪 双边裁剪法 线段裁剪 字符裁剪 引言 在人机交互编辑时，作业员往往要把某一区域放大到整个屏幕显示区，这要靠开窗裁剪来实现。另外，地图的输出往往是分幅输出的，这也要靠开窗裁剪来实现。裁剪是用于描述某一图形要素（如直线、圆等）是否与一多边形窗口（如矩形窗口）相交的过程，其主要用途是确定某些图形要素是否全部位于窗口之内，若只有部分在窗口内又如何裁剪去窗口外的图形，从而只显示窗口内的内容。对于一个完整的图形要素，开窗口时可能使得其一部分在窗口之内，一部分位于窗口外，为了显示窗口内的内容，就需要用裁剪的方法对图形要素进行剪取处理。裁剪时开取的窗口可以为任意多边形，但在实践工作中大多是开一个矩形窗口。1窗口区和视图区1.1坐标系 1.用户坐标系(World Coordinates) 又称为世界坐标系、完全坐标系等，它可以是用户用来定义设计对象的 各种标准坐标系，例直角坐标、极坐标、球坐标、对数坐标等。用户坐标系所拥有的区域范围从理论上说是连续的、无限的。 2.观察坐标系(Viewing Coordinates)在用户坐标中设置观察坐标系，在观察坐标系中定义一个观察窗口。观察坐标系用来任意设置矩形窗口的方向。一旦建立了观察参考系，就可以将用户坐标系下的描述变换到观察坐标系下。由于窗口和视图是在不同坐标系中定义的，因此，在把窗口中图形信息转换到视图区之前，必须进行坐标变换，即把用户坐标系的坐标值转化为设备坐标系的坐标值。图形输出时需要一定的设备，如绘图仪、显示器等，使用的是设备坐标系。设备坐标系一般为二维坐标，如屏幕坐标。它的范围有限，单位一般为整数。设备坐标一般采用无量刚方式，可以转换为有量刚坐标。一旦场景变换到规范化坐标系下的单位正方形中，以后该单位面积只需要简单地映射到具体输出设备的显示区。给出合适的设备驱动程序，就可以使用不同的输出设备。用户可以在用户坐标系中指定感兴趣的任意区域，把这部分区域内的图形输出到屏幕上，这个指定区域称为窗口区。窗口区一般是矩形区域，可以用左下角和右上角两点坐标来定义其大小和位置。图1 用户坐标系 3.规范化设备坐标系(Normalized Device Coordinates)在规范化坐标系下（取值范围从0到1）定义视区，将观察坐标系下的场景描述映射到规范坐标系下。图2 规范化设备坐标系 4.设备坐标系(Device Coordinates)图形输出时需要一定的设备，如绘图仪、显示器等，使用的是设备坐标系。设备坐标系一般为二维坐标，如屏幕坐标。它的范围有限，单位一般为整数。设备坐标一般采用无量刚方式，可以转换为有量刚坐标。一旦场景变换到规范化坐标系下的单位正方形中，以后该单位面积只需要简单地映射到具体输出设备的显示区。给出合适的设备驱动程序，就可以使用不同的输出设备。1.2窗口区和视图区用户可以在用户坐标系中指定感兴趣的任意区域，把这部分区域内的图形输出到屏幕上，这个指定区域称为窗口区。窗口区一般是矩形区域，可以用左下角和右上角两点坐标来定义其大小和位置。定义窗口的目的是要选取图形中需要观察的那一部分图形。在计算机图形学术语中，窗口最初是指要观察的图形区域，但是目前窗口也用于窗口管理系统。在本章中，我们将窗口理解为用户坐标系中要显示的区域。图形设备上用来输出图形的最大区域称之为屏幕域，它是有限的整数域，大小随具体设备而异。任何小于或等于屏幕域的区域都可定义为视图区。视图区由用户在屏幕域中用设备坐标定义，一般也定义成矩形，由其左下角和右上角两点坐标来定义。所以，用户可以利用窗口来选择需要观察那一部分图形，而利用视图区来指定这一部分图形在屏幕上显示的位置。标准的窗口区和视图区一般都是矩形，其各边分别与坐标轴平行。用户定义的图形从窗口区到视图区的输出过程如下：从应用程序得到图形的用户坐标(WC-World Coordinates)对窗口区进行裁剪(WC)窗口区到视图区的规格化变换(NDC-Normalized Device Coordinate)视图区从规格化设备系到设备坐标系的变换(DC-Device Coordinate)在图形设备上输出图形。下图是从用户坐标系取图形在设备坐标系下显示的示意图：图3 用户坐标系1.3窗口区和视图区之间的坐标变换 由于窗口和视图是在不同坐标系中定义的，因此，在把窗口中图形信息转换到视图区之前，必须进行坐标变换，即把用户坐标系的坐标值转化为设备坐标系的坐标值。 设在用户坐标系下，矩形窗口左下角点坐标为(Wxl,Wyb), 右上角点坐标为(Wxr,Wyt)。屏幕中视图区的两个角点在设备坐标系下分别为(Vxl,Vyb)和(Vxr,Vyt)。则在窗口中的点(xw,yw)对应视图区中的点（xv, yv)，其变换公式为：下图为示图： （1） 图4记: （2） （3） （4） （5）公式可以化简为： （6）写成矩阵形式为： （7）上述变换是二维变换中比例变换和平移变换的组合变换。通过变换，可以实现将用户坐标系中窗口区中任意一点转换成设备坐标系中视图区中一点，从而可以把实际图形转换到具体输出设备的显示区。2线段的裁剪 2.1线段的矢量裁剪1 在裁剪时不同的线段可能被窗口分成几段，但其中只有一段位于窗口内可见，线段的裁剪算法就是要找出位于窗口内部的起始点和终止点的坐标。因矢量裁剪法对寻找起点和终点坐标的处理方法相同，下面以求始点坐标为例来说明线段矢量裁剪方法。 在图5中，窗口的四条边界把XOY平面分成九个区域，分别用到对这九个窗口编号，设号区域为相应的可见窗口区，窗口的左下角点坐标（minX,minY），右上角点坐标为（maxX,maxY）。有一条矢量线段S，其起、终点的坐标分别为（Xs,Ys）和（Xe,Ye），则对线段S按矢量裁剪的算法步骤如下： 、图51.若线段完全位于区域以外的任意区域内或落在（，）、（，）、（，）、（，）中任意一区域组内，即满足下述条件之一： XsminX且XeminX且XeminX, YsminY且YeminY且YeminY, （8）则线段不在窗口内，不必作进一步的求交点处理，否则转下一步。2.若线段满足minXXsmaxX且minXYsmaxY ,则线段的起点在窗口内，新的起点坐标(,)即为（Xs,Ys）；否则，按以下各步判断与窗口的关系以及解算其新起点坐标(,)。3.若XsminY或YmaxY ，则线段S与窗口无交点； (3) 若YmaxY且TsmaxY或者YminY且YsmaxY或当起点在区且Ye (b)若YsmaxY，则： (11) 用（10）和（11）式求出的X若满足minXXmaxX，则（X,Y）的求解有效，否则线段与窗口仍无交点。4.当XsmaxX ，即线段起点位于窗口右界的右边，可仿照上述过程求出线段与右边界的交点。5.若起点（Xs,Ys）位于或区时，求解线段与窗口边界的交点公式为（12）和（13）式。 (12) (13)用式（12）和（13）求解得在满足minXXmaxX时才有效，否则线段不在窗口内。 同理，可求解出线段在窗口内新的终点坐标。2.2线段的编码裁剪法10 这种方法和上面介绍的方法相似，所不同的是这种方法把被窗口的边界分成的九个区按一定的规则用四位二进制编码来表示。这样，当线段的端点位于某一区时，该点的位置可以用其所在区域的四位二进制码来唯一确定，通过对线段两端点的编码进行逻辑运算，就可确定线段相对于窗口的关系。 如图6，编码顺序从右到左，每一编码对应线段端点的位置为：第一位为表示端点位于窗口左边界的左边；第二位为表示端点位于右边界的右边；第三位为表示端点位于下边界的下边；第四位为表示端点位于边界的上边。若某位为则表示端点的位置情况与取值时相反。很显然，如果线段的两个端点的四位编码全为，则此线段全部位于窗口内；若线段两个端点的四位编码进行逻辑乘运算的结果为非，则此线段全部在窗口外。对这两种情况无须作裁剪处理。图6 如果一条线段用上述方法无法确定是否全部在窗口内或全部在窗口外，则需要对线段进行裁剪分割，对分割后的每一子线段重复以上编码判断，把不在窗口内的子线段裁剪掉，直到找到位于窗口内的线段为止。 如图中的线段AB，第一次分割成了线段AC和CB，利用编码判断可把线段AC裁剪掉，对线段CB再分割成子线段CD和DB，再利用编码判断又裁剪掉子线段CD，而DB全部位于窗口内，即为裁剪后的线段，裁剪过程结束。直线与窗口边框的交点为：上边框交点： （14） 下边框交点： （15）左边框交点： （16） 右边框交点： （17） 式中（XA,YA）和（XB,YB）分别为线段端点和的坐标，YT为上边框的坐标，YU为下边框的坐标，XL为左边框的坐标，XR为右边框的坐标。2.3线段中点分割裁剪法又称对分法，其算法思想是：当一条线段既不能直接接受也不能直接舍弃，要求其与区域的交点时，预先假设此交点落在线段的中点，如果这估计是错误的，则将直线分为两段，并对线段分别加以测试。用这种方法一直进行下去，直到原来线段的一段被直接接受，而另一段被直接舍弃。中点分割法判断是否与区域有交，仍可采用前面介绍的编码方法，只是在不得不求其与区域交点时，不断用对分法求其中点，以增加循环为代价，避免求交运算。2.4线段的Cohen-Sutherland裁剪算法 该算法的思想是：对于每条线段P1P2分为三种情况处理。 （1）若两端点P1P2完全在窗口内，则完全可见该线段P1P2。否则进入下一步； （2）若线段P1P2明显在窗口外，即显然不可见，则丢弃该线段，否则进入下一步； （3）若线段既不满足（1）的条件，也不满足（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 3多边形的裁剪211 多边形是计算机制图中常用的图形元素，大到行政区域，小到各种地物图块，都是多边形元素。 多边形的裁剪比直线要复杂得多。因为经过裁剪后，多边形的轮廓线仍要闭合，而裁剪后的边数可能增加，也可能减少，或者被裁剪成几个多边形，这样必须适当地插入窗口边界才能保持多边形的封闭性。这就使得多边形的裁剪不能简单地用裁剪直线的方法来实现。 对于多边形的裁剪，人们研究出了多种算法，其中萨瑟兰德霍奇曼（Sutherland-Hodgman）算法根据相对于一条边界线裁剪多边形比较容易这一点，把整个多边形先相对于窗口的第一条边界裁剪，然后再把形成的新多边形相对于窗口的第二条裁剪，如此进行到窗口的最后一条边界，从而把多边形相对于窗口的全部边界进行了裁剪。 其算法描述为： 取多边形顶点Pi(i=1,2,n) ,将其相对于窗口的第一条边界进行判别，若点Pi位于边界的靠窗口一侧，则把Pi记录到要输出的多边形顶点中，否则不作记录。检查Pi点与Pi-1点（i=1时，检查Pi与Pn点）是否位于窗口边界的同一侧。若是，Pi点记录与否，随Pi-1点是否记录而定；否则计算出PiPi-1与窗口边界的交点，并将它记录到要输出的多边形的顶点中去。如此而已判别所有的顶点P1P2Pn后,得到一个新的多边形Q11,Q12,Qm,然后用新的多边形重复上述步骤1、，依次对窗口的第二、第三和第四条边界进行判别，判别完后得到的多边形Q14,Q24,Qm4即为裁剪的最后结果。 对于多边形的裁剪，人们研究出了多种算法，其中SutherlandHodgeman算法解决了裁剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法。在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于180度）、甚至是带有内环的（子区）。裁剪窗口和被裁剪多边形处于完全对等的地位，则称：被裁剪多边形为主多边形，记为A；裁剪窗口为裁剪多边形，记为B。主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域：1、AB（交：属于A且属于B）；2、AB（差：属于A不属于B）；3、BA（差：属于B不属于A）；4、AB(并：属于A或属于B，取反；即：不属于A且不属于B)。内裁剪即通常意义上的裁剪，取图元位于窗口之内的部分，结果为AB。外裁剪取图元位于窗口之外的部分，结果为AB。观察图3不难发现裁剪结果区域的边界由被裁剪多边形的部分边界和裁剪窗口的部分边界两部分构成，并且在交点处边界发生交替，即由被裁剪多边形的边界转至裁剪窗口的边界，或者反之。由于多边形构成一个封闭的区域，所以，如果被裁剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类：一类称“入”点，即被裁剪多边形由此点进入裁剪窗口，如图7中a、c、e；一类称“出”点，即被裁剪多边形；对于多边形的裁剪，人们研究出了多种算法，其中WeilerAtherton任意多边形裁剪算法思想是：假设被裁剪多边形和裁剪窗口的顶点序列都按顺时针方向排列。当两个多边形相交时，交点必然成对出现，其中一个是从被裁剪多边形进入裁剪窗口的交点，称为“入点”，另一个是从被裁剪多边形离开裁剪窗口的交点，称为“出点”。 图7算法从被裁剪多边形的一个入点开始，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点序列；而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。由于可能存在分裂的多边形，因此算法要考虑：将搜集过的入点的入点记号删去，以免重复跟踪。将所有的入点搜集完毕后算法结束。WeilerAtherton任意多边形裁剪算法步骤： 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步：满足“入”点没找到的条件时，算法结束。4圆的裁剪5 对圆的裁剪思路是，首先通过圆的外接矩形判断来确定圆是否全部位于窗口的外边，若全部位于窗口外边，则裁剪过程结束。否则，将圆分解成一组短线段，然后按照直线裁剪的方法来进行。 由于曲线在实际绘制时是采用短直线来逼近曲线的方法实现，故曲线的裁剪也采用一般直线裁剪方法对每一短线段进行裁剪，从而实现对整个曲线的裁剪。 5双边裁剪法9 此算法是由Weiler和Atherton提出来的。算法的基本做法是：有时沿着多边形边的方向来处理顶点，有时沿着窗口的边界方向来处理，从而避免产生多余的连线。设被裁剪多边形和裁剪窗口都按顺时针确定排列方向，因此，沿多边形的一条边前进，其右边为多边形的内部。算法首先沿多边形的任一点出发，跟踪检测多边形的每一条线段，当线段与裁剪窗口边界相交时： 1、如果线段起点在窗口外部而终点在窗口内部，则求出交点，输出线段可见部分，继续沿多边形方向往下处理； 2、 如果线段起点在窗口内部而终点在窗口外部，则求出交点，输出线段可见部分。从此交点开始，沿着窗口边界方向往前检测，找到一个多边形与窗口边界的新交点后，输出由前交点到此新交点之间窗口边界上的线段； 3、 返回到前交点，再沿着多边形方向往下处理，直到处理完多边形的每一条边，回到起点为止。图8说明了双边裁剪算法的执行过程。 Weiler-Atherton算法可适用于任何凸的或凹的多边形裁剪，不会产生多余连线。6非矩形裁剪窗口的线段裁剪9 在某些应用中，需要用任意形状的多边形对线段裁剪。对凸多边形裁剪窗口，可以修改粱友栋-Barsky的参数化线段裁剪方法，使参数化方程适合裁剪区域的边界，按照裁剪多边形的坐标范围处理线段。这就成为另一种称之为Cyrus-Beck线段裁剪方法的算法。而前面介绍的两种多边形裁剪方法都适应于任意凸多边形裁剪窗口。 圆或其他曲线边界也可以用作为裁剪窗口，但用的很少。用这些区域的裁剪算法速度更慢，因为它的求交计算涉及非线性曲线方程。加快速度的一个方法是可以首先使用曲线裁剪区域的外接矩形裁剪，完全落在外接矩形之外的裁剪对象被舍弃。如果是用圆作为窗口对线段裁剪，可以通过计算圆心到直线端点的距离来识别出内部线段。其他线段通过解联立方程来计算交点。7曲线的裁剪9 曲线的裁剪过程涉及到非线性方程，需要更多的处理。圆或者其它曲线对象的外接矩形可以用来首先测试是否与矩形裁剪窗口有重叠。如果曲线对象的外接矩形完全落在裁剪窗口内，则曲线对象完全可见，如果曲线对象的外接矩形完全落在裁剪窗口外，则曲线对象完全不可见。两种情况都不满足时，一般需要解直线和曲线的联立方程求交点。 图8 处理曲线对象的另一有效方法是把它们近似为直线段，然后使用线段或多边形的裁剪算法。曲线绘制时通常也使用直线段逼近的方法，由于逼近时总是将线段取的很短，为了减少计算时间，裁剪时可以不计算交点，只要线段的端点中至少有一个在裁剪窗口外，就舍弃该线段，从而提高裁剪效率。8字符的裁剪 字符既可由单个的线段或笔划构成，也可以用点阵来表示。由裁剪精度要求不同，字符裁剪也采用不同的方法。 精确裁剪是对单个字符进行裁剪。此时笔划式字符可看作是短直线段的集合，用裁剪线段的方法进行裁剪。点阵式字符必须将字符方框中每一象素同裁剪窗口进行比较，以确定它位于窗口内还是窗口外。若位于窗口内，该象素被激活，否则不予考虑。 如果把每个字符看作是不可分割的整体，那么对每一个字符串就可用逐字裁剪的方法。这可将字符方框同裁剪窗口进行比较，若整个方框位于窗口内，则显示相应字符，否则不予显示。最后一种处理方法是把一个字符串作为不可分割的整体来处理，或者全部显示，或者全部不显示。将字符串用一个字符串框封闭起来，若整个方框位于窗口内，则显示整串字符，否则整串字符就不显示。串精度裁剪：将包围字串的外接矩形对窗口作裁剪。当字符串方框整个在窗口内时予以显示，否则不显示。字符精度裁剪：将包围字的外接矩形对窗口作裁剪，某个字符方框整个落在窗口内予以显示，否则不显示。笔画象素精度裁剪：将笔划分解成直线段对窗口作裁剪，处理方法同上。 总结本文主要涉及二维图形的裁剪算法，裁剪有内裁剪及外裁剪, 即对各种不同的原始图形,如点、矢量线段、文本、多边形及曲线等进行判断, 把显示窗口以内的部分保留, 而裁去窗口以外的图形,称为内裁剪; 反之, 称为外裁剪。本文主要涉及线段的矢量裁剪、线段的编码裁剪法、多边形的裁剪、圆的裁剪、双边裁剪法、非矩形裁剪窗口的线段裁剪、曲线的裁剪、字符的裁剪。参考文献1 韩俊卿 葛永慧 张东升 多边形窗口的矢量图形裁剪算法 太原理工大