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