Skip to content

Rectangle Bin Packing – Turning it to 11

September 20, 2013

Remember the rectangles? Well, I was playing around with trying to get a heuristic which approaches the best possible packing – not just a good balance of speed vs packacity. I have finally succeeded in producing a new packing strategy which consistently beats all others!

Unfortunately it is has a cubic, rather than linear time complexity.

Anyway! The algorithm is pretty horrible. For each pixel on the edge of a possible rectangle allocation, it casts out along the edge normal to find the nearest used pixel (or border of the atlas), requiring that all heuristic invocations iterate over every allocated region. Then, it sums up the logarithm (because as the distance increases, the relative importance of it drops) of the ray lengths, for each pixel on each edge. I have used the minimize area system as a tiebreaker. To improve it further, I’ve made it attempt N positions within each free rectangle – aligning the corners with other allocated regions. I guess I could have tested each pixel, which could allow me to claim the time complexity is only quadratic… Hmmm!

It did do better than the others – getting past the dreaded allocation #63! Unfortunately, the thing really did run slowly. Like, many hundreds of time slower, for my tiny test program. Oh well, I’m sure you can’t wait to see it in action. Here it is!

Rects-SuperHeuristicRects-SuperHeuristicSmall

Update

Well obviously I was going to try checking all the pixels after musing that aloud on this post. It actually didn’t do as well on the normal test – that big beige alloc (#63) is a jerk and it’s really hard for the heuristics to deal with it. But on the small alloc test…

Brute force wins the day. Actually this is animating about 5x faster than I could generate it.

Brute force wins the day. Actually this is animating about 5x faster than I could generate it.

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: