第十一讲 面消隐
？基本概念
？提高消隐算法效率的常见方法
？画家算法
？ Z缓冲器算法
？扫描线 Z缓冲器算法
？区域子分算法
？光线投射算法
基本概念
产生真实感的方法之一：
反映三维场景中的相互遮挡关系
面消隐与线消隐
表面模型与线框模型
物体表面：平面与曲面
面消隐对象,由平面多边形构成的多面体
基本概念
消隐算法的分类
1）类：以窗口内的每个像素为处理单元；
for (窗口内的每一个像素 )
{ 确定距视点最近的物体，以该物体表面的颜色来显示像
素 }
2）类：以场景中的物体为处理单元；
for (场景中的每一个物体 )
{ 将其与场景中的其它物体比较，确定其表面的可见部分；
显示该物体表面的可见部分；
}
基本概念
算法复杂度
假设场景中有 k个物体，平均每个物体表
面由 h个多边形构成，显示区域中有 m x n
个像素，则：
第一种算法的复杂度为,O(mnkh)
第二种算法的复杂度为,O((kh)*(kh))
提高消隐算法效率的常见方法
利用连贯性
将透视投影转换成平行投影
包围盒技术
背面剔除
空间分割技术
物体分层表示
提高消隐算法效率的常见方法
1
利用连贯性
物体连贯性
面的连贯性
区域连贯性
扫描线的连贯性
深度连贯性
提高消隐算法效率的常见方法
2
将透视投影转换成平行投影
消隐与透视关系密切,体现有：
1）消隐必须在投影之前完成；
2）物体之间的遮挡关系与投影中心（视点）的选
取有关；
3）物体之间的遮挡关系与投影方式有关
提高消隐算法效率的常见方法
3
图 12.3 加入面消隐步骤的三维图形显示
流程图 p285 (参见图 8.30 p162）
图 12.4 先将透视投影转换成平行投影，南
后再消隐 p285 (参见图 8.33 p167）。
（避免除法，提高了效率）
提高消隐算法效率的常见方法
4
包围盒技术
定义,一个形体的包围盒指的是包围它的简单形体。
比如,…
该技术常用于,避免盲目的求交测试；
各种物体间的比较等。
一个好的包围盒要具有两个条件：
包围和充分紧密包围着形体；
对其的测试比较简单。
例,使用矩形包围合及长方体包围合来提高算法效
率 …
提高消隐算法效率的常见方法
5
背面剔除
外法向
外法向与投影方向（观察方向）的夹角
前向面与后向面（背面）
剔除依据,物体表面是封闭的，背面总是
被前向面所遮挡，从而始终是不可见的。
提高消隐算法效率的常见方法
6
空间分割技术
依据,场景中的物体，它们的投影在投影平面上
是否有重叠部分？（是否存在相互遮挡的可能？）对
于根本不存在相互遮挡关系的物体，应避免这种不必
要的测试。
方法,将投影平面上的窗口分成若干小区域；为
每个小区域建立相关物体表，表中物体的投影于该区
域有相交部分；则在小区域中判断那个物体可见时，
只要对该区域的相关物体表中的物体进行比较即可 。
提高消隐算法效率的常见方法
6
复杂度比较：
不妨假定每个小区域的相关物体表中平均有 h个物
体，场景中有 k个物体，由于物体在场景中的分布是分
散的，显然 h远小于 k。根据第二种消隐方法所述，其
算法复杂度为 O(h*h),远小于 O(k*k)。
提高消隐算法效率的常见方法
7
物体分层表示
表示形式,模型变换中的树形表示方式
原理,减少场景中物体的个数，从而降低算法复杂度。
方法,将父节点所代表的物体看成子节点所代表物体
的包围盒，当两个父节点之间不存在遮挡关系时，就
没有必要对两者的子节点做进一步测试。
父节点之间的遮挡关系可以用它们之间的包围盒
进行预测试。
画家算法
由来, 画家的作画顺序暗示出所画物体之间的
相互遮挡关系
算法基本思路：
1）先将场景中的物体按其距观察点的远近进
行排序，结果放在一张线性表中；（ 线性表构造：
距观察点远的称优先级低，放在表头；距观察点 近的称优先级高，
放在表尾。该表称为 深度优先级表 ）
2）然后按照从表头到表尾的顺序逐个绘制物
体。
画家算法
关键,如何对场景中的物体按深度（远
近）排序，建立深度优先级表？
一种针对多边形的排序算法如下：
假定在规范化投影坐标系 uvn中,投影方向是 n
轴的负向,因而 n坐标大距观察者近。记 nmin(P)
nmax(P)分别为多边形 P的各个顶点 n坐标的最小
值和最大值，算法步骤如下：
画家算法
Step 1:将场景中所有多边形存入一个线性表（链表或数组），记为 L;
Step 2,如果 L中仅有一个多边形，算法结束；否则根据每个多边形的 nmin对它们预
排序。不妨假定多边形 P落在表首，即 nmin(P)为最小。再记 Q为 L – {P}(表中其余
多边形）中任意一个；
Step 3,判别 P,Q之间的关系，有如下二种：
step 3.1,对有的 Q，有 nmax(P)< nmin (Q),则多边形的确距观察点最远，
它不可能遮挡别的多边形。令 L = L – {P},返回 step 2;
step 3.2,存在某一个多边形 Q，使 nmax(P) > nmin (Q),需进一步判别：
step 3.2.1 若 P,Q投影 P’,Q’的包围盒不相交，则 P,Q在表中的次序不重
要，令 L = L – {P},返回 step 2;否则进行下一步。
step 3.2.2 若 P的所有顶点位于 Q所在平面的不可见的一侧，则 P,Q关系
正确，令 L = L – {P},返回 step 2;否则进行下一步。
step 3.2.3 若 Q 的所有顶点位于 P所在平面的可见的一侧，则 P,Q关系正
确，令 L = L – {P},返回 step 2;否则进行下一步。
step 3.2.4 对 P,Q投影 P’,Q’求交，若 P’,Q’不相交，则 P,Q在表中的次序
不重要，令 L = L – {P},返回 step 2;否则在它们所相交的区域中任取一点，计算
P,Q在该点的深度值，如果 P的深度小，则 P,Q关系正确，令 L = L – {P},返回
step 2;否则交换 P,Q,返回 step 3.
画家算法
本算法不能处理的情况：
多边形循环遮挡
多边形相互穿透
解决办法：分割成两个
Z缓冲器算法
由来：
帧缓冲器 – 保 存各像素颜色值
z缓冲器 --保 存各像素处物体深度值
z缓冲器中的单元与帧缓冲器中的单元一一对应
思路,先将 z缓冲器中个单元的初始值置为 -1(规范视见体的最
小 n值）。当要改变某个像素的颜色值时，首先检查当前多边形
的深度值是否大于该像素原来的深度值（保存在该像素所对应的
Z缓冲器的单元中），如果大于，说明当前多边形更靠近观察点，
用它的颜色替换像素原来的颜色；否则说明在当前像素处，当前
多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色
值不改变。
Z缓冲器算法
算法描述,
for ( v= 0;v<vmax;v++)
for (u= 0; u<umax; u++)
{ 将帧缓冲器的第 (u,v)单元置为背景色；
将 Z缓冲器的第 (u,v)单元置为 -1(可见的最小深度值 ) }
for (每个多边形）
for （ 多边形在投影平面上的投影区域内的每个像素 (u,v) ）
{ 计算多边形在当前像素 (u,v)处的深度值 d；
if (d > Z缓冲器的第 (u,v)单元的值）
{ 置帧缓冲器的第 (u,v)单元值为当前多边形颜色；
置 Z缓冲器的第 (u,v)单元值为 d; }
}
Z缓冲器算法
优点：简单稳定，利于硬件实现
缺点,1）需要一个额外的 Z缓冲器
2）在每个多边形占据的每个像素
处都要计算深度值，计算量大
扫描线 Z缓冲器算法
由来,Z缓冲器算法中所需要的 Z缓冲器容量较大，
为克服这个缺点可以将整个绘图区域分割成若干个小
区域，然后一个区域一个区域地显示，这样 Z缓冲器的
单元数只要等于一个区域内像素的个数就可以了。如
果将小区域取成屏幕上的扫描线，就得到 扫描线 Z
缓冲器算法。
扫描线 Z缓冲器算法
算法描述
for ( v= 0;v<vmax;v++)
{ for (u= 0; u<umax; u++) //对绘图窗的每一条扫描线初始化
{ 将帧缓冲器的第 (u,v)单元置为背景色；
将 Z缓冲器的第 u单元置为 -1（可见的最小深度值 ） }
for (每个多边形）
{ 求出多边形在投影平面上的投影与当前扫描线的相交区间
for （该区间内的每个像素 (u,v) ）
{ 计算多边形在该像素处的深度值 d；
if (d > Z缓冲器的第 u单元的值）
{ 置帧缓冲器的第 (u,v)单元值为当前多边形颜色；
置 Z缓冲器的第 u单元值为 d; }
}
}
}
区域子分算法
由来,Z缓冲器算法与扫描线 Z缓冲器算法中
都是将像素孤立来考虑，未利用相邻像素之间
存在的属性的连贯性，即区域的连贯性，所以
算法效率不高。实际上，可见多边形至少覆盖
了绘图窗内的一块区域。如果能将这类区域找
出来，则避免了在每个像素处计算深度值，消
隐问题也就解决了。
区域子分算法
算法基本思路, 首先将场景中的多边形投影
到绘图窗口内（ 假设它为边长为 k的正方形 ），判
断窗口是否 足够简单,若是则算法结束；否则
将窗口进一步分为四块（左上，右上，左下，
右下）。对此四个小窗口重复上述过程，直到
窗口仅为一个像素大小。此时可能有多个多边
形覆盖了该像素，计算它们的深度值，以最近
的颜色显示该像素即可。
区域子分算法
何谓窗口足够简单？
存在下列情况之一即可称为窗口足够简单：
1）窗口为空，即多边形与窗口的关系是 分离 的；
2）窗口内仅含一个多边形，即有一个多边形与窗口的
关系是 包含或相交 。此时先对多边形投影进行裁剪，
再对裁剪结果进行填充；
3）有一个多边形的投影 包围 了窗口，并且它是最靠近
观察点的，以该多边形颜色填充窗口。
区域子分算法
如何判别多边形与窗口的 分离与包围 关系？
编码方法,1）区域编码
2）多边形顶点编码
3）多边形边的编码
4）多边形的编码
光线投射算法
算法思路：将通过绘图窗口内每一个像
素的投影线与场景中的所有多边形求交。
如果有交点，用深度值最大的交点（最
近的）所属的多边形的颜色显示相应的
像素；如果没有交点，说明没有多边形
的投影覆盖此像素，用背景色显示即可。
光线投射算法
算法描述：
for ( v= 0;v<vmax;v++)
for (u= 0; u<umax; u++)
{ 形成通过像素 (u,v)的投影线；
for (场景中每一个多边形）
将投影线与多边形求交；
if (有交点）
以最近交点所属多边形的颜色显示像素 (u,v)
else
以背景色显示像素 (u,v)；
}
思考：
区域子分算法中多边形投影与窗口的关系中
包含与相交 关系是如何判别的？编码方法中为何
对△ i = +/- 4的情况进行了特殊处理？
？基本概念
？提高消隐算法效率的常见方法
？画家算法
？ Z缓冲器算法
？扫描线 Z缓冲器算法
？区域子分算法
？光线投射算法
基本概念
产生真实感的方法之一：
反映三维场景中的相互遮挡关系
面消隐与线消隐
表面模型与线框模型
物体表面：平面与曲面
面消隐对象,由平面多边形构成的多面体
基本概念
消隐算法的分类
1）类：以窗口内的每个像素为处理单元；
for (窗口内的每一个像素 )
{ 确定距视点最近的物体，以该物体表面的颜色来显示像
素 }
2）类：以场景中的物体为处理单元；
for (场景中的每一个物体 )
{ 将其与场景中的其它物体比较，确定其表面的可见部分；
显示该物体表面的可见部分；
}
基本概念
算法复杂度
假设场景中有 k个物体，平均每个物体表
面由 h个多边形构成，显示区域中有 m x n
个像素，则：
第一种算法的复杂度为,O(mnkh)
第二种算法的复杂度为,O((kh)*(kh))
提高消隐算法效率的常见方法
利用连贯性
将透视投影转换成平行投影
包围盒技术
背面剔除
空间分割技术
物体分层表示
提高消隐算法效率的常见方法
1
利用连贯性
物体连贯性
面的连贯性
区域连贯性
扫描线的连贯性
深度连贯性
提高消隐算法效率的常见方法
2
将透视投影转换成平行投影
消隐与透视关系密切,体现有：
1）消隐必须在投影之前完成；
2）物体之间的遮挡关系与投影中心（视点）的选
取有关；
3）物体之间的遮挡关系与投影方式有关
提高消隐算法效率的常见方法
3
图 12.3 加入面消隐步骤的三维图形显示
流程图 p285 (参见图 8.30 p162）
图 12.4 先将透视投影转换成平行投影，南
后再消隐 p285 (参见图 8.33 p167）。
（避免除法，提高了效率）
提高消隐算法效率的常见方法
4
包围盒技术
定义,一个形体的包围盒指的是包围它的简单形体。
比如,…
该技术常用于,避免盲目的求交测试；
各种物体间的比较等。
一个好的包围盒要具有两个条件：
包围和充分紧密包围着形体；
对其的测试比较简单。
例,使用矩形包围合及长方体包围合来提高算法效
率 …
提高消隐算法效率的常见方法
5
背面剔除
外法向
外法向与投影方向（观察方向）的夹角
前向面与后向面（背面）
剔除依据,物体表面是封闭的，背面总是
被前向面所遮挡，从而始终是不可见的。
提高消隐算法效率的常见方法
6
空间分割技术
依据,场景中的物体，它们的投影在投影平面上
是否有重叠部分？（是否存在相互遮挡的可能？）对
于根本不存在相互遮挡关系的物体，应避免这种不必
要的测试。
方法,将投影平面上的窗口分成若干小区域；为
每个小区域建立相关物体表，表中物体的投影于该区
域有相交部分；则在小区域中判断那个物体可见时，
只要对该区域的相关物体表中的物体进行比较即可 。
提高消隐算法效率的常见方法
6
复杂度比较：
不妨假定每个小区域的相关物体表中平均有 h个物
体，场景中有 k个物体，由于物体在场景中的分布是分
散的，显然 h远小于 k。根据第二种消隐方法所述，其
算法复杂度为 O(h*h),远小于 O(k*k)。
提高消隐算法效率的常见方法
7
物体分层表示
表示形式,模型变换中的树形表示方式
原理,减少场景中物体的个数，从而降低算法复杂度。
方法,将父节点所代表的物体看成子节点所代表物体
的包围盒，当两个父节点之间不存在遮挡关系时，就
没有必要对两者的子节点做进一步测试。
父节点之间的遮挡关系可以用它们之间的包围盒
进行预测试。
画家算法
由来, 画家的作画顺序暗示出所画物体之间的
相互遮挡关系
算法基本思路：
1）先将场景中的物体按其距观察点的远近进
行排序，结果放在一张线性表中；（ 线性表构造：
距观察点远的称优先级低，放在表头；距观察点 近的称优先级高，
放在表尾。该表称为 深度优先级表 ）
2）然后按照从表头到表尾的顺序逐个绘制物
体。
画家算法
关键,如何对场景中的物体按深度（远
近）排序，建立深度优先级表？
一种针对多边形的排序算法如下：
假定在规范化投影坐标系 uvn中,投影方向是 n
轴的负向,因而 n坐标大距观察者近。记 nmin(P)
nmax(P)分别为多边形 P的各个顶点 n坐标的最小
值和最大值，算法步骤如下：
画家算法
Step 1:将场景中所有多边形存入一个线性表（链表或数组），记为 L;
Step 2,如果 L中仅有一个多边形，算法结束；否则根据每个多边形的 nmin对它们预
排序。不妨假定多边形 P落在表首，即 nmin(P)为最小。再记 Q为 L – {P}(表中其余
多边形）中任意一个；
Step 3,判别 P,Q之间的关系，有如下二种：
step 3.1,对有的 Q，有 nmax(P)< nmin (Q),则多边形的确距观察点最远，
它不可能遮挡别的多边形。令 L = L – {P},返回 step 2;
step 3.2,存在某一个多边形 Q，使 nmax(P) > nmin (Q),需进一步判别：
step 3.2.1 若 P,Q投影 P’,Q’的包围盒不相交，则 P,Q在表中的次序不重
要，令 L = L – {P},返回 step 2;否则进行下一步。
step 3.2.2 若 P的所有顶点位于 Q所在平面的不可见的一侧，则 P,Q关系
正确，令 L = L – {P},返回 step 2;否则进行下一步。
step 3.2.3 若 Q 的所有顶点位于 P所在平面的可见的一侧，则 P,Q关系正
确，令 L = L – {P},返回 step 2;否则进行下一步。
step 3.2.4 对 P,Q投影 P’,Q’求交，若 P’,Q’不相交，则 P,Q在表中的次序
不重要，令 L = L – {P},返回 step 2;否则在它们所相交的区域中任取一点，计算
P,Q在该点的深度值，如果 P的深度小，则 P,Q关系正确，令 L = L – {P},返回
step 2;否则交换 P,Q,返回 step 3.
画家算法
本算法不能处理的情况：
多边形循环遮挡
多边形相互穿透
解决办法：分割成两个
Z缓冲器算法
由来：
帧缓冲器 – 保 存各像素颜色值
z缓冲器 --保 存各像素处物体深度值
z缓冲器中的单元与帧缓冲器中的单元一一对应
思路,先将 z缓冲器中个单元的初始值置为 -1(规范视见体的最
小 n值）。当要改变某个像素的颜色值时，首先检查当前多边形
的深度值是否大于该像素原来的深度值（保存在该像素所对应的
Z缓冲器的单元中），如果大于，说明当前多边形更靠近观察点，
用它的颜色替换像素原来的颜色；否则说明在当前像素处，当前
多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色
值不改变。
Z缓冲器算法
算法描述,
for ( v= 0;v<vmax;v++)
for (u= 0; u<umax; u++)
{ 将帧缓冲器的第 (u,v)单元置为背景色；
将 Z缓冲器的第 (u,v)单元置为 -1(可见的最小深度值 ) }
for (每个多边形）
for （ 多边形在投影平面上的投影区域内的每个像素 (u,v) ）
{ 计算多边形在当前像素 (u,v)处的深度值 d；
if (d > Z缓冲器的第 (u,v)单元的值）
{ 置帧缓冲器的第 (u,v)单元值为当前多边形颜色；
置 Z缓冲器的第 (u,v)单元值为 d; }
}
Z缓冲器算法
优点：简单稳定，利于硬件实现
缺点,1）需要一个额外的 Z缓冲器
2）在每个多边形占据的每个像素
处都要计算深度值，计算量大
扫描线 Z缓冲器算法
由来,Z缓冲器算法中所需要的 Z缓冲器容量较大，
为克服这个缺点可以将整个绘图区域分割成若干个小
区域，然后一个区域一个区域地显示，这样 Z缓冲器的
单元数只要等于一个区域内像素的个数就可以了。如
果将小区域取成屏幕上的扫描线，就得到 扫描线 Z
缓冲器算法。
扫描线 Z缓冲器算法
算法描述
for ( v= 0;v<vmax;v++)
{ for (u= 0; u<umax; u++) //对绘图窗的每一条扫描线初始化
{ 将帧缓冲器的第 (u,v)单元置为背景色；
将 Z缓冲器的第 u单元置为 -1（可见的最小深度值 ） }
for (每个多边形）
{ 求出多边形在投影平面上的投影与当前扫描线的相交区间
for （该区间内的每个像素 (u,v) ）
{ 计算多边形在该像素处的深度值 d；
if (d > Z缓冲器的第 u单元的值）
{ 置帧缓冲器的第 (u,v)单元值为当前多边形颜色；
置 Z缓冲器的第 u单元值为 d; }
}
}
}
区域子分算法
由来,Z缓冲器算法与扫描线 Z缓冲器算法中
都是将像素孤立来考虑，未利用相邻像素之间
存在的属性的连贯性，即区域的连贯性，所以
算法效率不高。实际上，可见多边形至少覆盖
了绘图窗内的一块区域。如果能将这类区域找
出来，则避免了在每个像素处计算深度值，消
隐问题也就解决了。
区域子分算法
算法基本思路, 首先将场景中的多边形投影
到绘图窗口内（ 假设它为边长为 k的正方形 ），判
断窗口是否 足够简单,若是则算法结束；否则
将窗口进一步分为四块（左上，右上，左下，
右下）。对此四个小窗口重复上述过程，直到
窗口仅为一个像素大小。此时可能有多个多边
形覆盖了该像素，计算它们的深度值，以最近
的颜色显示该像素即可。
区域子分算法
何谓窗口足够简单？
存在下列情况之一即可称为窗口足够简单：
1）窗口为空，即多边形与窗口的关系是 分离 的；
2）窗口内仅含一个多边形，即有一个多边形与窗口的
关系是 包含或相交 。此时先对多边形投影进行裁剪，
再对裁剪结果进行填充；
3）有一个多边形的投影 包围 了窗口，并且它是最靠近
观察点的，以该多边形颜色填充窗口。
区域子分算法
如何判别多边形与窗口的 分离与包围 关系？
编码方法,1）区域编码
2）多边形顶点编码
3）多边形边的编码
4）多边形的编码
光线投射算法
算法思路：将通过绘图窗口内每一个像
素的投影线与场景中的所有多边形求交。
如果有交点，用深度值最大的交点（最
近的）所属的多边形的颜色显示相应的
像素；如果没有交点，说明没有多边形
的投影覆盖此像素，用背景色显示即可。
光线投射算法
算法描述：
for ( v= 0;v<vmax;v++)
for (u= 0; u<umax; u++)
{ 形成通过像素 (u,v)的投影线；
for (场景中每一个多边形）
将投影线与多边形求交；
if (有交点）
以最近交点所属多边形的颜色显示像素 (u,v)
else
以背景色显示像素 (u,v)；
}
思考：
区域子分算法中多边形投影与窗口的关系中
包含与相交 关系是如何判别的？编码方法中为何
对△ i = +/- 4的情况进行了特殊处理？
