第8章隐藏线及隐藏面消除

1、Computer Graphics第八章 隐藏线和隐藏面的消除Computer Graphics隐藏线和隐藏面的消除基于窗口的子分算法缓冲器算法和扫描线算法光线投射算法基于多边形的子分算法优先级排序表算法 曲面隐藏线的消除可见面判断的有效技术多面体隐藏线消除算法Computer Graphics线框架结构模型 它是将立体对象用轮廓线和小的元素面描述的模型，这种模型的对象立体数据输入方式简单，容易操作，可以实现描述的快速性，经常被人们使用。 但是由于线框表示会出现错误理解。如下图所示。 Computer Graphicsv 消隐的效果图Computer Graphics隐藏线或隐藏面消除确定线或

2、面可见性相对于投影中心透视投影相对于投影方向平行投影Computer Graphics以构成图像的每一个像素为处理单元，对场景中的所有表面，确定相对于观察点是可见的表面，用该表面的颜色填充该像素两种基本算法以三维场景中的物体对象为处理单元，在所有对象之间进行比较，除去完全不可见的物体和物体上不可见的部分在和投影点到像素连线相交的表面中，找到离观察点最近的表面；用该表面上交点处的颜色填充该像素；判定场景中的所有可见表面；用可见表面的颜色填充相应的像素以构成图形；Computer Graphics假定假定1 1：垂直投影垂直投影如果不是这种情况，可对消隐的对象先作变换，变成这种情况，然后再作消隐计

3、算。下面讨论消隐算法时，都假定投影平面是oxy平面，投影方向为负z轴方向的垂直投影。本章所讨论的消隐算法的前提假定：本章所讨论的消隐算法的前提假定：Computer Graphicsv 本章说明的各种消隐方法都假定构成对象的不同面不不能相互贯穿能相互贯穿，如图贯穿和循环遮挡例如用图中的虚线便可把原来循环遮挡的三个平面，分割成不互相循环遮挡的四个面。 也不能有循环遮挡不能有循环遮挡的情况，如果有这种情况，可把它们剖分成互不贯串和不循环遮挡的情况。假定假定2 2：Computer Graphics8.1 可见面判断的有效技术场景有N个面，所有的面两两求交判定可见面，O(N2)减少可见线和可见面判定

4、计算量的常用的技术非垂直投影转换成垂直投影后向面消除边界盒Computer Graphics8.1.1 边界盒Computer Graphics一个好的包围盒要具有两个条件：一个好的包围盒要具有两个条件：v包围和充分紧密包围包围和充分紧密包围着形体着形体； 对其的测试比较简单对其的测试比较简单。Computer Graphicsmin12min12max12max12min( , ),min( ,)max( , ),max( ,)xx xyy yxx xyy yQ1Q2边界盒Q5Q6的边界盒1max2min1max2min2max1min2max1minyyxxyyxx或或 边的边界盒maxC

5、omputer Graphics8.1.2 后向面消除后向面总是看不见的，而且别的棱也不会由于后向面的遮挡而成为不可见，因此，把后向面全部去掉并不影响消隐结果IJFGH，FABG，HCDI和IDEJ 前向面 其余为后相面多边形表面后向面表面的法向指向与观察者相背离前向面外法线方向指向观察者Computer Graphics8.1.2 后向面消除顶点 ，顶点的坐标LVVV,21),(iiizyx多边形F沿着顶点序列走时，其内部始终在他的右侧1V2V3VLV若构成凸的多边形 是F内法线方向12 ,111Lkvvvvkka a 大于零，外法线和 z轴正向的夹角大于90度，后向面z)(a a前向面前向

6、面0SP 后向面0SPComputer Graphicsv 设多边形设多边形F F的顶点为的顶点为 ，顶点，顶点 的坐标为的坐标为 。( (次序如图所示次序如图所示) )v 如果是一凸多边形，可只取一个三角形计算有向面积如果是一凸多边形，可只取一个三角形计算有向面积v 凹多边形的内法线方向，可以计算多边形在凹多边形的内法线方向，可以计算多边形在oxyoxy平面上投影的有向面积平面上投影的有向面积。有向面积。有向面积spsp可如下计算可如下计算v 如果如果 ，说明其，说明其外法线外法线方向与方向与z z轴正向的夹角轴正向的夹角90,90,则则F F所在的面为后向面。所在的面为后向面。v 如果如果

7、 ，说明其，说明其外法线外法线方向与方向与z z轴正向的夹角轴正向的夹角90,90,则则F F所在的面为前向面。所在的面为前向面。11112111111121() ()21 ()() ()()2LkkKzLkkkkKspv vv vxxyyxxyy LVVV,21iV),(iiizyx顶点的排列次序，使观察者在多顶点的排列次序，使观察者在多 面体外沿着面体外沿着 走时，走时，多边形的内部始终在他的右侧。多边形的内部始终在他的右侧。1V2V3VLVLVVV210SP0SPComputer Graphics背面剔除背面剔除法向向量N 视线向量V法向向量N 法向向量N 90 90V VN N cos

8、Computer Graphics8.2 多面体隐藏线消除算法用线框方式来表示多面体，在这种表示方式下，多面体用棱边来表示隐藏线便是不可见的棱边或棱边中不可见的部分找到各棱边上可见和不可见部分的分界点多面体的各棱边投影到oxy 平面上在oxy平面上求棱边和棱边之间的交点BC,BA,BG，EA为隐藏线Computer Graphics8.2.1 算法的基本思想v 隐藏线消除实际计算过程 ：Step1确定可能遮挡体A的那些体集合B (包括体A本身)。Step2A的每个多边形G，要从B中找出可能遮挡它的所有多边形的集合CStep3对多边形G的每一条边L，从集合C中找出可能遮挡它的所有多边形EStep

9、4求L和多边形E中的边的交点，确定L的可见部分Computer Graphics设边L的顶点是vi和vj，对边vivj和每一个可能遮挡它的多边形E，都要作下列计算和判断，以确定其隐藏关系 如果如果v vi i和和v vj j都在都在多边形多边形E E所在平面靠近观察者的一侧，所在平面靠近观察者的一侧，则则E E不能遮挡直线段不能遮挡直线段v vi iv vj j 如果如果v vi i和和v vj j不都在多边形不都在多边形E E所在平面靠所在平面靠 近观察者的一侧，且近观察者的一侧，且v vi iv vj j和和E E在在OxyOxy平面平面 的投影相交，求出其交点。只的投影相交，求出其交点。

10、只保留在保留在v vi i v vj j 上的对应点在多边形上的对应点在多边形E E后边的交点。后边的交点。若无交点，这时要判断若无交点，这时要判断v vi i或或v vj j在在OxyOxy平平 面上的投影是否在面上的投影是否在E E的投影的内部，的投影的内部， 若是，则若是，则v vi iv vj j就会整个被就会整个被E E所遮挡。所遮挡。Step4的处理技术的处理技术Computer Graphics1.1.确定确定L L顶点处与遮挡多边形的前后位置关系顶点处与遮挡多边形的前后位置关系),(jjjzyxjjjzyxz),(jvjvjvl 设点设点 的坐标为的坐标为 ，若，若 ，则，则

11、在多边形所在平面的前面，否则认为在多边形所在平面的前面，否则认为 在多边在多边 形所在平面的后面。形所在平面的后面。1v2vLv3v4v5v),(iiizyx)(),(5343vvvvcbacyybxxazyxz/)()(),(333l 设多边形的顶点为设多边形的顶点为 , , , 其坐标为其坐标为 i i=1,2,=1,2,L L。 任取三个不在一直线上的顶点，设为任取三个不在一直线上的顶点，设为 , , , , , 记向量记向量 , ,则多边形则多边形E E所在的平所在的平 面方程为面方程为8.2.2 确定边L和多边形E关系的技术Computer Graphics( , )jjz x yj

12、viv(,)jjjz xyzjzComputer Graphics 上对应的交点在多边形所在平面的前面，否则在后面。v 判断边vivj和多边形E在oxy平面的投影之间是否有交点，可通过求边vivj和E的边界在oxy平面上投影是否相交实现v 在 vivj平面的投影线段的参数方程为 (8.6) v 多边形上任一边vkvk+1在oxy平面上的投影为 (8.7)v 联立(8.6)和(8.7)，解方程得2. 确定L与遮挡多边形的交点和遮挡多边形的前后位置关系(1)(1)ijijxxsx syysy s11(1)(1)kkkkxxtxtyytyt11()() ()()/()() ()()/kikkkikk

13、ikjijiiksyy xxxxyyRtxxyyxxyyR11()() ()()kkjikkjiRxxyyyyxx0, 1s t边和线段vivj在oxy平面上的投影才有交点1(1)(1)ijkkzsz sztztjivv(1)ijzsz s 1(1 )kkztz t Computer Graphicsv 注意 ，其中 表示向量 在z轴上的投影。3. 确定交点和多边形的关系：是进点还是出点1()kkij zRw www ( )zAA11,kkijkkijw ww w w ww w满足右手系当 时， 由多边形外进入多 边形内（该交点称为进点）0R ijww当 时， 由多边形内离开多边形到多边形外（

14、该交点称为出点）。0Rijwwwiwj进入或走出多边形Wk+2Wk+1WkWiWjWjWiComputer Graphics4. 确定 点和多边形的关系iwv 判断 点在多边形内或外，可以从 点出发沿x轴的正向作一条射线v 若该射线和多边形边界的交点个数是奇数，则 在多边形内v 若该射线和多边形边界的交点个数是偶数，就在多边形外v 由于舍入误差，可得到完全不同的结果5w7w6w8w1w2w3w4wiwiwiw无交点奇交点单处理iw偶交点iwiwiw11()()/()kkkkkkyyyxxxxyiyy1kkw w把代入的方程11()()/()kkikkkkxxxyyyyx得1kkww说明ixx

15、Fwi若有一个交点。Computer Graphics8.2.3 确定L的可见部分v 不可见阶 它是一个数字，代表了边上从该点到下一个交点的部分被几个多边形遮挡 与所有多边形的交点进行由小到大的顺序排序jiww1, 01210nnsssss不可见阶的确定1确定边起始顶点处的不可见阶。将阶置为覆盖该点的多边形的个数。2确定边 与遮挡多边形各交点处的不可见阶。交点为进点则 不可见阶加1，交点为出点则 不可见阶减1jiww原则：若 处不可见阶为0，则由参数 和 所对应的直线段是可见的，否则为不可见isis1isComputer Graphics8.3 基于窗口的子分算法Computer Graphi

16、cs多边形与窗口的关系：Computer Graphics所有多边形均和窗口分离，这时只要把窗口内所有的像素填上背景色只有一个多边形和窗口相交，或这个多边形包含在窗口内。这时，先对窗口内每一像素填上背景颜色，再对窗口内多边形部分用扫描线算法填色只有一个包围窗口的多边形，则窗口用包围多边形的颜色填充。多个多边形和窗口的关系分别是相交、内含或包围，但是有一个包围窗口的多边形在其他多边形前面，整个窗口用该包围多边形的颜色填充窗口分割的结束条件不成立的窗口将再一分为四Computer Graphicsv 提高效率的有效的处理技术排序对所有的多边形按其顶点的z坐标最大值来排序细分每次细分窗口后，用边界盒

17、的办法判断多边形序列中的多边形是否和四个子窗口相交，不相交的多边形可从多边形序列中排除若窗口被多边形G包含，被G遮挡的多边形要从窗口的多边形序列中去掉 EA窗口zmaxzminB C D GHF图8.12 确定被遮的挡多边形izzmaxminCD被AB遮挡GHzzAB遮挡了EFComputer Graphics8.4 基于多边形的子分算法v 算法描述：各多边形在深度方向作初步的排序多边形序列中的第一个多边形(裁剪多边形)作为裁剪窗口区域内多边形确定内部表中多边形的前后顺序区域外多边形外部表中同样的工作裁剪过程要重复到外部表中不再有多边形为止v 目的是尽量减少对窗口划分的次数。 Computer

18、 Graphicszxy43212i3i4i4oa) ni为窗口内的多边形表，n=2,3,4； b) no为窗口外的多边形表,n=3,4图8.14 消隐多边形的裁剪3o例子Computer Graphics具体步骤：具体步骤：v 对各多边形在深度方向作初步 的排序v 把多边形序列中的第一个多边 形（裁剪多边形）取为裁剪窗口。 多边形序列中的其它的多边形 都要被此窗口裁剪。v 裁剪结果要建立两个多边形序 列表 消隐多边形的裁剪Ni为窗口内的多边形表；内部表内部表: :放入位于窗口内的部分放入位于窗口内的部分no为窗口外的多边形表外部表外部表: :放入位于窗口外的部放入位于窗口外的部分分Compu

