Sign in to follow this  
scarypajamas

Need algorithm for purging glyphs from an atlas.

Recommended Posts

I've implemented a font atlas using the guillotine method described here; its the same idea as this lightmap packing algorithm.  My implementation allows for using multiple font atlases at the same time.

I'm in need of an algorithm for determining which glyphs (and how many) to purge when all atlases reach capacity.

My current solution waits until a new glyph cannot be inserted (because all atlas have become full), then it finds the atlas with the oldest glyphs (on average), and then purges the oldest glyphs in batches until the new glyph can be inserted.  The batch size is computed as 10% of the total number of glyphs occupying the atlas before purging begins.  The age of a glyph is determined by its last accessed time and not by its insertion time.

Any recommendations, algorithms, and suggestions would be much appreciated.

Edited by scarypajamas

Share this post


Link to post
Share on other sites

What you described is a typical LRU (Least Recently Used) scheme, and it works pretty well. Make a public GC function that does the clean up so that you can explicitly run it at known points (e.g. scene/level transitions), and have it automaticaly call GC when failing to allocate space in an atlas and then allocate from the freed space. If GC fails during an allocation (e.g. the least recently used element was used this frame) then allocate a new atlas.

Share this post


Link to post
Share on other sites

Thank you both for your help.  I'm glad to hear I'm on the right track.

How "smart" do you think the deletion phase should be?

If a very large glyph is inserted that triggers a GC cycle, then I have a few options:

  • Delete the oldest glyphs one at a time until the new glyph fits.
  • Delete the oldest glyphs in batches until the new glyph fits (my current solution).
  • Try to find a "reasonably old glyph" that, if removed, would make room for the new glyph.
  • Try to find a batch of "reasonably old glyphs" adjacent to each that, if removed, would make room for the new glyph.

Thoughts or suggestions?  I'm currently deleting in batch sizes of 10% of the initial glyph count as a crude heuristic.
 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this