计算机图形学chp5-Cut

计算机图形学吴伟计算机学院E-mail:wuwei_imu@163.com2第5讲二维观察5.1观察流程5.2窗口到视口的变换5.3直线段裁剪直接求交算法；Cohen-Sutherland算法；中点算法

Nicholl-Lee-Nicholl算法5.4多边形裁剪

Sutlerland_Hodgman算法5.5文字裁剪计算机图形学课程ComputerGraphicsCourse3第5讲要求掌握二维图形的显示流程图，窗口到视区的变换掌握什么是裁剪、裁剪窗口，裁剪算法的基本内容；掌握裁剪直线段的Cohen-Sutherland算法、中点分割算法；了解裁剪直线段的Nicholl-Lee-Nicholl算法掌握裁剪多边形的Sutherland-Hodgman算法（又称逐边裁剪算法）；掌握如何裁剪一个字符串，如何裁剪一个点阵表示（或矢量表示）的字符第5讲二维裁剪4

二维图形的显示流程图（1/4）坐标系：建立了图形与数之间的对应联系世界坐标系(worldcoordinate)用户坐标系(usercoordinate)局部坐标系(localcoordinate)

5

二维图形的显示流程图（2/4)屏幕坐标系(screencoordinate)设备坐标系(devicecoordinate)

6

二维图形的显示流程图（3/4）窗口在世界坐标系中指定的矩形区域用来指定要显示的图形

视区在设备坐标系（屏幕或绘图纸）上指定的矩形区域用来指定窗口内的图形在屏幕上显示的大小及位置

窗口到视区的变换

7

二维图形的显示流程图（4/4）8

窗口到视区的变换（1/2）目标将窗口之中的图形变换到视区中变换的求法变换的分解与合成9

窗口到视区的变换（2/2）105.3直线段裁剪(1/18)裁剪的目的判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交假定条件矩形裁剪窗口：

[xmin,xmax]X[ymin,ymax]待裁剪线段：第5讲二维裁剪115.3直线段裁剪(2/18)待裁剪线段和窗口的关系线段完全可见显然不可见线段至少有一端点在窗口之外，但非显然不可见