19、ter Graphicsv 确定裁剪多边形（即取为窗口的那个多边形）是否比内部表中的多边形更靠近观察者v 如果是则内部表中的其他多边形都被其遮挡，可把该多边形区域填上裁剪多边形的颜色v 如果发现内部表中某多边形H比裁剪多边形更靠近观察者这时则只好把多边形H的原始多边形（即未被裁剪时的多边形）代替原来的裁剪多边形重复上述工作。Computer Graphicsv接着处理外部表中的各多边形，把外部表中的第一多边形作为裁剪窗口，重复上述工作v这一过程要重复到外部表中不再有多边形为止要消隐的多边形 消隐多边形的裁剪Ni为窗口内的多边形表；no为窗口外的多边形表Computer Graphicsv 算法

20、简述：各多边形在深度方向作初步的排序多边形序列中的第一个多边形(裁剪多边形)作为裁剪窗口区域内多边形确定内部表中多边形的前后顺序区域外多边形外部表中同样的工作裁剪过程要重复到外部表中不再有多边形为止Computer Graphics8.5 z缓冲器算法和扫描线算法uvnumaxvmaxv 基本思想：基本思想：Computer Graphics具体实现此算法需要z缓冲器数组和帧缓冲器数组，分别设为Zdepth 与Frame ：对屏幕上每个点（x,y），令Zdepth xy 为z的极小值，Frame xy为背景颜色。对所有多边形做如下工作：对多边形上 每一点（x,y）,计算其z值。 若z Zdep

