《计算机图形学》课件第四章a

第四章二维图形变换与二维观察

4.1几何变换的基本原理4.2基本变换4.3二维组合变换4.4变换模式4.5二维观察

4.1几何变换的基本原理

在图形的几何变换中，有时图形变化了，但原图形的构成规则（拓扑关系）没有改变，而图形发生的变化是由其顶点位置（几何关系）的改变决定的。这种通过保持图形的拓扑关系不变，而仅改变图形的几何关系来实现改变图形的方法，我们称之为图形的几何变换。既然图形的几何变换仅和点的位置变化有关，那么我们首先要讨论一个点在空间的位置及其变化。点可以用一个列向量来表示，要改变一个点的位置，就意味着要改变这个向量（大小及方向）。

对向量的运算通常用矩阵运算来实现。假如原顶点坐标为［x，y］Τ，经变换后的坐标为［x*，y*］Τ，那么用矩阵表示的变换过程为：（4.1）这是一个线性变换，其中的T为线性变换矩阵，它是二阶方阵。一个二维线性变换的一般形式也可以写成如下的代数式：（4.2）将其转换为矩阵形式，就得到（4.3）上面一个线性变换的矩阵形式和代数形式要统一，就必须对点向量的表示法稍作修改，即：（4.4）变换的矩阵形式和代数形式是完全可以统一的，只是原来用二维向量表示的点要变成用三维向量来表示，但其第三维是常数1。其几何意义为：［x，y］Τ代表z=0平面

上的点，［x，y，1］Τ代表z=1平面上的点。两种表示方法，仅从图形上来看是没有实质性差别的，如图4.1所示。图4.1在不同高度水平面上绘的图这样就用三维的形式表示了一个二维向量，进一步推广来说，用一个n+1维的形式来表示n维向量的方法，我们将它叫做齐次坐标表示法。这种小的改变，给图形变换的矩阵实现创造了条件。

采用了齐次坐标表示法以后，我们可以把二维的线性变换表示成如下规格化的形式：（4.5）三阶方阵T称为二维线性变换矩阵。于是，对于任何二维图形的顶点进行几何变换，均可以写成如下形式：

P*=T·P其中，P*为变换后的新顶点，P为变换前的顶点。矩阵T中元素取值的不同会导致对顶点的不同变换。连接新的顶点，从而构成新的图形（几何变换过程）。4.2基本变换

二维图形变换是指对平面图形作平移、旋转、缩放、错切、对称等操作，使原图形的几何位置、尺寸和形状得到所需要的变换，点的变换是图形变换的基础。

二维变换可分为四种基本类型：

（1）刚体变换，例如平移和旋转，这种变换保持变换前后图形中线段的长度和线段间的夹角不变。

（2）保角变换，例如平移、旋转和等比例缩放，它只保持变换前后线段间的夹角不变。

（3）仿射变换，例如平移、旋转、缩放、错切和对称。它能保持线段变换前后的平行关系，将直线段仍然映射成直线段，但不会发生扭曲现象。

（4）广义线性变换，它仅仅保持直线段变换前后的线性映射关系。

在此假设一切变换运算都在符合右手规则的笛卡尔坐标系中进行，在构造复合变换矩阵时，矩阵使用左乘运算规则，即每个随后的变换矩阵左乘前面的变换矩阵积。4.2.1平移

二维平移是指将物体沿直线路径从一个坐标位置移到另一个坐标位置的重定位，即通过给原坐标加上平移距离来平移二维点以实现到新位置的移动（图4.2）。图4.2平移变换若点(x*，y*)是由点(x，y)在x和y轴方向分别移动距离

tx和ty得到的，其变换结果为：(4.6)4.2.2旋转

二维旋转是指将物体沿xy平面内的圆弧路径重定位。为了实现旋转，需要指定旋转角θ和物体旋转的旋转点(或基准点，Pivotpoint)位置(xr，yr)。规定逆时针旋转时，

