云风的 BLOG: 通过斜切变换 2d sprite 提高装箱率

现代 2d 游戏的图形地层绝大多数也是基于 3d api 实现的。为了提高性能，通常要把若干图元 (sprite) 装箱在整张贴图中。这个装箱过程可以是在线下完成，也可以是在运行期来做。

TexturePacker 就是做这件事的优秀商业工具。不过我认为把它放在开发工具链中还有一些不足。图元的装箱和根据装箱结果合成贴图是两件事情，如果我们是手工操作，合在一起完成当然方便；但如果是在自动化流程中，分开独立完成更好。因为迭代开发过程中，每次重新打包资源，都只会修改少部分图元，且图元的大小未必会改变。如果大小不变，就不必重新做装箱运算。

如果部分修改图元，则合成贴图的过程有可能能减少运算过程。通常我们需要对最终的贴图做一次压缩，生成类似 ETC 的压缩贴图类型，这是极消耗 cpu 的。而 ETC 压缩格式是基于 4x4 的区块独立压缩，只要保证图元尺寸是 4 的倍数、就可以先压缩，再合成。这样，没有修改过的图元就可以不必重新运算，直接从文件 cache 中读回。

有些时候不合成、仅保存装箱结果更适用。可以在运行时根据 altas 数据把分离的图元装载在贴图中。分开打包独立的图元资源更适合游戏更新。

第二，在提高装箱利用率上面 TexturePacker 做了很多的努力。很多 sprite 的边角会有大量的空白，仅仅按轴对齐的四边形包围盒裁剪还是浪费太大。它的最新版本支持了多边形装箱、即尽可能的把边角都裁剪下来。这种做法的代价是增加了运行时的多边形数量（对 2d 游戏来说，通常不太重要），但让装箱边角余料可能多填一些小 sprite 进去。

但我认为其实还可以找到更多方法。

这篇 blog 就想谈谈最近我在为公司新的 2d 项目完善 ejoy2d 的工具链，编写装箱工具时，做的一些工作。

我发现，有很多 sprite 会在边角留下很多空白，虽然打包压缩后并不多占安装包空间，但是减少了贴图利用率（进而增加了运行时的显存/内存负担）。如果我们能稍做变形，就可以在不损失信息量的前提下，用更小的矩形包容下。比如我们上个项目中有下面这么一张（左）图，这把武器是按透视角度斜着创作的，在左下和右上都留下了空白。如果我们做一个斜切变换，就能变为右图，图元面积从 358x305 变为了 149x284 ，面积减少到 38.8% 。

由于线性过滤的关系，图在处理后有点糊，可以做一次锐化： weapon.sharpen.png

这个方法很容易想到，我们在之前的项目中却是人工制作的：美术先在图形处理软件中对图形做变形，然后再通过编辑器变回来组装成游戏里用的状态。明显这个过程是可以由程序自动化完成的，难点在于找到算法。我在这几天实现的图元打包工具时采用了一个时间复杂度为 O(n^2) 的算法来求最优解。但实际上算法优化空间很大，我认为理论上是能做到 O(log N) 的。好在通常 n 不大，整体运行时间不长。而且单个图元做完一次就可以 cache 结果，不修改图元就不必重新运算，所以这个优化可以留到后面慢慢做。

算法是这样的：

我们先尝试对图在水平方向做斜切，也就是按比例把每条水平扫描线做平移，即把矩形拉扯为一个平行四边形。在这个过程中，每个像素都是保留的，有效像素数量没有改变，所以信息量是一致的。同时，每移动一个像素，就尝试在垂直方向做同类处理，当我们尝试完所有的 x,y 方向的变幻组合，每种情况下都计算一下 AABB ，就能找到最佳参数。ps. 由于这个过程是线性变化的，所以未必要逐一尝试。

我试了另一张我们游戏中的图片，处理结果和美术手工处理的几乎一致（程序计算出来的甚至比美术凭经验做出来的略好一点）。

