若直线既不满足“简取”也不满足 “简弃”的条件，直线必然与窗口相交， 需要计算直线与窗口边界的交点。交点 将直线分为两段，其中一段完全位于窗 口外，可“简弃”之。对另一段赋予交 点处的区域编码，再次测试，再次求交， 直至找到确定完全位于窗口内的直线段 为止。 实现时，一般按固定顺序左 （x=wxl），右（x=wxr）、下（y=wyb）、 上（y=wyt）求解窗口与直线的交点。
规格化设备坐标系是将设备坐标系规格化到（0.0， 0.0）到（1.0，1.0）的范围内而定义的坐标系。规格化 设备坐标系独立于具体输出设备。一旦图形变换到规格 化设备坐标系中，只要作一个简单的乘法运算即可映射 到具体的设备坐标系中。由于规格化设备坐标系能统一 用户各种图形的显示范围，故把用户图形变换成规格化 设备坐标系中的统一大小标准图形的过程叫作图形的逻 辑输出。把规格化设备坐标系中的标准图形送到显示设 备上输出的过程叫作图形的物理输出。有了规格化设备 坐标系后，图形的输出可以在抽象的显示设备上进行讨 论，因而这种图形学又称为与具体设备无关的图形学。
在计算机图形学术语中，窗口最初是指 要观察的图形区域。但是随着Windows的出
现，窗口概念已广泛用于图形系统中，泛指
任何可以移动，改变大小、激活或变为无效
的屏幕上的矩形区域。在本章中，窗口回归
到其的原始定义，是在观察坐标系中确定输
出图形范围的矩形区域。
5.4.3 窗视变换矩阵
窗口和视区的边界定义如图5-23所示，假 定把窗口内的一点P（xw，yw)变换为视区中的 一点P’（xv，yv）。这属于相对于任一参考点 的二维几何变换，变换步骤为：
码RC=C4C3C2C1。
wyt 窗口 0000 wyb
1001
1000
1010
0001
0000
0010
wxl
wxr
0101
0100
0110
5-24 窗口坐标
5-25 区域编码
为了保证窗口内直线端点的编码为零，编码规则定义如下： 第一位：若端点位于窗口之左侧，即x<wxl，则C1=1，否则C1=0。 第二位：若端点位于窗口之右侧，即x>wxr，则C2=1，否则C2=0。 第三位：若端点位于窗口之下侧，即y<wyb，则C3=1，否则C3=0。 第四位：若端点位于窗口之上侧，即y>wyt，则C4=1，否则C4=0。
中点分割算法-求线段与窗口的交点

ห้องสมุดไป่ตู้
从P0出发找距离P0最近可见点采用中点分割方法 先求出P0P1的中点Pm, 若P0Pm不是显然不可见的，并且P0P1在窗口中有可见 部分，则距P0最近的可见点一定落在P0Pm上，所以用 P0Pm代替P0P1； 否则取PmP1代替P0P1。 再对新的P0P1求中点Pm。重复上述过程，直到PmP1长 度小于给定的控制常数为止，此时Pm收敛于交点。 从P1出发找距离P1最近可见点采用上面类似方法。
写成方程为：
xv S x xw vxl wxl S x yv S y yw v yb wyb S y
则窗视变换的展开式为：
xv a x w b yv c y w d
（5-12）
点的裁剪


图形裁剪中最基本的问题。 假设窗口的左下角坐标为 (xL,yB),右上角坐标为 (xR,yT)，对于给定点P(x,y), 则P点在窗口内的条件是要满 足下列不等式： xL <= x <= xR 并且yB <= y <= yT 否则，P点就在窗口外。
y k ( x x1 ) y1
其中
k ( y 2 y1 ) /( x2 x1 )
（5-13）
与窗口上边界（y＝wyt）或下边界（y＝wyb）交 点的x坐标的计算公式为：
y y1 x x1 k
（5-14）
其中
k ( y2 y1 ) /( x2 x1 )
5.6中点分割直线段裁剪算法
5.7 梁友栋-BARSKY算法

