第6章2二维观察及裁剪

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,6.4 两维观察,6.4.1 基本概念,在计算机图形学中，将在用户坐标系中需要进行观察和处理的一个坐标区域称为,窗口,（,Window）,将窗口映射到显示设备上的坐标区域称为,视区,（,Viewport）,要将窗口内的图形在视区中显示出来，必须经过将窗口到视区的变换（,Window-Viewport Transformation）,处理，这种变换就是,观察变换,）,。,观察坐标系(,View Coordinate),和规格化设备坐标系(,Normalized Device Coordinate),观察坐标系,是依据窗口的方向和形状在用户坐标平面中定义的直角坐标系。,规格化设备坐标系,也是直角坐标系，它是将二维的设备坐标系规格化到（0.0，0.0）到（1.0，1.0）的坐标范围内形成的。,引入了观察坐标系和规格化设备坐标系后，观察变换分为如下图所示的几个步骤，通常称为,二维观察流程,。,变焦距效果,整体放缩效果,漫游效果,6.4.3 窗口到视区的变换,要将窗口内的点（,x,w,y,w,）,映射到相对应的视区内的点（,x,v,y,v,）,需进行以下步骤：,(1)将窗口左下角点移至用户系统系的坐标原点,(2)针对原点进行比例变换,(3)进行反平移,6.5 裁剪,在二维观察中，需要在观察坐标系下对窗口进行,裁剪,，即只保留窗口内的那部分图形，去掉窗口外的图形。,假设,窗口是标准矩形，即边与坐标轴平行的矩形，由上（,y=wyt）、,下（,y=wyb）、,左（,x=wxl）、,右（,x=wxr）,四条边描述。,6.5.1 点的裁剪,(wxl,wyb),(wxr,wyt),P,6.5.2 直线段的裁剪,假定,直线段用,p,1,(x,1,y,1,)p,2,(x,2,y,2,),表示。,直线段和剪裁窗口的可能关系：,完全落在窗口内,完全落在窗口外,与窗口边界相交,实交点,是直线段与窗口矩形边界的交点。,虚交点,则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点。,1.,Cohen-Sutherland,算法,基本思想,：对每条直线段,p,1,(x,1,y,1,)p,2,(x,2,y,2,),分三种情况处理：,(1)直线段完全可见，“简取”之。,(2)直线段完全不可见，“简弃”之。,(3)直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。,编码,：对于任一端点(,x,y)，,根据其坐标所在的区域，赋予一个4位的二进制码,D,3,D,2,D,1,D,0,。(,上下右左,),编码规则如下：,若,xwxr，,则,D,1,=1，,否则,D,1,=0；,若,ywyt，,则,D,3,=1，,否则,D,3,=0。,裁剪,裁剪一条线段时，先求出端点,p,1,和,p,2,的编码,code1,和,code2，,然后：,(1)若,code1|code2=0，,对直线段应简取之。,(2)若,code1&code20，,对直线段可简弃之。,(3)若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。,求交,：假定直线的端点坐标为(,x,1,y,1,),和(,x,2,y,2,),左、右边界交点的计算：,上、下边界交点的计算：,算法的步骤,：,(1)输入直线段的两端点坐标：,p,1,(x,1,y,1,)、p,2,(x,2,y,2,)，,以及窗口的四条边界坐标：,wyt、wyb、wxl,和,wxr。,(2),对,p,1,、p,2,进行编码：点,p,1,的编码为,code1，,点,p,2,的编码为,code2。,(3),若,code1|code2=0，,对直线段应简取之，转(6)；否则，若,code1&code20，,对直线段可简弃之，转(7)；当上述两条均不满足时，进行步骤(4)。,(4)确保,p,1,在窗口外部：若,p,1,在窗口内，则交换,p,1,和,p,2,的坐标值和编码。,(5),按左、右、上、下的顺序求出直线段与窗口边界的交点,，并用该交点的坐标值替换,p,1,的坐标值。,也即在交点,s,处把线段一分为二，并去掉,p,1,s,这一段。,考虑到,p,1,是窗口外的一点，因此可以去掉,p,1,s。,转(2)。,(6)用直线扫描转换算法画出当前的直线段,p,1,p,2,。,(7),算法结束。,例如,：,特点,：,2.中点分割算法,基本思想,：,当对直线段不能简取也不能简弃时，简单地把线段等分为二段，对两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口外。,中点分割算法的,核心思想,是,通过二分逼近来确定直线段与窗口的交点,。,与,Cohen-Sutherland,算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。,A,、,B,分别为距,P,0,、,P,1,最近的可见点，,Pm,为,P,0,P,1,中点。,特点：以求直线的中点来代替求两直线的交点，只需进行整数的简单加法和运算器右移实现除法，避免做大量的乘除法,从,P,0,出发找距离,P,0,最近可见点采用中点分割方法,先求出,P,0,P,1,的中点,P,m,若,P,0,P,m,不是显然不可见的，并且,P,0,P,1,在窗口中有可见部分，则距,P,0,最近的可见点一定落在,P,0,P,m,上，所以用,P,0,P,m,代替,P,0,P,1,；,否则取,P,m,P,1,代替,P,0,P,1,。,再对新的,P,0,P,1,求中点,P,m,。重复上述过程，直到,P,m,P,1,长度小于给定的控制常数为止，此时,P,m,收敛于交点。,从,P1,出发找距离,P,1,最近可见点采用上面类似方法。,6.5.3 多边形的裁剪,问题的提出：,多边形的裁剪比直线的裁剪要复杂,：,1,）边界不再封闭，需要用窗口边界的恰当部分来封闭它，,如何确定其边界？,算法实施策略,：,为窗口各边界裁剪的多边形存储输入与输出顶点表。在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界继续裁剪。,窗口的一条边以及延长线构成的裁剪线把平面分为两个区域，包含有窗口区域的一个域称为,可见侧,；不包含窗口区域的域为,不可见侧,。,1.,Sutherland-Hodgeman,多边形裁剪,沿着多边形依次处理顶点会遇到四种情况：,逐边裁剪法,，基本思想,一次用窗口的一条边裁剪多边形,输入：,ABCDEFGH,A,B,C,D,E,F,G,H,输出：,12DEFGHA,1,2,(a),用左边界裁剪,输出：,34D56FGHA1,A,D,E,F,G,H,输入：,12DEFGHA,1,2,(b),用下边界裁剪,3,4,5,6,输入：,34D56FGHA1,A,D,F,G,H,1,(c),用右边界裁剪,3,4,5,6,输出：,4D5678GHA13,7,8,A,D,G,H,1,(d),用上边界裁剪,3,4,5,6,7,8,输入：,4D5678GHA13,输出：,D56789IHJK34,9,I,J,K,缺点：,S-H,法可以处理凸多边形和凹多边形的裁剪，但只能对裁剪后仍为一个连通图的凹多边形产生正确的裁剪效果。对裁剪后产生两个或多个分离部分的凹多边形会产生一些多余的边。,A,E,D,C,B,A,E,D,C,B,V1,V2,V3,V4,F,F,输出：,A-V1-V4-D-E-V3-V2,-A,输入：,A-B-C-D-E-F,-A,2.,Weiler-Atherton,多边形裁剪,假定,按顺时针方向处理顶点，且将用户多边形定义为,Ps，,窗口矩形为,Pw。,算法从,Ps,的任一点出发，跟踪检测,Ps,的每一条边，当,Ps,与,Pw,相交时（实交点），按如下规则处理：,(1)若是由不可见侧进入可见侧，则输出可见直线段，转(3)；,(2)若是由可见侧进入不可见侧，则从当前交点开始，沿窗口边界顺时针检测,Pw,的边，即用窗口的有效边界去裁剪,Ps,的边，找到,Ps,与,Pw,最靠近当前交点的另一交点，输出可见直线段和由当前交点到另一交点之间窗口边界上的线段，然后返回处理的当前交点；,(3)沿着,Ps,处理各条边，直到处理完,Ps,的每一条边，回到起点为止。,下图示了,Weiler-Atherton,算法裁剪凹多边形的过程和结果。,6.5.4 其它裁剪,1.曲线边界对象的裁剪,曲线边界对象与矩形窗口和多边形窗口的裁剪,加速方法,2.,字符裁剪,串精度,:,将包围字串的外接矩形对窗口作裁剪,字符精度,:,将包围字的外接矩形对窗口作裁剪,以及笔画,象素精度,:,将笔划分解成直线段对窗口作裁剪,待裁剪字符串 串精度裁剪 字符精度裁剪 象素精度裁剪,3.外部裁剪,保留落在裁剪区域外的图形部分、去掉裁剪区域内的所有图形，这种裁剪过程称为,外部裁剪,，也称,空白裁剪,。,