Sign in to follow this  
Headkaze

Algorithm to pack glyphs into a texture

Recommended Posts

Currently I'm writing font glyphs to a texture who's size is calculated using an algorithm that takes the maximum glyph size. I've noticed that there are many cases where a texture is created that is larger than necessary. Here is the algorithm I am using (thanks to another member on here)
private float RoundUp(float x, float multiple)
{
	return x + multiple - x % multiple;
}

private int CalculateTextureSize(int characterCount, int maxCharWidth, int maxCharHeight)
{
	int area = maxCharWidth * maxCharHeight * characterCount;
	float length = (float) Math.Sqrt(area);
	length = RoundUp(length, (maxCharWidth > maxCharHeight ? maxCharWidth : maxCharHeight));
	int pow = (int)(Math.Log(length) / Math.Log(2.0f)) + 1; // log base 2 of length, plus 1

	return (1 << pow);
}
While it works there are some situations where I'd like to pack the glyphs (or any graphic for that matter) into a texture for a more optimized use of texture space. So I'd like to sort and pack the glyphs according to size. Kind of like how the AngleCode's Bitmap Font Generator creates textures from a font. It's necessary that the algorithm can calculate the smallest power of two texture size required as well as pack them into the texture size. Any ideas on how to go about this?

Share this post


Link to post
Share on other sites
My packer starts with the largest reasonable texture size, and then tries halving either the width or height until the rectangles can't be packed into anything smaller. There could be some cases where you would get better packing with different aspect ratios, but this works well for me.

Share this post


Link to post
Share on other sites
Hmm perhaps your right, maybe the only way to do this is to keep trying texture sizes until it fits. Would this be the general consensus on how to approach getting the optimal size of the texture?

Also I'm curious about methods to do the actual glyph packing. Say I have an array of "Size" structures which have been sorted from largest to smallest. Judging by the AngleCode generated texture this is actually sorted by height only. So say I have an array of Size sorted from largest to smallest in height how is each glyph packed against the one above it? I can't see a simple way to do this apart from looping through every glyph while drawing each one to see where it will fit below them all. It's like a game of Tetris, isn't it?

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