better atlas layout

[aktau]

I was tinkering somewhat with the code and ended up implementing the skyline bottom-left binpacking heuristic that's also used in the freetype-gl project. I find it produces nice results. Images for comparison below.

old:

skyline bottom-left:

[memononen]

I split off the atlas code just recently in anticipation for this [1] :) (plus there was a stupid bug in the atlas code in the first place, would always place stuff on last line)

Are you using the algos from these articles: http://clb.demon.fi/projects/rectangle-bin-packing ?

[1] https://github.com/memononen/fontstash/commit/ef86c0505546e657f1c2096054b09ce2a809a662

[aktau]

I actually hadn't seen that specific page before, but indirectly, yes. I implemented the "skyline bottom-left" heuristic almost exactly as it's found in the freetype-gl project. Which in turn derives its implementation from this paper: http://clb.demon.fi/files/RectangleBinPack.pdf which I notice is from the same page as the one you linked. So I bet there are some similarities.

[aktau]

After taking a better look at the page you referenced. Nope, it's not the same algorithm, does look interesting though. I really wonder if it's better...

[aktau]

Alright, found a follow-up article to the one you posted:

http://clb.demon.fi/projects/more-rectangle-bin-packing

It clarifies that the page you first linked to describes the guillotine algorithm. The one I ended up implementing was the skyline algorithm. Which is simpler and can be implemented with a static data structure (no malloc/new). I didn't implement a waste-map yet. I've yet to see it be useful. But maybe it's possible to find some pathological cases that benefit from a waste-map...

[r-lyeh-archived]

hey guys. is this going to be integrated into the main repo? thx

[aktau]

hey guys. is this going to be integrated into the main repo? thx

