« X Window 编程的两个小问题 | 返回首页 | C++ 0x 中的垃圾收集 »

模型顶点数据的压缩

缘起:听天下组的同事谈起,游戏的资源数据量太大,导致了加载时间过长,影响到了操作感。最终不得不对数据进行压缩。

当玩家配置的物理内存足够大时,往往资源数据压缩会适得其反。因为多出来的数据解压缩的过程会占用掉太多的 CPU 时间。物理内存够大的话,操作系统会尽量的拿出物理内存做磁盘 IO 的 cache ,即使你的程序不占用太多的逻辑内存,而反复从硬盘加载大块数据,也不会感觉到磁盘速度的影响。当数据量大一个一个临界时,被迫做不断的外存内存的数据交换,这个时候,数据压缩就会体现出优势。因为解压缩的 CPU 时间消耗是远远小于硬盘 IO 所消耗的时间的。

btw, 玩现在的 MMORPG 往往配置更大的物理内存得到的性能提升,比升级 CPU 或显卡要划算的多,就是源于这个道理。通常 MMORPG 都需要配置海量的资源数据,来应付玩家的个性化需求。

天下组的同事暂时只做了骨骼动作信息的压缩。这个这里暂且不谈,我想写写关于模型顶点数据的压缩。记录下这两天在思考的一个有损压缩算法。

通常模型中的顶点数据分两部分,顶点坐标和索引信息。顶点坐标表示了每个顶点在三维空间中的位置信息;索引信息用来表示模型的结构,当模型网格用三角形表示时,每个面就用三个顶点索引值来表示。


先来看顶点坐标数据的压缩。

原始数据通常是 3 个 float 表示一个顶点。最简单的想法是用 half float 来压缩,这个可以得到 50% 的压缩比。half float 基数只有 10bit 的精度,对于游戏这种对精度要求不高的应用,倒是也够了。

不过我们用一个简单的方法,就可以在保障大约 50% 压缩比的前提下,提高精度。

只需要把所有顶点坐标信息归一化,即,让所有坐标值都放到 [0,1) 中。这样,我们再用 16bit 的 short 保存一个定点数,可以得到全部 16bit 的精度,而不是 half float 的 10bit 。这样需要付出的额外代价,只是多记两组缩放和位移的数据(6 个 float ,24 字节)用于还原到原始坐标。

这一步做了以后,其实我们还有进一步压缩的余地。

大多数情况下,考虑到游戏中每个最小单位的模型的顶点数少不过几十,多不过上千。归一化以后,16bit 的坐标精度对于屏幕显示都是多余(想想屏幕才多少像素精度)。下面我们想办法把 16bit 的数据压缩到 8bit 。

顶点的次序其实是无关紧要的,我们先对顶点进行某种排序,让最终的顶点数组中相邻顶点的相对距离都尽可能的短。考虑到顶点并非随机分布在单位立方体中,而是符合某种规律。这样的顶点序列通常可以找到。我们并不需要找到最优解,用贪心算法+模拟退火应该就够了。

因为只能保证整个顶点序列中绝大多数顶点的相对距离较短,而无可避免出现少量特例。我们需要允许加入一些冗余的顶点来缩短相临顶点间的距离。这样,可以让整个顶点序列遵循一个合理的限制:最终所有相临顶点间的任意坐标轴上的距离不得大于 0.5 。

ok ,求出这样一个合理的顶点坐标序列后就可以开始压缩了。

我们让每个顶点坐标都表示成相对前一个坐标的差值,大多数值都会是一个相对比较小的数值。从二进制来看,高位会有一大串的零。接下来把这些值分为 5 类。

  1. 至少有 9 个连续零在高位 (000)
  2. 至少有 7 个连续零在高位 (01)
  3. 至少有 5 个连续零在高位 (10)
  4. 至少有 3 个连续零在高位 (11)
  5. 至少有 1 个连续零在高位 (001)

由于前面提到的限制,最高位一定是 0 而不会是 1 。(差值的符号位单独记录,而不采用补码)以上五类数值可以用变长的编码来区分。(我已经标在上表中)

8bit 中除去符号位和类型标记,有 7/5/3 个连续零的坐标差值(小于 1/128 、1/32 、1/8 )可以有 5 bit 的精度,另两种情况则有 4 bit 的精度。我们可以把第 5 种情况:至少有 1 个零的数据统一认为是冗余顶点,这样方便在最终解码的时候剔除掉。(即在顶点跨度很大时,强制添加一个冗余顶点)

7 月 21 日 补充:云风对以上的算法的实现和测试结果附在文章最后。


索引数据的压缩则必须是无损的,惯例是用 short 来表示 index 值,限制单个模型的顶点数在 64k 或 32k 之内。最简单的压缩算法是用变长编码,比如小于 128 的索引用一个字节,否则用 2 字节。

我猜想,如果顶点的排列是有一定次序,比较临近的索引值对应的顶点构成三角形的概率也比较大。那么,我们同样可以利用临近的索引值的差值来做变长压缩。或许可以效果可以更好一些 :D


模型数据中还有法线信息、贴图 UV 坐标、骨骼信息和权重等。这些的压缩方案,今天就不一一展开讨论了。


7 月 21 日 凌晨 补充:

花了一天时间把压缩以上压缩算法初步实现了。

归一化并用定点数表示的这一步,精度损失在十万分之一之下。(这一点,根据 float 的有效位数,心算也可以估算)所以,不必考虑这里的精度损失。

压缩到 8bit 的这个步骤比较复杂,主要是找到一个合理的顶点排列。这个问题其实是一个 TSP(货郎担问题)的变形,我选用模拟退火法来解。

输入数据是从项目中任意选择的一个人物模型中的一部分(max 导出的模型文件中任选的一组数据),有 268 个顶点(构成了 423 个面)。这个数量级的顶点数颇具代表意义。

如果用 float 保存这些顶点信息,需要 268*12=3216 字节。

压缩后,添加了 30 个顶点,共 298 个。每个顶点用 3 字节表示,加上额外的 6 个 float 值,一共为 298*3+6=900 字节。

压缩比为 900/3216=28.0% 。

平均的精度损失为 0.08% ,误差最大的几个顶点坐标的误差为 0.2% 左右。我个人认为,这个误差对于屏幕渲染完全可以接受。因为这样一个模型最终渲染到屏幕上不过几十像素宽,这个数量级的误差反应到屏幕上,甚至不会超过一个像素。

如果顶点数更多一些的话,由于分布在单位立方体中的顶点更密集,我想误差还会再小一些。

Comments

谢谢啦..

没看懂..能说说吗??
后面的实现能提供一下吗??

压缩算法不能过于复杂,要便于shader实时解压,目前GPU不支持位操作

还有很多别的方法,比如adaptive reconstruction, 还有增量等等,你不妨试试

很巧,我们也正设计类似的压缩算法.

静态模型怎么诌都可以。。。

很好的方法.

我又仔细想了下,这个算法确实可行,误差应该是可以接受的

马肝兄也来这儿逛啊

连续几个零指:16bit 定点数从高位向低位数有几个零。

由于顶点序列中相邻的坐标差都比较小,所以定点数都比较小,高位会存在很多零。顾而压缩之。

这样能行么。。。
寒一个~

有趣啊:) 后面一点没看懂,什么连续几个零的?

Post a comment

非这个主题相关的留言请到:留言本