为提高效率，算法设计时应考虑：(一）快速判断情形(1)(2)；(二)设法减少情形(3)求交次数和每次求交时所需的计算量。第3节直线段裁剪125.3直线段裁剪(3/18)点裁剪点(x,y)在窗口内的充分必要条件是：

第3节直线段裁剪135.3直接求交算法直线与窗口边都写成参数形式，求参数值。第3节直线段裁剪145.3Cohen-Sutherland算法(编码算法)

算法步骤：第一步判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；第二步判别线段是否为显然不可见，如果是，则裁剪结束；否则进行第三步；第三步求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束裁剪过程是递归的第3节直线段裁剪155.3Cohen-SutherLand算法(编码算法)特点：对显然不可见线段的快速判别编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码， CtCbCrCl，上下右左；第3节直线段裁剪165.3Cohen-SutherLand算法(编码算法)端点编码：定义为它所在区域的编码结论：当线段的两个端点的编码的逻辑“与”非零时，线段为显然不可见的

第3节直线段裁剪17求交测试顺序固定(左上右下）最坏情形，线段求交四次。5.3Cohen-SutherLand算法(编码算法)对于那些非完全可见、又非显然不可见的线段，需要求交（如，线段AD)，求交前先测试与窗口哪条边所在直线有交？(按序判断端点编码中各位的值ClCtCrCb）

1）特点：用编码方法可快速判断线段--

完全可见和显然不可见。

2）特别适用二种场合：大窗口场合；窗口特别小的场合(如,光标拾取图形时,

光标看作小的裁剪窗口。）第3节直线段裁剪185.3Cohen-SutherLand算法第3节直线段裁剪195.3

中点分割法想法：从P0点出发找出距P0最近的可见点，从P1点出发找出距P1最近的可见点。取中点Pm=(P1+P0)/2。第3节直线段裁剪对分辩率为2N*2N的显示器，上述二分过程至多进行N次。主要过程只用到加法和除法运算，适合硬件实现。适合平行计算。205.3Nicholl-Lee-Nicholl算法(1/4)消除C-S算法中多次求交的情况。基本想法：对2D平面的更细的划分。第3节直线段裁剪215.3Nicholl-Lee-Nicholl算法(2/4)假定待裁剪线段P0P1为非完全可见且非显然不可见。步骤：第一步，窗口四边所在的直线将二维平面划分成9个区域，假定落在区域0、4、5第3节直线段裁剪225.3Nicholl-Lee-Nicholl算法(3/4)第二步：从P0点向窗口的四个角点发出射线，这四条射线和窗口的四条边所在的直线一起将二维平面划分为更多的小区域。此时P1的位置决定了P0P1和窗口边的相交关系。第3节直线段裁剪235.3Nicholl-Lee-Nicholl算法(4/4)第三步，确定P1所在的区域（判断P1所在区域位置，可判定P0、P1与窗口那条边求交)。 根据窗口四边的坐标值及P0P1和各射线的斜率可确定P1所在的区域。第四步，求交点，确定P0P1的可见部分。特点：效率较高，但仅适合二维矩形窗口。第3节直线段裁剪24梁友栋－Barsky算法梁-Barsky算法的几何含义：入边、出边与端点25梁友栋－Barsky算法

*

写入图形学教科书的唯一中国人的算法*CommunicationofACM的论文梁有栋教授的二三事Liang-Barsky算法几何连续理论从几何学与纤维缠绕理论到基因工程26梁友栋－Barsky算法参数化形式写出裁剪条件：可以统一表示为形式：

入边出边27梁友栋－Barsky算法

=0且<0，则线段完全在边界外，≥0，则该线段平行于裁剪边界并且在窗口内。28梁友栋－Barsky算法当≠0，当<0,线段从裁剪边界延长线的外部延伸到内部。当>0,线段从裁剪边界延长线的内部延伸到外部。29梁友栋－Barsky算法对于每条直线，可以计算出参数u1和u2，它们定义了在裁剪矩形内的线段部分u1的值由线段从外到内遇到的矩形边界所决定（p<0）。对这些边界计算rk=qk/pk

。u1取0和各个rk值之中的最大值。u2的值由线段从内到外遇到的矩形边界所决定（p>0）。对这些边界计算rk=qk/pk

。u2取1和各个rk值之中的最小值。30梁友栋－Barsky算法如果u1>u2，则线段完全落在裁剪窗口之外，被舍弃。否则裁剪线段由参数u的两个值u1,u2计算出来。31梁友栋－Barsky算法voidLB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)floatx1,y1,x2,y2,XL,XR,YB,YT;{ floatdx,dy,u1,u2; u1=0;u2=1; dx=x2-x1;dy=y2-y1;if(ClipT(-dx,x1-Xl,&u1,&u2)if(ClipT(dx,XR-x1,&u1,&u2)if(ClipT(-dy,y1-YB,&u1,&u2)if(ClipT(dy,YT-y1,&u1,&u2){ displayline(x1+u1*dx,y1+u1*dy, x1+u2*dx,y1+u2*dy) return; }}32梁友栋－Barsky算法boolClipT(p,q,u1,u2)floatp,q,*u1,*u2;{floatr;if(p<0){ r=q/p; if(r>*u2)returnFALSE; elseif(r>*u1) { *u1=r; returnTRUE; }}

。。。//下页33梁友栋－Barsky算法elseif(p>0){ r=p/q; if(r<*u1)returnFALSE; elseif(r<*u2){ *u2=r;returnTRUE;}}elseif(q<0)returnFALSE;returnTRUE;}34梁友栋－Barsky算法对三种算法比较:Cohen-Sutherland与中点法在区域码测试阶段能以位运算方式高效率地进行，因而当大多数线段能够简单的取舍时，效率较好。梁友栋—Barskey算法只能应用于矩形窗口的情形，但其效率比前两者要高，这是因为运算只涉及到参数，仅到必要时才进行坐标计算。355.4多边形裁剪(1/6)错觉：直线段裁剪的组合？新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？第5讲二维裁剪365.4多边形裁剪（2/6）2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？第4节多边形裁剪37Sutherland-Hodgman算法（3/6）分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程(左上右下)：左边的结果是上边的开始。亦称逐边裁剪算法第4节多边形裁剪38Sutherland-Hodgman算法（4/6）内侧空间与外侧空间多边形的边与半空间的关系第4节多边形裁剪输出P输出i无输出输出i，P39Sutherland-Hodgman算法(主要流程)第4节多边形裁剪40Sutherland-Hodgman算法(6/6)裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点。顺序连接。几点说明：裁剪算法采用流水线方式，适合硬件实现。可推广到任意凸多边形裁剪窗口第4节多边形裁剪415.4Weiler-Athenton算法裁剪窗口为任意多边形（凸、凹、带内环）的情况：主多边形：被裁剪多边形，记为A裁剪多边形：裁剪窗口，记为B第4节多边形裁剪42主多边形和裁剪多边形把二维平面分成两部分。内裁剪：A∩B外裁剪：A-BWeiler-Athenton算法（1/5）裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界

第4节多边形裁剪43Weiler-Athenton算法（2/5）如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：进点：主多边形边界由此进入裁剪多边形内

如I1,I3,I5,I7,I9,I11出点：主多边形边界由此离开裁剪多边形区域.如I0,I2,I4,I6,I8,I10

第4节多边形裁剪44Weiler-Athenton算（3/5）1）建顶点表；2）求交点；3）裁剪……Weiler_Athenton裁剪算法（内裁剪）步骤：1、建立主多边形和裁剪多边形的顶点表．2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针。3、裁剪如果存在没有被跟踪过的交点，执行以下步骤：

(1)建立裁剪结果多边形的顶点表．

(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．

(3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界．

(4)跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点．

(5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