计算机图形学第6章开窗口及二维裁剪.ppt

第6章 开窗口及二维裁剪 应用程序中所定义的画面均以世界坐标系表示，这些画面要映射到 设备坐标系才可以显示出来。在显示器上可以只选择一个显示区域观察一 幅画面，也可以同时选择若干显示区域观察若干幅画面。把用一观察窗口 有选择地显示物体地某一部分称为开窗口技术，如果要求删除显示区域之 外的画面部分则称为裁剪。 第6章 开窗口及二维裁剪 6.1 开窗口及裁剪的基本概念 6.2 直线裁剪算法 6.3 多边形裁剪 6.4 文本裁剪 6.1 开窗口及裁剪的基本概念 6.1.1 坐标系 组成图形的最基本元素是点，而点的位置通常是在一个坐标系 中定义的。图形系统中所使用的坐标系是人们广为熟悉的直角 坐标系，也称笛卡儿坐标系。 1.建模坐标系（MC） 依物体而建，物体在其中的表示相对简单，易于描述。是直角 右手坐标系，长度单位由用户自定，取值范围是整个实数域。 2.世界坐标系（WC） 单个物体的形状一旦被指定以后，需要将其放入到场景的适当 位置，场景是采用世界坐标系描述的。是直角右手坐标系，长 度单位由用户自定，取值范围是整个实数域。 6.1.1 坐标系 3.设备坐标系（DC） 无论是显示器、绘图仪还是数字化仪，通常都采用二维直角坐标 系，但原点及轴向依具体设备的不同而不同。 4.规格华设备坐标系（NDC） 是一种虚拟的坐标系，它与具体设备无关，其坐标在01之间。 NDC将WC与DC联系起来，使两种坐标系之间建立一一对应的关 系，用户在用WC描述物体图形时，能在具体的图形设备上正确 输出。 6.1.1 坐标系 在最后变换为特定设备坐标之前，图形系统需要将世界坐标位置变换 为规范化设备坐标位置。这样可使系统独立于可能使用的特定工作站 的各种设备。 图中，初始建模坐标位置（xmc，ymc）变换为设备坐标位置（xdc ，ydc），其系列为 6.1.2 窗口与视区 窗口：用户在世界坐标系中指定的局部区域，通常是矩形区域。 开窗口：指定或选取一个区域。 视区：在屏幕上指定一个较小的矩形区域，用于显示窗口内的图形， 这个在屏幕上的矩形区域称为视区，它是用规格化设备坐标系进行描 述的。 6.1.3 窗口在图形显示中的应用 1.利用开窗口技术，可灵活地在屏幕上显示一景物的不同部分、改变窗 口及视区的大小和位置，可使显示的图形发生变化。 2.对于一个显示物体可定义多个窗口及多个视区，这样可多方位、多侧 面观察一个物体。 3.在多工作站的情况下，可在各工作站建立不同的窗口及视区，这样就 可以在不同的输出设备上显示物体的不同部分。 6.2 直线裁剪算法 v裁剪的含义 为了能看到计算机内部存储数据量比较大的图形的各个局部细节 。在放大显示一幅图形的一部分区域时，必须确定图形中哪些部分落 在显示区之内，哪些落在显示区之外，以便显示落在显示区内的那部 分图形。这个选择过程称为裁剪。 v裁剪的实质 决定图形中哪些点、线段、文字、以及多边形在窗口之 内。 6.2.1直线裁剪的基本原理 n裁剪的目的 n判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分 n裁剪的处理的基础 n图元关于窗口内外关系的判别 n图元与窗口的求交 n假定条件 n矩形裁剪窗口：xmin,xmaxXymin,ymax n待裁剪线段： 6.2.1直线裁剪的基本原理 n点裁剪 n点(x, y)在窗口内的充分必要条件是： 6.2.1直线裁剪的基本原理 为提高效率，算法设计时应考虑： (一）快速判断情形(1)(2)； (二) 设法减少情形(3)求交次数和每次求交时所需的计算量 。 n待裁剪线段和窗口的关系 n线段完全可见 n显然不可见 n线段至少有一端点在窗口之外，但非显然不可见 6.2.2 Cohen-Sutherland直线裁剪算法 Cohen-Sutherland算法思想：对于每条线段P1P2，分为3种情况 处理： （1）若P1P2完全在窗口内，则显示该线段P1P2，简称取之 （2）若P1P2明显在窗口外，则丢弃该线段P1P2，简称弃之 （3）若线段既不满足“取”的条件，也满足“弃”的条件，则 把线段分成两段。其中一段完全在窗口外，可弃之。然后 对另一段重复上述处理。 6.2.2 Cohen-Sutherland直线裁剪算法 一、区域码建立 区域码：表示直线端点相对位置的4位二进制代码。 区域码按照端点与窗口边界的相对编码，即区域码的4位 分别代表端点位于窗口的上、下、左、右。 区域，码从右到左的各位所代表的坐标区如下： 6.2.2 Cohen-Sutherland直线裁剪算法 一、区域码建立 编码方法： 由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个 四位编码CtCbCrCl（上下右左）；代码每位用0或1来表示，并且规 定： 在窗口上边线之上，第4位为1，否则第4位为0； 在窗口下边线之下，第3位为1，否则第3位为0； 在窗口右边线之右，第2位为1，否则第2位为0； 在窗口左边线之左，第2位为1，否则第1位为0； 6.2.2 Cohen-Sutherland直线裁剪算法 一、区域码建立 6.2.2 Cohen-Sutherland直线裁剪算法 二、区域码裁剪算法 100110001010 0001 0000 0010 010101000110 P1P2 v端点间关系 线段与窗口关系 若code1=0且 code20，P1P2明显在窗口内，则“取” 6.2.2 Cohen-Sutherland直线裁剪算法 二、区域码裁剪算法 100110001010 000100000010 010101000110 P1 P2 code1: 0101 y=y1+(y2-y1)*(XL-x1)/(x2-x1); else if(RIGHTy=y1+(y2-y1)*(XR-x1)/(x2-x1); else if(BOTTOMx=x1+(x2-x1)*(YB-y1)/(y2-y1); else if(TOP x=x1+(x2-x1)*(YT-y1)/(y2-y1); 6.2.3 中点分割算法 n基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找 出离P1最近的可见点。这两个可见点的连线就是原线段的可见部 分。 n与Cohen-Sutherland算法一样首先对线段端点进行编码，并把 线段与窗口的关系分为三种情况，对前两种情况，进行一样的处 理；对于第三种情况，用中点分割的方法求出线段与窗口的交点 。A、B分别为距P0 、 P1最近的可见点，Pm为P0P1中点。 6.2.3 中点分割算法 从P0出发找距离P0最近可见点采用中点分割方法 先求出P0P1的中点Pm, 若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则 距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1； 否则取PmP1代替P0P1。 再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给 定的控制常数为止，此时Pm收敛于交点。 从P1出发找距离P1最近可见点采用上面类似方法。 6.2.3 中点分割算法 6.3 多边形裁剪 错觉：直线段裁剪的组合？ 新的问题：边界不再封闭，需要用窗口边界的恰当部分来封闭 它，如何确定其边界？ 6.3.1 Sutherland-Hodgman算法 v基本思想：每次用窗口的一条边裁剪多边形 v流水线过程(左上右下)：前边的结果是后边的输入 6.3.1 Sutherland-Hodgman算法 算法实现 v窗口的一条边以及延长线构成的裁剪线把平面分成两个部分 v多边形的各条边的两端点S、P与裁剪线的位置关系有四种 (1)输出顶点P (2)无输出 (3) 输出交点I (4) 输出I和P 6.3.1 Sutherland-Hodgman算法 （1） （2） （3） （4） 结果：上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序 列，作为下一条裁剪边处理过程的输入。 输出P3输出I1和P2输出I2无输出 6.3.1 Sutherland-Hodgman算法 算法需要附加空间以存放各保留点。为了减小存储空间，可把整个裁剪 程序划分为若干部分，每一部分对一个窗口边界进行裁剪，裁剪得到的 窗口内的点略去不再传送。只有在对所有边均作处理后才把保留点存放 起来。 在所裁剪的多边形是一个凹多边形时，最后裁剪生成的区域可能存在两 个或多个不相连接的多边形。 6.3.2 Weiler-Atherton算法 裁剪窗口为任意多边形（凸、凹、带内环）的情况： n主多边形：被裁剪多边形，记为A n裁剪多边形：裁剪窗口，记为B 6.3.2 Weiler-Atherton算法 裁剪结果区域的边界由A的部分边界和B 的部分边界两部分构成，并且在交点处 边界发生交替，即由A的边界转至B的边 界，或由B的边界转至A的边界 多边形顶点的排列顺序（使多边形区域位于有向边的左侧 ）外环：逆时针 ；内环：顺时针 n主多边形和裁剪多边形把二维平面分成两部分。 n内裁剪：AB n外裁剪：A-B 6.3.2 Weiler-Atherton算法 n如果主多边形与裁剪多边形有交点，则交点成对出 现，它们被分为如下两类： n进点：主多边形边界由此进入裁剪多边形内 如，I1,I3, I5, I7, I9, I11 n出点：主多边形边界由 此离开裁剪多边形区域. 如， I0,I2, I4, I6, I8, I10 6.3.2 Weiler-Atherton算法 6.3.2 Weiler-Atherton算法 6.3.2 Weiler-Atherton算法 1、建立主多边形和裁剪多边的顶点表 2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的 顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。 3、裁剪:如果存在没有被跟踪过的交点，执行以下步骤： 6.3.2 Weiler-Atherton算法 6.4 文本裁剪 图形包中的文本生成方法不同，可能有多种不同的裁剪方法。 （1）对于标准字符，一般把字符作为一个整体裁剪 （2）用线段组成的字符，可用直线裁剪方法裁剪。 文本的裁剪可分为： 以串为单