第7章隐藏线和隐藏面的消除.ppt

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

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

3、消隐算法的前提假定：,本章说明的各种消隐方法都假定构成对象的不同面不能相互贯穿，如图,贯穿和循环遮挡,例如用图中的虚线便可把原来循环遮挡的三个平面，分割成不互相循环遮挡的四个面。,也不能有循环遮挡的情况，如果有这种情况，可把它们剖分成互不贯串和不循环遮挡的情况。,假定2：,7.1可见面判断的有效技术,减少求交计算的常用技术：,用边界盒排除不相交的线段求交,非垂直投影转换成垂直投影,把后向面全部去掉,用边界盒排除不相交的线段求交,边界盒：,一个物体的边界盒是指能够包含该物体的 一个几何形状，该形状有较简单的边界。,边界盒的形状可以是长方形（体）状或是圆（球） 形状的。,边界盒可用于投影边界盒，可

4、用于物体本身边界盒， 还可用于某一维方向上的边界盒。,包围物体投影的边界盒不相交的情况,图7.3 两个物体投影在(x,y)平面，包围投影的边界盒,包围物体投影的边界盒相交的情况,一个好的包围盒要具有两个条件：,包围和充分紧密包围着形体；,对其的测试比较简单。,边界盒可用于包围物体本身而不只是他们的投影，在此情况下，边界盒是三维的。,边界盒也可用于在某一维方向上进行包围，以判断两个物体在该方向上是否相交。,1,zmin1,zmax1,2,zmin2,zmax2,生成边界盒的一个较简单的方法(P136)：,判断两条直线是否相交,多边形的判定,把内法线方向背向视点的面称为前向面 内法线方向指向视点的

5、面（即外法线方向背离视点）称为后向面 多面体面的顶点排序,IJFGH，FABG，HCDI，IDEJ所在的面为前向面 JEAF，DEABC，HGBC所在的面为后向面,去掉后向面,设多边形F的顶点为 ，顶点 的坐标为 。(次序如图所示) 如果是一凸多边形，可只取一个三角形计算有向面积 凹多边形的内法线方向，可以计算多边形在oxy平面上投影的有向面积。有向面积sp可如下计算 如果 ，说明其外法线方向与z轴正向的夹角90,则F所在的面为后向面。 如果 ，说明其外法线方向与z轴正向的夹角90,则F所在的面为前向面。,判断后向面的方法P137：,背面剔除,非垂直投影转换成垂直投影,物体之间的遮挡关系与投影

6、中心和投影方向有着密切的关系，对物体的可见性判定也和投影方式有密切的关系。,如果投影为垂直投影，则多边形在oxy平面上的投影可由忽略了z坐标的顶点得到，从而可大大减少计算量。,7.2多面体的隐藏线消除,讨论隐藏线消除问题，总假定它们是用线框方式来表示的。在这种方式下多面体用棱来表示。 如果能把各棱上可见和不可见部分的分界点找到，消隐问题也就迎刃而解了。 这些分界点都是多面体的各棱在oxy平面上投影间的交点，如图。 这样，问题就转化成了在oxy平面上求很多直线的交点的计算。,如果消隐对象有N条棱，用两两求交的方法求所有交点的工作量为 。 实际上交点个数远小于 ，如图的多面体有15条边，棱在oxy

7、平面上的投影相互间只有5个交点。 问题在于如何能预先知道它们是不相交的，从而把它们排挤在求交计算之外。(可用7.1中方法求棱边投影的包围盒，剔除后向面技术),棱间交点只有五个,在oxy平面上求很多直线的交点的计算,要对物体一个一个来考虑，如考虑体A的显示时，,对Step1-3可采用边界盒方法进行处理。下面讨论对Step4的处理技术。,Step4 求L和多边形E中的边的交点，确定L的可见部分。,Step3 对多边形G的每一条边L，从集合C中找出可能遮挡它的所有多边形E。,Step2 对体A的每个多边形G，要从B中找出可能遮挡它的所有多边形的集合C。,step1 确定可能遮挡体A的那些体集合B (

8、包括体A本身)。,隐藏线消除(物体用线框图表示)实际计算过程 ：,设边L的顶点是vi和vj，对边vivj和每一个可能遮挡它的 多边形E，都要作下列计算和判断，以确定其隐藏关系,如果vi和vj都在多边形E所在平面靠近观察者的一侧， 则E不能遮挡直线段vivj,如果vi和vj不都在多边形E所在平面靠 近观察者的一侧，且vivj和E在Oxy平面 的投影相交，求出其交点。只保留在vi vj 上的对应点在多边形E后边的交点。,若无交点，这时要判断vi或vj在Oxy平 面上的投影是否在E的投影的内部， 若是，则vivj就会整个被E所遮挡。,确定L的可见部分的具体计算过程 ：,（1）确定L顶点处与遮挡多边形

