Jump to content
  • Advertisement
Sign in to follow this  
krez

fitting small rectangles into a large rectangle

This topic is 4110 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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. :)


//in .cpp file
//note: all lists are 'vectors' cause vectors are cool. :)
//Combine all textures in MergeList into one texture
void 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 textures
struct 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;
}
};




Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
This should be faster:


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 :)

Share this post


Link to post
Share on other sites
Lol, thats not exactly my most critical bit of code anyway. If it was something that was running all the time, sure.

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'.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!