osu-framework icon indicating copy to clipboard operation
osu-framework copied to clipboard

Implement `IRectanglePacker` interface and various packing algorithms

Open EVAST9919 opened this issue 2 years ago • 2 comments

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: Снимок экрана (13)

EVAST9919 avatar Sep 15 '23 04:09 EVAST9919

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.

peppy avatar Sep 15 '23 05:09 peppy

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

EVAST9919 avatar Sep 17 '23 03:09 EVAST9919