计算机图形学 第七章 真实感图形学-消隐

六个算法，考其中一个

消隐：

• 消除隐藏线
• 消除隐藏面

消隐算法：

• 物体空间的消隐算法：将场景中每一个面于其他每个面比较，求出所有点、边、面的遮挡关系

  • 光线投射、Roberts

• 图像空间的消隐算法：对屏幕上每个像素进行判断，决定哪个多边形在该像素可见

  • Z-buffer、扫描线、warnock（区域子分割算法）

• 物体空间和图像空间的消隐算法：在物体空间中预先计算面的可见性优先级，再在图像空间中生成消隐图

  • 画家算法

消除隐藏线

平面对直线段的遮挡判断算法（消除隐藏线、Roberts算法）

不失一般性，取视点在 Z 轴正无穷远，视线方向为 Z 轴负方向，物体投影到 XOY 平面上

① 若线段两端点及视点在给定多边形的同侧，则线段不被其遮挡，转 ⑦ （深度检测，通过判断多边形最大 Z 坐标于线段端点的最小 Z 坐标）

② 若线段的投影与多边形投影的包围盒（指覆盖多边形投影的最小矩形区域）无交点，线段不被给定多边形遮挡，转 ⑦

①	②

③ 求直线与多边形的交；若无交点（平行）则转 ④ ，否则判断交点在线段内部或外部（即线段与多边形的交点在线段的延长线上）：

• 若交点在线段内部，则交点将线段分成两部分，与视点同侧一段不被遮挡，与视线异侧一段转④ 再判断；
• 若交点在线段外部，则转 ④

④ 求所剩线段（可能被遮挡部分）的投影与多边形边界投影的所有交点，并根据交点在原直线参数方程中的参数值求出 Z 值（即深度）。若无交点，则转 ⑤

③	④

⑤ 以上所求各交点将线段的投影分成若干段，求出第一段中点

⑥ 若第一段中点在多边形的投影内，则相应的段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值进行判断

⑦ 结束

优化：以上算法复杂度为 $O(n^2)$ ，可以通过以下方法减少求交的工作量：

设 $V$ 为由视点出发的观察向量，$N$ 为某多边形的法向量：

• 若 $V-N>0$ ，称该多边形为后向面
• 若 $V-N<0$ ，称该多边形为前向面

后向面总是看不见的，不仅会由于后向面的遮挡使别的棱成为不可见的。因此可以把后向面全部去掉，并不影响消隐结果。例如下图中的 $JEAF$ 、$HCBG$ 和 $DEABC$

消除隐藏面

（接下来五种算法是消除隐藏面的算法）

画家算法

算法：列表优先算法

• 把屏幕置成背景色
• 把物体的各个面按照其离视点的远近进行排序，离视点远者（z 轴坐标最小）在表头，离视点近者（z 轴坐标最大）在表尾，排序结果存储在一张深度优先级表中
• 从表头到表尾逐个取出多边形投影到屏幕并显示多边形包含的实心区域

（跟画家作画的过程类似，近景会覆盖远景）

排序方法：

• 深度重叠判断：判断相邻多边形最大 Z 坐标和最小 Z 坐标的关系，例如若 $Z_{min}(P)\ge Z_{max}(Q)$ ，则 Q 不可能遮挡 P 的任意部分，可以在 P 之前画出
• 投影重叠判断：
  • 若 P 和 Q 在 XY 平面上的投影的包围盒互不重叠，则 P、Q 不可能互相遮挡，其顺序无关紧要（需要保存最大/最小的 X、Y 坐标）
  • P 在 Q 之前：若 P 的所有顶点在 Q 所在平面的可见一侧，则 Q 不会遮挡 P 的任何部分（需要将 P 的各个顶点带入 Q 的方程判断符号，需要保存平面方程）
  • P 在 Q 之后：如果 P 在 Q 之前测试失败，则进行逆测试
• 精确的重叠测试：若所有测试失败，则必须对多边形在 XY 平面上的投影作求交运算（最简单的是对两多边形的任意两条边求交，求出第一个交点就可以在该交点处比较深度，只要能判断前后顺序即可）

缺点：只能处理互不相交的面，在两个面相交、三个以上的面重叠的情形，用任何排序方法都不可能排出正确的序，此时需要将有关的面进行分割后再排序

Z-Buffer 算法

Z Buffer：Z 缓冲区中每个单元的值是对应像素点所反映对象的 Z 坐标值，Z 缓冲器中每个单元的初值取成 Z 的极小值（离视点最远）；帧缓冲器中每个单元的初值可方对应背景颜色的值；消隐的过程就是给 Z 缓冲器和帧缓冲器中相应单元填值的过程

算法：把显示对象的每个面的每一点的属性（颜色/灰度）填入帧缓冲器的相应单元前，只要把这点的 Z 坐标值与 Z 缓冲器中相应单元的值进行比较：

• 前者大于后者时，改变帧缓冲器对应单元的值，同时 Z 缓冲器对应单元也要更新为这点的 Z 坐标值
• 前者小于后者，说明对应像素已经显示了另外一个对象上的某个点，而且其更靠近观察点，所以无需更新

帧缓存全部置为背景色;
Z缓存全部置为最小Z值;
for (每一个多边形) {
    扫描转换该多边形;
    for (该多边形覆盖的每个像素(x,y)) {
        计算该多边形在该像素的深度值z=Z(x,y);
        if (z > Z缓存[x,y]) {
            Z缓存[x,y] = z;
            帧缓存[x,y] = 该多边形在(x,y)处的颜色值;
        }
    }
}

