[图形算法]J2me上的凹凸拼图实现思路

出于个人兴趣，简单研究了一下凹凸拼图的实现。以下为本人的实现思路，多多交流。

以下来逐步讲解各个流程

 

生成拼图模板：

 

  

线框图形的填充需要用到填充算法，比较简单的是“种子填充算法”，但对于J2ME来说过多的递归会导致内存溢出。我测试了一下，如果使用8向连同方式，填充72X72的区域就会导致溢出了。

种子填充算法的相关链接：

种子填充算法

 

对此我绕了个大弯，通过改良了一下广度优先搜索算法来实现。我们的目的就是填充一个指定的区域，给定一个起始点（先前我们生成模板时做的记录），然后以线框边界为障碍，遍历填充线框内的每个点。而搜索算法本身的作用是给定一个起始点和终点，然后搜索可行路径，在搜索的过程中是试探式的，也就说如果一直没有找到终点，就会一直遍历下去，直到所有点都被尝试过了。我们这里就利用这点，让他找不到终点，然后试图遍历所有的点来达到填充的目的。而我们也得设定结束的条件，对此我用步数来限定（限定为图块像素的数量，这样做不一定合理，但能保证完全遍历，因为遍历的范围不会超出这个区域，而遍历过的路径也不会重复）。

这里给出一个实现：

/**
     * 使用指定颜色填充多边形
     * @param shape 包含多边形的图片
     * @param sx    多边形区域内的任意一点X坐标
     * @param sy    多边形区域内的任意一点Y坐标
     * @param borderColor   多边形的边界颜色
     * @param fillColor     希望填充的颜色
     */
	public static void fillPolygonWithColor(CustomImage shape, int sx, int sy,
			int borderColor, int fillColor) {

		int w = shape.getWidth();
		int h = shape.getHeight();

		int size = w * h;

		/*************************************
		 * 下面是通过广度优先搜索算法进行遍历
		 */
		int[][] pFace = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };

		int maxStep = size;
		int[] path = new int[maxStep];

		boolean AllComplete = false;
		int LevelNow = 1;
		int Act = 0;
		int ActBefore = 0;
		int MaxAct = pFace.length;
		int ActNow = 0;
		int sID = sy * w + sx;

		int[] LevelFoot = new int[maxStep];
		int[] Table = new int[maxStep];

		// 参数初始化
		LevelNow = 1;
		LevelFoot[1] = 0;
		LevelFoot[0] = -1;
		path[0] = sID;

		while (!AllComplete) {
			LevelNow++; // 进入下一层搜索
			if (LevelNow >= maxStep)
				break;
			LevelFoot[LevelNow] = LevelFoot[LevelNow - 1];
			for (ActBefore = LevelFoot[LevelNow - 2] + 1; 
             ActBefore <= LevelFoot[LevelNow - 1]; ActBefore++) {
				// 遍历预设的几个方向
				int srow = path[ActBefore] / w;
				int scol = path[ActBefore] % w;
				for (Act = 1; Act <= MaxAct; Act++) {
					if (!AllComplete) {
						// 试探下一步是否可行
						int trow = srow + pFace[Act - 1][0];
						int tcol = scol + pFace[Act - 1][1];

						if (trow < 0 || trow >= h || tcol < 0 || tcol >= w)
							continue;

						int tID = trow * w + tcol;

						if (tID < 0 || tID >= size) {
							continue;
						}
						if (Table[tID] == 1) {
							continue;
						} else {
							Table[tID] = 1;
						}
						if (shape.getRGB()[tID] == borderColor) {
							continue;
						}
						// 标记当前状态
						sID = tID;
						LevelFoot[LevelNow]++;
						ActNow = LevelFoot[LevelNow];
						path[ActNow] = sID;
						shape.getRGB()[sID] = fillColor;
						// 检测结束条件
						if (LevelNow >= maxStep)
							AllComplete = true;
					}
				}
			}
		}
	}

 

我们在遍历的同时提取填充为新的图片，而不直接在模板上填充。生成独立的模板便于后续的操作。

 

接下来我们通过蒙板从原图中提取不规则图块，这类似于DirectX中用实现图片透明的做法。需要一个填充为纯色的底图（蒙板），然后同时遍历蒙板和原图进行像素提取，生成新的图块。

 

具体思路可参考：

j2medev论坛里提到的一个显示特效实现

 

当蒙板生成后，就可以根据当初记录的起始坐标从原图中提取出对应的图块。

 

一个简单的实现（主要是当做练习和确定某些想法是否可行，所以实现不是很完整。顽童能跑）：

评论

4 楼 clarketang 2010-09-14  

大大，PuzzleGame_09.08.04.jar的源码可不可以分享下啊。
我邮箱 [e-mail]
万分感谢！

3 楼 稻-草 2010-04-20  

有没有具体代码可以分享下？

2 楼 univasity 2010-04-19  

稻-草 写道

赞一个。

问下博主,图片处理后,图片边缘的下凹效果和阴影效果是如何实现的？

观察得很仔细
这需要找到边界的点，再将颜色转为HSL，改变其亮度。目前我只是简单的判断了左右来处理明暗，立体效果还不是很强。至于阴影，按着图块的形状直接填充一张黑色的图即可，但比较毫内存，有更好的处理可以说说，呵呵。

1 楼 稻-草 2010-04-19  

赞一个。

问下博主,图片处理后,图片边缘的下凹效果和阴影效果是如何实现的？