3 ms·
I'm sure Aseprite could be further optimised to press down the constant factor, but it is performing a rect packing algorithm among other things, which is an NP
by Shinmera 4y ago
I'm sure Aseprite could be further optimised to press down the constant factor, but it is performing a rect packing algorithm among other things, which is an NP-hard problem.
- rednab 4y agoThe bin packing problem is NP-hard, but rectangle packing is "merely" NP. However, most people just use a recursive biggest-fit-first ¹), a simple heuristic that is surprisingly hard to beat for most workloads. I couldn't figure out what Aseprite is doing from their website or documentation, but if it's not that then it might be worth it writing your own sprite packer. ¹) https://codeincomplete.com/articles/bin-packing/ https://codeincomplete.com/articles/bin-packing/
- Shinmera 4y agoYeah I don't know what they use either, but so far repacking that atlas has not been frequent enough that writing my own packer would save time.