From 887d2514f9c7e57898cec5d598cd2a3bcd9ce757 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Fri, 4 May 2018 20:47:41 +0300
Subject: [PATCH] Use euclidean distance instead of manhattan distance

This turned out to be surprisingly efficient and compact once I put some
thought into it.
---
 ttf2png.c | 119 +++++++++++++++++++++++++++---------------------------
 1 file changed, 60 insertions(+), 59 deletions(-)

diff --git a/ttf2png.c b/ttf2png.c
index 13e5a80..5e6e351 100644
--- a/ttf2png.c
+++ b/ttf2png.c
@@ -81,7 +81,8 @@ void *alloc_image_data(size_t, size_t);
 int init_font(Font *, FT_Face, const Range *, unsigned, bool, unsigned);
 int init_glyphs(Font *, FT_Face, const Range *, bool, unsigned);
 int copy_bitmap(const FT_Bitmap *, Image *);
-void propagate_distance(unsigned short *, int);
+unsigned sqrti(unsigned);
+unsigned find_distance_to_edge(const Image *, int, int, unsigned);
 int create_distance_field(const FT_Bitmap *, Image *, unsigned, unsigned);
 int render_grid(Font *, unsigned, unsigned, unsigned, bool, bool);
 int render_packed(Font *, unsigned, unsigned, bool);
@@ -691,23 +692,61 @@ int copy_bitmap(const FT_Bitmap *bmp, Image *image)
 	return 0;
 }
 
-void propagate_distance(unsigned short *pixel, int offset)
+unsigned sqrti(unsigned num)
 {
-	unsigned short *neighbor = pixel+offset;
-	if((*neighbor^*pixel)&0x8000)
-		*neighbor = (*neighbor&0x8000)+1;
-	else if((*neighbor&0x7FFF)>(*pixel&0x7FFF))
-		*neighbor = *pixel+2;
+	unsigned result = num;
+	while(result*result>num)
+	{
+		unsigned diff = result*result-num;
+		if(diff<result)
+			break;
+
+		result -= (diff+result)/(result*2);
+	}
+
+	return result;
+}
+
+unsigned find_distance_to_edge(const Image *image, int origin_x, int origin_y, unsigned range)
+{
+	unsigned i, j;
+	int x, y;
+	unsigned char origin_pixel = 0;
+	unsigned closest = range*range;
+
+	if(origin_x>=0 && (unsigned)origin_x<image->w && origin_y>=0 && (unsigned)origin_y<image->h)
+		origin_pixel = image->data[origin_x+origin_y*image->w];
+
+	x = origin_x-1;
+	y = origin_y-1;
+	for(i=1; (i<range && i*i<=closest); ++i, --x, --y) for(j=0; j<4; ++j)
+	{
+		unsigned k;
+		int dx = (j==0 ? 1 : j==2 ? -1 : 0);
+		int dy = (j==1 ? 1 : j==3 ? -1 : 0);
+
+		for(k=0; k<i*2; ++k, x+=dx, y+=dy)
+		{
+			unsigned char pixel = 0;
+			if(x>=0 && (unsigned)x<image->w && y>=0 && (unsigned)y<image->h)
+				pixel = image->data[x+y*image->w];
+				
+			if((pixel^origin_pixel)&0x80)
+			{
+				unsigned d = 2*i*i + k*k - 2*k*i;
+				if(d<closest)
+					closest = d;
+			}
+		}
+	}
+
+	return sqrti(closest)*0x7F/range;
 }
 
 int create_distance_field(const FT_Bitmap *bmp, Image *image, unsigned scale, unsigned margin)
 {
 	unsigned x, y;
 	Image base_image;
-	unsigned short *distance_map;
-	unsigned map_w;
-	unsigned map_h;
-	unsigned offset;
 
 	if(!bmp->width || !bmp->rows)
 	{
@@ -720,66 +759,28 @@ int create_distance_field(const FT_Bitmap *bmp, Image *image, unsigned scale, un
 	if(copy_bitmap(bmp, &base_image))
 		return -1;
 
-	map_w = base_image.w+2*margin*scale+scale-1;
-	map_w -= map_w%scale;
-	map_h = base_image.h+2*margin*scale+scale-1;
-	map_h -= map_h%scale;
-	distance_map = (unsigned short *)malloc(map_w*map_h*sizeof(unsigned short));
-	if(!distance_map)
-	{
-		fprintf(stderr, "Cannot allocate %d bytes of memory for distance map\n", map_w*map_h);
-		free(base_image.data);
-		return -1;
-	}
-
-	image->w = map_w/scale;
-	image->h = map_h/scale;
+	image->w = (base_image.w-1)/scale+2*margin+1;
+	image->h = (base_image.h-1)/scale+2*margin+1;
 	image->data = (unsigned char *)malloc(image->w*image->h);
 	if(!image->data)
 	{
 		fprintf(stderr, "Cannot allocate %d bytes of memory for glyph\n", image->w*image->h);
 		free(base_image.data);
-		free(distance_map);
 		return -1;
 	}
 
-	for(x=0; x<map_w*map_h; ++x)
-		distance_map[x] = 0x7FFF;
-
-	offset = margin*scale*(map_w+1);
-	for(y=0; y<base_image.h; ++y) for(x=0; x<base_image.w; ++x)
-		distance_map[offset+x+y*map_w] |= (base_image.data[x+y*base_image.w]&0x80)<<8;
-
-	for(y=0; y<map_h; ++y)
-	{
-		for(x=0; x+1<map_w; ++x)
-			propagate_distance(distance_map+x+y*map_w, 1);
-		for(x=map_w-1; x>0; --x)
-			propagate_distance(distance_map+x+y*map_w, -1);
-	}
-
-	for(x=0; x<map_w; ++x)
-	{
-		for(y=0; y+1<map_h; ++y)
-			propagate_distance(distance_map+x+y*map_w, map_w);
-		for(y=map_h-1; y>0; --y)
-			propagate_distance(distance_map+x+y*map_w, -map_w);
-	}
-
-	offset = scale/2*(map_w+1);
 	for(y=0; y<image->h; ++y) for(x=0; x<image->w; ++x)
 	{
-		unsigned short pixel = distance_map[offset+(x+y*map_w)*scale];
-		unsigned short dist = (pixel&0x7FFF)*0x7F/(margin*scale*2+1);
-		if(dist>0x7F)
-			dist = 0x7F;
-		if(pixel&0x8000)
-			image->data[x+y*image->w] = 0x80+dist;
-		else
-			image->data[x+y*image->w] = 0x7F-dist;
+		int bx = (x-margin)*scale+scale/2;
+		int by = (y-margin)*scale+scale/2;
+		unsigned char pixel = find_distance_to_edge(&base_image, bx, by, margin*scale);
+		if(bx>=0 && (unsigned)bx<base_image.w && by>=0 && (unsigned)by<base_image.h)
+			pixel |= base_image.data[bx+by*base_image.w]&0x80;
+		if(!(pixel&0x80))
+			pixel = 0x80-pixel;
+		image->data[x+y*image->w] = pixel;
 	}
 
-	free(distance_map);
 	free(base_image.data);
 
 	return 0;
-- 
2.43.0