二、 消隐基本技术
为了提高消隐算法的效率，各种消隐算法常 采用一些有效的消隐基本算法。
利用连贯性 将透视投影转换成平行投影 包围盒技术 背面剔除 空间分割技术 物体分层表示
利用连贯性
连贯性是指从一个事物到另一个事物，其属性值(如颜色值、 空间位置)通常是平缓过渡的性质。
物体连贯性 面的连贯性 区域连贯性
包围盒技术
一个形体的包围盒指的是包围它的简单形体。 比如，2D的矩形，3D的立方块、长方体、球等。
目的： 避免盲目的求交测试； 各物体间的比较等。
一个好的包围盒要具有两个条件： 包围和充分紧密包围着形体； 对其的测试比较简单。
例：矩形包围盒及长方体包围盒提高算 法效率
• 包围盒不相交，线段和多边形也不相交，线段完全可见，无需就线段和多边形 的遮挡关系进行进一步判断。可推广到面与面的遮挡快速判断。
特点是：算法可以达到相当高的精度。
for (场景中的每一个物体) { 将其与场景中的其它物体比较，确定其表面的可见部分；
显示该物体表面的可见部分； }
第二种是像空间算法。 它以构成图形的每一个像素为处理单元的，确定场景中哪些表面的像• 特点是：算法精度低，只能达到屏幕精度为止，但速度往 往更高。
• 按消隐空间分类
物体空间消隐算法 图像空间消隐算法
线消隐（Hidden-line） 消隐对象是物体上不可见的线，一般用于线框图。当用笔式绘图仪或
其它画线设备绘制图形时，主要使用这种算法。 面消隐（Hidden-surface）
消隐对象是物体上不可见的面，一般用于填色图。当用光栅扫描显示 器绘制图形时，主要使用这种算法。
消隐算法
主要内容:
一、概述 二、消隐的基本技术 三、凸多面体消除隐藏线 四、消除隐藏面
一、概述
用计算机生成三维形体的真实图形，是计算机图形学研究 的重要内容之一。在使用显示设备描绘三维图形时，必须把三 维信息作某种投影变换，在二维显示表面上绘制出来。
由于投影变换失去了深度信息，往往导致图形的二义性：
要消除二义性，必须在绘制时消隐实际不可见得线和面， 即消隐。经过消隐的投影图称为物体的真实图形。
• 消隐不仅与消隐对象有关，还与观察者的位置有关。如图所示， 由于视点的位置不同，物体的可见部分也不同：
D
C
E2
A
B
E1
消隐与观察者的位置关系
• 按消隐的对象分类
线消隐（Hidden-line） 面消隐（Hidden-surface）
• 例如：两个空间多边形A、B在投影平面上的投影分别为A’，B’ ，因为A’ 、B’的 矩形包围盒不相交，则A’、B’不相交，无须进行遮挡测试。右图：包围盒相交， 投影也相交；包围盒相交，投影不相交。
A
B
A’
B’
背面剔除
剔除依据： 物体表面是封闭的，背面总是被前向面所遮挡，从 而始终是 不可见的。
早期图形显示器是用线条表示图形，消隐主要是消隐线问题。使用光栅显 示器后，物体可用连续变化的色调来描述，消隐算法的研究渐渐转向消隐面 的问题。
隐藏线（面）的消除的两种基本算法
第一种是物空间算法。 • 它以三维场景中的物体对像作为处理单元的，在所有的对像之间进行
比较，除去完全不可见的的物体和物体上不可见的部分。常用于线框 表示立体的线隐藏，也用于面隐藏。
9
象空间消隐算法： 这类算法对屏幕上的每个象素进行判断，以决定物体上哪个多边
形在该象素 点上是可见的。若屏幕上有m×n个象素点，每个物体表面 上有h个多边形，则该类消隐算法计算量正比于mnh。
则： k个物体的算法复杂度为： O(mnkh) 。
10
算法排序
各种消隐算法均采用一定形式的几何排序。通过排序，可搜查出位置 上靠近观察者的几何元素，确定几何元素之间在位置上的遮挡关系，解决 消隐计算的主要问题。各种算法都有各自的排序方法和排序次序。排序次 序影响算法的效率。
其算法是对每一个像素: 在和投影点到像素的连线相交的表面中找到离观察点最近的表面 用该表面上交点处的颜色填充该像素。
for (窗口内的每一个像素) { 确定距视点最近的物体，以该物体表 面的颜色来显示像素}
算法复杂度
假设场景中有k个物体，平均每个物体表面 由h个多边形构成，显示区域中有m x n个像素， 则：
• 一张面内的各种属性值一般是缓慢变化的，可采用增量的形式对其进行计算；
• 区域连贯性
• 一个区域一般指屏幕上一组相邻的象素，他们通常为同一个可见面所占据，可见性相 同；
• 扫描线的连贯性
• 在相邻两条扫描线上，可见面的分布情况相似；
• 深度连贯性
• 同一表面上的相邻部分深度是相近的，而占据屏幕上同一区域的不同表面的深度不同， 这样只需取其上一点计算出深度值，比较该深度值便能得出结果；
第一种算法的复杂度为： O((kh)×(kh)) 第二种算法的复杂度为：O(mnkh)
物空间消隐算法: 需对物体表面的h个多边形中的每个面与其余h-1个面进行比较，
精确地求出物体上每个棱边或每个面的遮挡关系。算法的计算量正 比于h2，即算法复杂度为：O((h)2) 。
则：k个物体的算法复杂度为：O((kh)2) 。
扫描线的连贯性
例如：
深度连贯性
棱边的连贯性是指：棱边的可见性在它与其他棱边相交时才发生变换；
面的连贯性是指：如果面的一部分是可见的，则一般情况下整个面都是可见的。
• 物体连贯性
• 若物体A与物体B是完全分离的，消隐时只需要比较两物体之间的遮挡关系即可，不需 要对它们的表面多边形逐一进行测试；
• 面的连贯性
外法向 外法向与投影方向（观察方向）的夹角判断：前向面与后向面
（背面）
视线向量V 法向向量N
法向向量N
<90°
可见
cos N V
<90°
可见
>90°
不可见
法向向量N
视线-法线夹角法
N 面的法向量
V 面上一点指向观察点的向量
= cos-1( )
N.V
|N||V|
0<= <

时2 可见
N
.
V
>0
2<= <=
时 不可见N . V <0
、空间分割技术
依据：场景中的物体，它们的投影在投影平面上 是否有相互遮挡的重叠部分？ 对于根本不存在相互遮挡关系的物体，应 避免这种不必要的测试。