stb/stb_rect_pack.h

   1 // stb_rect_pack.h - v0.10 - public domain - rectangle packing
   2 // Sean Barrett 2014
   3 //
   4 // Useful for e.g. packing rectangular textures into an atlas.
   5 // Does not do rotation.
   6 //
   7 // Not necessarily the awesomest packing method, but better than
   8 // the totally naive one in stb_truetype (which is primarily what
   9 // this is meant to replace).
  10 //
  11 // Has only had a few tests run, may have issues.
  12 //
  13 // More docs to come.
  14 //
  15 // No memory allocations; uses qsort() and assert() from stdlib.
  16 // Can override those by defining STBRP_SORT and STBRP_ASSERT.
  17 //
  18 // This library currently uses the Skyline Bottom-Left algorithm.
  19 //
  20 // Please note: better rectangle packers are welcome! Please
  21 // implement them to the same API, but with a different init
  22 // function.
  23 //
  24 // Credits
  25 //
  26 //  Library
  27 //    Sean Barrett
  28 //  Minor features
  29 //    Martins Mozeiko
  30 //  Bugfixes / warning fixes
  31 //    Jeremy Jaussaud
  32 //
  33 // Version history:
  34 //
  35 //     0.10  (2016-10-25)  remove cast-away-const to avoid warnings
  36 //     0.09  (2016-08-27)  fix compiler warnings
  37 //     0.08  (2015-09-13)  really fix bug with empty rects (w=0 or h=0)
  38 //     0.07  (2015-09-13)  fix bug with empty rects (w=0 or h=0)
  39 //     0.06  (2015-04-15)  added STBRP_SORT to allow replacing qsort
  40 //     0.05:  added STBRP_ASSERT to allow replacing assert
  41 //     0.04:  fixed minor bug in STBRP_LARGE_RECTS support
  42 //     0.01:  initial release
  43 //
  44 // LICENSE
  45 //
  46 //   This software is dual-licensed to the public domain and under the following
  47 //   license: you are granted a perpetual, irrevocable license to copy, modify,
  48 //   publish, and distribute this file as you see fit.
  49
  50 //////////////////////////////////////////////////////////////////////////////
  51 //
  52 //       INCLUDE SECTION
  53 //
  54
  55 #ifndef STB_INCLUDE_STB_RECT_PACK_H
  56 #define STB_INCLUDE_STB_RECT_PACK_H
  57
  58 #define STB_RECT_PACK_VERSION  1
  59
  60 #ifdef STBRP_STATIC
  61 #define STBRP_DEF static
  62 #else
  63 #define STBRP_DEF extern
  64 #endif
  65
  66 #ifdef __cplusplus
  67 extern "C" {
  68 #endif
  69
  70 typedef struct stbrp_context stbrp_context;
  71 typedef struct stbrp_node    stbrp_node;
  72 typedef struct stbrp_rect    stbrp_rect;
  73
  74 #ifdef STBRP_LARGE_RECTS
  75 typedef int            stbrp_coord;
  76 #else
  77 typedef unsigned short stbrp_coord;
  78 #endif
  79
  80 STBRP_DEF void stbrp_pack_rects (stbrp_context *context, stbrp_rect *rects, int num_rects);
  81 // Assign packed locations to rectangles. The rectangles are of type
  82 // 'stbrp_rect' defined below, stored in the array 'rects', and there
  83 // are 'num_rects' many of them.
  84 //
  85 // Rectangles which are successfully packed have the 'was_packed' flag
  86 // set to a non-zero value and 'x' and 'y' store the minimum location
  87 // on each axis (i.e. bottom-left in cartesian coordinates, top-left
  88 // if you imagine y increasing downwards). Rectangles which do not fit
  89 // have the 'was_packed' flag set to 0.
  90 //
  91 // You should not try to access the 'rects' array from another thread
  92 // while this function is running, as the function temporarily reorders
  93 // the array while it executes.
  94 //
  95 // To pack into another rectangle, you need to call stbrp_init_target
  96 // again. To continue packing into the same rectangle, you can call
  97 // this function again. Calling this multiple times with multiple rect
  98 // arrays will probably produce worse packing results than calling it
  99 // a single time with the full rectangle array, but the option is
 100 // available.
 101
 102 struct stbrp_rect
 103 {
 104    // reserved for your use:
 105    int            id;
 106
 107    // input:
 108    stbrp_coord    w, h;
 109
 110    // output:
 111    stbrp_coord    x, y;
 112    int            was_packed;  // non-zero if valid packing
 113
 114 }; // 16 bytes, nominally
 115
 116
 117 STBRP_DEF void stbrp_init_target (stbrp_context *context, int width, int height, stbrp_node *nodes, int num_nodes);
 118 // Initialize a rectangle packer to:
 119 //    pack a rectangle that is 'width' by 'height' in dimensions
 120 //    using temporary storage provided by the array 'nodes', which is 'num_nodes' long
 121 //
 122 // You must call this function every time you start packing into a new target.
 123 //
 124 // There is no "shutdown" function. The 'nodes' memory must stay valid for
 125 // the following stbrp_pack_rects() call (or calls), but can be freed after
 126 // the call (or calls) finish.
 127 //
 128 // Note: to guarantee best results, either:
 129 //       1. make sure 'num_nodes' >= 'width'
 130 //   or  2. call stbrp_allow_out_of_mem() defined below with 'allow_out_of_mem = 1'
 131 //
 132 // If you don't do either of the above things, widths will be quantized to multiples
 133 // of small integers to guarantee the algorithm doesn't run out of temporary storage.
 134 //
 135 // If you do #2, then the non-quantized algorithm will be used, but the algorithm
 136 // may run out of temporary storage and be unable to pack some rectangles.
 137
 138 STBRP_DEF void stbrp_setup_allow_out_of_mem (stbrp_context *context, int allow_out_of_mem);
 139 // Optionally call this function after init but before doing any packing to
 140 // change the handling of the out-of-temp-memory scenario, described above.
 141 // If you call init again, this will be reset to the default (false).
 142
 143
 144 STBRP_DEF void stbrp_setup_heuristic (stbrp_context *context, int heuristic);
 145 // Optionally select which packing heuristic the library should use. Different
 146 // heuristics will produce better/worse results for different data sets.
 147 // If you call init again, this will be reset to the default.
 148
 149 enum
 150 {
 151    STBRP_HEURISTIC_Skyline_default=0,
 152    STBRP_HEURISTIC_Skyline_BL_sortHeight = STBRP_HEURISTIC_Skyline_default,
 153    STBRP_HEURISTIC_Skyline_BF_sortHeight
 154 };
 155
 156
 157 //////////////////////////////////////////////////////////////////////////////
 158 //
 159 // the details of the following structures don't matter to you, but they must
 160 // be visible so you can handle the memory allocations for them
 161
 162 struct stbrp_node
 163 {
 164    stbrp_coord  x,y;
 165    stbrp_node  *next;
 166 };
 167
 168 struct stbrp_context
 169 {
 170    int width;
 171    int height;
 172    int align;
 173    int init_mode;
 174    int heuristic;
 175    int num_nodes;
 176    stbrp_node *active_head;
 177    stbrp_node *free_head;
 178    stbrp_node extra[2]; // we allocate two extra nodes so optimal user-node-count is 'width' not 'width+2'
 179 };
 180
 181 #ifdef __cplusplus
 182 }
 183 #endif
 184
 185 #endif
 186
 187 //////////////////////////////////////////////////////////////////////////////
 188 //
 189 //     IMPLEMENTATION SECTION
 190 //
 191
 192 #ifdef STB_RECT_PACK_IMPLEMENTATION
 193 #ifndef STBRP_SORT
 194 #include <stdlib.h>
 195 #define STBRP_SORT qsort
 196 #endif
 197
 198 #ifndef STBRP_ASSERT
 199 #include <assert.h>
 200 #define STBRP_ASSERT assert
 201 #endif
 202
 203 #ifdef _MSC_VER
 204 #define STBRP__NOTUSED(v)  (void)(v)
 205 #else
 206 #define STBRP__NOTUSED(v)  (void)sizeof(v)
 207 #endif
 208
 209 enum
 210 {
 211    STBRP__INIT_skyline = 1
 212 };
 213
 214 STBRP_DEF void stbrp_setup_heuristic(stbrp_context *context, int heuristic)
 215 {
 216    switch (context->init_mode) {
 217       case STBRP__INIT_skyline:
 218          STBRP_ASSERT(heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight || heuristic == STBRP_HEURISTIC_Skyline_BF_sortHeight);
 219          context->heuristic = heuristic;
 220          break;
 221       default:
 222          STBRP_ASSERT(0);
 223    }
 224 }
 225
 226 STBRP_DEF void stbrp_setup_allow_out_of_mem(stbrp_context *context, int allow_out_of_mem)
 227 {
 228    if (allow_out_of_mem)
 229       // if it's ok to run out of memory, then don't bother aligning them;
 230       // this gives better packing, but may fail due to OOM (even though
 231       // the rectangles easily fit). @TODO a smarter approach would be to only
 232       // quantize once we've hit OOM, then we could get rid of this parameter.
 233       context->align = 1;
 234    else {
 235       // if it's not ok to run out of memory, then quantize the widths
 236       // so that num_nodes is always enough nodes.
 237       //
 238       // I.e. num_nodes * align >= width
 239       //                  align >= width / num_nodes
 240       //                  align = ceil(width/num_nodes)
 241
 242       context->align = (context->width + context->num_nodes-1) / context->num_nodes;
 243    }
 244 }
 245
 246 STBRP_DEF void stbrp_init_target(stbrp_context *context, int width, int height, stbrp_node *nodes, int num_nodes)
 247 {
 248    int i;
 249 #ifndef STBRP_LARGE_RECTS
 250    STBRP_ASSERT(width <= 0xffff && height <= 0xffff);
 251 #endif
 252
 253    for (i=0; i < num_nodes-1; ++i)
 254       nodes[i].next = &nodes[i+1];
 255    nodes[i].next = NULL;
 256    context->init_mode = STBRP__INIT_skyline;
 257    context->heuristic = STBRP_HEURISTIC_Skyline_default;
 258    context->free_head = &nodes[0];
 259    context->active_head = &context->extra[0];
 260    context->width = width;
 261    context->height = height;
 262    context->num_nodes = num_nodes;
 263    stbrp_setup_allow_out_of_mem(context, 0);
 264
 265    // node 0 is the full width, node 1 is the sentinel (lets us not store width explicitly)
 266    context->extra[0].x = 0;
 267    context->extra[0].y = 0;
 268    context->extra[0].next = &context->extra[1];
 269    context->extra[1].x = (stbrp_coord) width;
 270 #ifdef STBRP_LARGE_RECTS
 271    context->extra[1].y = (1<<30);
 272 #else
 273    context->extra[1].y = 65535;
 274 #endif
 275    context->extra[1].next = NULL;
 276 }
 277
 278 // find minimum y position if it starts at x1
 279 static int stbrp__skyline_find_min_y(stbrp_context *c, stbrp_node *first, int x0, int width, int *pwaste)
 280 {
 281    stbrp_node *node = first;
 282    int x1 = x0 + width;
 283    int min_y, visited_width, waste_area;
 284
 285    STBRP__NOTUSED(c);
 286
 287    STBRP_ASSERT(first->x <= x0);
 288
 289    #if 0
 290    // skip in case we're past the node
 291    while (node->next->x <= x0)
 292       ++node;
 293    #else
 294    STBRP_ASSERT(node->next->x > x0); // we ended up handling this in the caller for efficiency
 295    #endif
 296
 297    STBRP_ASSERT(node->x <= x0);
 298
 299    min_y = 0;
 300    waste_area = 0;
 301    visited_width = 0;
 302    while (node->x < x1) {
 303       if (node->y > min_y) {
 304          // raise min_y higher.
 305          // we've accounted for all waste up to min_y,
 306          // but we'll now add more waste for everything we've visted
 307          waste_area += visited_width * (node->y - min_y);
 308          min_y = node->y;
 309          // the first time through, visited_width might be reduced
 310          if (node->x < x0)
 311             visited_width += node->next->x - x0;
 312          else
 313             visited_width += node->next->x - node->x;
 314       } else {
 315          // add waste area
 316          int under_width = node->next->x - node->x;
 317          if (under_width + visited_width > width)
 318             under_width = width - visited_width;
 319          waste_area += under_width * (min_y - node->y);
 320          visited_width += under_width;
 321       }
 322       node = node->next;
 323    }
 324
 325    *pwaste = waste_area;
 326    return min_y;
 327 }
 328
 329 typedef struct
 330 {
 331    int x,y;
 332    stbrp_node **prev_link;
 333 } stbrp__findresult;
 334
 335 static stbrp__findresult stbrp__skyline_find_best_pos(stbrp_context *c, int width, int height)
 336 {
 337    int best_waste = (1<<30), best_x, best_y = (1 << 30);
 338    stbrp__findresult fr;
 339    stbrp_node **prev, *node, *tail, **best = NULL;
 340
 341    // align to multiple of c->align
 342    width = (width + c->align - 1);
 343    width -= width % c->align;
 344    STBRP_ASSERT(width % c->align == 0);
 345
 346    node = c->active_head;
 347    prev = &c->active_head;
 348    while (node->x + width <= c->width) {
 349       int y,waste;
 350       y = stbrp__skyline_find_min_y(c, node, node->x, width, &waste);
 351       if (c->heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight) { // actually just want to test BL
 352          // bottom left
 353          if (y < best_y) {
 354             best_y = y;
 355             best = prev;
 356          }
 357       } else {
 358          // best-fit
 359          if (y + height <= c->height) {
 360             // can only use it if it first vertically
 361             if (y < best_y || (y == best_y && waste < best_waste)) {
 362                best_y = y;
 363                best_waste = waste;
 364                best = prev;
 365             }
 366          }
 367       }
 368       prev = &node->next;
 369       node = node->next;
 370    }
 371
 372    best_x = (best == NULL) ? 0 : (*best)->x;
 373
 374    // if doing best-fit (BF), we also have to try aligning right edge to each node position
 375    //
 376    // e.g, if fitting
 377    //
 378    //     ____________________
 379    //    |____________________|
 380    //
 381    //            into
 382    //
 383    //   |                         |
 384    //   |             ____________|
 385    //   |____________|
 386    //
 387    // then right-aligned reduces waste, but bottom-left BL is always chooses left-aligned
 388    //
 389    // This makes BF take about 2x the time
 390
 391    if (c->heuristic == STBRP_HEURISTIC_Skyline_BF_sortHeight) {
 392       tail = c->active_head;
 393       node = c->active_head;
 394       prev = &c->active_head;
 395       // find first node that's admissible
 396       while (tail->x < width)
 397          tail = tail->next;
 398       while (tail) {
 399          int xpos = tail->x - width;
 400          int y,waste;
 401          STBRP_ASSERT(xpos >= 0);
 402          // find the left position that matches this
 403          while (node->next->x <= xpos) {
 404             prev = &node->next;
 405             node = node->next;
 406          }
 407          STBRP_ASSERT(node->next->x > xpos && node->x <= xpos);
 408          y = stbrp__skyline_find_min_y(c, node, xpos, width, &waste);
 409          if (y + height < c->height) {
 410             if (y <= best_y) {
 411                if (y < best_y || waste < best_waste || (waste==best_waste && xpos < best_x)) {
 412                   best_x = xpos;
 413                   STBRP_ASSERT(y <= best_y);
 414                   best_y = y;
 415                   best_waste = waste;
 416                   best = prev;
 417                }
 418             }
 419          }
 420          tail = tail->next;
 421       }
 422    }
 423
 424    fr.prev_link = best;
 425    fr.x = best_x;
 426    fr.y = best_y;
 427    return fr;
 428 }
 429
 430 static stbrp__findresult stbrp__skyline_pack_rectangle(stbrp_context *context, int width, int height)
 431 {
 432    // find best position according to heuristic
 433    stbrp__findresult res = stbrp__skyline_find_best_pos(context, width, height);
 434    stbrp_node *node, *cur;
 435
 436    // bail if:
 437    //    1. it failed
 438    //    2. the best node doesn't fit (we don't always check this)
 439    //    3. we're out of memory
 440    if (res.prev_link == NULL || res.y + height > context->height || context->free_head == NULL) {
 441       res.prev_link = NULL;
 442       return res;
 443    }
 444
 445    // on success, create new node
 446    node = context->free_head;
 447    node->x = (stbrp_coord) res.x;
 448    node->y = (stbrp_coord) (res.y + height);
 449
 450    context->free_head = node->next;
 451
 452    // insert the new node into the right starting point, and
 453    // let 'cur' point to the remaining nodes needing to be
 454    // stiched back in
 455
 456    cur = *res.prev_link;
 457    if (cur->x < res.x) {
 458       // preserve the existing one, so start testing with the next one
 459       stbrp_node *next = cur->next;
 460       cur->next = node;
 461       cur = next;
 462    } else {
 463       *res.prev_link = node;
 464    }
 465
 466    // from here, traverse cur and free the nodes, until we get to one
 467    // that shouldn't be freed
 468    while (cur->next && cur->next->x <= res.x + width) {
 469       stbrp_node *next = cur->next;
 470       // move the current node to the free list
 471       cur->next = context->free_head;
 472       context->free_head = cur;
 473       cur = next;
 474    }
 475
 476    // stitch the list back in
 477    node->next = cur;
 478
 479    if (cur->x < res.x + width)
 480       cur->x = (stbrp_coord) (res.x + width);
 481
 482 #ifdef _DEBUG
 483    cur = context->active_head;
 484    while (cur->x < context->width) {
 485       STBRP_ASSERT(cur->x < cur->next->x);
 486       cur = cur->next;
 487    }
 488    STBRP_ASSERT(cur->next == NULL);
 489
 490    {
 491       stbrp_node *L1 = NULL, *L2 = NULL;
 492       int count=0;
 493       cur = context->active_head;
 494       while (cur) {
 495          L1 = cur;
 496          cur = cur->next;
 497          ++count;
 498       }
 499       cur = context->free_head;
 500       while (cur) {
 501          L2 = cur;
 502          cur = cur->next;
 503          ++count;
 504       }
 505       STBRP_ASSERT(count == context->num_nodes+2);
 506    }
 507 #endif
 508
 509    return res;
 510 }
 511
 512 static int rect_height_compare(const void *a, const void *b)
 513 {
 514    const stbrp_rect *p = (const stbrp_rect *) a;
 515    const stbrp_rect *q = (const stbrp_rect *) b;
 516    if (p->h > q->h)
 517       return -1;
 518    if (p->h < q->h)
 519       return  1;
 520    return (p->w > q->w) ? -1 : (p->w < q->w);
 521 }
 522
 523 static int rect_width_compare(const void *a, const void *b)
 524 {
 525    const stbrp_rect *p = (const stbrp_rect *) a;
 526    const stbrp_rect *q = (const stbrp_rect *) b;
 527    if (p->w > q->w)
 528       return -1;
 529    if (p->w < q->w)
 530       return  1;
 531    return (p->h > q->h) ? -1 : (p->h < q->h);
 532 }
 533
 534 static int rect_original_order(const void *a, const void *b)
 535 {
 536    const stbrp_rect *p = (const stbrp_rect *) a;
 537    const stbrp_rect *q = (const stbrp_rect *) b;
 538    return (p->was_packed < q->was_packed) ? -1 : (p->was_packed > q->was_packed);
 539 }
 540
 541 #ifdef STBRP_LARGE_RECTS
 542 #define STBRP__MAXVAL  0xffffffff
 543 #else
 544 #define STBRP__MAXVAL  0xffff
 545 #endif
 546
 547 STBRP_DEF void stbrp_pack_rects(stbrp_context *context, stbrp_rect *rects, int num_rects)
 548 {
 549    int i;
 550
 551    // we use the 'was_packed' field internally to allow sorting/unsorting
 552    for (i=0; i < num_rects; ++i) {
 553       rects[i].was_packed = i;
 554       #ifndef STBRP_LARGE_RECTS
 555       STBRP_ASSERT(rects[i].w <= 0xffff && rects[i].h <= 0xffff);
 556       #endif
 557    }
 558
 559    // sort according to heuristic
 560    STBRP_SORT(rects, num_rects, sizeof(rects[0]), rect_height_compare);
 561
 562    for (i=0; i < num_rects; ++i) {
 563       if (rects[i].w == 0 || rects[i].h == 0) {
 564          rects[i].x = rects[i].y = 0;  // empty rect needs no space
 565       } else {
 566          stbrp__findresult fr = stbrp__skyline_pack_rectangle(context, rects[i].w, rects[i].h);
 567          if (fr.prev_link) {
 568             rects[i].x = (stbrp_coord) fr.x;
 569             rects[i].y = (stbrp_coord) fr.y;
 570          } else {
 571             rects[i].x = rects[i].y = STBRP__MAXVAL;
 572          }
 573       }
 574    }
 575
 576    // unsort
 577    STBRP_SORT(rects, num_rects, sizeof(rects[0]), rect_original_order);
 578
 579    // set was_packed flags
 580    for (i=0; i < num_rects; ++i)
 581       rects[i].was_packed = !(rects[i].x == STBRP__MAXVAL && rects[i].y == STBRP__MAXVAL);
 582 }
 583 #endif