9、的前后位置关系,设点 的坐标为 ，若 ，则 在多边形所在平面的前面，否则认为 在多边 形所在平面的后面。,设多边形的顶点为 , , 其坐标为 i=1,2,L。 任取三个不在一直线上的顶点，设为 , , , 记向量 ,则多边形E所在的平 面方程为,（2）确定L与遮挡多边形的交点同遮挡多边形的前后 位置关系：,为了判断边vivj和多边形在oxy平面的投影之间是否有交点， 可首先计算求边vivj和多边形的边界在oxy平面上投影的交点， 我们可以把vivj的投影线段用参数方程表示:,多边形上任一边的投影用用参数方程表示:,求交点时解方程:,可得,只有当0l1和0t 1时线段和线段vivj在oxy平面上

10、 的投影才有交点,为了判断vIvj上对应交点的点是在多边形所在平面的前面 还是后面，则要去比较 和 ， 若前者大于后者，则vivj上交点的对应点在多边形所在 平面的前面，否则在后面。,这个信息也要和交点的信息一起保存起来。,（3）确定交点和多边形的关系：是进点还是出点P140,由式(7.9)可知 , 其中（）z是指向量在z轴上的投影。,判断Qi点在多边形内或外,若该射线和多边形边界的交点个数是奇数，则Qi在多边形内，否则就在多边形外。,但正确地找到交点的个 数并不容易。如图点Q6处，由于舍入误差，计算时可能认为Q5Q6，Q6Q7和QiF均有交点，也可能算出一个交点或没有求出交点，不同的交点数可

11、得到完全不同的结果。-需要特殊处理,（4）确定Qi起点和多边形的关系,不可见阶ivord,这里要分两步来做(P140-141)：,Step2.确定边QiQj与遮挡多边形交点处的不可见阶。,Step1.确定边QiQj顶点处的不可见阶,它是一个数字，是某个确定的点的属性,代表了边上从该点到下一个交点的部分被几个多边形遮挡。,（5）确定L的可见部分,首先对直线段QiQj与所有多边形交点按参数S由小到大排序 确定起点Qi处的不可见阶，就是遮挡他的多边形的个数，即S0处的不可见阶 Si处的不可见阶是：当其为进点时，为Si-1 处的加1；为出点时，Si-1 处的减1 L的可见部分为SiSi+1 ，其中Si

12、的不可见阶为0时,7.3 区域子分算法,区域子分算法（warnock）是一种所谓分而治之的算法。整个屏幕称为窗口，分而治之算法是一个递推的四等分过程，每一次把矩形的窗口等分成四个相等的小矩形，分成的矩形也称为窗口。,每一次子分，均要把要显示的多边形和窗口的关系作一判断。,子分的过程,这种关系可有以下四种，即,在窗口和每个多边形的关系确定之后，有些窗口内的图形便可显示了。它们属于下列四种情况之一。,所有多边形都和窗口分离 这时只要把窗口内所有的象素填上背景颜色。,只有一个多边形和窗口相交，或这个多边形包含在窗口内。这时先对窗口内每一象素填上背景颜色，再对窗口内多边形部分用扫描线算法填色,只有一个

