隐藏线和隐藏面的消除.ppt

《隐藏线和隐藏面的消除.ppt》由会员分享，可在线阅读，更多相关《隐藏线和隐藏面的消除.ppt（72页珍藏版）》请在金锄头文库上搜索。

1、第七章第七章隐藏线和隐藏面的消除隐藏线和隐藏面的消除消隐的几个效果图线框架结构模型 它是将立体对象用轮廓线和小的元素面描述的模型，这种模型的对象立体数据输入方式简单，容易操作，可以实现描述的快速性，经常被人们使用。 但是由于线框表示会出现错误理解。如下图所示。 隐藏线消除或隐藏面消除：用计算机生成三维图形，首先要确定三维场景中的物体哪些部分是可见的，即确定哪些线或面是可见确定哪些线或面是可见的的，生成三维图形时只绘制可见的部分只绘制可见的部分。场景中可见部分的判断过程称为可见线或面的判定，也称为隐藏线或面的消除。三维场景中物体的可见性对透视投影是相对于投影三维场景中物体的可见性对透视投影是相对

2、于投影中心；对平行投影则是相对于投影方向。中心；对平行投影则是相对于投影方向。v基于图像空间的方法基于图像空间的方法隐藏面和隐藏线的消除有两种基本的算法用该表面上交点处的颜色填充该像素；在和投影点到像素连线相交的表面中， 找到离观察点最近的表面；算法简单描述为：以构成图像的每一个像素为处理单元侧重于向屏幕投影后形成的图像对于图像空间中的每一个像素：v基于物体空间的方法基于物体空间的方法用可见表面的颜色填充相应的像素以构成图形;判定场景中的所有可见表面；对于三维场景中的每一个物体：是以三维场景中的物体对象为处理单元侧重于景中各物体之间的几何关系假定假定1 1：垂直投影垂直投影如果不是这种情况，可

3、对消隐的对象先作变换，变成这种情况，然后再作消隐计算。下面讨论消隐算法时，都假定投影平面是oxy平面，投影方向为负z轴方向的垂直投影。本章所讨论的消隐算法的前提假定：本章所讨论的消隐算法的前提假定：本章说明的各种消隐方法都假定构成对象的不同面不能相互贯穿不能相互贯穿，如图贯穿和循环遮挡例如用图中的虚线便可把原来循环遮挡的三个平面，分割成不互相循环遮挡的四个面。 也不能有循环遮挡不能有循环遮挡的情况，如果有这种情况，可把它们剖分成互不贯串和不循环遮挡的情况。假定假定2 2：7.1可见面判断的有效技术减少求交计算的减少求交计算的常用技术常用技术：l用边界盒排除不相交的线段求交用边界盒排除不相交的线

4、段求交l非垂直投影转换成垂直投影非垂直投影转换成垂直投影l把后向面全部去掉把后向面全部去掉用边界盒排除不相交的线段求交边界盒：边界盒：一个物体的边界盒是指能够包含该物体的一个物体的边界盒是指能够包含该物体的一个几何形状，该形状有较简单的边界一个几何形状，该形状有较简单的边界。边界盒的形状可以是长方形（体）状或是圆（球）形状的。边界盒可用于投影边界盒，可用于物体本身边界盒，还可用于某一维方向上的边界盒。包围物体投影的边界盒不相交的情况图7.3 两个物体投影在(x,y)平面，包围投影的边界盒包围物体投影的边界盒相交的情况(a) 边界盒和投影均重叠 (b) 边界盒重叠，投影不重叠 一个好的包围盒要具

5、有两个条件：一个好的包围盒要具有两个条件：包围和充分紧密包围和充分紧密包围着形体包围着形体； 对其的测试比较简单对其的测试比较简单。边界盒可用于包围物体本身而不只是他们的投影，边界盒可用于包围物体本身而不只是他们的投影，在此情况下，边界盒是三维的在此情况下，边界盒是三维的。 边界盒也可用于在某一维方向上进行包围，以判断边界盒也可用于在某一维方向上进行包围，以判断两个物体在该方向上是否相交。两个物体在该方向上是否相交。 oxz1zmin1min1zmax1max12zmin2min2zmax2max2 边的边界盒边的边界盒Q1Q2的边界盒Q5Q6的边界盒生成边界盒的一个较简单的方法(P136)：

