云风的 BLOG: 高度图压缩后的边界处理

几年前我曾经写过一篇 blog 介绍我发明的一种高度图压缩算法。最近几天，我将这个算法用于目前正在开发的 engine ，如之前所料，效果不错。由于数据被压缩，更改善了资源加载的速度。并在同等内存条件下，让用户得到更高的体验。（这是因为，现代操作系统，都会把暂时不用的物理内存全部用于磁盘缓存，更小的文件体积同时意味着在同等内存条件下能缓存更多的数据）

因为我们需要做动态地形数据的加载，所以地形高度数据也被切割成了一小块一小块。采用这个算法后带来的一个问题是：由于压缩有数据损失，两个相临块之间不能严丝合缝的衔接在一起。

为了解决这个问题，这两天想了好几个方法。

相临的数据块的接缝上，每个顶点被拆分成了两个。数据未压缩前，拆分出来的顶点值应该完全相等。最容易想到的方案是，每次加载完一个地形块，就去查看周围的块是否有加载入内存，如果有，就把邻接边的数据 copy 一份过来。

但这个方案增加了数据间的耦合度，同时导致在数据读取层的代码需要从更高的层次上获取数据。这会破坏 engine 的设计，故而放弃这个方案。

另一个方案是将边界上的一圈高度信息，以无损方式额外保存。但是我们每个地形块的数据本身不多，这将会极大的损失好不容易获得的压缩比。

今天白天，我一直在想如何有效的保存轮廓信息。想到了一些方法会轮廓上的顶点增加额外的精度（大约每个顶点多使用一个字节）。代码写了一堆，实现出来却不太满意，因为直觉告诉自己，我把问题弄复杂了。

晚上去健身房活动了一下，回来的路上突然灵机一动，想到一个最为简洁的方案。

其实，不应该从提高边界上顶点的精度（甚至是无损）这方面努力。我们需要的仅仅是让邻接的地块可以无缝连接，也就是说，邻接线上的顶点高度值应该一一相等。

其实，让我们降低结果浮点数的精度就够了。关于实际操作的方法，很早以前我在留言本上发过帖子。Blog 上也有一个帖子讨论过 EPSILON 取值的问题

这次我这样实现（把要降低精度的浮点指针传入即可）：


static __inline void
reduce_precision(float*fdata)
{
    uint32_t *d=(uint32_t *)fdata;
    *d=(*d + 0x8000) & 0xffff0000;
}

ps. Spore 是个好游戏。

9 月 6 日补充：这个方法对于在 0 附近的数值为有问题，因为它不能处理正负号所以应该要注意。解决方法很简单：发现数值绝对值小于 1 即浮点指数是负数的时候，把值先加一再做上述处理，然后再减一。

另外对于跨越指数边界的时候可能会出现问题，比如一个值的底数是 1.11111111111 而另一个是 1.000000000 ，而指数差了一位。解决这个问题应该手工判断进位。

有人提到法线，其实法线是按常规方法从顶点高度中推算出来的。可以多保存一圈顶点。也可以在轮廓上用较少顶点来计算。法线的细微差别不会对视觉上有太大影响。（从我们的渲染结果上看是这样）

9 月 10 日再补充：如果只是想去掉绝对数字上的浮点精度，比如去掉十进制小数点大约 4 位以后的偏差。可以如此：

a+=8192.0f; a-=8192.0f;

这样便可以将 a 降低精度。原理不详述。另外在写程序的时候应该想办法防止编译器优化掉上面的代码。

Comments

哎。其实有几个人能自己思考出类似jpeg的算法呢。这才是关键问题。云风做到了啊，这才是搞技术的。

Posted by: varg | (20) July 16, 2011 12:44 AM

听说网易买了UT的引擎啊。

Posted by: Anson Ling | (19) October 13, 2008 02:05 PM

chenyujie ,我怎么感觉你说话的口气就像你很有能力和魄力似的？

Posted by: Jet Wong | (18) September 23, 2008 02:41 AM

我做什么事，怎么做事。跟老板有没有钱关系不大。做了这些年，我早就不需要为钱去做事。不管是为自己的钱还是为别人的钱。 chenyujie 不管你信不信，我相信你没有能力评价我做的事情。（暂且模仿一下您的口气:) ）如果只是抱着玩的态度，我完全不必在网易为别人打工。花自己的钱衣食无忧的玩乐比花别人的钱要爽的多。和老气横秋的小朋友讨论这种问题，看来我最近的确是放松啊。

Posted by: Cloud | (17) September 20, 2008 09:14 PM

呵呵，挺年轻气盛的嘛没事，反正你们丁老板有钱，你也有追求，折腾呗，没事干一遍一遍重构“引擎”，锤炼你的内存分配，gc模块，替换你同事的代码呗，技术人员这么有时间，衣食无忧的玩乐也是难得的事情，更难得的是，你们公司自己人也评价“他是在玩呢”。我在此立贴为据，再过3年，我相信你们还搞不出成熟的东西来，顶多就是研究了一些底层的技术而已，离一个“引擎”还差的远。专门做一项技术没有什么难度，要把所有这些东西揉和起来顺利工作才是难度，云风不管你信不信，我认为你没有能力掌控一个如此庞大、复杂的系统，不管从你的管理方法，你对待项目的态度，还有你本身专注的领域。我也不和你争论什么是“引擎”，我是外行嘛，反正丑媳妇迟早要见公婆的，是骡子是马拉出来溜溜，最后你需要跟你的游戏用户解释这不是引擎，那不是引擎，以你在国内游戏界的威望，fans对你的引擎要求估计不低啊，呵呵。

Posted by: chenyujie | (16) September 20, 2008 07:29 PM

高度图的压缩，并不是 engine 的一部分。因为，engine 需要处理的是高度图里的数据，而这些数据如何编码则不关 engine 的事情了。不做压缩，只是占用硬盘或内存大一些，但丝毫不影响 engine 的工作。如果楼下的稍有些开发常识，就知道，这些枝梢末节的工作正是在 engine 开发完成后才应该去做的。这也是为什么设计压缩算法是在两年前，但是现在才实现的缘故。有如开发一个操作系统，图形窗口界面跟操作系统内核一点关系都没有。当然外行会认为图形窗口界面是系统内核的重要组成部分。我想若是这个外行异想天开的要做一个比 Windows 要酷的操作系统，恐怕第一件事情是去考虑窗口界面上的按钮应该是做成圆角的还是应该加一点毛玻璃效果吧。

Posted by: Cloud | (15) September 19, 2008 07:55 PM

我不得不说，云风是个技术呆子，你们的engine应该是3年前就开始设计了，到今天还在捣鼓地形高度图，我真是佩服云风的速度啊。拜托以后云风不要张口闭口“我们的engine”，我看就是些凑不到一块去的components而已，离能够在上层编写游戏还早呢。云风我看就是网易的技术广告旗帜，飘飘就算了，真的让云风担纲做产品、引擎，真够老板受的~~~~

Posted by: chenyujie | (14) September 19, 2008 04:28 PM

你的压缩算法比起标准的 jpeg 有什么优势？压缩比更高么？和 jpeg-2000 比起来呢？

Posted by: david | (13) September 17, 2008 05:12 PM

资源数据加载和解析应该是一个独立过程。如果在此过程中需要引用其它资源数据的一部分，这就导致了跨层次的耦合。的确在理论上，每块地形块在加载时，和它邻接的地形块要么存在于内存，要么不用关心边界衔接。但并不是存在于内存的数据就可以去使用。那会增加工程上的复杂度。为诸如多线程加载等添加麻烦。另，地形数据加载后，会生成 vertex buffer 灌到显存中，重新读回是很低效的。

Posted by: Cloud | (12) September 10, 2008 05:54 PM

为了避免影响已经渲染的边界多边形，可以采取这样的策略：当加载一个新的块时，如果其相邻块已经加载则使用相邻块的边界顶点信息，对于块的角点(可能三块或更多块共点)需要检测所用共用的块是否有已经加载的。另外，纯粹的一个胡思乱想：也许确实可以不存储边界的两份信息，而在相邻块加载后生成一个连接缝，使用相邻两块的边界点就可以了。对于渲染部分，多了一个连接缝需要渲染并不会有多大影响，毕竟总的多边形数量不会增加。

Posted by: plainroc | (11) September 10, 2008 09:24 AM

地图块的边界出现在屏幕中时一定这个边界两边的地图块都已经加载，所以我觉得可以在加载到内存时修正可见边界的顶点值(取相邻两个地图块的同一个顶点值的加权均值，我猜想平均值应该就可以)，修正之后再上行渲染。这个方案理论上会对已渲染的临近边界的多边形造成加载前后的不一致，但是这个不一致应该很小，不会影响玩家的视感。

