Voxel Space：重温1992年的3D渲染奇迹

背景

让我们将时间拨回1992年。那时的CPU速度比今天慢了1000倍，GPU加速技术要么尚未出现，要么对于普通消费者而言过于昂贵。因此，3D游戏完全依赖CPU进行计算，渲染引擎通常只能渲染填充了单一颜色的多边形。

在这一时期，MicroProse于1991年发布了《Gunship 2000》，而NovaLogic则在1992年推出了具有里程碑意义的游戏《Comanche》（武装直升机）。

《Comanche》的画面在当时令人叹为观止，甚至可以说领先时代整整三年。玩家可以看到更多细节，例如山脉和山谷上的纹理，以及首次出现的精致着色甚至阴影。虽然画面依然带有明显的像素感，但那是那个年代所有游戏的共同特征。

核心内容

《Comanche》采用了一种名为 Voxel Space（体素空间）的技术。该技术基于与光线投射（ray casting）相同的理念。因此，Voxel Space 引擎本质上是一个 2.5D 引擎，它并不具备常规 3D 引擎所拥有的全部自由度。

地形表示与预计算光照

表示地形最简单的方式是通过高度图（height map）和颜色图（color map）。在《Comanche》中，游戏使用了一个 1024 * 1024 分辨率、单字节的高度图，以及一个同样分辨率的单字节颜色图（读者可以在相关网站下载这些地图）。这些地图具有周期性特征。

这种表示方法将地形限制为“地图上的每个位置对应一个高度”，因此无法表示建筑物或树木等复杂几何结构。然而，颜色图的一个巨大优势在于，它已经包含了着色和阴影信息。Voxel Space 引擎只需直接读取颜色值，无需在渲染过程中计算光照。

渲染算法原理

对于 3D 引擎而言，其渲染算法其实非常简洁。Voxel Space 引擎对高度图和颜色图进行光栅化，并绘制垂直线。其核心流程如下：

1. 清屏。
2. 保证遮挡关系：从后向前渲染（即从远处到近处）。这被称为画家算法（Painter's Algorithm）。
3. 确定映射线：找到地图上对应于观察者相同光学距离的那条线。需考虑视场角（Field of View）和透视投影（物体越远显得越小）。
4. 线段分割：将这条线分割以匹配屏幕的列数。
5. 采样：从 2D 地图中获取对应线段片段的高度和颜色。
6. 透视投影：对高度坐标执行透视投影计算。
7. 绘制：根据透视投影得到的高度，使用对应的颜色绘制一条垂直线。

代码实现解析

在最简单的形式下，核心算法仅包含几行代码（以 Python 语法为例）：

def Render(p, height, horizon, scale_height, distance, screen_width, screen_height):
    # 从后向前绘制（高 z 坐标到低 z 坐标）
    for z in range(distance, 1, -1):
        # 在地图上找到对应的线。此计算对应 90° 的视场角
        pleft = Point(-z + p.x, -z + p.y)
        pright = Point( z + p.x, -z + p.y)
        
        # 分割线段
        dx = (pright.x - pleft.x) / screen_width
        
        # 对线段进行光栅化，并为每个段绘制一条垂直线
        for i in range(0, screen_width):
            # 计算屏幕上的高度：基于高度图采样，除以距离 z 实现透视缩放，加上地平线位置
            height_on_screen = (height - heightmap[pleft.x, pleft.y]) / z * scale_height + horizon
            
            # 绘制垂直线，使用从高度图采样的颜色
            DrawVerticalLine(i, height_on_screen, screen_height, colormap[pleft.x, pleft.y])
            
            pleft.x += dx

# 调用渲染函数，传入相机参数：
# 位置, 高度, 地平线位置, 高度缩放因子, 最大距离, 屏幕宽度和高度
Render( Point(0, 0), 50, 120, 120, 300, 800, 600 )

上述算法仅支持向北观看。若要改变角度，只需增加几行代码来旋转坐标：

def Render(p, phi, height, horizon, scale_height, distance, screen_width, screen_height):
    # 预计算视角参数
    var sinphi = math.sin(phi);
    var cosphi = math.cos(phi);
    
    # 从后向前绘制
    for z in range(distance, 1, -1):
        # 在地图上找到对应的线
        pleft = Point(
            (-cosphi*z - sinphi*z) + p.x,
            ( sinphi*z - cosphi*z) + p.y)
        pright = Point(
            ( cosphi*z - sinphi*z) + p.x,
            (-sinphi*z - cosphi*z) + p.y)
            
        # 分割线段
        dx = (pright.x - pleft.x) / screen_width
        dy = (pright.y - pleft.y) / screen_width
        
        # 光栅化并绘制垂直线
        for i in range(0, screen_width):
            height_on_screen = (height - heightmap[pleft.x, pleft.y]) / z * scale_height + horizon
            DrawVerticalLine(i, height_on_screen, screen_height, colormap[pleft.x, pleft.y])
            
            pleft.x += dx
            pleft.y += dy

# 调用渲染函数，增加视角参数 phi
Render( Point(0, 0), 0, 50, 120, 120, 300, 800, 600 )

性能优化技巧

当然，为了获得更高的性能，还有许多技巧可以使用：

1. 从前向后绘制与 Y 缓冲区： 我们可以改为从前向后绘制。优势在于，由于遮挡关系，我们不必每次都画到屏幕底部。然而，为了保证遮挡，我们需要一个额外的 Y 缓冲区（Y-buffer）。对于每一列，存储最高的 Y 位置。因为是从前向后画，下一行可见的部分只能比之前画过的最高线更大。

2. 细节层次（Level of Detail, LOD）： 在近处渲染更多细节，而在远处渲染较少细节。

结合上述优化（从前向后绘制 + LOD）的代码实现如下：

def Render(p, phi, height, horizon, scale_height, distance, screen_width, screen_height):
    # 预计算视角参数
    var sinphi = math.sin(phi);
    var cosphi = math.cos(phi);
    
    # 初始化可见性数组。屏幕每列的 Y 位置
    ybuffer = np.zeros(screen_width)
    for i in range(0, screen_width):
        ybuffer[i] = screen_height
        
    # 从前向后绘制（低 z 坐标到高 z 坐标）
    dz = 1.
    z = 1.
    while z < distance:
        # 在地图上找到对应的线
        pleft = Point(
            (-cosphi*z - sinphi*z) + p.x,
            ( sinphi*z - cosphi*z) + p.y)
        pright = Point(
            ( cosphi*z - sinphi*z) + p.x,
            (-sinphi*z - cosphi*z) + p.y)
            
        # 分割线段
        dx = (pright.x - pleft.x) / screen_width
        dy = (pright.y - pleft.y) / screen_width
        
        # 光栅化并绘制垂直线
        for i in range(0, screen_width):
            height_on_screen = (height - heightmap[pleft.x, pleft.y]) / z * scale_height + horizon
            
            # 使用 ybuffer