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

《计算机图形学第6章开窗口和二维裁剪.ppt》由会员分享，可在线阅读，更多相关《计算机图形学第6章开窗口和二维裁剪.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章章 开窗口及二维裁剪开窗口及二维裁剪 应用程序中所定义的画面均以世界坐标系表示，这些画面要映射到应用程序中所定义的画面均以世界坐标系表示，这些画面要映射到设备坐标系才可以显示出来。在显示器上可以只选择一个显示区域观察一设备坐标系才可以显示出来。在显示器上可以只选择一个显示区域观察一幅画面，也可以同时选择若干显示区域观察若干幅画面。把用一观察窗口幅画面，也可以同时选择若干显示区域观察若干幅画面。把用一观察窗口有选择地显示物体地某一部分称为开窗口技术，如果要求删除显示区域之有选择地显示物体地某一部分称为开窗口技术，如果要求删除显示区域之外的画面部分则称为裁剪。外的画面部分则称为裁剪。第第6

2、章章 开窗口及二维裁剪开窗口及二维裁剪6.1 开窗口及裁剪的基本概念开窗口及裁剪的基本概念6.2 直线裁剪算法直线裁剪算法6.3 多边形裁剪多边形裁剪6.4 文本裁剪文本裁剪6.1 开窗口及裁剪的基本概念6.1.1 6.1.1 坐标系坐标系组成图形的最基本元素是点，而点的位置通常是在一个坐标系组成图形的最基本元素是点，而点的位置通常是在一个坐标系中定义的。图形系统中所使用的坐标系是人们广为熟悉的直角中定义的。图形系统中所使用的坐标系是人们广为熟悉的直角坐标系，也称笛卡儿坐标系。坐标系，也称笛卡儿坐标系。1.建模坐标系（建模坐标系（MC）依物体而建，物体在其中的表示相对简单，易于描述。是直角依物

3、体而建，物体在其中的表示相对简单，易于描述。是直角右手坐标系，长度单位由用户自定，取值范围是整个实数域。右手坐标系，长度单位由用户自定，取值范围是整个实数域。2.世界坐标系（世界坐标系（WC）单个物体的形状一旦被指定以后，需要将其放入到场景的适当单个物体的形状一旦被指定以后，需要将其放入到场景的适当位置，场景是采用世界坐标系描述的。是直角右手坐标系，长位置，场景是采用世界坐标系描述的。是直角右手坐标系，长度单位由用户自定，取值范围是整个实数域。度单位由用户自定，取值范围是整个实数域。6.1.1 6.1.1 坐标系坐标系3.设备坐标系（设备坐标系（DC）无论是显示器、绘图仪还是数字化仪，通常都采

4、用二维直角坐标无论是显示器、绘图仪还是数字化仪，通常都采用二维直角坐标系，但原点及轴向依具体设备的不同而不同。系，但原点及轴向依具体设备的不同而不同。4.规格华设备坐标系（规格华设备坐标系（NDC）是一种虚拟的坐标系，它与具体设备无关，其坐标在是一种虚拟的坐标系，它与具体设备无关，其坐标在01之间。之间。NDC将将WC与与DC联系起来，使两种坐标系之间建立一一对应的关联系起来，使两种坐标系之间建立一一对应的关系，用户在用系，用户在用WC描述物体图形时，能在具体的图形设备上正确描述物体图形时，能在具体的图形设备上正确输出。输出。6.1.1 6.1.1 坐标系坐标系在最后变换为特定设备坐标之前，图

5、形系统需要将世界坐标位置变换在最后变换为特定设备坐标之前，图形系统需要将世界坐标位置变换为规范化设备坐标位置。这样可使系统独立于可能使用的特定工作站为规范化设备坐标位置。这样可使系统独立于可能使用的特定工作站的各种设备。的各种设备。图中，初始建模坐标位置（图中，初始建模坐标位置（xmc，ymc）变换为设备坐标位置（）变换为设备坐标位置（xdc，ydc），其系列为），其系列为6.1.2 6.1.2 窗口与视区窗口与视区窗口窗口：用户在世界坐标系中指定的局部区域，通常是矩形区域。：用户在世界坐标系中指定的局部区域，通常是矩形区域。开窗口开窗口：指定或选取一个区域。：指定或选取一个区域。视区视区：在

6、屏幕上指定一个较小的矩形区域，用于显示窗口内的图形，：在屏幕上指定一个较小的矩形区域，用于显示窗口内的图形，这个在屏幕上的矩形区域称为视区，它是用规格化设备坐标系进行描这个在屏幕上的矩形区域称为视区，它是用规格化设备坐标系进行描述的。述的。6.1.3 6.1.3 窗口在图形显示中的应用窗口在图形显示中的应用1.利用开窗口技术，可灵活地在屏幕上显示一景物的不同部分、改变窗利用开窗口技术，可灵活地在屏幕上显示一景物的不同部分、改变窗口及视区的大小和位置，可使显示的图形发生变化。口及视区的大小和位置，可使显示的图形发生变化。2.对于一个显示物体可定义多个窗口及多个视区，这样可多方位、多侧对于一个显示

