fitting small rectangles into a large rectangle
Author
is there an algorithm that can fill a rectangle with other rectangles in the most space efficient way possible (without overlap)? the inner rectangles are not the same size, and the outer rectangle needs to have power-of-two dimensions.
basically i am trying to render each character of a font onto a single texture, and keep that texture as small as possible (well maybe not small as possible, but i do not want to just create a giant texture and waste a LOT of space).
i don't know what terms to search for in this case, or if such an algorithm even exists. but if anyone knows of something that might help i'd appreciate it.
Author
Promit, thank you, now i know what i am looking for!
Deyja, that's nifty and i'm going to play with it, but i want to do it at run time.
Thanks to both of you!
Deyja, that's nifty and i'm going to play with it, but i want to do it at run time.
Thanks to both of you!
I posted some bin-packing code to this thread a while back. It's nothing special, but might at least serve as a point of reference.
The algorithm used is similar to that described in the link mattnewport posted above. It was written for lightmaps, specifically elongated lightmaps (you can see some example output in the thread), but I imagine it would work for fonts as well.
The algorithm used is similar to that described in the link mattnewport posted above. It was written for lightmaps, specifically elongated lightmaps (you can see some example output in the thread), but I imagine it would work for fonts as well.
Here is what I did recently.
I have a 'vector' list full of special texture structures that I want to merge into one big texture.
This function does the job. Note: There are bits in there that you may not understand since I have not given you the information about every 'structure/class'. But that's where you put your own classes in anyway.
The function does a pretty good job of packing the textures into the most square texture with the least space wasted.
Please comment. :)
I have a 'vector' list full of special texture structures that I want to merge into one big texture.
This function does the job. Note: There are bits in there that you may not understand since I have not given you the information about every 'structure/class'. But that's where you put your own classes in anyway.
The function does a pretty good job of packing the textures into the most square texture with the least space wasted.
Please comment. :)
//in .cpp file//note: all lists are 'vectors' cause vectors are cool. :)//Combine all textures in MergeList into one texturevoid CTextureManager::MergeTextures(const string &sMergedTextureName,const bool &bClearTextures){ //sort m_lstMergeList, largest area first, smallest last sort(m_lstMergeList.begin(),m_lstMergeList.end(),LOADEDTEXTURE()); vector <RECT> lstFilledRects;//list of inserted textures to make up final merged texture vector <RECT> lstHoles;//holes in merged texture that have to be filled with textures //use total area of all textures to be merged, to try and make the final texture as square as possible double dTextureWidth=sqrt(m_dTotalArea); if(dTextureWidth<32) dTextureWidth=32; else if(dTextureWidth>32 && dTextureWidth<64) dTextureWidth=64; else if(dTextureWidth>64 && dTextureWidth<128) dTextureWidth=128; else if(dTextureWidth>128 && dTextureWidth<256) dTextureWidth=256; else if(dTextureWidth>256 && dTextureWidth<512) dTextureWidth=512; else if(dTextureWidth>512 && dTextureWidth<1024) dTextureWidth=1024; else if(dTextureWidth>1024) dTextureWidth=2048; //could put in more for bigger textures //the first hole is the container, the final size of the merged texture RECT recContainer; recContainer.top=0; recContainer.left=0; recContainer.right=dTextureWidth; recContainer.bottom=dTextureWidth; lstHoles.push_back(recContainer); //put every texture to merge in a hole bool bBreak=false; vector<RECT>::iterator itHole=lstHoles.begin(); vector<LOADEDTEXTURE>::iterator itTexture=m_lstMergeList.begin(); while(itTexture!=m_lstMergeList.end() && bBreak==false) { //go back to first hole if there are still textures to put in holes if(itHole>=lstHoles.end()) itHole=lstHoles.begin(); //keep placing textures within merged texture as long as there are holes to place them in if(lstHoles.empty()==true) bBreak=true; else { //determine bin width and height int nHoleHeight=itHole->bottom-itHole->top; int nHoleWidth=itHole->right-itHole->left; //case (e) or (f): texture too tall for bin or too wide for bin if(itTexture->m_nHeight > nHoleHeight || itTexture->m_nWidth > nHoleWidth) ++itHole;//cannot fit in bin, try next hole else //can fit { //will fit in bin so put texture in top left RECT newFilledRect; newFilledRect.top=itHole->top; newFilledRect.left=itHole->left; newFilledRect.right=itHole->left+itTexture->m_nWidth; newFilledRect.bottom=itHole->top+itTexture->m_nHeight; recContainer.bottom=newFilledRect.bottom; lstFilledRects.push_back(newFilledRect); //add replacement holes if there are any RECT newHole; //case (a): Perfect width. Too short. if(itTexture->m_nWidth==nHoleWidth) { //case (a): Perfect width. Too short. if(itTexture->m_nHeight<nHoleHeight) { //one hole below newHole.top=itHole->top+itTexture->m_nHeight; newHole.left=itHole->left; newHole.right=itHole->right; newHole.bottom=itHole->bottom; lstHoles.push_back(newHole); itHole=lstHoles.begin(); } //case (d): Perfect width and height. else if(itTexture->m_nHeight==nHoleHeight) { //no holes } } else if(itTexture->m_nWidth<nHoleWidth) { //case (b): Too narrow. Too short. if(itTexture->m_nHeight<nHoleHeight) { //one hole below newHole.top=itHole->top+itTexture->m_nHeight; newHole.left=itHole->left; newHole.right=itHole->left+itTexture->m_nWidth; newHole.bottom=itHole->bottom; lstHoles.push_back(newHole); itHole=lstHoles.begin(); //one hole to right newHole.top=itHole->top; newHole.left=itHole->left+itTexture->m_nWidth; newHole.right=itHole->right; newHole.bottom=itHole->bottom; lstHoles.push_back(newHole); itHole=lstHoles.begin(); } //case (c): Too narrow. Perfect height. else if(itTexture->m_nHeight==nHoleHeight) { //one hole to right newHole.top=itHole->top; newHole.left=itHole->left+itTexture->m_nWidth; newHole.right=itHole->right; newHole.bottom=itHole->bottom; lstHoles.push_back(newHole); itHole=lstHoles.begin(); } } //remove old hole lstHoles.erase(itHole); //sort list of holes sort(lstHoles.begin(),lstHoles.end(),compareHoleRects()); ++itTexture; } } } //create texture the size of 'container' LOADEDTEXTURE newTexture; HRESULT hrCreateTex=D3DXCreateTexture(g_pD3DDevice9,recContainer.right,recContainer.bottom,D3DX_DEFAULT,0,D3DFMT_A8R8G8B8,D3DPOOL_MANAGED,&newTexture.m_texture); g_Log<<"MergeTextures("<<sMergedTextureName<<") Create Texture: "<<DXGetErrorString9(hrCreateTex)<<endl; //setup surfaces for copying textures LPDIRECT3DSURFACE9 pSrcSurface=NULL; LPDIRECT3DSURFACE9 pDestSurface=NULL; newTexture.m_texture->GetSurfaceLevel(0,&pDestSurface); //get correct width and height of texture (incase texture size is adjusted automatically when created) D3DSURFACE_DESC surfaceDesc; newTexture.m_texture->GetLevelDesc(0,&surfaceDesc); recContainer.right=surfaceDesc.Width; recContainer.bottom=surfaceDesc.Height; //store textures filename, height and width newTexture.m_sName=sMergedTextureName; newTexture.m_nHeight=recContainer.bottom; newTexture.m_nWidth=recContainer.right; newTexture.m_nArea=recContainer.bottom*recContainer.right; //go through list of textures and filled rects and copy textures to container texture sort(m_lstMainTextureList.begin(),m_lstMainTextureList.end(),SortByNameAscending<LOADEDTEXTURE>()); vector<RECT>::iterator itCurrentRECT=lstFilledRects.begin(); vector<TILE>::iterator itTiles; while(itCurrentRECT!=lstFilledRects.end()) { //copy from texture to container texture m_lstMergeList[0].m_texture->GetSurfaceLevel(0,&pSrcSurface); D3DXLoadSurfaceFromSurface(pDestSurface,NULL,&(*itCurrentRECT),pSrcSurface,NULL,NULL,D3DX_FILTER_NONE,0); pSrcSurface->Release(); //add tiles to merged texture, from each texture itTiles=m_lstMergeList[0].m_TileList.begin(); while(itTiles!=m_lstMergeList[0].m_TileList.end()) { //recalculate tile coordinates TILE newTile; newTile.m_sName=itTiles->m_sName; newTile.m_tvTop=(float)((itTiles->m_tvTop*m_lstMergeList[0].m_nHeight)+itCurrentRECT->top)/recContainer.bottom; newTile.m_tuLeft=(float)((itTiles->m_tuLeft*m_lstMergeList[0].m_nWidth)+itCurrentRECT->left)/recContainer.right; newTile.m_tuRight=(float)((itTiles->m_tuRight*m_lstMergeList[0].m_nWidth)+itCurrentRECT->left)/recContainer.right; newTile.m_TvBottom=(float)((itTiles->m_TvBottom*m_lstMergeList[0].m_nHeight)+itCurrentRECT->top)/recContainer.bottom; //add a tile onto the tile list newTexture.m_TileList.push_back(newTile); ++itTiles; } //clear textures in main texture list if(bClearTextures==true) { int nTexIndex=BinarySearch(m_lstMainTextureList,m_lstMergeList[0].m_sName); if(nTexIndex!=-1) { //release textures and set texture pointer to null if(m_lstMainTextureList[nTexIndex].m_texture) m_lstMainTextureList[nTexIndex].m_texture->Release(); m_lstMainTextureList[nTexIndex].m_texture=NULL; //clear tile list and remove loadedtexture object from main texture list m_lstMainTextureList[nTexIndex].m_TileList.clear(); m_lstMainTextureList.erase(m_lstMainTextureList.begin()+nTexIndex); } } //set texture pointer to null m_lstMergeList[0].m_texture=NULL; //clear tile list and erase loadedtexture from merge list m_lstMergeList[0].m_TileList.clear(); m_lstMergeList.erase(m_lstMergeList.begin()); ++itCurrentRECT; } pDestSurface->Release(); //put texture into list m_lstMainTextureList.push_back(newTexture); m_lstMergeList.clear(); lstHoles.clear(); lstFilledRects.clear(); m_dTotalArea=0; //add tile for whole texture automatically AddTile(sMergedTextureName,"MAIN",1,1,recContainer.right,recContainer.bottom);//top, left, right, bottom}//in .h file - used for sorting://compare holes when merging texturesstruct compareHoleRects{ bool operator() (const RECT &recA, const RECT &recB) { if (recA.top < recB.top) return true; if (recA.top == recB.top) return (recA.right-recA.left) < (recB.right-recB.left); return false; }};
Just a neat trick I remembered.
any of these should work. 2 might look a bit nicer. I haven't profiled any of them, but I think that the second one should be faster given that the optimizer recognizes that we're calculating a power of two with the pow.
dTextureWidth = double( 1<< ( int(ceil( log(dTextureWidth)/log(2))));
or
dTextureWidth = pow( 2, ceil( log(dTextureWidth)/log(2)));
What it basically does is calculate the number of bits necessary to represent the width, rounds it up and then just calculates 2^bits.
edit: Changed ln to log (been using my TI-calculator too much).
any of these should work. 2 might look a bit nicer. I haven't profiled any of them, but I think that the second one should be faster given that the optimizer recognizes that we're calculating a power of two with the pow.
dTextureWidth = double( 1<< ( int(ceil( log(dTextureWidth)/log(2))));
or
dTextureWidth = pow( 2, ceil( log(dTextureWidth)/log(2)));
What it basically does is calculate the number of bits necessary to represent the width, rounds it up and then just calculates 2^bits.
edit: Changed ln to log (been using my TI-calculator too much).
This should be faster:
It only works for 32-bit integers, but can be easily modified to work with 64-bit integers. But i highly doubt that we will ever need textures with dimensions that can't be represented using 32-bit integers :)
unsigned int nextPowerOf2(unsigned int value){ --value; value |= value >> 1; value |= value >> 2; value |= value >> 4; value |= value >> 8; value |= value >> 16; ++value; return value;}It only works for 32-bit integers, but can be easily modified to work with 64-bit integers. But i highly doubt that we will ever need textures with dimensions that can't be represented using 32-bit integers :)
Lol, thats not exactly my most critical bit of code anyway. If it was something that was running all the time, sure.
I tried to implement this, but is seems incomplete. Plus I just thought that going up and down the tree would be too slow. I went for a more direct method, straight loop through the vector, i'm not sure what you call it, a 'line' as opposed to a 'tree'.
Quote:Original post by mattnewport
Here's one way to do it. It's far from perfectly optimal but it usually works reasonably well.
I tried to implement this, but is seems incomplete. Plus I just thought that going up and down the tree would be too slow. I went for a more direct method, straight loop through the vector, i'm not sure what you call it, a 'line' as opposed to a 'tree'.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement