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