? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Voxel Space：不到20行代碼實現(xiàn)地形渲染
姓名：余玥 ? ? 學號：16010188033
轉(zhuǎn)載自http://blog.csdn.net/dev_csdn/article/details/78651264，有刪節(jié)。
【嵌牛導讀】：1992年，當時的CPU處理速度比現(xiàn)在的要慢1000倍，通過GPU加速當時還未問世，而且CPU也是無法承受的。3D游戲僅在CPU上進行計算，渲染引擎使用單一顏色對多邊形進行渲染填充。
【嵌牛鼻子】：游戲/Voxel-Space/渲染算法
【嵌牛提問】：游戲里的地形渲染是如何實現(xiàn)的？
【嵌牛正文】：
讓我們把時間撥回到1992年。當時的CPU處理速度比現(xiàn)在的要慢1000倍，通過GPU加速當時還未問世，而且CPU也是無法承受的。3D游戲僅在CPU上進行計算，渲染引擎使用單一顏色對多邊形進行渲染填充。
MicroProse于1991年發(fā)布的游戲Gunship 2000
NovaLogic于1992年發(fā)布的游戲Comanche
在我看來，當時這種圖形出來以后簡直嘆為觀止，它最起碼提前了3年。用戶可以看到很多的細節(jié)，比如山脈，甚至山谷的紋理，這是第一次有一個比較清晰的陰影。當然，它是像素化的，但那時候所有的游戲都是像素化的。
科曼奇使用了一種名為體素空間（Voxel Space）的技術，它和ray casting是基于同一個想法。因此，體素空間引擎是2.5D引擎，它不具有規(guī)則的3D引擎提供的所有自由度。。
高度地圖和顏色地圖
高度地圖和顏色圖是表示地形最簡單的方法。科曼奇使用了1024 * 1024一個字節(jié)代表了高度地圖，同樣使用了1024 * 1024一個字節(jié)表示顏色地圖，你可以在這個網(wǎng)站上下載。這些地圖是周期性：
這樣的地圖將地形限制為“地圖上每個位置一個高度” - 因此像建筑物或樹木這樣的復雜幾何形狀不可能表示出來。然而，色彩地圖的一大優(yōu)點是，它已經(jīng)包含了色彩和陰影。體素空間引擎只需要顏色，在渲染過程中不需要計算光照。
基本算法
對于3D引擎來說，渲染算法非常簡單。體素空間引擎負責渲染高度地圖和顏色地圖，并繪制垂直線。下圖演示了這種技術。
清除屏幕。
為了保證遮擋從后面開始并呈現(xiàn)在前面。這被稱為畫家算法。
確定地圖上的線，它對應于與觀察者相同的光距離?？紤]視場和透視投影(物體在更遠的地方)
光柵線是用來匹配屏幕的列數(shù)。
從線段對應的二維地圖中檢索高度和顏色。
執(zhí)行高度坐標的透視投影。
用透視投影中檢索到的高度畫一條垂直線。
核心算法以最簡單的形式包含了幾行代碼(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 )
添加旋轉(zhuǎn)
按照上面的算法我們只能看到北面。不同的角度需要多行代碼來旋轉(zhuǎn)坐標。
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ōu)點之一就是我們不必每次都因為遮擋而需要在屏幕的底部畫線。但是，為了保證遮擋，我們需要一個額外的Y緩沖區(qū)。對于每一列來說，相當于y的最高位置已經(jīng)存儲了。因為我們是按照從前面到后面這個順序進行繪制的，那么下一行的可見部分只能大于先前繪制的最高行。
詳細的渲染程度。前面的細節(jié)渲染多一點，遠處的細節(jié)渲染的少一點。
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 )
