第8章 可见面判断算法

《第8章 可见面判断算法》由会员分享，可在线阅读，更多相关《第8章 可见面判断算法（63页珍藏版）》请在装配图网上搜索。

1、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,‹#›,2014年11月7日9时47分,,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,哈尔滨工业大学计算机学院 苏小红,（一）,计

2、算机工程学院,真实感图形生成,三维图形消除隐藏线的处理,在前面章节中介绍了三维图形变换，从而可画出物体的轴测图，但是这种方法是将物体上的所有棱线全部画出，不能考虑物体上哪些棱线是可见的，哪些是不可见的，这就造成了表达物体的不确切性。如图,a,所示，作投影变换是表示的物体,b,呢还是物体,c?,2,a,b,c,上,图所示物体还仅仅是一个单个物体，但物体往往由多个形体或在一个形体上存有不同结构组成，情况会更复杂。,因此，要画出确定的立体感更强的轴测图时，利用计算机自动地判别棱线或立体表面的可见性，将那些不可见的棱线消去不画或画成虚线，这项工作称为消除隐藏线（或隐藏面），简称消隐。,由于图形的表现形

3、式不同，消隐对象也不同，对于线框图是要消除隐藏线，对于用不同灰度的表面构成的图形，是要消除隐藏面。无,3,论是消除隐藏线还是消除隐藏面，需要程序准确，可靠地判别出棱线的可见性，这不是件容易的事情，因此消隐是计算机绘图中的难点之一。,本,例以凸多面体为例，介绍消除隐藏线的原理，计算方法，还介绍任意平面立体的消隐方法。,4,消除隐藏线的原理,一、基本概念,凸多面体是由若干个平面围成的立体，而每个平面又都是由凸多边形组成。所以，若某个多边形表面是可见的，则该表面上的所有的线均可见。若某个多边形表面为不可见，则该表面上所有的线均不可见。如果画出可见面上所有的线，消去不可见面上所有的线，那么就画出了凸多

4、面体消隐后的立体图。,5,二、平面的可见性,由于组成凸多面体的各个表面是由凸多边形围成的，因此我们先来讨论多边形平面的投影性质，每个平面均有其法线，如图中,R,平面，有法线,N,，当法线,N,确定后平面,R,就为有向平面，引出法线方向的面称为平面的正面，与法线相反的面，称为平面的背面，平面向某一投影面投影后，平面的,可见性有以下几种情况：,1,）平面的正面朝着观察,,,者，投影后平面为可见,6,N,法线,R,正面,背面,2,）,平面,的背面,朝着,观察者,，投影后平面,为不可见。,3,）平面垂直于投影面时，投影后平面积聚为一条线，平面视为可见。,,7,三、立体表面的可见性,组成凸多面体的各个表

5、面均有其法线，我们可用它的外法线来描述。所谓外法线，其方向是由物体的内部指向物体的外部。,,8,N1,N2,N3,N4,N5,N6,立体经过投影后，通常是在,V,面（,XOY,平面）输出正投影图，此时,V,面是投影面，则视线的反向与,OY,轴平行，所以外法线与,OY,轴的夹角 反应了外法线与视线的夹角，根据这一夹角的大小，就可以判别出该法线所在的平面的可见性。,有以下几种情况：,1,）当,β,＜,90,时，则平面的正面朝向观察者，该平面为可见。,2,）当,β,＞,90,时，,则平面,的背面,朝向观察者，该平面,为不可见,。,9,β,3,）当,β,=90,时，,则平面,的正面垂直于投影面，投

