计算机图形学课件第4讲：图形裁剪算法

第6讲图形裁剪算法

图形裁剪计算机内部存储的图形数据量往往比较大，而屏幕显示的只是图的局部部分。因此需要确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形窗口：矩形2图形裁剪的策略先变换后裁剪将图形经过扫描转换后变成像素的集合，然后对图形中的每一个像素进行裁剪先裁剪后变换将原始图形进行裁剪，保留窗口内的可见部分，舍弃窗口外的不可见部分。然后对窗口内保留的这部分图形进行扫描转换先裁剪后变换！可以省去许多不必要的扫描转换的工作3图形裁剪的处理步骤图形裁剪的目的：判断图形元素是否在所考虑的区域内如在区域内，则进一步求出区域内的那一部分处理步骤：点在区域内外的判断计算图形元素与区域边界的交点4点的裁剪对于一点P(x,y)，要判断其是否可见

xmin≤x≤xmaxandymin≤y≤ymax

满足上述不等式组的点则在窗口范围内，则保留；反之，该点落在窗口外，应裁剪5xminymaxyminxmax直线的裁剪对于矩形窗口任何直线至多只有一段处于该窗口之内即在此窗口范围内永远不会产生一条直线的两条或更多的可见部分线段基本思想：判断直线与窗口的位置关系，确定该直线是完全可见、部分可见或完全不可见输出处于窗口内线段的端点，并显示此线段6直线的裁剪整条线在窗口之内不需剪裁，显示整条线段整条线在窗口之外不需剪裁，不显示整条线段部分线在窗口之内求出线段与窗口边界的交点将窗口外的线段部分剪裁掉显示窗口内的部分7直线裁剪的效率策略快速排除完全在窗口内完全在窗口外的直线若是部分在窗口内的情况减少直线与窗口边界的求交次数和每次的求交计算量8直线裁剪算法Cohen-Sutherland裁剪算法中点分割算法梁友栋-Barsky裁剪算法9基本思想：对于每条待裁剪的线段P1P2分三种情况处理若P1P2完全在窗口内，则显示该线段若P1P2完全在窗口外，则丢弃该线段若线段不满足上述条件则求线段与窗口边界的交点，在交点处把线段分为两段其中一段完全在窗口外，可舍弃之，然后对另一段重复上述处理10Cohen-Sutherland裁剪算法Cohen-Sutherland裁剪算法如何快速排除完全在窗口内完全在窗口外的直线编码9个区域4位编码CtCbCrCl按位运算11100110101000000000010100011000100101ymaxyminxmaxxmin延长窗口的四条边线(ymin,ymax,xmin,xmax)，将二维平面分成九个区域,区域赋予4位编码CtCbCrCl第一位为1：端点处于上边界的上方第二位为1：端点处于下边界的下方第三位为1：端点处于右边界的右方第四位为1：端点处于左边界的左方否则，相应位为012Cohen-Sutherland裁剪算法Cohen-Sutherland裁剪算法对线段的每个顶点，根据其所在区域赋予此编码if(x<XL)c|=0x0001; …一个在窗口内的顶点编码为000013100110101000000000010100011000100101Cohen-Sutherland裁剪算法先排除简单情形：若某线段两个端点的四位二进制编码全为0000线段位于窗口内，显示之若对两端点的四位二进制编码进行逻辑与运算（&）结果不为0线段位于窗口外，直接舍弃再裁剪递归执行14100110101000000000010100011000100101Cohen-Sutherland裁剪算法裁剪：若线段既不能直接保留，也不能直接舍弃它可能与窗口相交对线段进行再分割，并找到与窗口边线的一个交点，根据交点位置，赋予4位二进制编码，对分割后的线段舍弃一定在窗口外部分另一部分做进一步检查15100110101000000000010100011000100101例：如图，裁剪AB、CD、EF直线段。解：根据编码算法，各直线段的端点四位二进制编码如下：

