图形学第5章隐藏线课件

1、第五章第五章 隐藏面和隐藏线的消除隐藏面和隐藏线的消除 三维立体模型主要有:线框结构模型,表面模型,实体模型. 问题:线框结构模型会出现错误理解.投影变换失去了深度信息，往往导致图形的二义性 图5-1 立体出现的不同理解真实感图形真实感图形 1)1)常规视觉上的真实（区分可见和不可见面）。 2)表面效果的真实（表达材质、光照、明暗等）。 可见和不可见面 对于空间任何一个不透明的物体，只能看到该物体上朝向视线方向的那部分表面，而其余的表面是不可能看见的。 对于包含有多个物体的场景，只能看到前面的物体，被挡在后面的物体是不可能看见的。提出问题提出问题 在给定视点和视线方向后，决定场景中哪些物体的表

2、面是可见的，哪些是被遮挡不可见的。 消隐:解决显示三维立体的图形中消去不可见部分的方法,包括隐藏线和隐藏面.消隐算法也就成了真实感图形的基本算法。 线框图 消隐图 真实感图形消隐结果与观察物体有关，也与视点有关。 消隐 要绘出意义明确的，有真实感的立体图形，首先必须消去形体中的不可见部分，而只表现可见部分。这就要去寻求解决显示三维立体的图形中消去不可见部分的方法，称为 消隐 。 消隐隐线 隐面消隐的分类按消隐对象分类线消隐:消隐对象是物体上的边，消除的是物体上不可见的边。 面消隐 :消隐对象是物体上的面，消除的是物体上不可见的面。 按消隐空间分类物体空间的消隐算法 （光线投射、Roberts）

3、：将场景中每一个面与其他每个面比较，求出所有点、边、面遮挡关系。 图像空间的消隐算法 (Zbuffer、扫描线、Warnock)：对屏幕上每个象素进行判断，决定哪个多边形在该象素可见。 物体空间和图像空间的消隐算法 (画家算法):在物体空间中预先计算面的可见性优先级，再在图像空间中生成消隐图。5.1 5.1 多面体的隐藏线消除多面体的隐藏线消除 三维模型一般用三种方法：线框模型、表面模型和实体模型。对于线框模型来说，所谓的消隐就是要消去线框模型中的隐藏线。5.1.1 5.1.1 减少直线求交减少直线求交 线框结构模型,则隐藏线便是某些不可见的棱或棱的一部分。 解决方法:找到各棱上可见和不可见部

4、分的分界点，这些分界点都是多面体的各棱在oxy平面上投影间的交点。 把内法线方向背向视点的面称为前向面，如图5-2中的IJFGH，FABG，HCDI和IDEJ所在的面为前向面，其余为后向面。图图5-2 5-2 棱间交点只有棱间交点只有5 5个个5.1.25.1.2凸多面体的隐线消去凸多面体的隐线消去 1.定义:凸多面体是由多个平面凸多边形包围而成的立体. 2.方法:对于单个凸多面体来说，只要画出了立体上的全部朝前面，也就是正确地画出了消隐后的立体图形，因为凸多面体本身不存在朝前面间的遮挡关系。过程： (1)建立描述立体图形的数据结构； (2)按图形种类进行顶点表变换； (3)按环表计算各面的值

5、，根据其正负号判别是否可见； (4)连点画出可见面的边框线段。1)数据结构数据结构 面表：面号，环指针。 环表：组环逆向顶点号。 顶点表：顶点坐标（x,y,z）。2)内法向的计算内法向的计算 设多边形F的顶点为v1,v2vi，顶点vi坐标为（xi,yi,zi）。顶点的次序： 使观察者在多面体外沿着v1v2vi走时，多边形的内部始终在他的左侧. 计算多边形在oxy平面上投影的有向面积B，计算方法如下：)()(21)()(211111112111121yyxxyyxxvvvvBkkkLkkzkkLk如果B0，则F所在的面为后相面。 平面方程 凸多面体:由若干个平面围成的物体，这些平面方程为：)2

