计算机图形学-第六章.ppt

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,第六章、二维观察,（a）,（b）,已知，有两个坐标系,a,、,b,。构造一个矩阵，将坐标系,a,蓝色矩形框中的点,(xw,yw),映射到坐标系,b,中蓝色矩形框中。注意，矩阵变换使用列向量。,第六章、二维观察,二维观察流水线,裁剪窗口,规范化和视口变换,OpenGL,二维观察函数,裁剪算法,二维点裁剪,二维线裁剪,多边形填充区裁剪,曲线裁剪,坐标系,世界坐标系（,W,orld,C,oordinates,）,用户处理自己的对象时所采用的坐标系，坐标系的大小及尺寸由用户自己定义。,设备坐标系（,D,evice,C,oordinates,）,与图形显示设备相关的坐标系。如显示器或打印机的坐标系。,规范化坐标系（,N,ormal,D,evice,C,oordinates,）,它是独立于具体的物理设备的一种坐标系，其坐标空间限定在（,0.0,，,0.0,）到（,1.0,，,1.0,）的坐标范围内。,二维观察流水线,裁剪窗口,二维场景中要显示的部分称为裁剪窗口。,视口,显示设备上用于显示裁剪窗口中图形内容的区域称为视口。,二维观察流水线,变焦距效果,整体放缩效果,漫游效果,把固定大小的裁剪窗口在一幅大图形上移动，视口不变，可以产生漫游的效果。,二维观察流水线,二维观察变换流水线,使用建模坐标变换构造世界坐标系场景,将世界坐标转换为摄像坐标,将摄像坐标转换为规范化设备坐标,将规范化设备坐标映射到设备坐标,MC,WC,VC,NC,DC,世界坐标系到观察坐标系的变换矩阵,世界坐标系到摄像坐标系的变换,（,1,）点变换等于坐标系相反方向的变换,（,2,）将摄像坐标系原点移动到世界坐标系原点,（,3,）绕原点旋转使两坐标系重合,规范化和视口变换,裁剪窗口到规范化视口的映射,在这种映射中，规范化坐标系对应显示设备。,裁剪窗口,规范化坐标系,视口,规范化和视口变换,变换方法,规范化和视口变换,裁剪窗口到规范化坐标系的映射,在这种映射中规范化坐标系对应裁剪窗口,裁剪窗口,规范化坐标系,视口,规范化和视口变换,变换方法,摄像坐标系和裁剪窗口,（,a,）,标准化设备坐标系,（,b,）,设备坐标系和视口,（,c,）,1.,以点 为中心进行缩放变换，将裁剪窗口变换成标准化正方形大小,2.,将标准化正方形映射到平面指定的视口中。,规范化和视口变换,变换方法,OpenGL,中的二维观察变换,(1),指定矩阵栈,glMatrixMode(GL_PROJECTION);,glLoadIdentity();,(2),指定裁剪窗口,gluOrtho2D(0,w,0,h);,(3),指定视口,glViewport(0,0,w,h);,二维点裁剪,二维点裁剪,点的裁剪是图形裁剪的基础，点在窗口内的条件如下：,二维线裁剪,实交点与虚交点,实交点是直线段与窗口矩形边界的交点。虚交点则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点。,二维线裁剪,Cohen-Sutherland,算法,中点分割算法,Liang-Barsky,算法,Cohen-Sutherland,算法,编码,对于任一端点,(x,y),，根据其坐标所在的区域，赋予一个位的二进制码,D,3,D,2,D,1,D,0,。编码规则如下图所示：,(1),若 ，则,D,0,=1,，否则,D,0,=0,；,(2),若,，则,D,1,=1,，否则,D,1,=0,；,(3),若,，则,D,2,=1,，否则,D,2,=0,；,(4),若,，则,D,3,=1,，否则,D,3,=0,。,上,下,右,左,1,0,0,1,Cohen-Sutherland,算法,裁剪,裁剪一条线段时，先求出端点,p1,和,p2,的编码,code1,和,code2,，然后,(1),若,code1|code2=0,，对直线段应简取之。,(2),若,code1&code20,，对直线段可简弃之。,(3),若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。,Cohen-Sutherland,算法,算法步骤,(1),输入直线段的两端点坐标：,p1(x1,y1),、,p2(x2,y2),，以及窗口的四条边界坐标。,(2),对,p1,、,p2,进行编码：点,p1,的编码为,code1,，点,p2,的编码为,code2,。,(3),若,code1|code2=0,，对直线段应简取之，转,(6),；否则，若,code1&code20,，对直线段可简弃之，转,(7),；当上述两条均不满足时，进行步骤,(4),。,(4),确保,p1,在窗口外部：若,p1,在窗口内，则交换,p1,和,p2,的坐标值和编码。,(5),根据,p1,编码从低位开始找码为,1,处，从而确定,p1,在窗口外的哪一侧，然后求出直线段与相应窗口边界的交点，并用该交点的坐标值替换,p1,的坐标值。也即在交点,s,处把线段一分为二，并去掉,p1s,这一段。考虑到,p1,是窗口外的一点，因此可以去掉,p1s,。转,(2),。,(6),用直线扫描转换算法画出当前的直线段,p1p2,。,(7),算法结束。,Cohen-Sutherland,算法,举例,Cohen-Sutherland,算法,举例,中点分割算法,算法步骤,(1),若,code1|code2=0,，对直线段应简取之，结束；否则，若,code1&code20,，对直线段可简弃之，结束；当这两条均不满足时，进行步骤,(2),。,(2),找出该直线段离窗口边界最远的点和该直线段的中点。判中点是否在窗口内：若中点不在窗口内，则把中点和离窗口边界最远点构成的线段丢掉，以线段上的另一点和该中点再构成线段求其中点；如中点在窗口内，则又以中点和最远点构成线段，并求其中点，直到中点与窗口边界的坐标值在规定的误差范围内相等，则该中点就是该线段落在窗口内的一个端点坐标。,(3),如另一点在窗口内，则经,(2),即确定了该线段在窗口内的部分。如另一点不在窗口内，则该点和所求出的在窗口上的那一点构成一条线段，重复步骤,(2),，即可求出落在窗口内的另一点。,Liang-Barsky,算法,(,参数方程法,),直线的参数方程,设线段的两个端点为 参数方程如下：,其中，。，参数,u,取,0,1,之间的值。当,u,0,时 ，当,u=1,时 。如果点 处于裁剪窗口内：,Liang-Barsky,算法,(,参数方程法,),令：,有不等式：,Liang-Barsky,算法,(,参数方程法,),直线与窗口边界的相对位置：,1,、直线段与窗口边界平行，其 ，,k,表示取哪一条边（,k=1,2,3,4,，分别对应左、右、下、上）。如果对某一,k,值，还满足 ，则此直线完全在边界外，可不考虑；如果 ，此线段在边界内。,Liang-Barsky,算法,(,参数方程法,),2,、如果 ，此时把直线从 到 的连线方向作为正向，将此直线无限延伸，同时把把窗口边界无限延伸；然后分以下两种情况进行讨论,Liang-Barsky,算法,(,参数方程法,),（,a,）当 时，则是由窗口边界延伸线的外部发出的一条直线进入相应窗口边界延伸线的内部。,（,b,）当 时，则是由窗口边界延伸线的内部发出的一条直线进入相应窗口边界延伸线的外部。,Liang-Barsky,算法,(,参数方程法,),直线与窗口边界的交点,当 时，可以用下式计算一参数,u,，此,u,值代入直线的参数方程所得点,(x,y),，是直线延长线与窗口边界,k,的延长线的交点。,对于每条直线，可计算出一对,u,值 ，通过这两个参数可以判断直线是如何裁剪的。,Liang-Barsky,算法,(,参数方程法,),的值可由从窗口边界外出发进入窗口边界内的直线 所涉及窗口边界确定。对于这些窗口边界可计算出各 ，取 中最大值为,的值可由从窗口边界内发出进入窗口边界外的直线 所涉及窗口边界确定。对于这些窗口边界可计算出各 ，取 中最小值为 。,Liang-Barsky,算法,(,参数方程法,),如果 ，则此直线全部在窗口外部可排除，反之，此直线在窗口内，可由 计算出被裁剪直线的端点。,多边形裁剪,问题,直接用直线段裁剪算法对多边形的每条边进行裁剪，会得到如下图,b,的结果，而实际结果应该如下图,c,所示。,（a）裁剪前,（,b,）直接采用直线段裁剪的结果,（c）正确的裁剪结果,Sutherland-Hodgeman,多边形裁剪算法,基本思想,将多边形的边界作为一个整体，每次用窗口的一条边界作为裁剪边,以裁剪边及其延长线构成裁剪线，将平面区域分成内侧半平面（称为可见侧）和外侧半平面（又叫非可见侧）。,Sutherland-Hodgeman,多边形裁剪算法,1)P1,不可见，,P2,可见，则输出线段,P1P2,与裁剪边界的交点和,P2,点。,2)P1P2,均在可见侧，输出,P,2,；,3)P,1,可见，,P,2,不可见，则输出线段,P,1,P,2,与裁剪边界的交点；,4)P,1,P,2,均在不可见侧，没有输出；,P1,P2,I,输出焦点,I,与,P2,可见,P1,P2,输出,P2,可见,P1,P2,输出,I,I,可见,P1,P2,不输出,可见,Sutherland-Hodgeman,多边形裁剪算法,实例,Sutherland-Hodgeman,多边形裁剪算法,实例,Sutherland-Hodgeman,多边形裁剪算法,特点,可以正确地裁剪凸多边形，但裁剪凹多边形会出现如下图所示的问题。即由于多边形是当作一个整体被裁剪的，若裁剪结果出现多个多边形时，,Sutherland-Hodgeman,多边形裁剪不能获得正确的结果,裁剪前,裁剪后,V,1,AV,2,V,3,EDV,4,Weiler-Atherton,多边形裁剪算法,基本思想,（,1,）,假设被裁剪多边形和裁剪窗口的顶点序列都按顺时针方向排列。当两个多边形相交时，交点必然成对出现，其中一个是从被裁剪多边形进入裁剪窗口的交点，称为“入点”，另一个是从被裁剪多边形离开裁剪窗口的交点，称为“出点”。,（,2,）算法从被裁剪多边形的一个入点开始，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点序列；,（,3,）而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。,（,4,）按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。,（,5,）由于可能存在分裂的多边形，因此算法要考虑：将搜集过的入点的入点记号删去，以免重复跟踪。将所有的入点搜集完毕后算法结束。,Weiler-Atherton,多边形裁剪算法,算法步骤：,1,、顺时针输入被裁剪多边形顶点序列,放入数组,1,中。,2,、顺时针输入裁剪窗口顶点序列,放入数组,2,中。,3,、求出被裁剪多边形和裁剪窗口相交的所有交点，并给每个交点打上“入”、“出”标记。,然后将交点按顺序插入序列,得到新的顶点序列,，并放入数组,3,中；,同样也将交点按顺序插入序列,得到新的顶点序列,，放入数组,4,中；,4,、,初始化输出数组,Q,，令数组,Q,为空。接着从数组,3,中寻找“入”点。,如果“入”点没找到，程序结束。,5,、,如果找到“入”点，则将“入”点放入,S,中暂存。,6,、,将“入”点录入到输出数组,Q,中。并从数组,3,中将该“入”点的“入”点标记删去。,7,、,沿数组,3,顺序取顶点：,如果顶点不是“出点”，则将顶点录入到输出数组,Q,中，流程转第,7,步。否则，转第,8,步。,8,、,沿数组,4,顺序取顶点：,如果顶点不是“入点”，则将顶点录入到输出数组,Q,中，流程转第,8,步。否则，转第,9,步。,9,、,如果顶点不等于起始点,S,，流程转第,6,步，继续跟踪数组,3,。否则，将数组,Q,输出；,流程转第,4,步，寻找可能存在的分裂多边形。,Weiler-Atherton,多边形裁剪算法,例子,Weiler-Atherton,多边形裁剪算法,例子,请写出使用,Weiler-Atherton,多边形裁剪算法对下图进行裁剪的流程。,Weiler-Atherton,多边形裁剪算法,特点,1,、裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。,2,、可实现被裁剪多边形相对裁剪窗口的内裁或外裁，即保留窗口,内的图形或保留窗口外的图形，因此在三维消隐中可以用来处,理物体表面间的相互遮挡关系。,3,、裁剪思想新颖，方法简洁，裁剪一次完成，与裁剪窗口的边数,无关。,谢谢,!,