AtlasPreview

图集预览,MaxRectBinPacker算法

使用方法 在放贴图文件夹上右键,查看图集预览,方便的查看打出来的图集资源,以便及时对不合理的图集规划做调整 例如2048 * 20 的图片未经九宫就放在了图集中

Unity API

• 从此类派生以创建编辑器窗口:EditorWindow
• 获取当前屏幕T类型的EditorWindow:EditorWindow.GetWindow<T>
• 访问编辑器中的选择:Selection
• 返回所选资源的GUID:Selection.assetGUIDs
• 得到物体的完整路径:AssetDatabase.GUIDToAssetPath
• 项目所在的磁盘物理路径:Application.dataPath

代码分析

Unity原生打出来的图集在算法和策略上不是很好,都是从左下往右上扩散,所以需要重写贴图合并的算法

一 Rect坐标系

二 算法思路

维护“空闲矩形列表”。初始时，整张图片作为一个空闲矩形 若要放入一张图片，则在“空闲矩形列表”中寻找，找到一个合适的矩形，并从“空闲矩形列表”移除,把找到的矩形拆分为一个或多个矩形，其中一个正好容纳图片。剩余的矩形加入“空闲矩形列表”之中,因此主要的问题就是:

• 如何找到合适的矩形
• 找到矩形之后如何切分
• 如何应对多张图片的添加、删除

找到合适的矩形

遍历当前的“空闲矩形列表”，忽略那些无法容纳的，然后按照公式计算得分。 得分最高者作为结果。公式有：

• BestAreaFit - 面积最接近
• BestShortSideFit - 短边最接近
• BestLongSideFit - 长边最接近
• BottomLeftRule - 放在最左下
• ContactPointRule - 尽可能与更多的矩形相邻

找到矩形之后进行切分

例如一个 100x100 的矩形在装入一张 30x30 的图片之后。将剩下以下矩形:

• 方案 1. 剩下 30x70 和 70x100
• 方案 2. 剩下 70x30 和 100x70
• 方案 3. 全都要。把上述矩形都加入“空闲矩形列表”。

方案 3 最佳。

实际的做法应该是，遍历“空闲矩形列表”中的每一个，只要其与切分的矩形有交叉，则进行切割。 具体可以看 AS3 代码的 placeRectangle, splitFreeNode 这两个函数。

完成之后，用 pruneFreeList 进行修剪。即遍历“空闲矩形列表”，如果发现某矩形包含另一个矩形，则把小的矩形删除。 pruneFreeList是一个 O(n^2) 复杂度的计算，是整个算法最耗时的部分。

多张图片的添加、删除

如果需要把多张图片加入合图，只需要逐个处理即可。 当从合图中删除图片时，进行以下处理：

把图片所在矩形加入“空闲矩形列表”

遍历“空闲矩形列表”，如果发现有矩形正好与刚才加入的矩形相邻，则判断能否把两个矩形合并。在判断时，还需要一个“已经用掉的矩形列表”。 合并之后，也调用 pruneFreeList 进行修剪。