7、物体可定义多个窗口及多个视区，这样可多方位、多侧面观察一个物体。面观察一个物体。3.在多工作站的情况下，可在各工作站建立不同的窗口及视区，这样就在多工作站的情况下，可在各工作站建立不同的窗口及视区，这样就可以在不同的输出设备上显示物体的不同部分。可以在不同的输出设备上显示物体的不同部分。6.2 直线裁剪算法v裁剪的含义裁剪的含义 为了能为了能看到看到计算机内部存储数据量比较大的计算机内部存储数据量比较大的图形的各个局部细节图形的各个局部细节。在放大显示一幅图形的一部分区域时，必须在放大显示一幅图形的一部分区域时，必须确定图形中确定图形中哪些哪些部分落在部分落在显示区之内显示区之内，哪些哪些落在

8、显示区之外，落在显示区之外，以便显示以便显示落在显示区内的那部分落在显示区内的那部分图形。这个选择过程称为裁剪。图形。这个选择过程称为裁剪。v裁剪的实质裁剪的实质 决定图形中哪些点、线段、文字、以及多边形在窗口之决定图形中哪些点、线段、文字、以及多边形在窗口之内。内。直线裁剪的基本原理n裁剪的目的裁剪的目的n判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分n裁剪的处理的基础裁剪的处理的基础n图元关于窗口内外关系的判别图元关于窗口内外关系的判别n图元与窗口的求交图元与窗口的求交n假定条件假定条件n矩形裁剪窗口：矩形裁剪窗口：xmin,x

9、maxXymin,ymaxn待裁剪线段：待裁剪线段：直线裁剪的基本原理n点裁剪点裁剪 n点点(x,y)在窗口内的充分必要条件是：在窗口内的充分必要条件是：直线裁剪的基本原理为提高效率，算法设计时应考虑：(一）快速判断情形(1)(2)；(二)设法减少情形(3)求交次数和每次求交时所需的计算量。n待裁剪线段和窗口的关系待裁剪线段和窗口的关系 n线段完全可见线段完全可见n显然不可见显然不可见 n线段至少有一端点在窗口之外，但非显然不可见线段至少有一端点在窗口之外，但非显然不可见 6.2.2 Cohen-Sutherland直线裁剪算法Cohen-SutherlandCohen-Sutherland算

10、法思想：对于每条线段算法思想：对于每条线段P P1 1P P2 2，分为，分为3 3种情况种情况处理：处理：（1 1）若）若P P1 1P P2 2完全在窗口内，则显示该线段完全在窗口内，则显示该线段P P1 1P P2 2，简称，简称取取之之（2 2）若）若P P1 1P P2 2明显在窗口外，则丢弃该线段明显在窗口外，则丢弃该线段P P1 1P P2 2，简称，简称弃弃之之（3 3）若线段既不满足）若线段既不满足“取取”的条件，也满足的条件，也满足“弃弃”的条件，的条件，则把线段分成两段。其中一段完全在窗口外，可弃之。然则把线段分成两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处

11、理。后对另一段重复上述处理。6.2.2 Cohen-Sutherland直线裁剪算法一、区域码建立一、区域码建立区域码：表示直线端点相对位置的区域码：表示直线端点相对位置的4位二进制代码。位二进制代码。区域码按照端点与窗口边界的相对编码，即区域码的区域码按照端点与窗口边界的相对编码，即区域码的4位位分别代表端点位于窗口的上、下、左、右。分别代表端点位于窗口的上、下、左、右。区域，码从右到左的各位所代表的坐标区如下：区域，码从右到左的各位所代表的坐标区如下：6.2.2 Cohen-Sutherland直线裁剪算法一、区域码建立一、区域码建立 编码方法：编码方法：由窗口四条边所在直线把二维平面分成

12、由窗口四条边所在直线把二维平面分成9 9个区域，每个区域赋予一个个区域，每个区域赋予一个四位编码四位编码C Ct tC Cb bC Cr rC Cl l（上下右左）；代码每位用（上下右左）；代码每位用0 0或或1 1来表示，并且规来表示，并且规定：定：在窗口上边线之上，第在窗口上边线之上，第4 4位为位为1 1，否则第，否则第4 4位为位为0 0；在窗口下边线之下，第在窗口下边线之下，第3 3位为位为1 1，否则第，否则第3 3位为位为0 0；在窗口右边线之右，第在窗口右边线之右，第2 2位为位为1 1，否则第，否则第2 2位为位为0 0；在窗口左边线之左，第在窗口左边线之左，第2 2位为位为

13、1 1，否则第，否则第1 1位为位为0 0；6.2.2 Cohen-Sutherland直线裁剪算法一、区域码建立一、区域码建立6.2.2 Cohen-Sutherland直线裁剪算法二、区域码裁剪算法二、区域码裁剪算法100110001010000100000010010101000110P1P2v端点间关系端点间关系 线段与窗口关系线段与窗口关系若若code1=0且且 code20，P1P2明显在窗口内，则明显在窗口内，则“取取”6.2.2 Cohen-Sutherland直线裁剪算法二、区域码裁剪算法二、区域码裁剪算法10011000101000010000001001010100011

14、0P1P2code1:0101&code2:0100 0100v端点间关系端点间关系 线段与窗口关系线段与窗口关系若若code1&code20，P1P2明显在窗口外，则明显在窗口外，则“弃弃”6.2.2 Cohen-Sutherland直线裁剪算法二、区域码裁剪算法二、区域码裁剪算法100110001010000100000010010101000110P2P1P3 code1=000code1=0001 1，P1P1在窗口左边，计算线在窗口左边，计算线段与窗口左边界的交点段与窗口左边界的交点P3P3；code2=0code2=01 10000，P2P2在窗口下方，用窗口在窗口下方，用窗口下边

15、界与线段求交点下边界与线段求交点P4P4；code1=0001,code2=0100,不满足（不满足（1）code1&code2=0，不满足（，不满足（2）P4P3v端点间关系端点间关系 线段与窗口关系线段与窗口关系在交点处把线段分为两段。其中一段完全在窗口外，可在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。弃之。然后对另一段重复上述处理。6.2.2 Cohen-Sutherland直线裁剪算法二、区域码裁剪算法二、区域码裁剪算法如何判定应该与窗口的哪条边求交呢？如何判定应该与窗口的哪条边求交呢？编码中对应位为编码中对应位为1的边。的边。计算线段计算线段P1(

16、x1,y1)P2(x2,y2)与窗口边界的交点与窗口边界的交点if(LEFT&code!=0)x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);else if(RIGHT&code!=0)x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);else if(BOTTOM&code!=0)y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);else if(TOP&code!=0)y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);6.2.3 中点分割算法n基本思想：基本思想：从从P P0 0点出发找出离点出发找出离P P0 0最近的

