第六章 裁 剪.

Presentation on theme: "第六章 裁 剪."— Presentation transcript:

1 第六章 裁 剪

2 6.1 矩形窗口线裁剪 直接求交算法； Cohen-Sutherland算法； 中点分割裁剪算法； 梁友栋-Barsky算法
Nicholl-Lee-Nicholl算法； 拓展算法：二次及多次编码技术

3 点的裁剪 (xL,yB ) (xR,yT ) 图形裁剪中最基本的问题。 假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)，对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式： xL <= x <= xR yB <= y <= yT 否则，P点就在窗口外。

4 直接求交算法 直线与窗口边都写成参数形式，求参数值。

5 Cohen-Sutherland裁剪算法
基本思想： 对于每条线段P1P2分为三种情况处理: （1）若P1P2完全在窗口内，则显示该线段P1P2。 （2）若P1P2明显在窗口外，则丢弃该线段。 （3）若线段不满足（1）或（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 为快速判断，采用如下编码方法：

6 实现方法： 将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。 A 1001 1000 1010 C D 0001 0000 0010 B 0101 0100 0110

7 将区域码的各位从右到左编号，则坐标区 域与各位的关系为：
上 下 右 左 X X X X 任何位赋值为1，代表端点落在相应的位置上，否则该位为0。若端点在剪取矩形内，区域码为0000。如果端点落在矩形的左下角，则区域码为0101。

8 一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：

9 若P1P2完全在窗口内code1=0,且code2=0,则“取” 若P1P2明显在窗口外code1&code2≠0，则“弃”
在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 编码 线段裁剪

10 如何判定应该与窗口的哪条边求交呢？ 编码中对应位为1的边。 计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点 if(LEFT&code !=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} else if(RIGHT&code !=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} else if(BOTTOM&code !=0) { y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);} else if(TOP & code !=0) { y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}

11 小结 本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。 特点：用编码方法可快速判断线段的完全可见和显然不可见。

12 中点分割裁剪算法 基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。 与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A、B分别为距P0 、 P1最近的可见点，Pm为P0P1中点。

13 从P0出发找距离P0最近可见点采用中点分割方法
先求出P0P1的中点Pm, 若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1； 否则取PmP1代替P0P1。 再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。 从P1出发找距离P1最近 可见点采用上面类似方法。

14 中点分割裁剪算法

15 中点分割裁剪算法小结 对分辩率为2N*2N的显示器，上述二分过程至多进行N次。 主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。

16 Nicholl-Lee-Nicholl算法
基本想法：对2D平面的更细的划分。

17 Nicholl-Lee-Nicholl算法
假定待裁剪线段P0P1为非完全可见且非显然不可见。 步骤： 第一步，窗口四边所在的直线将二维平面划分成9个区域，假定落在区域0、4、5

18 Nicholl-Lee-Nicholl算法
第二步： 从P0点向窗口的四个角点发出射线，这四条射线和窗口的四条边所在的直线一起将二维平面划分为更多的小区域 。 此时P1的位置决定了P0P1和窗口边的相交关系。

19 Nicholl-Lee-Nicholl算法
第三步，确定P1所在的区域 （判断P1所在区域位置，可判定P0、P1与窗口那条边求交) 。 根据窗口四边的坐标值及P0P1和各射线的斜率可确定P1所在的区域。 第四步，求交点，确定P0P1的可见部分 。 特点：效率较高，但仅适合二维矩形窗口。

20 梁友栋-Barsky算法 设要裁剪的线段是P0P1。P0P1和窗口边界交于A,B,C,D四点，见图。算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。

21 线段的参数表示 窗口边界的四条边分为两类：始边和终边。 x=x0+t△x y=y0+t△y 0<=t<=1
△x=x1-x △y=y1-y0 窗口边界的四条边分为两类：始边和终边。

22 交点计算 求出P0P1与两条始边的交点参数t0, t1 , 令tl=max(t0 ,t1,0)，则tL即为三者中离p1最近的 点的参数
求出p0p1与两条终边的交点参数t2, t3, 令tu=min(t2,t3,1) ，则tU即为三者中离p0最近的 若tu > tl,则可见线段区间 [tl , tu] 交点计算 1 t3 t2 t1 t0

23 始边和终边的确定及交点计算： 令 QL= - △x DL= x0-xL QR= △x DR= xR-x0
QB= - △y DB= y0-yB QT= △y DT= yT-y0 交点为 ti= Di / Qi i=L,R,B,T Qi < ti为与始边交点参数 Qi > ti为与终边交点参数 Qi = Di <0 时,线段不可见 Di >0 时, 分析另一D, E A B F

24 当Qi =0时 若Di <0 时,线段不可见 （如图中AB，有QR=0，DR<0） 若Di >0 时, 分析另一D,
（如图中的EF就是这种情况，它使QL=0，DL>0和QR=0，DR>0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。） E A B F

25 传统算法拓展 尽快求出交点 …… 尽量避免求交 裁剪算法的本质： 在传统编码技术基础上进行二次编码， 尽可能多地舍弃窗外线段、减少求交。

26 二次编码技术 基于传统编码： A —— 完全可见，保留 B —— 完全不可见，舍弃 C —— 不取不弃，求交 基于二次编码：
E A 基于二次编码： A —— 完全可见，保留 B —— 完全不可见，舍弃 C —— 完全不可见，舍弃 F D 新窗口包容原窗口

27 二次编码技术 将原窗口扩大旋转450形成新窗口，重新把平面分为九个区域，并类似得进行编码，可快速抛弃C类线段。 易得450旋转窗口编码程序：
A B C D E F 新窗口包容原窗口 将原窗口扩大旋转450形成新窗口，重新把平面分为九个区域，并类似得进行编码，可快速抛弃C类线段。 易得450旋转窗口编码程序： #define LEFT1 if (x+y-YB<XL) code=code | LEFT; #define RIGHT2 else if (x+y-YT<XR) code=code | RIGHT; #define BOTTOM4 if (y-x+XR<YB) code=code | BOTTOM; #define TOP8 else if (y-x+XL>YT) code=code | TOP; Code = 0; return code;

28

29 效果分析 1. CS算法排除区域面积比例 （1）4个矩形形区域部分：(ABLG，AEDJ，DKHC，ICBF)
（2）重叠部分(AEML, BGNF, CIOH,DKPJ) （3）完全排除部分(MNOP) CS算法排除区域面积比例

30 算法需要分析其效率！ 效果分析 2. 45°旋转窗口排除区域面积比例
（1）完全落在（XLM，ESM ）或 （QKP ，JVP ）或（WIO ，THO ）或（RFN ，UGN ） 故在CS算法后， 45°旋转窗口还能排除线段的比例 t 5 10 100 1000 Infinite M1 53.9% 64.6% 74.0% 74.9% 75% M2 11.1% 23.2% 46.2% 49.6% 50% 算法需要分析其效率！

31 多次编码技术 二次编码技术以450静态窗口对线段进行过滤，为了扩展动态范围滤除更多窗外线段，可以采用多次编码技术。
基于窗口变换的过滤技术的选取课选择合适的窗型。 x z y c a b

32 6.2 多边形窗口线裁剪 参数化算法(Cyrus-Beck) 算法拓展： 多边形顶点编码裁剪算法

33 参数化算法(Cyrus-Beck) 考虑凸多边形区域R和直线段P1P2 P(t)=(P2-P1)*t+P1 设A是区域R的边界上一点，
N是区域边界在A点的内法线向量 R 则对于线段P1P2上任一点P(t) N ·(P(t)-A)<0 -> 外侧 N ·(P(t)-A)>0 -> 内侧 N ·(P(t)-A)=0 -> 边界或其延长线上 P2 N A P1

34 k条边的多边形，可见线段参数区间的解: Ni· (p(t)-Ai)>=0, i=0,…,k, 0≤t ≤1. 代入P(t)=(P2-P1)*t+P1 得： Ni· (P1-Ai)+ Ni· (P2-P1) t>=0

35 Ni· (P2-P1) =0 则线段平行于对应边。 此时判断Ni· (P1-Ai) 若Ni· (P1-Ai) <0 则P1 P2在多边形外侧，不可见； 若Ni· (P1-Ai) >0 则P1 P2在多边形内侧，继续其它边的判断。

36 对于t值的选择：首先，要符合0≤t≤1；其次，对于凸窗口来说，每一个线段与其至多有两个交点，即有两个相应的t值。所以我们可以把计算出的t值分成两组：一组为下限组，是分布在线段起点一侧的；一组为上限组，是分布在线段终点一侧的。这样，只要找出下限组中的最大值及上限组中的最小值，就可确定线段了。 分组的依据是： 如果Ni· (P2-P1) ＜0，则计算出的值属于上限组 如果Ni· (P2-P1) ＞0，则计算出的值属于下限组

37 因此，线段可见的交点参数： tl=max{0,max{ti: Ni· (P2-P1) >0}} tu=min{1,min{ti: Ni· (P2-P1)<0}} 若 tl <= tu, [tl ， tu]是可见线段的交点参数区间，否则，线段不可见。

38 算法拓展 对于多边形窗口的裁剪，关键是能否快速的判断出窗口边界是否与被裁直线存在交点。 基于多边形窗口分区编码的裁剪算法，该算法首先以被裁剪直线为参照系，将多边形窗口划分为正区、负区和近零区三类区域；然后通过对多边形窗口顶点的编码来快速地求出交点。

39 （1）对多边形窗口分区

40 （2）对多边形窗口顶点编码 顶点落在负区 则 fi = -1； 顶点落在负区 则 fi = 1； 顶点落在近零区 方程 判断

41 （3）快速裁剪 基于裁剪直线的窗口顶点编码技术 极限点位置判断法 编码之和判断法 对于多边形窗口的任意一边，其端点编码和有如下的三种关系
若满足（1）式，则窗口边与被裁剪直线不相交；若满足（2）式，则窗口边与被裁剪直线存在交点；若满足（3）式，则窗口边或顶点与被裁剪直线处于特殊位置。 （1） （2） （3）

42 （3）特殊情况快速处理 被裁直线通过多边形窗口的顶点 被裁直线与窗口的某一边重合

43 算法框图 效率分析

44 6.3 矩形窗口的多边形裁剪 参数化算法(Cyrus-Beck) 算法拓展： 多边形顶点编码裁剪算法

45 错觉：直线段裁剪的组合？ 新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？

46 2）一个凹多边形可能被裁剪成几个小的多边形，如何
确定这些小多边形的边界？

47 Sutherland-Hodgman算法
分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。 流水线过程(左上右下)：左边的结果是上边的开始。 亦称逐边裁剪算法

48 内侧空间与外侧空间 多边形的边与半空间的关系

49 裁剪结果的顶点构成： 顺序连接 裁剪边内侧的原顶点； 多边形的边与裁剪边的交点。 几点说明： 裁剪算法采用流水线方式， 适合硬件实现。
可推广到任意凸多边形裁剪 窗口

50 Weiler-Athenton算法 裁剪窗口为任意多边形（凸、凹、带内环）的情况： 主多边形：被裁剪多边形，记为A
裁剪多边形：裁剪窗口，记为B

51 主多边形和裁剪多边形把二维平面分成两部分。 内裁剪：A∩B 外裁剪：A-B
裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界

52 如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：
进点：主多边形边界由此进入裁剪多边形内 如，I1,I3, I5, I7, I9, I11 出点：主多边形边界由 此离开裁剪多边形区域. 如， I0,I2, I4, I6, I8, I10