6、, 1(0nidzcybxaiiii平面的法向量n为（ai，bi，ci）或（-ai，-bi，-ci），规定n的选取满足下列条件：对物体内一点P0（x0，y0，z0）使得n（x0，y0，z0）Tdi0，这样规定的法向量n指向了物体内部隐藏面判断 视点与第i个面上一点连线方向为（li，mi，ni），则第i个面为自隐藏面的判断方法是： 0),(),(iiiiiinmlcba 对于任意凸对面体，可先求出所有隐藏面，然后检查每条边，若此边为两隐藏面的交线，则此边是隐藏线，用虚线表示或消除。5.1.3 5.1.3 凹多面体的隐藏线消除凹多面体的隐藏线消除 任意平面体消隐包括凹多面体、立体群。 问题：空间一

7、段线段AB和一个多边形，判断线段是否被多边形遮挡。如果全被遮挡则是隐藏线；若部分遮挡，则求出隐藏部分。 方法:以视点为投影中心，把线段与多边形顶点投影到投影面上，将各对应投影点连线的方程与直线联立求解，即可求得线段与多边形投影的交点。算法思路： (1)计算，判别出所有的朝前面作潜在可见面； (2)处理潜在可见面间的遮挡关系，落实到棱边； (3)求出可见段的交集，绘成图形。 、均为潜在可见面。其前后顺序为，。所以 一条边线可能被多个面所遮挡。 线段AB与多边形投影的关系可能有两种： 线段与多边形的任何边都不相交；线段AB与投影多边形有交点。 1线段与多边形的任何边都不相交 又分两种：即线段AB与

8、投影多边形分离，或线段AB在投影多边形之中。 前一种情况，线段完全可见。 后一种情况，线段完全可见或完全隐藏，边界盒排除不相交的线段求交边界盒排除不相交的线段求交 方法: 把点vi在oxy平面上的投影记成Qi（xi，yi）。直线段Q1Q2的边界盒是一包含这直线的边平行于坐标轴的最小矩形，这个矩形由四个参数 xmin=min（x1，x2），ymin=min（y1，y2） xmax=max（x1，x2），ymax=max（y1，y2） 如果两个边界盒的参数为xmini，ymini，xmaxi，ymaxi，i=1,2.当它们满足 （xmin1 xmax2）或（ymin1 ymax2） （xmin2

9、xmax1）或（ymin2 ymax1） 这两个边界盒不相交，因而原来的两条边也不会相交。 2.线段AB与投影多边形有交点:平面对直线段的遮挡判断算法 (1) 若线段的两端点及视点在给定平面的同侧，线段不被给定平面遮挡，转7 (2) 若线段的投影与平面投影的包围盒无交，线段不被给定平面遮挡，转7 (3)求直线与相应平面的交。若无交点，转4。否则，交点在线段内部或外部。若交点在线段内部，交点将线段分成两段，与视点同侧的一段不被遮挡，另一段在视点异侧，转4再判；若交点在线段外部，转4。 (4)求所剩线段的投影与平面边界投影的所有交点，并根据交点在原直线参数方程中的参数值求出Z值(即深度)。若无交点

10、，转5。 5) 以上所求得的各交点将线段的投影分成若干段，求出第一段中点。 (6) 若第一段中点在平面的投影内，则相应的段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值进行判断。 (7) 结束。视点与线段同侧 包围盒不交 分段交替取值 分析: (1)每条线段上所有点具有相同的隐藏性。 (2)可以从线段中点向视点引射线，仅当此射线也多边形相交时，线段才被多边形隐藏。 (3)依次把多边形的边进行对比便得到所有隐藏线。5.2 5.2 曲面隐藏线消除曲面隐藏线消除 （1）曲面由方程 表示，建立M个象素，则建立M个内存单元yu(j)称之为上浮水平线数组，在这些单元中先放上初值，初值应取成小于min