但不是所有的图片都适合做这样的处理，比如常见的菱形手绘地块，由于变形太多，虽然像素都保留了，但运行时绘制的时候因采样算法的影响，图像糊得比较厉害。

这和图片旋转会糊掉的道理是一样的。这种可以在打包工具中标记出不做处理（美术给图片加个指定的后缀供打包程序识别）。另外，如果运行期不需要缩放的话，用 GL_NEAREST 采样比用 GL_LINEAR 更好。

ejoy2d 在设计贴图数据格式的时候就考虑了这种需求。sprite 在 altas 数据中描述的是贴图上的四个顶点坐标映射到屏幕上的四个顶点位置，而没有像其它 2d 引擎那样只描述了一个偏移量。所以我们只需要做逆运算计算出变换过的图元的四个顶点对应在屏幕上实际的四个角即可。

算法的实现在我正在开发的贴图打包工具里单列为一个 lua 的 C 模块，可以方便的由工具链调用。实现并没有优化，主要是希望简单明了。注：这个工具尚在开发中。

另外，我们还可以结合通过适当的切割来进一步提高利用率。比如一张 100x100 的图元，很可能切割成左右 50 像素的两半后，每一部分都小于 100 像素。（单个 sprite 由多个区块构成，在 ejoy2d 的底层也有天然支持）不过要注意：当把 100 像素宽的图元切割为两部分时，需要两侧都留边。即每边都是 51 像素，多保留对面的一个像素宽，这样运行时拼接起来才不会有缝。至于切割线的最优位置（未必在正中间），也可以通过穷举来计算。

Comments

凸包+旋转卡壳[思考]

Posted by: farter | (25) December 18, 2018 10:28 AM

@mColorfulCloud 不好意思，我骂那个"笑死人",不是你,博主这个技术帖子要不是感觉太搓，我是不想讲什么的，必竟一个大牛不去研究国外一手论文，整天整这些没用的，我随便一个方法就可以让整个2D游戏占用的贴图内存是恒定的，哪里来需要那么麻烦去抠资源？而且一个批次画完所有物件。

Posted by: A | (24) September 28, 2018 11:03 PM

@mColorfulCloud 你才是个脑残，我自己的实现方式不知道比这种方法高效多少倍。即使是皇室战争这些批次也是很多的，而且也会切换多次贴图，iphone4这种级别手机卡的很。比我的真3D游戏都卡。你嘲笑我抓祯，难道我的想法会比这个费内存？不去研究下两者技术的优劣。

Posted by: A | (23) September 28, 2018 10:51 PM

cloud 和A讲的是不同的东西。一个讲贴图的处理，一个讲效果的实现。A讲的是一个看上去是3D的东西在游戏里其实不是3D的，本来由3D的高模渲染后得到了一张贴图，然后这个贴图帖在低模，甚至面片上。只要camera的角度跟渲染时一样，哪怕在面片上，看上去的效果跟3D高模渲染的效果也一样！这样极大的节省了开销，当然，这个限制于固定视角的游戏。cloud单纯讲贴图资源的处理.本人虽然几年游戏编程但图形基础极差见识浅陋表达有限，但问题在这里，讨论下也未尝不可。

Posted by: mColorfulCloud | (22) July 18, 2018 02:59 PM

这个叫 A 的怕是个脑残吧。还通过抓帧的方式居然来嘲笑别人直接能解开资源的人。还“我认为”认你妈个头哦。傻逼都知道是美术3D渲好的动画帧。真不想骂人实在看不下去这SB

Posted by: 笑死人 | (21) March 10, 2018 06:05 PM

以前 sc 文件就是长度 + lzma prop ，今天下载了个 cr 新的包打开看了一眼，无非加了个很简单的自定义文件头。后面内容任然是 lzma 压缩的。改动了一下之前写的解压脚本，处理了一下文件头就解开了。不懂的话，态度好点请教。我事情忙，不想再在这里花时间了。 ps. 其实 github 上解 supercell 资源文件的项目一大堆，从旧版到新版的都有。伸手党也要学会 google 吧。

