From 887d2514f9c7e57898cec5d598cd2a3bcd9ce757 Mon Sep 17 00:00:00 2001 From: Mikko Rasa 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=0 && (unsigned)origin_xw && origin_y>=0 && (unsigned)origin_yh) + origin_pixel = image->data[origin_x+origin_y*image->w]; + + x = origin_x-1; + y = origin_y-1; + for(i=1; (i=0 && (unsigned)xw && y>=0 && (unsigned)yh) + pixel = image->data[x+y*image->w]; + + if((pixel^origin_pixel)&0x80) + { + unsigned d = 2*i*i + k*k - 2*k*i; + if(dwidth || !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; x0; --x) - propagate_distance(distance_map+x+y*map_w, -1); - } - - for(x=0; x0; --y) - propagate_distance(distance_map+x+y*map_w, -map_w); - } - - offset = scale/2*(map_w+1); for(y=0; yh; ++y) for(x=0; xw; ++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=0 && (unsigned)bydata[x+y*image->w] = pixel; } - free(distance_map); free(base_image.data); return 0; -- 2.45.2