My repo has deviated substantially and is more for experimentation before I integrate it into my toy engine. I prefer a mix of Miko's first ideas with the Mio architecture, rather than the current state of fontstash. That's just personal preference. However, my skyline code should be pretty easy to integrate and has the nice property of being statically allocated, and that one node only takes 8 bytes of memory. This makes it very likely to end up in the cache and reduces the need for defragmenting the static link list (which I haven't included yet anyhow). Of course it could use a bit of cleanup, I was prototyping it anyway...

The work is in the aktau-gl3 branch: https://github.com/aktau/fontstash/tree/aktau-gl3

Extracting the relevant code (I hope I got it all), gives me this (NOTE: it's not complete, the packer needs to be intialized from the calling code et cetera.):

/* I use ifdef's to switch out packers in my prototype */
#define SKYLINE_BL_PACKER

#ifdef SKYLINE_BL_PACKER
static void packer_init(void);
#endif

static void clear_glyph_cache(void) {
    text_flush();

    memset(table, 0, sizeof table);
    table_load = 0;

    glBindTexture(GL_TEXTURE_2D, cache_tex);
    glTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, CACHESIZE, CACHESIZE,
        GL_RED, GL_UNSIGNED_BYTE, cache_zero);

#ifdef SKYLINE_BL_PACKER
    printf("RE-INITIALIZING skyline packer\n");
    packer_init();
#else
    printf("RE-INITIALIZING normal packer\n");
    cache_row_y = PADDING;
    cache_row_x = PADDING;
    cache_row_h = 0;
#endif
}

#ifdef SKYLINE_BL_PACKER

#ifndef MAX
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#endif

#define SKYLINE_MAX_NODES 256

/**
 * struct 2+2+2+2 = 8 bytes, with a 64
 * bytes cacheline we can fetch 8 of these
 * in one go. Now we just have to make sure that
 * the indices are actually close together.
 */
struct skyline_node {
    int16_t next;
    uint16_t x;
    uint16_t y;
    uint16_t width;
};

static struct skyline_node skyline_nodes[SKYLINE_MAX_NODES];
int first_node_index = 0;

static void pack_debug(int max) {
    for (int i = 0; i < max; ++i) {
        struct skyline_node *node = &skyline_nodes[i];
        printf("%snode at index %d: (x: %u, y: %u, w: %u) -> points to %d\n",
                ((i == first_node_index) ? "[FIRST] " : ""),
                i, node->x, node->y, node->width, node->next);
    }
}

static int find_free_index() {
    for (int i = 0; i < SKYLINE_MAX_NODES; ++i) {
        if (skyline_nodes[i].width == 0) return i;
    }

    return -1;
}

static int insert_node(int index, int before, struct skyline_node *node) {
    /* find a free spot */
    int free_index = find_free_index();
    if (free_index == -1) {
        printf("[ERROR] everything is full\n");
        return -1;
    }

    /* printf("inserting a new node at %d, next is %d, before is %d, data is (x: %u, y: %u, w: %u)\n", */
    /*         free_index, index, before, node->x, node->y, node->width); */
    /* skyline_nodes[free_index] = (struct skyline_node){ best_index, best_x, best_height, width }; */

    skyline_nodes[free_index] = *node;
    skyline_nodes[free_index].next = index;

    if (before != -1) {
        skyline_nodes[before].next = free_index;
    }

    /* if this replaces the first node... */
    if (index == first_node_index) {
        first_node_index = free_index;
    }

    return free_index;
}

/* param i is the index from where to begin scanning, should be one
 * index before the newly inserted node */
static void merge(int i) {
    if (i == -1) return;

    struct skyline_node *node = &skyline_nodes[i];

    int counter = 2;
    do {
        struct skyline_node *next = &skyline_nodes[node->next];

        if (node->y == next->y) {
            /* if two adjacent nodes are at an equal height, suck the width
             * out of the last node and add it to the first. Then delete the
             * last node. */
            node->width += next->width;

            node->next   = next->next;
            next->width  = 0;

            ++counter;
        }
        else {
            if (node->next == -1) break;

            node = &skyline_nodes[node->next];
        }
    } while (--counter);
}

static void shrink(int i) {
    if (i == -1) return;

    /* printf("[shrink] starting at index: %d\n", i); */
    struct skyline_node *prev = &skyline_nodes[i];
    while (prev->next != -1) {
        struct skyline_node *node = &skyline_nodes[prev->next];

        if (node->x < prev->x + prev->width) {
            /* printf("[shrink] %u < %u + %u\n", node->x, prev->x, prev->width); */
            int shrink = prev->x + prev->width - node->x;

            /* node shrunk into oblivion, remove it */
            if (node->width - shrink <= 0) {
                /* printf("[shrink] node %d shrunk into oblivion, %u < %u + %u (new width: %u, next: %d)\n", prev->next, node->x, prev->x, prev->width, node->width, node->next); */
                node->width = 0;
                prev->next = node->next;
            }
            else {
                node->x     += shrink;
                node->width -= shrink;

                /* printf("[shrink] node did not shrink into oblivion, %u < %u + %u (new width: %u)\n", node->x, prev->x, prev->width, node->width); */
                break;
            }
        }
        else {
            /* printf("[shrink] break, %u >= %u + %u\n", node->x, prev->x, prev->width); */
            break;
        }
    }

    /* printf("[shrink] done shrinking\n"); */
}

/* for the node at index, tries to find a height which will
 * fit the area specified. */
static int fit(unsigned int index, unsigned int width, unsigned int height) {
    struct skyline_node *node = &skyline_nodes[index];

    unsigned int x = node->x;
    unsigned int y = node->y;

    int width_left = width;

    if (x + width > CACHESIZE - PADDING) {
        return -1;
    }

    while (width_left > 0 && node->next != -1) {
        /* TODO: should assert that the next nodes are after the
         * first ones on the horiz. axis */
        y = MAX(y, node->y);

        if (y + height > CACHESIZE - PADDING) {
            return -1;
        }

        width_left -= node->width;

        node = &skyline_nodes[node->next];
    }

    return y;
}

/**
 * returns 1 if the object was packed, 0 if it could not be packed.
 *
 * The coordinates are in the x and y parameters if succesful.
 *
 * Try to fit the area in every node you have, the node that's able
 * to accomodate the area and have the lowest "roof", wins. In case of
 * ties, the node with the smallest width wins.
 *
 * A new node is created afterwards and inserted at the position of the
 * node this area was fit in.
 */
/* static int counter = 0; */
static int pack(unsigned int width, unsigned int height, int *x_out, int *y_out) {
    /* if (++counter == 5) assert(NULL); */
    /* if (width == 3 && height == 4) assert(NULL); */
    /* printf("-> TRY TO PACK OBJECT: [%u, %u]\n", width, height); */

    int last_index = -1;
    int index = first_node_index;

    int y;

    int best_index        = -1;
    int before_best_index = -1;
    uint16_t best_x       = UINT16_MAX;
    uint16_t best_y       = UINT16_MAX;
    uint16_t best_width   = UINT16_MAX;
    uint16_t best_height  = UINT16_MAX;

    /* loop through all nodes */
    while (index != -1) {
        /* printf("LOOP THROUGH NODES: index = %d", index); */
        /* see if this node can fit the required size */
        y = fit(index, width, height);
        const struct skyline_node *node = &skyline_nodes[index];
        /* printf(", fit-y = %d, node = (x: %u, y: %u, w: %u)\n", y, node->x, node->y, node->width); */

        if (y >= 0) {
            /* if the current node can place the region lower than the last best
             * node, then this node becomes the new best. If it ranks equal,
             * then it will still be the best if the current node is less
             * wide than the last one */
            if (y + height < best_height ||
                (y + height == best_height && node->width < best_width)) {
                best_index  = index;
                before_best_index = last_index;

                best_height = y + height;
                best_width  = node->width;
                best_x      = node->x;
                best_y      = y;
            }
        }

        last_index = index;
        index      = node->next;
    }

    if (best_index == -1) {
        return 0;
    }

    /* insert new split node at the best index */
    int new_index = insert_node(
        best_index,
        before_best_index,
        &(struct skyline_node){ best_index, best_x, best_height, width }
    );

    shrink(new_index);
    merge(before_best_index);

    *x_out = best_x;
    *y_out = best_y;

    return 1;
}

static void packer_init() {
    for (int i = 0; i < SKYLINE_MAX_NODES; ++i) {
        skyline_nodes[i].next  = -1;
        skyline_nodes[i].x     = PADDING;
        skyline_nodes[i].y     = PADDING;
        skyline_nodes[i].width = 0;
    }

    skyline_nodes[0].width = CACHESIZE;
    first_node_index = 0;
}
#endif

static struct glyph *lookup_glyph(struct font *font, float scale, int gid, int subx, int suby) {
    struct key key;
    unsigned int pos;
    unsigned char *data;
    float shift_x, shift_y;
    int w, h, x, y;
    int advance, lsb;

    /* Look it up in the table */

    memset(&key, 0, sizeof key);
    key.font = font;
    key.size = scale * 10000;
    key.gid = gid;
    key.subx = subx;
    key.suby = suby;

    pos = lookup_table(&key);
    if (table[pos].key.font)
        return &table[pos].glyph;

    /* Render the bitmap */

    shift_x = (float)subx / XPRECISION;
    shift_y = (float)suby / YPRECISION;

    stbtt_GetGlyphHMetrics(&font->info, gid, &advance, &lsb);
    data = stbtt_GetGlyphBitmapSubpixel(&font->info, scale, scale, shift_x, shift_y, gid, &w, &h, &x, &y);

    /* if (!data || !w || !h) { */
    /*     printf("error: could not render glyph %p, %d, %d\n", data, w, h); */
    /*     return &table[pos].glyph; */
    /* } */

    if (h + PADDING > CACHESIZE || w + PADDING > CACHESIZE) {
        printf("error: rendered glyph exceeds cache dimensions");
        exit(1);
    }

    /* find an empty slot in the texture */
    if (table_load == (MAXGLYPHS * 3) / 4) {
        puts("glyph cache table full (load > 0.75), clearing cache");
        clear_glyph_cache();
        pos = lookup_table(&key);
    }

#ifndef SKYLINE_BL_PACKER
    if (cache_row_x + w + PADDING > CACHESIZE) {
        cache_row_y += cache_row_h + PADDING;
        cache_row_x = PADDING;
        cache_row_h = 0;
    }

    if (cache_row_y + h + PADDING > CACHESIZE) {
        printf("glyph cache texture full, (%d + %d + %d (%d) > %d), clearing cache\n", cache_row_y, h, PADDING, cache_row_y + h + PADDING, CACHESIZE);
        clear_glyph_cache();
        pos = lookup_table(&key);
    }

    int texture_x = cache_row_x;
    int texture_y = cache_row_y;

    cache_row_x += w + PADDING;
    if (cache_row_h < h + PADDING)
        cache_row_h = h + PADDING;
#else
retry:;
    int texture_x = -1;
    int texture_y = -1;
    int res = pack(w, h, &texture_x, &texture_y);
    /* printf("<- JUST PACKED OBJECT: [%u, %u] -> [%d, %d]\n", w, h, texture_x, texture_y); */

    if (res == -1) {
        printf("could not cache texture, resetting\n");
        clear_glyph_cache();
        goto retry;
    }
#endif

    ++table_load;

    /* copy the bitmap into our texture */
    memcpy(&table[pos].key, &key, sizeof(struct key));
    table[pos].glyph.w = w;
    table[pos].glyph.h = h;
    table[pos].glyph.x = x;
    table[pos].glyph.y = y;
    table[pos].glyph.s = texture_x;
    table[pos].glyph.t = texture_y;
    table[pos].glyph.advance = advance * scale;

    if (data && w && h) {
        glPixelStorei(GL_UNPACK_ALIGNMENT, 1);
        glPixelStorei(GL_UNPACK_ROW_LENGTH, w);
        glTexSubImage2D(GL_TEXTURE_2D, 0, texture_x, texture_y, w, h, GL_RED, GL_UNSIGNED_BYTE, data);
        glPixelStorei(GL_UNPACK_ROW_LENGTH, 0);
    }

    free(data);

    return &table[pos].glyph;
}

void text_init() {
#ifdef SKYLINE_BL_PACKER
    packer_init();
#endif
}

[memononen]

I've got distracted onto other projects recently.

Aktau, that code looks nice and clean, I'd love to use it. Which license it uses?

[aktau]

Aktau, that code looks nice and clean, I'd love to use it. Which license it uses?

For license compatibility with the fontstash project I'll just do this:

I formally state that the code I wrote and pasted above falls under the terms of the zlib license.

I can see that somehow the LICENSE file got excluded from your repo (possibly in some git operation while refactoring). It's probably best to re-add that and also add a COPYRIGHT notice and/or AUTHORS file.

[memononen]

Hi, I implemented the skyline packer based on bottom-left heuristic. I used the original code from http://clb.demon.fi/ but it is not substantially different from aktau's code.