2013-3-1 华中理工大学计算机学院 陆枫
99-7
1
第 9章 消隐
提出问题
? 物体的消隐 或 隐藏线面的消除,在给定视点和视
线方向后, 决定场景中哪些物体的表面是可见的,
哪些是被遮挡不可见的 。 物体的消隐或隐藏线面
的消除 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
2
? 图象空间消隐算法 以屏幕象素为采样单位，确定投
影于每一象素的可见景物表面区域，并将其颜色作
为该象素的显示颜色。
? 景物空间消隐算法 直接在景物空间（观察坐标系）
中确定视点不可见的表面区域，并将它们表达成同
原表面一致的数据结构。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
3
? 图象空间消隐算法：有深度缓冲器算法, A缓冲器算法,
区间扫描线算法等 。
? 景物空间消隐算法,BSP算法, 多边形区域排序算法 。
? 介于二者之间：深度排序算法, 区域细分算法, 光线投
射算法等 。
? 两个基本原则,排序, 连贯性
? 选择 z轴的负向为观察方向
2013-3-1 华中理工大学计算机学院 陆枫
99-7
4
9.1 深度缓存器算法（ Z-buffer算法）
Z-buffer算法的原理,
例如,
图9 - 1 深度缓存器算法的原理( P 1 近,可见)
z
x
y
(x,y)
P 1
P 2
屏幕
0
R
2013-3-1 华中理工大学计算机学院 陆枫
99-7
5
两块缓冲区,
? Z缓存,保存屏幕坐标系上各象素点所对应的
深度值
? 帧缓存,保存各点的颜色 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
6
Z-buffer算法的步骤如下,
1,初始化：把 Z缓存中各 (x,y)单元置为 z的最小值, 而
帧缓存各 (x,y)单元置为背景色 。
2,在把物体表面相应的多边形扫描转换成帧缓存中的
信息时, 对于多边形内的每一采样点 (x,y)进行处理,
(1)计算采样点 (x,y)的深度 z(x,y)；
(2)如 z(x,y)大于 Z缓存中在 (x,y)处的值, 则把 z(x,y)存入 Z
缓存中的 (x,y)处, 再把多边形在 z(x,y)处的颜色值存入
帧缓存的 (x,y)地址中 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
7
问题,计算采样点 (x,y)的深度 z(x,y)。
假定多边形的平面方程为,Ax+By+Cz+D=0。
C
DByAxyxz ????),(
2013-3-1 华中理工大学计算机学院 陆枫
99-7
8
利用连贯性加速深度的计算,
图9 - 2 利用扫描线的连贯性加速深度的计算
0 x
y
x+1x
y
y-1
扫描线
多边形
2013-3-1 华中理工大学计算机学院 陆枫
99-7
9
? 扫描线上所有后继点的深度值,
? 当处理下一条扫描线 y=y-1时, 该扫描线上与多边形相
交的最左边 （ x最小 ） 交点的 x值可以利用上一条扫描线
上的最左边的 x值计算,
),()1(),1( CAyxzC DByxAyxz ????????
1m i n,m i n,1
k
xx yy ???
2013-3-1 华中理工大学计算机学院 陆枫
99-7
10
),(
)1()
1
(
)1(
)1,(
m i n,
m i n,
m i n,1
m i n,1
C
B
k
A
yxz
C
DyB
k
xA
C
DyBAx
yxz
y
y
y
y
?
??
?????
?
????
??
?
?
? 扫描线深度缓存器算法 （扫描线 Z-buffer算法）
? 特点分析, A缓冲器算法
2013-3-1 华中理工大学计算机学院 陆枫
99-7
11
9.2 区间扫描线算法
算法原理,避免对被遮挡区域的采样是进一步提高扫描线
算法计算效率的关键
图9 - 3 区间扫描线算法原理
0 x
y
扫描线2
A 1
A 2
A 3
B 1
B 2
B 3 B 4
扫描线1
扫描线3
C 1
C 2
C 3
C 4
A B
C
2013-3-1 华中理工大学计算机学院 陆枫
99-7
12
算法,
? 三张表,边表, 多边形表, 有效边表 。
? 算法的关键,分割子区间, 确定子区间上的唯一可见面 。
? 特殊情形,贯穿情形, 循环遮挡情形 。
图9 - 4 扫描线子区间
xz
21
(a) (b) (c)
3 4
xz
21 3 4
xz
21 3 45 5 5
2013-3-1 华中理工大学计算机学院 陆枫
99-7
13
贯穿情形,
? 为了使算法能处理 互相贯穿的多边形, 扫描线上的分割
点不仅应包含各多边形的边与扫描线的交点, 而且应包
含这些贯穿边界与扫描线的交点
图9 - 4 扫描线子区间
xz
21
(a) (b) (c)
3 4
xz
21 3 4
xz
21 3 45 5 5
2013-3-1 华中理工大学计算机学院 陆枫
99-7
14
循环遮挡,
? 将多边形进行划分以消除循环遮挡
图9 - 5 多边形贯穿和循环遮挡的情形
(a) 贯穿 (b) 循环遮挡
2013-3-1 华中理工大学计算机学院 陆枫
99-7
15
例 如,
图9 - 3 区间扫描线算法原理
0 x
y
扫描线2
A 1
A 2
A 3
B 1
B 2
B 3 B 4
扫描线1
扫描线3
C 1
C 2
C 3
C 4
A B
C
2013-3-1 华中理工大学计算机学院 陆枫
99-7
16
9.3 深度排序算法 （ 画家算法 ）
算法原理,若场景中任何多边形在深度上均不贯穿或循环
遮挡, 则各多边形的优先级顺序可完全确定 。
深度排序算法,
1.将多边形按深度进行排序：距视点近的优先级高, 距视
点远的优先级低 。
2.由优先级低的多边形开始逐个对多边形进行扫描转换 。
其中的 关键是将多边形按深度进行排序 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
17
y
x
A B
图9 - 7 A 和 B 在 xoy 平面上投影的包围盒无重叠
xz
A
B
图9 - 8 A 位于B 上A 与B 的重叠面之后
2013-3-1 华中理工大学计算机学院 陆枫
99-7
18
x
A
B
图9- 9 B上A与B的重 叠面完全位于A之前
z x
A
B
图9- 10 A、B、C之间 的遮挡关系
z
C
2013-3-1 华中理工大学计算机学院 陆枫
99-7
19
9.4 区域细分算法
? 算法原理
? 一种简单的 细分方式是将区域分割为四块大小
相等的矩形
2013-3-1 华中理工大学计算机学院 陆枫
99-7
20
图9- 11 多边形的投影与考察区域之间的关系
考察区域 考察区域 考察区域 考察区域
(a)围绕多边形 (b)相交多边形 (c)被包含多边形 (d)分离多边形
2013-3-1 华中理工大学计算机学院 陆枫
99-7
21
可见性测试
自适应细分
图9 - 1 2 满足测试条件3 的两个例子
(a) (b)
xz
围绕多边形
相交多边形
被包含多边形
xz
围绕多边形
相交多边形
被包含多边形
2013-3-1 华中理工大学计算机学院 陆枫
99-7
22
9.5 光线投射算法
算法原理, x
y
z
图9 - 1 3 光线投射算法
投影线
投影平面
2013-3-1 华中理工大学计算机学院 陆枫
99-7
23
算法步骤可简单描述如下,
1,通过视点和投影平面 （ 显示屏幕 ） 上的所有象素
点作一入射线, 形成投影线 。
2,将任一投影线与场景中的所有多边形求交 。
3,若有交点, 则将所有交点按 z值的大小进行排序,
取出最近交点所属多边形的颜色；若没有交点,
则取出背景的颜色 。
4,将该射线穿过的象素点置为取出的颜色 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
24
9.6 BSP树算法
? 算法原理
? 实例说明
图9- 1 4 B S P 算法原理
投影线
B
(a) 空间剖分 (b) 形成的B SP树
P
Q Q
D B C A
P
Q
front
front front
back
back back
front
back
front
back
D
C
A
2013-3-1 华中理工大学计算机学院 陆枫
99-7
25
9.7 多边形区域排序算法
算法思想,
将多边形按深度值由小到大排序, 用前面的可
见多边形去切割位于其后的多边形, 使得最终
每一个多边形要么是完全可见的, 要么是完全
不可见的 。
2013-3-1 华中理工大学计算机学院 陆枫
99-7
26
习题