53 1）建顶点表； 2）求交点； 3）裁剪… … Weiler_Athenton裁剪算法（内裁剪）步骤： 1、建立主多边形和裁剪多边的顶点表．
2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。 3、裁剪 如果存在没有被跟踪过的交点，执行以下步骤： (1)建立裁剪结果多边形的顶点表． (2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中． (3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界． (4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点． (5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）． (6)重复(4)、(5)直至回到起点 1）建顶点表； 2）求交点； 3）裁剪… …

54 交点的奇异情况处理 1、与裁剪多边形边重合的主多边形的边不参与求交点；
2、对于顶点落在裁剪多边形的边上的主多边的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点

55 算法思路拓展 引入二次编码，舍弃不必求交的边 二次编码还可以用在其他场合吗？？

56 6.4 圆形窗口的直线与多边形裁剪 1．经典算法介绍，SZZ算法和HMF算法 第一类直线段判别 第一类直线段处理
＝ 第一类直线段和圆关系 第二类直线段和圆关系 第一类直线段判别 第一类直线段处理 min(y1，y2)≥yo+r; max(y1，y2)≤yo-r; min(x1，x2)≥xo+r; max(x1，x2)≤xo-r;

57 第二类直线段的处理 方法一 矢量法求交点 方法二 增量法求交点 P1P2＝（x2-x1，y2-y1，0），
方法一 矢量法求交点 方法二 增量法求交点 P1P2＝（x2-x1，y2-y1，0）， 令V＝（y2-y1，x1-x2，0）， 则V⊥P1P2 ,CP1=（x1-xo，y1-yo，0）

58 算法思路的拓展 基于多重编码的新颖的线裁剪算法 ——尽量避免无效的求交，尽量快速的求取有效交点。 第一重编码：常规外切正方形一次编码
code（P1）& code（P2）!= 0 第二重编码：旋转外切正方形二次编码

59 当flag ≥ 0，则为窗外线段，如线段a、线段b和线段g； 当flag < 0，则为可能与窗口相交线段，如线段e、线段f和线段h。
第三重编码：广义距离三次编码 定义fi=sgn|di-R|为广义距离编码 f1+f2 < 0 or （f1 ＝＝0 ）&& （f2 ＝＝0） f1+f2 ＝＝ 0 && （f1!=0 ）|| （f2! ＝ 0） f1+f2 ＝＝ 1 f1+f2 ＝＝ 2 flag=[（x2-x1）x1 +（y2-y1）y1]×[（x2-x1）x2 +（y2-y1）y2] 当flag ≥ 0，则为窗外线段，如线段a、线段b和线段g； 当flag < 0，则为可能与窗口相交线段，如线段e、线段f和线段h。 若flag < 0，还需继续进行判别，这些线段仍有可能是窗外线段，如线段f。

60 6.5 圆形窗口的直线与多边形裁剪 1．经典算法介绍，SZZ算法和HMF算法 第一类直线段判别 第一类直线段处理
＝ 第一类直线段和圆关系 第二类直线段和圆关系 第一类直线段判别 第一类直线段处理 min(y1，y2)≥yo+r; max(y1，y2)≤yo-r; min(x1，x2)≥xo+r; max(x1，x2)≤xo-r;

61 6.4 圆形窗口的多边形裁剪 经典算法 Ait2+2Bit+C=0 其中，Ai=(xi+1-xi)2+(yi+1-yi)2,
顶点pi的入边 顶点pi的出边 p1入p2p3出p3入p4p5p6出p6入p0出 (0≤t≤1) （0≤θ≤2π） Ait2+2Bit+C= 其中，Ai=(xi+1-xi)2+(yi+1-yi)2, Bi=xi(xi+1-xi)+yi(yi+1-yi)， Ci=xi2+yi2-R2,

62 算法思路拓展 Pi和Pi+1，计算它们的广义距离di和 di+1，根据di和 di+1与R（R＝r2）之间的关系将剩余多边形的边分为四类
a c b d f e g 1000 1010 0010 0110 0100 0101 0001 1001 0000 Pi和Pi+1，计算它们的广义距离di和 di+1，根据di和 di+1与R（R＝r2）之间的关系将剩余多边形的边分为四类 (d) (c) (a) （b） max{di,di+1}≤R min{di,di+1}<R max{di,di+1}>R min{di,di+1}=R max{di,di+1}>R

63 6.5 三维立方体的线裁剪 包围盒编码取舍线段 45°的直线的斜率k为1 y=x+b ,消去了乘法运算 (1)常规包围盒一次编码取舍线段
(2)新型包围盒二次编码舍弃线段 位置关系可转化为6位二进制代码表示，从高位到低位，依次表示的方位为上、下、右、左、后、前。 (3)包围盒与线段分类

64 包围盒编码取舍线段 Y Z X （1） 常规包围盒编码分区 8个角域，12个边域和6个面域以及1个窗体 ,
有三位为1，属于角域，二位为1，则属于边域，一位为1，属于面域。 采用移位运算符（>>和<<）判断高位或低位是否为1 。 （2）基于编码分区的几何变换求交 任何一个区域经过适当的几何变换， 最终都可以映射到三个基本区域中去。 Y Z X 通过线段端点编码与裁剪窗体各个面逻辑与（&）运算，如果所得值为真，则与此面求交，通过逐一求交并比较排除冗余交点，最终确定唯一有效交点。