《图形裁剪算法.doc》由会员分享，可在线阅读，更多相关《图形裁剪算法.doc（13页珍藏版）》请在金锄头文库上搜索。
1、图形裁剪算法研究 摘要 在用户坐标系中定义的图形往往是大而复杂的，而输出设备如显示屏幕的尺寸及其分辨率却是有限的，为了能够清晰地观察某一部分或对其进行某些绘图操作，就需要将所关心的这一局部区域的图形从整个图形中区分出来,这个区分指定区域内和区域外的图形过程称为裁剪，所指定的区域称为裁剪窗口。 裁剪通常是对用户坐标系中窗口边界进行裁剪，然后把窗口内的部分映射到视区中，也可以首先将用户坐标系的图形映射到设备坐标系或规范化设备坐标系中，然后用视区边界裁剪。关键词：矢量裁剪 多边形裁剪 圆裁剪 双边裁剪法 线段裁剪 字符裁剪 引言 在人机交互编辑时，作业员往往要把某一区域放大到整个屏幕显示区，这要靠开
2、窗裁剪来实现。另外，地图的输出往往是分幅输出的，这也要靠开窗裁剪来实现。裁剪是用于描述某一图形要素（如直线、圆等）是否与一多边形窗口（如矩形窗口）相交的过程，其主要用途是确定某些图形要素是否全部位于窗口之内，若只有部分在窗口内又如何裁剪去窗口外的图形，从而只显示窗口内的内容。对于一个完整的图形要素，开窗口时可能使得其一部分在窗口之内，一部分位于窗口外，为了显示窗口内的内容，就需要用裁剪的方法对图形要素进行剪取处理。裁剪时开取的窗口可以为任意多边形，但在实践工作中大多是开一个矩形窗口。1窗口区和视图区1.1坐标系 1.用户坐标系(World Coordinates) 又称为世界坐标系、完全坐标系
3、等，它可以是用户用来定义设计对象的 各种标准坐标系，例直角坐标、极坐标、球坐标、对数坐标等。用户坐标系所拥有的区域范围从理论上说是连续的、无限的。 2.观察坐标系(Viewing Coordinates)在用户坐标中设置观察坐标系，在观察坐标系中定义一个观察窗口。观察坐标系用来任意设置矩形窗口的方向。一旦建立了观察参考系，就可以将用户坐标系下的描述变换到观察坐标系下。由于窗口和视图是在不同坐标系中定义的，因此，在把窗口中图形信息转换到视图区之前，必须进行坐标变换，即把用户坐标系的坐标值转化为设备坐标系的坐标值。图形输出时需要一定的设备，如绘图仪、显示器等，使用的是设备坐标系。设备坐标系一般为二
4、维坐标，如屏幕坐标。它的范围有限，单位一般为整数。设备坐标一般采用无量刚方式，可以转换为有量刚坐标。一旦场景变换到规范化坐标系下的单位正方形中，以后该单位面积只需要简单地映射到具体输出设备的显示区。给出合适的设备驱动程序，就可以使用不同的输出设备。用户可以在用户坐标系中指定感兴趣的任意区域，把这部分区域内的图形输出到屏幕上，这个指定区域称为窗口区。窗口区一般是矩形区域，可以用左下角和右上角两点坐标来定义其大小和位置。图1 用户坐标系 3.规范化设备坐标系(Normalized Device Coordinates)在规范化坐标系下（取值范围从0到1）定义视区，将观察坐标系下的场景描述映射到规范
5、坐标系下。图2 规范化设备坐标系 4.设备坐标系(Device Coordinates)图形输出时需要一定的设备，如绘图仪、显示器等，使用的是设备坐标系。设备坐标系一般为二维坐标，如屏幕坐标。它的范围有限，单位一般为整数。设备坐标一般采用无量刚方式，可以转换为有量刚坐标。一旦场景变换到规范化坐标系下的单位正方形中，以后该单位面积只需要简单地映射到具体输出设备的显示区。给出合适的设备驱动程序，就可以使用不同的输出设备。1.2窗口区和视图区用户可以在用户坐标系中指定感兴趣的任意区域，把这部分区域内的图形输出到屏幕上，这个指定区域称为窗口区。窗口区一般是矩形区域，可以用左下角和右上角两点坐标来定义其
6、大小和位置。定义窗口的目的是要选取图形中需要观察的那一部分图形。在计算机图形学术语中，窗口最初是指要观察的图形区域，但是目前窗口也用于窗口管理系统。在本章中，我们将窗口理解为用户坐标系中要显示的区域。图形设备上用来输出图形的最大区域称之为屏幕域，它是有限的整数域，大小随具体设备而异。任何小于或等于屏幕域的区域都可定义为视图区。视图区由用户在屏幕域中用设备坐标定义，一般也定义成矩形，由其左下角和右上角两点坐标来定义。所以，用户可以利用窗口来选择需要观察那一部分图形，而利用视图区来指定这一部分图形在屏幕上显示的位置。标准的窗口区和视图区一般都是矩形，其各边分别与坐标轴平行。用户定义的图形从窗口区到
7、视图区的输出过程如下：从应用程序得到图形的用户坐标(WC-World Coordinates)对窗口区进行裁剪(WC)窗口区到视图区的规格化变换(NDC-Normalized Device Coordinate)视图区从规格化设备系到设备坐标系的变换(DC-Device Coordinate)在图形设备上输出图形。下图是从用户坐标系取图形在设备坐标系下显示的示意图：图3 用户坐标系1.3窗口区和视图区之间的坐标变换 由于窗口和视图是在不同坐标系中定义的，因此，在把窗口中图形信息转换到视图区之前，必须进行坐标变换，即把用户坐标系的坐标值转化为设备坐标系的坐标值。 设在用户坐标系下，矩形窗口左下角
8、点坐标为(Wxl,Wyb), 右上角点坐标为(Wxr,Wyt)。屏幕中视图区的两个角点在设备坐标系下分别为(Vxl,Vyb)和(Vxr,Vyt)。则在窗口中的点(xw,yw)对应视图区中的点（xv, yv)，其变换公式为：下图为示图： （1） 图4记: （2） （3） （4） （5）公式可以化简为： （6）写成矩阵形式为： （7）上述变换是二维变换中比例变换和平移变换的组合变换。通过变换，可以实现将用户坐标系中窗口区中任意一点转换成设备坐标系中视图区中一点，从而可以把实际图形转换到具体输出设备的显示区。2线段的裁剪 2.1线段的矢量裁剪1 在裁剪时不同的线段可能被窗口分成几段，但其中只有一段位
9、于窗口内可见，线段的裁剪算法就是要找出位于窗口内部的起始点和终止点的坐标。因矢量裁剪法对寻找起点和终点坐标的处理方法相同，下面以求始点坐标为例来说明线段矢量裁剪方法。 在图5中，窗口的四条边界把XOY平面分成九个区域，分别用到对这九个窗口编号，设号区域为相应的可见窗口区，窗口的左下角点坐标（minX,minY），右上角点坐标为（maxX,maxY）。有一条矢量线段S，其起、终点的坐标分别为（Xs,Ys）和（Xe,Ye），则对线段S按矢量裁剪的算法步骤如下： 、图51.若线段完全位于区域以外的任意区域内或落在（，）、（，）、（，）、（，）中任意一区域组内，即满足下述条件之一： XsminX且Xe
10、minX且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.
11、当XsmaxX ，即线段起点位于窗口右界的右边，可仿照上述过程求出线段与右边界的交点。5.若起点（Xs,Ys）位于或区时，求解线段与窗口边界的交点公式为（12）和（13）式。 (12) (13)用式（12）和（13）求解得在满足minXXmaxX时才有效，否则线段不在窗口内。 同理，可求解出线段在窗口内新的终点坐标。2.2线段的编码裁剪法10 这种方法和上面介绍的方法相似，所不同的是这种方法把被窗口的边界分成的九个区按一定的规则用四位二进制编码来表示。这样，当线段的端点位于某一区时，该点的位置可以用其所在区域的四位二进制码来唯一确定，通过对线段两端点的编码进行逻辑运算，就可确定线段相对于窗口的
12、关系。 如图6，编码顺序从右到左，每一编码对应线段端点的位置为：第一位为表示端点位于窗口左边界的左边；第二位为表示端点位于右边界的右边；第三位为表示端点位于下边界的下边；第四位为表示端点位于边界的上边。若某位为则表示端点的位置情况与取值时相反。很显然，如果线段的两个端点的四位编码全为，则此线段全部位于窗口内；若线段两个端点的四位编码进行逻辑乘运算的结果为非，则此线段全部在窗口外。对这两种情况无须作裁剪处理。图6 如果一条线段用上述方法无法确定是否全部在窗口内或全部在窗口外，则需要对线段进行裁剪分割，对分割后的每一子线段重复以上编码判断，把不在窗口内的子线段裁剪掉，直到找到位于窗口内的线段为止。 如图中的线段AB，第一次分割成了线段AC和CB，利用编码判断可把线段AC裁剪掉，对线段CB再分割成子线段CD和DB，再利用编码判断又裁剪掉子线段CD，而DB全部位于窗口内，即为裁剪后的线段，裁剪过程结束。直线与窗口边框的交点为：上边框交点： （14） 下边框交点： （15）左边
