第四章 消隐
4.1 消隐概述
4.1.1 消隐定义
-
消隐
-
如果把可见和不可见的线都画出来，会对视觉造成多义性。
-
要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，即消除隐藏线和隐藏面，简称消隐。
-
-
4.1.2 消隐分类
-
按消隐对象分类
-
线消隐
- 消隐对象是物体上的边，消除的是物体上不可见的边。
-
面消隐
- 消隐对象是物体上的面，消除的是物体上不可见的面，通常做真实感图形消隐时用面消隐。
-
-
按消隐空间分类
-
物体空间的消隐算法
-
以场景中的物体为处理单元。假设场景中有 k 个物体，将其中一个物体与其余 k-1 个物体逐一比较，仅显示它可见表明以达到消隐的目的。
-
此类算法常用于线框图的消隐。
-
Roberts 算法、光线投射法
-
-
图像空间的消隐算法
-
消隐算法的主流。
-
Z-buffer 算法
-
扫描线算法
-
Warnock 消隐算法
-
-
4.2 物体空间的消隐算法
4.2.1 Roberts 算法
-
算法步骤
-
逐个的独立考虑每个物体自身，找出为其自身所遮挡的边和面 (自消隐)
-
将每一物体上留下的边再与其它物体逐个的进行比较，以确定是完全可见还是部分或全部遮挡 (两两物体消隐)
-
确定由于物体之间的相互贯穿等原因，是否要形成新的显示边等，从而使被显示各物体更接近现实。
-
-
算法特点
- 数学处理严谨，计算量甚大。算法要求所有被显示的物体都是凸的，对于凹体要先分割成多个凸体的组合。
4.2.2 光线投射法
-
定义
- 光线投射是求光线与场景的交点，该光线就是所谓的视线 (如视点与像素连成的线)
-
特点
- 一条视线与场景中的物体可能有许多交点，求出这些交点后需要排序，在前面的才能被看到。人的眼睛可以一目了然，但计算机做需要大量的运算。
4.3 Z 缓冲区算法 (Z-Buffer)
4.3.1 Z-Buffer 算法概述
-
算法介绍
-
该算法由 Edwin Catmull 独立开发，能够跟踪屏幕上每个像素深度的算法。
-
该算法有帧缓冲器和深度缓冲器。
-
$intensity \ (x,y)$ —— 属性数组 (帧缓冲器)，存储图像空间每个可见像素的光强或颜色
-
$depth\ (x,y)$ —— 深度数组 (z-buffer)，存放图像空间每个可见像素的 z 坐标
-
-
-
深度
-
以 $xoy$ 面为投影面，$z$ 轴为观察方向。
-
过屏幕上任意像素点 $(x,y)$ 作平行于 $z$ 轴的射线 $R$，与物体表面相交于 $p_1$ 和 $p_2$ 点。
-
$p_1$ 和 $p_2$ 点的 $z$ 值称为该点的深度值。
-
-
-
算法思想
-
先将 $Z$ 缓冲器中各单元的初始值置为最小值。当要改变某个像素的颜色值时，首先检查当前多边形的深度值是否大于该像素原来的深度值 (保存在该像素所对应的 $Z$ 缓冲器的单元中)
-
如果大于原来的 $Z$ 值，说明当前多边形更靠近观察点，用它的颜色替换像素用来的颜色。
-
1 2 3 4 5 6 7 8 9 10 11 12 13
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-Buffer 算法比较简单，也很直观。
-
在像素级上以近物取代远物。与物体在屏幕上的出现顺序是无关紧要的，有利于硬件实现。
-
-
Z-Buffer 算法的缺点
-
占用空间大
-
没有利用图形的相关性与连续性 (严重缺陷)
-
该算法是在像素级上的消隐算法 (很大缺陷)
-
4.3.2 Z-Buffer 算法改进
-
算法改进
-
只用一个深度缓存变量 $zb$ 代替与图像大小相等的缓存数组，节省了空间。
-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
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) { 计算多边形 P 在交点 (i,j) 处的光照颜色并显示 } }
-
-
计算 $P_k$ 在点 $(i,j)$ 处的深度
- 多边形 $P_k$ 的平面方程为 $ax+by+cz+d=0$，$depth=-\frac{ai+bj+d}{c}$
-
计算一点是否在多边形中
-
射线法
-
核心：由被测点 $P$ 处向 $y=-inf $ 方向作射线，交点个数是奇数，则被测点在多边形内部；交点个数是偶数表示在多边形外部。
-
若射线正好经过多边形的顶点，则采用 “左开右闭” 的原则来实现。即：当射线与某条边的顶点相交时，若边在射线的左侧，交点有效，计数；若边在射线的右侧，交点无效，不计数。
-
-
- 缺点：计算量大、不稳定 (浮点误差)
-
-
弧长法
-
核心：以 $p$ 点为圆心，作单位圆，把边投影到单位圆上，对应一段段弧长，规定逆时针为正，顺时针为负，计算弧长代数和。
-
代数和为 0，点在多边形外部；代数和为 2π，点在多边形内部；代数和为 π，点在多边形边上。
-
-
-
以顶点符号为基础的弧长累加方法
-
核心：$p$ 是被测点，按照弧长法，$p$ 点的代数和为 2π。不要计算角度，做一个规定来取代原来的弧长计算。
-
在边上与内部均为 2π，外部为0。
-
-
$(x_i,y_i)$ $(x_{i+1},y_{i+1})$ 弧长变化 象限变化 $(+ \ +)$ $(+ \ +)$ 0 $1\rightarrow1$ $(+ \ +)$ $( - \ +)$ π/2 $1\rightarrow2$ $(+ \ +)$ $( - \ -)$ π $1\rightarrow3$ $(+ \ +)$ $( + \ - ) $ -π/2 $1\rightarrow4$ $(- \ +)$ $(+ \ +)$ -π/2 $2\rightarrow1$ $ (- \ +)$ $( - \ +)$ 0 $ 2\rightarrow2$ $ (- \ +)$ $( - \ -)$ π/2 $2\rightarrow3$ $ ( - \ +)$ $( + \ - ) $ π $2\rightarrow4$ $ ( - \ -)$ $(+ \ +)$ -π $3\rightarrow1$ $ ( - \ - ) $ $( - \ +)$ -π/2 $ 3\rightarrow2$ $(- \ -)$ $( - \ -)$ 0 $ 3\rightarrow3$ $ ( - \ -)$ $( + \ - ) $ π/2 $3\rightarrow4$ $(+ \ - ) $ $(+ \ +)$ π/2 $4\rightarrow1$ $(+ \ - ) $ $( - \ +)$ -π $ 4\rightarrow2$ $(+ \ - ) $ $( - \ -)$ -π/2 $ 4\rightarrow3$ $(+ \ - ) $ $( + \ - ) $ 0 $ 4\rightarrow4$
-
-
4.4 区间扫描线算法
-
算法概述
- 考虑Z-Buffer没有利用图形的相关性和连续性的缺陷，该算法放弃了Z-Buffer的思想（一个像素可能被多个多边形覆盖，即一个像素要多次判别，效率极低），是消隐算法中最快的算法之一。
-
算法过程
-
把扫描线和多边形的这些交点都求出来，对每个区间，只判一个像素的颜色，那么整个区间都是该颜色
-
像素计算 -> 逐段计算，效率大大提高。
-
-
确定小区间的颜色：
-
小区间无任何多边形，如[a4, a5]，用背景色显示
-
小区间仅有一多边形，如[a1, a2]，显示该多边形颜色
-
小区间存在两个以上多边形，如[a6, a7]，用深度检测
-
-
-
算法实现问题
-
如何求交点
- 利用增量算法简化求交
-
每段区间上要求 z 值最大的面，如何得知区间与哪些多边形相关
- 利用区间扫描转换算法中的 AET 与 NET 得知
-
4.5 Warnock消隐算法
-
算法概述
- 区域子分割算法，发明人 Warnock (Adobe创始人)，图像空间中非常经典的算法，其重要性不体现在其效率，而是体现在分治思想和堆栈数据结构的运用。
-
算法思想
-
把物体投影到全屏幕窗口
-
递归分割窗口，直到窗口内目标足够简单（可以显示）
- 若窗口分割至像素级别，仍有两个以上的面，则不必再分割。取窗口内最近的可见面颜色或所有可见面平均颜色即可。
-
-
-
如何判断窗口内图形足够简单
- 四种简单窗口图形
- 窗口中仅包含一个多边形
-
窗口与一个多边形相交，且窗口内无其它多边形 —— 直线方程作为判别函数
-
窗口为一个多边形所包围
-
窗口与一个多边形相分离
4.6 光栅扫描算法小结
-
核心思想
-
增量思想
- 通过增量算法可以减少计算量。
-
编码思想
-
符号判别 $\rightarrow$ 整数算法
- 尽可能地提高底层算法的效率，底层上提高效率才是真正解决问题。
-
图形连贯性
- 利用连贯性可以大大减少计算量。
-
分而治之
- 把一个复杂对象进行分块，分到足够简单再进行处理。
-