Changeset e66fd66 in opengl-game for IMGUI/imstb_rectpack.h
- Timestamp:
- Dec 5, 2020, 7:14:31 PM (4 years ago)
- Branches:
- feature/imgui-sdl, master
- Children:
- 95c657f
- Parents:
- 78c3045
- File:
-
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
IMGUI/imstb_rectpack.h
r78c3045 re66fd66 1 // stb_rect_pack.h - v0.11 - public domain - rectangle packing 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 2 8 // Sean Barrett 2014 3 9 // … … 32 38 // Bugfixes / warning fixes 33 39 // Jeremy Jaussaud 40 // Fabian Giesen 34 41 // 35 42 // Version history: 36 43 // 44 // 1.00 (2019-02-25) avoid small space waste; gracefully fail too-wide rectangles 45 // 0.99 (2019-02-07) warning fixes 37 46 // 0.11 (2017-03-03) return packing success/fail result 38 47 // 0.10 (2016-10-25) remove cast-away-const to avoid warnings … … 69 78 #endif 70 79 71 72 73 80 typedef struct stbrp_context stbrp_context; 81 typedef struct stbrp_node stbrp_node; 82 typedef struct stbrp_rect stbrp_rect; 74 83 75 84 #ifdef STBRP_LARGE_RECTS 76 85 typedef int stbrp_coord; 77 86 #else 78 79 #endif 80 81 STBRP_DEF int stbrp_pack_rects(stbrp_context *context, stbrp_rect *rects, int num_rects);82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 STBRP_DEF void stbrp_init_target(stbrp_context *context, int width, int height, stbrp_node *nodes, int num_nodes);122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 STBRP_DEF void stbrp_setup_allow_out_of_mem(stbrp_context *context, int allow_out_of_mem);143 144 145 146 147 148 STBRP_DEF void stbrp_setup_heuristic(stbrp_context *context, int heuristic);149 150 151 152 153 154 155 STBRP_HEURISTIC_Skyline_default =0,156 157 158 159 160 161 162 163 164 165 166 167 168 stbrp_coord x,y;169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 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 }; 184 193 185 194 #ifdef __cplusplus … … 205 214 #endif 206 215 216 // [DEAR IMGUI] Added STBRP__CDECL 207 217 #ifdef _MSC_VER 208 218 #define STBRP__NOTUSED(v) (void)(v) … … 221 231 { 222 232 switch (context->init_mode) { 223 case STBRP__INIT_skyline:224 STBRP_ASSERT(heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight || heuristic == STBRP_HEURISTIC_Skyline_BF_sortHeight);225 context->heuristic = heuristic;226 break;227 default:228 STBRP_ASSERT(0);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); 229 239 } 230 240 } … … 246 256 // align = ceil(width/num_nodes) 247 257 248 context->align = (context->width + context->num_nodes -1) / context->num_nodes;258 context->align = (context->width + context->num_nodes-1) / context->num_nodes; 249 259 } 250 260 } … … 257 267 #endif 258 268 259 for (i = 0; i < num_nodes -1; ++i)260 nodes[i].next = &nodes[i +1];269 for (i=0; i < num_nodes-1; ++i) 270 nodes[i].next = &nodes[i+1]; 261 271 nodes[i].next = NULL; 262 272 context->init_mode = STBRP__INIT_skyline; … … 273 283 context->extra[0].y = 0; 274 284 context->extra[0].next = &context->extra[1]; 275 context->extra[1].x = (stbrp_coord) width;285 context->extra[1].x = (stbrp_coord) width; 276 286 #ifdef STBRP_LARGE_RECTS 277 context->extra[1].y = (1 <<30);287 context->extra[1].y = (1<<30); 278 288 #else 279 289 context->extra[1].y = 65535; … … 293 303 STBRP_ASSERT(first->x <= x0); 294 304 295 #if 0305 #if 0 296 306 // skip in case we're past the node 297 307 while (node->next->x <= x0) 298 308 ++node; 299 #else309 #else 300 310 STBRP_ASSERT(node->next->x > x0); // we ended up handling this in the caller for efficiency 301 #endif311 #endif 302 312 303 313 STBRP_ASSERT(node->x <= x0); … … 318 328 else 319 329 visited_width += node->next->x - node->x; 320 } 321 else { 330 } else { 322 331 // add waste area 323 332 int under_width = node->next->x - node->x; … … 336 345 typedef struct 337 346 { 338 int x, 347 int x,y; 339 348 stbrp_node **prev_link; 340 349 } stbrp__findresult; … … 342 351 static stbrp__findresult stbrp__skyline_find_best_pos(stbrp_context *c, int width, int height) 343 352 { 344 int best_waste = (1 <<30), best_x, best_y = (1 << 30);353 int best_waste = (1<<30), best_x, best_y = (1 << 30); 345 354 stbrp__findresult fr; 346 355 stbrp_node **prev, *node, *tail, **best = NULL; … … 351 360 STBRP_ASSERT(width % c->align == 0); 352 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 353 369 node = c->active_head; 354 370 prev = &c->active_head; 355 371 while (node->x + width <= c->width) { 356 int y, 372 int y,waste; 357 373 y = stbrp__skyline_find_min_y(c, node, node->x, width, &waste); 358 374 if (c->heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight) { // actually just want to test BL 359 375 // bottom left 360 376 if (y < best_y) { 361 377 best_y = y; 362 378 best = prev; 363 379 } 364 } 365 else { 380 } else { 366 381 // best-fit 367 382 if (y + height <= c->height) { … … 406 421 while (tail) { 407 422 int xpos = tail->x - width; 408 int y, 423 int y,waste; 409 424 STBRP_ASSERT(xpos >= 0); 410 425 // find the left position that matches this … … 415 430 STBRP_ASSERT(node->next->x > xpos && node->x <= xpos); 416 431 y = stbrp__skyline_find_min_y(c, node, xpos, width, &waste); 417 if (y + height < c->height) {432 if (y + height <= c->height) { 418 433 if (y <= best_y) { 419 if (y < best_y || waste < best_waste || (waste ==best_waste && xpos < best_x)) {434 if (y < best_y || waste < best_waste || (waste==best_waste && xpos < best_x)) { 420 435 best_x = xpos; 421 436 STBRP_ASSERT(y <= best_y); … … 427 442 } 428 443 tail = tail->next; 429 } 444 } 430 445 } 431 446 … … 453 468 // on success, create new node 454 469 node = context->free_head; 455 node->x = (stbrp_coord) res.x;456 node->y = (stbrp_coord) (res.y + height);470 node->x = (stbrp_coord) res.x; 471 node->y = (stbrp_coord) (res.y + height); 457 472 458 473 context->free_head = node->next; … … 468 483 cur->next = node; 469 484 cur = next; 470 } 471 else { 485 } else { 472 486 *res.prev_link = node; 473 487 } … … 487 501 488 502 if (cur->x < res.x + width) 489 cur->x = (stbrp_coord) (res.x + width);503 cur->x = (stbrp_coord) (res.x + width); 490 504 491 505 #ifdef _DEBUG … … 498 512 499 513 { 500 int count =0;514 int count=0; 501 515 cur = context->active_head; 502 516 while (cur) { … … 509 523 ++count; 510 524 } 511 STBRP_ASSERT(count == context->num_nodes +2);525 STBRP_ASSERT(count == context->num_nodes+2); 512 526 } 513 527 #endif … … 516 530 } 517 531 532 // [DEAR IMGUI] Added STBRP__CDECL 518 533 static int STBRP__CDECL rect_height_compare(const void *a, const void *b) 519 534 { 520 const stbrp_rect *p = (const stbrp_rect *) a;521 const stbrp_rect *q = (const stbrp_rect *) b;535 const stbrp_rect *p = (const stbrp_rect *) a; 536 const stbrp_rect *q = (const stbrp_rect *) b; 522 537 if (p->h > q->h) 523 538 return -1; … … 527 542 } 528 543 544 // [DEAR IMGUI] Added STBRP__CDECL 529 545 static int STBRP__CDECL rect_original_order(const void *a, const void *b) 530 546 { 531 const stbrp_rect *p = (const stbrp_rect *) a;532 const stbrp_rect *q = (const stbrp_rect *) b;547 const stbrp_rect *p = (const stbrp_rect *) a; 548 const stbrp_rect *q = (const stbrp_rect *) b; 533 549 return (p->was_packed < q->was_packed) ? -1 : (p->was_packed > q->was_packed); 534 550 } … … 545 561 546 562 // we use the 'was_packed' field internally to allow sorting/unsorting 547 for (i =0; i < num_rects; ++i) {563 for (i=0; i < num_rects; ++i) { 548 564 rects[i].was_packed = i; 549 #ifndef STBRP_LARGE_RECTS550 STBRP_ASSERT(rects[i].w <= 0xffff && rects[i].h <= 0xffff);551 #endif552 565 } 553 566 … … 555 568 STBRP_SORT(rects, num_rects, sizeof(rects[0]), rect_height_compare); 556 569 557 for (i =0; i < num_rects; ++i) {570 for (i=0; i < num_rects; ++i) { 558 571 if (rects[i].w == 0 || rects[i].h == 0) { 559 572 rects[i].x = rects[i].y = 0; // empty rect needs no space 560 } 561 else { 573 } else { 562 574 stbrp__findresult fr = stbrp__skyline_pack_rectangle(context, rects[i].w, rects[i].h); 563 575 if (fr.prev_link) { 564 rects[i].x = (stbrp_coord)fr.x; 565 rects[i].y = (stbrp_coord)fr.y; 566 } 567 else { 576 rects[i].x = (stbrp_coord) fr.x; 577 rects[i].y = (stbrp_coord) fr.y; 578 } else { 568 579 rects[i].x = rects[i].y = STBRP__MAXVAL; 569 580 } … … 575 586 576 587 // set was_packed flags and all_rects_packed status 577 for (i =0; i < num_rects; ++i) {588 for (i=0; i < num_rects; ++i) { 578 589 rects[i].was_packed = !(rects[i].x == STBRP__MAXVAL && rects[i].y == STBRP__MAXVAL); 579 590 if (!rects[i].was_packed) … … 592 603 ALTERNATIVE A - MIT License 593 604 Copyright (c) 2017 Sean Barrett 594 Permission is hereby granted, free of charge, to any person obtaining a copy of 595 this software and associated documentation files (the "Software"), to deal in 596 the Software without restriction, including without limitation the rights to 597 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 598 of the Software, and to permit persons to whom the Software is furnished to do 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 599 610 so, subject to the following conditions: 600 The above copyright notice and this permission notice shall be included in all 611 The above copyright notice and this permission notice shall be included in all 601 612 copies or substantial portions of the Software. 602 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 603 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 604 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 605 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 606 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 607 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 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 608 619 SOFTWARE. 609 620 ------------------------------------------------------------------------------ 610 621 ALTERNATIVE B - Public Domain (www.unlicense.org) 611 622 This is free and unencumbered software released into the public domain. 612 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this 613 software, either in source code form or as a compiled binary, for any purpose, 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, 614 625 commercial or non-commercial, and by any means. 615 In jurisdictions that recognize copyright laws, the author or authors of this 616 software dedicate any and all copyright interest in the software to the public 617 domain. We make this dedication for the benefit of the public at large and to 618 the detriment of our heirs and successors. We intend this dedication to be an 619 overt act of relinquishment in perpetuity of all present and future rights to 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 620 631 this software under copyright law. 621 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 622 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 623 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 624 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 625 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 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 626 637 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 627 638 ------------------------------------------------------------------------------
Note:
See TracChangeset
for help on using the changeset viewer.