计算机图形学—— 隐藏线和隐藏面的消除（消隐算法）

一、概述

由于投影变换失去了深度信息，往往导致图形的二义性。要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面（或可见线判定、可见面判定），或简称为消隐。经过消隐得到的投影图称为物体的真实感图形。

下面这个图就很好体现了这种二义性。

消隐后的效果图：

消隐算法的分类

所有隐藏面消隐算法必须确定:
在沿透视投影的投影中心或沿平行投影的投影方向看过去哪些边或面是可见的

两种基本算法

1、以构成图像的每一个像素为处理单元，对场景中的所有表面，确定相对于观察点是可见的表面，用该表面的颜色填充该像素.
适于面消隐。

算法步骤：

a.在和投影点到像素连线相交的表面中，找到离观察点最近的表面；
b.用该表面上交点处的颜色填充该像素；

2、以三维场景中的物体对象为处理单元，在所有对象之间进行比较，除去完全不可见的物体和物体上不可见的部分.适于面消隐也适于线消隐。

算法步骤：
a.判定场景中的所有可见表面；
b.用可见表面的颜色填充相应的像素以构成图形；

提醒注意

1.假定构成物体的面不能相互贯穿，也不能有循环遮挡的情况。
2.假定投影平面是oxy平面，投影方向为z轴的负方向。

如果构成物体的面不满足该假定，可以把它们剖分成互不贯穿和不循环遮挡的情况。
例如，用图b中的虚线便可把原来循环遮挡的三个平面，分割成不存在循环遮挡的四个面。

二、可见面判断的有效技术

1、边界盒

指能够包含该物体的一个几何形状(如矩形/圆/长方体等)，该形状有较简单的边界。

边界盒技术用于判断两条直线是否相交。

进一步简化判断

2、后向面消除(Back-face Removal)

思路：把显然不可见的面去掉，减少消隐过程中的直线求交数目

如何判断：根据定义寻找外（或内）法向，若外法向背离观察者，或内法向指向观察者，则该面为后向面。

注意：如果多边形是凸的，则可只取一个三角形计算有向面积sp。如果多边形不是凸的，只取一个三角形计算有向面积sp可能会出现错误，即F所在的面为前向面也可能出现sp≥0的情况,因此，需按上式计算多边形F的有向面积。如果sp ≥0，则F所在的面为后向面。

3、非垂直投影转化成垂直投影

物体之间的遮挡关系与投影中心和投影方向有着密切的关系,因此，对物体的可见性判定也和投影方式有密切的关系。

垂直投影的优点:进行投影时可以忽略z值,即：实物的(x,y)可直接做为投影后的二维平面上的坐标(x,y)

上述讨论说明，垂直投影比非垂直投影容易实现，并且计算量小。因此在进行消隐工作之前，首先应将非垂直投影转换成垂直投影，从而降低算法的复杂性，提高运算速度。

如何把透视投影变为垂直投影,其本质是把棱台变成长方体。

三、基于窗口的子分算法（Warnack算法）

是一种分而治之(Divide-Conquer)的算法。

1、关系判断

2、可见性判断

3、分隔结束条件

4、提高效率的有效的处理技术

5、算法描述

用多边形的边界对区域作划分，其目的是尽量减少对区域划分的次数－－利用裁剪算法

四、八叉树算法

为了生成真实感图形，关键问题之一就是对图像空间的每一个像素进行处理。从场景中所有的在该像素上有投影的表面中确定相对于观察点是可见表面。为了提高算法效率，自然是希望从可能在像素上有投影的面片中寻找可见表面。八叉树算法是快速寻找可见面的一种有效方法，是一种搜索算法。

基本思想：将能够包含整个场景的立方体，即八叉树的根结点，按照x，y，z三个方向中的剖面分割成八个子立方体，称为根结点的八个子结点。对每一个子立方体，如果它包含的表面片少于一个给定的值，则该子立方体为八叉树的终端结点，否则为非终端结点并将其进一步分割成八个子立方体；重复上述过程，直到每个小立方体所包含的表面片少于一个给定的值，分割即告终止。

那么对于上述图所示，视图平面法向量（1,1,1）那么此时它的一个排列是0,1,2,4,3,5,6,7，即最远的八分体是0，与八分体0共享一个面的三个相邻八分体是1,2和4,与最近八分体7的3个相邻八分体是3,5和6。

五、Z缓冲器算法

1、算法描述

z缓冲器算法是最简单的隐藏面消除算法之一。
基本思想：对屏幕上每一个像素点，过像素中心做一条投影线，找到此投影线与所有多边形交点中离观察者最近的点，此点的属性(颜色或灰度)值即为这一屏幕像素点的属性值。

需要两个缓冲器数组，即：z缓冲器数组和帧缓冲器数组，分别设为 Zdepth[ ][ ] 与 Frame[ ][ ]
z缓冲器是一组存贮单元，其单元个数和屏幕上像素的个数相同，也和帧缓冲器的单元个数相同，它们之间一一对应。
帧缓冲器每个单元存放对应像素的颜色值；z缓冲器每个单元存放对应像素的深度值;

2、算法实现

算法的复杂性正比于m*n*N，在屏幕大小即m*n一定的情况下,算法的计算量只和多边形个数N成正比

3、优缺点

z-Buffer算法没有利用图形的相关性和连续性，这是z-Buffer算法的严重缺陷，更为严重的是，该算法是像素级上的消隐算法。

六、扫描线z缓冲器算法

1、算法描述

将z缓冲器的单元数置为和一条扫描线上的像素数目相同。
从最上面的一条扫描线开始工作，向下对每一条扫描线作如下处理：

扫描线算法也属于图像空间消隐算法。该算法可以看作是多边形区域填充里介绍过的边相关扫描线填充算法的延伸。不同的是在消隐算法中处理的是多个面片，而多边形填充中是对单个多边形面进行填充。

2、数据结构

对每个多边形，检查它在oxy平面上的投影和当前扫描线是否相交？
若不相交，则不考虑该多边形。
如果相交，则扫描线和多边形边界的交点是成对地出现
对每对交点中间的像素计算多边形所在平面对应点的深度（即z值），并和z缓冲器中相应单元存放的深度值作比较。
若前者大于后者，则z缓冲器的相应单元内容要被求得的平面深度代替，帧缓冲器相应单元的内容也要换成该平面的属性。
对所有的多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐后的图形。
对帧缓冲器每一行的单元都填上相应内容后就得到了整个消隐后的图。

每处理一条扫描线，都要检查各多边形是否和该线相交，还要计算多边形所在平面上很多点的z值，需要花费很大的计算
为了提高算法效率，采用跟多边形扫描转换中的扫描线算法类似的数据结构和算法.

多边形Y表

实际上是一个指针数组 ,每个表的深度和显示屏幕行数相同.将所有多边形存在多边形Y表中,根据多边形顶点中Y坐标最大值,插入多边形Y表中的相应位置,多边形Y表中保存多边形的序号和其顶点的最大y坐标.

边Y表

要注意：Δx是下一条扫描线与边交点的x减去当前的扫描线与边交点的x。

多边形活化表

边对活化表

其实这里最难理解的就是Δyl和Δxr了，这里的意思就是当前扫描线所处的y值和与该扫描线相交边的最小y值的差值。

就比如说扫描线y=6,与第一个三角形有两个交点，左交点（4,6），右交点（7,6）那么Δyl=6-3 Δyr=6-3

3、重温算法目标

对每一条扫描线，检查对每个多边形的投影是否相交，如相交则交点成对出现，对每对交点中间的每个像素计算多边形所在平面对应点的深度（即z值），并和z缓冲器中相应单元存放的深度值作比较，若前者大于后者，则z缓冲器的相应单元内容要被求得的平面深度代替，帧缓冲器相应单元的内容也要换成该平面的属性。
对所有的多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐后的图形，对帧缓冲器每一行的单元都填上相应内容后也就得到了整个消隐后的图。

4、算法步骤

算法描述如下

七、优先级排序表算法

1、算法思想

优先级排序表算法按多边形离观察者的远近来建立一个多边形排序表，距观察者远的优先级低，放在表头；近的优先级高，放在表尾
从优先级低的多边形开始，依次把多边形的颜色填入帧缓冲存储器中
表中距观察者近的元素覆盖帧缓冲存储器中原有的内容
当优先级最高的多边形的图形送入帧缓冲器后，整幅图形就形成了
类似于油画家绘画过程，因此又称为油画家算法。