0
0

通过斜切变换 2d sprite 提高装箱率

云风 发表于 2018年01月19日 17:05 | Hits: 1032
Tag: 游戏开发

现代 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.png weapon.trans.png

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

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

算法是这样的:

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

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

box.png box.trans.png

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

tile.png tile.trans.png

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

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

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

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

原文链接: https://blog.codingnow.com/2018/01/2d_sprite_transform_binpacking.html

0     0

评价列表(0)