13、包围窗口的多边形 窗口用包围多边形的颜色填充。,如果有多个多边形和窗口的关系分别是相交、内含或包围，但是有一个包围窗口的多边形在其它多边形前面 整个窗口用该包围多边形的颜色填充。,对上述四种情况不成立的窗口再一分为四。分得的窗口重复上述的处理。 窗口的边长越分越短，分了若干次后，窗口的边长就和一个象素的宽度一样了， 这时这个窗口对应的象素的颜色可取成最靠近观察者的多边形的颜色， 或和这个窗口相交的多边形颜色的平均值。,7.4 基于多边形的子分算法,目的是尽量减少对窗口划分的次数。,用多边形的边界来对窗口作划分的方法,是对基于窗口子分算法的改进。,要消隐的多边形,算法思想： 对各多边形在深度方向

14、作初步 的排序 把多边形序列中的第一个多边 形（裁剪多边形）取为裁减窗口。 多边形序列中的其它的多边形 都要被此窗口裁剪。 裁剪结果要建立两个多边形序 列表,消隐多边形的裁剪,确定裁剪多边形（即取为窗口的那个多边形）是否比内部表中的多边形更靠近观察者 如果是则内部表中的其他多边形都被其遮挡，可把该多边形区域填上裁剪多边形的颜色 如果发现内部表中某多边形H比裁剪多边形更靠近观察者，,这时则只好把多边形H的原始多边形（即未被裁剪时的多边形）代替原来的裁剪多边形重复上述工作。,接着处理外部表中的各多边形，把外部表中的第一多边形作为裁剪窗口，重复上述工作 这一过程要重复到外部表中不再有多边形为止,要消

15、隐的多边形,消隐多边形的裁剪 Ni为窗口内的多边形表；no为窗口外的多边形表,7.5 Z缓冲器算法和扫描线算法,z缓冲器算法是最简单的消除隐藏面算法之一 基本思想：对屏幕上每一个像素点，找到此像素投影线与所有多边形交点中离观察者最近的点，此点的属性值即为这一屏幕像素点的属性值 z缓冲器是一组存贮单元 其单元个数和屏幕上象素的个数相同 也和帧缓冲器的单元个数相同，它们之间一一对应。,算法 步骤,在把显示物体的每个面上每一点的属性（颜色或灰度）值填入帧缓冲器相应单元前，要把这点的z坐标值和z缓冲器中相应单元内的值作比较。,只有前者大于后者时才改变帧缓冲器的那一个单元的值，同时z缓冲器中相应单元的值

16、也要改成这点的z坐标值。,如果这点的z坐标值小于z缓冲器中相应单元的值，则说明对应象素已显示了物体上一个点的属性，该点比要考虑的点更接近观察者。这样，无论帧缓冲器或z缓冲器相应单元的值均不应改变。,对显示物体的每一个面上的每一个点都做上述处理后，便可得到消除了隐藏面的图。,图形消隐和生成的过程就是给帧缓冲器和z缓冲器中相应单元填值的过程,设置两个缓冲器数组，即z缓冲器和帧缓冲器：Zdepth, Frame,流程： for（场景中的每一个多边形） 扫描转换该多边形； for（多边形所覆盖的每一个像素点(x,y)） 计算多边形在该像素点的深度值z(x,y)； if（z(x,y) Z-buf中对应此

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

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

