计算机图形学第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：端点处于左边界的左方否则，相应位为012otherwise0if1maxyyCtotherwise0if1minyyCbCohen-Sutherland裁剪算法otherwise0if1minxxClotherwise0if1maxxxCrCohen-Sutherland裁剪算法对线段的每个顶点，根据其所在区域赋予此编码if(xXL)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点。elseP2=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!2700xxuxyyuy01u00LRBTxxuxxyyuyy梁友栋-Barsky裁剪算法不等式可写作：即线段与裁剪边界的交点有280000,,,.LRBTuxxxuxxxuyyyuyyyiiupq,/,0.iiiiiiupquqppyxyTyBxLxRABCDP1P0梁友栋-Barsky裁剪算法窗口边界的四条边分成两类，一类称为始边，另一类称为终边当Δx≥0时，称x=xL为始边，x=xR为终边当Δx0时，称x=xL为终边，x=xR为始边当Δy≥0时，称y=yB为始边，y=yT为终边当Δy0时，称y=yB为终边，y=yT为始边29yxyTyBxLxRP1P0P0P1AB可知边界交点的参数：当pi0时，求得的ti必是P0P1和始边的交点的参数当pi0时，ui必是P0P1和终边的交点的参数30/,0.iiiiuqpp梁友栋-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裁剪算法当u1u0时，参数t∈[u0,u1]的线段就是P0P1的可见部分当u1u0时，整个直线段为不可见32xyyTyBxLxRCABDP1P0u0u1BCADP1P0u0u1当pi=0时,若qi0则P0P1是完全不可见的若qi≥0，则P0P1平行于裁剪边界,并且至少部分在窗口内33xLxRyxCDABEFyByT梁友栋-Barsky裁剪算法梁友栋-Barsky裁剪算法算法步骤1、初始化线段交点的参数：u1=0，u2=1；2、计算出4个裁剪边界的p、q值；3、调用函数clipTest()，在函数中根据p、q来判断：是舍弃线段还是改变交点的参数。（1）当p0时，参数r用于更新u0：（u0=max{u0，rk}）（2）当p0时，参数r用于更新u1：（u1=min{u1，rk}）（3）如果更新了u0或u1后，使u0u1，则舍弃该线段（4）当p=0且q0时，因为线段平行于边界并且位于边界之外，则舍弃该线段。4、p、q的4个值经判断后，如果该线段未被舍弃，则裁剪线段的端点坐标由参数u1和u2的值决定。34梁友栋-Barsky裁剪算法特点通常比Cohen－Sutherland算法效率更高更新参数u1、u2仅仅需要一次除法Cohen－Sutherland算法：而且每次求交计算都需要做乘除法35多边形裁剪多边形裁剪基于直线的裁剪，可以把多边形裁剪分解为边界的线段，逐段来进行裁剪不仅在于求出新的顶点，删去界外顶点，还在于形成正确的顶点序列36多边形的描述方式多边形可以描述为一组顶点按一定顺序连接而成的有向点列一般可将多边形的顶点按逆时针方向顺序形成有向线段，进而连接成一个环来描述多边形的组成数据结构上，可用链表结构来描述372341多边形裁剪的特点多边形的各条边是顺次连接直线裁剪把一条线段的两个端点孤立考虑，会产生鼓励线段裁剪之后各条边不一定能保持原来的连接顺序38裁剪前错误裁剪正确裁剪多边形裁剪算法Sutherland-Hodgman算法每次用窗口的一条边界对多边形进行裁剪把落在窗口外部的图形去掉，落在窗口内部的图形保留并把它作为下一次待裁剪的多边形连续用窗口的四条边界对原始多边形进行裁剪后，最后得到的就是裁剪后的结果多边形39每一步考虑窗口的一条边界及其延长线构成的裁剪线。该裁剪线把平面分成两个部分