云风的 BLOG: 高度图的压缩

3d游戏中的室外场景通常用高度图来表示，用一个二维数组来描述对应平面坐标的高度信息。

如果每个高度信息用一个 byte 来表示，很多情况下不太够用。因为对于很大的场景， 256 级的高度是远远不够的。通常我们会选择用 word 或者 float 来表示。

相比较而言，float 最为合适。这样，我们不太需要考虑缩放因子这个问题。但是 float 需要 4 个字节，这导致数据量很大。这里云风给出一个有损压缩方案用于压缩这些信息。

我们认为高度图上的信息大多数情况下是平滑过度的，这是这个有损压缩方案的前提。下面以一个 256x256 的高度图为例：

1. 生成 8 张序列图，分别为 128x128, 64x64, 32x32, ... 1x1 。生成的算法直接用上一级的图片每相临四个点取平均值记录下来。即，最后一张 1 像素的图上只有一个 float 信息，且为整个高度图的平均高度，这个值我们称作第 0 级高度图。下面，我们把 2x2 的图称做第1级高度图，4x4 的图称作第3级高度图，... ，原图称作第 8 级高度图。

2. 保存第0级高度图，即平均高度信息(最后一张 1x1 的图)

3. 迭代处理 1~8级高度图。对于第 n 级的高度图运算如下：
将这张图上，每相临四个坐标都对应到第 n-1 级高度图上一个坐标。每个坐标上的高度信息都减去其对应坐标的高度信息。这样把整张高度图转换为对应低一级高度图的差值。
扫描转换后的高度图，找到最小值(min)和最大值(max)，记录下来。
将所有差值信息[min,max]映射成 [0,255] 的整数，并记录下来。这样，我们就用 size*size+8 个字节记录下来这级高度图(size 为当前级的高度图的大小)。
用运算结果(size*size个 byte) 算回绝对高度信息，为下一级的运算做准备。

最后，我们就得到了一组用17 个 float 和 2x2+4x4+8x8+...+256x256=87380 个 byte 的数据(87448字节)共，用于表示 256x256 的高度图。相比较之前需要用 256x256x4=262144 个字节记录，压缩比为 87448/262144=33%

关于有损压缩后的误差，我没有做数学上的严格计算，用一张我们编辑器实际产生的比较复杂的地形图测试，误差为万分之一点五左右。从这个实际效果来看，效果是非常的好的。

如果一开始高度图就只有 256 级，我们把 [0,255] 的高度信息转换成 [0,1] 的浮点数后，依然可以用这个算法压缩。只不过，输出数据保存为 [0,15] 的整数即可。这样，每个字节可以保存 2 个点，既而可以得到一些压缩率。我用一些黑白图片做了测试，误差是非常的小的（肉眼不可分辨差别）。

这个压缩方案带来的额外好处就是，我们可以根据需要得到低精度的高度图。

写 blog 不是写论文，就点到为止啦 :) 恕不提供插图，代码，和更为精确的文字描述。

---

补充：<a href="http://blog.codingnow.com/2008/09/height_map_border.html)">高度图压缩后的边界处理</a>

Comments

应该说是用了小波(wavelet)的原理(Haar bassis). jpeg2000用的就是类似的东西

Posted by: Anonymous | (15) February 16, 2011 04:44 AM

空明流转这个小人也来了？

Posted by: 路过 | (14) October 10, 2010 11:39 PM

这不就和haar基的小波差不多咩。。。

Posted by: 空明流转 | (13) September 29, 2010 02:46 PM

就他马一个图象的平滑处理...日..

Posted by: 111 | (12) September 18, 2009 10:52 AM

呵呵，不错。再地形变化明显的地方会有些误差。。把大量冗余数据，抽取差值表示，再加上跌代处理。比较合算。 2x2 4x4 8x8是限制在2维上。如果是直线，则为2 4 8 3维场揍是2x2x2 4x4x4 8x8x8。

Posted by: happymonkey | (11) August 5, 2009 05:06 PM

这种算法充分利用了高度的局部性（locality）, 即一般高度图在小范围内的起伏不会很大，算法没有涉及到频域分析，没有冗长的推倒过程，一切理解都很intuitive，在理论和实际中都很有意义。这就叫把东西学活并活用。其实作为技术人员，最忌讳就是一碰到问题，就强般一些所谓“成熟”的方法出来，有时自己多想想，反而有可能开拓一片新天地。

Posted by: Kypck | (10) June 7, 2006 08:15 PM

您是把所有的时间都用在编程上了,但我觉得编程只是一个职业,如果把休息时间都搭上了才干得好的话这样的职业不好.我还是喜欢准点上下班,周末双休.我也是游戏程序员,呵呵.

Posted by: Anonymous | (9) March 9, 2006 01:16 PM

用 DXT 的算法是不恰当的，因为它损失了太多信息。高度图不是图片，不能用视觉效果作为评判标准。

Posted by: Cloud | (8) March 3, 2006 06:55 PM