计算机图形学：Lecture 8 开窗口及二维裁剪

1、Lecture 8开窗口及二维裁剪 概述我们把用一观察窗口有选择地显示物体的某一部分称为开窗口技术，如果要求删除显示区域之外的画面部分则称为裁剪，用开窗口技术不但可灵活地显示物体的各个部分，还可通过动态地改变画面的大小及位置，产生某些特殊的显示效果。 开窗口及裁剪的基本概念 坐标系 窗口与视区 窗口在图形显示中的应用 裁剪 坐标系 图形系统中使用的坐标系是人们广为熟悉的直角坐标系，也称笛卡尔坐标系。 建模坐标系 世界坐标系 设备坐标系 规格化设备坐标系 建模坐标系 构造一个复杂的场景需要许多物体，如果这些物体都定义于世界坐标系中，那么它们的表示可能是极其复杂的，甚至是难于构造的.此时，不妨将物

2、体定义于其局部坐标系建模坐标系（MC：Modeling Coordinates）中，由于建模坐标系是依物体而建的，物体在其中的表示相对简单，易于描述，模型坐标系是直角右手坐标系，长度单位由用户自定，取值范围是整个实数域。 世界坐标系 单个物体的形状一旦被指定后，需要将其放入到场景的适当位置.世界坐标系也就是场景坐标系。场景是采用世界坐标系（WC：World Coordinates）描述的，世界坐标系是直角右手坐标系，长度单位由用户自定，取值范围是整个实数域。 设备坐标系 图形用的第三种坐标系是设备坐标系（DC：Device Coordinates）。 显示器屏幕的直角坐标系，原点在左上角，x轴

3、向右为正，y轴向下为正，长度以光栅单位(两个像素之距)为单位。 绘图仪、数字化仪这类设备的坐标系，原点在设备台面的左下角，x轴向右为正，y轴向上为正，长度单位是设备的步距。 规格化设备坐标系 第四种坐标系称为规格化设备坐标系（NDC：Normalized Device Coordinates）。NDC是一种虚拟的坐标系，它与具体设备无关，其坐标值在0l之间。NDC将WC与DC联系起来，使两种坐标系间建立一一对应的关系，用户在用WC描述物体图形时，能在具体的图形设备上正确输出。 坐标系变换通常，在最后变换为特定的设备坐标之前，图形系统需要将世界坐标位置变换为规范化设备坐标位置。这样可使系统独立于

4、可能使用的特定工作站的各种设备。下图是从建模坐标系到设备坐标系的坐标变换系列。图中初始的建模坐标位置（xmc, ymc）变换为设备坐标位置（xdc, ydc），其序列为：（xmc, ymc）（xwc, ywc）（xndc, yndc）（xdc, ydc） 窗口与视区 考察一个图形时，采用两种模型：物理模型，它是用户在世界坐标系中描述物体的图形；逻辑模型，也就是在显示器上呈现的物体的图形它是在设备坐标系中描述的。世界坐标系中描述物体的图形可能相当复杂：只能在显示器上显示局部的内容，以使用户能清晰地观察其细节部分 用户可能只对图形的某一区域感兴趣，因此也只需要显示这一感兴趣的区域 窗口与视区这个局

5、部的区域是由用户在世界坐标系中指定，而且通常是矩形区域，称这个矩形区域为窗口（Window）指定或选取这样的一个区域称为开窗口。不是把整个屏幕都用来显示窗口内的图形，而是在屏幕上指定一个较小的矩形区域用于显示窗口内的图形，这个在屏幕上的矩形区域就称为视区（Viewport），它是用规格化设备坐标系进行描述的。 窗口与视区窗口是在世界坐标系中指定待显示内容的区域，视区是在显示器（输出设备）上显示窗口内图形的区域。 窗口与视区的关系 如下图：窗口在图形显示中的应用 利用开窗口技术，可灵活地在屏幕上显示一景物的不同部分 ：改变位置变焦：观察细节放大、缩小尺寸掠过要观察的物体多方位的观察物体窗口到视区

6、的变换 在点、直线、多边形及文本的裁剪完成后，最后的结果要映射到视区中显示出来。在此映射过程中，画面的相对比例保持不变。在下图中，窗口内位于（xw，yw）处的一点映射入视区的（xv，yv）处，为保持点在窗口与在视区的相对位置一致，则应满足以下关系： 窗口到视区的变换改写以下两式可得到计算坐标xv及yv的公式如下：从窗口到视区的变换中包括比例及平移两种变换。 窗口到视区的变换窗口视区变换也可以通过组合变换实现：在世界坐标系Owxwyw中，平移使(xwmin，ywmin)至坐标原点，变换为T(-xwmin,-ywmin)。 缩放使窗口的大小和视区相等，变换为：在设备坐标系Ovxvxv中，平移使窗口

