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:

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; } |

Why is there a

in the swap macro ? Is it to create a scope ?

1 | do { ... } while ( 0 ) |

It's a macro technique called "Swallowing the Semicolon".

https://gcc.gnu.org/onlinedocs/cpp/Swallowing-the-Semicolon.html

https://gcc.gnu.org/onlinedocs/cpp/Swallowing-the-Semicolon.html

aka the C preprocessor macro system suck so badly, most of the non-trivial code with it is workarounds.

Yeah I was playing around with using

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.

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.

Thanks for the answers.