luihabl / rect_pack.h Goto Github PK

Hi,

Let's say you have just two rects, dimensions 900x900 and 1100x1100,
and you call rect_pack(1000,1000, true, rects, 2)

The first rect can fit, but the second can't, paging enabled or not.
But, with paging enabled, rect_pack will successfully pack the second rect.

The bug is in pack_bin_tree():

pack_res res;
res.all_fit = true;
res.none_fit = true;

rect_r* r = ctx->r;

if(ctx->next == ctx->last) {
    // here, you don't check if it will actually fit
    r[ctx->next].info = empty_rect_r();
    r[ctx->next].info.packed = true;
    r[ctx->next].info.page = ctx->page;
    return res;
}

Also, ctx.paging is not actually used anywhere.

#define RECT_PACK_H_IMPL
#include "rect_pack.h"

#define nrects 199
static rect_r rects[nrects] = {
  #include "rects.h"
};

while (1) {
  // pack 199 rects of approx. 255x255 to 500x500, with paging
  bool b = rect_pack(500, 500, true, rects, nrects);
  if (b == false)
    STOP;
}

Execute this at least 3 times, and the last time it will fail. The first two times it works.

Notice the order of rects: compare_rect_r_max_side() doesn't sort them always the same.

The contents of rects.h:

{.id = 0, .w = 255, .h = 255},
{.id = 1, .w = 255, .h = 253},
{.id = 2, .w = 253, .h = 255},
{.id = 3, .w = 255, .h = 253},
{.id = 4, .w = 255, .h = 253},
{.id = 5, .w = 253, .h = 255},
{.id = 6, .w = 253, .h = 255},
{.id = 7, .w = 253, .h = 255},
{.id = 8, .w = 255, .h = 251},
{.id = 9, .w = 255, .h = 251},
{.id = 10, .w = 251, .h = 255},
{.id = 11, .w = 255, .h = 251},
{.id = 12, .w = 255, .h = 251},
{.id = 13, .w = 251, .h = 255},
{.id = 14, .w = 255, .h = 251},
{.id = 15, .w = 255, .h = 251},
{.id = 16, .w = 255, .h = 249},
{.id = 17, .w = 255, .h = 249},
{.id = 18, .w = 255, .h = 249},
{.id = 19, .w = 255, .h = 249},
{.id = 20, .w = 255, .h = 249},
{.id = 21, .w = 249, .h = 255},
{.id = 22, .w = 255, .h = 249},
{.id = 23, .w = 249, .h = 255},
{.id = 24, .w = 249, .h = 255},
{.id = 25, .w = 247, .h = 255},
{.id = 26, .w = 255, .h = 247},
{.id = 27, .w = 255, .h = 247},
{.id = 28, .w = 255, .h = 245},
{.id = 29, .w = 245, .h = 255},
{.id = 30, .w = 255, .h = 245},
{.id = 31, .w = 255, .h = 245},
{.id = 32, .w = 255, .h = 243},
{.id = 33, .w = 243, .h = 255},
{.id = 34, .w = 243, .h = 255},
{.id = 35, .w = 255, .h = 243},
{.id = 36, .w = 243, .h = 255},
{.id = 37, .w = 243, .h = 255},
{.id = 38, .w = 255, .h = 243},
{.id = 39, .w = 255, .h = 243},
{.id = 40, .w = 255, .h = 241},
{.id = 41, .w = 255, .h = 241},
{.id = 42, .w = 241, .h = 255},
{.id = 43, .w = 241, .h = 255},
{.id = 44, .w = 255, .h = 241},
{.id = 45, .w = 241, .h = 255},
{.id = 46, .w = 255, .h = 241},
{.id = 47, .w = 255, .h = 239},
{.id = 48, .w = 239, .h = 255},
{.id = 49, .w = 239, .h = 255},
{.id = 50, .w = 239, .h = 255},
{.id = 51, .w = 255, .h = 239},
{.id = 52, .w = 239, .h = 255},
{.id = 53, .w = 237, .h = 255},
{.id = 54, .w = 255, .h = 237},
{.id = 55, .w = 237, .h = 255},
{.id = 56, .w = 237, .h = 255},
{.id = 57, .w = 255, .h = 237},
{.id = 58, .w = 255, .h = 237},
{.id = 59, .w = 255, .h = 237},
{.id = 60, .w = 237, .h = 255},
{.id = 61, .w = 237, .h = 255},
{.id = 62, .w = 255, .h = 237},
{.id = 63, .w = 255, .h = 235},
{.id = 64, .w = 235, .h = 255},
{.id = 65, .w = 235, .h = 255},
{.id = 66, .w = 255, .h = 235},
{.id = 67, .w = 255, .h = 233},
{.id = 68, .w = 233, .h = 255},
{.id = 69, .w = 255, .h = 233},
{.id = 70, .w = 233, .h = 255},
{.id = 71, .w = 255, .h = 233},
{.id = 72, .w = 233, .h = 255},
{.id = 73, .w = 233, .h = 255},
{.id = 74, .w = 255, .h = 233},
{.id = 75, .w = 231, .h = 255},
{.id = 76, .w = 253, .h = 253},
{.id = 77, .w = 253, .h = 253},
{.id = 78, .w = 253, .h = 253},
{.id = 79, .w = 251, .h = 253},
{.id = 80, .w = 253, .h = 251},
{.id = 81, .w = 253, .h = 251},
{.id = 82, .w = 251, .h = 253},
{.id = 83, .w = 251, .h = 253},
{.id = 84, .w = 253, .h = 249},
{.id = 85, .w = 253, .h = 249},
{.id = 86, .w = 249, .h = 253},
{.id = 87, .w = 249, .h = 253},
{.id = 88, .w = 249, .h = 253},
{.id = 89, .w = 249, .h = 253},
{.id = 90, .w = 253, .h = 249},
{.id = 91, .w = 253, .h = 249},
{.id = 92, .w = 253, .h = 247},
{.id = 93, .w = 247, .h = 253},
{.id = 94, .w = 247, .h = 253},
{.id = 95, .w = 253, .h = 247},
{.id = 96, .w = 253, .h = 247},
{.id = 97, .w = 253, .h = 247},
{.id = 98, .w = 253, .h = 247},
{.id = 99, .w = 253, .h = 245},
{.id = 100, .w = 253, .h = 245},
{.id = 101, .w = 245, .h = 253},
{.id = 102, .w = 245, .h = 253},
{.id = 103, .w = 253, .h = 243},
{.id = 104, .w = 243, .h = 253},
{.id = 105, .w = 243, .h = 253},
{.id = 106, .w = 253, .h = 243},
{.id = 107, .w = 253, .h = 243},
{.id = 108, .w = 253, .h = 243},
{.id = 109, .w = 243, .h = 253},
{.id = 110, .w = 243, .h = 253},
{.id = 111, .w = 241, .h = 253},
{.id = 112, .w = 253, .h = 241},
{.id = 113, .w = 253, .h = 241},
{.id = 114, .w = 253, .h = 241},
{.id = 115, .w = 241, .h = 253},
{.id = 116, .w = 239, .h = 253},
{.id = 117, .w = 253, .h = 239},
{.id = 118, .w = 239, .h = 253},
{.id = 119, .w = 253, .h = 239},
{.id = 120, .w = 239, .h = 253},
{.id = 121, .w = 253, .h = 239},
{.id = 122, .w = 253, .h = 239},
{.id = 123, .w = 239, .h = 253},
{.id = 124, .w = 239, .h = 253},
{.id = 125, .w = 237, .h = 253},
{.id = 126, .w = 237, .h = 253},
{.id = 127, .w = 253, .h = 237},
{.id = 128, .w = 237, .h = 253},
{.id = 129, .w = 253, .h = 237},
{.id = 130, .w = 237, .h = 253},
{.id = 131, .w = 235, .h = 253},
{.id = 132, .w = 235, .h = 253},
{.id = 133, .w = 235, .h = 253},
{.id = 134, .w = 233, .h = 253},
{.id = 135, .w = 253, .h = 233},
{.id = 136, .w = 233, .h = 253},
{.id = 137, .w = 233, .h = 253},
{.id = 138, .w = 253, .h = 233},
{.id = 139, .w = 233, .h = 253},
{.id = 140, .w = 253, .h = 233},
{.id = 141, .w = 233, .h = 253},
{.id = 142, .w = 253, .h = 233},
{.id = 143, .w = 233, .h = 253},
{.id = 144, .w = 253, .h = 233},
{.id = 145, .w = 253, .h = 233},
{.id = 146, .w = 233, .h = 253},
{.id = 147, .w = 231, .h = 253},
{.id = 148, .w = 253, .h = 231},
{.id = 149, .w = 253, .h = 231},
{.id = 150, .w = 229, .h = 253},
{.id = 151, .w = 229, .h = 253},
{.id = 152, .w = 229, .h = 253},
{.id = 153, .w = 229, .h = 253},
{.id = 154, .w = 251, .h = 251},
{.id = 155, .w = 251, .h = 251},
{.id = 156, .w = 251, .h = 251},
{.id = 157, .w = 251, .h = 249},
{.id = 158, .w = 249, .h = 251},
{.id = 159, .w = 249, .h = 251},
{.id = 160, .w = 249, .h = 251},
{.id = 161, .w = 247, .h = 251},
{.id = 162, .w = 251, .h = 247},
{.id = 163, .w = 251, .h = 247},
{.id = 164, .w = 247, .h = 251},
{.id = 165, .w = 247, .h = 251},
{.id = 166, .w = 247, .h = 251},
{.id = 167, .w = 251, .h = 247},
{.id = 168, .w = 247, .h = 251},
{.id = 169, .w = 251, .h = 247},
{.id = 170, .w = 247, .h = 251},
{.id = 171, .w = 251, .h = 247},
{.id = 172, .w = 251, .h = 245},
{.id = 173, .w = 245, .h = 251},
{.id = 174, .w = 251, .h = 245},
{.id = 175, .w = 251, .h = 245},
{.id = 176, .w = 245, .h = 251},
{.id = 177, .w = 251, .h = 245},
{.id = 178, .w = 251, .h = 243},
{.id = 179, .w = 243, .h = 251},
{.id = 180, .w = 243, .h = 251},
{.id = 181, .w = 243, .h = 251},
{.id = 182, .w = 243, .h = 251},
{.id = 183, .w = 243, .h = 251},
{.id = 184, .w = 251, .h = 243},
{.id = 185, .w = 251, .h = 243},
{.id = 186, .w = 241, .h = 251},
{.id = 187, .w = 251, .h = 241},
{.id = 188, .w = 241, .h = 251},
{.id = 189, .w = 251, .h = 241},
{.id = 190, .w = 241, .h = 251},
{.id = 191, .w = 251, .h = 241},
{.id = 192, .w = 251, .h = 239},
{.id = 193, .w = 239, .h = 251},
{.id = 194, .w = 251, .h = 237},
{.id = 195, .w = 237, .h = 251},
{.id = 196, .w = 251, .h = 237},
{.id = 197, .w = 251, .h = 237},
{.id = 198, .w = 251, .h = 237},

Instead of bool, maybe you should return int, the number of pages used.
If zero, then it didn't successfully pack.
I presume something like this:
return all_packed ? ctx.page +1 : 0;
In my application, I need to know how many pages did it use, and "if (!rect_pack(…))" still works.

Q: if successfully packed, are all rects belonging to one page linear in memory?
All rects from page 0, then all rects from page 1, and so on.
Or, are they mixed - a few rects from page 1, then from page 2, then from page 1 again?
Maybe you should add that info in the readme.

#define nrects 6
static rect_r rects[nrects] = {
  {.id = 0, .w = 5, .h = 6},
  {.id = 1, .w = 5, .h = 5},
  {.id = 2, .w = 2, .h = 5},
  {.id = 3, .w = 4, .h = 6},
  {.id = 4, .w = 7, .h = 1},
  {.id = 5, .w = 2, .h = 7},
};

bool b = rect_pack(10, 10, true, rects, nrects);
if (b == false) STOP;

6 rects with dimensions less than 10x10, can't be packed to 10x10 with paging enabled.