装箱问题，是个NP问题。⾄于装箱问题到底是个什么东西，可以看看百度⽂档。其实我没看。
研究⼆维矩形装箱问题，是因为需要将⼩图拼成⼤图，作为⼀个⼤的texture加载到内存内，从⽽实现减少内存消耗的⽬的。做游戏的都知道texturepacker⼯具，⼀款付费软件，有⽆限多个破解安装程序。
texturepacker就是将⼩图合成为⼀张⼤图，导出png图像，以及含有⼩图⼤⼩，位置信息的plist⽂本⽂件。
给布置的作业，其实是让⽤设计模式完成⼀款texturepacker类⼯具，可惜编程能⼒不强，另⼀⽅⾯⽐较懒，不想去做可视化界⾯，于是就只找了篇硕⼠论⽂，按照论⽂内提到的⼀种算法，写了写程序。
论⽂是：。不知道原作者是⾼兴还是忧伤我酱紫给他做⼴告。程序运⾏环境为：cocos2dx 3.0, vs2012.
1 #ifndef __HELLOWORLD_SCENE_H__ 2 #define __HELLOWORLD_SCENE_H__ 3
4 #include \"cocos2d.h\" 5 #include \"BigImage.h\" 6 #include \"BaseObject.h\"
7 #include \"LLABF_Algorithm.h\" 8
9 class BigImage;
10 class HelloWorld : public cocos2d::Layer11 {
12 public:
13 ~HelloWorld();
14 // there's no 'id' in cpp, so we recommend returning the class instance pointer15 static cocos2d::Scene* createScene();16
17 // Here's a difference. Method 'init' in cocos2d-x returns bool, instead of returning 'id' in cocos2d-iphone18 virtual bool init(); 19
20 // a selector callback
21 void menuCloseCallback(cocos2d::Ref* pSender);22
23 void initSimpleImageInfo( SimpleImageInfo * simpleImage );24
25 // implement the \"static create()\" method manually26 CREATE_FUNC(HelloWorld);27
28 std::vector 30 // 图像像素拷贝 将⼀张图的内容复制到另⼀张⼤图中 31 void copyPixels();32 33 BigImage * m_bigImage;34 void initTestImageInfos();35 void initTestDictionary();36 };37 38 #endif // __HELLOWORLD_SCENE_H__ HelloWorldScene.h 1 #include \"HelloWorldScene.h\" 2 #include \"cocos2d/external/png/include/win32/png.h\" 3 #include 8 using namespace std; 9 10 USING_NS_CC; 11 12 Scene* HelloWorld::createScene() 13 { 14 auto scene = Scene::create(); 15 auto layer = HelloWorld::create(); 16 scene->addChild(layer); 17 return scene; 18 } 19 20 bool HelloWorld::init() 21 { 22 if ( !Layer::init() ) 23 { 24 return false; 25 } 26 27 Size visibleSize = Director::getInstance()->getVisibleSize(); 28 Point origin = Director::getInstance()->getVisibleOrigin(); 29 auto closeItem = MenuItemImage::create( 30 \"CloseNormal.png\", 31 \"CloseSelected.png\", 32 CC_CALLBACK_1(HelloWorld::menuCloseCallback, this)); 33 34 closeItem->setPosition(Point(origin.x + visibleSize.width - closeItem->getContentSize().width/2 , 35 origin.y + closeItem->getContentSize().height/2)); 36 auto menu = Menu::create(closeItem, NULL); 37 menu->setPosition(Point::ZERO); 38 this->addChild(menu, 1); 39 auto label = LabelTTF::create(\"Hello World\", \"Arial\", 24); 40 41 label->setPosition(Point(origin.x + visibleSize.width/2, 42 origin.y + visibleSize.height - label->getContentSize().height)); 43 44 return true; 45 } 46 47 48 void HelloWorld::menuCloseCallback(Ref* pSender) 49 { 50 #if (CC_TARGET_PLATFORM == CC_PLATFORM_WP8) || (CC_TARGET_PLATFORM == CC_PLATFORM_WINRT) 51 MessageBox(\"You pressed the close button. Windows Store Apps do not implement a close button.\",\"Alert\"); 52 return; 53 #endif 54 imageInfos.clear(); 55 system(\"dir /b *.png > untitled.plist\"); 56 int bigImageWidth = 512; 57 string fullPath = FileUtils::getInstance()->fullPathForFilename(\"untitled.plist\"); 58 string filecontent = FileUtils::getInstance()->getStringFromFile(fullPath); 59 ifstream fp( fullPath ); 60 if (!fp) 61 { 62 cerr << \"OPEN ERROR\" << endl; 63 return ; 64 } 65 66 if ( fp ) 67 { 68 string s; 69 while (getline(fp,s)) 70 { 71 SimpleImageInfo * image = new SimpleImageInfo(); 72 image->imageName = s; 73 imageInfos.push_back(image); 74 CCLog( s.c_str()) ; 75 } 76 fp.close(); 77 78 // 初始化I 79 for ( int i = 0; i< imageInfos.size(); i++ ) 80 { 81 initSimpleImageInfo(imageInfos[i]); 82 imageInfos[i]->id = i; 83 } 84 LLABF * llabf = new LLABF(); 85 llabf->initImages(imageInfos, bigImageWidth ); 86 llabf->runLLABF(); 87 88 89 90 m_bigImage = new BigImage(\"my_test_1.png\",bigImageWidth,llabf->getBigImageHeight(),\"my_test_1.plist\"); 91 m_bigImage->initBigImageWithImagesData(&imageInfos); 92 m_bigImage->publish(); 93 } 94 95 CCLog(\"end\"); 96 97 //SpriteFrameCache::getInstance()->addSpriteFramesWithFile(\"my_test_1.plist\"); 98 //auto sprite = Sprite::createWithSpriteFrameName(\"a1.png\"); 99 //sprite->setPosition( 300, 300);100 //this->addChild(sprite, 1000);101 102 #if (CC_TARGET_PLATFORM == CC_PLATFORM_IOS)103 exit(0);104 #endif105 }106 107 void HelloWorld::initSimpleImageInfo( SimpleImageInfo * simpleImage )108 { 109 // 读取png⽂件头 110 std::string fullPath_png = FileUtils::getInstance()->fullPathForFilename( simpleImage->imageName );111 unsigned char header[8];112 int width, height; 113 png_byte color_type; //图⽚到类型（可能会⽤在是否是开启来通道） 114 png_byte bit_depth; //字节深度 115 116 png_structp png_ptr; // 图⽚ 117 png_infop info_ptr; // 图⽚的信息 118 int number_of_passes;// 隔⾏扫描 119 png_bytep * row_pointers;// 图⽚的数据内容 120 int row, col, pos; // ⽤于改变png像素排列的问题 121 GLubyte * rgba;122 123 FILE * fp = fopen( fullPath_png.c_str(), \"rb\");124 if ( !fp )125 { 126 fclose(fp);127 return;128 } 129 fread(header, 1, 8, fp); 130 if ( png_sig_cmp(header, 0, 8 )) // 读取⽂件头判断是否是png图⽚，不是则做出相应处理 131 { 132 fclose(fp);133 return;134 } 135 //根据libpng的libpng-manual.txt的说明使⽤⽂档 接下来必须初始化png_structp 和 png_infop 136 png_ptr=png_create_read_struct(PNG_LIBPNG_VER_STRING,NULL,NULL,NULL); //后三个是绑定错误以及警告的函数这⾥设置为空 137 138 if(!png_ptr)139 { 140 fclose(fp);141 return;142 } 143 //根据初始化的png_ptr初始化png_infop 144 info_ptr=png_create_info_struct(png_ptr); 145 if(!info_ptr) 146 { 147 //初始化失败以后销毁png_structp 148 png_destroy_read_struct(&png_ptr,(png_infopp)NULL,(png_infopp)NULL); 149 fclose(fp); 150 return ; 151 } 152 //⽼⽼实实按照libpng给到的说明稳定步骤来 错误处理！ 153 if (setjmp(png_jmpbuf(png_ptr))) 154 { 155 //释放占⽤的内存！然后关闭⽂件返回⼀个贴图ID此处应该调⽤⼀个⽣成默认贴图返回ID的函数 156 157 png_destroy_read_struct(&png_ptr,(png_infopp)NULL,(png_infopp)NULL); 158 159 fclose(fp); 160 161 return ; 162 163 } 164 //你需要确保是通过2进制打开的⽂件。通过i/o定制函数png_init_io 165 png_init_io(png_ptr,fp); 166 //似乎是说要告诉libpng⽂件从第⼏个开始missing 167 png_set_sig_bytes(png_ptr, 8); 168 //如果你只想简单的操作你现在可以实际读取图⽚信息了！ 169 png_read_info(png_ptr, info_ptr); 170 //获得图⽚到信息 width height 颜⾊类型 字节深度 171 width = png_get_image_width(png_ptr, info_ptr); 172 height = png_get_image_height(png_ptr, info_ptr); 173 color_type = png_get_color_type(png_ptr, info_ptr); 174 //如果图⽚带有alpha通道就需要 175 // if (color_type == PNG_COLOR_TYPE_RGB_ALPHA) 176 177 // png_set_swap_alpha(png_ptr); 178 bit_depth = png_get_bit_depth(png_ptr, info_ptr); 179 180 fclose(fp); 181 182 simpleImage->width = width;183 simpleImage->height = height;184 }185 186 void HelloWorld::initTestImageInfos()187 { 188 SimpleImageInfo * image1 = new SimpleImageInfo();189 image1->imageName = \"a5.png\";190 image1->x = 0;191 image1->y = 0; 192 image1->width = 576;193 image1->height = 154;194 image1->isRotate = true; 195 imageInfos.push_back(image1);196 197 SimpleImageInfo * image2 = new SimpleImageInfo();198 image2->imageName = \"a6.png\";199 image2->x = 154;200 image2->y = 0; 201 image2->width = 576;202 image2->height = 154;203 image2->isRotate = true; 204 imageInfos.push_back(image2);205 }206 207 HelloWorld::~HelloWorld()208 { 209 for ( int i = 0; i< imageInfos.size(); i++ )210 { 211 delete imageInfos[i];212 } 213 imageInfos.clear();214 }215 216 void HelloWorld::initTestDictionary()217 { 218 Dictionary * dict = Dictionary::create();219 auto string = String::create(\"test_key\"); 220 dict->setObject(string, \"string element key\"); // 添加⼀个键值对 221 auto doubleObject = Double::create(1024.123);222 dict->setObject(doubleObject, \"double\");223 224 Dictionary * dict_1 = Dictionary::create(); 225 dict_1->setObject(String::create(\"string in dictInDict value\"), \"string in dictInDict key\");226 dict->setObject(dict_1, \"dict_test_key\");227 228 std::string writablePath = FileUtils::getInstance()->getWritablePath();229 std::string fullPath = writablePath + \"text.plist\";230 if(dict->writeToFile(fullPath.c_str())) 231 log(\"see the plist file at %s\", fullPath.c_str());232 else 233 log(\"write plist file failed\");234 } HelloWorldScene.cpp 其中⽤到了system函数，将Resource⽬录内的png图像导⼊untitled.plist⽂件内。其实这个应该做个UI，弹出⽂件夹选择框，多选⽂件，将⽂件名导⼊。我太懒了，不想去看MFC或者QT。就这样凑合吧。 HelloWorldScene主要就是导出⽂件夹内的png⽂件名。然后初始化⼀些⼩图信息，转给LLABF算法，最后BigImage类根据LLABF算法计算得到的⼩图位置信息，⽣成⼤图png，以及plist。就这么简单。 下⾯就是LLABF算法。应该差不多是按照论⽂内描述的那样写的。 1 #ifndef __LLABF_ALGORITHM_H_ 2 #define __LLABF_ALGORITHM_H_ 3 #include \"BaseObject.h\" 4 #include 7 class LLABF 8 { 9 public: 10 LLABF();11 ~LLABF();12 13 void initImages( std::vector 16 int FullFitFirst( SimpleEdgeInfo* edge ); // 完全匹配优先 17 int WidthFitFirst( SimpleEdgeInfo* edge ); // 宽度匹配优先 18 int HeightFitFirst( SimpleEdgeInfo* edge ); // ⾼度匹配优先 19 int JointWidthFitFirst( SimpleEdgeInfo* edge ); // 组合匹配优先 20 int PlaceabelFirst( SimpleEdgeInfo* edge ); // 可装⼊优先 21 22 void findEqualToEdgeWidth( SimpleEdgeInfo * edge ); // 查找和ek的width⼤⼩相等的image 从ii开始在imageInfos⾥查找 23 void findLessOrEqualToEdgeWidth( SimpleEdgeInfo * edge ); // 查找不⼩于ek的width的image 从ii开始在imageInfos⾥查找 24 void findJointEqualToEdgeWidth( SimpleEdgeInfo * edge ); 25 bool canLeftFill( SimpleImageInfo * image, SimpleEdgeInfo * edge ); // 是否能左填平 26 bool canRightFill( SimpleImageInfo * image, SimpleEdgeInfo * edge ); // 是否能右填平 27 int getBigImageHeight();28 private: 29 int H_packing; 30 std::vector 32 std::vector 33 std::vector 38 #endif LLABF_Algorithem 1 #include \"LLABF_Algorithm.h\" 2 #include \"cocos2d.h\" 3 4 LLABF::LLABF() 5 :m_bigImageWidth(0) 6 { 7 8 } 9 10 LLABF::~LLABF() 11 { 12 for ( int i = 0; i< edgeInfos.size(); i++ ) 13 { 14 delete edgeInfos[i]; 15 } 16 edgeInfos.clear(); 17 } 18 19 20 void LLABF::initImages( std::vector 22 imageInfos.clear(); 23 edgeInfos.clear(); 24 equalWidthImages.clear(); 25 lessOrEqualWidthImages.clear(); 26 joint_EqualWidthImages.clear(); 27 imageInfos = images; 28 m_bigImageWidth = width; 29 } 30 31 32 void LLABF::runLLABF() 33 { 34 // 初始化E 35 36 SimpleEdgeInfo * first_edge = new SimpleEdgeInfo(); 37 first_edge->x = 0; 38 first_edge->y = 0; 39 first_edge->width = 512; 40 first_edge->id = 0; 41 edgeInfos.push_back(first_edge); 42 43 44 SimpleEdgeInfo * the_lowest_line_edge = NULL; 45 int the_lowest_y = 0; 46 47 for ( int i = 0; i < imageInfos.size(); i++ ) 48 { 49 // 在E中选取最低⽔平线ek 50 the_lowest_line_edge = edgeInfos[0]; 51 the_lowest_y = the_lowest_line_edge->y; 52 for ( int j = 0 ; j< edgeInfos.size(); j++ ) 53 { 54 if ( the_lowest_y > edgeInfos[j]->y ) 55 { 56 the_lowest_y = edgeInfos[j]->y; 57 the_lowest_line_edge = edgeInfos[j]; 58 } 59 } // 选取结束 60 // 完全匹配优先 61 int m = -1; 62 // 传⼊参数为第⼏个矩形 i 为从哪个⼩image开始在imageInfos内搜索 ， ， 第⼏条ek边 63 if ( the_lowest_line_edge ) 64 { 65 m = FullFitFirst( the_lowest_line_edge ); // 选取的第m个⼩image 66 // 宽度匹配优先 67 if ( m <= -1 ) 68 { 69 m = WidthFitFirst( the_lowest_line_edge ); 70 } 71 // ⾼度匹配优先 72 if ( m<= -1) 73 { 74 m = HeightFitFirst( the_lowest_line_edge ); 75 } 76 // 组合宽度匹配优先 77 if ( m<= -1 ) 78 { 79 m = JointWidthFitFirst( the_lowest_line_edge ); 80 } 81 // 可装⼊优先 82 if ( m<= -1 ) 83 { 84 m = PlaceabelFirst( the_lowest_line_edge ); 85 } 86 87 if ( m <=-1 ) 88 { 89 i--; 90 // 合并E中的边 blablabla 怎么合并啊 91 if ( edgeInfos.size() > 1 ) 92 { 93 if ( the_lowest_line_edge->x == 0 && the_lowest_line_edge->x + the_lowest_line_edge->width < m_bigImageWidth ) 94 { 95 the_lowest_line_edge->y = edgeInfos[the_lowest_line_edge->id + 1]->y; 96 the_lowest_line_edge->width = the_lowest_line_edge->width + edgeInfos[the_lowest_line_edge->id + 1 ]->width; 97 edgeInfos[the_lowest_line_edge->id + 1 ]->isDelete = true; 98 } 99 else if ( the_lowest_line_edge->x + the_lowest_line_edge->width >= m_bigImageWidth)100 { 101 edgeInfos[the_lowest_line_edge->id - 1]->width = the_lowest_line_edge->width + edgeInfos[the_lowest_line_edge->id - 1 ]->width;102 the_lowest_line_edge->isDelete = true;103 }104 else105 { 106 // 从两边选择值较⼩的进⾏合并 107 if ( edgeInfos[the_lowest_line_edge->id - 1]->y < edgeInfos[the_lowest_line_edge->id + 1]->y )108 { 109 edgeInfos[the_lowest_line_edge->id - 1]->width = the_lowest_line_edge->width + edgeInfos[the_lowest_line_edge->id - 1 ]->width;110 the_lowest_line_edge->isDelete = true;111 }112 else113 { 114 the_lowest_line_edge->y = edgeInfos[the_lowest_line_edge->id + 1]->y; 115 the_lowest_line_edge->width = the_lowest_line_edge->width + edgeInfos[the_lowest_line_edge->id + 1 ]->width;116 edgeInfos[the_lowest_line_edge->id + 1 ]->isDelete = true;117 }118 } 119 std::vector 121 for( it= edgeInfos.begin();it!=edgeInfos.end();){122 123 if((*it)->isDelete){124 delete (*it); 125 edgeInfos.erase(it);126 break;127 }128 ++it;129 }130 131 for ( int i = 0; i< edgeInfos.size(); i++ )132 { 133 edgeInfos[i]->id = i;134 }135 }136 137 }138 else139 { 140 //将I集合中第j位元素对应的矩形件I(j)装⼊在E中的最低⽔平线ek上; blablabla 141 142 SimpleImageInfo * I_m = imageInfos[m];143 I_m->x = the_lowest_line_edge->x;144 I_m->y = the_lowest_line_edge->y;145 I_m->isInRect = true; 146 cocos2d::log(\"image name : %s\", I_m->imageName.c_str());147 148 int i_m_width = I_m->width;149 int i_m_height = I_m->height;150 if ( I_m->isRotate )151 { 152 i_m_width = I_m->height;153 i_m_height = I_m->width;154 }155 156 if ( the_lowest_line_edge->width - i_m_width > 0 ) // 如果宽度不同时，则实现的是⾼度匹配或者是组合宽度匹配 或者 可装⼊优先匹配 此时x轴不变 变化的是edge的宽度和 ⾼度，还会产⽣新的边 157 { 158 SimpleEdgeInfo * newEdgeInfo = new SimpleEdgeInfo();159 newEdgeInfo->id = the_lowest_line_edge->id + 1; 160 newEdgeInfo->x = the_lowest_line_edge->x + i_m_width; // 新边的x值 161 newEdgeInfo->y = the_lowest_line_edge->y; // 新边的⾼度 和以前的相等 162 newEdgeInfo->width = the_lowest_line_edge->width - i_m_width; // 新边的宽度 163 164 edgeInfos.insert(edgeInfos.begin() + newEdgeInfo->id, newEdgeInfo);165 166 the_lowest_line_edge->y = the_lowest_line_edge->y + i_m_height;167 the_lowest_line_edge->width = i_m_width;168 169 } 170 else // 宽度相同时 不产⽣新的edge 则直接将ek进⾏更新 此时x坐标不变 宽度不变 171 { 172 the_lowest_line_edge->y = the_lowest_line_edge->y + i_m_height;173 } 174 if ( I_m->isRotate )175 { 176 if ( H_packing < I_m->x + I_m->width )177 { 178 H_packing = I_m->x + I_m->width;179 }180 }181 else182 { 183 if ( H_packing < I_m->x + I_m->height )184 { 185 H_packing = I_m->x + I_m->height;186 }187 } 188 // 更新I 和E 集合 189 // 主要是更新集合E 更新Ei 的id 以及x y width 合并Ei 和Ei+1 190 for ( int i = 0; i< edgeInfos.size(); i++ )191 { 192 edgeInfos[i]->id = i;193 } 194 bool _tmp_delete = false; 195 for(int i = edgeInfos.size() - 1; i > 0 ;i-- )196 { 197 if ( edgeInfos[i]->y == edgeInfos[i-1]->y )198 { 199 edgeInfos[i-1]->width = edgeInfos[i-1]->width + edgeInfos[i]->width;200 edgeInfos[i]->isDelete = true;201 _tmp_delete = true;202 }203 }204 205 if ( _tmp_delete )206 { 207 std::vector 209 for( it= edgeInfos.begin();it!=edgeInfos.end();){210 211 if((*it)->isDelete){212 delete (*it); 213 edgeInfos.erase(it);214 break;215 }216 ++it;217 }218 219 for ( int i = 0; i< edgeInfos.size(); i++ )220 { 221 edgeInfos[i]->id = i;222 }223 } 224 for ( int i = 0; i< edgeInfos.size(); i++ )225 { 226 cocos2d::log( \" id :%d , x : %d, y : %d, width : %d \",edgeInfos[i]->id, edgeInfos[i]->x,edgeInfos[i]->y, edgeInfos[i]->width) ;227 }228 }229 }230 }231 }232 233 // 完全匹配优先 234 /* 在可装⼊的轮廓线中选取最低的⽔平线ek,如果有多个线段,则优先选取最左边的⼀段. 235 从待装矩形中按照装⼊序列依次将矩形与ek进⾏⽐较, 236 如果存在宽度或者⾼度与该线段宽度ek.w相等 237 且装⼊后刚好左填平或者右填平的矩形则优先装⼊. 238 完全匹配优先能够减少装⼊后产⽣的轮廓线数量,使得装⼊轮廓朝着顶部平齐的⽅向发展. 239 */ 240 int LLABF::FullFitFirst( SimpleEdgeInfo* edge ) //241 { 242 int result = -1; 243 // 存储宽度或者⾼度与edge相匹配的image 244 findEqualToEdgeWidth( edge);245 246 if ( equalWidthImages.size() > 0 ) // 存在和edge的宽度相等的image 然后求左填平 右填平 247 { 248 for( int i = 0; i < equalWidthImages.size(); i++ )249 { 250 if ( canLeftFill(equalWidthImages[i],edge) || canRightFill(equalWidthImages[i],edge))251 { 252 result = equalWidthImages[i]->id;253 break;254 }255 256 }257 } 258 return result;259 }260 261 /************************************************************************/262 /* 263 在装⼊过程中,优先装⼊宽度或者⾼度与最低⽔平线ek等宽的矩形, 264 如果存在多个匹配矩形,则优先装⼊⾯积最⼤的.与完全匹配优先规则不同的是, 265 宽度匹配优先并不要求装⼊后能够实现左填平或者右填平; 266 同时,该规则使得较⼩矩形有推迟装⼊的趋势.另外,WFF不会增加装⼊轮廓线数量. 267 */ 268 /************************************************************************/269 int LLABF::WidthFitFirst( SimpleEdgeInfo* edge )270 { 271 int result = -1; 272 // 存储宽度或者⾼度与edge相匹配的image 273 findEqualToEdgeWidth(edge); 274 if ( equalWidthImages.size() > 0 ) // 存在和edge的宽度相等的image 然后求矩形⾯积最⼤的image 275 { 276 int max_area = 0;277 int tmp_area; 278 SimpleImageInfo* max_area_image; 279 for( int i = 0; i < equalWidthImages.size(); i++ )280 { 281 tmp_area = equalWidthImages[i]->width * equalWidthImages[i]->height;282 if ( max_area < tmp_area )283 { 284 max_area = tmp_area; 285 max_area_image = equalWidthImages[i];286 }287 288 } 289 result = max_area_image->id;290 } 291 return result;292 } 293 /************************************************************************/294 /* 295 在待装矩形中,按照装⼊序列查询宽度或⾼度不⼤于最低⽔平线ek宽度且装⼊后能够实现左填平的矩形, 296 若存在则装⼊查询到的⾸个矩形. 297 与FFF和WFF不同,HFF可能会在最低⽔平线上产⽣新的、更⼩的可装⼊区域, 298 但却增加了轮廓线ek−1的宽度. 299 */ 300 /************************************************************************/301 int LLABF::HeightFitFirst( SimpleEdgeInfo* edge )302 { 303 int result = -1; 304 // 存储宽度或者⾼度不⼤于 edge.width 的 image 305 findLessOrEqualToEdgeWidth( edge ); 306 if ( lessOrEqualWidthImages.size() > 0 ) // 存在 则判断是否能左填平 307 { 308 for ( int i = 0; i< lessOrEqualWidthImages.size(); i++ )309 { 310 if ( canLeftFill( lessOrEqualWidthImages[i] , edge ) )311 { 312 result = lessOrEqualWidthImages[i]->id;313 }314 }315 } 316 return result;317 } 318 /************************************************************************/319 /* 320 按装⼊序列对两个矩形进⾏组合,如果组合后的宽度与最低⽔平线宽度ek相等,则优先装⼊组合序列中的⾸个矩形. 321 例如,存在两种组合I(i1).w+I(j1).w=ek.w, I(i2).w+I(j2).w=ek.w, 322 如果I(i1)的⾯积⼤于I(i2),则⾸先装⼊I(i1),否则装⼊I(i2). 323 */ 324 /************************************************************************/325 int LLABF::JointWidthFitFirst( SimpleEdgeInfo* edge )326 { 327 int result = -1;328 329 findJointEqualToEdgeWidth(edge);330 331 if ( joint_EqualWidthImages.size() > 0 ) // 存在组合和edge的宽度相等的image 然后求矩形⾯积最⼤的image 332 { 333 int max_area = 0;334 int tmp_area; 335 SimpleImageInfo* max_area_image; 336 for( int i = 0; i < joint_EqualWidthImages.size(); i++ )337 { 338 tmp_area = joint_EqualWidthImages[i]->width * joint_EqualWidthImages[i]->height;339 if ( max_area < tmp_area )340 { 341 max_area = tmp_area; 342 max_area_image = joint_EqualWidthImages[i];343 }344 345 } 346 result = max_area_image->id;347 } 348 return result;349 } 350 /************************************************************************/351 /* 352 在⼀定范围内,从待装矩形件中按照装⼊序列依次查找宽度或⾼度不⼤于最低⽔平线ek宽度的矩形, 353 若存在,则将其装⼊;若存在多个,则装⼊⾯积最⼤的矩形. 354 PF可能在最低⽔平线上产⽣新的、更⼩的可装⼊区域,同时使得较⼩矩形延迟装⼊. 355 */ 356 /************************************************************************/357 int LLABF::PlaceabelFirst( SimpleEdgeInfo* edge )358 { 359 int result = -1;360 361 findLessOrEqualToEdgeWidth(edge);362 363 if ( lessOrEqualWidthImages.size() > 0 ) // 存在和edge的宽度相等的image 然后求矩形⾯积最⼤的image 364 { 365 int max_area = 0;366 int tmp_area; 367 SimpleImageInfo* max_area_image; 368 for( int i = 0; i < lessOrEqualWidthImages.size(); i++ )369 { 370 tmp_area = lessOrEqualWidthImages[i]->width * lessOrEqualWidthImages[i]->height;371 if ( max_area < tmp_area )372 { 373 max_area = tmp_area; 374 max_area_image = lessOrEqualWidthImages[i];375 }376 } 377 result = max_area_image->id; 378 }379 380 return result;381 }382 383 void LLABF::findEqualToEdgeWidth( SimpleEdgeInfo * edge )384 { 385 equalWidthImages.clear(); 386 for ( int i = 0; i < imageInfos.size(); i++ )387 { 388 if ( !imageInfos[i]->isInRect )389 { 390 if ( imageInfos[i]->width == edge->width )391 { 392 equalWidthImages.push_back(imageInfos[i]);393 imageInfos[i]->isRotate = false;394 } 395 else if ( imageInfos[i]->height == edge->width )396 { 397 equalWidthImages.push_back(imageInfos[i]);398 imageInfos[i]->isRotate = true;399 } 400 }401 }402 }403 404 405 void LLABF::findLessOrEqualToEdgeWidth( SimpleEdgeInfo * edge )406 { 407 lessOrEqualWidthImages.clear(); 408 for ( int i = 0; i < imageInfos.size(); i++ )409 { 410 if ( !imageInfos[i]->isInRect )411 { 412 if ( imageInfos[i]->width <= edge->width )413 { 414 lessOrEqualWidthImages.push_back(imageInfos[i]);415 imageInfos[i]->isRotate = false;416 } 417 else if ( imageInfos[i]->height <= edge->width )418 { 419 lessOrEqualWidthImages.push_back(imageInfos[i]);420 imageInfos[i]->isRotate = true;421 } 422 }423 }424 }425 426 // 按装⼊序列对两个矩形进⾏组合,如果组合后的宽度与最低⽔平线宽度ek相等,则优先装⼊组合序列中的⾸个矩形 427 void LLABF::findJointEqualToEdgeWidth( SimpleEdgeInfo * edge )428 { 429 joint_EqualWidthImages.clear();430 int i_image_width = 0;431 int j_image_width = 0; 432 int edge_width = edge->width; 433 for ( int i = 0; i< imageInfos.size(); i++ )434 { 435 if ( !imageInfos[i]->isInRect )436 { 437 i_image_width = imageInfos[i]->width; 438 j_image_width = edge_width - i_image_width;439 for ( int j = 0; j< imageInfos.size(); j++ )440 { 441 if ( !imageInfos[j]->isInRect )442 { 443 if ( j_image_width == imageInfos[j]->width )444 { 445 joint_EqualWidthImages.push_back(imageInfos[i]);446 }447 448 }449 450 }451 }452 }453 }454 455 456 457 bool LLABF::canLeftFill( SimpleImageInfo * image, SimpleEdgeInfo * edge )458 { 459 if ( edge->id == 0 )460 { 461 return false;462 } 463 int tmpHeight = image->height;464 if ( image->isRotate )465 { 466 tmpHeight = image->width;467 }468 469 if ( tmpHeight == (edgeInfos[ edge->id - 1 ]->y - edge->y)) // 如果 image的⾼度和ek-1 - ek 的⾼度差相等，即可实现左填平 470 { 471 return true;472 } 473 return false;474 }475 476 bool LLABF::canRightFill( SimpleImageInfo * image, SimpleEdgeInfo * edge )477 { 478 if ( edge->id == edgeInfos.size() - 1 )479 { 480 return false;481 } 482 int tmpHeight = image->height;483 if ( image->isRotate )484 { 485 tmpHeight = image->width;486 } 487 if ( image->height == (edgeInfos[ edge->id + 1 ]->y - edge->y)) // 如果 image的⾼度和ek+1 - ek 的⾼度差相等，即可实现右填平 488 { 489 return true;490 } 491 return false;492 }493 494 int LLABF::getBigImageHeight()495 { 496 // 在E中选取最低⽔平线ek 497 int the_highest_y = 0; 498 for ( int j = 0 ; j< edgeInfos.size(); j++ )499 { 500 if ( the_highest_y < edgeInfos[j]->y )501 { 502 the_highest_y = edgeInfos[j]->y;503 } 504 } // 选取结束 505 return the_highest_y;506 } LLABF_Algorithem ⾥⾯都有注释，参照着论⽂应该都能明⽩。希望以后⾃⼰能够看懂。 下⾯就是根据信息，将⼩图的数据copy⾄⼤图内。⼩图旋转90度复制像素时，着实被坑了⼀把，后来⽅法没怎么改，只是将⼩图坐标固定，然后根据⼩图坐标去求⼤图坐标，也不知道怎么就正确了，玛蛋。 1 #ifndef __BIG_IMAGE_H__ 2 #define __BIG_IMAGE_H__ 3 #include \"cocos2d.h\" 4 #include \"HelloWorldScene.h\" 5 class SimpleImageInfo; 6 class BigImage 7 { 8 public : 9 BigImage();10 ~BigImage(); 11 BigImage( std::string bigFileName, int width, int height , std::string filePlist );12 13 void init();14 void publish(); 15 void initBigImageWithImagesData( std::vector< SimpleImageInfo* > * images );16 private: 17 std::vector 22 int m_dst_pixels_start_ptr; 23 unsigned char * m_dstImageData;24 std::string m_bigImageName;25 std::string m_plistName;26 };27 28 29 #endif BigImage 1 #include \"BigImage.h\" 2 //#include \"cocos2d/external/png/include/win32/png.h\" 3 //#include \"cocos2d/cocos/2d/platform/CCImage.h\" 4 #include 8 BigImage::BigImage() 9 :m_dstImageWidth(0) 10 ,m_dstImageHeight(0) 11 ,m_dst_ptr(0) 12 ,m_dst_pixels_start_ptr(0) 13 ,m_dataLen(0) 14 ,m_dstImageData(NULL) 15 ,m_bigImageName(\"test.png\") 16 { 17 18 } 19 20 BigImage::~BigImage() 21 { 22 free(m_dstImageData); 23 } 24 BigImage::BigImage( std::string bigFileName, int width, int height , std::string filePlist ) 25 { 26 m_bigImageName = bigFileName; 27 m_dstImageWidth = width; 28 m_dstImageHeight = height; 29 m_plistName = filePlist; 30 m_dataLen = m_dstImageWidth * m_dstImageHeight * 4; 31 this->init(); 32 } 33 34 void BigImage::init() 35 { 36 m_dstImageData = (unsigned char* )malloc(m_dstImageWidth * m_dstImageHeight * 4 ); 37 memset(m_dstImageData,0,m_dataLen); 38 } 39 40 void BigImage::publish() 41 { 42 std::string writablePath = FileUtils::getInstance()->getWritablePath(); 43 std::string fullPath_imageName = writablePath + m_bigImageName; 44 45 Image * new_image = new Image(); 46 new_image->initWithRawData( m_dstImageData,m_dataLen ,m_dstImageWidth,m_dstImageHeight,8 ); 47 new_image->saveToFile( fullPath_imageName,false); 48 49 // plist的根节点 50 Dictionary * dict_root = Dictionary::create(); 51 // plist下的frames节点 其内部为各个⼦图的信息节点 52 auto dict_frames = Dictionary::create(); 53 for ( int i = 0; i< imageInfos->size(); i++ ) 54 { 55 // small image name 56 SimpleImageInfo* srcImage = imageInfos->at(i); 57 auto imageDict = Dictionary::create(); 58 // frame 位置 图⽚⼤⼩ 59 auto str_frame = String::createWithFormat(\"{{%d,%d},{%d,%d}}\", srcImage->x,srcImage->y,srcImage->width,srcImage->height ); 60 imageDict->setObject(str_frame,\"frame\"); 61 // offset 62 auto str_offset = String::createWithFormat(\"{%d,%d}\",0,0 ); 63 imageDict->setObject(str_offset,\"offset\"); 64 // is rotated ? 65 auto b_rotate = Bool::create(srcImage->isRotate); 66 imageDict->setObject( b_rotate,\"rotated\"); 67 // sourceColorRect 68 auto str_colorRect = String::createWithFormat(\"{{%d,%d},{%d,%d}}\", 0,0,srcImage->width,srcImage->height ); 69 imageDict->setObject(str_colorRect,\"sourceColorRect\"); 70 // sourceSize 71 auto str_sourceSize = String::createWithFormat(\"{%d,%d}\", srcImage->width,srcImage->height ); 72 imageDict->setObject(str_sourceSize,\"sourceSize\"); 73 74 dict_frames->setObject( imageDict,srcImage->imageName ); 75 } 76 77 dict_root->setObject( dict_frames, \"frames\"); 78 79 // 根节点下的元数据节点 80 auto dict_metadata = Dictionary::create(); 81 82 auto intObject = Integer::create(2); 83 dict_metadata->setObject(intObject,\"format\"); 84 85 auto strObjectRealName = String::create(m_bigImageName); 86 dict_metadata->setObject(strObjectRealName,\"realTextureFileName\"); 87 88 auto strObjectSize = String::createWithFormat(\"{%d,%d}\", m_dstImageWidth, m_dstImageHeight); 89 dict_metadata->setObject( strObjectSize, \"size\"); 90 91 auto strObjectTextureFileName = String::create(m_bigImageName); 92 dict_metadata->setObject(strObjectTextureFileName,\"textureFileName\"); 93 94 dict_root->setObject( dict_metadata,\"metadata\"); 95 96 std::string fullPath_plist = writablePath + m_plistName; 97 if(dict_root->writeToFile(fullPath_plist.c_str())) 98 log(\"see the plist file at %s\", fullPath_plist.c_str()); 99 else 100 log(\"write plist file failed\");101 }102 103 void BigImage::initBigImageWithImagesData( std::vector 105 imageInfos = images;106 107 for ( int i = 0; i< images->size(); i++ )108 { 109 SimpleImageInfo* srcImageInfo = images->at(i);110 Image * srcImage = new Image(); 111 srcImage->initWithImageFile( srcImageInfo->imageName );112 unsigned char * srcImageData = srcImage->getData();113 ssize_t dataLen = srcImage->getDataLen();114 int srcImageWidth = srcImage->getWidth();115 int srcImageHeight = srcImage->getHeight();116 117 int nbitPerPixels = srcImage->getBitPerPixel();118 119 Point position = Point(srcImageInfo->x,srcImageInfo->y );120 int src_pixels_ptr = 0;121 122 if ( srcImageInfo->isRotate )123 { 124 int target_ptr = ( position.y * m_dstImageWidth + position.x ) * 4;125 126 src_pixels_ptr = ( srcImageWidth * srcImageHeight - srcImageWidth ) * 4;127 128 int target_pixels_start_ptr = target_ptr;129 int src_pixels_start_ptr = src_pixels_ptr;130 131 int inner_line_dert = m_dstImageWidth * 4; // 每⼀⾏的数据 132 int src_line_dert = 4 ; // 每⼀⾏的数据个数 133 134 for ( int i = 0; i< srcImageWidth; i++ )135 { 136 for ( int j = 0; j < srcImageHeight; j++ )137 { 138 m_dstImageData[ target_ptr ] = srcImageData[ src_pixels_ptr ]; 139 m_dstImageData[ target_ptr + 1 ] = srcImageData[ src_pixels_ptr + 1 ];140 m_dstImageData[ target_ptr + 2 ] = srcImageData[ src_pixels_ptr + 2 ]; 141 m_dstImageData[ target_ptr + 3 ] = srcImageData[ src_pixels_ptr + 3 ];142 target_ptr += 4; 143 src_pixels_ptr -= srcImageWidth * 4 ;144 }145 146 target_pixels_start_ptr += inner_line_dert;147 src_pixels_start_ptr += src_line_dert;148 149 src_pixels_ptr = src_pixels_start_ptr;150 target_ptr = target_pixels_start_ptr;151 }152 }153 else154 { 155 int target_ptr = ( position.y * m_dstImageWidth + position.x ) * 4;156 157 int src_pixels_start_ptr = src_pixels_ptr;158 int target_pixels_start_ptr = target_ptr;159 160 int inner_line_dert = m_dstImageWidth * 4; // 每⼀⾏的数据 161 int src_line_dert = srcImageWidth * 4; // 每⼀⾏的数据个数 162 163 for ( int i = 0; i< srcImageHeight; i++ )164 { 165 for ( int j = 0; j < srcImageWidth; j++ )166 { 167 m_dstImageData[ target_ptr ] = srcImageData[ src_pixels_ptr ]; 168 m_dstImageData[ target_ptr + 1 ] = srcImageData[ src_pixels_ptr + 1 ];169 m_dstImageData[ target_ptr + 2 ] = srcImageData[ src_pixels_ptr + 2 ];170 m_dstImageData[ target_ptr + 3 ] = srcImageData[ src_pixels_ptr + 3 ];171 target_ptr += 4;172 src_pixels_ptr += 4;173 }174 175 target_pixels_start_ptr += inner_line_dert;176 src_pixels_start_ptr += src_line_dert;177 178 src_pixels_ptr = src_pixels_start_ptr;179 target_ptr = target_pixels_start_ptr;180 }181 182 }183 184 185 delete srcImage;186 }187 188 } BigImage 估计可能是刚开始计算时，是按照左下⾓是坐标原点计算的。但是，实际上Image的data是以左上⾓为（0,0）点的。所以尽管⽅法对，但是因为⼀个是左⼿坐标系，⼀个是右⼿坐标系，所以才导致错误的。 这样看，⾸先确定坐标原点是多么重要的⼀件事。 LLABF算法，还没有texturepacker采⽤的maxRects算法优。但是结果还算是可以吧，加上⼈的智慧，其实也可以合出不错的图。⼤图的⾼度是根据LLABF算法返回的数据确定的，没有取2的整数次幂。想取的可以取。感觉不太必要。本博⽂的原意是解释⼀下程序的，但是发现注释其实挺多的，还有论⽂做参照，就不卖弄了。 遗传算法是个什么玩意？有时间再搞吧，加上遗传算法不知道是不是就会超过maxRects算法了，值得期待，期待⽆期啊。。。。。%>_<%。。。。 差点忘了，hb说，可以类似于kd树的⽅法去做，⾸先选出⾯积最⼤的⼩图，放⼊后，整个空间就被该图将剩余空间划分成了左右⼦树，然后在各个⼦树内采⽤同样的⽅式放⼊剩余⼩图。 没有细想，有看到这篇博⽂的可以试下，hb说这种树的⽅式算是最优的了。我没有试，所以不造真假。 因篇幅问题不能全部显示，请点此查看更多更全内容