Posted by: Cloud | (20) January 28, 2018 04:07 PM

然后我有个巨大的疑问，如是如你所说的先找AABB,再切去没用的角。最多8边形，那就是说最多会切4个角。而AABB应该是平行四边形。切了4个角后，应该还是会有4条边是平行的。而根据我抓祯来看网格，似乎没有发现有什么是平行的情况。

Posted by: A | (19) January 26, 2018 06:06 PM

新版的sc文件格式估计变了，文件头和lzma文件头差别巨大，没有一点点共同之处。

Posted by: A | (18) January 26, 2018 05:57 PM

sc 文件用 lzma 解压后，每个字节都是有含义的，也非常容易理解。 supercell 对 2d sprite 支持就两种，四边形和五到八边形。分别用了两种 tag 在 sc 文件里标示。不要臆测，打开看一下就明白了。八边形自然还可以切出更多边，但没有太大意义，反而增加了顶点数。而且把装箱算法搞复杂了。aabb 去掉角装箱只需要对传统算法做少许调整，对齐的时候判断一下斜边相交再缩进就能工作了。多边形装箱并没有什么特别好的算法，所以对于伸手党也搜不到什么开源实现，只有自己实现一下才能明白。

Posted by: cloud | (17) January 24, 2018 12:23 AM

@Cloud 我认为他们应该游戏的角色原本就是3D模型，也是3D动作。然后把这个角色的所有动作祯渲染出来，并记录下光栅化后的顶点数据和UV坐标和贴图。这时的贴图应该是没有一点多余的空白的，然后用多边形装箱的方式打包成大贴图。通过我的观查，我认为是这样，而且这种样子也是绝对比什么AABB再切成八边形更省空间和精确的，资源我的确没看过，不敢肯定.但我设想的这种做法我认为是不差的

Posted by: A | (16) January 23, 2018 11:46 PM

你以为八边形怎么渲染？自然是拆成 6 个三角形了。四边形拆成两个。每个 sprite 的顶点数明明白白写在 .sc 文件里了。前面我已经写的很明白了，super cell 的方案是先找出 sprite 的 aabb ，然后尝试切掉最大面积的四个角，方便装箱更紧凑。这些任何有点开发 2d 经验的程序员看一眼装箱后的贴图就能明白。（所以这个五到八边形一定是凸的）。至于 sc 文件里怎么描述，无非是记录下每个 sprite 的顶点数字，每个顶点的 uv 坐标，渲染映射的坐标，顶点变色。动画再加上有可能的变换矩阵。super cell 的大部分图元都是用 3x2 平面变换矩阵的，而不是 3 维空间需要的 4x3 矩阵。这些东西一点 3d 技术都没用。不要觉得有三角形片就是 3d 了。

Posted by: Cloud | (15) January 23, 2018 01:18 PM

@Cloud 你看一下皇室绘制的时候是八边形吗？明明就是3d模形光珊化后的样子。

Posted by: A | (14) January 23, 2018 11:58 AM

四边形也是多边形。supercell 的引擎一直是一套并在发展的。用八边形提高装箱效率是从 hayday 前几年的某个版本开始的。怎样切割八边形的算法是你抓帧看不到的。如何组织贴图上的碎片通过变形和变色渲染到游戏里也是你看不到的。要研究就好好研究，不要浮在表面。好好学习一下人家的资源文件的数据结构，比你看两张贴图有意义的多。至于变形，coc 的早期版本就用了。有个搅拌锅的棍子和锅里的溶液就是通过斜切变换做的。贴图上的图和游戏里的效果不一样。supercell 的引擎早就不是贴矩形了。这些和 3d 没有什么关系。supercell 只是在 bb 之后加了一点点模型渲染，点缀而已。 btw, 看不懂 supercell 的二进制格式可以看 ejoy2d 的，有源代码，基本和 supercell 的相同，也支持八边形 sprite ，实现机制也是类似的。