6、影积聚成一条线，,该平面,为可见。,4,）当,β,=0,时，则平面的正面平行于投影面，该平面为可见。,10,消隐的计算方法,一、平面的矢量,由空间解析几何可知，如有矢量,a,和矢量,b,，则它们烦人矢量积,a ×b,，必垂直于矢量,a,和,b,所决定的平面。因此矢量积,a ×,b,就是矢量,a,和,b,所在平面的法矢量。法矢量的方向按右手坐标系定义。,11,a,b,a,×,b,对于物体的任一表面，为保证正确地得到它的外法线，我们规定，当观察者面对平面的外表面时，在该平面上以逆时针方向顺序取三个点。各点的坐标为,D(x1,y1,z1),E(x2,y2,z2),F(x3,y3,z3),根据矢量积定

7、义平面的法矢量为,N=U,,×V,矢量,N,的方向就是平面,P,的外法线方向。,12,D,E,F,,13,14,,真实感图形绘制流程,,场景造型,,取景变换,,背面剔除,,视域四棱锥裁剪,,透视变换,,隐面消除、场景造型,,光亮度计算,,,,,,,,扫描转换、场景造型,,15,取景变换（,1/5,）,场景坐标系,场景的,局部,坐标系,完成物体的造型,,场景的,世界,坐标系（整体坐标系）,放入待绘制的场景，定义物体之间的相互位置,观察坐标系,也称,摄像机坐标系,，或者,视点坐标系,完成取景变换所需建立的第一个坐标系,16,取景变换（,2/5,）,建立观察坐标系的步骤,确定,观察参考点,，即,视点

8、位置,可以设在任何位置,通常选在靠近或在物体的表面,将视点位置取为视点坐标系的原点,确定,观察方向,，即,视线方向,一般取深度坐标轴，即,z,e,轴的正向,为简便起见，设为总是指向场景坐标系的原点,确定,观察平面,，即,视平面位置,一般取过视点且垂直于视线方向的平面，即,x,e,y,e,平面,17,取景变换（,3/5,）,场景坐标系,一般取,右手,坐标系,,观察坐标系,通常取,左手,坐标系,,符合人们的观察习惯,,,,,,,,,,,,,x,w,z,w,y,w,,,,,,z,e,x,e,y,e,视点,E,观察坐标系为左手坐标系,,场景坐标系为右手坐标系,O,18,取景变换（,4/5,）,将物体投

9、影到观察平面之前,必须将场景坐标系中的点转换到观察坐标系中,,这一过程称为,取景变换,，也称,视向变换,包括平移和旋转的一系列几何变换的级联,,取景变换矩阵,,19,取景变换（,5/5,）,场景坐标系原点平移到视点位置,E,,绕,x,e,轴逆时针旋转,90º,,绕,y,e,轴顺时针旋转,Ψ,角,,绕,x,e,轴逆时针旋转,θ,角,,调整,x,轴指向,对,x,轴作对称变换,,,,,,,,,,,,,,x,w,z,w,y,w,,,,,z,e,x,e,y,e,E,O,C,x,,C,y,C,z,Ψ,,,,,,,,,,,,x,w,z,w,y,w,,,,,z,e,x,e,y,e,E,O,C,x,,C,y,C

10、,z,90,º,,,,,,,,,,,,,x,w,z,w,y,w,,,,,z,e,x,e,y,e,E,O,C,x,,C,y,C,z,,,,,,,,,,,,,,,x,w,z,w,y,w,,,,,z,e,x,e,y,e,E,O,C,x,,C,y,C,z,Ψ,,,,,θ,θ,20,消隐算法,按实现方式不同分为两大类,：,景物空间,（,object space,） 消隐算法,直接在视点坐标系中确定视点不可见的表面区域,将它们表达成同原表面一致的数据结构,侧重于景中各物体之间的几何关系,图像空间,（,image space,）消隐算法,,在投影屏幕上，以屏幕像素为采样单位，确定投影于每一像素的可见景物表面