7、与视区重合，变换为T(xvmin, yvmin)。 窗口到视区的变换那么，窗口视区变换可表示为：则有： 裁剪 删去窗口边界外所定义画面部分的过程称为裁剪（Clipping）。裁剪有两种实现方式：一种是先将图形对象针对窗口进行裁剪，然后只把窗口内的图形映射入视区（这种方法称为先裁剪后扫描转换）另一种是把世界坐标系中定义的图形首先映射入规格化坐标系，然后沿视区边界裁剪（这种方法称为边扫描转换边裁剪）。一般采用前一种方式。裁剪为了实现沿窗口边界对图形的裁剪，我们首先要讨论组成图形的基本因素（点、线、区域）的裁剪算法。沿着边界对点的裁剪是十分简单方便的，我们只要检查一个点是否在边界内即可。点（x，y）

8、若满足以下不等式则保存下来并映射入视区： xwminxxwmax , ywminyywmax 如果以上四个不等式中任一个不成立，则该点被裁剪。直线及区域与边界相交的情况则复杂得多，其裁剪算法也必须考虑多种情况。 直线的裁剪直线与窗口的关系通常有以下三种情况：整个线段全在窗口内；整个线段全在窗口外；线段部分在窗口外，部分在窗口内。当窗口采用凸多边形时，任何一条直线只会至多有一段在窗口内：当一条直线的两个端点全在窗口内时，该直线整个在窗口内当一条直线的两个端点，一个在窗口内，一个在窗口外时，该直线部分在窗口内，部分在窗口外当一条直线的两个端点全在窗口外时，该直线可能整个在窗口外，也可能部分在窗口内

9、，部分在窗口外实交点是直线段与窗口矩形边界的交点。虚交点则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点。直线段和窗口边界的交点基本思想：对每条直线段p1(x1,y1)p2(x2,y2)分三种情况处理：(1) 直线段完全可见，“简取”之。(2) 直线段完全不可见，“简弃”之。(3) 直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。Cohen-Sutherland算法P1P2P5P6P3P4这是一个最早最流行的线段裁剪算法。该算法通过初始测试来减少要计算的交点数目从而加快线段裁剪算法的速度。编码 每条线段的端点都赋以四位二进

10、制码D3D2D1D0 (上下右左) ，称为区域码（region code）,用来标识出端点相对于裁剪矩形边界的位置。编码规则如下：若xxr，则D1=1，否则D1=0；若yyt，则D3=1，否则D3=0。 任何位赋值为1，代表端点落在相应的位置上，否则该位为0。若端点在裁剪矩形内，区域码为0000。如果端点落在矩形的左下角，则区域码为0101，其它类推。000010000100000110010101101000100110Cohen-Sutherland算法裁剪裁剪一条线段时，先求出端点p1和p2的编码code1和code2，然后：(1)若code1|code2=0，对直线段应简取之。(2)若

11、code1&code20，对直线段可简弃之。(3)若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。000010000100000110010101101000100110Cohen-Sutherland算法求交：假定直线的端点坐标为(x1,y1)和(x2,y2)左、右边界交点的计算：下、上边界交点的计算：计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点if(LEFT&code !=0)x=XL;y=y1+(y2-y1)*(XL-x1)/

12、(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);Cohen-Sutherland算法算法的步骤：(1)输入直线段的两端点坐标：p1(x1,y1)、p2(x2,y2)，以及窗口的四条边界坐标：yt、yb、xl和xr。(2)对p1、p2进行编码：点p1的编码为code1，点p2的编码为

13、code2。(3)若code1|code2=0，对直线段应简取之，转(6)；否则，若code1&code20，对直线段可简弃之，转(7)；当上述两条均不满足时，进行步骤(4)。(4)确保p1在窗口外部：若p1在窗口内，则交换p1和p2的坐标值和编码。(5)按左、右、下、上的顺序求出直线段与窗口边界的交点，并用该交点的坐标值替换p1的坐标值。也即在交点s处把线段一分为二，并去掉p1s这一段。考虑到p1是窗口外的一点，因此可以去掉p1s。转(2)。(6)用直线扫描转换算法画出当前的直线段p1p2。(7)算法结束。Cohen-Sutherland算法中点分割算法 中点分割算法的基本思想是，与Cohe