θ为正值，顺时针旋转时，θ为负值。当基准点为坐标原点时，如图4.3所示，由于(4.7)由此得到旋转变换矩阵：(4.8)其变换结果为：(4.9)平移和旋转都是物体的刚体运动，因此，对物体做平移和旋转变换时，物体上的每个点移动的距离相同或旋转的角度相同。图4.3旋转变换4.2.3缩放

缩放变换是一种改变物体尺寸的变换。为了实现缩放，需要指定缩放系数sx，sy和缩放变换的参考点（固定点）(xf，yf)。其变换矩阵为:(4.10)当参考点为坐标原点时，相应的变换公式是

x*=sx·x，y*=sy·y(4.11)

可以看到sx为x方向上的缩放因子，sy为y方向上的缩放因子，它们分别影响两个方向上的缩放效果（图4.4）。这些效果包括：

·sx=sy>1：图形沿x、y两个方向等比例放大。

·0<sx=sy<1：图形沿两个方向等比例缩小。

·sx≠sy：由于图形在两个方向上的缩放系数不相等，所以经过变换后的图形将产生畸变。若缩放中心为坐标系原点，也能对图形产生拉伸和压缩的几何效果。4.2.4对称

对称是产生物体镜像的一种变换，由对称轴、对称点或者对称平面所决定。对于二维图形，相对于对称点的对称是通过将物体绕对称点旋转180°而生成；对于对称轴的

对称则是通过将物体绕对称轴旋转180°而生成。对称点可以是平面内任一点，对称轴亦可以是平面内任一条直线。以下是一些常用的对称变换:

(1)关于x轴的对称变换，其变换公式(4.12)(2)关于y轴的对称变换，其变换公式是(4.13)

(3)关于45°线的对称变换，其变换公式是(4.14)(4)关于－45°线的对称变换，其变换公式是(4.15)以上四种变换的效果如图4.5所示。图4.5对称变换

(5)关于坐标原点的对称变换，其变换公式是(4.16)4.2.5错切

错切是一种使物体形状发生变化的变换。常用的错切变换有两种：沿x轴方向的错切和沿y轴方向的错切。

沿x轴方向的错切变换公式是（4.17）即x*=x+r12y，y*=y。从以上结果可以看到：新图形各顶点的y坐标没有变，而x坐标是在原有的值上加一个和y成正比例函数值的增量，所以使得整个图形在等高的前提下发生了倾斜。该变换的几何解释是将物体沿x方向做了角度α=tg－1(r12)的滑动，其参考线为x轴。

当r12>0时，图形沿x正向错切；当r12<0时，图形沿x

负向错切，如图4.6所示。图4.6错切变换沿y轴方向的错切变换公式是（4.18）即x*=x，y*=y+r21x。4.3二维组合变换

4.3.1对任意直线的对称变换

前面介绍过五种对称变换，但其对称轴都是特殊位置的直线。对于对称轴是任意位置直线的对称变换，以上的对称变换矩阵不能直接应用。图4.7关于任意直线的对称变换（1）让直线沿x轴方向平移C／A，使其通过坐标系原点。变换矩阵为：(4.19)（2）让直线绕坐标系原点旋转－α角，使其与x轴重合。变换矩阵为：(4.20)（3）由于原直线已与x轴重合，于是对于直线的对称变换即为对x轴的对称变换。变换矩阵为：(4.21)（4）绕原点旋转α角，使直线恢复到原倾斜位置。变换矩阵为：(4.22)（5）让直线沿x轴方向平移－C/A，使其回到原来位置。变换矩阵为：(4.23)综合以上的五步，对任意直线的对称变换过程为：(4.24)其组合变换矩阵为：(4.25)4.3.2绕任意点的旋转变换

绕坐标原点以外的任意点p(x，y)的旋转如图4.8所示。前面介绍的旋转是以坐标系原点为旋转中心的，现在的旋转中心p不在原点，所以不能简单地套用上面的旋转变换矩阵，我们可以通过以下几个基本变换来完成。图4.8绕任意点的旋转变换（1）将指定的任意旋转中心点p平移到坐标系原点，以使原来的绕任意点旋转转化为绕坐标系原点的旋转。其变换矩阵为：(4.26)（2）使图形绕坐标系原点旋转θ角，其变换矩阵为：(4.27)（3）复原。使旋转中心从坐标系原点平移到原来的位置(x，y)，变换矩阵为：(4.2８)所以，绕任意点p(x，y)的旋转过程为：(4.29)其组合变换矩阵为：(4.30)4.3.3组合变换矩阵