Posted by: plainroc | (10) September 10, 2008 09:09 AM

@ 3 楼，法线多保存一圈顶点即可。其实不额外保存，在轮廓上少计算一个附近顶点的影响，对视觉效果也无太大影响。就是程序算法要做特殊处理。 @ Zhe, 邻接边上两边上的点逻辑上是同一个点，由于压缩损失才使值不相同的。指数通常是相同的。（否则值会差两倍以上）有种特殊情况我补充里列出来了，实际中并没有遇到。 @ Zwinger, 两边都必须保存边界顶点。因为显卡渲染的是面，不是点。除非加载以后再根据内存中邻接信息把点补上。最终那些点的信息一定要有的。做过 3d 游戏的人自然会明白。另外，这个算法对某些特殊情况处理的并太好，我周末想办法再改进一下。

Posted by: Cloud | (9) September 6, 2008 01:54 AM

用闭开区间就可以解决了。

Posted by: Zwinger | (8) September 5, 2008 12:44 PM

有点像adpcm

Posted by: liuzhi | (7) September 5, 2008 10:32 AM

按照文中的描述，似乎是地图切割的那条线上的顶点数据被保存了两份（两侧的块中各一份）？不如干脆只保存一份……只要精度损失不太大，那么地形的变化也应该不大。

Posted by: sjinny | (6) September 5, 2008 09:49 AM

你好云风，一直很关注你的ＢＬＯＧ，刚才在大话２里挂机，突然有个关于游戏安全的问题，想告诉你，希望大话２包括网易的所有游戏能修改下，这个游戏安全ＢＵＧ，可以饶过将军令盗号，不知道你有没发现，比如说现在大话２出了体力系统，当游戏玩家的体力因为炼话生产装备等因素导致体力不足，他们就需要挂机，再或者玩家摆滩的时候也多数是挂机的时候．而挂机的时间，一般都是玩家睡觉或不在电脑前的时候，而这个时候游戏窗口和电脑是无人职守的，那怕是玩家的帐号绑定了将军令等可以避免帐号被盗的东西，在玩家睡觉，电脑无人职守的情况下，如果该玩家电脑被种植了远程控制木马，那么盗号者完全可以利用该玩家睡觉挂机的时间，远程控制玩家的桌面，比如：将键盘记录到的解锁码输入，将玩家的一些值钱的装备＼宝宝拿去和别人交易等等，因为很多玩家为了使用方便，并不会将值钱的装备和ＢＢ加时间锁，一般我用将军领｀包括我自己的号，我号上装备价值差不多１万多，我也不加时间锁，因为有将军领，但是解锁码是没有防护的，一般玩家会选择键盘输入，而这个时候被记录解锁玛则很正常，而通过远程控制木马，在玩家挂机的时候，就可以饶过将军令等密保程序盗走玩家的装备和宝宝！　我觉得你们可以做一个挂机的ＮＰＣ，比如这个ＮＰＣ的功能可以设置成：设置挂机时间，比如我现在早上８点半离开电脑，晚上８点半回来，那么我就设置挂机时间为１２小时，１２小时内我身上的所有加锁装备和ＢＢ全部不允许交易！如果是想更方便玩家，可以直接在人物状态烂，加个挂机的栏目，然后加个密码，要求玩家必须输入将军领动态密码，才可以解锁，这个可能涉及到数据库调用的一些烦琐问题，可以改成要求输入一个只允许用软键盘输入的密码，这样可以有效防止在使用了将军令，而挂机这个时间的疏忽导致玩家被盗！

Posted by: xiumu | (5) September 5, 2008 08:17 AM

似乎是，变位长？那么这么拼接，需要知道最小有效位长……相邻几图边界的幂差距不能太大啊

Posted by: Zhe | (4) September 5, 2008 08:00 AM

看了看高度图压缩算法的原文,有一个问题,法线怎么保存呢?还是根据高度图计算得到?那不是也要增加耦合性?

Posted by: Anonymous | (3) September 5, 2008 07:50 AM

沙发：engine什么时候完工？

Posted by: rayment | (2) September 5, 2008 07:46 AM

沙发：engine什么时候可以完工？

Posted by: Anonymous | (1) September 5, 2008 07:42 AM