③ 如何突出边对信息；
④ 如何方便地计算边对中各像素点处的相关坐标。 y
j+1 j
Ⅰ Ⅱ
扫描线
x
2. 相关性的应用 ① 计算多边形边的投影与扫描线交点的 x 坐标
设多边形 Fk 的投影上的边 L 的方程为： y px + qy + r = 0
则扫描线 y=j 与其交点的 X 坐标为： qj + r Xj = — (p ≠ 0) p 而扫描线 y=j+1 与其交点的 X 坐标为：
视点位置
视线方向
z值
视点
按观察方向上离视点（投影参考点） 的远近（通常用 z 值来表示）排序。
u(x)
2. 测试 用以判断点与面、线与面、面与面之间的关系。
包含测试： 测试空间点的投影是否在某个空间多边形的投影内，若在， 则可能存在遮挡关系；若不在，则不存在遮挡关系。 测试方法： 从空间点的投影开始向与 －y 轴平行的方向作射线，计算 该射线与空间多边形的投影的交点个数，若为奇数，则点的投
二 深度缓存算法 ( Z—buffer算法)
为了避免画家算法复杂的运算，人们提出了Z缓 冲区算法。Z缓冲区算法又称为深度缓存算法， 是一种简单的面消隐算法。它不仅需要一个帧缓 冲区(FB)来存放每个像素的亮度值，而且还需要 有一个Z缓冲区(ZB)来存放每个像素的深度值， 即Z坐标。这正是Z缓冲区算法名称的来历。
for ( i=1; i<= m ; i++ )
/* 每根扫描线上有 m 个像素点 */
for ( k=1; k<=p ; k++ ) /* 共有 p 个多边形 */ { 判断像素点( i, j )是否在多边形Fk在投影面上的投影内; 若( i, j )在多边形Fk的投影内，计算多边形Fk上对应于 像素点( i, j )处的深度值 Zi, j ;
if ( Zi, j < ZB( i, j ) )
{ ZB( i, j ) = Zi, j ; FB( i, j ) =多边形Fk的颜色 } else 不作处理 }
3. 算法实现中的关键问题 ①判断点( i, j )是否在多边形Fk在投影面上的投影内 解决办法：采用包含测试。
②计算多边形Fk在点( i, j )处的深度值 Zi, j 若多边形Fk的平面方程为： ax + by + cz + d = 0 若 c ≠ 0，则 Zi, j = —
j+1 j L Fk 扫描线
o
xj xj+1
x
q(j+1)+r qj+r q q Xj+1= — = — p — p = Xj — p = Xj —Δ X p ∴利用Δ X 就可方便地递推得到该边与下一条扫描线交点 的 x 坐标。
② 计算多边形 Fk 在点( i, j , Zi, j )处的深度值 Zi, j 设多边形 Fk 的方程为： ax + by + cz + d = 0 则多边形 Fk 上的点 ( i, j , Zi, j )处的深度值 Zi, j 为： ai + bj + d Zi, j = — (c ≠ 0) c 而点 ( i+1, j , Zi+1, j )处的深度值 Zi+1, j为：
二 深度缓存算法 ( Z—buffer算法)
1. Z—Buffer 用于存放与屏幕上像素点对应的物体上点的深度值。 y
投影面
z
视线方向
视点位置
x
屏幕像素
F — Buffer
Z—Buffer
2. 算法 初始化：ZB( i, j )=机器最大值 ；FB( i, j )=背景色。 for ( j=1; j<= n ; j++ ) /* 共有 n 根扫描线 */
④ 有效边表 AET（边活化表） 记录多边形边界与当前扫描线相交的各个边对的信息。 xl：左交点的x坐标值；
Δxl：左交点所在边和相邻扫描线交点的x坐标之差；
ylmax：左侧边两端点中较大的 y 值； xr，Δxr， yrmax ：右交点对应的三个量； zl：左交点处多边形所在平面的深度值； Δzx：沿扫描线向右走过一个象素时，多边形所在平面深度的增
一个像素处，场景中的物体哪一个距离观察点最近（可见 的），从而用它的颜色来显示该像素。此类算法通常用于消除 隐藏面。 若显示区域中有 m×n 个像素，则其计算复杂度为O(mnkh)。
算法描述如下：
for (窗口内的每一个像素) {确定距观察点最近的物体，以该物体表面的颜色来显示像素； }
三.消隐算法中常用的处理技术 1. 排序 确定物体间遮挡关系的要素： v(y) n(z)
影在多边形的投影内；若为偶数，则点的投影不在多边形的投
影内。 y 特殊情况 左闭右开
x
P414
夹角之和检验法
重叠测试： 测试两个空间多边形的投影是否重叠，若重叠，则可能存 在遮挡关系；若不重叠，则不存在遮挡关系。
测试方法：包围盒法
四.提高消隐算法效率的常用方法 1. 利用相关性（连贯性） 物体的相关性：若物体 A 与物体 B 是完全相互分离的，消
1.消除隐藏线 对于采用物体的棱线或轮廓线表示的线框图形，应消去物 体本身看不见的棱线和轮廓线部分，以及因物体间的互相遮挡
而被隐藏的棱线和轮廓线。
2.消除隐藏面 对于采用光栅扫描着色方法（即采用物体表面不同的明暗 度）绘制的图形，应消除物体上看不见的面以及因物体间的互 相遮挡而被隐藏的面。
对象空间（Object Space）消隐算法 是以场景中的物体为处理单元，将一个物体与其余的 k－1 个物体逐一比较，仅显示它可见的表面以达到消隐的目的。此 类算法通常用于消除隐藏线。
ai + bj + d a Zi+1, j = — — c c ∴利用 Δ Zx 就可方便地递推得到
该多边形在同一条扫描线上相邻 后续各点的深度值。
= Zi, j —Δ Zx y
Zi+1, j Zi, j
Fk
j
z
i i+1
o
x
③ 计算多边形边界上（对应于边的投影与扫描线交点处）的深 度值 设 L 为多边形 Fk的一条边，与扫描线 j 的交点为 Xj ，
6. 算法的进一步改进
① 采用分区处理方法。 ② 利用相关性。
8.3 扫描线算法
1. 基本思路 ① 只需考虑与多边形投影相交的扫描线。 ② 对每条扫描线，只需处理与多边形投影中某二条边的交点 中间的部分（边对）。
③ 对各多边形逐个处理，方法同Z—Buffer算法。 y
扫描线
o
x
为提高算法的效率，需解决几个问题： ① 如何建立扫描线与多边形投影之间的关系； ② 如何建立扫描线与多边形边投影之间的关系；
假定场景中有 k 个物体，平均每个物体的表面由 h 个多边
形构成，其计算复杂度为 O((kh)2)。 算法描述如下： for (场景中的每一个物体) { 将该物体与场景中的其它物体进行比较，确定其表面的可
见部分；
显示该物体表面的可见部分；
}
图像空间（Image Space）消隐算法：
是以窗口内的每个像素为处理单元，确定在每
∧
① 多边形 Y 桶 用于描述图形中的各多边形与扫描线之间的关系。 桶的长度与屏幕上的扫描线数相同。
根据多边形各顶点中最小的 y 坐标，将其放入相应的桶内。
y
10 8 6 4 2
10 9 8 7 6 5 4 x 3 2 1
Ⅰ Ⅱ
Ⅲ
Ⅲ Ymax=10 ∧ Ⅰ Ymax=10 ∧ Ⅱ Ymax= 8 ∧
隐时只需比较 A 、 B 两物体之间的遮挡关系，而不需对其表面
多边形逐一进行测试。
面的相关性：一个面内的各种属性值（坐标值、灰度值等）
一般都是缓慢变化的，可采用简单增量方式进行计算。 区域相关性：一个区域是指屏幕上一组相邻的像素，它们 通常属于同一个可见面。区域相关性表现在一条扫描线上时,即 为扫描线上的每个区间内只有一个面可见。
3. 背面剔除 一个平面多面体的表面由若干个 平面多边形构成，若一个多边形表面
D
C
的外法线方向与投影方向（观察方向）
的夹角为钝角，则该面为前向面；若 其夹角为锐角，则为后向面或背面。
A
B
投影方向
4. 活化表技术 ( active list )
设置活化表，用于存放与当前的处理相关的信息，从而可
最大限度地缩小处理范围，提高算法的效率。
q b + · — c p c
a
= Z j + Δ Zx · X — Δ zy Δ ∴利用 Δ Zy 就可递推得到下一条扫描线与边 L 交点处的深度值。
3. 数据结构 桶 ─ 源于 Knuth 的 bucket sort。 用于存放按照一定的规则（顺序）排列的若干组数据或处
理对象。
通常情况下，桶是采用向量形式和链表形式结合起来构造成 的一种特定的数据结构。 ∧
一 画家算法
一 画家算法
画家算法的优点是简单、易于实现，并且可以 作为实现更为复杂算法的基础。它的缺点是只 能处理互不相交的面，而且深度优先级表中的 顺序可能出错，如两个面相交或三个面相互重 叠的情况，用任何方法都不能排出正确的顺序。 这时，只能把有关的面进行分割后再排序。增 加了算法的复杂度，因此，该算法使用具有一 定的局限性。
ai + bj + d c
若 c = 0，则多边形Fk的法线方向与 Z 轴垂直， Fk在投影面
上的投影为一条直线，可不予考虑。
4. 算法的特点 ① 简单 不需要将所有的多边形按离视点的远近排序，其算法的复
杂度只与多边形的个数成正比。
② 需要有一个较大容量的 Z—Buffer 。