In a previous post, I covered the guts of the dropdown console I wrote for my very simple FPS. However, I didn’t mention any techniques on how to actually render the console. When I was first implementing this, it didn’t seem too bad - just throw up a quad with some text on it, right?
In actuality, text rendering turns out to be a fairly non-trivial task. My first attempt loaded each character as a single texture, and drew one quad/character at a time. However, I quickly ran into performance problems with this - even with just a few hundred characters on screen, there was noticeable lag.
The solution to my problem was to pack all of the characters into one texture, and then batch the draw calls together by line. This reduced hundreds of draw calls to just ten or twenty. In this post, I’ll cover the algorithm I implemented to pack multiple textures into one.
Most of the algorithm is explained on this webpage. However, if you take a look at the algorithm as presented, you’ll see that the texture size is static; if the user wants to pack more textures but their texture atlas is full, they need to generate a new one.
Since different typefaces have different sizes for different glyphs, it’s difficult to predict how large of a texture atlas we need in advance. We could just re-pack the texture every time it becomes full, but I came up with a solution that makes this unnecessary. I’ll first cover the original algorithm (or, rather, something very close to it) for completeness, then present my modification.
Given a bitmap texture and the width/height of that texture, we want to find a space in the texture atlas where we can place that texture. We’re going to use a tree-based, recursive method which repeatedly subdivides a square.
The root node of the tree represents the entire space of the texture. The left and right nodes of each node in the tree represent two portions of the current node. We start with a single leaf node, the root node, which just represents a big empty texture atlas. After inserting the first glyph, we get this:
The tree now has nodes for each of the subdivisions. The root node is subdivided into two zones (nodes), 1 and 2. In turn, zone 1 is subdivided into a node holding the glyph “Q” and an empty node, 3.
After we insert another glyph, the tree and image look like this:
Zone 2 has now been subdivided in the same way; first vertically, then horizontally, whereupon we create a space just large enough to hold the new glyph “A”.
In the original algorithm, we’d continually do this until we run out of space, and then create a new texture. Here’s where my change comes in. Instead of having the root node use the real size of the texture, we’ll keep track of that separately using a variable textureSize. The root node instead has a size of INT_MAX. That means when we split the root node, new nodes along the texture atlas boundaries will have a very large size.
However, that means when we determine whether a texture fits within a node or not, we need to calculate of the “real size” of any node along the boundaries. We can do that using the following steps:
- Check if
origin.x + size.xis equal toINT_MAX. If not, just usesize.xas normal. - Otherwise, we know that the node is against the border. Calculate its real x dimension by taking
textureSize.x - origin.x. - Do the same for
y.
With this change, we’ll still run out of space, but when we do we can simply change textureSize and retry. The algorithm will then dynamically recalculate the “real size” of nodes along the border without having to repack nodes again.
Let’s get into some implementation details. Here’s the definition for the nodes in the tree. Note that I’m using glm for vector operations, but feel free to use any math library.
struct TextureNode
{
glm::ivec2 origin; // Top left of the rectangle this node represents
glm::ivec2 size; // Size of the rectangle this node represents
bool empty; // true if this node is a leaf and is filled
std::unique_ptr<TextureNode> left; // Left (or top) subdivision
std::unique_ptr<TextureNode> right; // Right (or bottom) subdivision
};
Using this struct, we can write the algorithm to find a space within the tree for a new texture:
TexturePacker::TextureNode* TexturePacker::pack(TextureNode* node, const glm::ivec2& size)
{
if (!node->empty) {
// The node is filled, not gonna fit anything else here
assert(!node->left && !node->right);
return NULL;
} else if (node->left && node->right) {
// Non-leaf, try inserting to the left and then to the right
TextureNode* retval = pack(node->left.get(), size);
if (retval != NULL) {
return retval;
}
return pack(node->right.get(), size);
} else {
// This is an unfilled leaf - let's see if we can fill it
glm::ivec2 realSize(node->size.x, node->size.y);
// If we're along a boundary, calculate the actual size
if (node->origin.x + node->size.x == INT_MAX) {
realSize.x = textureSize.x - node->origin.x;
}
if (node->origin.y + node->size.y == INT_MAX) {
realSize.y = textureSize.y - node->origin.y;
}
if (node->size.x == size.x && node->size.y == size.y) {
// Perfect size - just pack into this node
node->empty = false;
return node;
} else if (realSize.x < size.x || realSize.y < size.y) {
// Not big enough
return NULL;
} else {
// Large enough - split until we get a perfect fit
TextureNode* left,
TextureNode* right;
// Determine how much space we'll have left if we split each way
int remainX = realSize.x - size.x;
int remainY = realSize.y - size.y;
// Split the way that will leave the most room
bool verticalSplit = remainX < remainY;
if (remainX == 0 && remainY == 0) {
// Edge case - we are are going to hit the border of
// the texture atlas perfectly, split at the border instead
if (node->size.x > node->size.y) {
verticalSplit = false;
} else {
verticalSplit = true;
}
}
if (verticalSplit) {
// Split vertically (left is top)
left = new TextureNode(node->origin, glm::ivec2(node->size.x, size.y);
right = new TextureNode(glm::ivec2(node->origin.x, node->origin.y + size.y),
glm::ivec2(node->size.x, node->size.y - size.y));
} else {
// Split horizontally
left = new TextureNode(node->origin, glm::ivec2(size.x, node->size.y);
right = new TextureNode(glm::ivec2(node->origin.x + size.x, node->origin.y), glm::ivec2(node->size.x - size.x, node->size.y));
}
node->left = std::unique_ptr<TextureNode>(left);
node->right = std::unique_ptr<TextureNode>(right);
return pack(node->left.get(), size);
}
}
}
When we split a node, we always pack toward the left node; that’s because the left and top is where we begin.
Any time we find a place to eut the new texture, we return the node and bubble it up through the recursive calls. If no node is large enough to fit the new texture, then NULL is returned.
There’s still a couple of things to take care of; resizing the buffer when it gets full, and constructing the actual texture. We take care of those in the actual method which is exposed to callers:
glm::ivec2 TexturePacker::packTexture(unsigned char* textureBuffer,
const glm::ivec2& bufferSize)
{
TextureNode* node = pack(rootNode.get(), bufferSize);
if (node == NULL) {
this->resizeBuffer(glm::ivec2(textureSize.x*2, textureSize.y*2));
node = pack(rootNode.get(), bufferSize);
// Note: this assert will be hit if we try to pack a texture larger
// than the current size of the texture
assert(node != NULL);
}
assert(bufferSize.x == node->size.x);
assert(bufferSize.y == node->size.y);
// Copy the texture to the texture atlas' buffer
for (int ly = 0; ly < bufferSize.y; ly++) {
for (int lx = 0; lx < bufferSize.x; lx++) {
int y = node->origin.y + ly;
int x = node->origin.x + lx;
this->buffer[y * textureSize.x + x] = textureBuffer[ly * bufferSize.x + lx];
}
}
return node->origin;
}
void TexturePacker::resizeBuffer(const glm::ivec2& newSize)
{
std::vector<unsigned char> newBuffer;
newBuffer.resize(newSize.y*newSize.x);
for (int y = 0; y < textureSize.y; y++) {
for (int x = 0; x < textureSize.x; x++) {
newBuffer[y * newSize.x + x] = buffer[y * textureSize.x + x];
}
}
textureSize = newSize;
buffer = std::move(newBuffer);
}
I’ve delegated the responsibility of saving the position and size of the packed glyphs to the caller.
To actually draw the text, there are still a few details left - for example, alignment of each character with respect to each other and to the baseline. For those, I’ll refer you to this excellent tutorial, which covers all the aspects besides texture packing. Simply pack the Freetype glyphs and use the packed texture when rendering.