精华区文章阅读

发信人: Lerry (戒网·学习), 信区: Algorithm
标题: 三维图形的消隐算法分析
发信站: 哈工大紫丁香 (2001年11月20日20:48:06 星期二), 站内信件

三维图形的消隐算法分析
---- 摘要造型是计算机三维图形处理的基础，而消隐则是三
维造型的关键。本文剖析了当前在CAD 三维图形处理中最主要
的8 种物体空间消隐算法和4 种图象空间消隐算法。
---- 关键词造型、消隐、物体空间法、图象空间法
---- 分类号
---- 造型（modeling）是计算机三维图形处理的基础，而消除隐
藏面（hidden surface，简称消隐）则是三维造型的关键。所谓消
隐就是不画出即隐藏从当前观察点看不见的三维模型表面。
消隐算法的核心就是判断三维模型的表面是否可见。
---- 抽象来看，一种消隐算法可以看作一个五元组，即
HA = (I, O, D, P, S)
---- 其中，I 为要进行消隐处理的三维对象的集合；
---- O 为经过消隐处理的二维对象的集合；
---- D 为进行消隐处理时所采用的数据结构；
---- P 为进行消隐处理所需基本操作过程的集合，主要包括
分类、排序
三维坐标变换
透视投影变换
基本图形元素间的求交计算
两个区域重叠判断
点与区域的包含测试
面的朝向测试
---- S 为消隐策略，即规定P 中各基本操作过程被采用的先后
次序。
---- 因此，设计消隐算法时应考虑上述五个要素及它们之间
的相互关系。
---- 在计算机图形学中，为了简化算法，一般是利用多面体去
逼近曲面体，因此多面体的消隐算法是曲面体的基础。本文
的消隐算法讨论主要是基于多面体的消隐问题，对曲面体进
行多次多面体近似，对每一多面体运用多面体消隐算法就能
实现曲面体的消隐。
---- 基于B-rep 模型（Boundary Representative Model）和CSG 模型（Construc
tive Solid Geometry Model）的三维造型消隐算法可以分为两大类，
即物体空间法和图象空间法。物体空间法利用三维环境信息
或三维视图（主要使用三维观察坐标，有时也使用三维世界
坐标）来消除隐藏面，即根据空间中各物体三维模型的几何
关系，来判断哪些表面可见，哪些表面不可见。图象空间法
基于物体三维模型的二维显示图形（使用二维显示坐标）来
确定物体或表面与观察点的远近关系，从而判断哪些表面遮
挡了其它表面。
---- 本文将分析当前在CAD 三维图形处理中最主要的12 中消隐
算法，其中8 种属于物体空间法，4 种属于图象空间法。在实际
处理中，由于物体表面形态的复杂性和提高消隐处理的效率
，通常都是结合使用多种消隐算法来完成物体的消隐处理的
。
---- 一、物体空间法
---- 物体空间法是在三维坐标系中，通过分析物体模型间的
几何关系，如物体的几何位置、与观察点的相对位置等，来进
行隐藏面判断的消隐算法。世界坐标系是描述物体的原始坐
标系，物体的世界坐标描述了物体的基本形状。为了更好地
观察和描述物体，经常需要对其世界坐标进行平移和旋转，
而得到物体的观察坐标。物体的观察坐标能得到描述物体的
更好视角，所以物体空间法通常都是在观察坐标系中进行的
。观察坐标系的原点一般即是观察点。
---- 物体空间法消隐包括两个基本步骤，即三维坐标变换和
选取适当的隐藏面判断算法。
---- 一）三维坐标变换
---- 选择合适的观察坐标系不但可以更好地描述物体，而且
可以大大简化和降低消隐算法的运算。因此，利用物体空间
法进行消隐的第一步往往是将物体所处的坐标系转换为适当
的观察坐标系。这需要对物体进行三维旋转和平移变换。
---- 设物体顶点的原始坐标为（x, y, z），变化后的观察坐标为
（x*, y*, z*），则
---- 1 ．旋转变换
物体绕Y 轴旋转的角度 α 的三维旋转变换公式为
[x* y * z* 1]= [x y z] [ cosα sinα 0 0
-sinα cosα 0 0
0 0 1 0
0 0 0 1]
物体绕Z 轴旋转的角度 β 的三维旋转变换公式为
[x* y * z* 1]= [x y z] [ cosβ 0 -sinβ 0
0 1 0 0
sinβ 0 cosβ 0
0 0 0 1]
物体绕X 轴旋转的角度 γ 的三维旋转变换公式为
[x* y * z* 1]= [x y z] [1 0 0 0
0 corγ sinγ 0
0 -sinγ cosγ 0
0 0 0 1]
将上述表达式展开后可得如下公式
{ x'=cosα×x-sinα×z;
y'=cosβ×y-sinβ×x';
z'=sinα×x+cosα×z;
x*=cosβ×x'+sinβ×y;
y*=sinγ×z'+cosγ×y';
z*=cosγ×z'-sin γ×y';
---- 其中，x'、y' 和z' 是运算中间变量。
---- 2 ．平移变换
---- 三维平移变换公式如下
[x* y * z* 1]= [x y z 1] [1 0 0 0
0 1 0 0
0 0 1 0
Δx Δy Δz 1]
---- 展开后即得
[ x*=x+Δx
y*=y+Δy
z*=z+Δz
---- 其中 Δx、 Δy、 Δz 分别为物体沿X、Y、Z 轴的平移量。
---- 二）消隐算法
---- 常用的物体空间消隐算法包括平面公式法、背面消除法、
径向预排序法、径向排序法、隔离平面法、深度排序法、光线
跟踪法和分解法。其中前四种算法最常用，它们的基础都是
背面消隐原理。所谓背面消隐原理，即是相对观察点来说朝
向后面的物体表面是不可见的，应被隐藏。
---- 1 ．平面公式法
---- 根据解析几何原理，通过标准的平面方程可以判断给定
点是在平面的正面还是背面。平面公式法利用此原理来判断
观察点位于物体表面的哪一面，如位于背面一侧，则表面不
可见，应被消隐；反之则可见。
---- 对物体得任意表面，可将其划分为若干个平面，在根据平
面上任意三点的坐标可以求得其平面方程。标准得平面方程
为
Ax+By+Cz+D = 0;
---- 其中A、B、C、D 为决定平面得常数。如果（x1, y1, z1）、（x2, y2
, z2）、（x3, y3, z3）为平面上已知得三点坐标，则可求得A、B、C
、D 如下：
{ A=y1(x2-x3)+y2(z3-z1)+y3(z1-z2);
B=z1(x2-x3)+z2(x3-x1)+z3(x1-x2);
C=x1(y2-y3)+x2(y3-y1)+x3(y1-y2);
D=-x1(y2z3-y3z2)-x2(y3z1-y1z3)-x3(y1z2-y2z1);
---- 设观察点坐标为（x, y, z），如果
Ax+By+Cz+D = 0，则观察点（x, y, z）位于平面上；
Ax+By+Cz+D > 0，则观察点（x, y, z）位于平面背面一侧，平面不可
见，应被隐藏；
Ax+By+Cz+D < 0，则观察点（x, y, z）位于平面正面一侧，平面是可
见面，应被画出。
---- 通过对物体进行适当旋转和平移后，可将物体变换到以
观察点为原点得观察坐标系中，如果在观察坐标系中求得了
平面得方程Ax+By+Cz+D = 0，将观察点坐标（0，0，0）代入上面得
判断准则，则可得出如下得简单判据：
D > 0，则平面不可见，应被隐藏；
D < 0，则平面是可见面，应被画出。
---- 平面公式法算法简便，是在实际中使用最频繁得消隐算
法。但它只能用于凸面体得消隐，而不适用于凹面体消隐。
---- 2 ．背面消除法
---- 背面消除法是直接运用背面消隐原理的消隐算法。在数
学上，物体表面的法向量即是表面的朝向，因此，法向量方向
背向观察点的物体表面都应被消隐。
---- 表面的法向量是否背向观察点可以通过表面法向量与视
向量的点积来决定。如图1 所示，设经坐标变换后，坐标系的
原点O 即是观察点，空间中任意平面ABC 的法向量为，法向量为
与平面的交点为P，则从向量OP 即是平面ABC 的视向量。
---- 如果> 0，则物体表面是可见的朝向观察点的面；如果，则
物体表面是不可见的背向观察点的面，应被消隐。
---- 设 θ 为向量和之间的夹角，视向量的长度为线段OP 的长度
|OP|，则根据向量点积的定义可知=|OP|||cos θ。如果> 0，则cos θ
> 0（即> θ> 0）；反之，如果，则cos θ 0（即 θ）。
---- 因此，背面消除法的判据简化为：
cos θ 0，则物体表面不可见，应被消隐；
cos θ> 0，则物体表面可见，应被画出。
---- 根据平面法向量的定义可知，在平面上按逆时针方向选
取P1（x1, y1, z1）、P2（x2, y2, z2）、P3（x3, y3, z3）三点，则
---- (公式略)
---- 其中：
---- (公式略)
---- 经过投影变化后，视向量与Z 轴是平行的，因此向量和之
间的夹角 θ 即为Z 轴与向量的夹角，所以
---- 由于||>0，所以cos θ 的正负取决于C，因此背面消除法的判
据转化化为：
---- (公式略)
C 0，则物体表面不可见，应被消隐；
C > 0，则物体表面可见，应被画出。
---- 3 ．径向预排序法
---- 径向预排序法根据物体在三维坐标系XY 平面中的角位置
来判断哪些物体挡住了其它物体，物体的哪些表面挡住了其
它表面。对具有相同角位置的物体或表面，与观察点较近的
将挡住较远的。如图2 所示。
图2 径向预排序法示例
---- 径向预排序法消隐的要点是先对物体及物体的表面进行
由远及近的排序，对具有相同角位置的物体或表面，先画较
远的，后画较近的，这样如果较近的物体或表面挡住了较远
的物体或表面，则被遮挡的部分被覆盖而实现消隐。但对具
有不同角位置的物体或表面，先画哪一个可根据需要来决定
。如果存在凹面物体的消隐，一般应先画物体中心部分，再
画物体的两侧，以正确地表现互相重叠的凹面模型。
---- 径向预排序法可以对任意形状的物体进行消隐处理。但
需要预先知道观察角度，并根据角位置对物体的画图顺序预
先排序。而且构造模型的编码受到这种排序的限制，模型不
能进行旋转变换。
---- 4 ．径向排序法
---- 径向排序法是对径向预排序法的改进算法，使得构造模
型的编码能根据观察角度的变化，来自动调整物体或表面的
远近顺序即画图顺序，以实现对模型的旋转变换，以便能从
不同的角度来观察物体。算法需要检测旋转变换的角度，并
随角度的变化而调整物体或表面的远近顺序。
---- 5 ．隔离平面法
---- 隔离平面法主要用于多个物体之间的消隐处理，其基础
是平面公式法。其基本原理是，在需要进行消隐处理的两个
物体之间建立一个虚拟平面，并根据平面公式法判断出两个
物体分别位于该平面的哪一侧，以及该平面的哪一侧朝向观
察点，则可以推论得到位于平面朝向观察点一侧的物体离观
察点较近，将遮挡位于平面背向观察点一侧的物体。即位于
平面背向观察点一侧的物体应被首先画出，且应进行消隐。

---- 6 ．深度排序法
---- 深度排序法也是主要用于分析多个物体之间是否存在表
面遮挡的消隐算法。其原理是比较不同物体或表面的表示远
近的z 坐标，在观察点位于原点的观察坐标系中，|z| 值越大的
物体或表面离观察点越远，被消隐的可能性越大，应先画出
；|z| 值越小的物体或表面离观察点越近，将可能遮挡较远的
物体或表面，应后画出。
---- 深度排序法需要用到深度信息和绘图顺序，通常用于模
型数据中包含深度信息和绘图顺序的物体造型。
---- 7 ．光线跟踪法
---- 光线跟踪法的基本原理是，人能看见物体是因为物体能
反射光，因此，跟踪从光源发出的光线，光线投射到物体上，
再从物体反射到观察点，在光线轨迹中离观察点最近的物体
表面将遮挡其它物体表面。
---- 光线跟踪法需要分析物体表面的每一点的光反射状态，
因此需要的内存空间较大，运算速度也较慢。但这种方法可
同时生成物体的光照模型，产生的消隐效果和真实感都很好
。
---- 8 ．分解法
---- 分解法是对CSG 模型的一种消隐算法，首先将复杂物体分
解为一系列的立方体，离观察点近的立方体将遮挡远的立方
体，从而实现消隐。分解法算法复杂，需要的内存空间大，速
度也满，近仅用于一些特殊的场合。
---- 二、图象空间法
---- 图象空间法基于物体三维模型的二维显示图形来确定物
体或表面上的每一点与观察点的远近关系，从而判断哪些表
面遮挡了其它表面。为了获得三维物体的二维显示图形，在
对物体进行旋转和平移变化后，还需对物体进行透视投影变
换。
图3 透视投影变换示意
---- 如图3 所示，三维空间中点P(x, y, z) 由透视点E 沿Z 轴透视投
影变换到XOY 二维平面中的点P*(x*, y*, z*)。设E 点距原点O 的距
离为r，则透视投影变换公式为：
---- （x*, y*, z*, 1）=（x, y, z, 1）MPeMPr
---- 式中MPe、MPr 分别为透视变换矩阵和投影变换矩阵，它们的
表达式如下：
---- (公式略)
---- 将透视投影变换公式展开后可得：
---- (公式略)
---- 1 ． Z 缓冲区法
---- Z 缓冲区法首先建立一个大的缓冲区，用来存储三维物体
沿Z 轴透视投影而得到的二维图形的所有象素的值，因此叫
做Z 缓冲区。Z 缓冲区的单元个数与屏幕上象素点的个数相同，
也和帧缓冲区的单元个数相同，而且它们之间是一一对应的
。Z 缓冲区每个单元的大小取决于图形在观察坐标系中Z 方向
的变化范围。Z 缓冲区的每个单元的值是对应象素点所对应
的物体表面点的Z 坐标值。
---- 利用Z 缓冲区法进行消隐和造型的过程就是对屏幕中每一
点进行判断并给帧缓冲区和Z 缓冲区中相应单元进行赋值的
过程。现用形式化语言描述该算法如下：
Z缓冲区消隐算法
{
1）将帧缓冲区各单元的值置为背景色值;
2）将Z缓冲区各单元的值置为Z坐标可能出现的最大值;
3）循环：对每一物体
{
循环：对物体每一面的每一点（x, y, z）
{
i)对（x, y, z）做透视投影变换，得到变换后的X、Y坐标（x*, y*）；
ii)如果Z缓冲区中（x*, y*）对应单元的值小于z，则
{
a)将Z缓冲区中（x*, y*）对应单元的值置为z;
b)将帧缓冲区中（x*, y*）对应单元的值置为点
（x, y, z）的属性值（通常是亮度、颜色值或颜色查找表的索引值）;
}
iii)如果Z缓冲区中（x*, y*）对应单元的值大于z，则
{
a)说明目前帧缓冲区中（x*, y*）对应单元的
所表示的物体上点比点（x, y, z）
更接近观察点，即点（x, y, z）应被消隐；
b)将Z缓冲区和帧缓冲区中（x*, y*）对应单元的值均保持不变；
}
}
}
4）循环：对屏幕上每一点（x*, y*）
根据帧缓冲区中（x*, y*）对应单元的值画出象素点。
}
---- Z 缓冲区消隐算法简单、可靠，而且消隐和表现效果很好
。但需要的内存容量大，运算复杂，费时。
---- 2 ．扫描线法
---- 扫描线法是对Z 缓冲区法进行改进而派生出来的消隐算法
。为了克服Z 缓冲区法需要分配与屏幕上象素点的个数相同
单元的巨大内存这一缺点，可以将整个屏幕分成若干区域，
一个区一个区地进行处理，这样可以将Z 缓冲区的单元个数减
少为屏幕上一个区域的象素点的个数。将屏幕的一行作为这
样的区域，便得到了扫描线法，又称为扫描线Z 缓冲区法，Z 缓
冲区的单元个数仅为屏幕上一行的象素点的个数。
---- 扫描线法的形式化语言描述如下：
扫描线消隐算法
{
1）循环：从上到下对屏幕中每一条扫描线
{
i)将帧缓冲区对应行各单元的值置为背景色值;
ii)将Z缓冲区各单元的值置为Z坐标可能出现的最大值;
iii)循环：对每一物体
{
循环：对物体每一表面
{
如果当前扫描线与当前物体表面相交，则
{
循环：扫描线与当前物体表面的交点是成对的，
对每对交点之间的每一点（x, y, z）
{
A)对（x, y, z）做透视投影变换，
得到变换后的X、Y坐标（x*, y*）；
B)如果Z缓冲区中（x*, y*）对应单元的值小于z，则
{
a)将Z缓冲区中（x*, y*）对应单元的值置为z;
b)将帧缓冲区中（x*, y*）对应单元的值置为点（x, y, z）
的属性值（通常是亮度、颜色值或颜色查找表的索引值）;
}
C)如果Z缓冲区中（x*, y*）对应单元的值大于z，则
{
a)说明目前帧缓冲区中（x*, y*）对应单元的所表示
的物体上点比点（x, y, z）更接近观察点，即点（x, y, z）应被消隐；
b)将Z缓冲区和帧缓冲区中（x*, y*）对应单元的值均保持不变；
}
}
}
}
}
iv)循环：对屏幕上每一点（x*, y*）
根据帧缓冲区中（x*, y*）对应单元的值画出象素点。
}
}
---- 3 ．视线投射法
---- 视线投射法的基本原理是把物体的二维显示图像看成是
从眼睛到物体的视线把物体的可见点投射到显示屏上的投
影。该算法的形式化语言描述如下：
视线投射消隐算法
{
1）循环：对屏幕上每一象素（x*, y*）
{
确定经过视点和象素（x*, y*）的直线Ray；
判断直线Ray（x, y）与物体是否相交；
如果存在交点，则
{
a)求出直线Ray与物体的第一个交点（x, y, z）;
b)交点（x, y, z）是可见点，其余交点都应消隐；
c)将点（x, y, z）的属性值（通常是亮度、颜色值或
颜色查找表的索引值）赋给象素（x*, y*）;
}
}
2）循环：对屏幕上每一点（x*, y*）
画出象素（x*, y*）对应的属性值。
}
---- 4 ．极值检测法
---- 极值检测法需与与其它消隐算法结合适用，主要用来提
高消隐速度。极值检测法通过计算物体表面的显示坐标的极
大和极小值来判断这两个表面是否存在重叠。如果一个表面
的x 显示坐标的极大值小于另一个表面的x 显示坐标的极小值
，则这两个表面不重叠，可以按任意顺序直接画出。否则，这
两个表面存在重叠，需要用其它消隐算法进行消隐处理。
---- 通常先用极值检测法画出不发生重叠的表面，然后在用
其它算法处理重叠的表面。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]

Algorithm 版 (精华区)