深度值的增量求法：

• 给定多边形 $ax+by+cz+d=0$ 和坐标 $(x,y)$ 可计算出深度为 $z=-\frac{-d-ax-by}{c}$
• 若在 $(x,y)$ 求出深度为 $z$ ，则在 $(x+1,y)$ 处深度为 $z-\frac{a}{c}$

缺点：占用空间大，没有利用图形的相关性和连续性；可以改进算法，只用一个缓存深度的变量，而不是用缓存深度的数组（更改遍历顺序，先遍历像素再遍历多边形）

区间扫描线算法

算法：对 Z-Buffer 做出改进：

• 消隐问题分解到一条条扫描线上解决，一条扫描线上每个区间只计算一次深度值，减少所需的 Z 缓冲器；
• 计算深度值时，利用面连贯性，只用了一个加法；但在每个像素处都计算了深度值并比较深度，因此，被多个多边形覆盖的像素区还是要多次计算，计算量仍然很大。

把当前扫描线与各个多边形在投影平面的投影的交点进行排序后，使扫描线分为若干子区间；因此只要在区间任一点处找到该处 Z 值最大的一个面，这个区间上的每一个像素就用这个面的颜色来显示。
、

确定小区间上的颜色：

• 小区间上没有任何多边形，则用背景色显示（如上图 $[a_4,a_5]$ ）
• 小区间上只有一个多边形，以该多边形在该处的颜色显示（如上图 $[a_1,a_2]$ ）
• 小区间上存在多个多边形，需要通过深度测试判断可见多边形（如上图 $[a_6,a_7]$ ）
• 若允许物体表面相互贯穿，则必须求出他们在扫描平面（ZX 平面）的交点，用这些交点把小区间分为更小的子区间（称为间隔），在这些间隔上决定哪些多边形可见（如下图 $[a_2,a_3]$ 分为 $[a_2,b]$ 和 $[b,a_3]$）
  • 可在间隔内任取一采样点（如间隔中点），分析该点处哪个多边形离视点最近，即作为该间隔内可见的多边形（如下图 $[a_2,b]$ 上 $F_2$ 可见，$[b,a_3]$ 上 $F_1$ 可见）

Warnock 算法（区域子分割算法、区域采样算法）

包围和分离的情况：转角检查法、区域编码法（另外几种情况在裁剪中可能会考）

思想：把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口内目标足够简单、可以显示为止

四叉树算法：首先将屏幕坐标系的矩形作为初始窗口，再将场景中的多边形投影到窗口内

• 如果窗口内没有物体，则按背景色显示；若窗口内只有一个面，则把该面显示出来
• 否则，将窗口分成四个等大子窗口，重复上述过程

窗口与多边形的覆盖关系：内含和相交、包围和分离

• 判断内含和相交关系：裁剪算法，不必求出具体交点和裁剪，只要判断出多边形含于窗口内或多边形某边于窗口某边有交就可以了
• 判断包围和分离关系的转角检查法：按顺或逆时针方向绕多边形边界一周，累计相邻的两个顶点对窗口所张的交之和 $\sum \alpha$ ，若 $\sum \alpha =360^{\circ }$ ，则多边形包含窗口；若 $\sum \alpha =0$ ，则多边形与窗口分离（相对于窗口的张角其实是相对于窗口中心的张角，且是有方向的）

• 判断包围和分离关系的区域编码法：把窗口的平面区域分为八个部分，编号为 0-7，多边形的每一个顶点一定落在某个区域中，否则为前述的内含或相交关系，顶点所在区的编号就作为顶点的编号

  • 对每条边，$\alpha =$ 终点编码 - 起点编码
    • 若 $\alpha >4$ 或 $\alpha <-4$ ，则模 $8$
    • 若 $\alpha =\pm 4$ ，则将该边在窗口边界分为两段，每段分别求 $\alpha$ （分界点归属哪个区域都没有关系，但是必须规定它属于哪个区域）
  • 对每条边的 $\alpha$ 求和得到：

  $$\sum \alpha =\{\begin{array}{ll}\pm 8& 多边形包含窗口\\ 0& 多边形与窗口分离\end{array}$$

  Σα=8	Σα=0

可以直接显示的情况：

• 所有多边形均与窗口分离，置窗口为背景色
• 只有一个多边形与窗口相交，或该多边形包含窗口，则先整个窗口置背景色，再对多边形在窗口内部分使用扫描线算法绘制
• 有一个多边形包围了窗口，或窗口与多个多边形相交，但有一个多边形包围窗口，且在最前面（最靠近观察点、Z 轴坐标最大）

光线投影算法

算法：考察由视点出发穿过观察屏幕一像素而射入场景的一条射线

• 若没有物体相交，用背景色显示即可
• 若由物体相交，则计算出光线与物体表面的交点，取离像素最近的交点所在面片的颜色作为该像素的颜色

（就是相当于 Z-Buffer 算法的内外 for 循环颠倒顺序了，时间复杂度类似，但是大大节省了空间，也可使用包围盒技术、空间分割技术以及物体的层次表示法来加速）

for (屏幕上每一像素) {
    形成通过该屏幕像素(u,v)的射线;
   	for (场景中每一个物体) {
        将射线与该物体求交;
        if (存在交点) {
            以最近交点所属的颜色显示像素(u,v);
        } else {
            以背景色显示像素(u,v);
        }
    }
}