众所周知，上世纪的计算机在性能上都没法跟现在的计算机比，可那时的CPU极慢，浮点性能极低，那时候的程序员一谈到除法就眉头紧皱（因为那会CPU算除法的开销很大），可人们却又想玩游戏，怎么办？
于是那时的程序员们想到了各种聪明的方法去实现各种图形学算法，这些算法的特点在于：很符合那时的计算机硬件特点（内存小，主频低，IO慢）。我前几个月无意在github上发现了一个渲染地形的算法，原文链接https://github.com/s-macke/VoxelSpace，觉得挺巧妙的，所以就实现了一下。原作者使用python实现的，20行代码，我觉得执行速度慢，用的C++，上百行（......）
这个算法的原理可以用如下这个动图描述，一个colormap，RGB，用于表示每个地形位置的颜色，一个heightmap，Grayscale，用于表示高度信息。感兴趣的人看明白主要思想后，也可以直接实现一个，所以这里直接贴代码好像没有意义：
我用的是SDL图形库（这个库入门很简单，最初都是国外人用，但最近越来越多的国内人也在用，负责处理在屏幕上绘制像素点级的操作）
贴整个程序意义不大，在这里就只贴上最主要的部分：
采样结构对象定义，每次对colormap和heightmap采样后返回一个这样的结构对象：
1 struct TerrainSample 2 { 3 double h; // height 4 uint8_t r, g, b, a; // color 5 };
然后是用于插值的lerp函数系列：
1 inline double lerp(double xmin, double xmax, double weight) 2 { 3 return xmin * (1 - weight) + xmax * weight; 4 } 5 6 // uint8_t 2d lerp 7 template <typename Ty> 8 inline Ty lerp2d_scalar(Ty a0, Ty a1, Ty a2, Ty a3, double xw, double yw) 9 { 10 double t1 = lerp(double(a0), double(a1), xw); 11 double t2 = lerp(double(a2), double(a3), xw); 12 double t3 = lerp(t1, t2, yw); 13 return (Ty)t3; 14 }
执行采样的时候，由一个类实例对纹理采样，返回一个TerrainSample结构，以下是实现该功能的一个成员函数：
1 TerrainSample sample(double x, double y) 2 { 3 TerrainSample ts; 4 x = x - floor(x); 5 y = y - floor(y); 6 if (tsq == Point) 7 { 8 int px = int(x * colormap_w); 9 int py = int(y * colormap_h); 10 ts.r = colormap[4 * (py * colormap_w + px)]; 11 ts.g = colormap[4 * (py * colormap_w + px) + 1]; 12 ts.b = colormap[4 * (py * colormap_w + px) + 2]; 13 ts.a = colormap[4 * (py * colormap_w + px) + 3]; 14 px = int(x * heightmap_w); 15 py = int(y * heightmap_h); 16 ts.h = heightmap[py * colormap_w + px] / 2048.0; 17 } 18 else if (tsq == Linear) 19 { 20 x *= colormap_w; 21 y *= colormap_h; 22 double xl = x - 0.5; 23 double xr = x + 0.5; 24 double yu = y - 0.5; 25 double yd = y + 0.5; 26 double xw, yw; 27 xw = (x - floor(xl)) - 0.5; 28 yw = (y - floor(yu)) - 0.5; 29 xl = xl - floor(xl); 30 xr = xr - floor(xr); 31 yu = yu - floor(yu); 32 yd = yd - floor(yd); 33 uint8_t p0[4], p1[4], p2[4], p3[4]; 34 double h[4]; 35 uint32_t *pixel = (uint32_t *)colormap; 36 split32(pixel[int(yu) * colormap_w + int(xl)], p0, p0 + 1, p0 + 2, p0 + 3); // xl,yu 37 split32(pixel[int(yu) * colormap_w + int(xr)], p0, p0 + 1, p0 + 2, p0 + 3); // xr,yu 38 split32(pixel[int(yd) * colormap_w + int(xl)], p0, p0 + 1, p0 + 2, p0 + 3); // xl,yd 39 split32(pixel[int(yd) * colormap_w + int(xr)], p0, p0 + 1, p0 + 2, p0 + 3); // xr,yd 40 h[0] = heightmap[int(yu) * heightmap_w + int(xl)]; 41 h[1] = heightmap[int(yu) * heightmap_w + int(xr)]; 42 h[2] = heightmap[int(yd) * heightmap_w + int(xl)]; 43 h[3] = heightmap[int(yd) * heightmap_w + int(xr)]; 44 uint8_t color[4]; 45 double height; 46 color[0] = lerp2d_scalar(p0[0], p1[0], p2[0], p3[0], xw, yw); 47 color[1] = lerp2d_scalar(p0[1], p1[1], p2[1], p3[1], xw, yw); 48 color[2] = lerp2d_scalar(p0[2], p1[2], p2[2], p3[2], xw, yw); 49 color[3] = lerp2d_scalar(p0[3], p1[3], p2[3], p3[3], xw, yw); 50 height = lerp2d_scalar(h[0], h[1], h[2], h[3], xw, yw); 51 ts.r = color[0]; 52 ts.g = color[1]; 53 ts.b = color[2]; 54 ts.a = color[3]; 55 ts.h = height / 2048.0; 56 } 57 return ts; 58 }
程序跑出来的几个结果图如下，渲染结果里可以大致看出山脉的起伏，640x480分辨率。
算法的局限性在于它只能渲染平视地形的情况，虽说可以加入俯仰角，但是本质上是个hack，不能上仰/下俯太多角度，否则会出现视图拉伸，整个图像会有平行四边形的那种切变特点，失真较大，而且对于近距物体的表现不佳，颗粒感较为明显，读者可以把对高度图的nearest filter改为bilinear filter试一下效果，也许会创造出其它的一些有趣效果。但是对于一个上世纪的地形渲染来说，这个小算法背后的想法还是挺cute的。