（一）
苏 小 红
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机学院 苏小红 2
真实感图形绘制流程
场景造型
取景变换
背面剔除
视域四棱锥裁剪
透视变换
隐面消除、场景造型
光亮度计算
扫描转换、场景造型
哈尔滨工业大学计算机学院 苏小红 3
取景变换（ 1/5）
场景坐标系
? 场景的 局部 坐标系
完成物体的造型
? 场景的 世界 坐标系（整体坐标系）
放入待绘制的场景，定义物体之间的相互位置
观察坐标系
? 也称 摄像机坐标系,或者 视点坐标系
? 完成取景变换所需建立的第一个坐标系
哈尔滨工业大学计算机学院 苏小红 4
取景变换（ 2/5）
建立观察坐标系的步骤
? 确定 观察参考点,即 视点位置
可以设在任何位置
通常选在靠近或在物体的表面
将视点位置取为视点坐标系的原点
? 确定 观察方向,即 视线方向
一般取深度坐标轴，即 ze轴的正向
为简便起见，设为总是指向场景坐标系的原点
? 确定 观察平面,即 视平面位置
一般取过视点且垂直于视线方向的平面，即 xeye平面
哈尔滨工业大学计算机学院 苏小红 5
取景变换（ 3/5）
场景坐标系
? 一般取 右手 坐标系
观察坐标系
? 通常取 左手 坐标系
符合人们的观察习惯 xw
zw
yw
ze
xeye
视点 E
观察坐标系为左手坐标系
场景坐标系为右手坐标系
O
哈尔滨工业大学计算机学院 苏小红 6
取景变换（ 4/5）
将物体投影到观察平面之前
? 必须将场景坐标系中的点转换到观察坐标系中
这一过程称为 取景变换,也称 视向变换
? 包括平移和旋转的一系列几何变换的级联
取景变换矩阵
? ? ? ? Vzyxzyx wwweee ?? 11
哈尔滨工业大学计算机学院 苏小红 7
取景变换（ 5/5）
场景坐标系原点平移
到视点位置 E
绕 xe轴逆时针旋转 90o
绕 ye轴顺时针旋转 Ψ角
绕 xe轴逆时针旋转 θ
角
调整 x轴指向
? 对 x轴作对称变换
xw
zw
yw
ze
xe
ye
E
O
Cx
Cy
Cz
Ψ
xw
zw
yw
ze
xe
yeE
O
Cx
Cy
Cz
90o
xw
zw
yw
ze x
e
ye
E
O
Cx C
y
Cz
xw
zw
yw
ze
xe
ye
E
O
Cx
Cy
Cz
Ψ
θ
θ
哈尔滨工业大学计算机学院 苏小红 8
消隐算法
按实现方式不同分为两大类,
? 景物空间 （ object space） 消隐算法
直接在视点坐标系中确定视点不可见的表面区域
将它们表达成同原表面一致的数据结构
侧重于景中各物体之间的几何关系
? 图像空间 （ image space）消隐算法
在投影屏幕上，以屏幕像素为采样单位，确定投影于
每一像素的可见景物表面区域
将其颜色作为该像素的显示光亮度
侧重于向屏幕投影后形成的图像
哈尔滨工业大学计算机学院 苏小红 9
背面剔除算法
背面剔除算法
法向向量 N
视线向量 V
法向向量 N
法向向量 N
<90°
<90°
可见
可见
不可见
>90°
VN ???c o s
哈尔滨工业大学计算机学院 苏小红 10
隐藏面的消除 - Roberts算法 （ 1/9）
Roberts算法
景物空间消隐算法
1963年,Roberts于 MIT提出
哈尔滨工业大学计算机学院 苏小红 11
隐藏面的消除 - Roberts算法 （ 2/9）
基本思想
? 消除被物体自身遮挡的边和面
? 再用每个物体留下的边与其它物体比较
适用范围
? 凸体
凹体怎么办？
? 分解成若干凸体的组合
哈尔滨工业大学计算机学院 苏小红 12
隐藏面的消除 - Roberts算法 （ 3/9）
体矩阵
平面方程 ax+by+cz+d=0
? ? 01 ?
?
?
?
?
?
?
?
?
?
?
?
?
d
c
b
a
zyx
? ?? ? 01 ?TPzyx
? ?dcbaP ?
?
?
?
?
?
?
?
?
?
?
?
?
?
n
n
n
n
ddd
ccc
bbb
aaa
V
...
...
...
...
21
21
21
21
哈尔滨工业大学计算机学院 苏小红 13
隐藏面的消除 - Roberts算法 （ 4/9）
求平面方程 ax+by+cz+d=0的系
数
? 利用 不共线三点坐标
? 利用平面的 法向量
平面法向量,n=ai+bj+ck
d=-(ax1+by1+cz1)
? 利用 Martin Newell方法
?
?
??? n
i
jiji zzyya
1
))((
?
?
??? n
i
jiji xxzzb
1
))((
?
?
??? n
i
jiji yyxxc
1
))((
哈尔滨工业大学计算机学院 苏小红 14
隐藏面的消除 - Roberts算法 （ 5/9）
已知,S=[x y z 1],P=[a b c d]
? 若 S在平面上
则 S?P=0
? 若点 S不在平面上
则点积的正负号标识点在平面的哪一侧
约定：
? 若点 S在 体内一侧
则 S?P>0
? 若点 S在 体外一侧
则 S?P<0
哈尔滨工业大学计算机学院 苏小红 15
隐藏面的消除 - Roberts算法 （ 6/9）
体矩阵不一定保证体内点都满足 S?P>0
如何得到正确的体矩阵？
对体矩阵 V进行校正
? 在体内找一 试验点 S
若某平面方程系数 P与 S的点积符号为负
则将该方程系数均乘以 -1
哈尔滨工业大学计算机学院 苏小红 16
隐藏面的消除 - Roberts算法 （ 7/9）
自隐藏面的判别
假设
? 视点,位于 z轴正向的无穷远处
? 视线方向, z轴负向的无穷远点
E=[0 0 -1 0]
用 E作为试验点
判定一平面是自隐藏面的条件
? E?V<0
? 点积值为负，表示 E位于这些平面的外侧
哈尔滨工业大学计算机学院 苏小红 17
隐藏面的消除 - Roberts算法 （ 8/9）
y
z
x
③
④
② ①
⑤
⑥
?
?
?
?
?
?
?
?
?
?
?
?
???
?
2/12/12/12/12/12/1
110000
001100
000011
V
① ② ③ ④ ⑤ ⑥
?
?
?
?
?
?
?
?
?
?
?
?
???
?
11111
22000
002200
000022
① ② ③ ④ ⑤ ⑥
体内试验点 ? ? ? ?411114/14/14/1 ??S
? ?626262 ????? VS
正确的体矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
111111
220000
002200
000022
V
① ② ③ ④ ⑤ ⑥
哈尔滨工业大学计算机学院 苏小红 18
隐藏面的消除 - Roberts算法 （ 9/9）
y
z
x
③
④
② ①
⑤
⑥
x
-z
物体
内
外
内①②
⑥
⑤
负无穷远点 E=[00-1 0] ?
视线方向
视点位于正无穷远点 E=[00 1 0]
无限延伸平面
用 E=[0 0 -1 0]作为体内试验点
? ?220000 ??? VE
哈尔滨工业大学计算机学院 苏小红 19
隐藏面的消除 -画家算法 （ 1/3）
画家算法
1972年 M.E.Newell
受画家由远至近作画的启发
景物空间消隐算法
哈尔滨工业大学计算机学院 苏小红 20
隐藏面的消除 -画家算法 （ 2/3）
基本步骤
? 生成深度优先级队列
据视点距离 远 的多边形优先级低，排在队列的前端
据视点距离 近 的多边形优先级高，排在队列的后端
? 从队列中依次取出多边形,计算其表面光亮度
? 写入帧缓冲器
? 直到队列中所有多边形的光亮度都计算完毕，
并写入帧缓冲器
哈尔滨工业大学计算机学院 苏小红 21
隐藏面的消除 -画家算法 （ 3/3）
优点,
? 透明或半透明物体
? 图形的 动态显示
飞行训练模拟器中显示飞机着陆时的情景
场景中的物体是不变的,只是视点在变化
? 只要事先把不同视点的景物的优先级队列算出
? 再实时地采用画家算法来显示图形
? 就可以实现图形的快速消隐与显示
哈尔滨工业大学计算机学院 苏小红 22
隐藏面消除 -Weiler-Atherton算法 （ 1/3）
Weiler-Atherton算法
? 景物空间消隐算法
? 基于 Weiler-Atherton多边形裁剪操作
哈尔滨工业大学计算机学院 苏小红 23
隐藏面消除 -Weiler-Atherton算法 （ 2/3）
基本步骤
1)深度预排序，形成 景物多边形表
将变换到屏幕坐标系中的景物表面
按各顶点的 z最小值进行排序
2)当前具有 最大 z值 的景物表面作为裁剪多边形 CP
深度最大、离视点最近
3)用 CP对景物多边形表中排在后面的表面进行 裁剪
产生内部多边形 Pin和外部多边形 Pout
裁剪多边形将主多边形
裁剪为内部多边形和外部多边形
B1 B2
裁剪多边形 Pc 主多边形 Ps
哈尔滨工业大学计算机学院 苏小红 24
隐藏面消除 -Weiler-Atherton算法 （ 3/3）
4)比较 Pc与 Pin的深度，检查 Pc是否真正离视点最近
是，则 Pc为可见表面
不是，则取 Pin为新的 Pc，重复步骤 3)
5)将位于 Pc之外的景物表面组成外裁剪结果多边形表
取表中深度最大的表面为 Pc，重复步骤 3)
6)递归进行直到外裁剪结果多边形表为空时为止
哈尔滨工业大学计算机学院 苏小红 25
隐藏面的消除 - BSP树算法 （ 1/2）
BSP树算法
? Binary Space Partitioning
? 景物空间消隐算法
? 基于 BSP树，对景物表面进行二叉分类
? 与画家算法类似，景物多边形由远至近绘制
特别适合的场合
? 场景中 物体位置固定不变, 仅视点移动
哈尔滨工业大学计算机学院 苏小红 26
隐藏面的消除 -BSP树算法 （ 2/2）
基本步骤
? 选一剖分平面 P1，将场景空间分割成
两个半空间
? 剖分结果表示为一棵 BSP树
叶节点,景物
左分支,位于剖分平面前面的景物
右分支,位于剖分平面后面的景物
? 依据视点位置，对子空间进行分类
包含视点的子空间标识为,front”
另一侧子空间标识为,back”
? 递归搜索 该 BSP树，优先绘制标识为
,back”的子空间中所含的景物
Bfront
front
back
back
A
C
D
P1
P2 P2
front front
front
back back
back
A C DB
哈尔滨工业大学计算机学院 苏小红 27
隐藏面消除 -深度缓冲器算法 （ 1/8）
深度缓冲器算法
? Depth— buffer algorithm
? 图像空间消隐算法
? 1975年, Catmull提出
哈尔滨工业大学计算机学院 苏小红 28
隐藏面消除 -深度缓冲器算法 （ 2/8）
基本思想
? 将投影到显示屏上的每一个象素所对应的多边形表
面的深度进行比较
? 取最靠近视点的表面的属性值作为该像素的属性值
用 Z— buffer记录该表面在该像素点的 深度
用 frame— buffer记录该表面在该像素点的 颜色或亮度值
哈尔滨工业大学计算机学院 苏小红 29
隐藏面消除 -深度缓冲器算法 （ 3/8）
深度缓冲器
? 帧缓冲器的扩充
也称 Z-Buffer算法
哈尔滨工业大学计算机学院 苏小红 30
隐藏面消除 -深度缓冲器算法 （ 4/8）
流程：
for（场景中的每一个多边形）
{
扫描转换该多边形；
for（多边形所覆盖的每一个像素点 (x,y)）
{
计算多边形在该像素点的深度值 z(x,y)；
if（ z(x,y) > Z-buf中对应此像素点 (x,y)的 z值）
{
把多边形在 (x,y)处的深度值 z(x,y)存入 Z-buf中的 (x,y)处；
把多边形在 (x,y)处的亮度值存入 f-buf中的 (x,y)处；
}
}
}
当所有的多边形都处理完后，帧缓冲器中的内容即为消除隐藏面后的图像
哈尔滨工业大学计算机学院 苏小红 31
隐藏面消除 -深度缓冲器算法 （ 5/8）
优点
? 简单
在象素级上以近物代替远物，易于消除隐藏面，并准确显示复杂
曲面之间的交线。
? 计算量呈线性复杂度
场景中景物表面采样点的数目
? 无需对各景物表面片作深度预排序
景物表面上的可见点可按任意次序写入深度缓冲器和帧缓冲器
? 易于硬件实现
图形工作站上配置由硬件实现的深度缓冲器算法
很多微型机上都装有基于深度缓冲器算法的图形加速卡
哈尔滨工业大学计算机学院 苏小红 32
隐藏面消除 -深度缓冲器算法 （ 6/8）
缺点
? 需要很大的存储空间
象素数目为 500× 500，深度值采用浮点类型（ 4字节）
除刷新缓存外，还需 500*500*4=1M字节的额外存储空间
? 在实现反走样、处理透明和半透明等效果方面存在
困难，并由此会产生巨大的处理时间开销
由于在帧缓冲器内的同一象素点上可见表面的写入顺序
是不确定的，所以可能导致画面上的局部错误。
哈尔滨工业大学计算机学院 苏小红 33
隐藏面消除 -深度缓冲器算法 （ 7/8）
改进一：减少需要相对测试的多边形平面
数
? 最小最大测试
不重叠,不可能互相遮蔽 测试无确定结果 对每条边进行 最小最大 测试
Xmin
Xmax
哈尔滨工业大学计算机学院 苏小红 34
隐藏面消除 -深度缓冲器算法 （ 8/8）
改进二：利用连贯性计算深度
? 水平方向
? 竖直方向
改进三：降低对存储空间的需求
? 图像空间划分为 4,16甚至更多的子正方形或条状区域
? 在最小情况下，只对应一条扫描线的深度缓冲器
扫描线相关算法
哈尔滨工业大学计算机学院 苏小红 35
隐藏面的消除 -扫描线相关算法（ 1/3）
扫描线相关算法
? 按扫描线顺序处理一帧画面
? 在 扫描平面 （ ZOX平面）上解决消隐问题
由视点和扫描线所决定
深度缓冲器算法的一维版本
? 深度缓冲器所需的存储空间
屏幕水平分辨率 × 每个深度值所占的存储位数
哈尔滨工业大学计算机学院 苏小红 36
隐藏面的消除for (每条扫描线 ){
将扫描线帧缓冲器 f_buf置成背景色；
将扫描线深度缓冲器 Z_buf置成最小值；
for (每个多边形 )
{
求出该多边形与当前扫描线的相交区间；
for (相交区间内每个象素点 (x,y))
{
计算多边形在该处的深度值 z；
if (多边形在该处的深度值 z > Z_buf在该处的值 )
{
用多边形在该处的深度值 z取代 Z_buf在该处的值；
用多边形在该处的亮度值取代 f_buf在该处的值；
}
}
}
用 f_buf的内容显示当前扫描线；
}
哈尔滨工业大学计算机学院 苏小红 37
隐藏面的消除 -扫描线相关算法（ 3/3）
缺点
? 在每一个被多边形覆盖像素处需要计算深度值
? 被多个多边形覆盖的像素需要多次计算深度值
改进
? 在一条扫描线上，以区间为单位确定多边形的可见性
哈尔滨工业大学计算机学院 苏小红 38
隐藏面的消除 - Warnock算法 （ 1/4）
Warnock算法
? 图像空间消隐算
法
? 区域的连贯性
? 也称 区域细分
area-subdivision
? 实质
分而治之
哈尔滨工业大学计算机学院 苏小红 39
隐藏面的消除 - Warnock算法 （ 2/4）
基本思想
? 观察整个窗口区域
? 判别窗口是否单纯
窗口内 无任何可见物体
窗口 已被一个可见面片完全充满
? 将非单纯的窗口四等分为四个子窗口
? 对每个子窗口再进一步判别是否是单纯的
? 直到窗口单纯或窗口边长已缩至一个象素点为止
即使 1024× 1024分辨率
? 视图被细分 10次后，也能使每个子窗口覆盖一个像素
哈尔滨工业大学计算机学院 苏小红 40
隐藏面的消除 - Warnock算法 （ 3/4）
关键步骤
分析观察窗口与所有投影后多边形面片之间的关系
分离 内含 相交 包围
—— 判别窗口是否单纯
哈尔滨工业大学计算机学院 苏小红 41
隐藏面的消除 - Warnock算法 （ 4/4）
基本步骤
对每个窗口判断
? 与多边形 分离
? 仅 包含 一个多边形
? 与一个多边形 相交
? 被一个多边形所 包围 且窗口内无其它多边形
? 至少被一个多边形所包围，且此多边形 距离
视点最近
否则继续细分窗口，并重复以上测试
哈尔滨工业大学计算机学院 苏小红 42
光线投射算法（ 1/4）
Ray Casting
? Appel提出
? 建立在几何光学基础之上
? 对于包含曲面、特别是球面的场景效率高
哈尔滨工业大学计算机学院 苏小红 43
光线投射算法（ 2/4）
基本思想
? 观察者之所以能看见景物
光源发出的光照射到物体上的结果
其中一部分光到达人的眼睛引起视觉
? 到达观察者眼中的光
由物体表面反射
通过表面折射或透射
? 若 从光源出发跟踪光线
则只有极少量的光能到达观察者的眼睛
效率低
? 从视点或像素出发，仅对穿过像素的光线反向跟踪
? 当光线路径到达一个可见的不透明物体的表面时停止追踪
哈尔滨工业大学计算机学院 苏小红 44
将景物通过 透视投影变换 到图像空间
反向跟踪一条穿过像素点的光线
? 决定它与场景中的哪一景物表面相交
交点按深度排序
? 需求出该光线与景物表面的所有可能的交点
具有 最大 z值的交点 对应的面就是屏幕上该像素对应的 可见面
? 离视点最近
? 该像素处的显示值由相应物体的属性决定
对屏幕上所有像素都进行如上处理后，算法结束
视点
光线
投影面上的像素位置
物体
假设
? 视点 位于 z轴正向
? 投影平面 （屏幕）垂直于 z轴
反向跟踪一条穿过像素点的光线
光线投射算法（ 3/4）
哈尔滨工业大学计算机学院 苏小红 45
光线投射算法（ 4/4）
光线投射算法
{
for(y=0;y<=ymax;y++)
for(x=0;x<=xmax;x++)
{ 形成通过像素 (x,y)的投影线；
for(场景中的每一个多边形）
将投影线与多边形求交；
if(有交点 )
以最近交点所属多边形的颜色显示像素 (x,y);
else
以背景颜色显示像素 (x,y);
}
}
哈尔滨工业大学计算机学院 苏小红 46
阴影处理 （ 1/6）
判断视点、光源以及物体之间的位置关系
? 从视点可见，从光源也可见
? 从视点可见，从光源不可见
? 相对于部分光源可见，相对于另一部分光源不可见
哈尔滨工业大学计算机学院 苏小红 47
阴影处理（ 2/6）
当观察方向与光源方向重合时
? 观察者看不到任何阴影
? 可以不进行阴影测试
当观察方向与光源方向不一致
或光源多且光源体制比较复杂时
? 必须进行阴影处理
哈尔滨工业大学计算机学院 苏小红 48
阴影处理（ 3/6）
阴影由两部分组成
? 本影
任何光线都照不到的区域
呈现为全黑的轮廓分明的区域
? 半影
可接收到分布光源照射的部分光线的区域
通常位于本影周围，呈现为半明半暗的区域
本 半
区 影 区 影 区 影
无
光源
面光源照射形成的本影与半影
哈尔滨工业大学计算机学院 苏小红 49
阴影处理（ 4/6）
点光源
? 只能产生本影
位于有限距离内的分布光源
? 可同时产生本影和半影
需要的阴影计算量大
哈尔滨工业大学计算机学院 苏小红 50
阴影处理（ 5/6）
计算阴影的过程
相当于两次消隐过程
? 对每个光源进行消隐
? 对视点的位置进行消隐
好处
? 改变视点位置,第一次消隐过程不必重新计算
哈尔滨工业大学计算机学院 苏小红 51
阴影处理（ 6/6）
产生的本影包括
? 自身阴影面
假设视点在点光源位置，用 背面剔除 的方法求出
? 投射阴影
从光源向物体的所有可见面投射光线
将这些面投影到场景中得到投影面
将这些投影面与场景中其它平面求交线，可得阴影多边形
自身阴影
投射阴影
苏 小 红
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机学院 苏小红 2
真实感图形绘制流程
场景造型
取景变换
背面剔除
视域四棱锥裁剪
透视变换
隐面消除、场景造型
光亮度计算
扫描转换、场景造型
哈尔滨工业大学计算机学院 苏小红 3
取景变换（ 1/5）
场景坐标系
? 场景的 局部 坐标系
完成物体的造型
? 场景的 世界 坐标系（整体坐标系）
放入待绘制的场景，定义物体之间的相互位置
观察坐标系
? 也称 摄像机坐标系,或者 视点坐标系
? 完成取景变换所需建立的第一个坐标系
哈尔滨工业大学计算机学院 苏小红 4
取景变换（ 2/5）
建立观察坐标系的步骤
? 确定 观察参考点,即 视点位置
可以设在任何位置
通常选在靠近或在物体的表面
将视点位置取为视点坐标系的原点
? 确定 观察方向,即 视线方向
一般取深度坐标轴，即 ze轴的正向
为简便起见，设为总是指向场景坐标系的原点
? 确定 观察平面,即 视平面位置
一般取过视点且垂直于视线方向的平面，即 xeye平面
哈尔滨工业大学计算机学院 苏小红 5
取景变换（ 3/5）
场景坐标系
? 一般取 右手 坐标系
观察坐标系
? 通常取 左手 坐标系
符合人们的观察习惯 xw
zw
yw
ze
xeye
视点 E
观察坐标系为左手坐标系
场景坐标系为右手坐标系
O
哈尔滨工业大学计算机学院 苏小红 6
取景变换（ 4/5）
将物体投影到观察平面之前
? 必须将场景坐标系中的点转换到观察坐标系中
这一过程称为 取景变换,也称 视向变换
? 包括平移和旋转的一系列几何变换的级联
取景变换矩阵
? ? ? ? Vzyxzyx wwweee ?? 11
哈尔滨工业大学计算机学院 苏小红 7
取景变换（ 5/5）
场景坐标系原点平移
到视点位置 E
绕 xe轴逆时针旋转 90o
绕 ye轴顺时针旋转 Ψ角
绕 xe轴逆时针旋转 θ
角
调整 x轴指向
? 对 x轴作对称变换
xw
zw
yw
ze
xe
ye
E
O
Cx
Cy
Cz
Ψ
xw
zw
yw
ze
xe
yeE
O
Cx
Cy
Cz
90o
xw
zw
yw
ze x
e
ye
E
O
Cx C
y
Cz
xw
zw
yw
ze
xe
ye
E
O
Cx
Cy
Cz
Ψ
θ
θ
哈尔滨工业大学计算机学院 苏小红 8
消隐算法
按实现方式不同分为两大类,
? 景物空间 （ object space） 消隐算法
直接在视点坐标系中确定视点不可见的表面区域
将它们表达成同原表面一致的数据结构
侧重于景中各物体之间的几何关系
? 图像空间 （ image space）消隐算法
在投影屏幕上，以屏幕像素为采样单位，确定投影于
每一像素的可见景物表面区域
将其颜色作为该像素的显示光亮度
侧重于向屏幕投影后形成的图像
哈尔滨工业大学计算机学院 苏小红 9
背面剔除算法
背面剔除算法
法向向量 N
视线向量 V
法向向量 N
法向向量 N
<90°
<90°
可见
可见
不可见
>90°
VN ???c o s
哈尔滨工业大学计算机学院 苏小红 10
隐藏面的消除 - Roberts算法 （ 1/9）
Roberts算法
景物空间消隐算法
1963年,Roberts于 MIT提出
哈尔滨工业大学计算机学院 苏小红 11
隐藏面的消除 - Roberts算法 （ 2/9）
基本思想
? 消除被物体自身遮挡的边和面
? 再用每个物体留下的边与其它物体比较
适用范围
? 凸体
凹体怎么办？
? 分解成若干凸体的组合
哈尔滨工业大学计算机学院 苏小红 12
隐藏面的消除 - Roberts算法 （ 3/9）
体矩阵
平面方程 ax+by+cz+d=0
? ? 01 ?
?
?
?
?
?
?
?
?
?
?
?
?
d
c
b
a
zyx
? ?? ? 01 ?TPzyx
? ?dcbaP ?
?
?
?
?
?
?
?
?
?
?
?
?
?
n
n
n
n
ddd
ccc
bbb
aaa
V
...
...
...
...
21
21
21
21
哈尔滨工业大学计算机学院 苏小红 13
隐藏面的消除 - Roberts算法 （ 4/9）
求平面方程 ax+by+cz+d=0的系
数
? 利用 不共线三点坐标
? 利用平面的 法向量
平面法向量,n=ai+bj+ck
d=-(ax1+by1+cz1)
? 利用 Martin Newell方法
?
?
??? n
i
jiji zzyya
1
))((
?
?
??? n
i
jiji xxzzb
1
))((
?
?
??? n
i
jiji yyxxc
1
))((
哈尔滨工业大学计算机学院 苏小红 14
隐藏面的消除 - Roberts算法 （ 5/9）
已知,S=[x y z 1],P=[a b c d]
? 若 S在平面上
则 S?P=0
? 若点 S不在平面上
则点积的正负号标识点在平面的哪一侧
约定：
? 若点 S在 体内一侧
则 S?P>0
? 若点 S在 体外一侧
则 S?P<0
哈尔滨工业大学计算机学院 苏小红 15
隐藏面的消除 - Roberts算法 （ 6/9）
体矩阵不一定保证体内点都满足 S?P>0
如何得到正确的体矩阵？
对体矩阵 V进行校正
? 在体内找一 试验点 S
若某平面方程系数 P与 S的点积符号为负
则将该方程系数均乘以 -1
哈尔滨工业大学计算机学院 苏小红 16
隐藏面的消除 - Roberts算法 （ 7/9）
自隐藏面的判别
假设
? 视点,位于 z轴正向的无穷远处
? 视线方向, z轴负向的无穷远点
E=[0 0 -1 0]
用 E作为试验点
判定一平面是自隐藏面的条件
? E?V<0
? 点积值为负，表示 E位于这些平面的外侧
哈尔滨工业大学计算机学院 苏小红 17
隐藏面的消除 - Roberts算法 （ 8/9）
y
z
x
③
④
② ①
⑤
⑥
?
?
?
?
?
?
?
?
?
?
?
?
???
?
2/12/12/12/12/12/1
110000
001100
000011
V
① ② ③ ④ ⑤ ⑥
?
?
?
?
?
?
?
?
?
?
?
?
???
?
11111
22000
002200
000022
① ② ③ ④ ⑤ ⑥
体内试验点 ? ? ? ?411114/14/14/1 ??S
? ?626262 ????? VS
正确的体矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
111111
220000
002200
000022
V
① ② ③ ④ ⑤ ⑥
哈尔滨工业大学计算机学院 苏小红 18
隐藏面的消除 - Roberts算法 （ 9/9）
y
z
x
③
④
② ①
⑤
⑥
x
-z
物体
内
外
内①②
⑥
⑤
负无穷远点 E=[00-1 0] ?
视线方向
视点位于正无穷远点 E=[00 1 0]
无限延伸平面
用 E=[0 0 -1 0]作为体内试验点
? ?220000 ??? VE
哈尔滨工业大学计算机学院 苏小红 19
隐藏面的消除 -画家算法 （ 1/3）
画家算法
1972年 M.E.Newell
受画家由远至近作画的启发
景物空间消隐算法
哈尔滨工业大学计算机学院 苏小红 20
隐藏面的消除 -画家算法 （ 2/3）
基本步骤
? 生成深度优先级队列
据视点距离 远 的多边形优先级低，排在队列的前端
据视点距离 近 的多边形优先级高，排在队列的后端
? 从队列中依次取出多边形,计算其表面光亮度
? 写入帧缓冲器
? 直到队列中所有多边形的光亮度都计算完毕，
并写入帧缓冲器
哈尔滨工业大学计算机学院 苏小红 21
隐藏面的消除 -画家算法 （ 3/3）
优点,
? 透明或半透明物体
? 图形的 动态显示
飞行训练模拟器中显示飞机着陆时的情景
场景中的物体是不变的,只是视点在变化
? 只要事先把不同视点的景物的优先级队列算出
? 再实时地采用画家算法来显示图形
? 就可以实现图形的快速消隐与显示
哈尔滨工业大学计算机学院 苏小红 22
隐藏面消除 -Weiler-Atherton算法 （ 1/3）
Weiler-Atherton算法
? 景物空间消隐算法
? 基于 Weiler-Atherton多边形裁剪操作
哈尔滨工业大学计算机学院 苏小红 23
隐藏面消除 -Weiler-Atherton算法 （ 2/3）
基本步骤
1)深度预排序，形成 景物多边形表
将变换到屏幕坐标系中的景物表面
按各顶点的 z最小值进行排序
2)当前具有 最大 z值 的景物表面作为裁剪多边形 CP
深度最大、离视点最近
3)用 CP对景物多边形表中排在后面的表面进行 裁剪
产生内部多边形 Pin和外部多边形 Pout
裁剪多边形将主多边形
裁剪为内部多边形和外部多边形
B1 B2
裁剪多边形 Pc 主多边形 Ps
哈尔滨工业大学计算机学院 苏小红 24
隐藏面消除 -Weiler-Atherton算法 （ 3/3）
4)比较 Pc与 Pin的深度，检查 Pc是否真正离视点最近
是，则 Pc为可见表面
不是，则取 Pin为新的 Pc，重复步骤 3)
5)将位于 Pc之外的景物表面组成外裁剪结果多边形表
取表中深度最大的表面为 Pc，重复步骤 3)
6)递归进行直到外裁剪结果多边形表为空时为止
哈尔滨工业大学计算机学院 苏小红 25
隐藏面的消除 - BSP树算法 （ 1/2）
BSP树算法
? Binary Space Partitioning
? 景物空间消隐算法
? 基于 BSP树，对景物表面进行二叉分类
? 与画家算法类似，景物多边形由远至近绘制
特别适合的场合
? 场景中 物体位置固定不变, 仅视点移动
哈尔滨工业大学计算机学院 苏小红 26
隐藏面的消除 -BSP树算法 （ 2/2）
基本步骤
? 选一剖分平面 P1，将场景空间分割成
两个半空间
? 剖分结果表示为一棵 BSP树
叶节点,景物
左分支,位于剖分平面前面的景物
右分支,位于剖分平面后面的景物
? 依据视点位置，对子空间进行分类
包含视点的子空间标识为,front”
另一侧子空间标识为,back”
? 递归搜索 该 BSP树，优先绘制标识为
,back”的子空间中所含的景物
Bfront
front
back
back
A
C
D
P1
P2 P2
front front
front
back back
back
A C DB
哈尔滨工业大学计算机学院 苏小红 27
隐藏面消除 -深度缓冲器算法 （ 1/8）
深度缓冲器算法
? Depth— buffer algorithm
? 图像空间消隐算法
? 1975年, Catmull提出
哈尔滨工业大学计算机学院 苏小红 28
隐藏面消除 -深度缓冲器算法 （ 2/8）
基本思想
? 将投影到显示屏上的每一个象素所对应的多边形表
面的深度进行比较
? 取最靠近视点的表面的属性值作为该像素的属性值
用 Z— buffer记录该表面在该像素点的 深度
用 frame— buffer记录该表面在该像素点的 颜色或亮度值
哈尔滨工业大学计算机学院 苏小红 29
隐藏面消除 -深度缓冲器算法 （ 3/8）
深度缓冲器
? 帧缓冲器的扩充
也称 Z-Buffer算法
哈尔滨工业大学计算机学院 苏小红 30
隐藏面消除 -深度缓冲器算法 （ 4/8）
流程：
for（场景中的每一个多边形）
{
扫描转换该多边形；
for（多边形所覆盖的每一个像素点 (x,y)）
{
计算多边形在该像素点的深度值 z(x,y)；
if（ z(x,y) > Z-buf中对应此像素点 (x,y)的 z值）
{
把多边形在 (x,y)处的深度值 z(x,y)存入 Z-buf中的 (x,y)处；
把多边形在 (x,y)处的亮度值存入 f-buf中的 (x,y)处；
}
}
}
当所有的多边形都处理完后，帧缓冲器中的内容即为消除隐藏面后的图像
哈尔滨工业大学计算机学院 苏小红 31
隐藏面消除 -深度缓冲器算法 （ 5/8）
优点
? 简单
在象素级上以近物代替远物，易于消除隐藏面，并准确显示复杂
曲面之间的交线。
? 计算量呈线性复杂度
场景中景物表面采样点的数目
? 无需对各景物表面片作深度预排序
景物表面上的可见点可按任意次序写入深度缓冲器和帧缓冲器
? 易于硬件实现
图形工作站上配置由硬件实现的深度缓冲器算法
很多微型机上都装有基于深度缓冲器算法的图形加速卡
哈尔滨工业大学计算机学院 苏小红 32
隐藏面消除 -深度缓冲器算法 （ 6/8）
缺点
? 需要很大的存储空间
象素数目为 500× 500，深度值采用浮点类型（ 4字节）
除刷新缓存外，还需 500*500*4=1M字节的额外存储空间
? 在实现反走样、处理透明和半透明等效果方面存在
困难，并由此会产生巨大的处理时间开销
由于在帧缓冲器内的同一象素点上可见表面的写入顺序
是不确定的，所以可能导致画面上的局部错误。
哈尔滨工业大学计算机学院 苏小红 33
隐藏面消除 -深度缓冲器算法 （ 7/8）
改进一：减少需要相对测试的多边形平面
数
? 最小最大测试
不重叠,不可能互相遮蔽 测试无确定结果 对每条边进行 最小最大 测试
Xmin
Xmax
哈尔滨工业大学计算机学院 苏小红 34
隐藏面消除 -深度缓冲器算法 （ 8/8）
改进二：利用连贯性计算深度
? 水平方向
? 竖直方向
改进三：降低对存储空间的需求
? 图像空间划分为 4,16甚至更多的子正方形或条状区域
? 在最小情况下，只对应一条扫描线的深度缓冲器
扫描线相关算法
哈尔滨工业大学计算机学院 苏小红 35
隐藏面的消除 -扫描线相关算法（ 1/3）
扫描线相关算法
? 按扫描线顺序处理一帧画面
? 在 扫描平面 （ ZOX平面）上解决消隐问题
由视点和扫描线所决定
深度缓冲器算法的一维版本
? 深度缓冲器所需的存储空间
屏幕水平分辨率 × 每个深度值所占的存储位数
哈尔滨工业大学计算机学院 苏小红 36
隐藏面的消除for (每条扫描线 ){
将扫描线帧缓冲器 f_buf置成背景色；
将扫描线深度缓冲器 Z_buf置成最小值；
for (每个多边形 )
{
求出该多边形与当前扫描线的相交区间；
for (相交区间内每个象素点 (x,y))
{
计算多边形在该处的深度值 z；
if (多边形在该处的深度值 z > Z_buf在该处的值 )
{
用多边形在该处的深度值 z取代 Z_buf在该处的值；
用多边形在该处的亮度值取代 f_buf在该处的值；
}
}
}
用 f_buf的内容显示当前扫描线；
}
哈尔滨工业大学计算机学院 苏小红 37
隐藏面的消除 -扫描线相关算法（ 3/3）
缺点
? 在每一个被多边形覆盖像素处需要计算深度值
? 被多个多边形覆盖的像素需要多次计算深度值
改进
? 在一条扫描线上，以区间为单位确定多边形的可见性
哈尔滨工业大学计算机学院 苏小红 38
隐藏面的消除 - Warnock算法 （ 1/4）
Warnock算法
? 图像空间消隐算
法
? 区域的连贯性
? 也称 区域细分
area-subdivision
? 实质
分而治之
哈尔滨工业大学计算机学院 苏小红 39
隐藏面的消除 - Warnock算法 （ 2/4）
基本思想
? 观察整个窗口区域
? 判别窗口是否单纯
窗口内 无任何可见物体
窗口 已被一个可见面片完全充满
? 将非单纯的窗口四等分为四个子窗口
? 对每个子窗口再进一步判别是否是单纯的
? 直到窗口单纯或窗口边长已缩至一个象素点为止
即使 1024× 1024分辨率
? 视图被细分 10次后，也能使每个子窗口覆盖一个像素
哈尔滨工业大学计算机学院 苏小红 40
隐藏面的消除 - Warnock算法 （ 3/4）
关键步骤
分析观察窗口与所有投影后多边形面片之间的关系
分离 内含 相交 包围
—— 判别窗口是否单纯
哈尔滨工业大学计算机学院 苏小红 41
隐藏面的消除 - Warnock算法 （ 4/4）
基本步骤
对每个窗口判断
? 与多边形 分离
? 仅 包含 一个多边形
? 与一个多边形 相交
? 被一个多边形所 包围 且窗口内无其它多边形
? 至少被一个多边形所包围，且此多边形 距离
视点最近
否则继续细分窗口，并重复以上测试
哈尔滨工业大学计算机学院 苏小红 42
光线投射算法（ 1/4）
Ray Casting
? Appel提出
? 建立在几何光学基础之上
? 对于包含曲面、特别是球面的场景效率高
哈尔滨工业大学计算机学院 苏小红 43
光线投射算法（ 2/4）
基本思想
? 观察者之所以能看见景物
光源发出的光照射到物体上的结果
其中一部分光到达人的眼睛引起视觉
? 到达观察者眼中的光
由物体表面反射
通过表面折射或透射
? 若 从光源出发跟踪光线
则只有极少量的光能到达观察者的眼睛
效率低
? 从视点或像素出发，仅对穿过像素的光线反向跟踪
? 当光线路径到达一个可见的不透明物体的表面时停止追踪
哈尔滨工业大学计算机学院 苏小红 44
将景物通过 透视投影变换 到图像空间
反向跟踪一条穿过像素点的光线
? 决定它与场景中的哪一景物表面相交
交点按深度排序
? 需求出该光线与景物表面的所有可能的交点
具有 最大 z值的交点 对应的面就是屏幕上该像素对应的 可见面
? 离视点最近
? 该像素处的显示值由相应物体的属性决定
对屏幕上所有像素都进行如上处理后，算法结束
视点
光线
投影面上的像素位置
物体
假设
? 视点 位于 z轴正向
? 投影平面 （屏幕）垂直于 z轴
反向跟踪一条穿过像素点的光线
光线投射算法（ 3/4）
哈尔滨工业大学计算机学院 苏小红 45
光线投射算法（ 4/4）
光线投射算法
{
for(y=0;y<=ymax;y++)
for(x=0;x<=xmax;x++)
{ 形成通过像素 (x,y)的投影线；
for(场景中的每一个多边形）
将投影线与多边形求交；
if(有交点 )
以最近交点所属多边形的颜色显示像素 (x,y);
else
以背景颜色显示像素 (x,y);
}
}
哈尔滨工业大学计算机学院 苏小红 46
阴影处理 （ 1/6）
判断视点、光源以及物体之间的位置关系
? 从视点可见，从光源也可见
? 从视点可见，从光源不可见
? 相对于部分光源可见，相对于另一部分光源不可见
哈尔滨工业大学计算机学院 苏小红 47
阴影处理（ 2/6）
当观察方向与光源方向重合时
? 观察者看不到任何阴影
? 可以不进行阴影测试
当观察方向与光源方向不一致
或光源多且光源体制比较复杂时
? 必须进行阴影处理
哈尔滨工业大学计算机学院 苏小红 48
阴影处理（ 3/6）
阴影由两部分组成
? 本影
任何光线都照不到的区域
呈现为全黑的轮廓分明的区域
? 半影
可接收到分布光源照射的部分光线的区域
通常位于本影周围，呈现为半明半暗的区域
本 半
区 影 区 影 区 影
无
光源
面光源照射形成的本影与半影
哈尔滨工业大学计算机学院 苏小红 49
阴影处理（ 4/6）
点光源
? 只能产生本影
位于有限距离内的分布光源
? 可同时产生本影和半影
需要的阴影计算量大
哈尔滨工业大学计算机学院 苏小红 50
阴影处理（ 5/6）
计算阴影的过程
相当于两次消隐过程
? 对每个光源进行消隐
? 对视点的位置进行消隐
好处
? 改变视点位置,第一次消隐过程不必重新计算
哈尔滨工业大学计算机学院 苏小红 51
阴影处理（ 6/6）
产生的本影包括
? 自身阴影面
假设视点在点光源位置，用 背面剔除 的方法求出
? 投射阴影
从光源向物体的所有可见面投射光线
将这些面投影到场景中得到投影面
将这些投影面与场景中其它平面求交线，可得阴影多边形
自身阴影
投射阴影