6、判断两条直线是否相交多边形的判定多边形的边界盒多边形的边界盒max把内法线方向背向视点的面称为前向面前向面内法线方向指向视点的面（即外法线方向背离视点）称为后向面后向面多面体面的顶点多面体面的顶点排序排序IJFGH，FABG，HCDI，IDEJ所在的面为前向面 JEAF，DEABC，HGBC所在的面为后向面去掉后向面设设多多边边形形F的的顶顶点点为为 ，顶顶点点 的的坐坐标标为为 。(次序如图所示次序如图所示)如果是一凸多边形，可只取一个三角形计算有向面积如果是一凸多边形，可只取一个三角形计算有向面积凹凹多多边边形形的的内内法法线线方方向向，可可以以计计算算多多边边形形在在oxyoxy平平面面

7、上上投投影影的有向面积。有向面积的有向面积。有向面积spsp可如下计算可如下计算 如如果果 ，说说明明其其外外法法线线方方向向与与z z轴轴正正向向的的夹夹角角90,90,则则F F所在的面为后向面。所在的面为后向面。如如果果 ，说说明明其其外外法法线线方方向向与与z z轴轴正正向向的的夹夹角角90,90,则则F F所在的面为前向面。所在的面为前向面。顶点的排列次序，使观察者在多顶点的排列次序，使观察者在多 面体外沿着面体外沿着 走时，走时，多边形的内部始终在他的右侧。多边形的内部始终在他的右侧。判断后向面的方法判断后向面的方法P P137137：背面剔除背面剔除法向向量N 视线向量V法向向量

8、N 法向向量N9090非垂直投影转换成垂直投影非垂直投影转换成垂直投影 物体之间的遮挡关系与投影中心和投影方物体之间的遮挡关系与投影中心和投影方向有着密切的关系，对物体的可见性判定向有着密切的关系，对物体的可见性判定也和投影方式有密切的关系。也和投影方式有密切的关系。如果投影为垂直投影，则多边形在如果投影为垂直投影，则多边形在oxyoxy平面平面上的投影可由忽略了上的投影可由忽略了z z坐标的顶点得到，从坐标的顶点得到，从而可大大减少计算量。而可大大减少计算量。7.2多面体的隐藏线消除讨论隐藏线消除问题，总假定它们讨论隐藏线消除问题，总假定它们是用线框方式来表示的。在这种方是用线框方式来表示的

9、。在这种方式下多面体用棱来表示。式下多面体用棱来表示。如果能如果能把各棱上可见和不可见部分把各棱上可见和不可见部分的分界点找到的分界点找到，消隐问题也就迎刃，消隐问题也就迎刃而解了。而解了。这些分界点都是多面体的各棱在这些分界点都是多面体的各棱在oxyoxy平面上投影间的交点，如图。平面上投影间的交点，如图。这样，问题就转化成了在这样，问题就转化成了在oxyoxy平面平面上求很多直线的交点的计算。上求很多直线的交点的计算。 BC,BA,BG，EA为隐藏线如果消隐对象有如果消隐对象有N N条棱，用两两求交条棱，用两两求交的方法求所有交点的工作量为的方法求所有交点的工作量为 。实际上交点个数远小于

10、实际上交点个数远小于 ，如图的，如图的多面体有多面体有1515条边，棱在条边，棱在oxyoxy平面上的平面上的投影相互间只有投影相互间只有5 5个交点。个交点。问题在于如何能预先知道它们是不相问题在于如何能预先知道它们是不相交的，从而把它们排挤在求交计算之交的，从而把它们排挤在求交计算之外。外。( (可用可用7.17.1中方法中方法求棱边投影的包求棱边投影的包围盒，剔除后向面技术围盒，剔除后向面技术) ) 棱间交点只有五个在oxy平面上求很多直线的交点的计算要对物体一个一个来考虑，如考虑体要对物体一个一个来考虑，如考虑体A A的显示时，的显示时，对对Step1-3Step1-3可采用边界盒方法

