# Bin packing

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

## 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

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,

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

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

Edited by Kylotan

##### 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 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 on other sites

Depth First Search recursive algorithm.

##### 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

1. 1
2. 2
Rutin
22
3. 3
4. 4
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633742
• Total Posts
3013639
×