14、n-Sutherland算法一样对线段端点进行编码，并把线段与窗口的关系同样分为三种情况，并对前两种情况进行同样的处理。对于第三种情况，则简单地把线段等分为二段，对两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口外为止。 Liang - Barsky算法 Liang（梁友栋）Barsky算法又称为参数方程法。首先写出端点（x1，y1）及（x2，y2）之间连线的参数方程如下：如果直线上的某点（x，y）处于（xwmin，ywmin）及（xwmax，ywmax）所定义的窗口之内，则满足以下条件: Liang - Barsky算法以上四个不等式可改写为以下形式: 式中p及q定义为：若pk=0

15、，表示任何一条与窗口边界平行的直线，此处k值表示取哪一个边界(k=1,2,3及4,分别相应于左、右、下及上边界)。如果对某一k值，还满足qk0，则此直线完全在边界外，可不进一步考虑：如果qk0，则此与边界平行的直线在边界内。 Liang - Barsky算法如果pk0，则情况较复杂。此时我们可把直线按从（x1，y1）到（x2，y2）连线方向作为正向，将此直线无限延伸，同时把各窗口边界也无限延伸（如图所示）。然后分以下两种情况讨论：（1）当pk0时，则是由窗口外发出的一条直线的无限延伸线进入相应窗口边界的无限延伸线的内部。（2）当pk0时，情况相反。即直线的延伸线是由窗口边界延伸线的内部到外部。

16、 Liang - Barsky算法当qk0时，我们可以用式u=qk/pk计算出一参数u，此u值应于直线延伸线与窗口边界k的延伸线的交点u1,u2的计算： u1=max(u11, u12), u2=min(u21, u22)EnterEnterLeaveLeaveEnterLeaveEnterLeaveu11u12u21u22Liang - Barsky算法判别准则：u2u1，则此直线被裁剪，并可由u1及u2计算出裁剪点； u1u2，则此直线全部被排除。此裁剪算法所需的计算量较小。每修改一次u1或u2只需要一次除法，在u1及u2确定后，直线与窗口边界的交点只需计算一次，但该算法只能应用于矩形窗口

17、的情形。区域码方法要多次重复计算直线与窗口边界的交点，且每计算一次交点需要一次除法及一次乘法。 多边形裁剪 在一个多边形只画出外部轮廓时，其每条边可按上述直线裁剪算法处理，这样，多边形区域的裁剪就简化为一系列直线的裁剪，如图所示。当用多边形边界定义一个填充区时，要对此填充区裁剪时，就要对直线裁剪算法作某些修改，此时，最后产生的应是由一个以上的闭合区定义的填充区边界，如图所示。 多边形裁剪两种常用的多边形的裁剪算法：Sutherland-Hodgman算法Weiler-Atherton算法 Sutherland-Hodgman算法 基本思路：把被裁剪的多边形依次与窗口的各边界比较，裁剪去多余部分

18、。 此算法的执行过程 ：Sutherland-Hodgman算法为了裁剪此多边形，可把各顶点依次与窗口边界比较。在窗口边界内的顶点保留下来，窗口边界外的顶点则排除而不考虑，窗口边界内外两点连线与窗口边界的交点也应保留下来。设相对于某一边界处理的当前点为P，处理的前一点为S，此时可能有四种情况.：当所有顶点已相对于窗口左边界处理完时，得到的新的多边形顶点序列又相对于下一边界进行裁剪。 Sutherland-Hodgman算法在所裁剪的多边形是一个凹多边形时，最后裁剪生成的区域可能存在两个或多个不相连接的多边形。因为上述区域裁剪算法只产生一个顶点表，所以这些分开的区域可能被连接线连到一块，如图所示

19、。为了移去这些连接线，要对上述算法作修改，或采用更通用的裁剪算法。Weiler-Atherton算法 它可以用一个有内孔的凹多边形去裁剪另一个也有内孔的凹多边形，被裁剪的多边形简称为主多边形裁剪区域称为裁剪多边形。交点：主多边形和裁剪多边形的边界可能相交，也可能不相交。若它们相交，则交点必成对地出现，其中一个交点为主多边形的边进入裁剪多边形内部时的交点，而另一交点为其离开时的交点。Weiler-Atherton算法例如：I1为进入交点 I2为离开交点Weiler-Atherton算法算法从进入交点开始，沿主多边形的外部边界按照逆时针方向向前跟踪，直至找到它与裁剪多边形的一个交点为止。在交点处开始