设要裁剪的线段是P0P1。 P0P1 和窗口边界交于A,B,C,D四点， 见图。算法的基本思想是从 A,B和P0三点中找出最靠近P1的 点，图中要找的点是P0。从C,D 和P1中找出最靠近P0的点。图 中要找的点是C点。那么P0C就 是P0P1线段上的可见部分。
5-21三个窗口
5-22 三个视区
图形输出需要进行从窗口到视区的变换，只有窗口 内的图形才能在视区中输出，并且输出的形状要根据视 区的大小进行调整，这称为窗视变换（Window Viewport Transformation，WVT）。在二维图形观察中， 可以这样理解，窗口相当于一个一扇窗户，窗口内的图 形是希望看到的，就在视区中输出，窗口外的图形不希 望看到，不在视区中输出，因此需要对窗口中输出的二 维图形进行裁剪。
用来标识直线端点相对于窗口边界及其延长线的 位置。假设窗口是标准矩形，由上（y=wyt）、下 （y=wyb）、左（x=wxl）、右（x=wxr）四条边组成， 如图5-24所示。延长窗口四条边形成9个区域，如
图5-25所示。这样根据直线的任一端点P(x，y)所
处的窗口区域位置，可以赋予一组4位二进制区域
1 0 vxl
1 0 wxl
0 1 v yb
0 0 1
0 S x 0 0 1 0 0 Sy 0 0 1 0 0 1 vxl 0 1 v yb 0 0 1
因此，窗视变换矩阵为：
形变换到视区输出。直线的裁剪是二维图形
裁剪的基础，裁剪的实质是判断直线是否与 窗口相交，如相交则进一步确定位于窗口内 的部分。
5.5.1 编码原理
Cohen-Sutherland直线裁剪算法是最早流行 的编码算法。每条直线的端点都被赋予一组四位
二进制代码，称为区域编码(Region Code，RC)，
P0 A
Pm B P1
5.6.2 中点计算公式 对于端点坐标为P0（x0，y0)，P1（x1，y1） 的直线段，中点坐标的计算公式为：
x ( x0 x1 ) / 2
y ( y0 y1 ) / 2
（5-15）


对分辩率为2N*2N的显示器，上述二分过 程至多进行N次。 主要过程只用到加法和除法运算，适合 硬件实现，它可以用左右移位来代替乘 除法，这样就大大加快了速度。
Computer Graphics
第五章 二维变换和裁剪(2)
本章内容-2
5.4 5.5 5.6 5.7 二维图形裁剪 Cohen-Sutherland直线裁剪算法 中点分割直线段裁剪算法 梁友栋－Barsky直线段裁剪算法
5.4 二维图形裁剪
5.4.1 5.4.2 5.4.3 5.4.4 图形学中常用的坐标系 窗口和视区及窗视变换 窗视变换矩阵 点的裁剪
y
z
O
x
O x
y
5-17
二维和三维用户坐标系
2.观察坐标系(View Coordinate ，VC)
依据观察窗口的方向和形状在用户坐标系中 定义的坐标系称为观察坐标系，观察坐标系用 于指定图形的哪一部分可以输出范围。
y
y
x
O
x
5-18 观察坐标系
3.设备坐标系
(Device Coordinate ，DC)
显示器等图形输出设备自身都有一个坐标系 称为设备坐标系，也称为屏幕坐标系。设备坐标 系是二维坐标系，原点位于屏幕左上角，x轴垂 直向右，y轴垂直向下，基本单位为像素。
1
x O
O
y
1
5-19 设备坐标系
5-20 规格化设备坐标系
4.规格化设备坐标系 (Normalized Device Coordinate ，NDC)
5.4.1 图形学中常用的坐标系
计算机图形学中常用的坐标系有 用户坐标系、观察坐标系、设备坐标 系和规格化设备坐标系等。
1.用户坐标系（User Coordinate ，UC)
用户定义原始图形所采用的坐标系称为用户 坐标系。用户坐标系通常根据应用的需要可以选 择直角坐标系、圆柱坐标系、球坐标系以及极坐 标系等等。图5-17所示为常用的二维和三维用户 直角坐标系。
0 1 wyb T T平移 T比例 T反平移
代入，Sx和Sy的值，窗视变换矩阵为：
[ xv
yv 1] [ xw
yw
Sx 0 0 1] 0 Sy 0 vxl wxl S x v yb wyb S y 1
vxr vxl a S x w w xr xl b vxl wxl a 令 v v c S y yt yb wyt wyb d v yb wyb c
5.6.1 中点分割算法原理 5.6.2 中点计算公式
5.6.1 中点分割算法原理 Cohen-Sutherland裁剪算法提出对直 线段端点进行编码，并把直线段与窗口的关 系划分为三种情况，对前两种情况进行了 “简取”和“简弃”的简单处理。对于第三 种情况，需要根据公式（5-13）和（5-14） 计算直线段与窗口边界的交点。中点分割算 法对第三种情况做了改进，不需要求解直线 段与窗口边界的交点就可以对直线段进行裁 剪。
如何判定应该与窗口的哪条边求交？ 编码中对应位为1的边。
1001 1000 1010 P1 0001 0000 0010 P3 P4 0101 0100 0110 P2
编码
线段裁剪
5.5.3 交点计算公式
对于端点坐标为P1（x1，y1)和P2（x2，y2）的直 线，与窗口左边界（x＝wxl）或右边界（x＝wxr） 交点的y坐标的计算公式为：
5.4.2 窗口和视区及窗视变换
在观察坐标系中定义的确定显示内容的 区域称为窗口。显然此时窗口内的图形是用 户希望在屏幕上输出的，窗口是裁剪图形的 标准参照物。 在设备坐标系中定义的输出图形的区域 称为视区。视区和窗口的大小可以不相同。 一般情况下，用户把窗口内感兴趣的图形输 出到屏幕上相应的视区内。在屏幕上可以定 义多个视区，用来同时显示不同的窗口内的 图形信息，图5-21定义了三个窗口内容用于 输出，图5-22的屏幕被划分为三个视区，对 三个窗口内容进行了重组。