11、(f(x,z) 。 ),(zxfy 一般用xxi和zzi两簇曲线表示,视点在Z轴方向. 设， ,i1，2n，平面zzn是最靠近视点，于是平面Zzn上曲线都是可见的。而对于zzi平面上的曲线yf(x，zi)，在区间xa，b上只有两种情况是可见的。 ihzzi0(1) f(x，zi)max f(x，zj) xa，b (ij)(2) f(x，zi)min f(x，zj) xa，b (ij)其余线段上应当消隐，。改进的曲面隐藏线消除改进的曲面隐藏线消除 上述方法对下图的曲面是不适用的，图中的c点附近的虚线部分应是可见的，但按上述算法却成了不可见了。改进的曲面隐藏线消除技术改进的曲面隐藏线消除技术 首先

12、，另外建立首先，另外建立M M个单元个单元 ， 。并计算。并计算 若若 则则 为可见，并如下修改为可见，并如下修改 或或 的的 值，可以表示为：值，可以表示为：),(ijjizxfy )( jyl)()(jyyjyyljiuji或),(ijijzyx)( jyu)( jyljilljijiuujiyjyjyyifyjyjyyif)( then )( )( then )( )( jyu5.3 5.3 消除隐藏面消除隐藏面 问题：为了让曲面在图形显示器上显示，需要把对应的曲面某点在屏幕的位置决定出来，即把曲面点变换成图像中的点，这过程就是光栅化过程，于是有些曲面或曲面一部分会被遮挡住，因此需要解决

13、消除隐藏面的问题。5.3.1 5.3.1 区域子分算法区域子分算法 算法思想：采用分而治之的策略，将整个屏幕看作为窗口，采用一个递归的四等分过程，每一次把矩形的窗口等分成四个相等的小矩形，分成的矩形也称为窗口。每一次子分，均要把要显示的多边形和窗口的关系作一判断。这种关系可有以下四种，如图5-9所示。 (a)分离 （b）内含 (c)相交 (d)包围 图5-9 多边形与窗口的关系 在窗口和每个多边形的关系确定以后，分下列三种情况。 所有多边形都和窗口分离，这时只要把窗口内所有的象素填上背景颜色。 只有一个多边形和窗口相交，或这个多边形包含在窗口内。这时先对窗口内每一象素填上背景颜色，再对窗口内多

14、边形部分用扫描线算法填色。 只有一个多边形和窗口相交，这个多边形把窗口整个包围在内，或虽有几个多边形和窗口相交，但离观察者最近的一个多边形包围了整个窗口，这时把整个窗口填上离观察者最近的那个多边形的颜色。 对上述三种情况不成立的窗口再一分为四，分得的窗口重复上述的处理。 当窗口的边长和一个象素的宽度基本相等，则取最靠近观察者的多边形的颜色，或这个窗口相交的多边形颜色的平均值。5.3.2 5.3.2 画家算法画家算法 画家算法源于油画的作画过程。根据景物的深度，先往画布（背景色）上 涂远景的颜色，然后再涂上近景的颜色。这样由远及近，后涂的颜色遮盖掉先涂的颜色，最终得到的结果就相当于消除了隐藏面。

15、 画家算法的思想：把景物中各个面按其离视点的距离进行排序建成深度优先级表。然后由远至近取出表中的多边形投影到屏幕上，近的后投的,覆盖了远的先投的，结果相当于消除了隐藏面。算法特点：画家算法的优点是简单，容易实现，可以作为实现更复杂算法的基础。它的缺点是只能处理互不相交的面，而且，深度优先级表中面的顺序可能出错。画家算法的关键技术：对多边形进行深度排序画家算法的关键技术：对多边形进行深度排序 设每个多边形有一些顶点，这些顶点各有一个Z坐标，取其中Z坐标最小的记为Zmin，取其中Z坐标最大的记为Zmax，于是每一个多边形都有自己的Zmax和Zmin。 按Zmin的大小把多边形初步排序。假设Zmin

16、最小的多边形为P，它暂时成为优先级最低的一个多边形。对其他任意一个多边形Q，研究P与Q的关系：对场景中的物体按深度排序对场景中的物体按深度排序深度重叠测试.1.若Zmax(P )Zmin(Q )而又有Zmin(P )Zmin(Q )，则需要作进一步检查。投影重叠判断2.P和Q在oxy平面上投影的包围盒在x方向上不相交3.P和Q在oxy平面上投影的包围盒在y方向上不相交4.P在Q之后。P的各顶点均在Q的远离视点的一侧5.Q在P之前。Q的各顶点均在P的靠近视点的一侧 说明： （1）上面五项中有一项成立，则P就不遮挡Q。 （2）如果上述五项都不成立，则说明Q有部分被P遮挡了。于是要对P，Q两多边形在

17、xoy平面的投影进行求交运算，在交点处进行深度比较，判断出前后顺序便可。 （3）若遇到多边形相交或循环重叠（如图5-11（f）情况，还需要在相交处分割多边形，再进行判断。多边形的画家算法的实现：1）对每个多边形顶点求Zmin。以Zmin为排序关键码，建立相应的深度排序表。表中第一个多边形是最小的Zmin，记这多边形为P，同时，设视点位于Z轴方向的无穷远处，于是根据坐标系规定，P是离视点最远的多边形。2）取第二个多边形为Q。3）检查Q与P的关系。如果Zmax(P)Zmin(Q)，则P不遮挡Q，将P写入帧缓存。如果满足上述五个条件之一，则P不遮挡Q，于是P写入帧缓存。5.3.3 Z5.3.3 Z缓

18、冲算法缓冲算法Z缓冲算法又称为深度缓冲算法，是一种简单而且有效的隐藏面消除算法。 Z缓冲算法需要两张表来存放相应的数据帧缓存:来存放每个象素的颜色值初值取成z的极小值深度缓存:来存放每个象素的深度值。初值可放对应背景颜色的值。屏幕帧缓冲器Z缓冲器每个单元存放对应象素的颜色值每个单元存放对应象素的深度值ScreenyxYzZXdepth(x,y)算法过程1. Z缓冲器的值与空间一点的z值进行比较，若Z缓冲器的值小，则不变，即Z缓冲器的值不变，帧缓存的值也不变2.若Z缓冲器的值大，则Z缓冲器的值用此z值表示，同时帧缓存的对应值用空间点对应的多边形颜色填。3.对显示对象的每个面上的每个点都做了上述处

19、理后，便可得到消除了隐藏面的图。Z-Buffer算法（） 帧缓存全置为背景色深度缓存全置为最大Z值for(每一个多边形) 扫描转换该多边形 for(该多边形所覆盖的每个象素(x,y) ) 计算该多边形在该象素的深度值Z(x,y);if(Z(x,y)小于Z缓存在(x,y)的值) 把Z(x,y)存入Z缓存中(x,y)处 把多边形在(x,y)处的颜色值存入帧 缓存的(x,y)处 算法优点: Z-Buffer算法在象素级上以近物取代远物。形体在屏幕上的出现顺序是无关紧要的。这种取代方法实现起来远比总体排序灵活简单，有利于硬件实现。缺点：占用空间大，没有利用图形的相关性与连续性。改进算法：只用一个深度缓

20、存变量zb Z-Buffer算法需要开一个与图象大小相等的缓存数组ZB，实际上，可以改进算法，只用一个深度缓存变量zb。z-Buffer()帧缓存全置为背景色for(屏幕上的每个象素(i,j) 深度缓存变量zb置最小值MinValue for(多面体上的每个多边形Pk) if(象素点(i,j)在pk的投影多边形之内) 计算Pk在(i,j)处的深度值depth;if(depth小于zb)zb = depth;indexp = k;If(zb != MinValue) 计算多边形Pindexp在交点 (I,j) 处的光照颜色并显示关键问题：（1）判断象素点(i,j)是否在pk的投影多边形之内（2）

21、计算多边形Pk在点（i，j）处的深度。设多边形Pk的平面方程为： （2）深度计算方法：0dczbyaxcdbjaidepth（1）点与多边形的包含性检测射线法由被测点P处向 y = - 方向作射线交点个数是奇数，则被测点在多边形内部否则，偶数，在多边形外部。PPP1P2P3P1P2(1)在处理当前扫描线时，开一个一维数组作为当前扫描线的Z-buffer。首先找出与当前扫描线相关的多边形，以及每个多边形中相关的边对。(2)对每一个边对之间的小区间上的各象素，计算深度，并与Z-buffer中的值比较，找出各象素处可见平面。(3)计算颜色，写帧缓存。采用增量算法计算深度。5.3.4 扫描线Z缓冲算法

22、数据结构(1)多边形Y表：将所有多边形存在多边形Y表中。 (2)根据多边形顶点中最小的y坐标，插入多边形Y表中的相应位置。(3)多边形Y表中只保存多边形的序号和其顶点的最大y坐标。根据序号可以从定义多边形的数据结构中取多边形信息0 1 2 3 45 6 71234567xy1234560IP2 Ymax2IP1 Ymax1P1P2e0e1e2e3e4e5待消隐对象 多边形y表活化多边形表APT:与当前扫描线相交的多边形。APT是一个动态的链表边Y表ET:活化多边形表中的每一个多边形都有一个边表ET 多边形P1的边表ETIP2 Ymax2IP1 Ymax1IP2 Ymax2APTAPTy=2y=

23、41234560Ymax, x,x,zYmax, x,x,zYmax, x,x,ze0e1e2活化边对表AET 在一条扫描线上，同一多边形的相邻两条边构成一个边对边对。活化边表AET中存放当前多边形中与当前扫描线相交的各边对的信息。xl xl ylmax xr xr yrmax zl IP za zb AET(y=6)0 1 2 3 45 6 71234567xye0e1e2e3e4AET(y=2)e0e4e3e2e0e15.3.5 扫描线Z-buffer算法()建多边形y表；对每一个多边形根据顶点最小的y值，将多边形置入多边形y表。活化多边形表APT，活化边表AET初始化为空。For(每条扫

24、描线i，i从小到大)1. 帧缓存CB置为背景色。2. 深度缓存ZB (一维数组) 置为无穷大。3. 将对应扫描线i的，多边形y表中的多边形加入到活化多边形表APT中。4. 对新加入的多边形，生成其相应的边Y表。5. 对APT中每一个多边形，若其边Y表中对应扫描线I增加了新的边， 将新的边配对，加到活化边对表AET中。6. 对AET中的每一对边：6.1 对xl x xr 的每一个象素，按增量公式z = z - za计算各点深度depth。6.2 与ZB中的量比较，depth ZB(I), 则令ZB(I) =depth，并计算颜色值， 写帧缓存。 7. 删除APT中，多边形顶点最大y坐标为I的多边形，并删除相应的边。8. 对AET中的每一个边对，作如下处理：8.1 删除ylmax或ylmax 已等于I的边。若一边对中只删除了其中一边， 需对该多边形的边重新配对。 8.2 用增量公式计算新的xl 、xl 和zl 5.3.6 5.3.6 区间扫描线算法区间扫描线算法基本思想：它是把当前扫描线与各多边形在投影平面的投影的交点进行排序后，使扫描线分为若干子区间。只要在区间任一点处找出在该处z值