Skyline packer

[basil-cow]

I've read about skyline heuristics given in 2011 and 2016 works and they both work by trying to achieve as low height as possible given a width of a spritesheet.

1. I'm not sure how to adopt this to output multiple spritesheets, since their approach relies heavily on being able to shuffle the input. One possible approach is trying to fit it into one spritesheet, then if it fails, splitting the input randomly into two parts and trying to fit it into two spritesheets and so on. I'm not sure this is an optimal approach and would like to hear your thoughts.

2. I'm not sure how to choose the width of a spritesheet, I don't really like maxrects approach of giving it a default value since in it will just produce a long horizontal stripe of sprites and that doesn't feel optimal (maybe it's really efficient or doesn't make a difference at all, I don't know). So I propose to make some kind of algorithm on top of skyline (and maybe maxrects too) that tries to determine optimal width and height. Again, I'd like to hear your thoughts.

[happenslol]

Hey again! Thanks for being so active on this project, I really appreciate the help =)

I reommend you first have a look at this, which is a very comprehensive explanation and benchmark of most known bin packing algorithms. The accompanying reference implementation and benchmarks can be found here. It's what I looked at for the maxrects implementation, and it seems maxrects mostly outperforms skyline except for when it comes to online packing scenarios (i.e. when you're getting the sprites one after another instead of all at once).

As for your questions:

1. Iterating and doing the algorithm multiple times doesn't seem like a very effective approach to me at first glance - Depending on the input sprites, you're almost guaranteed an increase in time complexity at some point. Generally there's a few approaches I can imagine - You can keep packing things into the same bin until it's "filled", and then either close it or keep it open and check every time you have a new sprite whether it fits into an existing bin or needs a new one. You can extend this by calculating a score for "least space left over" or some other heuristic and choose a bin based on that.

2. Actually it doesn't matter at all! I was concerned about this at the start too. I wrote the first version of the rect packer back when OpenGL ES still required quadratic textures, which was a royal pain in the ass and made the implementation of such algorithms much harder than it needed to be. At this point, it doesn't matter - we can just find out a good max size (dependant on the max texture size imposed by graphics APIs) and then stick with that.
   One solution I could imagine would be to start with a much lower bin size, and then, as the rectangle fills up, gradually increasing it up until the max. This would cause the "inner rectanlges" to fill up first, avoiding the strip of images you're describing. However, if a strip results from maxrects, you can be pretty sure that it's optimal.

[basil-cow]

Yeah, I have read both the implementation and the paper you linked but unfortunately they came before both of the mentioned articles. The complexity of the skyline algorithm was improved from O(n^2) to O(nlogn) and the authors of the 2016 paper claim to outperform all other algorithms given a time constraint. I couldn't find a more recent comparison.

As for iterating and redoing the algorithm multiple times - with O(nlogn) vs O(n^2logn) (as far as I understood) maxrects average complexity you can afford it and it's a major point of the algorithm. So the user can input a time constraint and kinda regulate how good of a result they want to get.

[happenslol]

Oh, very interesting! I'll be sure to look into the newer studies further then. And yes you're right, O(nlogn) would be far cheaper, the free list culling does take a lot of time with maxrects.

For now, we could definitely use a very simple heuristic for choosing a bin (such as best first fit), and see if we can find something better once we have the algorithm implemented - benchmarking will also become much easier then.

[basil-cow]

Ok, so I'll commit a basic variant in a few hours I guess.

[happenslol]

Sounds great! I'm actually pretty excited to match these 2 against each other and see what happens =P