A:0000B:0000A,B编码全为0，AB直接保留

C:0010D:0110C,D编码进行逻辑与运算，结果非0，CD直线段直接舍弃

E:0001F:0000E,F编码进行逻辑与运算，结果为0，此时应求EF与窗口边界的交点16ABCDEFCohen-Sutherland裁剪算法Cohen-Sutherland裁剪算法求交将两个端点的编码CtCbCrCl进行逻辑或操作，根据其结果中1的位置来确定可能相交的窗口边求交按照固定的顺序来进行（左右下上或上下右左）一条线段与窗口最多求交4次17A(1010)B(0101)DCEFCohen-Sutherland裁剪算法特点：简单，易实现依次裁剪在窗口外部分，直到直线完全处于窗口内快速判断线段的完全可见和显然不可见巧妙的编码方法18中点分割算法类似于Cohen-Sutherland算法将直线的两端点P1、P2编码得：C1、C2；根据C1和C2的具体值，可以有三种情况：C1＝C2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。C1&C2≠0，表明两端点全在窗口外同侧，整个线段全在窗外，应予舍弃。不属于上面两种情况，均需要求交点，并进行裁剪裁剪：裁剪一端，得到最近可见点求最近可见点（交点）：中点分割算法！19中点分割算法中点观察：中点将线段P1P2分为两部分，必定有一部分存在最近可见点（交点）保留存在最近可见点部分，舍弃另一部分20P1P2P中点分割算法当线段P1P2求出中点P后，舍弃线段的哪部分？若如果P1与P同侧，移动P1点；（即可能的交点只能出现在PP2段）

if((C1&C)!=0)P1=P;若P1与P不同侧，移动P2点。（即可能的交点只能出现在P1P段）

if((C1&C)==0)P2=P;21中点分割算法将中点分割进行到底!可收敛到最近可见点22中点分割算法求交点STEP1：令窗外端点为P1，如果窗外点不是P1，则P1和P2交换端点；STEP2：保留窗内端点P2到暂存器里；STEP3：对P1编码为C1；STEP4：用中点公式求出中点，并编码得C；STEP5：按照中点算法的求交规则：若P1和P同侧，移动P1点；if((C1&C)!=0)

P1=P;

否则，移动P2点。else

P2=P;GOTOSTEP3，直到P1和P2相差一个单位时：令交点为P2，对暂存器断点P2裁剪23中点分割算法特点：求交点的次数（n）与线段长度（L）有关，其关系为：L=2n。例如：线段长度为256，则求交点的次数为8。求出的交点是边界上的有效交点（最近可见点），而非边界及其延长线上的交点Cohen－Sutherland直线裁剪算法：边界上或者边界的延长线上的交点求中点：加法与除法，容易硬件实现24梁友栋-Barsky裁剪算法梁友栋生于1935年7月，福建福州人1956-1960年：复旦大学研究生，师从苏步青先生学习几何理论1960年研究生毕业后任教于浙江大学数学系1984-1990年任浙大数学系主任Liang,Y.D.,andBarsky,B.,"ANewConceptandMethodforLineClipping",ACMTransactionsonGraphics,3(1):1-22,January1984.25梁友栋-Barsky裁剪算法算法的基本思想：当要裁剪的线段是P0P1，P0P1和窗口边界交于A,B,C,D四点。从A,B和P0三点中找出最靠近的P1的点，从C,D和P1中找出最靠近P0的点。26yxyTyBxLxRABCDP1P0P0C是P0P1线段上的可见部分梁友栋-Barsky裁剪算法具体计算时，把P0P1写成其参数方程：

