Voxel Space：不到20行代码实现地形渲染

                                 Voxel Space：不到20行代码实现地形渲染

姓名：余玥     学号：16010188033

转载自http://blog.csdn.net/dev_csdn/article/details/78651264，有删节。

【嵌牛导读】：1992年，当时的CPU处理速度比现在的要慢1000倍，通过GPU加速当时还未问世，而且CPU也是无法承受的。3D游戏仅在CPU上进行计算，渲染引擎使用单一颜色对多边形进行渲染填充。

【嵌牛鼻子】：游戏/Voxel-Space/渲染算法

【嵌牛提问】：游戏里的地形渲染是如何实现的？

【嵌牛正文】：

Voxel Space

体素空间引擎的Web Demo

追溯历史

让我们把时间拨回到1992年。当时的CPU处理速度比现在的要慢1000倍，通过GPU加速当时还未问世，而且CPU也是无法承受的。3D游戏仅在CPU上进行计算，渲染引擎使用单一颜色对多边形进行渲染填充。

MicroProse于1991年发布的游戏Gunship 2000

同年NovaLogic也发布了游戏科曼奇。

NovaLogic于1992年发布的游戏Comanche

在我看来，当时这种图形出来以后简直叹为观止，它最起码提前了3年。用户可以看到很多的细节，比如山脉，甚至山谷的纹理，这是第一次有一个比较清晰的阴影。当然，它是像素化的，但那时候所有的游戏都是像素化的。

渲染算法

科曼奇使用了一种名为体素空间（Voxel Space）的技术，它和ray casting是基于同一个想法。因此，体素空间引擎是2.5D引擎，它不具有规则的3D引擎提供的所有自由度。。

高度地图和颜色地图

高度地图和颜色图是表示地形最简单的方法。科曼奇使用了1024 * 1024一个字节代表了高度地图，同样使用了1024 * 1024一个字节表示颜色地图，你可以在这个网站上下载。这些地图是周期性：

这样的地图将地形限制为“地图上每个位置一个高度” - 因此像建筑物或树木这样的复杂几何形状不可能表示出来。然而，色彩地图的一大优点是，它已经包含了色彩和阴影。体素空间引擎只需要颜色，在渲染过程中不需要计算光照。

基本算法

对于3D引擎来说，渲染算法非常简单。体素空间引擎负责渲染高度地图和颜色地图，并绘制垂直线。下图演示了这种技术。

清除屏幕。

为了保证遮挡从后面开始并呈现在前面。这被称为画家算法。

确定地图上的线，它对应于与观察者相同的光距离。考虑视场和透视投影(物体在更远的地方)

光栅线是用来匹配屏幕的列数。

从线段对应的二维地图中检索高度和颜色。

执行高度坐标的透视投影。

用透视投影中检索到的高度画一条垂直线。

核心算法以最简单的形式包含了几行代码(python语法)：

def Render(p, height, horizon, scale_height, distance, screen_width, screen_height):

# Draw from back to the front (high z coordinate to low z coordinate)

for z in range(distance, 1, -1):

# Find line on map. This calculation corresponds to a field of view of 90°

pleft  = Point(-z + p.x, -z + p.y)

pright = Point( z + p.x, -z + p.y)

# segment the line

dx = (pright.x - pleft.x) / screen_width

# Raster line and draw a vertical line for each segment

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])

p1eft.x += dx

# Call the render function with the camera parameters:

# position, height, horizon line position,

# scaling factor for the height, the largest distance,

# screen width and the screen height parameter

Render( Point(0, 0), 50, 120, 120, 300, 800, 600 )

添加旋转

按照上面的算法我们只能看到北面。不同的角度需要多行代码来旋转坐标。

def Render(p, phi, height, horizon, scale_height, distance, screen_width, screen_height):

# precalculate viewing angle parameters

var sinphi = math.sin(phi);

var cosphi = math.cos(phi);

# Draw from back to the front (high z coordinate to low z coordinate)

for z in range(distance, 1, -1):

# Find line on map. This calculation corresponds to a field of view of 90°

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)

# segment the line

dx = (pright.x - pleft.x) / screen_width

dy = (pright.y - pleft.y) / screen_width

# Raster line and draw a vertical line for each segment

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])

p1eft.x += dx

p1eft.y += dy

# Call the render function with the camera parameters:

# position, viewing angle, height, horizon line position,

# scaling factor for the height, the largest distance,

# screen width and the screen height parameter

Render( Point(0, 0), 0, 50, 120, 120, 300, 800, 600 )

更多的性能说明

当然，要想达到更高的性能，还有很多小技巧可以使用。

与从后面到前面绘制相比，从前面到后面进行绘制会更好。优点之一就是我们不必每次都因为遮挡而需要在屏幕的底部画线。但是，为了保证遮挡，我们需要一个额外的Y缓冲区。对于每一列来说，相当于y的最高位置已经存储了。因为我们是按照从前面到后面这个顺序进行绘制的，那么下一行的可见部分只能大于先前绘制的最高行。

详细的渲染程度。前面的细节渲染多一点，远处的细节渲染的少一点。

def Render(p, phi, height, horizon, scale_height, distance, screen_width, screen_height):

# precalculate viewing angle parameters

var sinphi = math.sin(phi);

var cosphi = math.cos(phi);

# initialize visibility array. Y position for each column on screen

ybuffer = np.zeros(screen_width)

for i in range(0, screen_width):

ybuffer[i] = screen_height

# Draw from front to the back (low z coordinate to high z coordinate)

dz = 1.

z = 1.

while z < distance

# Find line on map. This calculation corresponds to a field of view of 90°

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)

# segment the line

dx = (pright.x - pleft.x) / screen_width

dy = (pright.y - pleft.y) / screen_width

# Raster line and draw a vertical line for each segment

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, ybuffer[i], colormap[pleft.x, pleft.y])

if height_on_screen < ybuffer[i]:

ybuffer[i] = heightonscreen

p1eft.x += dx

p1eft.y += dy

# Go to next line and increase step size when you are far away

z += dz

dz += 0.2

# Call the render function with the camera parameters:

# position, viewing angle, height, horizon line position,

# scaling factor for the height, the largest distance,

# screen width and the screen height parameter

Render( Point(0, 0), 0, 50, 120, 120, 300, 800, 600 )

地图

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度

颜色，高度