第6章二维观察.ppt

《第6章二维观察.ppt》由会员分享，可在线阅读，更多相关《第6章二维观察.ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章二维观察 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望xyw1w2w3w4窗口6.1 2D 观察变换世界坐标系设备坐标系xyv1v2v3v4视口6.1.1 窗口&视口l l窗口的定义：常规图形系统中，世界坐标系中指定的用于显示的坐标区域。l l视口的定义：显示设备上用于窗口映射的坐标区域，也叫视区。l l观察变换：通常,世界坐标系中部分场景映射到设备坐标系的过程称为观察变换，也叫视像变换，或称为从窗口到视口的变换。l l窗口的另一种定义：窗口的另一种定义：

2、窗口管理系统中，任何可移动（窗口管理系统中，任何可移动（move about）、）、改变大小改变大小(resized)、激活激活(active)或变为无效或变为无效(inactive)的屏幕上的屏幕上的矩形区域。的矩形区域。6.1.2 2D 的观察流程WC将世界坐标转换为观察坐标使用建模坐标变换构造世界坐标场景使用窗口视区描述将观察坐标映射到规范化观察坐标将规范化视口映射到设备坐标MCVCNVCDC世界坐标-观察坐标的变换x0y0X世界y世界X观察Y观察世界坐标-观察坐标的变换M=R.Tx0y0X世界y世界X观察Y观察TR窗口到视口的坐标变换xyw1w2w3w4窗口(xw,yw)xyv1v2v

3、3v4视口(xv,yv)l l(Xw-W1)/(W2-W1)=(Xv-V1)/(V2-V1)(Yw-W3)/(W4-W3)=(Yv-V3)/(V4-V3)l lXv=AX+B Yv=CY+D A=(V2-V1)/(W2-W1)B=(W2*V1-W1*V2)/(W2-W1)C=(V4-V3)/(W4-W3)D=(W4*V3-W3*V4)/(W4-W3)窗口到视口的坐标变换窗口到视口的坐标变换l l变换矩阵：A 0 B 0 C D 0 0 1l l已知w1=10,w2=20,w3=40,w4=80,v1=80,v2=110,v3=10,v4=130,窗口中一点P(15，60)，求视口中的映射点Pl

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

5、口中显示一个圆，把它映射到视口中，下面哪些视口中图形不发生畸变。l l视口坐标 vx1 vx2 vy1 vy2 1 10 60 50 120 2 80 110 10 40 3 85 105 50 100 4 10 60 15 356.5 2D剪裁操作l l剪裁的定义识别图形在指定区域内或区域外的图形部分的过程l l剪裁窗口:用来剪裁对象的区域。l l剪裁时机l l针对窗口剪裁l l针对视口剪裁l l剪裁类型剪裁类型l l点剪裁点剪裁l l直线剪裁直线剪裁l l多边形剪裁多边形剪裁l l曲线剪裁曲线剪裁l l文本剪裁文本剪裁l l空白剪裁空白剪裁6.5 2D剪裁操作6.6 点的剪裁l l任何图形

6、都可能包含点、直线、字符、和多边形乃至直线，但它们都可以分解成点的集合。l l点的剪裁是图形剪裁中最基本的问题。6.6 点的剪裁 l l假设剪裁窗口是在标准位置的矩形窗口l l点P(x,y)如果满足下列不等式则保留：w1xw2，w3yw4l l否则，P点就在窗口外，被剪裁w1w2w3w4(x,y)6.7 线段的剪裁 P1P2P3P4P5P6P7P8P9P10剪裁前P3P4P5P6P7P8剪裁后l l线段与窗口的位置关系：l l整个线段全在窗口内；l l整个线段全在窗口外；l l线段部分在窗口外，部分在窗口内。6.7 线段的剪裁l l当线段的两个端点全在窗口内时，该直线整个在窗口内l l当线段的