17、可见点，和从最近的可见点，和从P P1 1点出发找点出发找出离出离P P1 1最近的可见点。这两个可见点的连线就是原线段的可见部最近的可见点。这两个可见点的连线就是原线段的可见部分。分。n与与Cohen-SutherlandCohen-Sutherland算法一样首先对线段端点进行编码，并把算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A A、B B分别为距分别为距P P0 0

18、、P P1 1最近的可见点，最近的可见点，PmPm为为P P0 0P P1 1中点。中点。6.2.3 中点分割算法从从P0P0出发找距离出发找距离P0P0最近可见点采用中点分割方法最近可见点采用中点分割方法先求出先求出P0P1P0P1的中点的中点Pm,Pm,若若P0PmP0Pm不是显然不可见的，并且不是显然不可见的，并且P0P1P0P1在窗口中有可见部分，则在窗口中有可见部分，则距距P0P0最近的可见点一定落在最近的可见点一定落在P0PmP0Pm上，所以用上，所以用P0PmP0Pm代替代替P0P1P0P1；否则取否则取PmP1PmP1代替代替P0P1P0P1。再对新的再对新的P0P1P0P1求

19、中点求中点PmPm。重复上述过程，直到。重复上述过程，直到PmP1PmP1长度小于给长度小于给定的控制常数为止，此时定的控制常数为止，此时PmPm收敛于交点。收敛于交点。从从P1P1出发找距离出发找距离P1P1最近可见点采用上面类似方法。最近可见点采用上面类似方法。6.2.3 中点分割算法6.3 多边形裁剪错觉：错觉：直线段裁剪的组合？直线段裁剪的组合？新的问题：新的问题：边界不再封闭，需要用窗口边界的恰当部分来封闭边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？它，如何确定其边界？Sutherland-Hodgman算法v基本思想基本思想：每次用窗口的一条边裁剪多边形每次用窗

20、口的一条边裁剪多边形v流水线过程流水线过程(左上右下左上右下)：前边的结果是后边的输入前边的结果是后边的输入 Sutherland-Hodgman算法算法实现算法实现v窗口的一条边以及延长线构成的裁剪线把平面分成两个部分窗口的一条边以及延长线构成的裁剪线把平面分成两个部分v多边形的各条边的两端点多边形的各条边的两端点S S、P P与裁剪线的位置关系有四种与裁剪线的位置关系有四种(1)(1)输出顶点输出顶点P P(2)(2)无输出无输出(3)(3)输出交点输出交点I I(4)(4)输出输出I I和和P P Sutherland-Hodgman算法（1）（2）（3）（4）结果：上述算法仅用一条裁剪

