计算机图形学第三章二维图形的裁剪

第三章二维图形的裁剪掌握二维图形点、线段、多边形和字符的裁剪算法。理解二维裁剪算法思想并且用C语言进行算法的实现。课时安排：授课4学时（线段裁剪：2学时；多边形裁剪：2学时）；4学时（多边形裁剪）。第三章二维图形的裁剪第三章二维图形的裁剪►一、裁剪的意义►为了描述图形对象，我们必须存储它的全部信息，但有时为了达到分区描述或重点描述某一部分的目的，往往将要描述的部分置于一个窗口内，而将窗口外的部分“剪掉”，这个处理过程叫做裁剪，裁剪在计算机图形处理中具有十分重要的意义。►裁剪实质上是从数据集合中抽取信息的过程，这个过程是通过一定的计算方法来实现。►内的图形保留，而窗口外的图形则被舍弃。第三章二维图形的裁剪►二、裁剪的目的►裁剪的基本目的是判断某个图形元素是否落在窗口之内，如落在窗口之内则进一步求出位于窗口内的部分。►三、裁剪处理涉及►1、图元在窗口内外的判别；2、图形元素与窗口的求交。3.1点的裁剪►先看简单的点图元裁剪，它是线段裁剪以及后面的多边形裁剪的基础。►如果矩形窗口的左、右横坐标为：xmin、xmax；上、下纵坐标为：ymin，ymax。►某点（x，y）在窗口内的充分必要条件是：3.1点的裁剪►xmin≤x≤xmax（3－1）►ymin≤y≤ymax►如果上面四个不等式中任何一个不满足，则点（x，y）位于窗口之外。►对于任意多边形窗口，需要根据第二章提到的多边形内点的判别准则进行判断。3.2线段的裁剪►直线段的裁剪比点复杂，其裁剪方法又是多边形裁剪和三维图形裁剪的基础。►一、直线裁剪的基本思想►判断直线与窗口的位置关系：►1．确定直线是完全可见；►2．部分可见；►3．还是完全不可见。►对部分可见线段，求出它与窗口边界的交点，并将窗口内的线段输出。3.2线段的裁剪►二、裁剪线段和窗口的关系►假定窗口左下角坐标为(xmin，ymin)，右上角坐标为(xmax，ymax)，待裁剪线段和窗口的关系如图所示，这五种位置关系存在下面三种情况：►1、直线的两个端点均在窗口内，如图中AB线。这时直线完全可见，可被简单接受。►2、直线的两个端点都在窗口外，并且位于窗口某一边界的同一外侧，如图中EF线。则直线完全不可见，可被简单舍弃。►3、除此之外需要求交点，以确定直线在窗口某一边界内是否有可见部分,并裁掉外部线段，显示内部线段。如CD、GH、IJ线。3.2线段的裁剪3.2线段的裁剪►为了提高裁剪效率，算法设计一般可从下面两方面作出考虑：►(1)快速判断情况1和情况2。►(2)在情况3中，设法减少求交的次数和每次求交时所需的计算量。►三、直线求交计算►当线段P1P2穿过某边界L时，交点P的计算如图中所示。3.2线段的裁剪►根据直线两点式方程：►(3－2)3.2线段的裁剪►整理后得通用交点公式：►(3－3)►1、与上边界的求交公式：►(3－4)3.2线段的裁剪►2、与下边界的求交公式：►(3－5)►3、与右边界的求交公式：►(3－6)►4、与左边界的求交公式：►(3－7)3.2.1Cohen－Sutherland算法►一、Cohen－Sutherland算法思想：►该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。►对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。3.2.1Cohen－Sutherland算法►二、Cohen－Sutherland算法步骤：►1、分区编码►延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。►3.2.1Cohen－Sutherland算法►四位二进制代码的编码规则是：►►►(1)第一位置1：区域在左边界外侧►(2)第二位置1：区域在右边界外侧►(3)第三位置1：区域在下边界外侧►(4)第四位置1：区域在上边界外侧裁剪窗口内（包括边界上）的区域，四位二进制代码均为0。►设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。3.2.1Cohen－Sutherland算法►2、判别►根据C1和C2的具体值，可以有三种情况：►（1）C1=C2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。►（2）C1&C2≠0（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。►（3）不属于上面两种情况，均需要求交点。3.2.1Cohen－Sutherland算法►3、求交点►假设算法按照：左、右、下、上边界的顺序进行求交处理，对每一个边界求完交点，并相关处理后，算法转向第2步，重新判断，如果需要接着进入下一边界的处理。►为了规范算法，令线段的端点P1为外端点，如果不是这样，就需要P1和P2交换端点。►当条件(C1&0001≠0)成立时，表示端点P1位于窗口左边界外侧，按照前面介绍的求交公式，进行对左边界的求交运算。3.2.1Cohen－Sutherland算法►次类推，对位于右、下、上边界外侧的判别，应将条件式中的0001分别改为0010、0100、1000即可。►求出交点P后，用P1=P来舍去线段的窗外部分，并对P1重新编码得到C1，接下来算法转回第2步继续对其它边界进行判别。►三、Cohen－Sutherland算法分区编码程序：3.2.1Cohen－Sutherland算法►Code(intx,inty,int*c)►{*c=0;if(yymax)/*（xmin，ymin）和（xmax，ymax）为窗口左下角、右上角坐标。*/*c=*c|0x08;elseif(yymin)*c=*c|0x04;if(xxmax)*c=*c|0x02;elseif(xxmin)*c=*c|0x01;}3.2.1Cohen－Sutherland算法3.2.2中点分割算法Cohen－Sutherland直线裁剪算法，充分利用了直线段与裁剪边框的相关性，使裁剪速度大大提高，但在求交过程中仍采用了乘除运算，裁剪速度受到影响。而中点分割法的特点，就在于它是用连续平分线段最终求得交点的方法代替用乘除法实现求交运算。这样只需进行整数的加法和用运算器右移一位来实现除法运算，从而避免去做大量的乘除法。3.2.2中点分割算法一、中点分割算法思想1、中点公式（3－8）2、中点分割法求交点的规则如图中所示，当线段P1P2求出中点P后，舍弃线段的哪部分，由下面两条规则决定：中点分割法求交点规则3.2.2中点分割算法（1）如果P1与P同侧，移动P1点；（即可能的交点只能出现在PP2段）if((C1&C)!=0)P1=P;（2）如果P1与P不同侧，移动P2点。（即可能的交点只能出现在P1P段）if((C1&C)==0)P2=P;二、中点分割算法实现1、将直线的两端点P1、P2编码得：C1、C2；3.2.2中点分割算法2、判别根据C1和C2的具体值，可以有三种情况：（1）C1＝C2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。（2）C1&C2≠0（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。（3）不属于上面两种情况，均需要求交点。3.2.2中点分割算法3、求交点（1）令窗外端点为P1，如果窗外点不是P1，则P1和P2交换端点；（2）保留窗内端点P2到暂存器里；（3）对P1编码为C1；（4）用中点公式求出中点，并编码得C；3.2.2中点分割算法（5）按照中点算法的求交规则：若P1和P同侧，移动P1点；if((C1&C)!=0)P1=P;否则，移动P2点。elseP2=P;（6）流程转（3），直到P1和P2相差一个单位时：令交点为P2，取出暂存器的端点赋给P1，然后转向流程1。3.2.2中点分割算法三、中点分割算法特点1、求交点的次数（n）与线段长度（L）有关，其关系为：L=2n。例如：线段长度为256，则求交点的次数为8。2、中点分割法求出的交点是边界上的有效交点，而不是边界及其延长线上的交点。（而Cohen－Sutherland直线裁剪算法求出的则是边界上或者边界的延长线上的交点。）3.2.3梁友栋-Barsky裁剪算法Cyrus和Beck用参数化方法提出了比Cohen-Sutherland更有效的算法。后来梁友栋和Barsky独立地提出了更快的参数化线段裁剪算法，也称为Liany-Barsky（LB）算法。一、梁友栋-Barsky裁剪算法思想：我们知道，一条两端点为P1（x1，y1）、P2（x2，y2）的线段可以用参数方程形式表示：x=x1+u·（x2-x1）=x1+u·Δxy=y1+u·（y2-y1）=y1+u·Δy0≤u≤1（3-9）3.2.3梁友栋-Barsky裁剪算法式中，Δx=x2-x1，Δy=y2-y1，参数u在0～1之间取值，P（x，y）代表了该线段上的一个点，其值由参数u确定，由公式可知，当u=0时，该点为P1（x1，y1），当u=1时，该点为P2（x2，y2）。如果点P（x，y）位于由坐标（xwmin，ywmin）和（xwmax，ywmax）所确定的窗口内，那么下式成立：xwmin≤x1+u·Δx≤xwmaxywmin≤y1+u·Δy≤ywmax（3-10）3.2.3梁友栋-Barsky裁剪算法这四个不等式可以表示为：u·pk≤qk，k=1，2，3，4（3-11）其中，p、q定义为：p1=-Δx，q1=x1-xwminp2=Δx，q2=xwmax-x1p3=-Δy，q3=y1-ywminp4=Δy，q4=ywmax-y1（3-12）3.2.3梁友栋-Barsky裁剪算法从（3-12）式可以知道：任何平行于窗口某边界的直线，其pk=0，k值对应于相应的边界（k=1，2，3，4对应于左、右、下、上边界）。如果还满足qk0，则线段完全在边界外，应舍弃该线段。如果pk=0并且qk≥0，则线段平行于窗口某边界并在窗口内，见图中所示。公式（3-12）式还告诉我们：3.2.3梁友栋-Barsky裁剪算法1、当pk0时，线段从裁剪边界延长线的外部延伸到内部；2、当pk0时，线段从裁剪边界延长线的内部延伸到外部；3.2.3梁友栋-Barsky裁剪算法例如:当Δx≥0时，对于左边界p10（p1=-Δx），线段从左边界的外部到内部；对于右边界p20（p2=Δx），线段从右边界的内部到外部。当Δy0时，对于下边界p30（p3=-Δy），线段从下边界的内部到外部；对于上边界p40（p4=Δy），线段从上边界的外部到内部。当pK≠0时，可以计算出参数u的值，它对应于无限延伸的直线与延伸的窗口边界k的交点，即：（3-13）3.2.3梁友栋-Barsky裁剪算法对于每条直线，可以计算出参数u1和u2，该值定义了位于窗口内的线段部分：1、u1的值由线段从外到内遇到的矩形边界所决定（pk0），对这些边界计算rk=qk/pk，u1取0和各个r值之中的最大值。2、u2的值由线段从内到外遇到的矩形边界所决定（pk0），对这些边界计算rk=qk/pk，u2取0和各个r值之中的最小值。3、如果u1u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u1和u2计算出来。3.2.3梁友栋-Barsky裁剪算法二、梁友栋-Barsky裁剪算法实现1、初始化线段交点的参数：u1=0，u2=1；2、计算出各个裁剪边界的p、q值；3、调用函数clipTest()，在函数中根据p、q来判断：是舍弃线段还是改变交点的参数。3.2.3梁友栋-Barsky裁剪算法（1）当p0时，参数r用于更新u1；（u1=max{u1，…，rk}）（2）当p0时，参数r用于更新u2。（u2=min{u2，…，rk}）（3）如果更新