11、区域,将其颜色作为该像素的显示光亮度,侧重于向屏幕投影后形成的图像,21,背面剔除算法,背面剔除算法,,,,法向向量,N,,视线向量,V,,,,,,,,,,,,,,,,,法向向量,N,,,法向向量,N,<90°,<90,°,,可见,,可见,,不可见,>90°,22,隐藏面的消除,-,Roberts,算法,（,1/9,）,Roberts,算法,景物空间消隐算法,1963,年，,Roberts,于,MIT,提出,,23,隐藏面的消除,-,Roberts,算法,（,2/9,）,基本思想,消除被物体自身遮挡的边和面,再用每个物体留下的边与其它物体比较,适用范围,凸体,凹体怎么办？,分解成若干凸体的组合

12、,24,隐藏面的消除,-,Roberts,算法,（,3/9,）,体矩阵,平面方程,ax+by+cz+d=0,,,,,,,25,隐藏面的消除,-,Roberts,算法,（,4/9,）,求平面方程,ax+by+cz+d=0,的系数,利用,不共线三点坐标,,利用平面的,法向量,平面法向量,:n=ai+bj+ck,d=-(ax,1,+by,1,+cz,1,),,利用,Martin Newell,方法,,,,,26,隐藏面的消除,-,Roberts,算法,（,5/9,）,已知：,S=[x y z 1],，,P=[a b c d],若,S,在平面上,则,S,•P=0,若点,S,不在平面上,则点积的正负号标

13、识点在平面的哪一侧,,约定：,若点,S,在,体内一侧,则,S,•P>0,,若点,S,在,体外一侧,则,S,•P<0,,27,隐藏面的消除,-,Roberts,算法,（,6/9,）,体矩阵不一定保证体内点都满足,S,•P>0,,如何得到正确的体矩阵？,,对体矩阵,V,进行校正,,在体内找一,试验点,S,若某平面方程系数,P,与,S,的点积符号为负,则将该方程系数均乘以,-1,28,隐藏面的消除,-,Roberts,算法,（,7/9,）,自隐藏面的判别,,,假设,视点,：位于,z,轴正向的无穷远处,视线方向,：,z,轴负向的无穷远点,,E,=[0 0 -1 0],,用,E,作为试验点,判定一

14、平面是自隐藏面的条件,,E,•,V<0,点积值为负，表示,E,位于这些平面的外侧,29,隐藏面的消除,-,Roberts,算法,（,8/9,）,,,,,,,,,,,,,,,,,,,,,,y,z,x,③,④,②,①,⑤,⑥,,,,① ② ③ ④ ⑤ ⑥,,① ② ③ ④ ⑤ ⑥,体内试验点,,,,正确的体矩阵,,,① ② ③ ④ ⑤ ⑥,30,隐藏面的消除,-,Roberts,算法,（,9/9,）,,,,,,,,,,,,,,,,,,,,,,y,z,x,③,④,②,①,⑤,⑥,,,,,,,,,,,,,,,x,,-,z,物体,,内,,外,

15、,内,,①,,②,,⑥,,⑤,,负无穷远点,E,=[0 0 -1 0],•,视线方向,视点位于正无穷远点,E,= [0 0 1 0],,,,,,,无限延伸平面,,用,E=[0 0 -1 0],作为体内试验点,,,31,隐藏面的消除,-,画家算法,,（,1/3,）,画家算法,,1972,年,M.E.Newell,受画家由远至近作画的启发,景物空间消隐算法,32,隐藏面的消除,-,画家算法,,（,2/3,）,基本步骤,生成深度优先级队列,据视点距离,远,的多边形优先级低，排在队列的前端,据视点距离,近,的多边形优先级高，排在队列的后端,从队列中依次取出多边形，,计算其表面光亮度,写入帧缓冲器,,直

16、到队列中所有多边形的光亮度都计算完毕，并写入帧缓冲器,33,隐藏面的消除,-,画家算法,,（,3/3,）,优点,：,透明或半透明物体,图形的,动态显示,飞行训练模拟器中显示飞机着陆时的情景,场景中的物体是不变的，,只是视点在变化,只要事先把不同视点的景物的优先级队列算出,再实时地采用画家算法来显示图形,就可以实现图形的快速消隐与显示,34,隐藏面消除,-,Weiler-Atherton,算法,（,1/3,）,Weiler-Atherton,算法,景物空间消隐算法,基于,Weiler-Atherton,多边形裁剪操作,35,隐藏面消除,-,Weiler-Atherton,算法,（,2/3,）,基