21、边对多边形进行裁剪，得到一个顶点序结果：上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。列，作为下一条裁剪边处理过程的输入。输出输出P P3 3输出输出I I1 1和和P P2 2输出输出I I2 2无输出无输出 Sutherland-Hodgman算法算法需要附加空间以存放各保留点。为了减小存储空间，可把整个裁剪算法需要附加空间以存放各保留点。为了减小存储空间，可把整个裁剪程序划分为若干部分，每一部分对一个窗口边界进行裁剪，裁剪得到的程序划分为若干部分，每一部分对一个窗口边界进行裁剪，裁剪得到的窗口内的点略去不再传送。只有在对所有边均作处理后才把保留

22、点存放窗口内的点略去不再传送。只有在对所有边均作处理后才把保留点存放起来。起来。在所裁剪的多边形是一个凹多边形时，最后裁剪生成的区域可能存在两在所裁剪的多边形是一个凹多边形时，最后裁剪生成的区域可能存在两个或多个不相连接的多边形。个或多个不相连接的多边形。Weiler-Atherton算法裁剪窗口为任意多边形（凸、凹、带内环）的情况：裁剪窗口为任意多边形（凸、凹、带内环）的情况：n主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为A n裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为B Weiler-Atherton算法裁剪结果区域的边界由裁剪结果区域的边界由A的部分边界和的部分边界

23、和B的部分边界两部分构成，并且在交点处的部分边界两部分构成，并且在交点处边界发生交替，即由边界发生交替，即由A的边界转至的边界转至B的边的边界，或由界，或由B的边界转至的边界转至A的边界的边界 多边形顶点的排列顺序（使多边形区域位于有向边的左侧多边形顶点的排列顺序（使多边形区域位于有向边的左侧）外环：逆时针）外环：逆时针；内环：顺时针；内环：顺时针n主多边形和裁剪多边形把二维平面分成两部分。主多边形和裁剪多边形把二维平面分成两部分。n内裁剪：内裁剪：ABABn外裁剪：外裁剪：A-BA-B Weiler-Atherton算法n如果主多边形与裁剪多边形有交点，则如果主多边形与裁剪多边形有交点，则交

24、点成对出交点成对出现，现，它们被分为如下两类：它们被分为如下两类：n进点进点：主多边形边界由此进入裁剪多边形内：主多边形边界由此进入裁剪多边形内 如，如，I1,I3,I5,I7,I9,I11n出点出点：主多边形边界由：主多边形边界由此离开裁剪多边形区域此离开裁剪多边形区域.如，如，I0,I2,I4,I6,I8,I10 Weiler-Atherton算法 Weiler-Atherton算法 Weiler-Atherton算法1 1、建立主多边形和裁剪多边的顶点表、建立主多边形和裁剪多边的顶点表2 2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的、求主多边形和裁剪多边形的交点，并

25、将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。3 3、裁剪、裁剪:如果存在没有被跟踪过的交点，执行以下步骤：如果存在没有被跟踪过的交点，执行以下步骤：Weiler-Atherton算法6.4 文本裁剪图形包中的文本生成方法不同，可能有多种不同的裁剪方法。图形包中的文本生成方法不同，可能有多种不同的裁剪方法。（1 1）对于标准字符，一般把字符作为一个整体裁剪）对于标准字符，一般把字符作为一个整体裁剪（2 2）用线段组成的字符，可用直线裁剪方法裁剪。）用线段组成的字符，可用直线裁剪方法裁剪。文本的裁剪可

26、分为：文本的裁剪可分为：以串为单位的裁剪以串为单位的裁剪以字符为单位的裁剪以字符为单位的裁剪矢量裁剪矢量裁剪 以串为单位的裁剪v字符串裁剪：字符串裁剪：把整个字符串作为整体来处理：或者全部显示，或者全部不显把整个字符串作为整体来处理：或者全部显示，或者全部不显示。测试时可以选用整个字符界框。示。测试时可以选用整个字符界框。以字符为单位的裁剪v字符裁剪：字符裁剪：每个字符被一个称为字符框的矩形所包围，然后以这个框和窗每个字符被一个称为字符框的矩形所包围，然后以这个框和窗口进行比较，如果这个框在窗口内，则显示此字符。口进行比较，如果这个框在窗口内，则显示此字符。矢量裁剪v矢量裁剪：矢量裁剪：把每个字符都看作是一些短直线（笔划）的组合，故每一笔划把每个字符都看作是一些短直线（笔划）的组合，故每一笔划都必须个别地进行裁剪。都必须个别地进行裁剪。