happenslol
commented
5 years ago 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:
-
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.
-
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
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.
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.
I'm not sure how to choose the width of a spritesheet, I don't really like
maxrectsapproach 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.