关键字透明图片 图块 module 自动切割 回溯算法问题的引出 在通常的2D游戏动画编辑器中，经常要把一个背景透明的图片(素材图)上的图块进行切割，这些切割后的图块一般叫做module，游戏动画中的一帧（frame）通常由这样的几个module，进行变换后组合而成。多个frame序列形成一个动画(animation)。当然，这里的切割，并不是说要把原始的素材图切割成几张小图片，只是说记录下每个module在素材图上的位置(x，y)和大小(width，height)而已。下图说明了这个过程:
图1:原始的动画素材图
如上图所示，假定美工最初的动画素材图如上图所示。这是一张背景透明的素材图，里面有4个module，中间的module所包含的像素，全部是不透明的，而左右两边的module，其边缘像素是不透明的，内部的像素为全透明的，最下面的module，为1条不透明的折线。下图表示进行切割后的素材图:
图2:进行module切割后的素材图(红线表示module的外切矩形)
上图清楚的说明了所谓的切割，就是确定素材图上每一个module的外切矩形而已。通过使用这些module，程序员就可以组合成一帧帧的动画了，如下图:
图3:由4种module组合成了1帧(红线为位置标尺线，并非帧内像素)
如果我们把图2中的4个module从左至右，从上到下分别编号为module0，module1，module2，module3，那么图3所示的动画帧就是由1个module0，1个module2，1个module1，1个module3,1个左右镜像变换后的module0，1个左右镜像变换后的module3,共6个module按照一定位置摆布组合而成。有了每个module的位置和大小信息，以及这6个module的变换，摆布信息，我们就能把图3所示的这个动画帧绘制出来。当然这些信息的生成，通常是使用专门的动画编辑器来做的。
由以上过程可知，在动画编辑的过程中，很重要的一步就是确定每个module的位置和大小，也就是其外切矩形，如何来确定这个外切矩形呢？当然可以在动画编辑器中，让使用者手工操作来确定，比如通过鼠标拖拽出一个module的外切矩形，或者使用类似于photoshop中标尺线的方式，通过拖拽4条标尺线，确定module的外切矩形。但是这样做，很费时费力，而且存在手误的可能。其实，我们可以设计一个算法，让电脑帮我们来自动切割，对那些需要特别处理的module,再使用人工切割。本文讲述如何使用回溯算法，来进行module的自动切割。使用回溯算法，自动切割module使用回溯法来自动切割module，可以分成以下几步来做。
1． 准备一个队列q1。
2． 扫描整个材质图，把所有非透明像素点加入q1中。如下图:
图4:材质图中非透明像素加入队列
3． 准备一个栈s。
4． 取q1的第一个元素，加入s。
图5:取q1队列头像素入栈
5． 取s的栈顶元素p,扫描q1,如果发现有像素为p之相连像素x，那么把x从队列中取出，入栈。所谓相连，是指x像素在材质图中位于p像素的相邻四周，如下图所示p周围的红色区域:
图6:像素p的相连像素
图7:在q1中发现栈顶像素的相连像素，则把该像素从q1中取出，入栈。
如果有元素入栈，那么重复本步骤，如果在q1中找不到栈顶元素的相连像素，那么s弹出栈顶元素到队列q2中。
图8:s弹出无相连像素的栈顶到q2
继续重复本步骤(回溯)，当s为空时,q2中的所有像素组成1个module，由这些像素的最小x,最小y,最大x,最大y，就可以确定出该module的外切矩形，进而确定出该module的位置和大小。
6． 重复步骤4,步骤5，直到q1为空。这样，所有的module都被找出来了。算法的限制条件1. 同一个module的所有像素，必须是相连的，不能是断开的。如下图所示，该算法认为这个同心圆是2个module,如果你需要把这个同心圆当作一个module来处理的话，就需要手动进行切割。
图9:2个module,1个module?
2. 不同module的像素，不能连接在一起。只要连接在一起的像素，该算法都认为属于同一个module。如下图所示，2个圆有公共像素，该算法认为这2个圆属于同一个module,但是如果你需要把这2个圆当作2个module来处理的话，就需要手动切割了。
图10:2个module,1个module?
3. 背景必须全透明。
也就是说要求材质图上的像素，要么全透明，要么全不透明。这个条件是必须的，这是该算法区分像素是否相连的判定依据。
总之，使用本算法，编程简单，大大减少了动画编辑器使用者进行module切割的工作量。是手动module切割的有力助手。作者信息Jagie，软件开发爱好者 可以通过chen_cwf@163.com与他联系。本文来自Jagie的google page:http://chencwf.googlepages.com/modulecut
|
|
11 
0
