Initial import.

diff --git a/Makefile b/Makefile
new file mode 100644 (file)
index 0000000..394cd0e
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,15 @@
+WARNINGS = -Wall -Werror -Wextra -Wfloat-equal -Wcast-qual -Wcast-align \
+          -Wconversion
+
+CXXFLAGS = $(WARNINGS) `pkg-config --cflags freetype2` -std=c++11 -Os
+LDFLAGS = `pkg-config --libs freetype2`
+
+all: ttf-to-distfield
+
+ttf-to-distfield: ttf-to-distfield.cpp
+
+clean:
+       rm -f ttf-to-distfield
+
+distclean: clean
+       rm *~

diff --git a/README.md b/README.md
new file mode 100644 (file)
index 0000000..e529253
--- /dev/null
+++ b/README.md
@@ -0,0 +1,73 @@
+# ttf-to-distfield
+## Render a distance field from a TrueType font
+
+This tool generates an atlas (spritesheet) of a distance field from
+codepoints rendered in a 2D font, along with a JSON file describing
+the contents of the atlas.
+
+### Compiling
+
+Compiling `ttf-to-distfield` requires [FreeType], Make, and a C++
+compiler with minimal C++11 support. Basically, it should work on most
+desktop OSs.
+
+    $ make
+
+### Usage
+
+    $ ./ttf-to-distfield my-font.ttf
+ 
+This will take a couple seconds and maybe print some warnings for
+characters it can't find. When it's done it will generate two files in
+the working directory, the atlas itself `my-font.tga` and the font
+positioning data as a JSON blob `my-font.font.json`.
+
+For advanced usage,
+
+    $ ./ttf-to-distfield my-font.ttf size codepoints
+
+`size` is specified in pixels and can be tuned to adjust the output
+texture size. Good values for display quality are 32 to 64.
+
+The codepoints can be specified as a comma-separated list or as
+hyphen-separated range, e.g. `32,48-57,65-90` for only uppercase
+alphanumerics. Hexadecimal ranges are also supported, e.g. `0x20-0x7E`
+for the printable ASCII set.
+
+The JSON file contains the TrueType positioning information for each
+character along with the texture coordinates of it within the TGA
+file. It also contains the pixel height, distance field scale radius,
+and inter-character distances. Note that the padding is included in
+the width/height of the characters. This is probably what you want,
+but it means you need to start from `x = -padding` and `y = padding`
+rather than 0 when drawing a string.
+
+### Why?
+
+There are methods of rendering text that can take advantage of the
+information encoded in the distance field to perform high-quality
+rendering,
+
+For a common example, see Chris Green's paper [_Improved Alpha-Tested
+Magnification for Vector Textures and Special Effects_][1] from
+SIGGRAPH 2007.
+
+There are some tools that did this already, but they all had heavy
+dependencies (e.g. Windows) and/or required GUIs and/or output weird
+formats.
+
+### Known Issues
+
+This tool punts on all the hard stuff in Unicode. It's just a dump of
+the data from FreeType out to JSON. You still need to handle all the
+nasty details of composition yourself.
+
+TGA is probably not the most useful format. But even if it did output
+PNG you'd probably want to run it through a crusher later in your
+pipeline anyway.
+
+The packing algorithm isn't smart but it's simple and easy to read the
+result.
+
+ [FreeType]: http://freetype.org/
+ [1]: http://www.valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf

diff --git a/ttf-to-distfield.cpp b/ttf-to-distfield.cpp
new file mode 100644 (file)
index 0000000..c75053c
--- /dev/null
+++ b/ttf-to-distfield.cpp
@@ -0,0 +1,358 @@
+#include <ft2build.h>
+#include FT_FREETYPE_H
+#include FT_GLYPH_H
+
+#include <err.h>
+#include <stdint.h>
+
+#include <algorithm>
+#include <cmath>
+#include <cstdlib>
+#include <string>
+#include <utility>
+#include <vector>
+
+const auto SCALE = 16u;
+const auto PADDING = 4u;
+const auto SCALED_PADDING = SCALE * PADDING;
+
+struct Bitmap {
+    unsigned width;
+    unsigned height;
+    std::vector<uint8_t> buffer;
+
+    Bitmap(unsigned width, unsigned height)
+        : width(width)
+        , height(height)
+        , buffer(width * height)
+    {}
+
+    Bitmap(const FT_Bitmap &bitmap)
+        : width((unsigned)bitmap.width + 2 * SCALED_PADDING)
+        , height((unsigned)bitmap.rows + 2 * SCALED_PADDING)
+        , buffer(width * height)
+    {
+        for (auto y = 0u; y < (unsigned)bitmap.rows; ++y) {
+            for (auto x = 0u; x < (unsigned)bitmap.width; ++x) {
+                auto c = bitmap.buffer[y * (unsigned)bitmap.pitch + x / 8];
+                auto set = !!(c >> (7 - (x & 7)));
+                (*this)(x + SCALED_PADDING, y + SCALED_PADDING) = set;
+            }
+        }
+    }
+
+    inline uint8_t &operator()(unsigned x, unsigned y) {
+        auto idx = y * width + x;
+        return buffer[idx];
+    }
+
+    inline uint8_t operator()(unsigned x, unsigned y) const {
+        if (x >= width || y >= height)
+            return 0;
+        auto idx = y * width + x;
+        return buffer[idx];
+    }
+
+    void blit(const Bitmap &src, unsigned x, unsigned y) {
+        for (auto dy = 0u; dy < src.height; ++dy)
+            for (auto dx = 0u; dx < src.width; ++dx)
+                (*this)(x + dx, y + dy) = src(dx, dy);
+    }
+
+    uint8_t sdf(unsigned x, unsigned y, unsigned max_r) const {
+        auto dsq = max_r * max_r;
+        auto v = (*this)(x, y);
+
+        for (unsigned r = 1, rsq; r <= max_r && (rsq = r * r) < dsq; ++r) {
+            for (unsigned d = -r; (int)d <= (int)r; ++d) {
+                if ((*this)(x + d, y - r) != v)
+                    dsq = std::min(d * d + rsq, dsq);
+                else if ((*this)(x + d, y + r) != v)
+                    dsq = std::min(d * d + rsq, dsq);
+                else if ((*this)(x - r, y + d) != v)
+                    dsq = std::min(rsq + d * d, dsq);
+                else if ((*this)(x + r, y + d) != v)
+                    dsq = std::min(rsq + d * d, dsq);
+            }
+        }
+
+        // Map distance onto to [0, 255].
+        auto d = std::sqrt((float)dsq);
+        if (v == 0)
+            d = -d;
+        d *= (255.f / 2.f) / max_r;
+        d += (255.f / 2.f);
+        d = std::min(255.f, std::max(0.f, d));
+        return (uint8_t)(d + 0.5);
+    }
+
+    void save(const std::string &filename) const {
+        auto f = fopen(filename.c_str(), "wb");
+        if (!f)
+            err(1, "unable to write image: %s", filename.c_str());
+        const uint8_t header[] = {
+            0, // ID length
+            0, // color map
+            3, // image type = greyscale
+            0, 0, 0, 0, 0, // color map specification
+            0, 0, // X origin
+            0, 0, // Y origin
+            (uint8_t)(width & 0xFF),
+            (uint8_t)((width >> 8) & 0xFF),
+            (uint8_t)(height & 0xFF),
+            (uint8_t)((height >> 8) & 0xFF),
+            8, // bits per pixel
+            1 << 5, // scanlines are from top-left
+        };
+        fwrite(header, sizeof(header[0]), sizeof(header), f);
+        fwrite(&buffer[0], sizeof(buffer[0]), buffer.size(), f);
+        fclose(f);
+    }
+};
+
+struct Glyph {
+    Bitmap pixels;
+    unsigned codepoint;
+    unsigned width;
+    unsigned height;
+    unsigned x;
+    unsigned y;
+    float u0;
+    float v0;
+    float u1;
+    float v1;
+    float advance_x;
+    float advance_y;
+    float left;
+    float top;
+
+    Glyph(unsigned codepoint, const FT_BitmapGlyph &glyph)
+        : pixels(glyph->bitmap.width > 0
+                 ? ((unsigned)glyph->bitmap.width / SCALE + 2 * PADDING)
+                 : 0,
+                 glyph->bitmap.rows > 0
+                 ? ((unsigned)glyph->bitmap.rows / SCALE + 2 * PADDING)
+                 : 0)
+        , codepoint(codepoint)
+        , width(pixels.width)
+        , height(pixels.height)
+        , x(0), y(0)
+        , u0(0), v0(0), u1(0), v1(0)
+        , advance_x((glyph->root.advance.x >> 16) / (float)SCALE)
+        , advance_y((glyph->root.advance.y >> 16) / (float)SCALE)
+        , left(glyph->left / (float)SCALE)
+        , top(glyph->top / (float)SCALE)
+    {
+        const Bitmap bmap(glyph->bitmap);
+
+        for (auto y = 0u; y < height; y++) {
+            for (auto x = 0u; x < width; x++) {
+                // Sample from center of high-res area.
+                auto xs = x * SCALE + SCALE / 2;
+                auto ys = y * SCALE + SCALE / 2;
+                pixels(x, y) = bmap.sdf(xs, ys, 2 * SCALE);
+            }
+        }
+    }
+};
+
+static bool glyph_codepoint_sort(const Glyph &a, const Glyph &b) {
+    return a.codepoint < b.codepoint;
+}
+
+static bool glyph_height_sort(const Glyph &a, const Glyph &b) {
+    // sort high to low, break ties by codepoint for stable output.
+    return a.height > b.height
+        || (a.height == b.height && glyph_codepoint_sort(a, b));
+}
+
+static std::vector<Glyph> get_glyphs(
+    FT_Face face, const std::vector<unsigned> &codepoints)
+{
+    std::vector<Glyph> glyphs;
+    // A number of fonts provide two different glyph indices for
+    // "invalid" vs. "undisplayable" characters. Invalid characters
+    // should be ignored. Undisplayable characters should be ignored
+    // unless the character requested is the special undisplayable
+    // character.
+    const unsigned REPLACEMENT = 0xFFFD;
+    auto invalid = FT_Get_Char_Index(face, 0);
+    auto missing = FT_Get_Char_Index(face, REPLACEMENT);
+    auto warning = false;
+    glyphs.reserve(codepoints.size());
+
+    for (auto i : codepoints) {
+        FT_Glyph glyph;
+        if (FT_Get_Char_Index(face, i) != invalid
+            && (i == REPLACEMENT || FT_Get_Char_Index(face, i) != missing)
+            && !FT_Load_Char(face, i, FT_LOAD_MONOCHROME)
+            && !FT_Get_Glyph(face->glyph, &glyph)
+            && !FT_Glyph_To_Bitmap(&glyph, FT_RENDER_MODE_MONO, 0, 1)
+            && ((FT_BitmapGlyph)glyph)->bitmap.pixel_mode == FT_PIXEL_MODE_MONO
+            )
+        {
+            auto bmp_glyph = (FT_BitmapGlyph)glyph;
+            glyphs.push_back(Glyph(i, bmp_glyph));
+            if (warning)
+                warnx("Resuming generation at codepoint %d.", i);
+            warning = false;
+        } else if (!warning) {
+            warnx("Can't load codepoint %d and onwards.", i);
+            warning = true;
+        }
+    }
+
+    return glyphs;
+}
+
+static unsigned get_texture_size(unsigned &width, unsigned &height, std::vector<Glyph> &glyphs)
+{
+    // Sort glyphs by height to minimize vertically wasted space.
+    std::sort(glyphs.begin(), glyphs.end(), glyph_height_sort);
+
+    // Get an estimated size by assuming all characters are the same
+    // height, and that we can lay them out exactly in a square. This
+    // drastically overestimates the space required unless the
+    // characters are actually all the max height, then it slightly
+    // underestimates it.
+    auto max_height = glyphs.front().height;
+    auto total_width = 0u;
+    for (auto &glyph : glyphs)
+        total_width += glyph.width;
+    auto side = ceil(sqrt(total_width * max_height));
+
+    // Round width up to the nearest power of 2.
+    for (width = 1; width < side; width *= 2);
+
+    // Now, lay glyphs out horizontally in fixed rows, to figure out
+    // how tall it *really* needs to be. While we're at it, figure out
+    // what the optimum space usage would be.
+    //
+    // This is a naive algorithm that leaves "a lot" of space empty,
+    // like 30-50% of the texture. The problem is unless the space is
+    // at least 50%, no amount of smart packing is going to improve it
+    // anyway, and will just make the texture harder to spot-check.
+
+    auto total_height = 0u;
+    auto width_accum = width + 1;
+    auto real_area = 0u;
+    auto row_start = 0u;
+    for (auto &glyph : glyphs) {
+        if (width_accum + glyph.width > width) {
+            width_accum = 0;
+            row_start = total_height;
+            total_height += glyph.height;
+        }
+        glyph.x = width_accum;
+        glyph.y = row_start;
+        width_accum += glyph.width;
+        real_area += glyph.width * glyph.height;
+    }
+
+    // Now round height up to nearest power of 2.
+    for (height = 1; height < total_height; height *= 2);
+
+    // With the height known, texture coordinates can be set.
+    for (auto &glyph : glyphs) {
+        if (glyph.width) {
+            glyph.u0 = (float)(glyph.x) / width;
+            glyph.v0 = (float)(glyph.y) / height;
+            glyph.u1 = (float)(glyph.x + glyph.width) / width;
+            glyph.v1 = (float)(glyph.y + glyph.height) / height;
+        } else {
+            glyph.u0 = glyph.v0 = glyph.u1 = glyph.v1 = 0.f;
+        }
+    }
+
+    return real_area;
+}
+
+static std::vector<unsigned> parse_ranges(const char *s) {
+    std::vector<unsigned> v;
+    for (; *s; s += !!*s) {
+        auto start = std::strtoul(s, (char **)&s, 0);
+        if (*s == '-') {
+            auto end = std::strtoul(++s, (char **)&s, 0);
+            if (start > end)
+                std::swap(start, end);
+            for (auto i = start; i <= end; ++i)
+                v.push_back((unsigned)i);
+        } else {
+            v.push_back((unsigned)start);
+        }
+    }
+    return v;
+}
+
+int main(int argc, char **argv) {
+    FT_Library library;
+    FT_Face face;
+    int error;
+
+    if (argc < 2 || argc > 4)
+        errx(1, "Usage: %s font size char-range", argv[0]);
+
+    auto size = argc > 2 ? (unsigned)atoi(argv[2]) : 64u;
+    auto codepoints = parse_ranges(argc > 3 ? argv[3] : "0-16777216");
+
+    if (codepoints.size() == 0)
+        errx(1, "Invalid codepoint range: %s", argv[3]);
+    if (size < 8)
+        errx(1, "Invalid size %s", argv[2]);
+
+    if ((error = FT_Init_FreeType(&library)))
+        errx(1, "Can't initialize FreeType: %d", error);
+    if ((error = FT_New_Face(library, argv[1], 0, &face)))
+        errx(1, "Can't load %s: %d", argv[1], error);
+    if ((error = FT_Set_Pixel_Sizes(face, 0, size * SCALE)))
+        errx(1, "Unable to set pixel size.");
+
+    auto glyphs = get_glyphs(face, codepoints);
+    if (glyphs.size() == 0)
+        errx(1, "No glyphs found.");
+    
+    unsigned width, height;
+    auto real_area = get_texture_size(width, height, glyphs);
+    auto wasted = 1.f - float(real_area) / (width * height);
+    fprintf(stderr,
+            "%ux%u texture for %zi glyphs (%u%% wasted).\n", width, height,
+            glyphs.size(), (unsigned)(wasted * 100));
+
+    std::string name(argv[1]);
+    size_t sep;
+    name.erase(name.rfind("."));
+    if ((sep = name.rfind("/")) != std::string::npos)
+        name.erase(0, sep + 1);
+    if ((sep = name.rfind("\\")) != std::string::npos)
+        name.erase(0, sep + 1);
+    
+    Bitmap total(width, height);
+    std::sort(glyphs.begin(), glyphs.end(), glyph_codepoint_sort);
+    auto json_filename = name + ".font.json";
+    auto f = fopen(json_filename.c_str(), "w");
+    if (!f)
+        errx(1, "unable to write JSON data: %s", json_filename.c_str());
+    fprintf(f, "{\n    \"height\": %u,\n", size);
+    fprintf(f, "    \"scale\": %u,\n", SCALE);
+    fprintf(f, "    \"padding\": %u,\n", PADDING);
+    fprintf(f, "    \"glyphs\": {");
+    auto first = true;
+    for (auto &glyph : glyphs) {
+        if (!first)
+            fprintf(f, ",");
+        first = false;
+        fprintf(f, "\n        \"%u\": {\n", glyph.codepoint);
+        fprintf(f, "            \"size\": [%u, %u],\n",
+                glyph.width, glyph.height);
+        fprintf(f, "            \"advance\": [%g, %g],\n",
+                glyph.advance_x, glyph.advance_y);
+        fprintf(f, "            \"offset\": [%g, %g],\n",
+                glyph.left, glyph.top);
+        fprintf(f, "            \"tex_coords\": [%g, %g, %g, %g]\n",
+                glyph.u0, glyph.v0, glyph.u1, glyph.v1);
+        fprintf(f, "        }");
+        total.blit(glyph.pixels, glyph.x, glyph.y);
+    }
+    fprintf(f, "\n    }\n}\n");
+    total.save(name + ".tga");
+}