17、本步骤,,1),深度预排序，形成,景物多边形表,,将变换到屏幕坐标系中的景物表面,按各顶点的,z,最小值进行排序,2),当前具有,最大,z,值,的景物表面作为裁剪多边形,CP,,,深度最大、离视点最近,3),用,CP,对景物多边形表中排在后面的表面进行,裁剪,,产生内部多边形,Pin,和外部多边形,Pout,,,裁剪多边形将主多边形,裁剪为内部多边形和外部多边形,B1,B2,裁剪多边形,Pc,主多边形,Ps,,,,,36,隐藏面消除,-,Weiler-Atherton,算法,（,3/3,）,4),比较,Pc,与,Pin,的深度，检查,Pc,是否真正离视点最近,是，则,Pc,为可见表面,不是，则

18、取,Pin,为新的,Pc,，重复步骤,3),5),将位于,Pc,之外的景物表面组成外裁剪结果多边形表,,取表中深度最大的表面为,Pc,，重复步骤,3),6),递归进行直到外裁剪结果多边形表为空时为止,,37,隐藏面的消除,-,BSP,树算法,（,1/2,）,BSP,树算法,Binary Space Partitioning,景物空间消隐算法,基于,BSP,树，对景物表面进行二叉分类,与画家算法类似，景物多边形由远至近绘制,,特别适合的场合,,场景中,物体位置固定不变,、,仅视点移动,38,隐藏面的消除,-,BSP,树算法,（,2/2,）,基本步骤,,选一剖分平面,P1,，将场景空间分割成两个半

19、空间,剖分结果表示为一棵,BSP,树,叶节点,：景物,左分支,：位于剖分平面前面的景物,右分支,：位于剖分平面后面的景物,依据视点位置，对子空间进行分类,包含视点的子空间标识为“,front”,另一侧子空间标识为“,back”,递归搜索,该,BSP,树，优先绘制标识为“,back”,的子空间中所含的景物,,,B,front,,,,,,,,front,back,back,A,C,D,,,,,,P1,P2,P2,,front,front,front,back,back,back,A,C,,D,B,39,隐藏面消除,-,深度缓冲器算法,（,1/8,）,深度缓冲器算法,Depth—buffer alg

20、orithm,图像空间消隐算法,1975,年，,Catmull,提出,40,隐藏面消除,-,深度缓冲器算法,（,2/8,）,基本思想,将投影到显示屏上的每一个象素所对应的多边形表面的深度进行比较,取最靠近视点的表面的属性值作为该像素的属性值,用,Z—buffer,记录该表面在该像素点的,深度,用,frame—buffer,记录该表面在该像素点的,颜色或亮度值,,41,隐藏面消除,-,深度缓冲器算法,（,3/8,）,,深度缓冲器,帧缓冲器的扩充,也称,Z-Buffer,算法,42,隐藏面消除,-,深度缓冲器算法,（,4/8,）,流程：,for,（场景中的每一个多边形）,{,,扫描转换该多边形；,

21、,for,（多边形所覆盖的每一个像素点,(x,y),）,,{,,计算多边形在该像素点的深度值,z,(,x,y,),；,,if,（,z(x,y) > Z-buf,中对应此像素点,(x,y),的,z,值）,,{,,把多边形在,(,x,y,),处的深度值,z,(,x,y,),存入,Z-buf,中的,(,x,y,),处；,把多边形在,(,x,y,),处的亮度值存入,f-buf,中的,(,x,y,),处；,,},},},当所有的多边形都处理完后，帧缓冲器中的内容即为消除隐藏面后的图像,43,隐藏面消除,-,深度缓冲器算法,（,5/8,）,优点,简单,在象素级上以近物代替远物，易于消除隐藏面，并准确显示复

22、杂曲面之间的交线。,计算量呈线性复杂度,场景中景物表面采样点的数目,无需对各景物表面片作深度预排序,景物表面上的可见点可按任意次序写入深度缓冲器和帧缓冲器,易于硬件实现,图形工作站上配置由硬件实现的深度缓冲器算法,很多微型机上都装有基于深度缓冲器算法的图形加速卡,44,隐藏面消除,-,深度缓冲器算法,（,6/8,）,缺点,需要很大的存储空间,象素数目为,500×500,，深度值采用浮点类型（,4,字节）,除刷新缓存外，还需,500*500*4=1M,字节的额外存储空间,在实现反走样、处理透明和半透明等效果方面存在困难，并由此会产生巨大的处理时间开销,由于在帧缓冲器内的同一象素点上可见表面的写入

23、顺序是不确定的，所以可能导致画面上的局部错误。,45,隐藏面消除,-,深度缓冲器算法,（,7/8,）,改进一：减少需要相对测试的多边形平面数,最小最大测试,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,不重叠,,,不可能互相遮蔽,测试无确定结果,,对每条边进行,最小最大,测试,Xmin,Xmax,46,隐藏面消除,-,深度缓冲器算法,（,8/8,）,改进二：利用连贯性计算深度,水平方向,竖直方向,改进三：降低对存储空间的需求,图像空间划分为,4,、,16,甚至更多的子正方形或条状区域,在最小情况下，只对应一条扫描线的深度缓冲器,扫描线相关算法,47,隐

24、藏面的消除,-,扫描线相关算法（,1/3,）,扫描线相关算法,按扫描线顺序处理一帧画面,在,扫描平面,（,ZOX,平面）上解决消隐问题,由视点和扫描线所决定,,深度缓冲器算法的一维版本,深度缓冲器所需的存储空间,屏幕水平分辨率,×,每个深度值所占的存储位数,48,隐藏面的消除,for (,每条扫描线,),{,,将扫描线帧缓冲器,f_buf,置成背景色；,将扫描线深度缓冲器,Z_buf,置成最小值；,,for (,每个多边形,),{,,求出该多边形与当前扫描线的相交区间；,,for (,相交区间内每个象素点,(x,y)),{,,计算多边形在该处的深度值,z,；,,if (,多边形在该处的深度值,

25、z > Z_buf,在该处的值,),{,,用多边形在该处的深度值,z,取代,Z_buf,在该处的值；,用多边形在该处的亮度值取代,f_buf,在该处的值；,,},},},,用,f_buf,的内容显示当前扫描线；,},49,隐藏面的消除,-,扫描线相关算法（,3/3,）,缺点,在每一个被多边形覆盖像素处需要计算深度值,被多个多边形覆盖的像素需要多次计算深度值,,改进,在一条扫描线上，以区间为单位确定多边形的可见性,50,隐藏面的消除,-,Warnock,算法,（,1/4,）,Warnock,算法,图像空间消隐算法,区域的连贯性,也称,区域细分,area-subdivision,实质,分而治之,5

26、1,隐藏面的消除,-,Warnock,算法,（,2/4,）,基本思想,观察整个窗口区域,判别窗口是否单纯,窗口内,无任何可见物体,窗口,已被一个可见面片完全充满,将非单纯的窗口四等分为四个子窗口,对每个子窗口再进一步判别是否是单纯的,直到窗口单纯或窗口边长已缩至一个象素点为止,,,即使,1024×1024,分辨率,视图被细分,10,次后，也能使每个子窗口覆盖一个像素,,52,隐藏面的消除,-,Warnock,算法,（,3/4,）,关键步骤,,分析观察窗口与所有投影后多边形面片之间的关系,,,,,,,,,,分离,内含,相交,包围,——,判别窗口是否单纯,53,隐藏面的消除,-,Warnock,算

