二维矩形装箱问题

装箱问题，是个NP问题。至于装箱问题到底是个什么东西，可以看看百度文档http://wenku.baidu.com/view/f6e7f80590c69ec3d5bb755f.html。其实我没看。

研究二维矩形装箱问题，是因为需要将小图拼成大图，作为一个大的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::Layer
11 {
12 public:
13     ~HelloWorld();
14     // there's no 'id' in cpp, so we recommend returning the class instance pointer
15     static cocos2d::Scene* createScene();
16 
17     // Here's a difference. Method 'init' in cocos2d-x returns bool, instead of returning 'id' in cocos2d-iphone
18     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 manually
26     CREATE_FUNC(HelloWorld);
27 
28     std::vector<SimpleImageInfo*> imageInfos;
29 
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  <math.h>
  4 #include  <iostream>
  5 #include  <fstream>
  6 #include  <string>
  7 
  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 #endif
105 }
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         //如果你只想简单的操作你现在可以实际读取图片信息了！