第6章 二维观察.ppt

1、第6章 二维观察,2D 观察变换2D 剪裁操作,x,y,w1,w2,w3,w4,窗口,6.1 2D 观察变换,世界坐标系,设备坐标系,6.1.1 窗口 & 视口,窗口的定义： 常规图形系统中，世界坐标系中指定的用于显示的坐标区域。 视口的定义： 显示设备上用于窗口映射的坐标区域，也叫视区。 观察变换： 通常, 世界坐标系中部分场景映射到设备坐标系的过程称为观察变换，也叫视像变换，或称为从窗口到视口的变换。,窗口的另一种定义：窗口管理系统中，任何可移动（move about）、改变大小(resized)、激活(active)或变为无效(inactive)的屏幕上的矩形区域。,6.1.2 2D 的

2、观察流程,世界坐标 观察坐标的变换,x0,y0,X世界,y世界,X观察,Y观察,世界坐标 观察坐标的变换,M = R.T,窗口到视口的坐标变换,(Xw-W1)/(W2-W1) = (Xv-V1)/(V2-V1)(Yw-W3)/(W4-W3) = (Yv-V3)/(V4-V3) Xv = AX+BYv = CY+DA = (V2-V1)/(W2-W1)B = (W2*V1-W1*V2)/(W2-W1)C = (V4-V3)/(W4-W3)D = (W4*V3-W3*V4)/(W4-W3),窗口到视口的坐标变换,窗口到视口的坐标变换,变换矩阵：A 0 B0 C D0 0 1,已知w1=10,w2=

3、20,w3=40,w4=80, v1=80,v2=110,v3=10,v4=130, 窗口中一点P(15，60)，求视口中的映射点P 解：(15-10)/(20-10) = (xv-80)/(110-80)(60-40)/(80-40) = (yv-10)/(130-10)xv = 95, yv=70P(95，70),例：窗口到视口的坐标变换,窗口与视口的位似性,定义：如果窗口的底与高之比等于视区的底与高之比，则称窗口与视区是位似的。(w2-w1)/(w4-w3)=(v2-v1)/(v4-v3)此时图形从窗口变换到视口不畸变。,窗口与视口的位似性,在坐标分别为wx1=-2.5,wx2=2.5,

4、wy1=-2.5,wy2=2.5的窗口中显示一个圆，把它映射到视口中，下面哪些视口中图形不发生畸变。 视口坐标 vx1 vx2 vy1 vy21 10 60 50 1202 80 110 10 403 85 105 50 1004 10 60 15 35,6.5 2D剪裁操作,剪裁的定义识别图形在指定区域内或区域外的图形部分的过程 剪裁窗口:用来剪裁对象的区域。 剪裁时机 针对窗口剪裁 针对视口剪裁,剪裁类型 点剪裁 直线剪裁 多边形剪裁 曲线剪裁 文本剪裁 空白剪裁,6.5 2D剪裁操作,6.6 点的剪裁,任何图形都可能包含点、直线、字符、和多边形乃至直线， 但它们都可以分解成点的集合。 点

5、的剪裁是图形剪裁中最基本的问题。,6.6 点的剪裁,假设剪裁窗口是在标准位置的矩形窗口 点P(x,y)如果满足下列不等式则保留：w1xw2， w3yw4 否则，P点就在窗口外，被剪裁,w1,w2,w3,w4,(x,y),6.7 线段的剪裁,线段与窗口的位置关系： 整个线段全在窗口内； 整个线段全在窗口外； 线段部分在窗口外，部分在窗口内。,6.7 线段的剪裁,当线段的两个端点全在窗口内时，该直线整个在窗口内 当线段的两个端点，一个在窗口内，一个在窗口外时，该直线部分在窗口内，部分在窗口外 当线段的两个端点全在窗口外时，该直线可能整个在窗口外；也可能部分在窗口内，部分在窗口外,线段的剪裁,Coh

6、en-Sutherland直线剪裁(CS算法) Liang-Barsky 直线剪裁(LB算法) Nicholl-Lee-Nicholl 直线剪裁(NLN算法) 非矩形剪裁窗口,线段的剪裁,6.7.1 Cohen-Sutherland 线段剪裁,思想： 线段由端点标识； 测试线段端点和窗口边界的关系以确定是否需要计算交点 当线段的两个端点全在窗口内时，该线段整个在窗口内 当线段的两个端点，一个在窗口内，一个在窗口外时，该线段部分在窗口内，部分在窗口外 当线段的两个端点全在窗口外时，该线段可能整个在窗口外，也可能部分在窗口内，部分在窗口外,扩展窗口的边界将整个2D平面划分为9个区域 每个区域赋予一

7、个4位编码, 称为区域码b3b2b1b0,CS算法 编码方案,编码规则：b3b2 b1 b0 b0 = 1 if x w2 b2 = 1 if y w4,0000,0110,0100,0101,0010,0001,1001,1000,1010,w1,w2,w3,w4,6.7.1 Cohen-Sutherland 线段剪裁,计算直线端点区域编码： c1 和 c2; 判断 c1 和 c2 均为0000，保留直线 c1 & c2 不为零，同在某一边界外，删除该直线 c1 & c2 为零，需要进一步求解交点 以左、右、下、上为序，找出端点区域码中第一位为1的位，将窗口边界方程x=w1/w2或y=w3/

8、w4带入直线方程，计算直线与窗口边界的交点，将交点和另一端点形成新的直线，重复上述过程，直至线段保留或删除,CS 算法描述,程序流程图 程序实现(P178) 例,6.7.1 Cohen-Sutherland 线段剪裁,P3,P4,CS线段剪裁算法 举例,0000,0110,0100,0101,0010,0001,1001,1000,1010,CS线段剪裁算法 举例,优点：简单，易于实现。它可以简单的描述为将直线在窗口外边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。此算法中求交点是很重要的，决定了算法的速度。,CS线段剪裁算法小结:,CS线段剪裁算法 作业,已知线

9、段的两个端点P1(-3/2,1/6)，P2(1/2,3/2)窗口边界x=-1,x=1,y=-1,y=1 用CS算法对线段进行剪裁,思想：以线段的中点作为线段的分割点分别寻找直线段两个端点各自对应的最远的可见点,线段的中点剪裁算法,步骤：在求线段与边界的交点时采用折半查找技术(与CS算法不同)，其余步骤同CS 特点：中点分割剪裁是对于硬件很适合的，它可以用移位来代替除法，大大加快了速度。,线段的中点剪裁算法,1,3,2,线段的中点剪裁算法,P1,P2,0000,0110,0100,0101,0010,0001,1001,1000,1010,3,4,6.7.2 Liang-Barsky 线段剪裁算

10、法,思想： 基于直线段参数方程分析的快速直线剪裁算法 参数方程直线两端点 P1(x1,y1),P2 (x2,y2)x=x1+(x2x1)uy=y1+(y2y1)u, 0 u 1,6.7.2 Liang-Barsky 线段剪裁算法,已知直线端点 ：起点P1(x1,y1),终点P2 (x2,y2) 参数方程：x=x1+(x2x1)uy=y1+(y2y1)u其中: 0u1,LB算法推导如果直线在窗口内, 则w1x1+dx*uw2w3y1+dy*uw4Pk*uQk k=1,2,3,4 P1= - dx, Q1=x1-w1 P2= dx, Q2=w2-x1 P3= - dy, Q3=y1-w3 P4=

11、dy, Q4=w4-y1,6.7.2 Liang-Barsky 线段剪裁算法,LB算法描述 计算 Pk, Qk, k=14 判断是否存在Pk=0, 如果存在,进一步判断QkPk=0，表示直线平行于窗口某边界if Qk0，直线在窗口外，被剪裁else 直线在窗口内 对 Pk!=0的情形, 用Qk/Pk计算交点所对应的U值,6.7.2 LB线段剪裁算法,对每条线计算参数u1&u2u1=Max0, Qk/Pk, Pk 0 如果u1 u2, 则直线在窗口外，否则计算交点坐标,6.7.2 Liang-Barsky 线段剪裁算法,LB线段剪裁算法 举例,已知线段的两个端点P1(3,4)，P2(8,2)窗口

12、边界x=1,x=4,y=1,y=3 用LB算法对线段进行剪裁,LB线段剪裁算法 举例： 已知线段的两个端点(3,4)，(8,2) 窗口边界x=1,x=4,y=1,y=3,线段的参数方程 x=3+5uy=4-2u P1=-5,Q1=2,R1=-2/5P2=5,Q2=1,R2=1/5P3=2,Q3=3,R3=3/2P4=-2,Q4=-1,R4=1/2 u1=max(0,-2/5,1/2)=1/2u2=min(1,1/5,3/2)=1/5 u1u2 所以线段全部被剪裁,算法实现(P181) LB与CS的比较 LB 效率高于 CS, 因为减少了交点计算次数。 参数u1 和 u2 的更新需要四次除法,

13、交点坐标计算至多4次乘法。,6.7.2 Liang-Barsky 线段剪裁算法,LB线段剪裁算法 作业,已知线段的两个端点P1(-1,3)，P2(1,1)窗口边界x=0,x=2,y=0,y=2 用LB算法对线段进行剪裁,思想通过在剪裁窗口周围创立多个区域，从而避免对直线段进行多次剪裁。 适用范围仅仅适用于2D剪裁,6.7.3 Nicholl-Lee-Nicholl直线剪裁,算法步骤 从P1点向窗口的四个顶角点发出射线，这四条射线和窗口的四条边所在的直线一起将二维平面划分为更多的小区域 。,6.7.3 Nicholl-Lee-Nicholl直线剪裁,6.7.3 Nicholl-Lee-Nicho

14、ll直线剪裁,线段端点P1的三种位置,P1在窗口内,P1在窗口左边,P1在角区,情况 1：P1位于窗口内部，则设定四个剪裁区域 如果 P2 位于窗口内部，P1P2保留； 否则，计算所在区域边界交点P并保留P1P,L,T,B,R,P1,NLN直线剪裁,情况2： p1位于窗口左侧： 如果P2 位于窗口内部L区域，计算和左边界交点P并保留P1P； 如果 P2位于区域LT，计算直线与窗口左边界、上边界的交点并保留该线段部分。 同理处理P2位于区域LR、LB。 如果P2不在四个剪裁区域，舍弃整个线段。,L,LT,LB,LR,P1,L,L,情况3： p1位于窗口左上侧 区域划分有两种情况,P1,NLN直线

15、剪裁,p1位于窗口左上侧_情况1,if p2 位于窗口内部 L(T)区域，计算和左边( 上)界交点p并保留p1p； if p2位于LB，计算左、下边界交点并保留。同理处理TR、LR。 if p2不在四个剪裁区域，整个舍弃。,NLN直线剪裁,NLN直线剪裁,if p2 位于窗口内部L(T)区域，计算和左边( 上)界交点p并保留p1p； if p2位于LB，计算左、下边界交点并保留。同理处理TB、TR。 if p2不在四个剪裁区域，整个舍弃。,p1位于窗口左上侧_ 情况2,如何确定P2的位置?比较直线段P1P2的斜率和剪裁区域边界的斜率. mP1PTR mP1P2 mP1PTL,L,LT,LB,L

16、R,P1,L,L,NLN直线剪裁,PTL,PTR,PBL,PBR,直线段P1P2和窗口边界的交点计算 窗口边界x=xL,x=xR,y=yB,y=yT 根据直线段P1P2和窗口边界的位置关系，确定边界，带入参数方程,NLN直线剪裁,NLN直线剪裁算法,总结 求交前的检测为了避免过多的不必要的计算；NLN算法的最主要目的是： 对于必须求交点的情况，给出确定的相交边界，从而利用参数方程快速求取交点。,当窗口采用凸多边形时，任何一条线段只会至多有一段在窗口内： 当线段的两个端点全在窗口内时，该直线整个在窗口内 当线段的两个端点，一个在窗口内，一个在窗口外时，该直线部分在窗口内，部分在窗口外 当线段的两

17、个端点全在窗口外时，该直线可能整个在窗口外；也可能部分在窗口内，部分在窗口外,6.7.4非矩形裁剪窗口的线段剪裁,基于参数化直线方程的算法可以扩充到凸多边形凹多边形裁剪窗口如何处理？ 将凹多边形分解为一组凸多边形后再使用参数化裁剪算法,6.7.4非矩形裁剪窗口的线段剪裁,6.7.5 多边形的判定和处理,凸多边形判定 叉积法 旋转法 凹多边形分割,凸多边形判定叉积法,绕多边形的周长计算相邻边向量的叉乘 如果各叉积全部为零，则多边形各边共线； 如果各叉积一部分为正，一部分为负，则多边形为凹多边形； 如果所有叉积全部大于零或等于零，则多边形为凸多边形，此时沿着边的正向，内法矢量指向其左侧； 如果所有