11、进行处理。下面讨论对可采用边界盒方法进行处理。下面讨论对Step4Step4的处理技术。的处理技术。Step4Step4 求求L L和多边形和多边形E E中的边的交点，中的边的交点，确定确定L L的可见部分的可见部分。Step3Step3 对对多边形多边形G G的每一条边的每一条边L L，从集合从集合C C中找出中找出可能可能遮挡它遮挡它的所有多边形的所有多边形E E。Step2Step2 对对体体A A的每个多边形的每个多边形G G，要从要从B B中找出中找出可能可能遮挡它的所遮挡它的所有多边形的集合有多边形的集合C C。step1step1 确定确定可能可能遮挡遮挡体体A A的那些体集合的

12、那些体集合B B ( (包括体包括体A A本身本身) )。隐藏线消除隐藏线消除( (物体用线框图表示物体用线框图表示) )实际计算过程实际计算过程 ：设边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在在O

13、xyOxy平面平面 的投影相交，求出其交点。的投影相交，求出其交点。只只保留在保留在v vi i v vj j 上的对应点在多边形上的对应点在多边形E E后边的交点。后边的交点。若无交点，这时要判断若无交点，这时要判断v vi i或或v vj j在在OxyOxy平平 面上的投影是否在面上的投影是否在E E的投影的内部，的投影的内部， 若是，则若是，则v vi iv vj j就会整个被就会整个被E E所遮挡。所遮挡。确定确定L L的可见部分的具体计算过程的可见部分的具体计算过程 ：（1 1）确定）确定L L顶点处与遮挡多边形的前后位置关系顶点处与遮挡多边形的前后位置关系l 设点设点 的坐标为的坐

14、标为 ，若，若 ，则，则 在多边形所在平面的前面，否则认为在多边形所在平面的前面，否则认为 在多边在多边 形所在平面的后面。形所在平面的后面。l 设多边形的顶点为设多边形的顶点为 , , , , 其坐标为其坐标为 i i=1,2,=1,2, ,L L。 任取三个不在一直线上的顶点，设为任取三个不在一直线上的顶点，设为 , , , , , 记向量记向量 , ,则多边形则多边形E E所在的平所在的平 面方程为面方程为（2 2）确定）确定L L与遮挡多边形的交点同遮挡多边形的前后与遮挡多边形的交点同遮挡多边形的前后 位置关系：位置关系：为了判断边为了判断边v vi iv vj j和多边形在和多边形在

15、oxyoxy平面的投影之间是否有交点，平面的投影之间是否有交点，可首先计算求边可首先计算求边v vi iv vj j和多边形的边界在和多边形的边界在oxyoxy平面上投影的交点，平面上投影的交点，我们可以把我们可以把v vi iv vj j的投影线段用参数方程表示的投影线段用参数方程表示: : 多边形上任一边的投影用用参数方程表示多边形上任一边的投影用用参数方程表示: :求交点时解方程求交点时解方程: :可得可得只有当只有当00l l11和和00t t 11时线段和线段时线段和线段v vi iv vj j在在oxyoxy平面上平面上 的投影才有交点的投影才有交点为了判断为了判断v vI Iv

16、vj j上对应交点的点是在多边形所在平面的前面上对应交点的点是在多边形所在平面的前面还是后面，则要去比较还是后面，则要去比较 和和 ，若前者大于后者，则若前者大于后者，则v vi iv vj j上交点的对应点在多边形所在上交点的对应点在多边形所在平面的前面，否则在后面。平面的前面，否则在后面。 这个信息也要和交点的信息这个信息也要和交点的信息一起保存起来。一起保存起来。QiQj进入或走出多边形 当当 000时，时，Q Qi iQ Qj j由多边形内离由多边形内离开多边形到多边形外（该交点称开多边形到多边形外（该交点称为出点）。为出点）。（3 3）确定交点和多边形的关系：是进点还是出点）确定交点

