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.
7 // stb_rect_pack.h - v0.99 - public domain - rectangle packing
10 // Useful for e.g. packing rectangular textures into an atlas.
11 // Does not do rotation.
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).
17 // Has only had a few tests run, may have issues.
21 // No memory allocations; uses qsort() and assert() from stdlib.
22 // Can override those by defining STBRP_SORT and STBRP_ASSERT.
24 // This library currently uses the Skyline Bottom-Left algorithm.
26 // Please note: better rectangle packers are welcome! Please
27 // implement them to the same API, but with a different init
36 // github:IntellectualKitty
38 // Bugfixes / warning fixes
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
56 // See end of file for license information.
58 //////////////////////////////////////////////////////////////////////////////
63 #ifndef STB_INCLUDE_STB_RECT_PACK_H
64 #define STB_INCLUDE_STB_RECT_PACK_H
66 #define STB_RECT_PACK_VERSION 1
69 #define STBRP_DEF static
71 #define STBRP_DEF extern
78 typedef struct stbrp_context stbrp_context
;
79 typedef struct stbrp_node stbrp_node
;
80 typedef struct stbrp_rect stbrp_rect
;
82 #ifdef STBRP_LARGE_RECTS
83 typedef int stbrp_coord
;
85 typedef unsigned short stbrp_coord
;
88 STBRP_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.
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.
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.
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
110 // The function returns 1 if all of the rectangles were successfully
111 // packed and 0 otherwise.
115 // reserved for your use:
123 int was_packed
; // non-zero if valid packing
125 }; // 16 bytes, nominally
128 STBRP_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
133 // You must call this function every time you start packing into a new target.
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.
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'
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.
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.
149 STBRP_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).
155 STBRP_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.
162 STBRP_HEURISTIC_Skyline_default
=0,
163 STBRP_HEURISTIC_Skyline_BL_sortHeight
= STBRP_HEURISTIC_Skyline_default
,
164 STBRP_HEURISTIC_Skyline_BF_sortHeight
168 //////////////////////////////////////////////////////////////////////////////
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
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'
198 //////////////////////////////////////////////////////////////////////////////
200 // IMPLEMENTATION SECTION
203 #ifdef STB_RECT_PACK_IMPLEMENTATION
206 #define STBRP_SORT qsort
211 #define STBRP_ASSERT assert
214 // [DEAR IMGUI] Added STBRP__CDECL
216 #define STBRP__NOTUSED(v) (void)(v)
217 #define STBRP__CDECL __cdecl
219 #define STBRP__NOTUSED(v) (void)sizeof(v)
225 STBRP__INIT_skyline
= 1
228 STBRP_DEF
void stbrp_setup_heuristic(stbrp_context
*context
, int heuristic
)
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
;
240 STBRP_DEF
void stbrp_setup_allow_out_of_mem(stbrp_context
*context
, int allow_out_of_mem
)
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.
249 // if it's not ok to run out of memory, then quantize the widths
250 // so that num_nodes is always enough nodes.
252 // I.e. num_nodes * align >= width
253 // align >= width / num_nodes
254 // align = ceil(width/num_nodes)
256 context
->align
= (context
->width
+ context
->num_nodes
-1) / context
->num_nodes
;
260 STBRP_DEF
void stbrp_init_target(stbrp_context
*context
, int width
, int height
, stbrp_node
*nodes
, int num_nodes
)
263 #ifndef STBRP_LARGE_RECTS
264 STBRP_ASSERT(width
<= 0xffff && height
<= 0xffff);
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);
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);
287 context
->extra
[1].y
= 65535;
289 context
->extra
[1].next
= NULL
;
292 // find minimum y position if it starts at x1
293 static int stbrp__skyline_find_min_y(stbrp_context
*c
, stbrp_node
*first
, int x0
, int width
, int *pwaste
)
295 stbrp_node
*node
= first
;
297 int min_y
, visited_width
, waste_area
;
301 STBRP_ASSERT(first
->x
<= x0
);
304 // skip in case we're past the node
305 while (node
->next
->x
<= x0
)
308 STBRP_ASSERT(node
->next
->x
> x0
); // we ended up handling this in the caller for efficiency
311 STBRP_ASSERT(node
->x
<= x0
);
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
);
323 // the first time through, visited_width might be reduced
325 visited_width
+= node
->next
->x
- x0
;
327 visited_width
+= node
->next
->x
- node
->x
;
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
;
339 *pwaste
= waste_area
;
346 stbrp_node
**prev_link
;
349 static stbrp__findresult
stbrp__skyline_find_best_pos(stbrp_context
*c
, int width
, int height
)
351 int best_waste
= (1<<30), best_x
, best_y
= (1 << 30);
352 stbrp__findresult fr
;
353 stbrp_node
**prev
, *node
, *tail
, **best
= NULL
;
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);
360 node
= c
->active_head
;
361 prev
= &c
->active_head
;
362 while (node
->x
+ width
<= c
->width
) {
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
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
)) {
386 best_x
= (best
== NULL
) ? 0 : (*best
)->x
;
388 // if doing best-fit (BF), we also have to try aligning right edge to each node position
392 // ____________________
393 // |____________________|
401 // then right-aligned reduces waste, but bottom-left BL is always chooses left-aligned
403 // This makes BF take about 2x the time
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
)
413 int xpos
= tail
->x
- width
;
415 STBRP_ASSERT(xpos
>= 0);
416 // find the left position that matches this
417 while (node
->next
->x
<= xpos
) {
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
) {
425 if (y
< best_y
|| waste
< best_waste
|| (waste
==best_waste
&& xpos
< best_x
)) {
427 STBRP_ASSERT(y
<= best_y
);
444 static stbrp__findresult
stbrp__skyline_pack_rectangle(stbrp_context
*context
, int width
, int height
)
446 // find best position according to heuristic
447 stbrp__findresult res
= stbrp__skyline_find_best_pos(context
, width
, height
);
448 stbrp_node
*node
, *cur
;
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
;
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
);
464 context
->free_head
= node
->next
;
466 // insert the new node into the right starting point, and
467 // let 'cur' point to the remaining nodes needing to be
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
;
477 *res
.prev_link
= node
;
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
;
490 // stitch the list back in
493 if (cur
->x
< res
.x
+ width
)
494 cur
->x
= (stbrp_coord
) (res
.x
+ width
);
497 cur
= context
->active_head
;
498 while (cur
->x
< context
->width
) {
499 STBRP_ASSERT(cur
->x
< cur
->next
->x
);
502 STBRP_ASSERT(cur
->next
== NULL
);
506 cur
= context
->active_head
;
511 cur
= context
->free_head
;
516 STBRP_ASSERT(count
== context
->num_nodes
+2);
523 // [DEAR IMGUI] Added STBRP__CDECL
524 static int STBRP__CDECL
rect_height_compare(const void *a
, const void *b
)
526 const stbrp_rect
*p
= (const stbrp_rect
*) a
;
527 const stbrp_rect
*q
= (const stbrp_rect
*) b
;
532 return (p
->w
> q
->w
) ? -1 : (p
->w
< q
->w
);
535 // [DEAR IMGUI] Added STBRP__CDECL
536 static int STBRP__CDECL
rect_original_order(const void *a
, const void *b
)
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
);
543 #ifdef STBRP_LARGE_RECTS
544 #define STBRP__MAXVAL 0xffffffff
546 #define STBRP__MAXVAL 0xffff
549 STBRP_DEF
int stbrp_pack_rects(stbrp_context
*context
, stbrp_rect
*rects
, int num_rects
)
551 int i
, all_rects_packed
= 1;
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
;
558 // sort according to heuristic
559 STBRP_SORT(rects
, num_rects
, sizeof(rects
[0]), rect_height_compare
);
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
565 stbrp__findresult fr
= stbrp__skyline_pack_rectangle(context
, rects
[i
].w
, rects
[i
].h
);
567 rects
[i
].x
= (stbrp_coord
) fr
.x
;
568 rects
[i
].y
= (stbrp_coord
) fr
.y
;
570 rects
[i
].x
= rects
[i
].y
= STBRP__MAXVAL
;
576 STBRP_SORT(rects
, num_rects
, sizeof(rects
[0]), rect_original_order
);
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;
585 // return the all_rects_packed status
586 return all_rects_packed
;
591 ------------------------------------------------------------------------------
592 This software is available under 2 licenses -- choose whichever you prefer.
593 ------------------------------------------------------------------------------
594 ALTERNATIVE A - MIT License
595 Copyright (c) 2017 Sean Barrett
596 Permission is hereby granted, free of charge, to any person obtaining a copy of
597 this software and associated documentation files (the "Software"), to deal in
598 the Software without restriction, including without limitation the rights to
599 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
600 of the Software, and to permit persons to whom the Software is furnished to do
601 so, subject to the following conditions:
602 The above copyright notice and this permission notice shall be included in all
603 copies or substantial portions of the Software.
604 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
605 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
606 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
607 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
608 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
609 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
611 ------------------------------------------------------------------------------
612 ALTERNATIVE B - Public Domain (www.unlicense.org)
613 This is free and unencumbered software released into the public domain.
614 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
615 software, either in source code form or as a compiled binary, for any purpose,
616 commercial or non-commercial, and by any means.
617 In jurisdictions that recognize copyright laws, the author or authors of this
618 software dedicate any and all copyright interest in the software to the public
619 domain. We make this dedication for the benefit of the public at large and to
620 the detriment of our heirs and successors. We intend this dedication to be an
621 overt act of relinquishment in perpetuity of all present and future rights to
622 this software under copyright law.
623 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
624 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
625 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
626 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
627 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
628 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
629 ------------------------------------------------------------------------------