Implement `IRectanglePacker` interface and various packing algorithms
A step towards resolving https://github.com/ppy/osu-framework/issues/5986.
TextureAtlas has been reworked to support new IRectanglePacker interface, so switching the algorithm is a one line change. For now it's using the same algo as previously since I'm not sure about performance concerns (probably benchmarking needed).
Also adds a nice test scene to play around with:
If performance is a perceived concern, I'd recommend adding benchmarks. They should be very simple to create, since we already have all the tooling in place.
So I've added some benchmarks in which I'm creating and populating bins with 20 rectangles of various sizes. As you can see the difference is quite big. Basically we are trading performance for potential capacity (as expected, probably). From these we can assume that Guillotine is a good middle ground, although it can peroform worse than Shelf (currently used in TextureAtlas on master) in some cases fitness-wise and practially it's trash when in comes to adding a big rectangle after many small ones because it's best use-case is when upcoming rectangles are sorted beforehand. However with the underlying structure we can easily track big chunks of previously wasted space (as per issue) and removing a rectangle is as simple as adding the new empty space to already existing list, which is a desired behavior. Also note that my implementation probably isn't perfect and can potentially be improved.
| Method | Mean | Error | StdDev | Gen0 | Allocated |
|---|---|---|---|---|---|
| PopulateShelf | 914.7 ns | 1.48 ns | 1.38 ns | 0.0191 | 40 B |
| PopulateShelfRemainder | 1,039.4 ns | 2.06 ns | 1.92 ns | 0.0381 | 80 B |
| PopulateGuillotine | 11,709.0 ns | 29.93 ns | 28.00 ns | 0.5341 | 1128 B |
| PopulateMaximal | 337,441.9 ns | 1,453.73 ns | 1,359.82 ns | 0.9766 | 2176 B |