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

source code of qt3d/src/3rdparty/imgui/imstb_rectpack.h