Posted by: Cloud | (13) January 23, 2018 11:48 AM

@Cloud 我们的重点并不是分析资源包，而是研究人家的渲染方式。你理解人家是怎么工作才是重要的，我又不使用人家的资源。皇室和COC明显不同啊，你就算得到它的贴图你不抓祯你是明白不了他是怎么画的。他是基于3D光栅化后以后的多边形来处理的。你认为COC的效果能和皇室比？COC一看就是纯2D的，皇室看上云是3D的感觉。但实际上优化成2D来做了。只不过是用多边形画SPRITE，而不是矩形

Posted by: A | (12) January 23, 2018 09:44 AM

@Cloud @A 两位大侠休怒都是有基础的牛人坐下来斟杯酒

Posted by: 磊磊落落 | (11) January 23, 2018 09:34 AM

supercell 在 hayday 里对地面块做了变换方便装箱（同时可以去掉 alpha channel) 大多数图元并不变形，而使用八边形装箱的方法，并不同于 texture packer 那样的完全多边形化。算法是先找到 aabb 的四边形，然后再尝试切掉四个角。装箱算法只需要对传统算法做一点改进，允许边角重合。稍微分析一下资源文件格式的话就知道 supercell 的图元最多是八边形的（最近一年新版本不知道有没有改进）。至于 3d 模型混用，只是点缀，本质上还是 2d 图元渲染。只想看装箱的贴图的话，这里就有： https://tcrf.net/Clash_Royale/Removed_and_Changed_Sprites

Posted by: Cloud | (10) January 23, 2018 02:22 AM

supercell 用的那么简单明了的资源文件格式都分析不出来，low 到需要运行时截帧来猜测怎么做的，有脸说研究过？

Posted by: Cloud | (9) January 23, 2018 01:50 AM

@Cloud 搞的好像你看过一样，你这句话一出口就知道你没有研究过，也没有看过。你能加载皇室战争的资源？你如果研究过也不会讲这种话了。人家本质是3D的。但是光栅化成2D。看看人家装箱是多么的紧凑，我说你丢人现眼你好像还不服气似的。我说错了？

Posted by: A | (8) January 22, 2018 05:41 PM

@A 用抓帧工具看人家的资源实在是太 low 了。supercell 设计的那么简单的资源格式，打开看一下不就知道了。 ejoy2d 的内部版本可以直接加载 coc/bb/hayday 的资源包文件，一个字节都不需要修改，包括所有贴图，sprite 和动画。只是因为资源格式并没有公开，所以加载代码也不能开源而已。 ps. 通过斜切变换来把菱形地块变形为矩形，hayday 里就是这么干的。喷子请多长点脑子再喷。

Posted by: Cloud | (7) January 22, 2018 04:32 PM

不知道你有没有看过皇室战争还有海岛奇兵的做法？麻烦你用抓祯工具抓下来看看人家人图片是怎么存放的，好好学习一下，不要在这边丢人现眼。

Posted by: A | (6) January 22, 2018 03:40 PM

还不如多边形装箱合算

Posted by: kk | (5) January 19, 2018 07:38 PM

不如写个工具把这种有大量空白的图片切分再pack到图集，同时记录切分索引，用的时候先还原。简单而且没有损失精度

Posted by: ll | (4) January 19, 2018 04:08 PM

Posted by: unkown | (3) January 18, 2018 06:55 PM

感觉除了上面武器的例子外都不太划算, 每经过一次线性采样都是一种损失, 即使再锐化也不靠谱.

Posted by: dwing | (2) January 13, 2018 12:39 PM

Posted by: alex4j | (1) January 12, 2018 04:49 PM