Jump to content
  • Advertisement
Sign in to follow this  
FantasyVII

Bin packing

This topic is 546 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

Hi everyone,

 

I'm having trouble understand this algorithm 

http://blackpawn.com/texts/lightmaps/default.html

 

Here what I understood from the algorithm.

 

First lets assume my large texture is 128 x 128. Lets also assume the first texture I want to add is 32 x 32 pixels. So according to the algorithm I have to split my big texture into two regions. After that I add the 32 x 32 blue texture. At this point my tree and texture looks something like this

 

b3Jex0A.jpg

 

After that lets assume the next texture I want to pack is 32 x 96 green texture. So my tree would look something like this,

 

YVlwu0x.jpg

 

finally lets try and add another 32x32 pink texture. Here is my problem.

 

4kELtdL.jpg

 

 

When I look at node 0 and 1 I can see that the 32 x 32 pink texture can fit in both nodes. but since node 0 is first, I will pick that node. But if you go down the tree you can see that the last node size is 0, 0 which means there is no space left. My question is now what do I do? if I just go back to the root node and do the same thing I will get to the same consultation. Unless I have to somehow update node 0 every time I add a new texture. But if that is the case he never explained how that would work.

 

I don't understand this algorithm. Any help would be appreciated. 

 

Cheers.

Edited by FantasyVII

Share this post


Link to post
Share on other sites
Advertisement

A recursive traversal of the tree will - when it gets back to the root node - look at the 2nd child instead of looking at the 1st child again.
 
You can see this in the code example you linked to: if child[0]->Insert( img ) failed, it then tries child[1]->Insert( img )

Edited by Kylotan

Share this post


Link to post
Share on other sites

A recursive traversal of the tree will - when it gets back to the root node - look at the 2nd child instead of looking at the 1st child again.
 
You can see this in the code example you linked to: if child[0]->Insert( img ) failed, it then tries child[1]->Insert( img )

 

So my tree looks right? only thing I have to do is go to node 1 instead of node 0 if node 0 fails?

Share this post


Link to post
Share on other sites

Sure, it looks correct. The key is to remember that you don't have to think about the tree as a whole - the algorithm just deals with the current node and the 2 children at each step. That's why it 'knows' to go back up to the 96x128 node; the 32x96 fails, because both children are full. So its parent (32x128) also fails, since both its children are full too. Then we're back up to the root node (128x128) and that will succeed, because it'll be able to find space inside the 96x128 child node.

Share this post


Link to post
Share on other sites

Hi everyone,

 

I'm having trouble understand this algorithm 

http://blackpawn.com/texts/lightmaps/default.html

 

Here what I understood from the algorithm.

 

First lets assume my large texture is 128 x 128. Lets also assume the first texture I want to add is 32 x 32 pixels. So according to the algorithm I have to split my big texture into two regions. After that I add the 32 x 32 blue texture.

After that lets assume the next texture I want to pack is 32 x 96 green texture. So my tree would look something like this,...

 

Blocks are first sorted by height, so you will never insert a smaller block before a larger block.

If insertion fails, then you may have to re-initialized it with a slightly larger tree, and start over again.

 

Edited by sevenfold1

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!