27、法,（,4/4,）,基本步骤,对每个窗口判断,与多边形,分离,仅,包含,一个多边形,与一个多边形,相交,被一个多边形所,包围,且窗口内无其它多边形,至少被一个多边形所包围，且此多边形,距离视点最近,否则继续细分窗口，并重复以上测试,,,,,,,,,,,,,,,54,,光线投射算法（,1/4,）,Ray Casting,Appel,提出,,建立在几何光学基础之上,,对于包含曲面、特别是球面的场景效率高,55,,光线投射算法（,2/4,）,基本思想,观察者之所以能看见景物,光源发出的光照射到物体上的结果,其中一部分光到达人的眼睛引起视觉,到达观察者眼中的光,由物体表面反射,通过表面折射或透射,若,

28、从光源出发跟踪光线,则只有极少量的光能到达观察者的眼睛,效率低,从视点或像素出发，仅对穿过像素的光线反向跟踪,当光线路径到达一个可见的不透明物体的表面时停止追踪,56,将景物通过,透视投影变换,到图像空间,反向跟踪一条穿过像素点的光线,决定它与场景中的哪一景物表面相交,交点按深度排序,需求出该光线与景物表面的所有可能的交点,具有,最大,z,值的交点,对应的面就是屏幕上该像素对应的,可见面,离视点最近,该像素处的显示值由相应物体的属性决定,对屏幕上所有像素都进行如上处理后，算法结束,,,,,,,,,,,,,,,,,,,,,,,,,,,,,视点,光线,投影面上的像素位置,物体,,,,,,,,,,,

29、,假设,视点,位于,z,轴正向,投影平面,（屏幕）垂直于,z,轴,反向跟踪一条穿过像素点的光线,光线投射算法（,3/4,）,57,光线投射算法（,4/4,）,,光线投射算法,{,for(y=0;y<=ymax;y++),for(x=0;x<=xmax;x++),{,形成通过像素,(x,y),的投影线；,,for(,场景中的每一个多边形）,将投影线与多边形求交；,,if(,有交点,),,以最近交点所属多边形的颜色显示像素,(x,y);,else,,以背景颜色显示像素,(x,y);,},},58,阴影处理 （,1/6,）,判断视点、光源以及物体之间的位置关系,,从视点可见，从光源也可见,从视点可见

30、，从光源不可见,相对于部分光源可见，相对于另一部分光源不可见,59,阴影处理（,2/6,）,当观察方向与光源方向重合时,观察者看不到任何阴影,可以不进行阴影测试,,当观察方向与光源方向不一致,或光源多且光源体制比较复杂时,必须进行阴影处理,60,阴影处理（,3/6,）,阴影由两部分组成,本影,任何光线都照不到的区域,呈现为全黑的轮廓分明的区域,,,半影,可接收到分布光源照射的部分光线的区域,通常位于本影周围，呈现为半明半暗的区域,,,,,,,,,,,,本,半,区,影,区,影,区,影,无,光源,面光源照射形成的本影与半影,61,阴影处理（,4/6,）,点光源,只能产生本影,,位于有限距离内的分布光源,可同时产生本影和半影,需要的阴影计算量大,62,阴影处理（,5/6,）,计算阴影的过程,相当于两次消隐过程,对每个光源进行消隐,对视点的位置进行消隐,,好处,改变视点位置,，第一次消隐过程不必重新计算,63,阴影处理（,6/6,）,产生的本影包括,自身阴影面,假设视点在点光源位置，用,背面剔除,的方法求出,,投射阴影,从光源向物体的所有可见面投射光线,将这些面投影到场景中得到投影面,将这些投影面与场景中其它平面求交线，可得阴影多边形,,,,,,,,,,,,,,,,,,,,,,,,,,,自身阴影,,投射阴影,,