浙江大学信息学院 计算机图形学第九章 消隐
消隐的分类
消除隐藏线
消除隐藏面
– 基本概念
– 提高消隐算法效率的常见方法
– 画家算法
– Z缓冲区 (Z-Buffer)算法
– 扫描线 Z-buffer算法
– 扫描线算法
– 区域子分割算法
– 光线投射算法浙江大学信息学院 计算机图形学基本概念
投影变换失去了深度信息,往往导致图形的二义性
要消除二义性,就必须在绘制时消除被遮挡的不可见的线或面,习惯上称作消除隐藏线和隐藏面,简称为消隐 。
经过消隐得到的投影图称为物体的真实图形。
长方体线框投影图的二义性浙江大学信息学院 计算机图形学基本概念
消隐的对象是三维物体。三维体的表示主要有边界表示和 CSG表示等。
消隐结果与观察物体有关，也与视点有关。
线框图 消隐图 真实感图形浙江大学信息学院 计算机图形学消隐的分类
按消隐对象分类
– 线消隐
消隐对象是物体上的边,消除的是物体上不可见的边 。
– 面消隐
消隐对象是物体上的面,消除的是物体上不可见的面 。
浙江大学信息学院 计算机图形学消除隐藏线
对造型的要求
– 在线框显示模型中,要求造型系统中有面的信息，最好有体的信息。
坐标变换
– 将视点变换到 Z轴的正无穷大处，视线方向变为 Z轴的负方向。
最基本的运算
– 判断面对线的遮挡关系,反复地进行线线、
线面之间的求交运算浙江大学信息学院 计算机图形学面消隐面消隐算法的分类提高消隐算法效率的常见方法画家算法
Z缓冲器算法扫描线 Z缓冲器算法区域子分算法光线投射算法浙江大学信息学院 计算机图形学面消隐算法的分类
消隐算法的分类第一类（图像空间的消隐算法）：以窗口内的每个像素为处理单元；如 Z－ buffer、扫描线,Warnock算法
for (窗口内的每一个像素 )
{ 确定距视点最近的物体，以该物体表面的颜色来显示像素 }
第二类（物体空间的消隐算法）：以场景中的物体为处理单元；如光线投射算法
for (场景中的每一个物体 )
{ 将其与场景中的其它物体比较，确定其表面的可见部分；
显示该物体表面的可见部分；
}
浙江大学信息学院 计算机图形学面消隐算法的分类第一类（图像空间的消隐算法）：以窗口内的每个像素为处理单元；
for (窗口内的每一个像素 )
{ 确定距视点最近的物体，以该物体表面的颜色来显示像素 }
假设场景中有 k个物体，平均每个物体表面由 h个多边形构成，显示区域中有 m x n个像素，则：
算法的复杂度为,O(mnkh)
浙江大学信息学院 计算机图形学面消隐算法的分类第二类（物体空间的消隐算法 ）：以场景中的物体为处理单元；
for (场景中的每一个物体 )
{ 将其与场景中的其它物体比较，确定其表面的可见部分；
显示该物体表面的可见部分；
}
假设场景中有 k个物体，平均每个物体表面由 h个多边形构成，显示区域中有 m x n个像素，则：
算法的复杂度为,O((kh)*(kh))
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法
利用连贯性
将透视投影转换成平行投影
包围盒技术
背面剔除
空间分割技术
物体分层表示浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 1
利用连贯性：相邻事物的属性之间有一定的连贯性，其属性值通常是平缓过渡的，如颜色值、空间位置关系等。
物体连贯性
面的连贯性
区域连贯性
扫描线的连贯性
深度连贯性浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 1
物体连贯性：如果物体 A与物体 B是完全相互分离的，则在消隐时，只需比较 A,B两物体之间的遮挡关系就可以了，无须对它们的表面多边形逐一进行测试。例如，若 A距视点较 B远，则在测试 B上的表面的可见性时，无须考虑 A的表面。
面的连贯性：一张面内的各种属性值一般都是缓慢变化的，允许采用增量形式对其进行计算。
区域连贯性：区域指屏幕上一组相邻的像素，
它们通常为同一个可见面所占据，可见性相同。
区域连贯性表现在一条扫描线上即为扫描线上的每个区间内只有一个面可见。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 1
扫描线的连贯性：相邻两条扫描线上，
可见面的分布情况相似。
深度连贯性：同一表面上的相邻部分深度是相近的，而占据屏幕上同一区域的不同表面的深度不同。这样在判断表面间的遮挡关系时，只需取其上一点计算出深度值，比较该深度值即可得到结果。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 2
将透视投影转换成平行投影消隐与透视关系密切,体现在：
1）消隐必须在投影之前完成；
2）物体之间的遮挡关系与投影中心（视点）的选取有关；
3）物体之间的遮挡关系与投影方式有关浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 3
包围盒技术定义,一个形体的包围盒指的是包围它的简单形体。
一个好的包围盒要具有两个条件：
包围和充分紧密包围着形体；
对其的测试比较简单。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 3
应用 —避 免盲目求交例如：两个空间多边形 A,B在投影平面上的投影分别为 A’,B’,因为 A’,B’ 的矩形包围盒不相交，则 A’,B’ 不相交，
无须进行遮挡测试。右下图：包围盒相交，
投影也相交；包围盒相交，投影不相交。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 4
背面剔除外法向：规定每个多边形的外法向都是指向物体外部的。
前向面：若多边形的外法向与投影方向（观察方向）的夹角为钝角，称为前向面。
后向面：若多边形的外法向与投影方向（观察方向）的夹角为锐角，称为后向面（背面） 。
剔除依据：背面总是被前向面所遮挡，从而不可见。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 4
前向面 后向面 多面体的隐藏线消除图中的 JEAF,HCBG和 DEABC所在的面均为后向面。
其它为前向面。
V
A
B
C
D
E
F
G
H
I
J
N
V
n
V
n
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 5
空间分割技术依据：场景中的物体，它们的投影在投影平面上是否有重叠部分？（是否存在相互遮挡的可能？）对于根本不存在相互遮挡关系的物体，应避免这种不必要的测试。
方法：将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断那个物体可见时，只要对该区域的相关物体表中的物体进行比较即可。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 5
复杂度比较：
不妨假定每个小区域的相关物体表中平均有 h个物体，场景中有 k个物体，由于物体在场景中的分布是分散的，显然 h远小于 k。根据第二种消隐方法所述，其算法复杂度为 O(h*h),远小于 O(k*k)。
第二类消隐方法（物体空间的消隐算法）：以场景中的物体为处理单元；
for (场景中的每一个物体 )
{ 将其与场景中的其它物体比较，确定其表面的可见部分 }
假设场景中有 k个物体，平均每个物体表面由 h个多边形构成，则：算法的复杂度为,O((kh)*(kh))
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 6
物体分层表示表示形式：模型变换中的树形表示方式原理：减少场景中物体的个数，从而降低算法复杂度。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 6
方法,将父节点所代表的物体看成子节点所代表物体的包围盒，当两个父节点之间不存在遮挡关系时，就没有必要对两者的子节点做进一步测试。父节点之间的遮挡关系可以用它们之间的包围盒进行预测试。
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
由来：画家的作画顺序暗示出所画物体之间的相互遮挡关系
算法基本思想：
1）先把屏幕置成背景色
2）先将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中；（线性表构造：距观察点远的称优先级低，放在表头；距观察点近的称优先级高，放在表尾。该表称为深度优先级表）
3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体。
关键：如何对场景中的物体按深度（远近）排序，建立深度优先级表？
一种针对多边形的排序算法如下：
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
Step 1:将场景中所有多边形存入一个线性表，记为 L；
Step 2,如果 L中仅有一个多边形，算法结束；否则根据每个多边形的 Zmin对它们预排序。不妨假定多边形 P落在表首，即 Zmin(P)为最小。再记 Q为 L – {P}(表中其余多边形）中任意一个；
Step 3,判别 P,Q之间的关系，有如下二种：
（ 1）,对所有的 Q，有 Zmax(P)< Zmin (Q),则多边形
P的确距观察点最远，它不可能遮挡别的多边形。令 L
= L – {P},返回第二步 ;
（ 2）,存在某一个多边形 Q，使 Zmax(P) > Zmin (Q),
需进一步判别：
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
A）若 P,Q的投影 P’,Q’ 的包围盒不相交（图 a），
则 P,Q在表中的次序不重要，令 L = L – {P},
返回 step 2;否则进行下一步。
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
B）若 P的所有顶点位于 Q所在平面的不可见的一侧 (图 b)，则 P,Q关系正确，令 L = L – {P},
返回 step 2;否则进行下一步。
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
C）若 Q的所有顶点位于 P所在平面的可见的一侧
(图 c)，则 P,Q关系正确，令 L = L – {P},返回 step 2;否则进行下一步。
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
D） 对 P,Q投影 P’,Q’ 求交，若 P’,Q’ 不相交 (图 d)，则
P,Q在表中的次序不重要，令 L = L – {P},返回 step
2;否则在它们所相交的区域中任取一点，计算 P,Q在该点的深度值，如果 P的深度小，则 P,Q关系正确，令 L =
L – {P},返回 step 2;否则交换 P,Q,返回 step 3.
浙江大学信息学院 计算机图形学画家算法
本算法不能处理的情况：
多边形循环遮挡多边形相互穿透解决办法：分割成两个浙江大学信息学院 计算机图形学
Z-Buffer算法
由来：
帧缓冲器 – 保 存各像素颜色值
Z缓冲器 --保 存各像素处物体深度值
Z缓冲器中的单元与帧缓冲器中的单元一一对应屏幕 帧缓冲器 Z缓 冲器每个单元存放对应象素的颜色值每个单元存放对应象素的深度值浙江大学信息学院 计算机图形学
Z-Buffer算法思想,先将 Z缓冲器中个单元的初始值置为最小值。当要改变某个像素的颜色值时，首先检查当前多边形的深度值是否大于该像素原来的深度值（保存在该像素所对应的 Z缓冲器的单元中），如果大于，说明当前多边形更靠近观察点，用它的颜色替换像素原来的颜色；否则说明在当前像素处，当前多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色值不改变。
浙江大学信息学院 计算机图形学
Z-Buffer算法 -算法描述
{ 帧缓存全置为背景色深度缓存全置为最小 Z值
for(每一个多边形 )
{ for(该多边形所覆盖的每个象素 (x,y) )
{ 计算该多边形在该象素的深度值 Z(x,y);
if(Z(x,y)大于 Z缓存在 (x,y)的值 )
{ 把 Z(x,y)存入 Z缓存中 (x,y)处把多边形在 (x,y)处的颜色值存入帧缓存的 (x,y)处
}
}
}
}
需要计算的像素深度值次数
=多边形个数 *多边形平均占据的像素个数浙江大学信息学院 计算机图形学
Z-Buffer算法
Z缓冲器算法是所有图像空间算法中最简单的一种隐藏面消除算法。它 在象素级上以近物取代远物，与形体在屏幕上的出现顺序无关。
优点,1）简单稳定，利于硬件实现
2） 不需要整个场景的几何数据
缺点,1）需要一个额外的 Z缓冲器
2）在每个多边形占据的每个像素处都要计算深度值，计算量大浙江大学信息学院 计算机图形学
Z-Buffer算法 -改进算法
只用一个深度缓存变量 zb的改进算法。
– 一般认为,Z-Buffer算法需要开一个与图象大小相等的缓存数组 ZB，实际上，可以改进算法，只用一个深度缓存变量 zb。
浙江大学信息学院 计算机图形学
Z-Buffer算法 -改进算法过程
{ 帧缓存全置为背景色
for(屏幕上的每个象素 (i,j))
{ 深度缓存变量 zb置最小值 MinValue
for(多面体上的每个多边形 Pk)
{ if(象素点 (i,j)在 pk的投影多边形之内 )
{ 计算 Pk在 (i,j)处的深度值 depth;
if(depth大于 zb)
{ zb = depth;
indexp = k; }
}
}
}
if(zb != MinValue)
在交点 (i,j) 处用多边形 Pindexp的颜色显示
}
}
浙江大学信息学院 计算机图形学
Z-Buffer算法 -改进算法
– 关键问题：判断象素点 (i,j)是否在多边形
Pk的投影多边形之内
– 计算多边形 Pk在点（ i,j）处的深度。设多边形 Pk的平面方程为,0 dczbyax
c
dbjaide pt h
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
由来,Z缓冲器算法中所需要的 Z缓冲器容量较大，
为克服这个缺点可以将整个绘图区域分割成若干个小区域，然后一个区域一个区域地显示，这样 Z缓冲器的单元数只要等于一个区域内像素的个数就可以了。
如果将小区域取成屏幕上的扫描线，就得到 扫描线 Z
缓冲器算法。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
算法思想,
– 在处理当前扫描线时，开一个一维数组作为当前扫描线的 Z-buffer。首先 找出与当前扫描线相关的多边形，以及每个多边形中相关的边对 。
– 对每一个边对之间的小区间上的各象素，计算深度，并与 Z-buffer中的值比较，找出各象素处可见平面。
– 写帧缓存。采用增量算法计算深度。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
for ( v= 0;v<vmax;v++)
{ for (u= 0; u<umax; u++)
{ 将帧缓冲器的第 (u,v)单元置为背景色；
将 Z缓冲器的第 u单元置为最小值 }
for (每个多边形）
{ 求出多边形在投影平面上的投影与当前扫描线的相交区间
for （该区间内的每个像素 (u,v) ）
{ 计算多边形在该像素处的深度值 d；
if (d > Z缓冲器的第 u单元的值）
{ 置帧缓冲器的第 (u,v)单元值为当前多边形颜色；
置 Z缓冲器的第 u单元值为 d; }
}
}
//处理下一条扫描线
}
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
改进之一：将窗口分割成扫描线
Z缓冲器的单元数只要等于一条扫描线内像素的个数就可以了。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
改进之二：采用多边形分类表、活化多边形表避免 多边形 与扫描线的盲目求交浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -多边形分类表
多边形分类表（ PT）：对多边形进行分类的一维数组，长度等于绘图窗口内扫描线的数目。若一个多边形在投影平面上的投影的最小 v坐标为 v，则它属于第 v类。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -活化多边形表
活化多边形表
（ APL）：记录投影与当前扫描线相交的多边形。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -多边形
其中，多边形的数据结构如下：
a,b,c,d：多边形所在平面方程
f(u,v,n)=au+bv+cn+d=0的系数。
color:多边形的颜色
vmax:多边形在投影平面上的投影的最大
v坐标值。
PI：多边形的序号
nextP：指向下一个多边形结构的指针浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
改进之三：利用边、边的分类表、
边对、活化边对表避免 边 与扫描线的盲目求交浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -边数据结构
边：用来记录多边形的一条边，其中
vmax：边的投影的上端点的 v坐标。
u：边的下端点的 u坐标
n：边的下端点的 n坐标
Du：在该边上 v值增加一个单位时,u坐标的变化量 D
nextE：指向下一条边结构的指针。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -边的分类表
边的分类表（ ET）：当一个多边形 进入活化多边形表时,需为其建立一个边分类表（ ET）。这里,ET与其在扫描转换多边形的扫描线算法中的含义相同，是对多边形的非水平边进行分类的一维数组，长度等于绘图窗口内扫描线的数目。若一条边在投影平面上的投影的下端点的 v坐标为 v，则将该边归为第 v类。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -边对
边对：在一条扫描线上,同一多边形的相邻两条边构成一个边对 。
边对中包含了如下信息：
ul,边对的左侧边与扫描交点的 u坐标
Dul,当沿左侧边 v坐标递增一个像素时,u坐标的增量
vlmax,左侧边投影的上端点的 v坐标。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -边对
ur,边对的右侧边与扫描交点的 x坐标
Dur,当沿右侧边 v坐标递增一个像素时,u坐标的增量
vrmax,右侧边投影的上端点的 v坐标 。
nl,左侧边与扫描线交点的 n坐标
PI,多边形的序号浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -边对
Dnu,当沿扫描线 u递增一个像素时，多边形所在平面
n坐标的增量,对方程 au+bv+cn+d=0来说,Dnu =-a/c
Dnv,当沿扫描线 v递增一个像素时，多边形所在平面
n坐标的增量，类似,Dnv =-b/c (c!=0)
nextEP:指向下一个边对结构的指针。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -活化边表对
活化边表对（ AEPL）：记录了活化多边形表中与当前扫描线相交的边对，边对在 AEPL中的顺序无关紧要。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
改进之四：利用连贯性计算深度
– 水平方向,当沿扫描线 u递增一个像素时，多边形所在平面 n坐标的增量,对方程 au+bv+cn+d=0来说,Dnu =-a/c
– 竖直方向
Dnv,当沿扫描线 v递增一个像素时，多边形所在平面 n坐标的增量,Dnv =-b/c
下一条扫描线与边对左侧边交点处的深度值：
nl=nl+DnuDul+Dnv
umax
vmax
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
1、建多边形分类表：对每一个多边形,若它 在投影平面上的投影的最小 v坐标为 v，则它属于第 v类。
2、置活化多边形表 APL为空，置活化边对表 AEPL为空。
3、对每条扫描线 v，执行下列步骤：
（ 1）置帧缓存器第 v行中的各单元为背景色。
（ 2）置 Z缓冲器各单元的值为最小的深度值。
（ 3）检查 PT(多边形分类表 )的第 v类是否非空，如果非空，将该类中的多边形取出加入 APL(活化多边形表 )中。
（ 4）对新加入 APL(活化多边形表 )中的多边形，为其建立边的分类表 ET。
（ 5）对新加入 APL (活化多边形表 )中的多边形，若它的
ET（边的分类表）中的第 v类非空，将其中的边配对插入 AEPL（活化边对表）中；
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
（ 6）对 AEPL（活化边对表）中的每一个边对，
执行下列步骤：
深度值 n=nl;
for （ u=ul;u<=ur;u=u+1 ）
{
if (n > Z缓冲器的第 u单元的值）
{ 置帧缓冲器的第 (u,v)单元值为当前多边形颜色；
置 Z缓冲器的第 u单元值为 n;
}
n=n+ Dnu;//计算下一个像素 (u+1,v)处多边形的深度值
}
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
（ 7）检查 APL (活化多边形表 ),删除那些满足 vmax=v的多边形，
释放该多边形的 ET，并从 AEPL中删除属于该多边形的边对。
（ 8）检查 AEPL（活化边对表）中的每一个边对，执行下列步骤：
A 若 vlmax=v或 vrmax=v，删除边对中的左侧边或右侧边。
B 若左侧边和右侧边都从边对中删除了，则从 AEPL（活化边对表）中删去该边对；若边对中仅有一条边被删去了，则从该边对所属的多边形的 ET中找到另一条边与余下的边配对，组成新的边对，加入 AEPL（活化边对表） ；
C 计算下一条扫描线与边对两边交点的 x坐标：
ul=ul+Dul； ur=ur+Dur
D 计算下一条扫描线与边对左侧边交点处的深度值：
nl=nl+DnuDul+Dnv
（ 9）将扫描线递增一个像素,v=v+1
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
缺点
– 在每一个被多边形覆盖像素处需要计算深度值
– 被多个多边形覆盖的像素需要多次计算深度值浙江大学信息学院 计算机图形学区间扫描线算法与 Z-Buffer算法相比，扫描线算法有了很大改进，比如所需的 Z-Buffer大大减小，
计算深度利用了面连贯性等；
缺点：每个像素处都计算深度值，甚至不止一次的计算，运算量仍然很大。
改进：在一条扫描线上，每个区间只计算一次深度，即区间扫描线算法，又称扫描线算法。
浙江大学信息学院 计算机图形学区间扫描线算法
基本思想,如下图，多边形 P1,P2的边界在投影平面上的投影将一条扫描线划分成若干个区间
[0,u1][u1,u2][u2,u3][u3,u4],[u4,umax],覆盖每个区间的有 0个,1个或多个多边形，但仅有一个可见。在区间上任取一个像素，计算该像素处各多边形（投影包含了该像素的多边形）的深度值，深度值最大者即为可见多边形，用它的颜色显示整个区间。
浙江大学信息学院 计算机图形学区间扫描线算法注意：该算法要求多边形不能相互贯穿，否则在同一区间上，多边形深度值的次序会发生变化。
如图：在区间 [u1,u2]上，多边形 P1的深度值大，
在区间 [u3,u4]上，多边形 P2的深度值大，而在区间 [u2,u3]上，两个多边形的深度值次序发生交替。
浙江大学信息学院 计算机图形学区间扫描线算法
数据结构
– 多边形分类表
– 活化多边形表
– 边的分类表
– 活化边表
类似于扫描线 Z-Buffer算法中的数据结构浙江大学信息学院 计算机图形学区间扫描线算法 -算法描述
for (绘图窗口内的每一条扫描线）
{ 求投影与当前扫描线相交的所有多边形求上述多边形中投影与当前扫描线相交的所 有边，将它们记录在活化边表 AEL中求 AEL中每条边的投影与扫描线的交点；
按交点的 u坐标将 AEL中各边从左到右排序,两两配对组成一个区间；
for （ AEL中每个区间）
{
求覆盖该区间的所有多边形，将它们记入活化多边形表 APL中；
在区间上任取一点，计算 APL中各多边形在该点的深度值，记深度最大者为 P；
用多边形 P的颜色填充该区间
}
}
浙江大学信息学院 计算机图形学区间扫描线算法
相比较扫描线 Z-Buffer算法而言，区间扫描线算法做了如下改进：
一、在一条扫描线上，以区间为单位确定多边形的可见性二、不再需要 Z-Buffer
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
由来,Z缓冲器算法与扫描线 Z缓冲器算法中都是将像素孤立来考虑，未利用相邻像素之间存在的属性的连贯性，即区域的连贯性，所以算法效率不高。实际上，可见多边形至少覆盖了绘图窗内的一块区域，这块区域由多边形在投影平面上的投影的边界围成。如果能将这类区域找出来，再用相应的多边形颜色加以填充则避免了在每个像素处计算深度值，消隐问题也就解决了。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
算法基本思路,首先将场景中的多边形投影到绘图窗口内（ 假设它为边长为 k的正方形 ），判断窗口是否 足够简单,若是则算法结束；否则将窗口进一步分为四块。对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。此时可能有多个多边形覆盖了该像素，计算它们的深度值，以最近的颜色显示该像素即可。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
何谓窗口足够简单？
存在下列情况之一即可称为窗口足够简单：
1）窗口为空，即多边形与窗口的关系是 分离 的；
2）窗口内仅含一个多边形，即有一个多边形与窗口的关系是 包含或相交 。此时先对多边形投影进行裁剪，
再对裁剪结果进行填充；
3）有一个多边形的投影 包围 了窗口，
并且它是最靠近观察点的，以该多边形颜色填充窗口。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
分离和包围多边形的判别：通常有 3种判别方法：
射线检查法，转角累计检查法和区域检查法。
这三种检查都假定相交的和内含的多边形已经事先判定了。
– 射线检查法：从窗口内的任意点，画一条射线至无穷远处，累计射线与多边形交点的个数。如果为偶数 (或为零 )，则此多边形与窗口分离；否则，此多边形包围窗口。但当射线通过多边形的顶点时，会得出错误结论。
(如左图 )解决方法有：当射线通过多边形的局部极值顶点时，记入两个交点；当射线通过多边形的非局部极值顶点时，记入一交点。
y
x
p6
p7
p8
p4 p
10
p9
p3
p1
p2
p5
y
x
p6
p4
p3
p1
p2
p5
p6
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
转角累计检查法,按顺时针方向或逆时针方向绕多边形依次累加多边形各边起点与终点对窗口内任意一点所张的夹角。按累计角度之和可以判定：
– 若角度之和等于 0，则表示多边形与窗口分离；
– 若角度之和等于 ± 360o·n，则表示多边形包围窗口
(n次 )。
多边形窗口 窗口多边形
α
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
区域检查法,1）区域编码
2）多边形顶点编码
3）多边形边的编码
4）多边形的编码浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
1、区域编码。窗口四条边所在直线将屏幕划分成 9个区域，对窗口以外的 8个区域按逆时针（或顺时针）进行编码，编码为 0~7。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
2、多边形顶点编码。多边形 v0v1…v n的顶点 vi的投影落在哪个区域，那个区域的编码便作为该顶点的编码，记为 Ii。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
3、多边形的编码。多边形的边 vivi+1的编码定义为 Di=Ii+1-Ii,i=0,1…n ；其中，令
In+1=I0，并且，当 Di >4时，取 Di = Di -8；
当 Di <4时，取 Di = Di +8；
当 Di =+/-4时，取该边与窗口边的延长线的交点将该边分为两段，对两段分别按上面的规则编码，再令 Di等于两者之和。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
4、多边形的编码。定义多边形的编码为其边的编码之和,则
D
D
8
0
0
0
n
i
i
n
i
i
当多边形包围窗口当窗口与多边形分离浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
例如,I0=5,I1=7,I2=3,D0=7-
5=2,D1=3-7=-4,D2=5-3=2,
因为 D1=-4,按第三步的处理规则，取边 v1v2与窗口上边所在直线的交点将 v1v2分为两段，两段的编码分别为 2，
2，从而 D2=4。最终求出多边形的编码为
D0+ D1+D2=2+4+2=8，因此，
该三角形包围窗口。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
如图,I0=1,I1=3,I2=7,D0=3-1=2,
D1=7-3=4,D2=1-7=-6。按第 3步处理规则，取 v1v2与窗口上边所在直线的交点 v’ 将其分为两段，两段的编码分别为 -2,-
2，从而 D1=-2+（ -2） =-4。而
D2=-6+8=2。最终求出多边形的编码为 D0+D1+D2=2+（ -4）
+2=0。
从而得出结论：多边形与窗口分离。
浙江大学信息学院 计算机图形学光线投射算法
算法思想：将通过绘图窗口内每一个像素的投影线与场景中的所有多边形求交。如果有交点，用深度值最大的交点（最近的）所属的多边形的颜色显示相应的像素；如果没有交点，说明没有多边形的投影覆盖此像素，用背景色显示即可。
浙江大学信息学院 计算机图形学光线投射算法 -算法描述
for ( v= 0;v<vmax;v++)
for (u= 0; u<umax; u++)
{ 形成通过像素 (u,v)的投影线；
for (场景中每一个多边形）
将投影线与多边形求交；
if (有交点）
以最近交点所属多边形的颜色显示像素 (u,v)
else
以背景色显示像素 (u,v)；
}
浙江大学信息学院 计算机图形学光线投射算法
基本问题
– 光线与物体表面的求交浙江大学信息学院 计算机图形学消隐的考虑
选择不同的消隐算法消隐问题有不同的算法，有些算法要求速度快，有些要求图形的真实度高。例如，快速消隐算法可用于实时模拟如飞行模拟等；具有高度真实感图形的消隐算法可用于计算机动画等领域，所生成的图形一般具有连续色调，并能产生阴影、透明、表面纹理及反射、
折射等视觉效果。不过这类算法比较慢。产生一幅图可能需要几分钟甚至几小时。所以，在进行消隐算法的设计时，应在计算速度和图形细节之间进行权衡，
任何一种算法都不能兼顾两者。
浙江大学信息学院 计算机图形学消隐的考虑
消隐算法的实现空间消隐算法可以在物体空间或图像空间中实现。
物体空间算法是在定义物体的坐标系中实现的，而图像空间算法是在对象显示的屏幕坐标系中实现的。
物体空间算法以尽可能高的精度完成几何计算，所以可以把图像放大许多倍而不致损害其准确性，但是图像空间算法只能以与显示屏的分辨率相适应的精度来完成计算，所以其图像的放大效果较差。
这两类算法的性能特性也是不同的。物体空间算法所需的计算时间随场量中物体的个数而增加，而图像空间的计算时间则随图像中可见部分的复杂程度而增加。
消隐的分类
消除隐藏线
消除隐藏面
– 基本概念
– 提高消隐算法效率的常见方法
– 画家算法
– Z缓冲区 (Z-Buffer)算法
– 扫描线 Z-buffer算法
– 扫描线算法
– 区域子分割算法
– 光线投射算法浙江大学信息学院 计算机图形学基本概念
投影变换失去了深度信息,往往导致图形的二义性
要消除二义性,就必须在绘制时消除被遮挡的不可见的线或面,习惯上称作消除隐藏线和隐藏面,简称为消隐 。
经过消隐得到的投影图称为物体的真实图形。
长方体线框投影图的二义性浙江大学信息学院 计算机图形学基本概念
消隐的对象是三维物体。三维体的表示主要有边界表示和 CSG表示等。
消隐结果与观察物体有关，也与视点有关。
线框图 消隐图 真实感图形浙江大学信息学院 计算机图形学消隐的分类
按消隐对象分类
– 线消隐
消隐对象是物体上的边,消除的是物体上不可见的边 。
– 面消隐
消隐对象是物体上的面,消除的是物体上不可见的面 。
浙江大学信息学院 计算机图形学消除隐藏线
对造型的要求
– 在线框显示模型中,要求造型系统中有面的信息，最好有体的信息。
坐标变换
– 将视点变换到 Z轴的正无穷大处，视线方向变为 Z轴的负方向。
最基本的运算
– 判断面对线的遮挡关系,反复地进行线线、
线面之间的求交运算浙江大学信息学院 计算机图形学面消隐面消隐算法的分类提高消隐算法效率的常见方法画家算法
Z缓冲器算法扫描线 Z缓冲器算法区域子分算法光线投射算法浙江大学信息学院 计算机图形学面消隐算法的分类
消隐算法的分类第一类（图像空间的消隐算法）：以窗口内的每个像素为处理单元；如 Z－ buffer、扫描线,Warnock算法
for (窗口内的每一个像素 )
{ 确定距视点最近的物体，以该物体表面的颜色来显示像素 }
第二类（物体空间的消隐算法）：以场景中的物体为处理单元；如光线投射算法
for (场景中的每一个物体 )
{ 将其与场景中的其它物体比较，确定其表面的可见部分；
显示该物体表面的可见部分；
}
浙江大学信息学院 计算机图形学面消隐算法的分类第一类（图像空间的消隐算法）：以窗口内的每个像素为处理单元；
for (窗口内的每一个像素 )
{ 确定距视点最近的物体，以该物体表面的颜色来显示像素 }
假设场景中有 k个物体，平均每个物体表面由 h个多边形构成，显示区域中有 m x n个像素，则：
算法的复杂度为,O(mnkh)
浙江大学信息学院 计算机图形学面消隐算法的分类第二类（物体空间的消隐算法 ）：以场景中的物体为处理单元；
for (场景中的每一个物体 )
{ 将其与场景中的其它物体比较，确定其表面的可见部分；
显示该物体表面的可见部分；
}
假设场景中有 k个物体，平均每个物体表面由 h个多边形构成，显示区域中有 m x n个像素，则：
算法的复杂度为,O((kh)*(kh))
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法
利用连贯性
将透视投影转换成平行投影
包围盒技术
背面剔除
空间分割技术
物体分层表示浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 1
利用连贯性：相邻事物的属性之间有一定的连贯性，其属性值通常是平缓过渡的，如颜色值、空间位置关系等。
物体连贯性
面的连贯性
区域连贯性
扫描线的连贯性
深度连贯性浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 1
物体连贯性：如果物体 A与物体 B是完全相互分离的，则在消隐时，只需比较 A,B两物体之间的遮挡关系就可以了，无须对它们的表面多边形逐一进行测试。例如，若 A距视点较 B远，则在测试 B上的表面的可见性时，无须考虑 A的表面。
面的连贯性：一张面内的各种属性值一般都是缓慢变化的，允许采用增量形式对其进行计算。
区域连贯性：区域指屏幕上一组相邻的像素，
它们通常为同一个可见面所占据，可见性相同。
区域连贯性表现在一条扫描线上即为扫描线上的每个区间内只有一个面可见。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 1
扫描线的连贯性：相邻两条扫描线上，
可见面的分布情况相似。
深度连贯性：同一表面上的相邻部分深度是相近的，而占据屏幕上同一区域的不同表面的深度不同。这样在判断表面间的遮挡关系时，只需取其上一点计算出深度值，比较该深度值即可得到结果。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 2
将透视投影转换成平行投影消隐与透视关系密切,体现在：
1）消隐必须在投影之前完成；
2）物体之间的遮挡关系与投影中心（视点）的选取有关；
3）物体之间的遮挡关系与投影方式有关浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 3
包围盒技术定义,一个形体的包围盒指的是包围它的简单形体。
一个好的包围盒要具有两个条件：
包围和充分紧密包围着形体；
对其的测试比较简单。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 3
应用 —避 免盲目求交例如：两个空间多边形 A,B在投影平面上的投影分别为 A’,B’,因为 A’,B’ 的矩形包围盒不相交，则 A’,B’ 不相交，
无须进行遮挡测试。右下图：包围盒相交，
投影也相交；包围盒相交，投影不相交。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 4
背面剔除外法向：规定每个多边形的外法向都是指向物体外部的。
前向面：若多边形的外法向与投影方向（观察方向）的夹角为钝角，称为前向面。
后向面：若多边形的外法向与投影方向（观察方向）的夹角为锐角，称为后向面（背面） 。
剔除依据：背面总是被前向面所遮挡，从而不可见。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 4
前向面 后向面 多面体的隐藏线消除图中的 JEAF,HCBG和 DEABC所在的面均为后向面。
其它为前向面。
V
A
B
C
D
E
F
G
H
I
J
N
V
n
V
n
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 5
空间分割技术依据：场景中的物体，它们的投影在投影平面上是否有重叠部分？（是否存在相互遮挡的可能？）对于根本不存在相互遮挡关系的物体，应避免这种不必要的测试。
方法：将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断那个物体可见时，只要对该区域的相关物体表中的物体进行比较即可。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 5
复杂度比较：
不妨假定每个小区域的相关物体表中平均有 h个物体，场景中有 k个物体，由于物体在场景中的分布是分散的，显然 h远小于 k。根据第二种消隐方法所述，其算法复杂度为 O(h*h),远小于 O(k*k)。
第二类消隐方法（物体空间的消隐算法）：以场景中的物体为处理单元；
for (场景中的每一个物体 )
{ 将其与场景中的其它物体比较，确定其表面的可见部分 }
假设场景中有 k个物体，平均每个物体表面由 h个多边形构成，则：算法的复杂度为,O((kh)*(kh))
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 6
物体分层表示表示形式：模型变换中的树形表示方式原理：减少场景中物体的个数，从而降低算法复杂度。
浙江大学信息学院 计算机图形学提高消隐算法效率的常见方法 6
方法,将父节点所代表的物体看成子节点所代表物体的包围盒，当两个父节点之间不存在遮挡关系时，就没有必要对两者的子节点做进一步测试。父节点之间的遮挡关系可以用它们之间的包围盒进行预测试。
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
由来：画家的作画顺序暗示出所画物体之间的相互遮挡关系
算法基本思想：
1）先把屏幕置成背景色
2）先将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中；（线性表构造：距观察点远的称优先级低，放在表头；距观察点近的称优先级高，放在表尾。该表称为深度优先级表）
3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体。
关键：如何对场景中的物体按深度（远近）排序，建立深度优先级表？
一种针对多边形的排序算法如下：
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
Step 1:将场景中所有多边形存入一个线性表，记为 L；
Step 2,如果 L中仅有一个多边形，算法结束；否则根据每个多边形的 Zmin对它们预排序。不妨假定多边形 P落在表首，即 Zmin(P)为最小。再记 Q为 L – {P}(表中其余多边形）中任意一个；
Step 3,判别 P,Q之间的关系，有如下二种：
（ 1）,对所有的 Q，有 Zmax(P)< Zmin (Q),则多边形
P的确距观察点最远，它不可能遮挡别的多边形。令 L
= L – {P},返回第二步 ;
（ 2）,存在某一个多边形 Q，使 Zmax(P) > Zmin (Q),
需进一步判别：
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
A）若 P,Q的投影 P’,Q’ 的包围盒不相交（图 a），
则 P,Q在表中的次序不重要，令 L = L – {P},
返回 step 2;否则进行下一步。
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
B）若 P的所有顶点位于 Q所在平面的不可见的一侧 (图 b)，则 P,Q关系正确，令 L = L – {P},
返回 step 2;否则进行下一步。
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
C）若 Q的所有顶点位于 P所在平面的可见的一侧
(图 c)，则 P,Q关系正确，令 L = L – {P},返回 step 2;否则进行下一步。
浙江大学信息学院 计算机图形学画家算法（列表优先算法）
D） 对 P,Q投影 P’,Q’ 求交，若 P’,Q’ 不相交 (图 d)，则
P,Q在表中的次序不重要，令 L = L – {P},返回 step
2;否则在它们所相交的区域中任取一点，计算 P,Q在该点的深度值，如果 P的深度小，则 P,Q关系正确，令 L =
L – {P},返回 step 2;否则交换 P,Q,返回 step 3.
浙江大学信息学院 计算机图形学画家算法
本算法不能处理的情况：
多边形循环遮挡多边形相互穿透解决办法：分割成两个浙江大学信息学院 计算机图形学
Z-Buffer算法
由来：
帧缓冲器 – 保 存各像素颜色值
Z缓冲器 --保 存各像素处物体深度值
Z缓冲器中的单元与帧缓冲器中的单元一一对应屏幕 帧缓冲器 Z缓 冲器每个单元存放对应象素的颜色值每个单元存放对应象素的深度值浙江大学信息学院 计算机图形学
Z-Buffer算法思想,先将 Z缓冲器中个单元的初始值置为最小值。当要改变某个像素的颜色值时，首先检查当前多边形的深度值是否大于该像素原来的深度值（保存在该像素所对应的 Z缓冲器的单元中），如果大于，说明当前多边形更靠近观察点，用它的颜色替换像素原来的颜色；否则说明在当前像素处，当前多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色值不改变。
浙江大学信息学院 计算机图形学
Z-Buffer算法 -算法描述
{ 帧缓存全置为背景色深度缓存全置为最小 Z值
for(每一个多边形 )
{ for(该多边形所覆盖的每个象素 (x,y) )
{ 计算该多边形在该象素的深度值 Z(x,y);
if(Z(x,y)大于 Z缓存在 (x,y)的值 )
{ 把 Z(x,y)存入 Z缓存中 (x,y)处把多边形在 (x,y)处的颜色值存入帧缓存的 (x,y)处
}
}
}
}
需要计算的像素深度值次数
=多边形个数 *多边形平均占据的像素个数浙江大学信息学院 计算机图形学
Z-Buffer算法
Z缓冲器算法是所有图像空间算法中最简单的一种隐藏面消除算法。它 在象素级上以近物取代远物，与形体在屏幕上的出现顺序无关。
优点,1）简单稳定，利于硬件实现
2） 不需要整个场景的几何数据
缺点,1）需要一个额外的 Z缓冲器
2）在每个多边形占据的每个像素处都要计算深度值，计算量大浙江大学信息学院 计算机图形学
Z-Buffer算法 -改进算法
只用一个深度缓存变量 zb的改进算法。
– 一般认为,Z-Buffer算法需要开一个与图象大小相等的缓存数组 ZB，实际上，可以改进算法，只用一个深度缓存变量 zb。
浙江大学信息学院 计算机图形学
Z-Buffer算法 -改进算法过程
{ 帧缓存全置为背景色
for(屏幕上的每个象素 (i,j))
{ 深度缓存变量 zb置最小值 MinValue
for(多面体上的每个多边形 Pk)
{ if(象素点 (i,j)在 pk的投影多边形之内 )
{ 计算 Pk在 (i,j)处的深度值 depth;
if(depth大于 zb)
{ zb = depth;
indexp = k; }
}
}
}
if(zb != MinValue)
在交点 (i,j) 处用多边形 Pindexp的颜色显示
}
}
浙江大学信息学院 计算机图形学
Z-Buffer算法 -改进算法
– 关键问题：判断象素点 (i,j)是否在多边形
Pk的投影多边形之内
– 计算多边形 Pk在点（ i,j）处的深度。设多边形 Pk的平面方程为,0 dczbyax
c
dbjaide pt h
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
由来,Z缓冲器算法中所需要的 Z缓冲器容量较大，
为克服这个缺点可以将整个绘图区域分割成若干个小区域，然后一个区域一个区域地显示，这样 Z缓冲器的单元数只要等于一个区域内像素的个数就可以了。
如果将小区域取成屏幕上的扫描线，就得到 扫描线 Z
缓冲器算法。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
算法思想,
– 在处理当前扫描线时，开一个一维数组作为当前扫描线的 Z-buffer。首先 找出与当前扫描线相关的多边形，以及每个多边形中相关的边对 。
– 对每一个边对之间的小区间上的各象素，计算深度，并与 Z-buffer中的值比较，找出各象素处可见平面。
– 写帧缓存。采用增量算法计算深度。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
for ( v= 0;v<vmax;v++)
{ for (u= 0; u<umax; u++)
{ 将帧缓冲器的第 (u,v)单元置为背景色；
将 Z缓冲器的第 u单元置为最小值 }
for (每个多边形）
{ 求出多边形在投影平面上的投影与当前扫描线的相交区间
for （该区间内的每个像素 (u,v) ）
{ 计算多边形在该像素处的深度值 d；
if (d > Z缓冲器的第 u单元的值）
{ 置帧缓冲器的第 (u,v)单元值为当前多边形颜色；
置 Z缓冲器的第 u单元值为 d; }
}
}
//处理下一条扫描线
}
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
改进之一：将窗口分割成扫描线
Z缓冲器的单元数只要等于一条扫描线内像素的个数就可以了。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
改进之二：采用多边形分类表、活化多边形表避免 多边形 与扫描线的盲目求交浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -多边形分类表
多边形分类表（ PT）：对多边形进行分类的一维数组，长度等于绘图窗口内扫描线的数目。若一个多边形在投影平面上的投影的最小 v坐标为 v，则它属于第 v类。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -活化多边形表
活化多边形表
（ APL）：记录投影与当前扫描线相交的多边形。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -多边形
其中，多边形的数据结构如下：
a,b,c,d：多边形所在平面方程
f(u,v,n)=au+bv+cn+d=0的系数。
color:多边形的颜色
vmax:多边形在投影平面上的投影的最大
v坐标值。
PI：多边形的序号
nextP：指向下一个多边形结构的指针浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
改进之三：利用边、边的分类表、
边对、活化边对表避免 边 与扫描线的盲目求交浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -边数据结构
边：用来记录多边形的一条边，其中
vmax：边的投影的上端点的 v坐标。
u：边的下端点的 u坐标
n：边的下端点的 n坐标
Du：在该边上 v值增加一个单位时,u坐标的变化量 D
nextE：指向下一条边结构的指针。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -边的分类表
边的分类表（ ET）：当一个多边形 进入活化多边形表时,需为其建立一个边分类表（ ET）。这里,ET与其在扫描转换多边形的扫描线算法中的含义相同，是对多边形的非水平边进行分类的一维数组，长度等于绘图窗口内扫描线的数目。若一条边在投影平面上的投影的下端点的 v坐标为 v，则将该边归为第 v类。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -边对
边对：在一条扫描线上,同一多边形的相邻两条边构成一个边对 。
边对中包含了如下信息：
ul,边对的左侧边与扫描交点的 u坐标
Dul,当沿左侧边 v坐标递增一个像素时,u坐标的增量
vlmax,左侧边投影的上端点的 v坐标。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -边对
ur,边对的右侧边与扫描交点的 x坐标
Dur,当沿右侧边 v坐标递增一个像素时,u坐标的增量
vrmax,右侧边投影的上端点的 v坐标 。
nl,左侧边与扫描线交点的 n坐标
PI,多边形的序号浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -边对
Dnu,当沿扫描线 u递增一个像素时，多边形所在平面
n坐标的增量,对方程 au+bv+cn+d=0来说,Dnu =-a/c
Dnv,当沿扫描线 v递增一个像素时，多边形所在平面
n坐标的增量，类似,Dnv =-b/c (c!=0)
nextEP:指向下一个边对结构的指针。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法 -活化边表对
活化边表对（ AEPL）：记录了活化多边形表中与当前扫描线相交的边对，边对在 AEPL中的顺序无关紧要。
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
改进之四：利用连贯性计算深度
– 水平方向,当沿扫描线 u递增一个像素时，多边形所在平面 n坐标的增量,对方程 au+bv+cn+d=0来说,Dnu =-a/c
– 竖直方向
Dnv,当沿扫描线 v递增一个像素时，多边形所在平面 n坐标的增量,Dnv =-b/c
下一条扫描线与边对左侧边交点处的深度值：
nl=nl+DnuDul+Dnv
umax
vmax
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
1、建多边形分类表：对每一个多边形,若它 在投影平面上的投影的最小 v坐标为 v，则它属于第 v类。
2、置活化多边形表 APL为空，置活化边对表 AEPL为空。
3、对每条扫描线 v，执行下列步骤：
（ 1）置帧缓存器第 v行中的各单元为背景色。
（ 2）置 Z缓冲器各单元的值为最小的深度值。
（ 3）检查 PT(多边形分类表 )的第 v类是否非空，如果非空，将该类中的多边形取出加入 APL(活化多边形表 )中。
（ 4）对新加入 APL(活化多边形表 )中的多边形，为其建立边的分类表 ET。
（ 5）对新加入 APL (活化多边形表 )中的多边形，若它的
ET（边的分类表）中的第 v类非空，将其中的边配对插入 AEPL（活化边对表）中；
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
（ 6）对 AEPL（活化边对表）中的每一个边对，
执行下列步骤：
深度值 n=nl;
for （ u=ul;u<=ur;u=u+1 ）
{
if (n > Z缓冲器的第 u单元的值）
{ 置帧缓冲器的第 (u,v)单元值为当前多边形颜色；
置 Z缓冲器的第 u单元值为 n;
}
n=n+ Dnu;//计算下一个像素 (u+1,v)处多边形的深度值
}
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
（ 7）检查 APL (活化多边形表 ),删除那些满足 vmax=v的多边形，
释放该多边形的 ET，并从 AEPL中删除属于该多边形的边对。
（ 8）检查 AEPL（活化边对表）中的每一个边对，执行下列步骤：
A 若 vlmax=v或 vrmax=v，删除边对中的左侧边或右侧边。
B 若左侧边和右侧边都从边对中删除了，则从 AEPL（活化边对表）中删去该边对；若边对中仅有一条边被删去了，则从该边对所属的多边形的 ET中找到另一条边与余下的边配对，组成新的边对，加入 AEPL（活化边对表） ；
C 计算下一条扫描线与边对两边交点的 x坐标：
ul=ul+Dul； ur=ur+Dur
D 计算下一条扫描线与边对左侧边交点处的深度值：
nl=nl+DnuDul+Dnv
（ 9）将扫描线递增一个像素,v=v+1
浙江大学信息学院 计算机图形学扫描线 Z-buffer算法
缺点
– 在每一个被多边形覆盖像素处需要计算深度值
– 被多个多边形覆盖的像素需要多次计算深度值浙江大学信息学院 计算机图形学区间扫描线算法与 Z-Buffer算法相比，扫描线算法有了很大改进，比如所需的 Z-Buffer大大减小，
计算深度利用了面连贯性等；
缺点：每个像素处都计算深度值，甚至不止一次的计算，运算量仍然很大。
改进：在一条扫描线上，每个区间只计算一次深度，即区间扫描线算法，又称扫描线算法。
浙江大学信息学院 计算机图形学区间扫描线算法
基本思想,如下图，多边形 P1,P2的边界在投影平面上的投影将一条扫描线划分成若干个区间
[0,u1][u1,u2][u2,u3][u3,u4],[u4,umax],覆盖每个区间的有 0个,1个或多个多边形，但仅有一个可见。在区间上任取一个像素，计算该像素处各多边形（投影包含了该像素的多边形）的深度值，深度值最大者即为可见多边形，用它的颜色显示整个区间。
浙江大学信息学院 计算机图形学区间扫描线算法注意：该算法要求多边形不能相互贯穿，否则在同一区间上，多边形深度值的次序会发生变化。
如图：在区间 [u1,u2]上，多边形 P1的深度值大，
在区间 [u3,u4]上，多边形 P2的深度值大，而在区间 [u2,u3]上，两个多边形的深度值次序发生交替。
浙江大学信息学院 计算机图形学区间扫描线算法
数据结构
– 多边形分类表
– 活化多边形表
– 边的分类表
– 活化边表
类似于扫描线 Z-Buffer算法中的数据结构浙江大学信息学院 计算机图形学区间扫描线算法 -算法描述
for (绘图窗口内的每一条扫描线）
{ 求投影与当前扫描线相交的所有多边形求上述多边形中投影与当前扫描线相交的所 有边，将它们记录在活化边表 AEL中求 AEL中每条边的投影与扫描线的交点；
按交点的 u坐标将 AEL中各边从左到右排序,两两配对组成一个区间；
for （ AEL中每个区间）
{
求覆盖该区间的所有多边形，将它们记入活化多边形表 APL中；
在区间上任取一点，计算 APL中各多边形在该点的深度值，记深度最大者为 P；
用多边形 P的颜色填充该区间
}
}
浙江大学信息学院 计算机图形学区间扫描线算法
相比较扫描线 Z-Buffer算法而言，区间扫描线算法做了如下改进：
一、在一条扫描线上，以区间为单位确定多边形的可见性二、不再需要 Z-Buffer
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
由来,Z缓冲器算法与扫描线 Z缓冲器算法中都是将像素孤立来考虑，未利用相邻像素之间存在的属性的连贯性，即区域的连贯性，所以算法效率不高。实际上，可见多边形至少覆盖了绘图窗内的一块区域，这块区域由多边形在投影平面上的投影的边界围成。如果能将这类区域找出来，再用相应的多边形颜色加以填充则避免了在每个像素处计算深度值，消隐问题也就解决了。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
算法基本思路,首先将场景中的多边形投影到绘图窗口内（ 假设它为边长为 k的正方形 ），判断窗口是否 足够简单,若是则算法结束；否则将窗口进一步分为四块。对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。此时可能有多个多边形覆盖了该像素，计算它们的深度值，以最近的颜色显示该像素即可。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
何谓窗口足够简单？
存在下列情况之一即可称为窗口足够简单：
1）窗口为空，即多边形与窗口的关系是 分离 的；
2）窗口内仅含一个多边形，即有一个多边形与窗口的关系是 包含或相交 。此时先对多边形投影进行裁剪，
再对裁剪结果进行填充；
3）有一个多边形的投影 包围 了窗口，
并且它是最靠近观察点的，以该多边形颜色填充窗口。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
分离和包围多边形的判别：通常有 3种判别方法：
射线检查法，转角累计检查法和区域检查法。
这三种检查都假定相交的和内含的多边形已经事先判定了。
– 射线检查法：从窗口内的任意点，画一条射线至无穷远处，累计射线与多边形交点的个数。如果为偶数 (或为零 )，则此多边形与窗口分离；否则，此多边形包围窗口。但当射线通过多边形的顶点时，会得出错误结论。
(如左图 )解决方法有：当射线通过多边形的局部极值顶点时，记入两个交点；当射线通过多边形的非局部极值顶点时，记入一交点。
y
x
p6
p7
p8
p4 p
10
p9
p3
p1
p2
p5
y
x
p6
p4
p3
p1
p2
p5
p6
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
转角累计检查法,按顺时针方向或逆时针方向绕多边形依次累加多边形各边起点与终点对窗口内任意一点所张的夹角。按累计角度之和可以判定：
– 若角度之和等于 0，则表示多边形与窗口分离；
– 若角度之和等于 ± 360o·n，则表示多边形包围窗口
(n次 )。
多边形窗口 窗口多边形
α
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
区域检查法,1）区域编码
2）多边形顶点编码
3）多边形边的编码
4）多边形的编码浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
1、区域编码。窗口四条边所在直线将屏幕划分成 9个区域，对窗口以外的 8个区域按逆时针（或顺时针）进行编码，编码为 0~7。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
2、多边形顶点编码。多边形 v0v1…v n的顶点 vi的投影落在哪个区域，那个区域的编码便作为该顶点的编码，记为 Ii。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
3、多边形的编码。多边形的边 vivi+1的编码定义为 Di=Ii+1-Ii,i=0,1…n ；其中，令
In+1=I0，并且，当 Di >4时，取 Di = Di -8；
当 Di <4时，取 Di = Di +8；
当 Di =+/-4时，取该边与窗口边的延长线的交点将该边分为两段，对两段分别按上面的规则编码，再令 Di等于两者之和。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
4、多边形的编码。定义多边形的编码为其边的编码之和,则
D
D
8
0
0
0
n
i
i
n
i
i
当多边形包围窗口当窗口与多边形分离浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
例如,I0=5,I1=7,I2=3,D0=7-
5=2,D1=3-7=-4,D2=5-3=2,
因为 D1=-4,按第三步的处理规则，取边 v1v2与窗口上边所在直线的交点将 v1v2分为两段，两段的编码分别为 2，
2，从而 D2=4。最终求出多边形的编码为
D0+ D1+D2=2+4+2=8，因此，
该三角形包围窗口。
浙江大学信息学院 计算机图形学区域子分算法（ Warnock 算法）
如图,I0=1,I1=3,I2=7,D0=3-1=2,
D1=7-3=4,D2=1-7=-6。按第 3步处理规则，取 v1v2与窗口上边所在直线的交点 v’ 将其分为两段，两段的编码分别为 -2,-
2，从而 D1=-2+（ -2） =-4。而
D2=-6+8=2。最终求出多边形的编码为 D0+D1+D2=2+（ -4）
+2=0。
从而得出结论：多边形与窗口分离。
浙江大学信息学院 计算机图形学光线投射算法
算法思想：将通过绘图窗口内每一个像素的投影线与场景中的所有多边形求交。如果有交点，用深度值最大的交点（最近的）所属的多边形的颜色显示相应的像素；如果没有交点，说明没有多边形的投影覆盖此像素，用背景色显示即可。
浙江大学信息学院 计算机图形学光线投射算法 -算法描述
for ( v= 0;v<vmax;v++)
for (u= 0; u<umax; u++)
{ 形成通过像素 (u,v)的投影线；
for (场景中每一个多边形）
将投影线与多边形求交；
if (有交点）
以最近交点所属多边形的颜色显示像素 (u,v)
else
以背景色显示像素 (u,v)；
}
浙江大学信息学院 计算机图形学光线投射算法
基本问题
– 光线与物体表面的求交浙江大学信息学院 计算机图形学消隐的考虑
选择不同的消隐算法消隐问题有不同的算法，有些算法要求速度快，有些要求图形的真实度高。例如，快速消隐算法可用于实时模拟如飞行模拟等；具有高度真实感图形的消隐算法可用于计算机动画等领域，所生成的图形一般具有连续色调，并能产生阴影、透明、表面纹理及反射、
折射等视觉效果。不过这类算法比较慢。产生一幅图可能需要几分钟甚至几小时。所以，在进行消隐算法的设计时，应在计算速度和图形细节之间进行权衡，
任何一种算法都不能兼顾两者。
浙江大学信息学院 计算机图形学消隐的考虑
消隐算法的实现空间消隐算法可以在物体空间或图像空间中实现。
物体空间算法是在定义物体的坐标系中实现的，而图像空间算法是在对象显示的屏幕坐标系中实现的。
物体空间算法以尽可能高的精度完成几何计算，所以可以把图像放大许多倍而不致损害其准确性，但是图像空间算法只能以与显示屏的分辨率相适应的精度来完成计算，所以其图像的放大效果较差。
这两类算法的性能特性也是不同的。物体空间算法所需的计算时间随场量中物体的个数而增加，而图像空间的计算时间则随图像中可见部分的复杂程度而增加。