其中Δx=x1－x0，Δy=y1－y0窗口内线段应满足求u!27梁友栋-Barsky裁剪算法不等式可写作：即线段与裁剪边界的交点有28yxyTyBxLxRABCDP1P0梁友栋-Barsky裁剪算法窗口边界的四条边分成两类，一类称为始边，另一类称为终边当Δx≥0时，称x=xL为始边，x=xR为终边当Δx<0时，称x=xL为终边，x=xR为始边当Δy≥0时，称y=yB为始边，y=yT为终边当Δy<0时，称y=yB为终边，y=yT为始边29yxyTyBxLxRP1P0P0P1AB可知边界交点的参数：

当pi<0时，求得的ti必是P0P1和始边的交点的参数当pi>0时，ui必是P0P1和终边的交点的参数30梁友栋-Barsky裁剪算法求出P0P1和两条始边的交点的参数u0’和u0’’，令

u0=max(u0’，u0’’，0)则u0

就是图中A、B和P0三点中最靠近P1的点的参数求出P0P1和两条终边的交点的参数u1’和u1’’，令

u1=min(u1’，u1’’，1)则u1就是图中C、D和P1三点中最靠近P0的点的参数31xyyTyBxLxRABCDP1P0t0t1梁友栋-Barsky裁剪算法当u1>u0时，参数t∈[u0,u1]的线段就是P0P1的可见部分当u1<u0时，整个直线段为不可见32xyyTyBxLxRCABDP1P0u0u1BCADP1P0u0u1当pi=0时,若qi<0则P0P1是完全不可见的若qi≥0，则P0P1平行于裁剪边界,并且至少部分在窗口内

33xLxRyxCDABEFyByT梁友栋-Barsky裁剪算法梁友栋-Barsky裁剪算法算法步骤1、初始化线段交点的参数：u1=0，u2=1；2、计算出4个裁剪边界的p、q值；3、调用函数clipTest()，在函数中根据p、q来判断：是舍弃线段还是改变交点的参数。（1）当p<0时，参数r用于更新u0：（u0=max{u0，rk}）（2）当p>0时，参数r用于更新u1：（u1=min{u1，rk}）（3）如果更新了u0或u1后，使u0>u1，则舍弃该线段（4）当p=0且q<0时，因为线段平行于边界并且位于边界之外，则舍弃该线段。4、p、q的4个值经判断后，如果该线段未被舍弃，则裁剪线段的端点坐标由参数u1和u2的值决定。34梁友栋-Barsky裁剪算法特点通常比Cohen－Sutherland算法效率更高更新参数u1、u2仅仅需要一次除法Cohen－Sutherland算法：而且每次求交计算都需要做乘除法35多边形裁剪多边形裁剪基于直线的裁剪，可以把多边形裁剪分解为边界的线段，逐段来进行裁剪不仅在于求出新的顶点，删去界外顶点，还在于形成正确的顶点序列36多边形的描述方式多边形可以描述为一组顶点按一定顺序连接而成的有向点列一般可将多边形的顶点按逆时针方向顺序形成有向线段，进而连接成一个环来描述多边形的组成数据结构上，可用链表结构来描述372341多边形裁剪的特点多边形的各条边是顺次连接直线裁剪把一条线段的两个端点孤立考虑，会产生鼓励线段裁剪之后各条边不一定能保持原来的连接顺序38裁剪前错误裁剪正确裁剪多边形裁剪算法Sutherland-Hodgman算法每次用窗口的一条边界对多边形进行裁剪把落在窗口外部的图形去掉，落在窗口内部的图形保留并把它作为下一次待裁剪的多边形连续用窗口的四条边界对原始多边形进行裁剪后，最后得到的就是裁剪后的结果多边形39每一步考虑窗口的一条边界及其延长线构成的裁剪线。该裁剪线把平面分成两个部分，一部分包含窗口，称为可见一侧；另一部分称为不可见一侧。依序处理多边形各边时会有四种情况：边SP全部处于可见一侧：此时将终点P放入新的顶点序列边SP全部处于不可见一侧：此时没有点放入新的顶点序列边SP从可见一侧进入不可见一侧：