Search code examples
c++bitmaptexturespackingbin-packing

Packing bitmaps

I am trying to pack font glyph images into a single texture. The bitmaps are 1 byte per pixel monochromatic and I wish to pack them all together onto 1 texture. I am able to calculate the minimum texture size required but I am unable to manage an algorithm to packing them all together.

I currently have the bitmaps stored as char pointers and I am able to get the dimensions of each.

Solution

  • I'm not an expert in bin packing, but here's a simple algorithm you may try.

    1. Order glyphs from tallest to shortest. The tallest glyphs will be placed first.
    2. Let H be the height of the next tallest unplaced glyph.
    3. Expand your texture vertically by adding a level of height H.
    4. Fill the level with the remaining glyphs (tallest to shortest) until there is no room left for the next glyph.
    5. Goto #2

    This is known as Next-Fit Decreasing Height (NFDH) algorithm. An interactive demo can be seen here.

    Since your glyphs are more or less the same height, I think this simple algorithm should give you good results.

    Check out this survey for more algorithms.