The Plasma Engine

In the first post, we looked at some of the difficulties of rectangle packing and how the easy algorithms can fail. While the recursive algorithm can work well for lots of similarly-shaped rectangles, it falls apart when we have fewer rectangles or a large variety of shapes. So I decided to start from scratch, trying to come up with an algorithm which could sort the rectangles below:

It isn’t possible to fit these rectangles as shown with a recursive algorithm, because there is no line which goes all the way through any of the spaces a recursive algorithm would create. So I did some more research and decided to use a stripe-based algorithm. Instead of sorting by area, a stripe algorithm sorts all the rectangles by height. It them puts the tallest rectangle at the top-left corner, creates an area to the right of that rectangle, fills it in as best as possible, and repeats.

We can split this algorithm into basically 5 steps:

1. Sort rectangles by height
2. Put the tallest rectangle into the map on the far left side, below the last stripe
3. Create a stripe with a height of the rectangle from step 2 and width of the area remaining to the right of the rectangle
4. Fill in this stripe
5. If we still have more rectangles, go to step 2.

The tricky part of this algorithm is step 4 – there are a lot of ways to fill in the stripe. You could use the recursive algorithm discussed in the previous post, but it would still fail with the 5-rectangle example above. The algorithm I’m currently using is somewhat like a Tetris game played upside-down. I put all the rectangles I can against the top of the stripe, then fill in below them recursively. I use a hight-map of the free space to keep track of where it is safe to place new rectangles. After filling in the top of the stripe, we end up with the layout in step 1.

From that layout, we take the coordinates of the bottom corners of the rectangles to create a hight map. We then try to fill in the tallest area of the hight map, as shown in step 2.

We find that the cyan colored rectangle fits here, so we put it in the right side of the shaded area, and re-calculate our hight map. We again find the tallest area of the height map and try to fill it with the remaining pink rectangle.

The remaining pink rectangle won’t fit into the shaded area left in step 3, so we modify our height map.  We toss out the tallest portion so a wider portion remains. We then repeat and try to fill in the area in step 4.

We get lucky in step 4 and the pink rectangle happens to fit into the remaining space. We put it there are return, now that all the rectangles have been placed.

While this algorithm isn’t perfect, it seems to work really well for Plasma’s needs. It is fast and better at packing a small number of rectangles than the recursive algorithm.

There are a few improvements which I’d still like to investigate for this algorithm. When a texture doesn’t fit, I could try rotating it 90 degrees and trying again. I haven’t tested yet to see if this will have an effect on drawing performance, but it will probably help the packing efficiency. Also, I could try keeping track of the height map from the last stripe when packing the next one. That way, instead of putting new textures at the top of the strip, I might be able to shift them up a little bit further.

So far, the new packing algorithm has been working out really well. I haven’t had a need to implement any of the above improvements, because it is already efficient enough and runs very fast. It doesn’t have the problems I ran into with the recursive algorithm. I think the results speak for themselves:

Leave a response Trackback