7、两个端点，一个在窗口内，一个在窗口外时，该直线部分在窗口内，部分在窗口外l l当线段的两个端点全在窗口外时，该直线可能整个在窗口外；也可能部分在窗口内，部分在窗口外线段的剪裁l lCohen-Sutherland直线剪裁(CS算法)l lLiang-Barsky 直线剪裁(LB算法)l lNicholl-Lee-Nicholl 直线剪裁(NLN算法)l l非矩形剪裁窗口线段的剪裁6.7.1 Cohen-Sutherland 线段剪裁 l l思想：l l线段由端点标识；线段由端点标识；l l测试线段端点和窗口边界的关系以确定是否需测试线段端点和窗口边界的关系以确定是否需要计算交点要计算交点 l

8、l当当线段线段线段线段的两个端点全在窗口内时，该的两个端点全在窗口内时，该线段线段线段线段整个在窗整个在窗口内口内l l当当线段线段线段线段的两个端点，一个在窗口内，一个在窗口外的两个端点，一个在窗口内，一个在窗口外时，该时，该线段线段线段线段部分在窗口内，部分在窗口外部分在窗口内，部分在窗口外l l当当线段线段线段线段的两个端点全在窗口外时，该的两个端点全在窗口外时，该线段线段线段线段可能整个可能整个在窗口外，也可能部分在窗口内，部分在窗口外在窗口外，也可能部分在窗口内，部分在窗口外l l扩展窗口的边界将整个2D平面划分为9个区域l l每个区域赋予一个4位编码,称为区域码b3b2b1b000

9、0001100100010100100001100110001010上下右左w1w2w3w4CS算法 编码方案l l编码规则：b3b2 b1 b0l lb0=1 if x w2l lb2=1 if y w4000001100100010100100001100110001010w1w2w3w46.7.1 Cohen-Sutherland 线段剪裁=计算直线端点区域编码：c1 和 c2;=判断4c1 和 c2 均为0000，保留直线4c1&c2 不为零，同在某一边界外，删除该直线4c1&c2 为零，需要进一步求解交点=以左、右、下、上为序，找出端点区域码中第一位为1的位，将窗口边界方程x=w1/

10、w2或y=w3/w4带入直线方程，计算直线与窗口边界的交点，将交点和另一端点形成新的直线，重复上述过程，直至线段保留或删除CS 算法描述l l程序流程图程序流程图l l程序实现程序实现(P178)l l例例6.7.1 Cohen-Sutherland 线段剪裁 P3P41CS线段剪裁算法 举例000001100100010100100001100110001010132CS线段剪裁算法 举例P1P2000001100100010100100001100110001010l l 优点：简单，易于实现。l l 它可以简单的描述为将直线在窗口外边的部分删去，按左，右，下，上的顺序依次进行，处理之后，

11、剩余部分就是可见的了。此算法中求交点是很重要的，决定了算法的速度。CS线段剪裁算法小结:CS线段剪裁算法 作业l l已知线段的两个端点P1(-3/2,1/6)，P2(1/2,3/2)窗口边界x=-1,x=1,y=-1,y=1l l用CS算法对线段进行剪裁l l思想：以线段的中点作为线段的分割点 分别寻找直线段两个端点各自对应的最远的可见点线段的中点剪裁算法 l l步骤：在求线段与边界的交点时采用折半查找技术(与CS算法不同)，其余步骤同CSl l特点：中点分割剪裁是对于硬件很适合的，它可以用移位来代替除法，大大加快了速度。线段的中点剪裁算法 132线段的中点剪裁算法 P1P2000001100

12、100010100100001100110001010346.7.2 Liang-Barsky 线段剪裁算法l l思想：基于直线段参数方程分析的快速直线剪裁算法l l参数方程直线两端点 P1(x1,y1),P2(x2,y2)x=x1+(x2x1)uy=y1+(y2y1)u,0 u 16.7.2 Liang-Barsky 线段剪裁算法l l已知直线端点：起点P1(x1,y1),终点P2(x2,y2)l l参数方程：x=x1+(x2x1)uy=y1+(y2y1)u 其中:0u1P1P2u1l lLB算法推导如果直线在窗口内,则w1x1+dx*uw2w3y1+dy*uw4Pk*uQk k=1,2,3

