generating:Terrain Generating

在飞行模拟中或在些需要实时产生地形游戏中用了Voxel技术Voxel这个词从Pixel(像素)中来即“volumetric pixel”如果Pixel代表了 2维世界中各矩形那voxel就是 3维世界个立方块如图:
( i have time i\'ll make better pictures)


Voxeldata就是由x(宽度),z(深度从屏幕往里)加上高度y组成

在生成地形时光有这些粒粒还不行要看上去象地形还得Render它们可用区别颜色表示地形高低和远近有几种思路方法可以render它们光线跟踪(ray tracing)就是其中种光线跟踪基本思路方法是从视点投射束光线(ray casting)直到这束光线被障碍物阻挡为止然后向另个方向再投射束光线依此类推最后光线中止点集合就构成了地形在飞行模拟中多用这个思路方法在如Quake/Doom类游戏中也用了光线跟踪

如图 2


把 3维ray casting拆成 2维就有了图 3Y-Z和图 4X-Z:


我们用到数学只是 3角比例关系(图 5)


这个算法可以这样来表示:
p=当前点
while (不是屏幕上最后点)
{

从视点投射光线去p点
穿过p点后光线继续
( 光线碰到障碍物)
{ 以障碍物位置区别根据高低远近给于p点以区别颜色}
p指向下个屏幕像素

}


飞行模拟中地形模拟就是这么回事简单不简单？(说“简单”)如果你回答是“复杂”这里有个对简单地图Render 例子

现实和理论总有区别其结果能差好多好多倍比如在理论上我是个好人而在实际上我是个....hum....很好很好人当光线跟踪被军方使用时他们用了几台超级电脑系统才能使画面保持实时效果在我们PC based游戏系统上要能维持20fps以上连续画面在换帧的间完成所有地形光线跟踪是很困难因而在PC game里我们有更好光线跟踪近似算法实际效果比标准光线跟踪算法快约千倍

标准光线跟踪思路方法慢原因是对屏幕上每个像素点都要投射次光线并做相应运算在典型640X480分辨率中共有307200个像素需要投射307200条光线并做计算这些计算花去了太多时间但如果我们仅仅投射少量光线比如说640条其余让它自动生成就会快得多

简化思路方法是先投射条光线去屏幕最下面像素等光线碰到地形障碍物后不是再从视点投射另条而是让光线自己顺着地形起伏爬所以对每列屏幕像素只需投射条光线在640x480例子里我们只要投射640条光线(图 6)


那么怎样才能让光线爬行并返回我们要数值呢？这里有些数学窍门技巧经过这些数学运算可以得出这样个结论:(图 7)


最后我们有了个优化算法:
for (像素列从0到639)
{
　　 //由于在SINCOS运算会耗去50-80个CPU时钟数所以事先
　　 //算好每个角度正余弦值放在COS_LOOKSIN_LOOK表中
　　 //用时差表就快多了
　　 dx=COS_LOOK[当前角度]；
　　 dy=SIN_LOOK[当前角度]；
　　 dz=斜度*(试点夹角-屏幕高度)；
　　 画点；
　　 当前角度递减--；
}



如果你是个“拿来主义者”或对算法本身不感兴趣下面子程式可以整个抄去你主程式
这里是个完整Render地形子程式
这个子程式原作者为David Lindauer,后经过许多人许多次修改最后定型

void Render_Terrain( vp_x,
　　　　 　　　　 vp_y,
　　　　 　　　　 vp_z,
　　　　 　　　　 vp_ang_x,
　　　　 　　　　 vp_ang_y,
　　　　 　　　　 vp_ang_z,
　　　　 　　　　 UCHAR *dest_buffer)
{
// this function renders the terrain

//at the given position and orientation


xr,yr,
curr_column,
curr_step, //current step ray is at
raycast_ang, //current angle of ray being cast
dx,dy,dz, //general deltas for ray to move from
//pt to pt
curr_voxel_scale, //current scaling factor to draw each voxel line
column_height, //height of the column ersected and being rendered
curr_row, //number of rows processed in current column
x_ray,y_ray,z_ray, // the position of the tip of the ray
map_addr; //temp var used to hold the addr of data s

CHAR color, //color of pixel being rendered
? dest_column_ptr; //address screen pixel being rendered
//convert needed vars to fixed po

vp_x=(vp_x<<FIXP_SHIFT); vp_y=(vp_y<<FIXP_SHIFT); vp_z=(vp_z<<FIXP_SHIFT);

//push down destination buffer to bottom of screen dest_buffer (SCREEN_WIDTH * (SCREEN_HEIGHT-1));



//compute starting angle raycast_ang=vp_ang_y+ANGLE_30;

//cast a ray for each column of the screen for (curr_column=0; curr_column < SCREEN_WIDTH-1;curr_column) { //seed starting po for cast x_ray=vp_x; y_ray=vp_y; z_ray=vp_z;

//compute deltas to project ray at, note the spherical cancelation factor dx=COS_LOOK(raycast_ang)<<1; dy=SIN_LOOK(raycast_ang)<<1;

//dz is a bit complex, remember dz is the slope of the ray we are casting, //therefore, we need to take o consideration the //down angle, or x axis angle, the more we are looking down the //larger the initial dz must be dz=dslope*(vp_ang_x-SCREEN_HEIGHT);

// re current voxel scale curr_voxel_scale=0;

//re row curr_row=0;

//get starting address of bottom of current video column dest_column_ptr=dest_buffer;

//enter o casting loop for(curr_step=0;curr_step<MAX_STEPS;curr_step) { //compute pixel in height map to process //note that the ray is converted back to an //and it is clipped to stay positive and in range xr=(x_ray>>FIXP_SHIFT); yr=(y_ray >> FIXP_SHIFT); xr=(xr&(HFIELD_WIDTH-1)); yr=(yr&(HFIELD_HEIGHT-1)); map_addr=(xr+(yr<<HFIELD_BIT_SHIFT));

//get current height in height map, note the conversion to //fixed po and the added multiplication factor used to //scale the mountains column_height=(heigth_map_ptr[map_addr]<<(FIXP_SHIFT+TERRAIN_SCALE_X2));

//test column height is greater than current voxel height //for current step from initial projection po (column_height>z_ray) { //get the color for the voxel color=color_map_ptr[map_addr];

//draw vertical column voxel while(1) { //draw a pixel *dest_column_ptr=color;

//now we need to push the ray upward _disibledevent=>

//now translate the current z position of the ray by //the current voxel scale per unit z_raycurr_voxel_scale;

//move up _disibledevent=>

//test we can out of the loop (z_ray>column_height); }//end while

}//end

//update the position of the ray x_raydx; y_raydy; z_raydz;

//update the current voxel scale, remember each step out //means the scale increases by the delta scale curr_voxel_scaledslope;

}//end for curr_step

//advance video poer ot bottom of next column

dest_buffer;

//advance to next angle raycast_ang--;

}//end for curr_col

}//end render_terrain

延伸阅读

• 2009-2-12-- terrain:地形渲染 terrain render