Hidden Surface Removal 隐藏表面消除

隐藏面测定 - 维基百科 --- Hidden-surface determination - Wikipedia

简介

• 计算机图形学(Computer Graphics)试图表示三维空间中的物体
• 大多数物体不透明，我们只关注它们的外表面，这些表面具有形状、颜色和纹理等属性
• 实心物体的线框(wire-frame)绘制效果不够真实，因为它包含了现实中被遮挡的部分，因此需要某种形式的隐藏线(hidden-line)或隐藏表面消除(hidden-surface removal)
• 不存在对所有情况都同样有效的单一算法
• 大多数算法通过考虑数据格式来提高速度和效率，这自动限制了它们的使用范围

简化假设

a) 将物体表面划分为若干由"边界曲线(boundary curves)"或"轮廓(contours)"包围的面。轮廓可以是任意闭合曲线，面可以是曲面，因此需要某种方式来指定曲面方程

b) 限制描述，只允许平面(planar)面。轮廓现在必须是平面内的封闭多边形。（由于两个平面必须在直线上相交，没有任何孔的物体必须由直线组成其边缘曲线）

c) 细分多边形直到它们都是凸(convex)的

d) 细分多边形直到物体被描述为三角面片(triangular facets)（某些隐藏表面算法需要）

定义

• 隐藏表面消除(Hidden surface removal, HSR)、遮挡剔除(occlusion culling, OC)或可见表面确定(visible surface determination, VSD)是用于确定从特定视点看不到哪些表面和部分表面的过程
• 隐藏表面确定算法是可见性问题(visibility problem)的解决方案，这是3D计算机图形学领域最早的主要问题之一
• 隐藏表面确定是一个过程，通过它防止渲染对用户不可见的表面，例如因为它们位于不透明物体（如墙）后面
• 尽管硬件能力不断提高，但仍需要先进的渲染算法
• 渲染引擎的责任是允许大型世界空间，并且随着世界大小接近无穷大，引擎不应减速，而应保持恒定速度
• 优化这一过程依赖于能够确保尽可能少地将资源部署到最终不会显示给用户的表面的渲染上

Painter's Algorithm 画家算法

• Painter's algorithm 按多边形的重心(barycenter)对其排序，并从后向前绘制
• 当应用于具有相似大小的多边形形成平滑网格且打开背面剔除(back-face culling)的场景时，会产生很少的伪影(artifacts)
• 这里的代价是排序步骤以及可能发生视觉伪影的事实
• 该算法在设计上对一般场景是不适用的，因为它无法处理各种常见配置中的多边形

Z-Buffer Method

• 在光栅化(rasterization)期间，检查每个像素或采样（在抗锯齿(anti-aliasing)情况下）的深度/Z值，但在不损失一般性的情况下使用术语"像素"
• 如果当前像素在Z-buffer中的像素后面，则拒绝该像素，否则对其着色并将其深度值替换Z-buffer中的值
• Z-buffering很容易支持动态场景，目前在图形硬件中有效实现
• 这是当前的标准。使用Z-buffering的成本是每个像素最多使用4个字节，并且光栅化算法需要根据z-buffer检查每个光栅化样本。 Z-buffer也可能因精度误差而产生伪影

算法步骤：

对于每个像素位置$(x, y)$:

1. 设置$Z_{buffer}(x,y) = 1$
2. 对于每个多边形$P_i, i=1,2, ..., n$:
   1. 计算$P_i$在$(x,y)$处的深度$z_i$
   2. 如果$z_i < Z_{buffer}(x,y)$，则:
      1. 设置$Z_{buffer}(x,y) = z_i$
      2. 设置$framebuffer(x,y) = I(P_i, x, y)$

其中$I(P_i, x, y)$表示多边形$P_i$在$(x,y)$处的强度值（即该像素的最终颜色）。

注意事项:

• 多边形必须首先转换为（归一化的）观察坐标并根据归一化的视图体积进行裁剪
• 深度计算可以按如下方式进行："在（归一化的）观察坐标系中记录每个多边形的平面方程，然后使用增量法找到深度z"

Coverage Buffers 和 Surface Buffer

• Coverage buffers (C-Buffer)和Surface buffer (S-Buffer)：比z-buffer更快，常用于游戏
• 它们不是为每个像素存储Z值，而是为屏幕的每一行存储已显示片段的列表
• 然后根据已显示的片段裁剪新多边形，这些片段会隐藏它们
• S-Buffer可以显示未排序的多边形，而C-Buffer要求多边形从最近到最远显示
• 因为C-buffer技术不需要一个像素被绘制多次，所以该过程稍微快一些
• 与二进制空间分区(binary space partitioning, BSP)树一起使用，可为多边形提供排序

Scan-Line Method 扫描线方法

1. 通过将多边形与由扫描线表示的平面相交来创建多边形的片段(segments)
2. 按x对所有片段端点进行排序，以确定扫描线的所有跨度(spans)
3. 如果一个跨度中没有出现片段，则该跨度使用背景强度
4. 如果一个跨度只包含一个片段，则该片段可见，并使用多边形方程计算该跨度中所有像素的强度值
5. 如果几个片段延伸到整个跨度，则找到最接近观察者的片段（z值最小），并将其强度用于该跨度

需要两个列表：

• Active-edge list (AEL)：与当前扫描线相交的边
• Active polygon list (APL)：与当前跨度重叠的多边形计数

Binary Space Partitioning (BSP) 二进制空间分区

• 二进制空间分区(BSP)沿与多边形边界对应的平面划分场景
• 细分的构造方式是，当遍历BSP树时，从场景中的任何一点都能提供明确的深度排序
• 这里的缺点是BSP树的创建需要昂贵的预处理
• 这意味着它不太适合由动态几何组成的场景
• 优点是数据是预先排序的，没有错误，可用于前面提到的算法

BSP树的构建

1. 选择一个多边形作为根节点，创建一个空树
2. 对于每个剩余的多边形，检查它与根多边形的位置关系：
   • 如果多边形完全在根多边形的正面，将其插入到正子树中
   • 如果多边形完全在根多边形的反面，将其插入到负子树中
   • 如果多边形与根多边形相交，将其分割为两部分，分别插入正负子树
3. 递归地对正负子树中的多边形重复步骤2，直到所有多边形都被插入到树中

使用BSP树进行可见性计算

1. 根据视点位置，从BSP树的根节点开始遍历
2. 在每个节点：
   • 如果视点在节点表示的多边形正面，先遍历负子树，再遍历正子树，最后绘制该节点的多边形
   • 如果视点在节点表示的多边形反面，先遍历正子树，再遍历负子树，最后绘制该节点的多边形
   • 如果视点在节点表示的多边形所在平面上，只需遍历正子树或负子树，最后绘制该节点的多边形
3. 按照遍历顺序绘制多边形，就可以得到正确的可见性

总结

隐藏表面消除是计算机图形学中的一个基本问题，其目的是确定哪些表面或表面的部分从特定视点看不到。常用的隐藏表面消除算法包括：

• Painter's Algorithm（画家算法）：按照多边形的深度顺序从后向前绘制，简单但可能产生伪影
• Z-Buffer Method（Z缓冲算法）：为每个像素维护一个深度值，只绘制最靠近视点的像素，目前在图形硬件中广泛使用
• Coverage Buffers和Surface Buffer：比Z-Buffer更快，常用于游戏，与BSP树结合使用
• Scan-Line Method（扫描线算法）：按扫描线逐行处理，维护活动边表和活动多边形表
• Binary Space Partitioning（二进制空间分区）：将空间递归地划分为两个子空间，构建BSP树，可以高效地确定多边形的可见性

选择合适的隐藏表面消除算法需要权衡速度、内存消耗、实现难度以及场景的特点等因素。