21、th xy， 则 Zdepth xyz，并将此点属性值 赋给Framexy，否则 说明此点离观察 者较远，两个数组的值都不用改变x,y（）Computer Graphics克服Computer Graphics扫描线z缓冲器算法v 算法思想Computer Graphicsv 每处理一条扫描线，都要检查各多边形是否和该线相交，还要计算多边形所在平面上很多点的z值，需要花费很大的计算v 采取类似多边形扫描转换的扫描线算法处理，提高效率x,y（）Computer Graphics数据结构1多边形Y筒系数a，b，c和dy 属性color编号IP2边Y筒上端点x坐标的值y x 编号IP3多边形活化表.

22、多边形活化表中记录了在 平面上的投影和当前考虑的扫描线相交的多边形4边活化表边活化表中存放多边形的边和当前扫描线相交的边对Computer Graphics367811101198713图 8.15 要消隐的物体xo多边形y筒边y筒1/7107 28 2 1 2多边形活化表1,; 3, 0, 7; 3, 1, 4111IPzzzyxxyxxyxlrrrlll2,; 5,71,7210; 5,65,656222IPzzzyxxyxxyxlrrrlll边活化表Computer Graphics算法如下建立多边形Y筒和边Y筒，初始化多边形和边的活化表为空。1TEXT2以最上面的扫描线为当前扫描线。4