13、,4P1=-dx,Q1=x1-w1 P2=dx,Q2=w2-x1P3=-dy,Q3=y1-w3 P4=dy,Q4=w4-y16.7.2 Liang-Barsky 线段剪裁算法l lLB算法描述算法描述l l计算计算 Pk,Qk,k=14l l判断是否存在判断是否存在Pk=0,如果存在如果存在,进一步进一步判断判断Qk Pk=0，表示直线平行于窗口某边界，表示直线平行于窗口某边界if Qk0，直线在窗口外，被剪裁，直线在窗口外，被剪裁else 直线在窗口内直线在窗口内l l对对 Pk!=0的情形的情形,用用Qk/Pk计算交点所对应的计算交点所对应的U值值6.7.2 LB线段剪裁算法l l对每条线

14、计算参数u1&u2u1=Max0,Qk/Pk,Pk 0l l如果u1 u2,则直线在窗口外，否则计算交点坐标6.7.2 Liang-Barsky 线段剪裁算法LB线段剪裁算法 举例l l已知线段的两个端点P1(3,4)，P2(8,2)窗口边界x=1,x=4,y=1,y=3l l用LB算法对线段进行剪裁LB线段剪裁算法 举例：已知线段的两个端点已知线段的两个端点(3,4)(3,4)，(8,2)(8,2)窗口边界窗口边界x=1,x=4,y=1,y=3x=1,x=4,y=1,y=3l l线段的参数方程 x=3+5ux=3+5u y=4-2u y=4-2ul lP1=-5,Q1=2,R1=-2/5P1

15、=-5,Q1=2,R1=-2/5P2=5,Q2=1,R2=1/5P2=5,Q2=1,R2=1/5P3=2,Q3=3,R3=3/2P3=2,Q3=3,R3=3/2P4=-2,Q4=-1,R4=1/2P4=-2,Q4=-1,R4=1/2l lu1=max(0,-2/5,1/2)=1/2u1=max(0,-2/5,1/2)=1/2u2=min(1,1/5,3/2)=1/5u2=min(1,1/5,3/2)=1/5l lu1u2 u1u2 所以线段全部被剪裁所以线段全部被剪裁l l算法实现(P181)l lLB与CS的比较LB 效率高于 CS,因为减少了交点计算次数。参数u1 和 u2 的更新需要四次

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

17、平面划分为更多的小区域。6.7.3 Nicholl-Lee-Nicholl直线剪裁6.7.3 Nicholl-Lee-Nicholl直线剪裁P1P1P1线段端点P1的三种位置P1在窗口内P1在窗口左边P1在角区情况 1：P1位于窗口内部，则设定四个剪裁区域如果 P2 位于窗口内部，P1P2保留；否则，计算所在区域边界交点P并保留P1PLTBRP1NLN直线剪裁情况2：p1位于窗口左侧：如果P2 位于窗口内部L区域，计算和左边界交点P并保留P1P；如果 P2位于区域LT，计算直线与窗口左边界、上边界的交点并保留该线段部分。同理处理P2位于区域LR、LB。如果P2不在四个剪裁区域，舍弃整个线段。L

18、LTLBLRP1LL情况3：p1位于窗口左上侧区域划分有两种情况P1NLN直线剪裁p1位于窗口左上侧_情况1 l lif p2 位于窗口内部 L(T)区域，计算和左边(上)界交点p并保留p1p；l lif p2位于LB，计算左、下边界交点并保留。同理处理TR、LR。l lif p2不在四个剪裁区域，整个舍弃。NLN直线剪裁LTLBTRP1LLRNLN直线剪裁l lif p2 位于窗口内部L(T)区域，计算和左边(上)界交点p并保留p1p；l lif p2位于LB，计算左、下边界交点并保留。同理处理TB、TR。l lif p2不在四个剪裁区域，整个舍弃。p1位于窗口左上侧_ 情况2 TTLBTR

19、P1LTBl l如何确定P2的位置?比较直线段P1P2的斜率和剪裁区域边界的斜率.mP1PTR mP1P2-内内l l内内-内内l l内内-外外l l外外-外外6.8.1 Sutherland-Hodgman 多边形剪裁 l举例ABDC窗口左边界l l情况情况1:外-内l l保存交点和第二点V1V2V1l l情况2:内-内l l保存第二点V1V2l l情况3:内-外l l保存交点V1V2V1l l情况4:外-外l l不保存 V1V2l l例例123456窗口左边界l l例例12345612345窗口左边界l l例例12345612345窗口左边界l l算法改进算法改进 只有当窗口的四个边界只有

20、当窗口的四个边界都确定一个点在窗口内都确定一个点在窗口内时才加入到输出顶点表时才加入到输出顶点表中中l lExample(P188)l l程序实现程序实现 l l例V1V2V3V2V1V3V1V2V3V2V2V3l l程序实现程序实现 小结：l l对凸多边形应用本算法可以获得正确的裁剪结果l l对凹多边形的裁剪将如图P191所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。l l原因：只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。6.8.1 Sutherland-Hodgman 多边形剪裁 l l解决方法：l l把凹多边形分割成若干个凸多边形，然

21、后分别处理各个凸多边形l l修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。l l使用Weiler-Altherton算法。6.8.1 Sutherland-Hodgman 多边形剪裁 l l问题：SH算法适用于凸多边形算法适用于凸多边形多余的线Weiler-Atherton 算法Weiler-Atherton 算法l l按顺时针处理主多边形顶点：l l规则：l l对由外到内的顶点对，沿着多边形边界的方向l l对有内到外的顶点对，按顺时针沿着窗口边界的方向v1v1v2v3v4v5v6v3v4v5l l文本是由字符组成的。l l字符分类：l l矢量字符矢量字符l l点阵字符点阵字

22、符l l文本的剪裁按剪裁的精度分类：l l字符串剪裁字符串剪裁l l字符剪裁字符剪裁l l笔画剪裁等笔画剪裁等6.10 文字的裁剪6.10 文本剪裁 l lall-or-none string-clipping 全有或全无字符串剪裁裁剪前STRING 1STRING 2裁剪后STRING 2l lall-or-none character-clipping 全有或全无字符剪裁全有或全无字符剪裁ING 1STRING 2STRING 1STRING 2裁剪前裁剪后l l单字符剪裁单字符剪裁l l笔画剪裁是指在显示文本时，把窗口以外的字符予以剪裁，笔画剪裁是指在显示文本时，把窗口以外的字符予以剪裁

23、，笔画剪裁是指在显示文本时，把窗口以外的字符予以剪裁，笔画剪裁是指在显示文本时，把窗口以外的字符予以剪裁，并且对与窗口相交的字符，也把其在窗口以外的部分予以并且对与窗口相交的字符，也把其在窗口以外的部分予以并且对与窗口相交的字符，也把其在窗口以外的部分予以并且对与窗口相交的字符，也把其在窗口以外的部分予以剪裁。若是矢量字符，可以按直线的剪裁方法来剪裁与窗剪裁。若是矢量字符，可以按直线的剪裁方法来剪裁与窗剪裁。若是矢量字符，可以按直线的剪裁方法来剪裁与窗剪裁。若是矢量字符，可以按直线的剪裁方法来剪裁与窗口相交的字符。若是点阵字符，则可按点的剪裁方法来剪口相交的字符。若是点阵字符，则可按点的剪裁方法来剪口相交的字符。若是点阵字符，则可按点的剪裁方法来剪口相交的字符。若是点阵字符，则可按点的剪裁方法来剪裁与窗口相交的字符。裁与窗口相交的字符。裁与窗口相交的字符。裁与窗口相交的字符。STRING 1STRING 2RING 1STRING 2裁剪前裁剪后6.11 外部剪裁l l外部剪裁的定义：保留位于剪裁区域外的图形部分的剪裁过程l l例 多窗口系统