nothings/stb — pull request #31 by rcgordon (2014-08-10 05:47:29+00:00)
Title: Make stbtt_BakeFontBitmap() do a better job at packing.

This is now using the "Skyline Bottom-Left" algorithm, as described here:

http://clb.demon.fi/files/RectangleBinPack.pdf

Caveats:
- This is pretty fast, but I'm sure it's not as fast as the previous code.
- It adds about 150 lines of code to the header.
- This needs to malloc a linked list to do its work, and I had to change the function to accept a "userdata" argument for that.
- This is the same algorithm that freetype-gl uses. I wrote this from scratch, but I did look at the (public domain) code that comes with that PDF and not freetype-gl when writing it, so there shouldn't be any licensing concerns.
- This doesn't attempt to rotate glyphs to see if they'll pack better on their sides. There might be wins there, but it adds complexity and the calling program would need to be ready to deal with that. I added a TODO comment if someone wants to play with it.
- This doesn't maintain a wastemap to try to fill in gaps in places the algorithm has otherwise decided are full, as the original paper and reference source does. That added more complexity and more allocations for what appears to be minimal gain (see the waste bitmaps below).

Here's what baking with the original might look like:

![orig](https://cloud.githubusercontent.com/assets/673562/3868581/3a0efdaa-204f-11e4-94c4-d2c11fce8c7a.png)

Here's the output from the same program with the new packing code:

![skyline](https://cloud.githubusercontent.com/assets/673562/3868582/4cf837d8-204f-11e4-8bcc-e15a495736c7.png)

Here's the original with the glyph bounding boxes filled in, to show wasted space:

![waste-original](https://cloud.githubusercontent.com/assets/673562/3868599/4d4b3594-2051-11e4-85d4-f02405e5c0d9.png)

Here's the same for the new approach:

![waste-skyline](https://cloud.githubusercontent.com/assets/673562/3868601/590d8d5a-2051-11e4-8b73-6a7e0e502780.png)

--ryan.