23、检查多边形Y筒若有新的多边形涉及当前扫描线，则把它放入多边形活化表中。若有新的多边形加入多边形活化表，则要把该多边形在 平面上的投影和扫描线相交的边对加入边活化表中。对当前扫描线y，把帧缓冲器相应行置成底色，z缓冲器的各单元放z的极小值3若所有扫描线都已经处理完，则算法结束，否则选下一条扫描线为当前扫描线，转步骤365对边活化表中的每个边对，令 ，对每一个满足 的坐标为 的像素从左到右依次进行处理。lxzz rlxxx),(yxComputer Graphics对边活化表和多边形活化表修改1）、修改边活化表，对每一边做如下计算 若yl 或yr小于0，相应的边就要从一个边对中去掉，并从y筒中找到

24、合适的边来代替。若这两条边同时结束于某一点，则去掉这一边对。若yl和yr都不小于0，则修改 为 修改后的表便是新扫描线的边活话表。2）、修改多边形活化表。令 ，若 ，则将该多边形从多边形活化表中删除。 1 -y y1, -y yrrll算法步骤：算法步骤：-对边活化表修改rrrlllxxx ,xxxylxllz xzz zllrzxx,1yy0 yComputer Graphics8.6 优先级排序表算法v 模拟示例Computer Graphicsv 算法思想 优先级排序表算法按多边形离观察者的远近来建立一个多边形排序表，距观察者远的优先级低，近的优先级高 从优先级低的多边形开始，依次把多边

25、形的颜色填入帧缓冲存储器中 表中距观察者近的元素覆盖帧缓冲存储器中原有的内容 当优先级最高的多边形的图形送入帧缓冲器后，整幅图形就形成了Computer Graphicsv 优先级排序表算法的关键在于对多边形做正确的排序优先级排序表算法的关键在于对多边形做正确的排序v 动态的算法： 根据每个多边形顶点z坐标的极小值zmin的大小，按由小到大对它们做初步排序，并把它们组成一个链表 若链表中只有一个多边形，则算法结束。否则取表头多边形为P。1. 设Q为链表中P之外的任一多边形。若对所有Q都有 ,则P不会遮挡其它多边形，为优先级最低的多边形，在链表中去除P，转（2）；否则，若所有Q都满足下面四项条件

26、中的一项，则在链表中去除P，转（2）。若不满足此四项条件中任何一个的Q，交换P和Q，转（3）。minzQmaxzPComputer Graphics四项条件P和Q在平面 oxy上的投影不相交Q 的各顶点均在P的近视点的一侧P 的各顶点均在Q的远离视点的一侧P和Q在oxy平面上投影的边界盒在x或y方向上不相交Computer Graphics特殊情况v 解决：图8.22，把多边形序列中原多边形P从序列中去掉，而把P分成的两个多边形加入链表中，这样可避免使多边形P和Q不断地循环进行交换图8.21 互相遮挡 图8.22 用Q所在平面把P一分为二 Computer Graphicsv 对飞机驾驶员着陆

27、进行模拟训练时要显示消隐后的跑道周围情况，这时景物是不变的，仅视点发生变化。v 可对不同的视点位置把景物的优先级排序表预先算好，然后再用油画家算法显示图形，这样便可使消隐过程加速，实现动态显示图8.23 视点在不同区域有不同的优先级ABCD视点所在区域 优先级表优先级表Computer Graphics8.7 光线投射算法v原理：要处理的场景中有无限多条光线，从采样的角度讲我们仅对穿过像素的光线感兴趣，因此，可考虑从像素出发，逆向追踪射入场景的光线路径Computer Graphics具体做法是：v 由视点出发穿过观察平面上一像素向场景发射一条射线(如图8.25)v 求出射线与场景中各物体表面

28、的交点v 离视点最近的交点的颜色即为像素要填的颜色。v 光线投射算法对于包含曲面，特别是包含球面的场景有很高的效率。图8.25 一条由象素点射入场景的视线 Computer Graphicsz z缓冲器算法:每次处理一个面片,对面片上的每个投影点计算z值，计算出来的值与以前保存的z值进行比较，从而确定每个像素所对应的可见面片光线投射算法可看作是z缓冲器算法的一种变形光线投射算法:每次处理一个像素，并沿光线的投射路径计算出该像素所对应的所有面片的z值。Computer Graphics8.8 曲面的隐藏线消除v 由方程 表示曲面v 曲面可以由 和 产生的 条曲线来表示 即由 和 两组平面和曲面 的交线来表示v 隐藏线消除就是要去掉这两 族交线中被遮挡的部分),(zxfy (a)未消隐的曲面表示(b)消隐的曲面表示( , ), 0,1,2,iyf x zin( , ), 0