Voxel Space (2017)

Voxel Space Engine History

Let us go back to the year 1992. The CPUs were 1000 times slower than today and the acceleration via a GPU was unknown or unaffordable. 3D games were calculated exclusively on the CPU and the rendering engine rendered filled polygons with a single color. It was during that year NovaLogic published the game Comanche.

Voxel Space 引擎历史

让我们回到 1992 年。当时的 CPU 比今天慢 1000 倍，通过 GPU 进行加速在当时闻所未闻，或者根本无法负担。3D 游戏完全由 CPU 计算，渲染引擎只能渲染单色的填充多边形。正是在那一年，NovaLogic 发布了游戏《Comanche》（卡曼奇）。

The graphics were breathtaking for the time being and in my opinion 3 years ahead of its time. You see many more details such as textures on mountains and valleys, and for the first time a neat shading and even shadows. Sure, it’s pixelated, but all games in those years were pixelated.

在当时，其图形效果令人叹为观止，在我看来，它领先了时代 3 年。你可以看到更多细节，例如山脉和山谷的纹理，以及首次出现的精美明暗处理甚至阴影。当然，画面是有像素感的，但那个年代的所有游戏都是如此。

Render algorithm

Comanche uses a technique called Voxel Space, which is based on the same ideas like ray casting. Hence the Voxel Space engine is a 2.5D engine, it doesn’t have all the levels of freedom that a regular 3D engine offers.

渲染算法

《Comanche》使用了一种称为 Voxel Space（体素空间）的技术，其原理与光线投射（ray casting）相同。因此，Voxel Space 引擎是一个 2.5D 引擎，它并不具备常规 3D 引擎所提供的所有自由度。

Height map and color map

The easiest way to represent a terrain is through a height map and color map. For the game Comanche a 1024 * 1024 one byte height map and a 1024 * 1024 one byte color map is used. These maps are periodic: Such maps limit the terrain to “one height per position on the map” - Complex geometries such as buildings or trees are not possible to represent. However, a great advantage of the colormap is, that it already contains the shading and shadows. The Voxel Space engine just takes the color and doesn’t have to compute illumination during the render process.

高度图与颜色图

表示地形最简单的方法是通过高度图和颜色图。对于《Comanche》这款游戏，使用的是 1024 * 1024 的单字节高度图和 1024 * 1024 的单字节颜色图。这些地图是周期性的：此类地图将地形限制为“地图上每个位置只有一个高度”——因此无法表示建筑物或树木等复杂几何体。然而，颜色图的一大优势在于它已经包含了明暗处理和阴影。Voxel Space 引擎只需直接读取颜色，无需在渲染过程中计算光照。

Basic algorithm

For a 3D engine the rendering algorithm is amazingly simple. The Voxel Space engine rasters the height and color map and draws vertical lines. The following figure demonstrate this technique:

1. Clear Screen.
2. To guarantee occlusion start from the back and render to the front. This is called painter algorithm.
3. Determine the line on the map, which corresponds to the same optical distance from the observer.
4. Consider the field of view and the perspective projection (Objects are smaller farther away).
5. Raster the line so that it matches the number of columns of the screen.
6. Retrieve the height and color from the 2D maps corresponding of the segment of the line.
7. Perform the perspective projection for the height coordinate.
8. Draw a vertical line with the corresponding color with the height retrieved from the perspective projection.

基本算法

对于 3D 引擎来说，其渲染算法简单得惊人。Voxel Space 引擎对高度图和颜色图进行光栅化，并绘制垂直线。下图展示了该技术：

1. 清除屏幕。
2. 为保证遮挡关系，从后向前渲染。这被称为画家算法。
3. 确定地图上与观察者距离相同的线。
4. 考虑视野和透视投影（远处的物体较小）。
5. 对该线进行光栅化，使其与屏幕的列数匹配。
6. 从 2D 地图中检索对应线段的高度和颜色。
7. 对高度坐标执行透视投影。
8. 使用透视投影检索到的高度，绘制对应颜色的垂直线。

(Code snippets omitted for brevity, but the logic follows the provided Python syntax.)

More performance

There are of course a lot of tricks to achieve higher performance. Instead of drawing from back to the front we can draw from front to back. The advantage is, that we don’t have to draw lines to the bottom of the screen every time because of occlusion. However, to guarantee occlusion we need an additional y-buffer. For every column, the highest y position is stored. Because we are drawing from the front to back, the visible part of the next line can only be larger than the highest line previously drawn.

性能优化

当然，有很多技巧可以实现更高的性能。我们可以从前向后绘制，而不是从后向前。这样做的好处是，由于遮挡关系，我们不必每次都将线绘制到屏幕底部。然而，为了保证遮挡效果，我们需要一个额外的 y-buffer（y 缓冲区）。每一列都会存储最高的 y 位置。因为我们是从前向后绘制的，下一条线的可见部分只能比之前绘制的最高线更高。