18、叉积全部小于零或等于零，则多边形为凸多边形，此时沿着边的正向，内法矢量指向其右侧。,多边形凹凸性判定叉积法,凸多边形,+,+,+,+,内法线方向,x,y,凸多边形,内法线方向,x,y,多边形凹凸性判定叉积法,凹多边形,+,+,+,+,-,x,y,多边形凹凸性判定旋 转 法,绕多边形逆时针前进，将多边形顶点Vk平移到坐标原点，然后绕原点顺时针旋转，使下一个顶点Vk+1落在x轴上： 如果所有Vk+2的y分量为正，则多边形为凸多边形，否则多边形为凹多边形； 如果Vk+2的y分量为零，则Vk、Vk+1、Vk+2三点共线； 如果所有Vk+2的y分量为零，则多边形退化为一条直线。,多边形凹凸性判定旋 转

19、法,v1,v2,y,旋 转 法,y,x,分解凹多边形的向量方法,按逆时针方向计算多边形的边向量的叉积，并记录叉积结果Z分量的符号。如果Z分量变为负值，则多边形为凹多边形，可以沿叉乘向量对中的第一条边的延长线将多边形分解开。,分解凹多边形的向量方法,1,2,6,5,4,3,6.8 多边形的剪裁,剪裁前,6.8 多边形的剪裁,剪裁前,剪裁后,多边形的剪取可利用直线剪裁算法将多边形分解为若干条直线段，然后对直线进行剪裁。,未考虑多边形的封闭性,6.8 多边形的剪裁,利用直线剪裁算法对多边形进行剪裁存在的问题：如考虑多边形的封闭性，则一个窗口对一个多边形的剪裁可产生一个或者多个多边形。,剪裁前,剪裁后

20、,多边形剪裁,Sutherland-Hodgeman 多边形剪裁 Weiler-Atherton 算法,6.8 Sutherland-Hodgman 算法,思想 (亦称逐边裁剪算法)以多边形顶点为初始集合, 首先用窗口左边界剪裁多边形，产生新的顶点序列。新的顶点集依次传给右边界、下边界和上边界进行处理。 SH算法最终输出定义剪裁后的多边形边界的顶点序列。,6.8.1 Sutherland-Hodgman 多边形剪裁,通过对单一边界的裁剪来实现多边形的剪取。即在算法中，裁剪窗口的每一边将逐次对原多边形和每次剪取所生成的多边形进行剪取。 沿多边形依次处理顶点可能遇到的四种情况： 外-内 内-内 内

21、-外 外-外,6.8.1 Sutherland-Hodgman 多边形剪裁,举例,A,B,D,C,窗口左边界,情况1: 外-内 保存交点和第二点,V1,V2,V1,情况2: 内-内 保存第二点,V1,V2,情况3: 内-外 保存交点,V1,V2,V1,情况4: 外-外 不保存,V1,V2,例,例,例,窗口左边界,算法改进只有当窗口的四个边界都确定一个点在窗口内时才加入到输出顶点表中 Example(P188)程序实现,例,程序实现,小结： 对凸多边形应用本算法可以获得正确的裁剪结果 对凹多边形的裁剪将如图P191所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现

22、。 原因：只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。,6.8.1 Sutherland-Hodgman 多边形剪裁,解决方法： 把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形 修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。 使用Weiler-Altherton算法。,6.8.1 Sutherland-Hodgman 多边形剪裁,问题：SH算法适用于凸多边形,多余的线,Weiler-Atherton 算法,Weiler-Atherton 算法,按顺时针处理主多边形顶点： 规则： 对由外到内的顶点对，沿着多边形边界的方向 对有内到外的顶点对，按顺时针沿

23、着窗口边界的方向,v1,v1,v2,v3,v4,v5,v6,v3,v4,v5,文本是由字符组成的。 字符分类： 矢量字符 点阵字符 文本的剪裁按剪裁的精度分类： 字符串剪裁 字符剪裁 笔画剪裁等,6.10 文字的裁剪,6.10 文本剪裁,all-or-none string-clipping全有或全无字符串剪裁,裁剪前,STRING 1,STRING 2,裁剪后,STRING 2,all-or-none character-clipping全有或全无字符剪裁,ING 1,STRING 2,STRING 1,STRING 2,裁剪前,裁剪后,单字符剪裁 笔画剪裁是指在显示文本时，把窗口以外的字符予以剪裁，并且对与窗口相交的字符，也把其在窗口以外的部分予以剪裁。若是矢量字符，可以按直线的剪裁方法来剪裁与窗口相交的字符。若是点阵字符，则可按点的剪裁方法来剪裁与窗口相交的字符。,STRING 1,STRING 2,RING 1,STRING 2,裁剪前,裁剪后,6.11 外部剪裁,外部剪裁的定义：保留位于剪裁区域外的图形部分的剪裁过程 例多窗口系统,