Not knowing anything, I started this adventure by attempting to understand a rectangle packing library called stb_rect_pack, it’s public domain, easy to use and I figured would be a great place for me to start learning.
Note I’m only going to explore a few packing algorithms I found in my research, but there truly are endless amounts of these. Thus you have to pick what suits your needs, which is what we’ll attempt to do here. As a result, there are countless different algorithms that “solve” the problem to some degree, but all have tradeoffs and issues. I don’t understand computational complexity enough to define that in detail, but suffice to say it’s extremely difficult and does not have a “perfect” solution. The tricky thing is, this is what’s called an NP-hard (non-deterministic polynomial) problem. In game development, we’re used to 2D packing problems, and more specifically the rectangle packing problem, where you have some set of rectangles of different dimensions and you need to fit them into a containing rectangle. More generally, “packing” problems are a set of problems related to fitting shapes into some kind of container. What is a rectangle packing algorithm?īefore we get stuck into the details lets just take a moment to get everyone on the same page as to what a rectangle packing algorithm is. What I came away with though was an appreciation for how sometimes the simplest option is a much better option that you might care to admit. So here I am several weeks later, still not quite finished texture packing my fonts after having explored several algorithms and learned a great deal about something probably not that important. Turns out though, this is not such a trivial problem, and there’s a huge wealth of literature on the topic.
I figured it would be easy, I’d just search around for an algorithm to do this, implement it and move on. Recently, while working on my engine, I decided I should pack all my rasterized font bitmaps into one big texture rather than uploading all these individual characters bitmaps to the GPU. Exploring rectangle packing algorithms Posted | Share:
0 kommentar(er)