19、了消隐后的图形。 对帧缓冲器每一行的单元都填上相应内容后也就得到了整个消隐后的图。,流程： for (每条扫描线) 将扫描线帧缓冲器f_buf置成背景色； 将扫描线深度缓冲器Z_buf置成最小值； for (每个多边形) 求出该多边形与当前扫描线的相交区间； for (相交区间内每个象素点(x,y) 计算多边形在该处的深度值z； if (多边形在该处的深度值z Z_buf在该处的值) 用多边形在该处的深度值z取代Z_buf在该处的值； 用多边形在该处的亮度值取代f_buf在该处的值； 用f_buf的内容显示当前扫描线； ,上述算法要花费很多时间去计算 在处理每一条扫描线时，要检查各多边形是否和

20、该线相交 还要计算多边形所在平面上很多点的z值 为了使这些工作能高效率地进行，可采取类似多边形扫描转换的扫描线算法处理。,扫描线z缓冲器 -算法 分析,数据结构,y,扫描线算法 -算法数据结构,每个筒的深度和显示屏幕行数相同。 根据多边形顶点Y坐标最大值来决定放入多边形Y筒的相应行数。 多边形Y筒要记录多边形所在平面方程ax+by+cz+d=0系数a，b，c和d， 还要记录和该多边形在oxy平面上的投影相交的扫描线的条数y， 以及多边形的属性color和编号IP。,建立一个多边形Y筒,每个筒的深度和显示屏幕行数相同。 根据边两端点较大的Y坐标值为决定放入边Y筒的相应行数。 边Y筒中记录的每一条

21、边要保存下列信息： 和该边在oxy平面上的投影相交的扫描线条数y， 该投影和相邻的两条扫描线交点的x坐标的差x，(由上到下扫描) 该边所属多边形的编号IP 及边的上端点x坐标的值x。,建立一个边Y筒,记录在oxy平面上的投影和当前考虑的扫描线相交的多边形， 例，当扫描线对应y=10或11时，多边形活化表只有一个多边形。 当y=8时多边形活化表如图。表中的y值是已经过修改的。（由上到下扫描，故y=5,和y=7）,建立一个多边形活化表,边活化表中存放多边形边界和扫描线相交的边对。 例如图中y=6的扫描线上的边活化表中应有两个对边， 一是和多边形在oxy平面上的投影相交的两条边 另一是和多边形投影相

22、交的两条边。,建立一个边活化表,边活化表中每一边对要保存下列信息,1）、建立多边形y筒和边y筒，初始化多边形和边的活化 表为空。 2）、以最上面的扫描线为当前扫描线。 3）、对当前扫描线y，把帧缓冲器相应行置成底色，z缓冲器的各单元放z的极小值。 4）、检查多边形的y筒，如果有新的多边形涉及当前扫描线，则把它放入多边形活化表中。若有新的多边形加入多边形活化表，则要把该多边形在Oxy平面上的投影和扫描线相交的边对加入边活化表中。,算法步骤：,扫描线z缓冲器 -算法 步骤,5）、对边活化表中的每个边对，令 ，对每一个满足 的坐标为 的像素从左到右依次进行处理。P164具体处理,6）、若所有扫描线都

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

24、序，并把它们组成一个链表。 （2）若链表中只有一个多边形，则算法结束。 否则取表头多边形为P。,(3) 设Q为链表中P之外的任一多边形。 若对所有Q都有 , 则P不会遮挡其它多边形，在链表中去除P，转（2）； 否则，若所有Q都满足下面四项中的一项，则在链表中去除P，转（2）。 否则，对不满足此四项条件之一的Q，交换P和Q，转（3）。,图7.21 互相遮挡,虽然P并不遮挡Q，但它也不能使上述四项检查成立。对这样的特殊情况，需要把P沿Q平面一分为二，见图7.22，把多边形序列中原多边形P从序列中去掉，而把P分成的两个多边形加入链表中，这样可避免使多边形P和Q不断地循环进行交换。,某些特殊情况,图7

25、.22 用Q所在平面把P一分为二,互相遮挡,优点: 可以较好地解决透明或半透明物体的存在 可采用反走样算法改善多边形边界的显示效果。 用来解决动态显示问题时,可大大提高效率。,图7.23 视点在不同区域有不同的优先级,用来解决动态显示问题时,可大大提高效率,对飞机驾驶员着陆进行模拟训练时要显示消隐后的跑道周围情况，这时景物是不变的，仅视点发生变化。 可对不同的视点位置把景物的优先级排序表预先算好，然后再用油画家算法显示图形，这样便可使消隐过程加速，实现动态显示。 有了这个优先级表，不论视点在哪一个区域，均可很容易地用油画家算法得到消除隐藏面的图。,优先级表,Ray Casting Appel提出 建立在几何光学基础之上 对于包含曲面、特别是球面的场景效率高,7.7 光线投射算法,基本思想 观察者之所以能看见景物 光源发出的光照射到物体上的结果 其中一部分光到达人的眼睛引起视觉 到达观察者眼中的光 由物体表面反射 通过表面折射或透射 若从光源出发跟踪光线 则只有极少量的光能到达观察者的眼睛 效率低 从视点或像素出发，仅对穿过像素的光线反向跟踪 当光线路径到达一个可见的不透明物体的表面时停止追踪,将景物通过透视投影变换到图像空间 反向跟踪一条穿过像素点的光线 决定它与场景中