《开发动态Web网站的几种技术》由会员分享，可在线阅读，更多相关《开发动态Web网站的几种技术（32页珍藏版）》请在金锄头文库上搜索。
1、1 1、Cohen-SutherlandCohen-Sutherland算法算法 本算法又称为编码裁剪算法，算法的基本思想是对每条直线段p1(x1,y1)，p2(x2,y2)分三种情况处理：a、若点p1和p2完全在裁剪窗口内，则该直线段完全可 见， “简取”之。b、若点p1和p2均在窗口外，且满足下列4个条件之一， 直线段完全不可见，“简弃”之。c、直线段既不满足“简取”的条件，也不满足“简弃” 的条件，需要对直线段按交点进行分段，分段后 重复上述处理。 算法具体实现是：每条线段的端点都赋以四位二进制码D3D2D1D0 ，称为区域码，用来标识出端点相对于裁剪矩形边界的位置。编码规则如下：若xw
2、xr，则D1=1，否则D1=0；若ywyt，则D3=1，否则D3=0。 区域码的各位指出端点对于裁剪窗口的四个相对坐标位置：左、右、下、上。将区域码各位从右到左编号，则坐标区域与各位的关系为：位1：左位2：右位3：下位4：上 任何位赋值为1，代表端点落在相应的位置上，否则该位置为0。 根据该编码规则，窗口及其延长线所构成的9个区域的编码如图所示。01000101100100011010011010000010 窗口及区域编码D3D2D1D0窗口0000 裁剪一条线段时，先求出端点p1和p2的编码code1和code2，然后进行处理：（1）若code1|code2=0，对直线段应简取之。（2）若
3、code1&code20，对直线段可简弃之。 这是因为若code1和code2经按位与运算后的结果不为0，说明两个端点同在窗口的上方、下方、左方或右方。（3）若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。 实现时，一般按固定顺序检查直线段端点的编码位是否为0。这里按左、右、下、上的顺序。与窗口边界求交的顺序也可以任意选择，这里也按左（x=wxl）、右（x=wxr）、下（y=wyb）、上（y=wyt）的顺序进行。 对于端点坐标为（x1，y1）和（x
4、2，y2）的直线，与左、右边界交点的y坐标可以这样计算：其中，x为wxl或wxr，线段的斜率为：与上、下边界交点的x坐标可以这样计算：其中，y为wyb或wyt。下面写出Cohen-Sutherland直线段裁剪算法的步骤：（1）输入直线段的两端点坐标： P1（x1，y1），P2（x2，y2）,以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。（2）对P1、P2编码：点P1的编码为code1，点P2的编码为code2。（3）若code1|code2=0，对直线段应简取之，转（6）；否则，若code1&code20，对直线段可简弃之，转（7）；当上述两条均不满足时，进行步骤（4）。（4）确保
5、P1在窗口外部：若P1在窗口内，则交换P1和P2的坐标值和编码。（5）按左、右、下、上的顺序求出直线段与窗口边界的交点，并用该交点的坐标值替换P1的坐标值。 也就是在交点，假定为S，S处把线段一分为二，并去掉P1S这一段（考虑到P1是窗口外的一点，因此可以去掉P1S转（2）。（6）画出当前的直线段P1 P2 。（7）算法结束 。下面根据该算法步骤来裁剪如图所示的直线段P1P2 ：P1P2P3P4直线段P1P2的编码裁剪001010001001000010100101000101100100 首先对P1P2进行编码， P1的编码code1为0001，P2的编码code2为0100。由于 code
6、1|code20，且code1&code2=0，因此对直线段P1P2既不能简取也不能简弃，故进行求交处理。 由code1=0001知P1在窗口左外侧，按左、右、下、上的顺序求出直线段与窗口左边界的交点为P3， P1P3必在窗口外，可简弃之。 对P2P3重复上述处理（此时用原P3替换P1）： P1（原P3）的编码为0000，P2编码为0100，因此对直线段P1P2既不能简取也不能简弃。 由于P1（原P3）已在窗口内，交换P1、P2的坐标值和编码，按左、右、下、上的顺序求出P1P2与窗口下边界的交点P4 ，丢弃P1（原P2）P4 。 剩下的直线段（P3P4）再进行进一步判断， code1|code
7、2=0，全在窗口中，简取之。 Cohen-Sutherland算法用编码的方法实现了对完全可见和不可见直线段的快速接受和拒绝。比较适合两种情况：一是大部分线段完全可见；二是大部分线段完全不可见。2 2、LiangLiang- -BarskyBarsky算法算法 在Cohen-Sutherland算法提出后，Cyrus和Beck用参数化方法提出了针对凸多边形的裁剪算法，它比编码算法更有效。而梁友栋和Barsky 又针对标准矩形窗口提出了更快的Liang-Barsky直线段裁剪算法。 Liang-Barsky算法的基本出发点是直线的参数方程。给出任一条直线段P1（x1，y1），P2（x2，y2），
8、其参数方程为： 其中，（x,y）为直线上任意一点。如果直线上一点（x,y）位于由坐标（x,y）和（x,y）所确定的窗口内，则有下式成立：即有：将 代入上式可以得到：令：于是有：其中，k = 1，2，3，4。 首先分析pk=0的情况，若p1=p2=0,则直线与窗口边界wxl和wxr平行。其中k对应于该裁剪边界（k=1,3,4对应于左、右、下、上边界）。(a)直线段与窗口边界wxl和wxr平行的情况wytwybwxlwxrA AB BC CD DE EF F 从右图中可以看出，若满足 q10（直线A）或q20 （直线F），则相应的有x1wxl或wxrumin，则直线段在窗口外，删除该直线。若uma
9、umin，将uma和umin代回直线的参数方程即求出直线与窗口的两实交点坐标。 注：注： 当Pk0，表示线段从裁剪边界延长线的内部延伸到外部。 对于每条直线，可以计算出参数umax和umin，它们定义了在裁剪矩形内的线段部分。 umax的值由线段从外到内遇到的矩形边界所决定（p0）。 umin取1和uk值之中的最小值。如果umaxumin，则线段完全落在裁剪窗口之外，删除该直线；若umaxumin，将umax和umin代回直线参数方程，即求出直线与窗口的两实交点坐标。 上述解的几何意义可以这样来看：将直线与窗口边界的实交点和虚交点分为两组，下限组以pk0为特征：表示在该处，直线从裁剪边界延长线
10、的内部延伸到外部。在有交情形，下限组分布于直线段起点一侧，上限组分布于直线段终点一侧，则下限组的最大值和上限组的最大值就分别对应于直线与窗口边界的实交点（假定存在）。 类似地，若p3=p4=0,则直线与窗口边界wyb和wyt平行，如右图所示。(b)直线段与窗口边界wyb和wyt平行的情况wxrwxlwybwytG GH HI IJ JK KL L 若q30（直线段L）或q40 （直线段G），则相应的有y1wyb或wytumin，则直线段在窗口外，删除该直线。若umaxumin，将umax和umin代回直线参数方程，即求出直线与窗口的两实交点坐标。 对于PK0的情况，则直接求出直线段与窗口边界的
11、交点： 同样， uk是窗口边界及其延长线的交点的对应值。此时分别计算umax和umin： 若umaxumin，则直线段在窗口外，删除该直线。若umaxumin，将umax和umin代回直线参数方程，即求出直线与窗口的两实交点坐标。 下面写出Liang-Barsky算法的算法步骤：（1）输入直线段的两端点坐标（x1,y1）、（x2,y2），以及窗口的四条边界坐标：wxl、wxr、wyb和wyt。（2）若X=0，则p1=p2=0,此时进一步判断是否满足q10或q20，若满足，则该直线段不在窗口内，算法转（7）。否则，满足q10且q20，则进一步计算uma和umin：其中， 。算法转（5）（3）若y
12、=0，则p3=p4=0,此时进一步判断是否满足q30或q4umin，则直线段在窗口外，算法转（7）。若umaumin，利用直线的参数方程：求得直线段与窗口的两实交点坐标。（6）利用直线的扫描转换算法绘制在窗口内的直线段。（7）算法结束。3 3、多边形的裁剪、多边形的裁剪 假定直接用上述介绍的直线段裁剪算法对多边形的每条边进行裁剪，会得到下面的情况：(a)裁剪前(b)直接采用直线段裁剪的结果即得到一系列不连续的直线段。而实际上，应该得到的是下图所示的有边界的区域：(c)正确的裁剪结果 多边形裁剪算法的输出应该是定义裁剪后的多边形边界的顶点序列。于是，需要构造能产生一个或多个封闭区域的多边形裁剪算
13、法。Sutherland-Sutherland-HodgemanHodgeman多边形裁剪多边形裁剪 该算法又称逐边裁剪算法，其基本思想是将多边形边界作为一个整体，每次用窗口的一条边界对要裁剪的多边形进行裁剪，体现一种分而治之的思想。窗口各边界裁剪的多边形存储输入与输出顶点表在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界继续裁剪。 每次裁剪时把落在窗口外部区域的图形去掉，只保留落在窗口内部区域的图形，并把它作为下一次裁剪的多边形。依次用窗口的四条边界（按任何顺序均可，这里采用左、下、右、上的顺序）对要裁剪的多边形进行裁剪，则原始多边形即被裁剪完毕。输入：ABCDEFGH
14、ABCDEFGH输出：A12DEFGH12(a)用左边界裁剪输出：A134D56FGHADEFGH输入：A12DEFGH12(b)用下边界裁剪3456 从上图中可以看到，窗口的一条边及其延长线构成的裁剪线把平面分为两个区域：包含有窗口区域的一个域称为可见侧；不包含窗口区域的域为不可见侧。这样，沿着多边形依次处理顶点会遇到四种情况：SPI(a)输出I、P可见侧 一是第一点S在不可见侧面而第二点P在可见侧，则多边形的该边与窗口边界的交点I与第二点P均被加入到输出顶点表中。SP(b)输出P可见侧 二是S和P都在可见侧，则P、S被加入到输出顶点表中； 三是S在可见侧，而P在不可见侧，则交点I被加入到输
15、出顶点表中；SPI(c)输出I可见侧SP(d)不输出可见侧 四是如果S和P都在不可见侧，输出顶点表中不增加任何顶点。 在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界继续裁剪。A(a)裁剪前BCDEF(b)Sutherland-Hodgeman算法的裁剪结果ABCDEFV1V2V3V4 要实现上述算法，就要为窗口各边界裁剪的多边形存储输入与输出顶点表，如果每一步仅仅裁剪点并且将裁剪后的顶点传输到下一边界的裁剪程序，就可以减少中间输出顶点表。 这样就可以用并行处理器或单处理器的裁剪算法的流水线完成。只有当一个点（输入点或交点）被窗口的4个边界都判定在窗口内或窗口边界上时，才加入到输出顶点表。因此，该算法特别适合于用硬件实现。
