+ unsigned short *neighbor = pixel+offset;
+ if((*neighbor^*pixel)&0x8000)
+ *neighbor = (*neighbor&0x8000)+1;
+ else if((*neighbor&0x7FFF)>(*pixel&0x7FFF))
+ *neighbor = *pixel+2;
+}
+
+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)
+ {
+ image->w = 0;
+ image->h = 0;
+ image->data = NULL;
+ return 0;
+ }
+
+ 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->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;
+ }
+
+ free(distance_map);
+ free(base_image.data);
+
+ return 0;
+}
+
+int render_grid(Font *font, unsigned cellw, unsigned cellh, unsigned cpl, bool seq, bool npot)
+{
+ unsigned i;
+ int top = 0, bot = 0;
+ unsigned first, last;
+ unsigned maxw = 0, maxh = 0;
+
+ /* Find extremes of the glyph images. */
+ for(i=0; i<font->n_glyphs; ++i)
+ {
+ int y;
+
+ y = font->glyphs[i].offset_y+font->glyphs[i].image.h;
+ if(y>top)
+ top = y;
+ if(font->glyphs[i].offset_y<bot)
+ bot = font->glyphs[i].offset_y;
+ if(font->glyphs[i].image.w>maxw)
+ maxw = font->glyphs[i].image.w;
+ if(font->glyphs[i].image.h>maxh)
+ maxh = font->glyphs[i].image.h;
+ }
+
+ if(cellw==0)
+ {
+ /* Establish a large enough cell to hold all glyphs in the range. */
+ int square = (cellh==cellw);
+ cellw = maxw;
+ cellh = top-bot;
+ if(square)
+ {
+ if(cellh>cellw)
+ cellw = cellh;
+ else
+ cellh = cellw;
+ }
+ }
+
+ if(verbose>=1)
+ {
+ printf("Max size: %u x %u\n", maxw, maxh);
+ printf("Y range: [%d %d]\n", bot, top);
+ printf("Cell size: %u x %u\n", cellw, cellh);
+ if(maxw>cellw || (unsigned)(top-bot)>cellh)
+ fprintf(stderr, "Warning: character size exceeds cell size\n");
+ }
+
+ if(cpl==0)
+ {
+ /* Determine number of characters per line, trying to fit all the glyphs
+ in a square image. */
+ for(i=1;; i<<=1)
+ {
+ cpl = i/cellw;
+ if(cpl>0 && font->n_glyphs/cpl*cellh<=cpl*cellw)
+ break;
+ }
+ }
+
+ first = font->glyphs[0].code;
+ if(!seq)
+ first -= first%cpl;
+ last = font->glyphs[font->n_glyphs-1].code;
+
+ font->image.w = cpl*cellw;
+ if(!npot)
+ font->image.w = round_to_pot(font->image.w);
+ if(seq)
+ font->image.h = (font->n_glyphs+cpl-1)/cpl*cellh;
+ else
+ font->image.h = (last-first+cpl)/cpl*cellh;
+ if(!npot)
+ font->image.h = round_to_pot(font->image.h);
+
+ font->image.data = (unsigned char *)alloc_image_data(font->image.w, font->image.h);
+ if(!font->image.data)
+ return -1;
+ memset(font->image.data, 255, font->image.w*font->image.h);
+
+ for(i=0; i<font->n_glyphs; ++i)
+ {
+ Glyph *glyph;
+ unsigned ci, cx, cy;
+ unsigned x, y;
+
+ glyph = &font->glyphs[i];
+
+ if(seq)
+ ci = i;
+ else
+ ci = glyph->code-first;
+
+ cx = (ci%cpl)*cellw;
+ cy = (ci/cpl)*cellh;
+
+ if(cellw>glyph->image.w)
+ cx += (cellw-glyph->image.w)/2;
+ cy += top-glyph->offset_y-glyph->image.h;
+
+ glyph->x = cx;
+ glyph->y = cy;
+
+ for(y=0; y<glyph->image.h; ++y) for(x=0; x<glyph->image.w; ++x)
+ {
+ if(cx+x>=font->image.w || cy+y>=font->image.h)
+ continue;
+ font->image.data[cx+x+(cy+y)*font->image.w] = 255-glyph->image.data[x+y*glyph->image.w];
+ }
+ }
+
+ return 0;
+}
+
+int render_packed(Font *font, unsigned margin, unsigned padding, bool npot)
+{
+ unsigned i;
+ size_t area = 0;
+ char *used_glyphs;
+ unsigned *used_pixels;
+ unsigned cx = margin, cy;
+ unsigned used_h = 0;
+
+ /* Compute the total area occupied by glyphs and padding. */
+ for(i=0; i<font->n_glyphs; ++i)
+ {
+ size_t a = area+(font->glyphs[i].image.w+padding)*(font->glyphs[i].image.h+padding);
+ if(a<area)
+ {
+ fprintf(stderr, "Overflow in counting total glyph area\n");
+ return -1;
+ }
+ area = a;
+ }
+
+ /* Find an image size that's no higher than wide, allowing for some
+ imperfections in the packing. */
+ for(font->image.w=1;; font->image.w<<=1)
+ {
+ if(font->image.w<=margin*2)
+ continue;
+ font->image.h = (area*5/4)/(font->image.w-margin*2)+margin*2;
+ if(font->image.h<=font->image.w)
+ break;
+ }
+ if(!npot)
+ font->image.h = round_to_pot(font->image.h);
+
+ /* Allocate arrays for storing the image and keeping track of used pixels and
+ glyphs. Since glyphs are rectangular and the image is filled starting from
+ the top, it's enough to track the number of used pixels at the top of each
+ column. */
+ font->image.data = (unsigned char *)alloc_image_data(font->image.w, font->image.h);
+ if(!font->image.data)
+ return -1;
+ memset(font->image.data, 255, font->image.w*font->image.h);
+ used_pixels = (unsigned *)malloc(font->image.w*sizeof(unsigned));
+ memset(used_pixels, 0, font->image.w*sizeof(unsigned));
+ used_glyphs = (char *)malloc(font->n_glyphs);
+ memset(used_glyphs, 0, font->n_glyphs);
+
+ for(cy=margin; cy+margin<font->image.h;)
+ {
+ unsigned w;
+ unsigned x, y;
+ Glyph *glyph = NULL;
+ unsigned best_score = 0;
+ unsigned target_h = 0;
+
+ /* Find the leftmost free pixel on this row. Also record the lowest
+ extent of glyphs to the left of the free position. */
+ for(; (cx+margin<font->image.w && used_pixels[cx]>cy); ++cx)
+ if(used_pixels[cx]-cy-padding>target_h)
+ target_h = used_pixels[cx]-cy-padding;
+
+ if(cx+margin>=font->image.w)
+ {
+ cx = margin;
+ ++cy;
+ continue;
+ }
+
+ /* Count the free pixel at this position. */
+ for(w=0; (cx+w+margin<font->image.w && used_pixels[cx+w]<=cy); ++w) ;
+
+ /* Find a suitable glyph to put here. */
+ for(i=0; i<font->n_glyphs; ++i)
+ {
+ Glyph *g;
+
+ g = &font->glyphs[i];
+ if(!used_glyphs[i] && g->image.w<=w)
+ {
+ unsigned score;
+
+ /* Prefer glyphs that would reach exactly as low as the ones left
+ of here. This aims to create a straight edge at the bottom for
+ lining up further glyphs. */
+ score = g->image.h+padding;
+ if(g->image.h==target_h)
+ score *= g->image.w;
+ else
+ score += g->image.w;
+
+ if(score>best_score)
+ {
+ glyph = g;
+ best_score = score;
+ }
+ }
+ }
+
+ if(!glyph)
+ {
+ cx += w;
+ continue;
+ }
+
+ used_glyphs[glyph-font->glyphs] = 1;
+ glyph->x = cx;
+ glyph->y = cy;
+
+ for(y=0; y<glyph->image.h; ++y) for(x=0; x<glyph->image.w; ++x)
+ {
+ if(cx+x>=font->image.w || cy+y>=font->image.h)
+ continue;
+ font->image.data[cx+x+(cy+y)*font->image.w] = 255-glyph->image.data[x+y*glyph->image.w];
+ }
+ for(x=0; x<glyph->image.w+2*padding; ++x)
+ {
+ if(cx+x<padding || cx+x>=font->image.w+padding)
+ continue;
+ if(used_pixels[cx+x-padding]<cy+glyph->image.h+padding)
+ used_pixels[cx+x-padding] = cy+glyph->image.h+padding;
+ }
+
+ if(cy+glyph->image.h+margin>used_h)
+ used_h = cy+glyph->image.h+margin;
+ }
+
+ /* Trim the image to the actually used size, in case the original estimate
+ was too pessimistic. */
+ font->image.h = used_h;
+ if(!npot)
+ font->image.h = round_to_pot(font->image.h);
+
+ free(used_glyphs);
+ free(used_pixels);
+
+ return 0;