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