从上述两个例子的求解过程可以看到，对于一般条件下的图形变换，解决问题的思路可以分为三步：

Step1分析变换的性质；

Step2分解改变成可用基本变换实现；

Step3恢复原状态。于是利用变换的矩阵表示，就可以通过计算单个变换的矩阵乘积，将任意顺序变换的矩阵合并为复合变换矩阵。作用于点p的两个连续平移(tx1，ty1)和(tx2，ty2)产生的复合变换矩阵为：

T(tx2，ty2)·T(tx1，ty1)=T(tx1+tx2，ty1+ty2)

(4.31)

两个连续旋转θ1、θ2产生的复合变换矩阵是：

R(θ2)·R(θ1)=R(θ1+θ2)

(4.32)两个连续缩放变换产生的复合变换矩阵是：

S(sx2，sy2)·S(sx1，sy1)=S(sx1·sx2，sy1·sy2)

(4.33)

若以通用基准点为中心进行旋转，则可通过完成“平移→旋转→平移”操作序列来实现绕任意选择的基准点(xr，yr)的旋转：

（1）平移物体使基准点移至坐标原点。

（2）绕坐标原点旋转。

（3）平移物体使基准点回到其原始位置。相应的复合变换矩阵是：

T(xr，yr)·R(θ)·T(－xr，－yr)=R(xr，yr，θ)（4.34）

生成关于所选固定点(xf，yf)缩放的变换顺序如下：

（1）平移物体使固定点移至坐标原点。

（2）关于坐标原点缩放。

（3）平移物体使固定点回到其原始位置。

相应的复合变换为：

T(xf，yf)·S(sx，sy)·T(－xf，－yf)

=S(xf，yf，sx，sy)（4.35）其相应的缩放变换公式是：（4.36）若要求物体沿任意方向进行缩放，那么在进行缩放变换前，应先将物体进行旋转，使其所希望的缩放方向与坐标轴一致。然后应用缩放变换，最后进行反向旋转使物体回到原始位置。由此得到的复合变换矩阵是：(4.37)由以上的讨论可知，表示平移、旋转、对称和错切组合的通用二维图形变换可表示为：（4.38）尽管形式上矩阵方程（4.38）需要九次乘法和六次加法，然而，矩阵最后一行的固定结构将实际运算简化为：（4.39）因此，实际变换坐标的计算仅需四次乘法和四次加法。这种比较明显的简化在当这个运算被应用到每张图形上数以千计甚至数以万计的点上时，效果更明显。所以，尽管3×3矩阵对组合二维变换很方便也很有用，但是通过利用最终矩阵的特殊结构我们能够在程序中有效地利用它。一些硬件矩阵乘法器具有并行的加法器和乘法器，从而能减少或消除了这个问题。4.3.4级联顺序对组合变换的影响

由于矩阵的乘法运算不适用于交换律，即两个矩阵的左乘和右乘其结果是不相等的。所以在矩阵的乘法中，由于先后次序不同，得到的结果也是不同的。也就是说，用基本变换的级联来实现图形的组合变换时，矩阵级联的顺序不同导致得到的最终结果图形也不同。下面我们举例说明矩阵级联的顺序对变换结果图形的影响。给定一平移变换和一旋转变换：

（4.40）先进行平移变换，然后再进行旋转变换，则最后的结果为：（4.41）反过来，若先进行旋转变换，然后再进行平移变换，则最后的结果为：（4.42）从以上两个过程可以看出：两个结果矩阵是明显不同的。因此，在进行组合变换时，要特别注意不能搞错基本变换的次序。这其实引出了图形学中图形变换的变换模式问题。

4.4变换模式

