From 096d2b648330013d13d42cf3efe414f7860d6e77 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Fri, 23 Nov 2012 11:45:31 +0200
Subject: [PATCH] Improve the packing algorithm

---
 ttf2png.c | 20 +++++++++++++++-----
 1 file changed, 15 insertions(+), 5 deletions(-)

diff --git a/ttf2png.c b/ttf2png.c
index c77cd58..ebc9530 100644
--- a/ttf2png.c
+++ b/ttf2png.c
@@ -465,13 +465,13 @@ void render_packed(Font *font)
 {
 	unsigned i;
 	unsigned area = 0;
-	unsigned last_h = 0xFFFF;
 	char     *used_glyphs;
 	char     *used_pixels;
 	unsigned cx = 0, cy;
+	unsigned used_h = 0;
 
 	for(i=0; i<font->n_glyphs; ++i)
-		area+=(font->glyphs[i].image.w+1)*(font->glyphs[i].image.h+1);
+		area += (font->glyphs[i].image.w+1)*(font->glyphs[i].image.h+1);
 
 	for(font->image.w=1;; font->image.w<<=1)
 	{
@@ -494,17 +494,24 @@ void render_packed(Font *font)
 		unsigned x, y;
 		Glyph    *glyph = NULL;
 		unsigned best_score = 0;
+		unsigned target_h = 0;
 
 		for(; (cx<font->image.w && used_pixels[cx+cy*font->image.w]); ++cx) ;
 		if(cx>=font->image.w)
 		{
 			cx = 0;
 			++cy;
-			last_h = 0xFFFF;
 			continue;
 		}
 		for(w=0; (cx+w<font->image.w && !used_pixels[cx+w+cy*font->image.w]); ++w) ;
 
+		for(x=0; x<cx; ++x)
+		{
+			for(y=0; (cy+y+1<font->image.h && used_pixels[cx-x+(cy+y+1)*font->image.w]); ++y) ;
+			if(y>target_h)
+				target_h = y;
+		}
+
 		for(i=0; i<font->n_glyphs; ++i)
 		{
 			Glyph *g;
@@ -515,7 +522,7 @@ void render_packed(Font *font)
 				unsigned score;
 
 				score = g->image.h+1;
-				if(g->image.h==last_h)
+				if(g->image.h==target_h)
 					score *= g->image.w;
 				else
 					score += g->image.w;
@@ -551,8 +558,11 @@ void render_packed(Font *font)
 			used_pixels[cx+x-1+(cy+y-1)*font->image.w] = 1;
 		}
 
-		last_h = glyph->image.h;
+		if(cy+glyph->image.h>used_h)
+			used_h = cy+glyph->image.h;
 	}
+
+	font->image.h = round_to_pot(used_h);
 }
 
 int save_defs(const char *fn, const Font *font)
-- 
2.45.2