云风的 BLOG

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

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

原始数据通常是 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% 左右。我个人认为，这个误差对于屏幕渲染完全可以接受。因为这样一个模型最终渲染到屏幕上不过几十像素宽，这个数量级的误差反应到屏幕上，甚至不会超过一个像素。

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