先调用的变换先执行，后调用的后执行。体现在级联矩阵中，先调用的变换矩阵乘在右边，后调用的变换矩阵乘在左边（图4.9），这种方式称为图形模式或固定坐标系模式。它的特点是在连续执行几次变换时，每一次变换均可以看成相对于原始坐标系来执行。图4.9图形模式另一种模式称为空间模式或活动坐标系模式。在这种变换模式下，连续执行多次变换时，变换矩阵的合并方式恰好与图形模式相反，即后进行的变换矩阵要乘在右边，先进行的变换矩阵则乘在左边。它的特点是每一次变换均可以看成是在前一次变换所形成的新坐标系中进行的（图

4.10）。图4.10空间模式

4.5二维观察

4.5.1观察流程

一般地，二维图形的观察流程如图4.11所示。图4.11两维观察变换流程4.5.2观察坐标系

观察坐标系能为世界坐标系窗口提供参考系。为了建立观察坐标系，需在世界坐标系中指定观察坐标系的坐标原点p0=(x0，y0)和观察坐标系yv轴方向向量V=(vx，vy)。(4.43)4.5.3视窗变换

所谓窗口到视区的变换就是将给定窗口中的图形显示在屏幕上的视区中。因此，我们需要进行坐标变换，如图4.12所示。图4.12视窗变换示意图（1）做平移变换，使窗口左下角位于坐标原点。相应的坐标变换矩阵是：(4.44)（2）做缩放变换，使窗口的尺寸与视区一致。相应的变换如下：(4.45)（3）平移变换设置视区的位置，对应的变换矩阵为：(4.46)经过上述三步，可得到窗口到视区的变换矩阵：

T=T3·T2·T1

(4.47)

如果T2中的缩放因子相同，物体就会保持相似性。否则，世界坐标系中的物体在输出设备上显示时将在x方向或y方向拉伸或压缩。4.5.4裁剪操作

基本的图形裁剪算法有：

·点的裁剪

·直线段的裁剪

·多边形的裁剪

·曲线的裁剪

·字符的裁剪直线和多边形的裁剪是图形软件包中的标准部分。许多软件包中还有曲线、拟合曲线、圆锥曲线的裁剪。另外，处理曲线物体的方法是把它们近似为直线段，然后用直线或多边形的裁剪算法进行裁剪。4.5.5点的裁剪

设裁剪窗口是一个由参数xL、

xR、yB和yT所确定的矩形。如果点P=(x，y)满足下列不等式：

xL≤x≤xR，yB≤y≤yT

(4.48)

则保存该点用于显示。如果这四个不等式中有任何一个不满足，则裁剪该点。4.5.6直线段的裁剪

