Rectangle Packing for Font Atlas

Allen Webster —
Hi everyone, I am here with the follow up on the Cipher Drive stream today. I ended up working on rectangle packing because I need it to complete the font atlas baker utility. I could have just written something dumb and moved on, but the problem struck me as interesting so we dug in and had some fun with that.

On stream the idea I got was the sort the rects by height, so that I could place them in rows. Since I place the tallest rects first, I can treat the first rect of each row as defining the height of that row, and all future rects are guaranteed to fit in that row. Every time I go to place a rect I can either insert it at the end of an existing row, or make a new row. I set it up to make it's decision based on whichever choice minimizes the difference in the width and height of the entire atlas. I chose that method because the obvious move of optimizing the area at each step tends to prevent it from ever starting new rows. Keeping it square some how intuitively meant to me that it would have to be high density and it worked.

Off stream I fixed it up some more to allow it to slip the shortest rectangles in by using the extra space left over when a rectangle that is shorter than the max height of the row it is placed in. With this it got up to 91% efficiency on my test case of LiberationSans-Regular.ttf.

For me, the whole point of making this game is to experiment with everything in order to find new things to make and share. This rectangle packing algorithm is exactly that. So I'm posting to share the code that I came up with. Everyone is free to take it, use it, critique it, improve it, or anything else. I will try to get it on a public git repository sometime soon, but for now it's right here:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
typedef struct Packing_Rectangle{
    uint32_t w,h;
    uint32_t i;
    
    uint32_t x0,y0,x1,y1;
} Packing_Rectangle;

typedef struct Packing_Row{
    uint32_t x,y,h;
} Packing_Row;

#define RectSwap(a,b) do{        \
    uint32_t t;                  \
    t = a.w; a.w = b.w; b.w = t; \
    t = a.h; a.h = b.h; b.h = t; \
    t = a.i; a.i = b.i; b.i = t; \
}while(0)

static int32_t
sort_rects_by_h_partition(Packing_Rectangle *rects, int32_t start, int32_t max){
    int32_t pivot = max - 1;
    uint32_t pivot_h = rects[pivot].h;
    for (int32_t i = start; i < pivot; ++i){
        if (rects[i].h > pivot_h){
            RectSwap(rects[i], rects[start]);
            ++start;
        }
    }
    RectSwap(rects[pivot], rects[start]);
    return(start);
}

static void
sort_rects_by_h(Packing_Rectangle *rects, int32_t start, int32_t max){
    if (start+1 < max){
        int32_t mid = sort_rects_by_h_partition(rects, start, max);
        sort_rects_by_h(rects, start, mid);
        sort_rects_by_h(rects, mid+1, max);
    }
}

#define AbsDif(a,b) (((a)>(b))?((a)-(b)):((b)-(a)))

static void
pack_sorted_rectangles(Packing_Rectangle *rectangles, int32_t count, Packing_Row *rows,
                       uint32_t *packed_w_out, uint32_t *packed_h_out){
    int32_t row_count = 0;
    int32_t best_row_i = 0;
    uint32_t best_row_x = 0, best_row_h = 0, this_x = 0;
    
    uint32_t new_row_y = 0, new_row_x = 0;
    
    uint32_t y_dif = 0, x_dif = 0;
    uint32_t max_x = 0, max_y = 0;
    Packing_Rectangle *rect = 0, *rect2 = 0;
    
    uint32_t left_over_h = 0, under_w = 0;
    
    for (int32_t i = 0; i < count; ++i){
        rect = rectangles + i;
        
        best_row_i = -1;
        best_row_x = 0xFFFFFFFF;
        best_row_h = 0;
        for (int32_t j = 0; j < row_count; ++j){
            this_x = rows[j].x + rect->w;
            if (this_x < max_x){
                this_x = max_x;
            }
            if (this_x < best_row_x || 
                (this_x == best_row_x && best_row_h > rows[j].h)){
                best_row_x = this_x;
                best_row_i = j;
                best_row_h = rows[j].h;
            }
        }
        
        new_row_x = (max_x > rect->w)?(max_x):(rect->w);
        new_row_y = max_y + rect->h;
        y_dif = AbsDif(new_row_y, new_row_x);
        x_dif = AbsDif(max_y, best_row_x);
        
        if (y_dif < x_dif){
            rows[row_count].x = 0;
            rows[row_count].y = max_y;
            rows[row_count].h = rect->h;
            max_y += rect->h;
            best_row_i = row_count;
            ++row_count;
        }
        
        rect->x0 = rows[best_row_i].x;
        rect->y0 = rows[best_row_i].y;
        rect->x1 = rect->x0 + rect->w;
        rect->y1 = rect->y0 + rect->h;
        
        rows[best_row_i].x += rect->w;
        
        under_w = rect->w;
        left_over_h = rows[best_row_i].h - rect->h;
        while (i+1 < count &&
               rectangles[count-1].h <= left_over_h &&
               rectangles[count-1].w <= under_w){
            rect2 = &rectangles[count-1];
            rect2->x0 = rect->x0 + (under_w - rect2->w);
            rect2->y0 = rect->y1;
            rect2->x1 = rect2->x0 + rect2->w;
            rect2->y1 = rect2->y0 + rect2->h;
            under_w -= rect2->w;
            --count;
        }
        
        if (rows[best_row_i].x > max_x){
            max_x = rows[best_row_i].x;
        }
    }
    
    *packed_w_out = max_x;
    *packed_h_out = max_y;
}

Comments

Simon Anciaux
Edited by Simon Anciaux on Reason: typo
Why is there a 
1
do { ... } while ( 0 )
in the swap macro ? Is it to create a scope ?
Jesse
It's a macro technique called "Swallowing the Semicolon".

https://gcc.gnu.org/onlinedocs/cpp/Swallowing-the-Semicolon.html
ratchetfreak
aka the C preprocessor macro system suck so badly, most of the non-trivial code with it is workarounds.
Allen Webster
Edited by Allen Webster on
Yeah I was playing around with using
1
2
3
4
if (condition)
    single_statement();
else
    single_statement2();

style at one point and it broke my macros because if I just use {} to make the scope the else thinks two statements have come since the if instead of one. the do { }while(0) is the only way to get one statement, in a scope, that still needs to end with a semicolon. I quit doing the single statement ifs, but I liked the idea of making the macros more "correct" anyway.
Simon Anciaux
Thanks for the answers.