17、和多边形的关系：是进点还是出点P P140由式由式(7.9)(7.9)可知可知 , ,其中（）其中（）z z是指向量在是指向量在z z轴上的投影。轴上的投影。判断Qi点在多边形内或外确定Qi在多边形内或外可以从Qi点出发沿x轴的正向作一射线，如图。若该射线和多边形边界的交点个数是奇数，则Qi在多边形内，否则就在多边形外。但正确地找到交点的个 数并不容易。如图点Q6处，由于舍入误差，计算时可能认为Q5Q6，Q6Q7和QiF均有交点，也可能算出一个交点或没有求出交点，不同的交点数可得到完全不同的结果。-需要特殊处理 （4 4）确定）确定Q Qi i起点和多边形的关系起点和多边形的关系不可见阶不可见

18、阶ivordivord这里要分两步来做这里要分两步来做( (P140-141)P140-141)：Step2.Step2.确定边确定边Q Qi iQ Qj j与遮挡多边形交点处的不可见阶。与遮挡多边形交点处的不可见阶。Step1.Step1.确定边确定边Q Qi iQ Qj j顶点处的不可见阶顶点处的不可见阶它是一个数字，是某个确定的点的属性它是一个数字，是某个确定的点的属性代表了边上从该点到下一个交点的部分被几个多边形代表了边上从该点到下一个交点的部分被几个多边形遮挡。遮挡。（5 5）确定）确定L L的可见部分的可见部分首先对直线段首先对直线段QiQj与所有多边形交点按参与所有多边形交点按参

19、数数S由小到大排序由小到大排序确定起点确定起点Qi处的不可见阶，就是遮挡他的处的不可见阶，就是遮挡他的多边形的个数，即多边形的个数，即S0处的不可见阶处的不可见阶Si处的不可见阶是：当其为进点时，为处的不可见阶是：当其为进点时，为Si-1 处的加处的加1；为出点时，；为出点时，Si-1 处的减处的减1L的可见部分为的可见部分为SiSi+1 ，其中，其中Si的不可见阶的不可见阶为为0时时7.3 区域子分算法区域子分算法（warnock）是一种所谓分而治之的算法。整个屏幕称为窗口，分而治之算法是一个递推的四等分过程，每一次把矩形的窗口等分成四个相等的小矩形，分成的矩形也称为窗口。每一次子分，均要把

20、要显示的多边形和窗口的关系作一判断。子分的过程这种关系可有以下四种，即这种关系可有以下四种，即多边形包围了窗口多边形和窗口相交窗口包围了多边形窗口和多边形分离窗口 在窗口和每个多边形的关系确定之后，有些窗口内的图形便可显示了。它们属于下列四种情况之一。l所有所有多边形都和窗口分离 这时只要把窗口内所有的象素填上背景颜色。l只有一个只有一个多边形和窗口相交，或这个多边形包含在窗口内。这时先对窗口内每一象素填上背景颜色，再对窗口内多边形部分用扫描线算法填色l只有一个只有一个包围窗口的多边形 窗口用包围多边形的颜色填充。l如果有多个如果有多个多边形和窗口的关系分别是相交、内含或包围，但是有一个但是有

21、一个包围窗口的多边形在其它多边形前面 整个窗口用该包围多边形的颜色填充。对上述四种情况不成立的窗口再一分为四。分得的窗口重复上述的处理。窗口的边长越分越短，分了若干次后，窗口的边长就和一个象素的宽度一样了，这时这个窗口对应的象素的颜色可取成最靠近观察者的多边形的颜色，或和这个窗口相交的多边形颜色的平均值。 7.4 基于多边形的子分算法目的是尽量减少对窗口划分的次数。 用多边形的边界来对窗口作划分多边形的边界来对窗口作划分的方法,是对基于窗口子分算法的改进。要消隐的多边形对多边形按照对多边形按照z z值由大到小进行排序，值由大到小进行排序，z z值最大的为裁剪窗口值最大的为裁剪窗口算法思想：算法