算法解析 MaxRectsBinPack 矩形合并算法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using UnityEngine;
namespace EditorTools.UI {
    //定义贴图数据的排序
    public class Texture2DComparison : IComparer<TextureData> {
        public int Compare(TextureData x, TextureData y) { //进行比较的贴图数据x和y
            int ret = 0;
            if (Mathf.Max(x.width , x.height) > Mathf.Max(y.width , y.height)) { //x宽高最大值 比 y宽高最大值 大
                ret = -1; //返回负数,代表x插入在y的前面
            } else if (Mathf.Max(x.width , x.height) < Mathf.Max(y.width + y.height)) { //x的宽高最大值小于y的宽高值
                ret = 1; //返回整数,代表将x插入在y的后面
            }
            return ret;//返回相等
        }
    }
    public class MaxRectsBinPack {
        //是否使用此算法进行图集合并
        public static bool IsUseMaxRectsAlgo = true;
        public int binWidth = 0; //容器的宽
        public int binHeight = 0; //容器的高
        public bool allowRotations; // 是否可旋转
        public List<Rect> usedRectangles = new List<Rect>(); //已经用掉的矩形列表
        public List<Rect> freeRectangles = new List<Rect>(); //空闲矩形列表
        public enum FreeRectChoiceHeuristic { //匹配规则
            RectBestShortSideFit, // BSSF: 短边最接近
            RectBestLongSideFit, // BLSF: 长边最接近
            RectBestAreaFit, // BAF: 面积最接近
            RectBottomLeftRule, /// BL: 放在最左下
            RectContactPointRule // CP: 尽可能与更多矩形相邻
        };
        public MaxRectsBinPack(int width, int height, bool rotations = true) { //roattions 是否可旋转
            Init(width, height, rotations);
        }
        //一些初始化操作,清空空闲矩形列表
        public void Init(int width, int height, bool rotations = true) { 
            binWidth = width;
            binHeight = height;
            allowRotations = rotations;
            Rect n = new Rect(); //一个矩形,左上角起始,宽高
            n.x = 0;
            n.y = 0;
            n.width = width;
            n.height = height;
            usedRectangles.Clear();
            freeRectangles.Clear();
            freeRectangles.Add(n); //把初始化的矩形添加进来
        }
        public Rect Insert(int width, int height, FreeRectChoiceHeuristic method) {
            Rect newNode = new Rect();
            int score1 = 0;
            int score2 = 0;
            switch (method) { //根据匹配的方法进行四种匹配,返回匹配到的最佳的矩形
                case FreeRectChoiceHeuristic.RectBestShortSideFit: newNode = FindPositionForNewNodeBestShortSideFit(width, height, ref score1, ref score2); break;
                case FreeRectChoiceHeuristic.RectBottomLeftRule: newNode = FindPositionForNewNodeBottomLeft(width, height, ref score1, ref score2); break;      
                case FreeRectChoiceHeuristic.RectContactPointRule: newNode = FindPositionForNewNodeContactPoint(width, height, ref score1); break;
                case FreeRectChoiceHeuristic.RectBestLongSideFit: newNode = FindPositionForNewNodeBestLongSideFit(width, height, ref score2, ref score1); break;
                case FreeRectChoiceHeuristic.RectBestAreaFit: newNode = FindPositionForNewNodeBestAreaFit(width, height, ref score1, ref score2); break;
            }
            if (newNode.height == 0)
                return newNode;
            int numRectanglesToProcess = freeRectangles.Count;
            for (int i = 0; i < numRectanglesToProcess; ++i) {
                if (SplitFreeNode(freeRectangles[i], ref newNode)) {
                    freeRectangles.RemoveAt(i);
                    --i;
                    --numRectanglesToProcess;
                }
            }
            PruneFreeList(); // 对空闲矩形列表进行修剪,删减掉已经使用的矩形
            usedRectangles.Add(newNode);//将已经使用的矩形添加到已使用列表
            return newNode;//返回经过计算匹配到的最佳矩形
        }
        //优先匹配最左下角的矩形匹配方法
        Rect FindPositionForNewNodeBottomLeft(int width, int height, ref int bestY, ref int bestX) {  
            Rect bestNode = new Rect(); //创建矩形
            bestY = int.MaxValue;
            for (int i = 0; i < freeRectangles.Count; ++i) { //遍历空闲矩形列表
                if (freeRectangles[i].width >= width && freeRectangles[i].height >= height) { //若查找到一个长宽都大于目标的长宽的矩形
                    int topSideY = (int)freeRectangles[i].y + height; //下边界等于查找到的空闲矩形的y坐标 + 目标矩形的高度
                    // 新的满足条件的矩形下边界比上一次满足条件的矩形还要小,下边界相等但是x比上一次满足条件的矩形要小,也就是说新匹配的矩形比上次满足条件的矩形更加左下
                    if (topSideY < bestY || (topSideY == bestY && freeRectangles[i].x < bestX)) { //<是由Rect的坐标系轴增量方向决定的,易混淆
                        bestNode.x = freeRectangles[i].x; //寻找的矩形左下点x坐标为符合条件的矩形左上点x坐标
                        bestNode.y = freeRectangles[i].y; //寻找的矩形左下点y坐标为符合条件的矩形左上点y坐标
                        bestNode.width = width; // 记录匹配到的矩形的宽高
                        bestNode.height = height;
                        bestY = topSideY;//下边界
                        bestX = (int)freeRectangles[i].x;//左边界
                    }
                }
                //和上方的操作一致,只是允许旋转的时候进行下方的逻辑,匹配宽高的时候可以交叉匹配
                if (allowRotations && freeRectangles[i].width >= height && freeRectangles[i].height >= width) {
                    int topSideY = (int)freeRectangles[i].y + width;
                    if (topSideY < bestY || (topSideY == bestY && freeRectangles[i].x < bestX)) {
                        bestNode.x = freeRectangles[i].x;
                        bestNode.y = freeRectangles[i].y;
                        bestNode.width = height;
                        bestNode.height = width;
                        bestY = topSideY;
                        bestX = (int)freeRectangles[i].x;
                    }
                }
            }
            return bestNode;//返回匹配到的最佳矩形
        }
        //优先匹配最短边的矩形匹配算法
        Rect FindPositionForNewNodeBestShortSideFit(int width, int height, ref int bestShortSideFit, ref int bestLongSideFit) {
            Rect bestNode = new Rect();//创建一个新矩形
            bestShortSideFit = int.MaxValue;//最短边匹配
            for (int i = 0; i < freeRectangles.Count; ++i) { //遍历空闲矩形列表

                if (freeRectangles[i].width >= width && freeRectangles[i].height >= height) { //遍历到一个可以容纳目标矩形的空闲矩形
                    int leftoverHoriz = Mathf.Abs((int)freeRectangles[i].width - width);//目标矩形宽度相比查找的矩形多余的部分
                    int leftoverVert = Mathf.Abs((int)freeRectangles[i].height - height);//目标矩形高度相比查找的矩形多余的部分
                    int shortSideFit = Mathf.Min(leftoverHoriz, leftoverVert);//宽高多余值的较小值
                    int longSideFit = Mathf.Max(leftoverHoriz, leftoverVert);//宽高多余值的较大值
                    // 新的满足条件的矩形短边匹配值比上一次满足条件的矩形还要小,或者短边多余值相等但是长边匹配值比上一次满足条件的矩形要小
                    // 也就是说新匹配的矩形比上次满足条件的矩形在较短边上更加适合
                    if (shortSideFit < bestShortSideFit || (shortSideFit == bestShortSideFit && longSideFit < bestLongSideFit)) {
                        bestNode.x = freeRectangles[i].x; //保存匹配到的矩形数据
                        bestNode.y = freeRectangles[i].y;
                        bestNode.width = width;
                        bestNode.height = height;
                        bestShortSideFit = shortSideFit; //短边匹配值
                        bestLongSideFit = longSideFit; //长边匹配值
                    }
                }
                if (allowRotations && freeRectangles[i].width >= height && freeRectangles[i].height >= width) { //和上边操作一致,在允许旋转的情况下进行宽高的交叉对比
                    int flippedLeftoverHoriz = Mathf.Abs((int)freeRectangles[i].width - height);
                    int flippedLeftoverVert = Mathf.Abs((int)freeRectangles[i].height - width);
                    int flippedShortSideFit = Mathf.Min(flippedLeftoverHoriz, flippedLeftoverVert);
                    int flippedLongSideFit = Mathf.Max(flippedLeftoverHoriz, flippedLeftoverVert);
                    if (flippedShortSideFit < bestShortSideFit || (flippedShortSideFit == bestShortSideFit && flippedLongSideFit < bestLongSideFit)) {
                        bestNode.x = freeRectangles[i].x;
                        bestNode.y = freeRectangles[i].y;
                        bestNode.width = height;
                        bestNode.height = width;
                        bestShortSideFit = flippedShortSideFit;
                        bestLongSideFit = flippedLongSideFit;
                    }
                }
            }
            return bestNode;
        }
        //优先匹配最长边的矩形匹配算法
        Rect FindPositionForNewNodeBestLongSideFit(int width, int height, ref int bestShortSideFit, ref int bestLongSideFit) {
            Rect bestNode = new Rect();//创建一个新矩形
            bestLongSideFit = int.MaxValue