计算机图形学-10、隐藏面的消除.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章 真实图形,三维世界中的物体之间存在遮挡关系。,为了真实表现三维场景，必须体现出这种遮挡关系。,三维物体的三种模型：线框模型，表面模型，实体模型。,线框模型：涉及隐藏线的消隐。,表面模型：涉及隐藏面的消隐。,实体模型：只需考虑实体表面的问题，与表面模型相似,基本概念与基本方法,面消隐算法的基本思想：沿着视线方向，寻找物体上的像素，只有离观察点最近的像素被显示。,若以像素为单位逐一判断，效率太低。常用的方法是以面为单位，显示离观察点最近的面。,场景无限，显示窗口有限。只有能落入窗口范围内的物体，才有显示的可能。为了减少计算量，在三维空间中设置一个包围盒，包围盒内的物体能够显示在窗口中，包围盒外的物体不用考虑。,基本概念与基本方法,前面的平面不一定遮挡或完全遮挡后面的平面，这样就要将不被遮挡的部分显示出来。,判断两个物体是否相互遮挡，可以在物体投影到窗口平面后，用物体投影的边界盒是否相交来判断,投影规范化,消隐与投影有密切的关系，同样的一组物体，投影的方式不一样，投影与消隐的结果不一样。,消隐是在投影完成后进行的，是在二维投影平面进行,为了简化消隐处理，在消隐前将各种投影转化为正射（平行）投影。,投影的规范化,将点,p(x,y,z),投影的结果,(x,p,y,p,),，看作是点,p(x,p,y,p,z),。即将点,p,的,z,直接赋予点,p,，就完成了投影的规范化。,斜平行投影规范化,透视投影规范化,1.,线框图消隐（隐藏线消隐）,物体用线框图形表示，才会出现隐藏线消隐问题。,1.,线框图消隐（隐藏线消隐）,物体是由多个面围成的，可以将一个物体分解成多个面。,线框图形是用棱线来表示物体，棱线是两个面的交线,每个面都用多边形来表示，多边形用顶点表示，多边形的边就是棱线,减少计算量的方法,位于一条棱线后面的物体不可能遮挡该棱线,用三维边界盒判断,Z,min,线,Z,max,体,投影线,Z,Y,Z,max,体,Z,min,线,减少计算量的方法,后向面（自隐藏面）可以全部去掉。,后向面：面的外法线方向与,Z,轴成钝角,其它的面都是可能的遮挡面,交点计算方法,投影线段参数方程表示,设两直线段分别为,P1P2,、,P3P4,，如图中所示。,其参数方程：,两直线的交点,交点计算方法,两直线的交点应满足：,求得：,交点计算方法,若参数值同时满足,0u1,，,0v1,，则两线段有交点，代入公式（,8-1,）或者（,8-2,）即可求得交点坐标（,x,，,y,）。否则无交点。,可见部分确定,当一根线的所有交点都求处，就可以确定可见部分了。,将所有交点按照参数从小到大排列；对应参数为：,l,1,l,2,l,3,l,k,。,设不可见阶参数,ivord=0,。,P,Q,j1,j2,j3,j4,j5,j6,j7,j8,可见部分确定,线段起点,P,处的不可见阶,ivord,的确定方法：分别考虑线段,PQ,与所有多边形的第一个交点，如果为“出点”，,ivord,加,1,；如果为“进点”，,ivord,不变。,如果,P,处,ivord=0,，则,PJ1,段可见，否则，不可见。,J1,的不可见阶,ivord,，若,J1,为“出点”，,ivord,减,1,；若,J1,为“进点”，,ivord,加,1,。,若,ivord,不为,0,，则,J1J2,段不可见，否则可见。,按照,5,、,6,依次处理余下的各个交点，直到每一段可见性判断完毕。,2.,曲面隐藏线消除,这里的曲面特指由方程,z=f(x,y),表示的曲面，如,DEM,表示的地形,2.,曲面隐藏线消除,DEM,与影像数据类似，有排列整齐的点阵数据阵列组成,数据所在的行列表明位置信息，用,(x,y),表示，数据本身,z,表示高程值,这种曲面的绘制方法是将每个高程,z=f(x,y),看成三维空间中的一个空间点,(x,y,z),，将每一行、每一列的空间点分别投影后连接起来，构成空间曲面,为了真实，必须消除被遮挡的曲线部分,2.,曲面隐藏线消除,不做消隐的绘制方法,将每一行（列）的数据看作空间点,(x,y,z),依次投影到投影平面得到投影点,(xp,yp),将各个投影点依次连接起来的,2.,曲面隐藏线消除,做消隐的绘制方法,绘制空间点连线的方法同前一种方法，只是绘制次序有规定,绘制次序是按照距离视点的远近，从近到远依次绘制,为了只绘制未被遮挡的曲线部分，设置一个高度记录器，依次记录已绘制的最高点值,y,p,值,只有超出,高度,记录器的曲线部分被绘制，并且其高度值,y,p,值代替原有的,高度,值记录进记录器,2.曲面隐藏线消除,考虑到前行（列）可以遮挡后列（行），依据,离视点的远近程度,，按照,从前到后（行）、从左到右（列）的顺序，交替绘制行、列曲线,其中,超出高度记录器,范围的曲线被绘制,，并且其高度记录进,高度,记录器，未,超出的部分不绘制,2.曲面隐藏线消除,高度记录器为一个一维数组，数组单元数量与显示器视区宽度相同，即每个单元对应于一个像素，也就是每个单元对应于,X,轴整数部分,相邻两个空间点投影坐标,(xp,i,yp,i,),、,(xp,i+1,yp,i+1,),中的,yp,值必须线性内插到,x,整数坐标上,2.曲面隐藏线消除,为了不遮挡“漏斗”型曲面，设置两个高度记录器，分别记录最大最小值,3.,画家算法,算法的基本思想是：先将场景中的物体按其距观察点的远近进行排序，排序结果存在一张深度优先表中。距观察点远者称其优先级低，放在表头；距观察点近者称其优先级高，放在表尾。按照从表头到表尾的顺序逐个绘制物体，近的物体后画，覆盖了先画的远的物体，产生了正确的遮挡关系。,3.,画家算法,1,2,3,4,1,2,4,3,优先级表,绘图顺序,视线方向,u,v,n,3.,画家算法,用三维包围盒确定能够投影到窗口的空间范围，除去包围盒以外的物体。,每个物体去除后向面，只剩下前向面，每个前向面用多边形顶点表示。,画家算法的关键和难点在于如何对多边形按远近进行排序。,3.,画家算法,每个多边形顶点中，最大的纵坐标,z,值用,z,max,表示,最小的纵坐标,n,值用,z,min,表示,;,根据每个多边形的,z,min,对它们进行预排序，并放入优先级表中；这样大部分多边形都是按照远近关系得到排序，但有少量特例例外。,例外,视线,n,3.,画家算法,为了排除例外，需要逐个判断多边形之间的远近关系。,设,P,是在优先级表中排列第一的多边形，,Q,为任意一个其他多边形。,Q,与,P,进行比较。,3.,画家算法,若,z,max,(P)z,min,(Q),，,P,确实是比,Q,距离视线更远。,Q,在,P,的前向面，,P,确实是比,Q,距离视线更远。,Q,在,P,的后向面，,P,比,Q,距离视线更近，需要交换,P,、,Q,的位置。,视线,z,轴,z,min,(Q),z,max,(P),视线,前向,后向,3.,画家算法,前、后向面判别方法：,平面上任意一点与另一平面任意顶点作一连线，平面的法线矢量与该连线的夹角小于,90,度，那个平面位于该平面的前向面一边；否则位于后向面一边。,平面法矢,4.Z,缓冲器算法,画家算法需要对多边形排序，计算量大,Z,缓冲器算法简单稳定，利于硬件实现。,Z,缓冲器是一组存储单元，其单元个数与屏幕上的像素个数相同，与帧缓冲器（显存）单元个数相同。它们三者存在一一对应的关系。,4.Z,缓冲器算法,Z,缓冲器算法为每一个要填入的像素，不光准备颜色值，还准备一个深度值。,屏幕上像素的显示颜色由对应的帧缓冲器单元中的数值决定，该像素对应的,z,值存储在,Z,缓冲器对应单元中。,有多个空间物体对应同一个显示像素。一个颜色值是否能填入显示缓冲器像素，取决于该颜色值所对应的深度值是否大于当前缓冲器中的深度值。,4.Z,缓冲器算法,视线方向,u,v,n,深度值的获取：,由多边形的任意三个顶点，可以确定平面方程；,将多边形投影到投影平面，并着色；,在着色的过程中可以确定多边形的每一个内点坐标；,由内点坐标和平面方程可以确定内点对应的纵坐标（深度值）。,4.Z,缓冲器算法,Z,缓冲器算法的缺点是需要太多的缓冲存储空间，要准备一个与屏幕像素对应的深度,Z,值存储空间。,对于当前的计算机（或显卡），不成问题。但在该算法提出的当年，是一个大问题。,当时为了克服这一问题，提出了扫描线,Z,缓冲器算法。,5.,扫描线,Z,缓冲器算法,Z,缓冲器算法的缺点是需要很大的,Z,缓冲器；每一点处都需要计算它的纵坐标值，计算量大。,为了克服第一个缺点，可以把整个显示平面分成若干个区域，一区一区来显示，这样,Z,缓冲器的单元数只要等于一个区域的像素个数。,如果把区域变成显示屏幕的一行，就得到扫描线,Z,缓冲器算法。,5.,扫描线,Z,缓冲器算法,缓冲区由区域变成水平扫描线，问题发生质的变化：,使用一个多边形表,(PT),对所有的多边形排序、分类；,使用一个活化多边形表,(APT),列出与当前扫描线相交的多边形；,为每个多边形建立一个边表,(ET),；,使用一个活化边表,(AEPT),列出与当前扫描线相交的边对。,5.,扫描线,Z,缓冲器算法,将这些数据结构组织起来，可以快速地确定每个像素的深度值，从而确定像素的颜色值。,思路与多边形的扫描转换类似，但因为有多个多边形存在，复杂得多。,6.,区域子分算法,显示窗口与投影多边形的四种关系：,多边形包围了窗口；,多边形与窗口相交；,窗口包围了多边形；,窗口与多边形分离。,1,2,3,4,6.,区域子分算法,所有的多边形与窗口的关系确定以后，有些情况下就可以确定颜色了：,所有多边形与窗口分离，窗口填上背景色；,6.,区域子分算法,只有一个多边形与窗口相交或包含在窗口内，先对窗口填上背景色，再运用多边形扫描线方法对多边形内部填上该多边形的颜色；,6.,区域子分算法,离观测者最近的多边形包围了窗口，对窗口填上该多边形的颜色。,6.,区域子分算法,只有满足上述三种情况，我们才能够处理。除此之外，我们无能为力。,6.,区域子分算法,区域子分算法的处理方法是，将窗口一分为四，再判断每个子窗口与多边形的关系。这样，一些多边形与子窗口的关系成为上述三种关系中的一种。,6.,区域子分算法,如果子窗口与多边形的关系还不能满足三种情况之一，再将该窗口一分为四。如此重复，直到所有的子窗口与多边形的关系能满足三种情况之一为止。,6.,区域子分算法,经过若干次划分，窗口的宽度与一个像素的宽度一样了，可以按照第三种情况处理了。,由于窗口宽度一次减少一半，很快就能达到一个像素的宽度。,