上一篇提到了BC7的结构，以及压缩的巨大计算量。本篇将阐述FasTC算法，一种可以快速压缩BC7的方法。
慢的根源
之前讲过，传统BC7压缩之所以慢，是因为需要穷举所有的可能性，从中挑出最好的一种。在这种情况下，最快的实现靠的是GPU的巨大并行度，虽然能解决问题，但效率仍然很低，并依赖于D3D11的CS。
审视BC7的压缩步骤，可以看出首先有64个partition，8个mode，有的mode有2种颜色编码和3种旋转。很显然，占决定性作用的是64个partition。如果能有个算法不需要穷举就能决定一个partition，就能迅速把计算量减少几十倍。
Partition的确定
那么有没有可能直接确定出partition呢？09年刚完成BC6H/BC7 DirectCompute Encoder Tool的时候我就想过这个问题，当时觉得可以用聚类的方法得出如何partition，至少可以得出有几个subset。比如，上红下绿的block就不需要去试左右分割的partition了。可惜后来没有继续想下去。Pavel Krajcevski在2012年完成了一个称为FasTC的算法，发表在I3D 2013上。该算法的主要加速就来自对block中的texel进行聚类，从而不需要穷举就得出partition，和我的想法不谋而合。FasTC算法不单可以用于BC7，还能扩展到其他带分区的纹理压缩，比如BC6，ETC1，ETC2等。这个项目现在已经在github上开源了。
但是，这篇文章本身有多个不足之处，严格按照它的流程来的话，压缩很多实际中的纹理都会失败。另外，它的代码实现也非常差，需要做很多修改才能真正实用起来。下文会提到一些改进的方法。
算法的框架
FasTC的大体框架如上图所示。下面我会解析每一个步骤。
Uniformity check是检查一个block是否是同一种颜色。是的话直接查一个预计算的表就可以得出编码后的字节流。Transparency check检查一个block是不是全透明的。这实际上是错误的，因为A=0不等于RGB通道就应该被清除。这是算法上的一个问题，必须要修改才行。
Partition estimation是整个算法的核心。它对block的颜色在RGB空间进行直线拟合，如果得到的是N条直线，就表示这个block需要被分成N个subset。根据每个subset在block上的分布可以找到最接近的partition。
比如上图的两个block，分别可以拟合出两条直线，并直接得出它们分别是partition 31和partition 3。
分好subset之后，该算法再次对每个subset做一下uniformity check，颜色都相同的话找查找表。否则估计出两个端点的颜色。由于已经有了拟合的直线，相当于已经有了端点的初始值。只要迭代优化出最佳的端点就可以了。这一步和BC1的做法一样，用牛顿下山法，PCA，最小二乘法都行。
其他的东西还是省不了，照样需要穷举所有的mode，颜色变吗方式和rotation。但运算量已经减少了16-64倍。在中等质量下，已经和原算法的GPU加速后的速度类似了。纯CPU的好处就是可以再任何平台上跑，包括移动平台。并且，理论上这个算法也可以用GPU加速，再一次提高上百倍的速度。
吐槽
介绍完算法框架后，该论文就开始了无数的废话。比如block之间可以并行计算（废话，谁都知道）。比如压缩速度和CPU核数成反比（废话，block之间无关联，可以完全并行）。在和其他算法进行比较的环节，它能和DX CPU以及NVTT比信噪比和速度，却忽略了GPU的实现，甚至连提都不提。显然是不敢比，一比这两方面都优势。适用性好的优点在论文里却基本没提。
在实现上，它的代码有无数的bug，需要用它来压缩各种图片进行测试，一点点修正。并且，那个代码好像由两个水平和风格迥异的人写成。一个精通位运算，能把复杂的表达转化成一组位运算得出结果。另一个连&都不会，取int的某个bit居然用的>>和%。还有一些很令人崩溃的写法，比如把两个int转成float，做一些绝不会溢出的相加相乘后转回int。单单把这些低级错误改好，速度已经提升30%以上。Intel用同样的算法，配合SIMD和多线程优化，直接做到毫秒级的BC7压缩。
总结和未来
目前KlayGE里根据FasTC的框架，实现了一个BC7的编码器。在D3D11的平台上，diffuse, specular, emit都默认设置成压缩到BC7格式。可以方便地使用。
以后我可能会把这个框架扩展到ETC上，毕竟ETC也是一个多模式分subset的压缩，按理也适用于这个方案。另外，扩展到HDR就能压缩BC6，改动量应该也不大。
近几年内，纹理压缩的最高境界应该是ASTC。它可以压缩各种类型、各种通道数、各种位数的纹理。OpenGL 4.3，OpenGL ES 3.0和D3D 12都支持ASTC。如果要把FasTC扩展到ASTC，可能还需要打破4×4 block的假设。但FasTC这个方向是肯定没错的。
Comments