Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


fitting small rectangles into a large rectangle


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
12 replies to this topic

#1 krez   Members   -  Reputation: 443

Like
0Likes
Like

Posted 27 April 2007 - 08:57 PM

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.

Sponsor:

#2 Promit   Moderators   -  Reputation: 9863

Like
0Likes
Like

Posted 27 April 2007 - 09:26 PM

The Packing Problem is what you're looking for, yes?

#3 Deyja   Members   -  Reputation: 920

Like
0Likes
Like

Posted 28 April 2007 - 12:09 AM

http://www.angelcode.com/products/bmfont/

#4 krez   Members   -  Reputation: 443

Like
0Likes
Like

Posted 30 April 2007 - 02:56 PM

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!

#5 mattnewport   GDNet+   -  Reputation: 1030

Like
0Likes
Like

Posted 30 April 2007 - 03:13 PM

Here's one way to do it. It's far from perfectly optimal but it usually works reasonably well.

#6 scgames   Members   -  Reputation: 2038

Like
0Likes
Like

Posted 30 April 2007 - 03:19 PM

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.

#7 utilae   Members   -  Reputation: 188

Like
0Likes
Like

Posted 12 May 2007 - 07:36 PM

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 ©: 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;
}
};






#8 Necator   Members   -  Reputation: 239

Like
0Likes
Like

Posted 12 May 2007 - 09:37 PM

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

#9 Deaken Frost   Members   -  Reputation: 133

Like
0Likes
Like

Posted 12 May 2007 - 11:54 PM

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

#10 utilae   Members   -  Reputation: 188

Like
0Likes
Like

Posted 13 May 2007 - 12:08 AM

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



#11 errcw   Members   -  Reputation: 169

Like
0Likes
Like

Posted 13 May 2007 - 09:48 AM

I, too, recently needed a rectangle packing algorithm to stuff images into an overall palette. I was thoroughly surprised to discover that truly optimal rectangle packing is an area of active research. It appears that this paper describes the current cutting-edge solution. What again surprised me was that packing even 20 rectangles took over 15 minutes! So, even applying a state of the art constraint satisfaction problem solution algorithm, the problem is still very difficult.

I suppose the moral of my research is that any decent (read: works well enough for you) heuristic solution should be fine, and that implementing a genuinely optimal algorithm is likely infeasible for packing even small numbers of elements.

#12 utilae   Members   -  Reputation: 188

Like
0Likes
Like

Posted 13 May 2007 - 01:42 PM

Quote:
Original post by errcw
What again surprised me was that packing even 20 rectangles took over 15 minutes!

15 minutes! Mine seems to pack about 50 rectangles of various sizes, neatly and instantly. Seems strange.



#13 Deaken Frost   Members   -  Reputation: 133

Like
0Likes
Like

Posted 14 May 2007 - 05:24 AM

Quote:
15 minutes! Mine seems to pack about 50 rectangles of various sizes, neatly and instantly. Seems strange.

The paper deals with optimal rectangle packing. Your method may be fast, but hardly optimal.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS