imstb_rectpack.h (20540B)
1 // [DEAR IMGUI] 2 // This is a slightly modified version of stb_rect_pack.h 1.00. 3 // Those changes would need to be pushed into nothings/stb: 4 // - Added STBRP__CDECL 5 // Grep for [DEAR IMGUI] to find the changes. 6 7 // stb_rect_pack.h - v1.00 - public domain - rectangle packing 8 // Sean Barrett 2014 9 // 10 // Useful for e.g. packing rectangular textures into an atlas. 11 // Does not do rotation. 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.00 (2019-02-25) avoid small space waste; gracefully fail too-wide rectangles 45 // 0.99 (2019-02-07) warning fixes 46 // 0.11 (2017-03-03) return packing success/fail result 47 // 0.10 (2016-10-25) remove cast-away-const to avoid warnings 48 // 0.09 (2016-08-27) fix compiler warnings 49 // 0.08 (2015-09-13) really fix bug with empty rects (w=0 or h=0) 50 // 0.07 (2015-09-13) fix bug with empty rects (w=0 or h=0) 51 // 0.06 (2015-04-15) added STBRP_SORT to allow replacing qsort 52 // 0.05: added STBRP_ASSERT to allow replacing assert 53 // 0.04: fixed minor bug in STBRP_LARGE_RECTS support 54 // 0.01: initial release 55 // 56 // LICENSE 57 // 58 // See end of file for license information. 59 60 ////////////////////////////////////////////////////////////////////////////// 61 // 62 // INCLUDE SECTION 63 // 64 65 #ifndef STB_INCLUDE_STB_RECT_PACK_H 66 #define STB_INCLUDE_STB_RECT_PACK_H 67 68 #define STB_RECT_PACK_VERSION 1 69 70 #ifdef STBRP_STATIC 71 #define STBRP_DEF static 72 #else 73 #define STBRP_DEF extern 74 #endif 75 76 #ifdef __cplusplus 77 extern "C" { 78 #endif 79 80 typedef struct stbrp_context stbrp_context; 81 typedef struct stbrp_node stbrp_node; 82 typedef struct stbrp_rect stbrp_rect; 83 84 #ifdef STBRP_LARGE_RECTS 85 typedef int stbrp_coord; 86 #else 87 typedef unsigned short stbrp_coord; 88 #endif 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 // [DEAR IMGUI] Added STBRP__CDECL 217 #ifdef _MSC_VER 218 #define STBRP__NOTUSED(v) (void)(v) 219 #define STBRP__CDECL __cdecl 220 #else 221 #define STBRP__NOTUSED(v) (void)sizeof(v) 222 #define STBRP__CDECL 223 #endif 224 225 enum 226 { 227 STBRP__INIT_skyline = 1 228 }; 229 230 STBRP_DEF void stbrp_setup_heuristic(stbrp_context *context, int heuristic) 231 { 232 switch (context->init_mode) { 233 case STBRP__INIT_skyline: 234 STBRP_ASSERT(heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight || heuristic == STBRP_HEURISTIC_Skyline_BF_sortHeight); 235 context->heuristic = heuristic; 236 break; 237 default: 238 STBRP_ASSERT(0); 239 } 240 } 241 242 STBRP_DEF void stbrp_setup_allow_out_of_mem(stbrp_context *context, int allow_out_of_mem) 243 { 244 if (allow_out_of_mem) 245 // if it's ok to run out of memory, then don't bother aligning them; 246 // this gives better packing, but may fail due to OOM (even though 247 // the rectangles easily fit). @TODO a smarter approach would be to only 248 // quantize once we've hit OOM, then we could get rid of this parameter. 249 context->align = 1; 250 else { 251 // if it's not ok to run out of memory, then quantize the widths 252 // so that num_nodes is always enough nodes. 253 // 254 // I.e. num_nodes * align >= width 255 // align >= width / num_nodes 256 // align = ceil(width/num_nodes) 257 258 context->align = (context->width + context->num_nodes-1) / context->num_nodes; 259 } 260 } 261 262 STBRP_DEF void stbrp_init_target(stbrp_context *context, int width, int height, stbrp_node *nodes, int num_nodes) 263 { 264 int i; 265 #ifndef STBRP_LARGE_RECTS 266 STBRP_ASSERT(width <= 0xffff && height <= 0xffff); 267 #endif 268 269 for (i=0; i < num_nodes-1; ++i) 270 nodes[i].next = &nodes[i+1]; 271 nodes[i].next = NULL; 272 context->init_mode = STBRP__INIT_skyline; 273 context->heuristic = STBRP_HEURISTIC_Skyline_default; 274 context->free_head = &nodes[0]; 275 context->active_head = &context->extra[0]; 276 context->width = width; 277 context->height = height; 278 context->num_nodes = num_nodes; 279 stbrp_setup_allow_out_of_mem(context, 0); 280 281 // node 0 is the full width, node 1 is the sentinel (lets us not store width explicitly) 282 context->extra[0].x = 0; 283 context->extra[0].y = 0; 284 context->extra[0].next = &context->extra[1]; 285 context->extra[1].x = (stbrp_coord) width; 286 #ifdef STBRP_LARGE_RECTS 287 context->extra[1].y = (1<<30); 288 #else 289 context->extra[1].y = 65535; 290 #endif 291 context->extra[1].next = NULL; 292 } 293 294 // find minimum y position if it starts at x1 295 static int stbrp__skyline_find_min_y(stbrp_context *c, stbrp_node *first, int x0, int width, int *pwaste) 296 { 297 stbrp_node *node = first; 298 int x1 = x0 + width; 299 int min_y, visited_width, waste_area; 300 301 STBRP__NOTUSED(c); 302 303 STBRP_ASSERT(first->x <= x0); 304 305 #if 0 306 // skip in case we're past the node 307 while (node->next->x <= x0) 308 ++node; 309 #else 310 STBRP_ASSERT(node->next->x > x0); // we ended up handling this in the caller for efficiency 311 #endif 312 313 STBRP_ASSERT(node->x <= x0); 314 315 min_y = 0; 316 waste_area = 0; 317 visited_width = 0; 318 while (node->x < x1) { 319 if (node->y > min_y) { 320 // raise min_y higher. 321 // we've accounted for all waste up to min_y, 322 // but we'll now add more waste for everything we've visted 323 waste_area += visited_width * (node->y - min_y); 324 min_y = node->y; 325 // the first time through, visited_width might be reduced 326 if (node->x < x0) 327 visited_width += node->next->x - x0; 328 else 329 visited_width += node->next->x - node->x; 330 } else { 331 // add waste area 332 int under_width = node->next->x - node->x; 333 if (under_width + visited_width > width) 334 under_width = width - visited_width; 335 waste_area += under_width * (min_y - node->y); 336 visited_width += under_width; 337 } 338 node = node->next; 339 } 340 341 *pwaste = waste_area; 342 return min_y; 343 } 344 345 typedef struct 346 { 347 int x,y; 348 stbrp_node **prev_link; 349 } stbrp__findresult; 350 351 static stbrp__findresult stbrp__skyline_find_best_pos(stbrp_context *c, int width, int height) 352 { 353 int best_waste = (1<<30), best_x, best_y = (1 << 30); 354 stbrp__findresult fr; 355 stbrp_node **prev, *node, *tail, **best = NULL; 356 357 // align to multiple of c->align 358 width = (width + c->align - 1); 359 width -= width % c->align; 360 STBRP_ASSERT(width % c->align == 0); 361 362 // if it can't possibly fit, bail immediately 363 if (width > c->width || height > c->height) { 364 fr.prev_link = NULL; 365 fr.x = fr.y = 0; 366 return fr; 367 } 368 369 node = c->active_head; 370 prev = &c->active_head; 371 while (node->x + width <= c->width) { 372 int y,waste; 373 y = stbrp__skyline_find_min_y(c, node, node->x, width, &waste); 374 if (c->heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight) { // actually just want to test BL 375 // bottom left 376 if (y < best_y) { 377 best_y = y; 378 best = prev; 379 } 380 } else { 381 // best-fit 382 if (y + height <= c->height) { 383 // can only use it if it first vertically 384 if (y < best_y || (y == best_y && waste < best_waste)) { 385 best_y = y; 386 best_waste = waste; 387 best = prev; 388 } 389 } 390 } 391 prev = &node->next; 392 node = node->next; 393 } 394 395 best_x = (best == NULL) ? 0 : (*best)->x; 396 397 // if doing best-fit (BF), we also have to try aligning right edge to each node position 398 // 399 // e.g, if fitting 400 // 401 // ____________________ 402 // |____________________| 403 // 404 // into 405 // 406 // | | 407 // | ____________| 408 // |____________| 409 // 410 // then right-aligned reduces waste, but bottom-left BL is always chooses left-aligned 411 // 412 // This makes BF take about 2x the time 413 414 if (c->heuristic == STBRP_HEURISTIC_Skyline_BF_sortHeight) { 415 tail = c->active_head; 416 node = c->active_head; 417 prev = &c->active_head; 418 // find first node that's admissible 419 while (tail->x < width) 420 tail = tail->next; 421 while (tail) { 422 int xpos = tail->x - width; 423 int y,waste; 424 STBRP_ASSERT(xpos >= 0); 425 // find the left position that matches this 426 while (node->next->x <= xpos) { 427 prev = &node->next; 428 node = node->next; 429 } 430 STBRP_ASSERT(node->next->x > xpos && node->x <= xpos); 431 y = stbrp__skyline_find_min_y(c, node, xpos, width, &waste); 432 if (y + height <= c->height) { 433 if (y <= best_y) { 434 if (y < best_y || waste < best_waste || (waste==best_waste && xpos < best_x)) { 435 best_x = xpos; 436 STBRP_ASSERT(y <= best_y); 437 best_y = y; 438 best_waste = waste; 439 best = prev; 440 } 441 } 442 } 443 tail = tail->next; 444 } 445 } 446 447 fr.prev_link = best; 448 fr.x = best_x; 449 fr.y = best_y; 450 return fr; 451 } 452 453 static stbrp__findresult stbrp__skyline_pack_rectangle(stbrp_context *context, int width, int height) 454 { 455 // find best position according to heuristic 456 stbrp__findresult res = stbrp__skyline_find_best_pos(context, width, height); 457 stbrp_node *node, *cur; 458 459 // bail if: 460 // 1. it failed 461 // 2. the best node doesn't fit (we don't always check this) 462 // 3. we're out of memory 463 if (res.prev_link == NULL || res.y + height > context->height || context->free_head == NULL) { 464 res.prev_link = NULL; 465 return res; 466 } 467 468 // on success, create new node 469 node = context->free_head; 470 node->x = (stbrp_coord) res.x; 471 node->y = (stbrp_coord) (res.y + height); 472 473 context->free_head = node->next; 474 475 // insert the new node into the right starting point, and 476 // let 'cur' point to the remaining nodes needing to be 477 // stiched back in 478 479 cur = *res.prev_link; 480 if (cur->x < res.x) { 481 // preserve the existing one, so start testing with the next one 482 stbrp_node *next = cur->next; 483 cur->next = node; 484 cur = next; 485 } else { 486 *res.prev_link = node; 487 } 488 489 // from here, traverse cur and free the nodes, until we get to one 490 // that shouldn't be freed 491 while (cur->next && cur->next->x <= res.x + width) { 492 stbrp_node *next = cur->next; 493 // move the current node to the free list 494 cur->next = context->free_head; 495 context->free_head = cur; 496 cur = next; 497 } 498 499 // stitch the list back in 500 node->next = cur; 501 502 if (cur->x < res.x + width) 503 cur->x = (stbrp_coord) (res.x + width); 504 505 #ifdef _DEBUG 506 cur = context->active_head; 507 while (cur->x < context->width) { 508 STBRP_ASSERT(cur->x < cur->next->x); 509 cur = cur->next; 510 } 511 STBRP_ASSERT(cur->next == NULL); 512 513 { 514 int count=0; 515 cur = context->active_head; 516 while (cur) { 517 cur = cur->next; 518 ++count; 519 } 520 cur = context->free_head; 521 while (cur) { 522 cur = cur->next; 523 ++count; 524 } 525 STBRP_ASSERT(count == context->num_nodes+2); 526 } 527 #endif 528 529 return res; 530 } 531 532 // [DEAR IMGUI] Added STBRP__CDECL 533 static int STBRP__CDECL rect_height_compare(const void *a, const void *b) 534 { 535 const stbrp_rect *p = (const stbrp_rect *) a; 536 const stbrp_rect *q = (const stbrp_rect *) b; 537 if (p->h > q->h) 538 return -1; 539 if (p->h < q->h) 540 return 1; 541 return (p->w > q->w) ? -1 : (p->w < q->w); 542 } 543 544 // [DEAR IMGUI] Added STBRP__CDECL 545 static int STBRP__CDECL rect_original_order(const void *a, const void *b) 546 { 547 const stbrp_rect *p = (const stbrp_rect *) a; 548 const stbrp_rect *q = (const stbrp_rect *) b; 549 return (p->was_packed < q->was_packed) ? -1 : (p->was_packed > q->was_packed); 550 } 551 552 #ifdef STBRP_LARGE_RECTS 553 #define STBRP__MAXVAL 0xffffffff 554 #else 555 #define STBRP__MAXVAL 0xffff 556 #endif 557 558 STBRP_DEF int stbrp_pack_rects(stbrp_context *context, stbrp_rect *rects, int num_rects) 559 { 560 int i, all_rects_packed = 1; 561 562 // we use the 'was_packed' field internally to allow sorting/unsorting 563 for (i=0; i < num_rects; ++i) { 564 rects[i].was_packed = i; 565 } 566 567 // sort according to heuristic 568 STBRP_SORT(rects, num_rects, sizeof(rects[0]), rect_height_compare); 569 570 for (i=0; i < num_rects; ++i) { 571 if (rects[i].w == 0 || rects[i].h == 0) { 572 rects[i].x = rects[i].y = 0; // empty rect needs no space 573 } else { 574 stbrp__findresult fr = stbrp__skyline_pack_rectangle(context, rects[i].w, rects[i].h); 575 if (fr.prev_link) { 576 rects[i].x = (stbrp_coord) fr.x; 577 rects[i].y = (stbrp_coord) fr.y; 578 } else { 579 rects[i].x = rects[i].y = STBRP__MAXVAL; 580 } 581 } 582 } 583 584 // unsort 585 STBRP_SORT(rects, num_rects, sizeof(rects[0]), rect_original_order); 586 587 // set was_packed flags and all_rects_packed status 588 for (i=0; i < num_rects; ++i) { 589 rects[i].was_packed = !(rects[i].x == STBRP__MAXVAL && rects[i].y == STBRP__MAXVAL); 590 if (!rects[i].was_packed) 591 all_rects_packed = 0; 592 } 593 594 // return the all_rects_packed status 595 return all_rects_packed; 596 } 597 #endif 598 599 /* 600 ------------------------------------------------------------------------------ 601 This software is available under 2 licenses -- choose whichever you prefer. 602 ------------------------------------------------------------------------------ 603 ALTERNATIVE A - MIT License 604 Copyright (c) 2017 Sean Barrett 605 Permission is hereby granted, free of charge, to any person obtaining a copy of 606 this software and associated documentation files (the "Software"), to deal in 607 the Software without restriction, including without limitation the rights to 608 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 609 of the Software, and to permit persons to whom the Software is furnished to do 610 so, subject to the following conditions: 611 The above copyright notice and this permission notice shall be included in all 612 copies or substantial portions of the Software. 613 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 614 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 615 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 616 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 617 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 618 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 619 SOFTWARE. 620 ------------------------------------------------------------------------------ 621 ALTERNATIVE B - Public Domain (www.unlicense.org) 622 This is free and unencumbered software released into the public domain. 623 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this 624 software, either in source code form or as a compiled binary, for any purpose, 625 commercial or non-commercial, and by any means. 626 In jurisdictions that recognize copyright laws, the author or authors of this 627 software dedicate any and all copyright interest in the software to the public 628 domain. We make this dedication for the benefit of the public at large and to 629 the detriment of our heirs and successors. We intend this dedication to be an 630 overt act of relinquishment in perpetuity of all present and future rights to 631 this software under copyright law. 632 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 633 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 634 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 635 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 636 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 637 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 638 ------------------------------------------------------------------------------ 639 */