直线段的裁剪过程包括几个部分：首先测试一个给定的线段，判断它是否完全落在裁剪窗口内。如果没有完全落在窗口内，再判断是否完全落在窗口外。最后，对既不能确定完全落在窗口内又不能确定完全落在窗口外的线段，计算它与一个或多个裁剪边界的交点。图4.13给出了线段和标准矩形裁剪窗口之间的不同关系。图4.13用矩形窗口裁剪线段通常通过对线段的端点进行“内部→外部”测试来处理线段的裁剪问题。对于两个端点都在窗口内的线段(如图4.13中的P1P2)予以保存；两个端点都在同一条裁剪边界外的线段(如图4.13中的P3P4)判定其为落在窗口外；其他贯穿一个或多个裁剪边界的线段需要计算其多个交点。为了使计算量最小，需设计一个能有效地识别外部线段并减少求交运算的裁剪算法。对于端点为Pi=(xi，yi)，i=0，1的线段，其参数方程为：对该线段与裁剪边界求交时，可求得参数u值。若u[0，1］，则该线段不在该边界处进入窗口内，否则，线段穿过了裁剪区。该方法可用于各个裁剪边界，以确定是否该线段的所有部分都能显示。平行于窗口边界的线段需作为特殊情况处理。

1.Sutherland-Cohen算法

以裁剪窗口的四条边界将平面区域分为九个子区域，为每个子区域赋以相应的编码，称其为区域码（regioncode），每个子区域中的点采用同一编码。区域码的各位指出了点关于裁剪窗口的四个相对坐标位置：左、右、下、上。将区域码各位从右到左编号，则坐标区域与各位的

关系如下（图4.14）：位1—左；位2—右；位3—下；位4—上。对位置赋值1，代表点落在相应的位置上，赋0则代表点不在相应位置上。图4.14区域编码对于要裁剪的线段的两个端点，根据所在区域确定其相应的编码。各位的值按以下两步确定：

①计算端点坐标和裁剪边界之间的差值；

②用各差值的符号位来设置区域码中相应的值。

第一位为xL－x的符号位；第二位为x－xR的符号位；第三位为yB－y的符号位；第四位为y－yT的符号位。一旦确定了线段两端点的区域码，便可快速判断完全可见和完全不可见的线段。如果线段两端点的编码均为0000，则该线段完全可见；如果线段两端点的编码中同一位都为1，或线段两端点编码的逻辑与不为0000，则该线段完全不可见。如果上述判断没有定论，则需要进行线段与窗口边界的求交计算。按照左、右、下、上的顺序用裁剪边界检查线段的端点以确定应裁剪掉的线段部分。下面以图4.15中的线段为例说明Sutherland-Cohen算法的处理过程。图4.15线段P0P1的裁剪对于线段P0P1，由下端点P0开始，依次按左、右、下、上边界对P0进行检查。发现P0位于下边界的下方，然后求线段P0P1与下边界的交点P0′，并舍弃线段P0P0′。对于端点P1进行同样的检查，发现P1位于左边界的左侧，求线段P0P1与左边界的交点P1′。但因为P1′位于上边界之上，因此需再求一次交点，计算得到P1″，并舍弃线段P1P1″,该线段的裁剪则处理完毕。在与裁剪边界的求交计算中，直线段采用斜截式方程。对于端点坐标为Pi=(xi，yi)，i=0，1的直线，与垂直边界交点y的坐标由下述公式计算得到：(4.50)其中，x值为xL或xR。

寻找与水平边界交点的x坐标的计算公式是：(4.51)其中，y值为yB或yT。下面给出了Sutherland—Cohen直线段裁剪算法的程序，各端点的编码以字节存储，并按位操作处理。

#defineLEFT_EDGE0x1

#defineRIGHT_EDGE0x2

#defineBOTTOM_EDGE0x4

#defineTOP_EDGE0x8

#defineINSIDE(a)(!a)

#defineREJECT(a，b)(a&b)

#defineACCEPT(a，b)(!(a|b))

structwcPt2{/*世界坐标系中点的坐标*/

floatx;

floaty;

}

structdcPt{/*屏幕坐标系中点的坐标*/

intx;

inty;

}

unsignedCharencode(wcPt2pt，dcPtWinMax，dcPtWinMin)

{/*WinMin为窗口左下角坐标；WinMax为窗口右上角坐标*/

unsignedcharcode=0x00;

if(pt.x<WinMin.x)

code=code|LEFT_EDGE;

if(pt.x>WinMax.x)

code=code|RIGHT_EDGE;

if(pt.y<WinMin.y)

code=code|BOTTOM_EDGE;

if(pt.y>WinMax.y)

code=code|TOP_EDGE;

renturn(code);

}

voidSwapPts(wcPt2*p1，wcPt2*p2)/*点交换*/

{

wcPt2temp;

temp=*p1;*p1=*p2;*p2=temp;

}

voidSwapCodes(unsignedchar*c1，unsignedchar*c2)

/*编码交换*/

{

unsignedchartemp;

temp=*c1;*c1=*c2;*c2=temp;

}

voidClipLine(dcPtWinMin，dcPtWinMax，wcPt2p1，wcPt2p2)

{

unsingedcharcode1，code2;

intdone=FALSE;draw=FALSE;

floatm;

while(!done)

{

code1=encode(p1，WinMin，WinMax);

code2=encode(p2，WinMin，WinMax);

if(ACCEPT(code1，code2))

{

done=TRUE;

draw=TRUE;

}

else

if(REJECT(code1，code2))

done=TRUE;

else

{

if(INSIDE(code1))

{

SwapPts(&p1，&p2);

SwapPts(&c1，&c2);

}

if(p2.x!=p1.x)

m=(p2.y-p1.y)/(p2.x-p1.x);

if(code1&LEFT_EDGE)

{

p1.y+=(WinMin.x-p1.x)*m;

p1.x=WinMin.x;

}

else

if(code1&RIGHT_EDGE)

{

p1.y+=(WinMax.x-p1.x)*m;

p1.x=WinMax.x;

}

else

if(code1&BOTTOM_EDGE)

{

if(p2.x!=p1.x)

p1.x+=(WinMin.y-p1.y)/m;

p1.y=WinMin.y;

}

else

if(code1&TOP_EDGE)

{

if(p2.x!=p1.x)

p1.x+=(WinMax.y-p1.y)/m;

p1.y=WinMax.y;

}

}

}

if(draw)

linDDA(p1.x，p1.y，p2.x，p2.y);

}

2.中点分割裁剪算法

与Sutherland-Cohen算法一样，中点分割裁剪算法首先对线段端点进行编码，并据此把线段与窗口的关系分为三种情况：全在窗口内、完全不在窗口内和线段与窗口相交。对前两种情况作同样的处理，对于第三种情况，用中点分割的方法求出线段与窗口的交点，即从点P0出发找出距P0最近的可见点A，并从点P1出发找出距P1最近的可见点B，两个可见点之间的连线即为线段P0P1的可见部分，如图4.16所示。图4.16中点分割裁剪算法采用中点分割方法从P0出发找出最近可见点，先求出P0P1的中点Pm。若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，故用P0Pm代替P0P1，否则用PmP1代替P0P1。再对新的P0P1求中点Pm。重复上述过程，直到PmP1的长度小于给定的控制常数为止。求距P1最近的可见点过程一样，只要把P0和P1交换即可。由于该算法的主要计算过程只用到加法和除2运算，所以特别易于硬件实现，同时也适合于并行计算。求距P0最近的可见点的框图如图4.17所示。图4.17中点分割流程图

3.梁友栋-Barsky算法

该算法是基于线段的参数方程分析的，通过减少计算交点的次数，可使其运算速度比Sutherland-Cohen算法更快。

端点为Pi=(xi，yi)，i=0，1的线段，其参数方程为(4.52)其中Δx=(x1－x0)，Δy=(y1－y0)。直线段P0P1上点的裁剪条件是(4.53)这四个不等式可以表示为

uQi≤Di，i=L，R，B，T

(4.54)其中，Qi，Di定义如下(4.55)任何平行于裁剪边界的直线都满足条件Qi=0，若还满足Di<0，则线段完全在边界外，应舍弃该线段；Di≥0，则线段平行于裁剪边界并在窗口内，需用另外一组边界进行检查。当Qi<0时，表明线段从裁剪边界i的延长线外部延伸到内部；当Qi>0时，表明线段从裁剪边界i的延长线内部延伸到外部。这里说的外部是指沿裁剪边界逆时针行走时，右手所在的一侧，左手侧则被称为内部。线段与边界i的延长线的交点参数为(4.56)对于每条线段，都可计算出参数u0、u1，它们定义了窗口内部线段的部分。u0的值由线段从外到内遇到的边

界（Qi<0）所决定，对于这些边界，计算ri=Di/Qi，则u0=max{0，ri}。

u1的值由线段从内到外遇到的边界(Qi>0)

所决定，计算相应的ri=Di/Qi，则u1=min{1，ri}。若u0>u1，则线段完全落在裁剪窗口之外，应将其舍弃；若u0≤u1,则线段可见部分的两端点可由参数u0、u1计算得到。梁友栋－Barsky算法可用下面的程序来描述。线段与边界交点的参数可初始化为u0=0，u1=1。计算出各个裁剪边界的Q、D值，函数ClipTest通过Q、D来判断是否舍弃线段还是改变交点的参数。当Q<0时，参数r用于更新u0；

当Q>0时，参数r用于更新u1；当Q=0且D<0时，应舍弃该线段。Q、D的四个值经过测试后，该线段未被舍弃，则裁剪线段的端点由参数u0、u1的值决定。

intClipTest(floatq，floatd，float*u0，float*u1)

{

floatr;

intretVal=TRUE;

if(q<0.0)

{r=d/q;

if(r>*u1)

retVal=FALSE;

elseif(r>*u0)

*u0=r;

}

elseif(q>0.0)

{r=d/q;

if(r<*u0)

retVal=FALSE;

elseif(r<*u1)

*u1=r;

}

elseif(d<0.0)

retVal=FALSE;

return(retVal);

}

voidClipLine(dcPtWinMin，dcPtWinMax，wcPt2p0，wcPt2p1)

{floatu0=0.0，u1=1.0，dx=p1.x-p0.x，dy;

if(ClipTest(-dx，p0.x-WinMin.x，&u0，&u1)

if(ClipTest(dx，WinMax.x-p0.x，&u0，&u1))

{dy=p1.y-p0.y;

if(ClipTest(-dy，p0.y-WinMin.y，&u0，&u1))

if(clipTest(dy，WinMax.y-p0.y，&u0，&u1))

{if(u1<1.0)

{p1.x=p0.x+u1*dx;

p1.y=p0.y+u1*dy;

}

if(u0>0.0)

{p0.x+=u0*dx;

p0.y+=u0*dy;

}

lineDDA(p0.x，p0.y，p1.x，p1.y)

}

}

}梁友栋-Barsky算法比Sutherland-Cohen算法更有效，因为它需要计算的交点数目比较少，且更新参数u0、u1仅仅需要一次除法。线段与窗口的交点仅需计算一次，就能

计算出u0、u1的最后值。相比之下，即使一条直线完全落在裁剪窗口之外，Sutherland-Cohen算法也要对它反复求交点，而且每次求交都需要进行乘除法运算。

4.Nicholl-Lee-Nicholl算法

Nicholl-Lee-Nicholl算法，简称为NLN算法，通过在裁剪窗口周围创建多个区域的方法来避免对一条直线段的多次裁剪。在Sutherland-Cohen算法中，在找到与裁剪边界的交点之前或完全舍弃该线段之前，必须对一条线段进行多次求交计算。而NLN算法在求交计算前能进行更多的区域测试来减少求交计算。与梁友栋-Barsky算法和Sutherland-Cohen算法相比，NLN算法的比较次数和除法次数都比较少，但NLN算法仅适用于二维直线段的裁剪，而梁友栋-Barsky算法和Sutherland-Cohen算法可以很方便地推广到三维裁剪。

NLN算法分两步执行：

（1）对于端点为P0、P1的线段，首先决定P0相对于裁剪窗口的九个区域的位置，这里我们仅考虑三个区域，如图4.18所示。对于其他六个区域，可利用对称变换将其变为这三个区域中的任何一个区域。图4.18

NLN裁剪算法中线段端点P0的三种位置（2）判断端点P1相对于P0的位置。根据P0的位置在平面上建立新的区域。新区域的边界是由P0发出的穿过窗口角点的射线，如图4.19所示。

如果P0位于窗口内，P1位于窗口外，我们设置四个裁剪区域：L、T、R和B，如图4.19(a)所示。根据P1点所在区域，决定直线段和窗口边界的求交计算。如果P0P1在窗口内，则为可见线段。图4.19

NLN算法的裁剪区域为了确定P1在哪个区域，需要比较该线段的斜率和裁剪区域边界的斜率。例如，如果P0在裁剪边界的左边（图4.19(b)），那么，P1∈LT的条件是或者若满足下列条件：则整个直线段不可见。4.5.7多边形的裁剪

1.Sutherland-Hodgeman算法

Sutherland-Hodgeman算法将多边形边界作为一个整体用窗口的每一条边界裁剪。通过依次按照裁剪窗口的各边界处理所有的多边形顶点来实现。在对多边形顶点集初始化后，首先用窗口左边界裁剪多边形，产生一新的顶点序列。新的顶点集依次传给窗口的右边界、下边界和上边界来处理。每一步产生的新的顶点序列可作为下一个窗口边界的输入顶点序列。沿着多边形依次处理顶点时会遇到四种情况。当相邻的一对多边形顶点被传到窗口的边界裁剪程序时，可做以下测试：①若第一点在窗口边界外而第二点在窗口边界内，则多边形的该边与窗口边界的交点和第二点都加入到输出顶点表中；②如果两点都在窗口边界内，则只将第

二点加入到输出顶点表中；③如果第一点在窗口边界内，而第二点在窗口边界外，则只有该边与窗口边界的交点加入到输出顶点表中；④如果两点都在窗口边界外，输出顶点表中不增加任何顶点。图4.20给出了多边形相邻两顶点的上述四种情况。图4.20按照窗口左边界连续处理多边形顶点时由此，可以将Sutherland-Hodgeman多边形裁剪算法总结如下：将裁剪窗口的四条边界分别设置为裁剪器，按照左、下、右、上的顺序用这些裁剪器依次处理多边形顶点序列。每一裁剪器产生的新的顶点序列作为下一裁剪器的输入顶点序列，最后得到的顶点序列即为裁剪后的多边形顶点序列。这一裁剪过程如图4.21所示。图4.21多边形裁剪流程图利用Sutherland-Hodgeman算法对凸多边形进行裁剪时可获得正确的裁剪结果，但是对凹多边形的裁剪将不能得到正确的结果，如图4.22所示，会显示出一条多余的线段。这种情况会在裁剪后的多边形有两个以上的分离部分时出现，因为只有一个输出顶点表，所以表中最后一个顶点总是与第一个顶点相连。为了正确地裁剪凹多边形，可利用以下几种方法，其一是将凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形；其二是修改Sutherland-Hodgeman算法，沿着任何一个裁剪窗口边界检查顶点表，正确地连接顶点对；第三种方法就是随后介绍的Weiler-Atherton算法。图4.22凹多边形的裁剪

2.凹多边形的判定与分解

在xy平面上判定和分解凹多边形的方法有两种。

（1）向量法。沿多边形的边界计算相邻边向量的叉乘可判定凹多边形。如果一些叉乘的z分量为正，另一些叉乘的z分量为负，则该多边形必为凹多边形，否则为凸多边形。如果所有叉乘为零，则可得到退化的多边形(一条直线)。逆时针方向计算边向量的叉乘并记录z分量的符号。如果z分量的值变为负值，则多边形为凹多边形，可以沿叉乘向量对中的第一边的延长线将多边形分解。例4.1说明了判定凹多边形的边向量的叉乘方法。例4.1分解凹多边形的向量法。图4.23为一有六条边的多边形，其边向量分别为：则Ei×Ej为因为(E2×E3)z=－2<0，我们沿E2的延长线分解多边形，求其和多边形的交点。这样一个多边形可分为两个。由于这两个子多边形边向量叉乘的z分量均为正，所以他

们都是凸多边形。图4.23用向量法分解凹多边形（2）旋转法。沿多边形逆时针前进，将多边形顶点Vk平移到坐标原点，然后顺时针旋转多边形，使下一顶

点Vk+1在x轴上。如果下一顶点Vk+2位于x轴下方，即Vk+2，y<0，则该多边形为凹多边形，沿x轴将多边形分解为两个子多边形。对两个子多边形重复进行凹多边形测试。否则，继续处理下一顶点直至所有顶点都测试完。图4.24说明了分解凹多边形的旋转法。图4.24用旋转法分解凹多边形

3.Weiler-Atherton算法

Weiler-Atherton算法是基于修改多边形边界顶点的处理过程，来获得凹多边形的正确裁剪。该方法开始是作为识别可见面的方法而提出的，因此可用于任意多边形窗口的裁剪。算法的基本思想是：有时沿着多边形边的方向来处理顶点；有时沿着窗口的边界方向处理顶点。采用哪一条路径，要根据多边形处理方向(