22、思想：对各多边形在深度方向作初步 的排序把多边形序列中的第一个多边 形（裁剪多边形）取为裁减窗口。 多边形序列中的其它的多边形 都要被此窗口裁剪。裁剪结果要建立两个多边形序 列表 消隐多边形的裁剪Ni为窗口内的多边形表；内部表内部表: :放入位于窗口内的部分放入位于窗口内的部分no为窗口外的多边形表外部表外部表: :放入位于窗口外的部分放入位于窗口外的部分确定裁剪多边形（即取为窗口的那个多边形）是否比内部表中的多边形更靠近观察者如果是则内部表中的其他多边形都被其遮挡，可把该多边形区域填上裁剪多边形的颜色如果发现内部表中某多边形H比裁剪多边形更靠近观察者，这时则只好把多边形H的原始多边形（即未被

23、裁剪时的多边形）代替原来的裁剪多边形重复上述工作。接着处理外部表中的各多边形，把外部表中的第一多边形作为裁剪窗口，重复上述工作这一过程要重复到外部表中不再有多边形为止要消隐的多边形 消隐多边形的裁剪Ni为窗口内的多边形表；no为窗口外的多边形表7.5 Z缓冲器算法和扫描线算法z缓冲器算法是最简单的消除隐藏面算法之一基本思想：对屏幕上每一个像素点，找到此像素投影线与所有多边形交点中离观察者最近的点，此点的属性值即为这一屏幕像素点的属性值z缓冲器是一组存贮单元其单元个数和屏幕上象素的个数相同也和帧缓冲器的单元个数相同，它们之间一一对应。算法 步骤l在把显示物体的每个面上每一点的属性（颜色或灰度）值

24、填入帧缓冲器相应单元前，要把这点的z坐标值和z缓冲器中相应单元内的值作比较。只有前者大于后者时才改变帧缓冲器的那一个单元的值，同时只有前者大于后者时才改变帧缓冲器的那一个单元的值，同时z z缓冲器中相应缓冲器中相应单元的值也要改成这点的单元的值也要改成这点的z z坐标值。坐标值。如果这点的如果这点的z z坐标值小于坐标值小于z z缓冲器中相应单元的值，则说明对应象素已显示了缓冲器中相应单元的值，则说明对应象素已显示了物体上一个点的属性，该点比要考虑的点更接近观察者。这样，无论帧缓冲物体上一个点的属性，该点比要考虑的点更接近观察者。这样，无论帧缓冲器或器或z z缓冲器相应单元的值均不应改变。缓冲

25、器相应单元的值均不应改变。l对显示物体的每一个面上的每一个点都做上述处理后，便可得到消除了隐藏面的图。 l图形消隐和生成的过程就是给帧缓冲器和z缓冲器中相应单元填值的过程设置两个缓冲器数组，即z缓冲器和帧缓冲器：Zdepth,Frame流程：流程：for（场景中的每一个多边形）（场景中的每一个多边形） 扫描转换该多边形；扫描转换该多边形； for（多边形所覆盖的每一个像素点（多边形所覆盖的每一个像素点(x,y)） 计算多边形在该像素点的深度值计算多边形在该像素点的深度值z(x,y)； if（z(x,y) Z-buf中对应此像素点中对应此像素点(x,y)的的z值）值） 把多边形在把多边形在(x,

26、y)处的深度值处的深度值z(x,y)存入存入Z-buf中的中的(x,y)处；处； 把多边形在把多边形在(x,y)处的亮度值存入处的亮度值存入f-buf中的中的(x,y)处；处； 当所有的多边形都处理完后，帧缓冲器中的内容即为消除隐藏面后的图像当所有的多边形都处理完后，帧缓冲器中的内容即为消除隐藏面后的图像l为了克服这个缺点如果把这个区域取成屏幕上一行，就得到了扫描线z缓冲器算法。可把整个平面分成若干区域，一区一区来显示，这样z缓冲器的单元数只要等于屏幕上一个区域的象素个数。l算法的缺点工作量较大：显示物体的表面和象素对应的每一个点处都要计算它的z值要很大的z缓冲器不需要对显示物体的面预先进行排

27、序简单、可靠l算法的优点扫描线扫描线z z缓冲器缓冲器 -算法算法 思想思想对每一条扫描线来说，把相应的帧缓冲器单元置成底色，在z缓冲器中存放z的极小值。从最上面的一条扫描线开始工作，向下对每一条扫描线作处理。z缓冲器的单元数可以取成和一行上的象素数目相同。对每个多边形检查它在oxy平面上的投影和当前的扫描是否相交，若不相交，则不考虑该多边形。如果相交，则扫描线和多边形边界的交点事实上是成对地出现对每对交点中间的象素计算多边形所在平面对应点的深度（即z值），并和z缓冲器中相应单元存放的深度值作比较。若前者大于后者，则z缓冲器的相应单元内容要被求得的平面深度代替，帧缓冲器相应单元的内容也要换成该

28、平面的属性。对所有的多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐后的图形。对帧缓冲器每一行的单元都填上相应内容后也就得到了整个消隐后的图。 流程：流程：for (每条扫描线每条扫描线)将扫描线帧缓冲器将扫描线帧缓冲器f_buf置成背景色；置成背景色； 将扫描线深度缓冲器将扫描线深度缓冲器Z_buf置成最小值；置成最小值；for (每个多边形每个多边形)求出该多边形与当前扫描线的相交区间；求出该多边形与当前扫描线的相交区间；for (相交区间内每个象素点相交区间内每个象素点(x,y)计算多边形在该处的深度值计算多边形在该处的深度值z；if (多边形在该处的深度值多边形在该处的深度值z

29、Z_buf在该处的值在该处的值)用多边形在该处的深度值用多边形在该处的深度值z取代取代Z_buf在该处的值；在该处的值； 用多边形在该处的亮度值取代用多边形在该处的亮度值取代f_buf在该处的值；在该处的值；用用f_buf的内容显示当前扫描线；的内容显示当前扫描线；上述算法要花费很多时间去计算上述算法要花费很多时间去计算在处理每一条扫描线时，要检查各多边形是否和该线相交在处理每一条扫描线时，要检查各多边形是否和该线相交还要计算多边形所在平面上很多点的还要计算多边形所在平面上很多点的z z值值为了使这些工作能高效率地进行，可采取类似多边形扫描为了使这些工作能高效率地进行，可采取类似多边形扫描转换

30、的扫描线算法处理。转换的扫描线算法处理。 扫描线z缓冲器 -算法 分析数据结构数据结构y36 7 811101198713图 7.15 要消隐的物体xo1/7107 28 2 1 2一个边活化表一个多边形活化表一个边Y筒一个多边形Y筒扫描线算法 -算法数据结构每个筒的深度和显示屏幕行数相同。每个筒的深度和显示屏幕行数相同。根据多边形顶点根据多边形顶点Y Y坐标最大值来决定放入多边形坐标最大值来决定放入多边形Y Y筒的相应行数。筒的相应行数。多边形多边形Y Y筒要记录多边形所在平面方程筒要记录多边形所在平面方程axax+ +byby+ +czcz+ +d d=0=0系数系数a a，b b，c c

31、和和d d，还要记录和该多边形在还要记录和该多边形在oxyoxy平面上的投影相交的扫描线的条数平面上的投影相交的扫描线的条数y y，以及多边形的属性以及多边形的属性colorcolor和编号和编号IPIP。 367811101198713图 7.15 要消隐的物体xo建立一个多边形建立一个多边形Y Y筒筒每个筒的深度和显示屏幕行数相同。每个筒的深度和显示屏幕行数相同。根据边两端点较大的根据边两端点较大的Y Y坐标值为决定放入边坐标值为决定放入边Y Y筒的相应行数。筒的相应行数。边边Y Y筒中记录的每一条边要保存下列信息：筒中记录的每一条边要保存下列信息：和该边在和该边在oxyoxy平面上的投影

32、相交的扫描线条数平面上的投影相交的扫描线条数y y，该该投投影影和和相相邻邻的的两两条条扫扫描描线线交交点点的的x x坐坐标标的的差差x x，( (由由上上到到下下扫扫描描) )该边所属多边形的编号该边所属多边形的编号IPIP及边的上端点及边的上端点x x坐标的值坐标的值x x。 367811101198713图 7.15 要消隐的物体xo1/7107 28 2 1 2建立一个边建立一个边Y Y筒筒记记录录在在oxyoxy平平面面上上的的投投影影和和当当前前考考虑虑的的扫扫描描线线相相交交的的多多边形，边形，例例，当当扫扫描描线线对对应应y y=10=10或或1111时时，多多边边形形活活化化

33、表表只只有有一一个个多多边边形。形。当当y y=8=8时时多多边边形形活活化化表表如如图图。表表中中的的y y值值是是已已经经过过修修改改的的。（由上到下扫描，故由上到下扫描，故 y=5,y=5,和和 y=7y=7）367811101198713图 7.15 要消隐的物体xo建立一个多边形活化表建立一个多边形活化表边活化表中存放多边形边界和扫描线相交的边对。边活化表中存放多边形边界和扫描线相交的边对。例如图中例如图中y y=6=6的扫描线上的边活化表中应有两个对边，的扫描线上的边活化表中应有两个对边，一是和多边形一是和多边形在在oxyoxy平面上的投影相交的两条边平面上的投影相交的两条边另一是

34、和多边形另一是和多边形投影相交的两条边。投影相交的两条边。367811101198713图 7.15 要消隐的物体xo建立一个边活化表建立一个边活化表边活化表中每一边对要保存下列信息边活化表中每一边对要保存下列信息xl左交点的左交点的x x坐标值坐标值xl左交点所在边和两相邻扫描线交点的左交点所在边和两相邻扫描线交点的x x坐标之差坐标之差yl以以和和左左交交点点所所在在边边相相交交的的扫扫描描线线条条数数为为初初值值，以以后每处理一条扫描线减后每处理一条扫描线减1 1xr右交点的右交点的x x坐标值坐标值xr右交点所在边和两相邻扫描线交点的右交点所在边和两相邻扫描线交点的x x坐标之差坐标之

35、差要消隐的物体yr以以和和右右交交点点所所在在边边相相交交的的扫扫描描线线条条数数为为初初值值，以以后每处理一条扫描线减后每处理一条扫描线减1 1zl左交点处多边形所在平面的深度值左交点处多边形所在平面的深度值zx沿沿扫扫描描线线向向右右走走过过一一个个象象素素时时，多多边边形形所所在在平平面面深深度度的的增增量量。对对方方程程为为ax+by+cz+dax+by+cz+d=0=0的的平平面面来来说说z zx x= =a a/ /c c（c c00）zy沿沿y y方方向向向向下下移移过过一一根根扫扫描描线线时时，多多边边形形所所在在平平面面深深度度的的增增量量。对对方方程程为为ax+by+cz+

36、dax+by+cz+d=0=0的的平平面面来来说说z zy y= =b b/ /c c（c c00）IP所在多边形的编号所在多边形的编号1 1）、建建立立多多边边形形y y筒筒和和边边y y筒筒，初初始始化化多多边边形形和和边边的的活活化化 表为空。表为空。2 2）、以最上面的扫描线为当前扫描线。）、以最上面的扫描线为当前扫描线。3 3）、对对当当前前扫扫描描线线y y，把把帧帧缓缓冲冲器器相相应应行行置置成成底底色色，z z缓缓冲器的各单元放冲器的各单元放z z的极小值。的极小值。4 4）、检检查查多多边边形形的的y y筒筒，如如果果有有新新的的多多边边形形涉涉及及当当前前扫扫描描线线，则则

37、把把它它放放入入多多边边形形活活化化表表中中。若若有有新新的的多多边边形形加加入入多多边边形形活活化化表表，则则要要把把该该多多边边形形在在OxyOxy平平面面上上的的投投影和扫描线相交的边对加入边活化表中。影和扫描线相交的边对加入边活化表中。算法步骤：算法步骤：扫描线z缓冲器 -算法 步骤5 5）、对边活化表中的每个边对，令）、对边活化表中的每个边对，令 ，对每一个满，对每一个满足足 的坐标为的坐标为 的像素从左到右依次进行处的像素从左到右依次进行处理。理。P P164164具体处理具体处理6 6）、若所有扫描线都已经处理完，则算法结束，否则选）、若所有扫描线都已经处理完，则算法结束，否则选

38、下一条扫描线为当前扫描线，转步骤下一条扫描线为当前扫描线，转步骤3 3），直到所有的扫），直到所有的扫描线都处理完。描线都处理完。7.6 优先级表算法算法思想算法思想: :按多边形离观察者的远近来建立一张表距观察者远的优先级低，近的优先级高。如果这张表能正确地建立好，那么只要从优先级低的多边形开始，依次把多边形的颜色填入帧缓冲存储器中以形成该多边形的图形直到优先级最高的多边形的图形送入帧缓冲器后，整幅图就显示好了。这种算法也称为油画家算法油画家算法因为油画家绘画时常先画底色，然后再一层层往上画。 算法的关键-对多边形做正确的排序。下面给出一个动态的算法：（1）根据每个多边形顶点z坐标的极小值z

39、min的大小，按由小到大对它们做初步排序，并把它们组成一个链表。（2）若链表中只有一个多边形，则算法结束。 否则取表头多边形为P。(3) 设Q为链表中P之外的任一多边形。 若对所有Q都有 , 则P不会遮挡其它多边形，在链表中去除P，转（2）； 否则，若所有Q都满足下面四项中的一项，则在链表中去除P，转（2）。 否则，对不满足此四项条件之一的Q，交换P和Q，转（3）。 P和Q在平面 oxy上的投影不相交Q 的各顶点均在P的近视点的一侧P 的各顶点均在Q的远离视点的一侧P和Q在oxy平面上投影的边界盒在x或y方向上不相交图7.21 互相遮挡虽然P并不遮挡Q，但它也不能使上述四项检查成立。对这样的特

40、殊情况，需要把P沿Q平面一分为二，见图7.22，把多边形序列中原多边形P从序列中去掉，而把P分成的两个多边形加入链表中，这样可避免使多边形P和Q不断地循环进行交换。某些特殊情况图7.22 用Q所在平面把P一分为二 互相遮挡 优点优点: :可以较好地解决透明或半透明物体的存在可采用反走样算法改善多边形边界的显示效果。用来解决动态显示问题时,可大大提高效率。 图7.23 视点在不同区域有不同的优先级视点所在区域ABCD优先级表用来解决动态显示问题时,可大大提高效率对飞机驾驶员着陆进行模拟训练时要显示消隐后的跑道周围情况，这时景物是不变的，仅视点发生变化。可对不同的视点位置把景物的优先级排序表预先算

41、好，然后再用油画家算法显示图形，这样便可使消隐过程加速，实现动态显示。有了这个优先级表，不论视点在哪一个区域，均可很容易地用油画家算法得到消除隐藏面的图。优先级表Ray CastingAppel提出提出建立在几何光学基础之上建立在几何光学基础之上对于包含曲面、特别是球面的场景效率高对于包含曲面、特别是球面的场景效率高7.77.7 光线投射算法光线投射算法基本思想基本思想观察者之所以能看见景物观察者之所以能看见景物光源发出的光照射到物体上的结果其中一部分光到达人的眼睛引起视觉到达观察者眼中的光到达观察者眼中的光由物体表面反射通过表面折射或透射若若从光源出发跟踪光线从光源出发跟踪光线则只有极少量的

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

43、，算法结束 视点光线投影面上的像素位置物体假设假设视点视点位于z轴正向投影平面投影平面（屏幕）垂直于z轴反向跟踪一条穿过像素点的光线光线投射算法光线投射算法 for(y=0;y=ymax;y+) for(x=0;x0，平面z=zn 是最靠近观察者的从平面z=zn 上的曲线y = f（x，zn）开始，对水平方向每个象素的对应x坐标值xj，计算yjn= f（xjn，zn） 若yjnyu（j），则点（xj, yjn, zn）是可见点，并把yu（j）内容换成yjn。消隐算法消隐算法-对应对应z z= =z zi i=const=const的一族曲线的消隐算法的一族曲线的消隐算法若yjnyu(j)，则点（xj, yjn, zn）为不可见，不要改变yu(j)的内容。对z= zn 平面上的曲线完成上述工作后，再对平面z=zn1上的曲线重复上述工作，这样按z值递减方向一条一条曲线处理过去，就得到一组消除隐藏线的曲线族了。