source: opengl-game/IMGUI/stb_rect_pack.h@ cf727ca

feature/imgui-sdl points-test
Last change on this file since cf727ca was c58ebc3, checked in by Dmitry Portnoy <dmp1488@…>, 7 years ago

Create an IMGUI folder for the imgui library files.

  • Property mode set to 100644
File size: 19.9 KB
RevLine 
[4e0b82b]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
71 typedef struct stbrp_context stbrp_context;
72 typedef struct stbrp_node stbrp_node;
73 typedef struct stbrp_rect stbrp_rect;
74
75#ifdef STBRP_LARGE_RECTS
76 typedef int stbrp_coord;
77#else
78 typedef unsigned short stbrp_coord;
79#endif
80
81 STBRP_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
106 struct 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
121 STBRP_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
142 STBRP_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
148 STBRP_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
153 enum
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
166 struct stbrp_node
167 {
168 stbrp_coord x, y;
169 stbrp_node *next;
170 };
171
172 struct 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, 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 }
321 else {
322 // add waste area
323 int under_width = node->next->x - node->x;
324 if (under_width + visited_width > width)
325 under_width = width - visited_width;
326 waste_area += under_width * (min_y - node->y);
327 visited_width += under_width;
328 }
329 node = node->next;
330 }
331
332 *pwaste = waste_area;
333 return min_y;
334}
335
336typedef struct
337{
338 int x, y;
339 stbrp_node **prev_link;
340} stbrp__findresult;
341
342static stbrp__findresult stbrp__skyline_find_best_pos(stbrp_context *c, int width, int height)
343{
344 int best_waste = (1 << 30), best_x, best_y = (1 << 30);
345 stbrp__findresult fr;
346 stbrp_node **prev, *node, *tail, **best = NULL;
347
348 // align to multiple of c->align
349 width = (width + c->align - 1);
350 width -= width % c->align;
351 STBRP_ASSERT(width % c->align == 0);
352
353 node = c->active_head;
354 prev = &c->active_head;
355 while (node->x + width <= c->width) {
356 int y, waste;
357 y = stbrp__skyline_find_min_y(c, node, node->x, width, &waste);
358 if (c->heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight) { // actually just want to test BL
359 // bottom left
360 if (y < best_y) {
361 best_y = y;
362 best = prev;
363 }
364 }
365 else {
366 // best-fit
367 if (y + height <= c->height) {
368 // can only use it if it first vertically
369 if (y < best_y || (y == best_y && waste < best_waste)) {
370 best_y = y;
371 best_waste = waste;
372 best = prev;
373 }
374 }
375 }
376 prev = &node->next;
377 node = node->next;
378 }
379
380 best_x = (best == NULL) ? 0 : (*best)->x;
381
382 // if doing best-fit (BF), we also have to try aligning right edge to each node position
383 //
384 // e.g, if fitting
385 //
386 // ____________________
387 // |____________________|
388 //
389 // into
390 //
391 // | |
392 // | ____________|
393 // |____________|
394 //
395 // then right-aligned reduces waste, but bottom-left BL is always chooses left-aligned
396 //
397 // This makes BF take about 2x the time
398
399 if (c->heuristic == STBRP_HEURISTIC_Skyline_BF_sortHeight) {
400 tail = c->active_head;
401 node = c->active_head;
402 prev = &c->active_head;
403 // find first node that's admissible
404 while (tail->x < width)
405 tail = tail->next;
406 while (tail) {
407 int xpos = tail->x - width;
408 int y, waste;
409 STBRP_ASSERT(xpos >= 0);
410 // find the left position that matches this
411 while (node->next->x <= xpos) {
412 prev = &node->next;
413 node = node->next;
414 }
415 STBRP_ASSERT(node->next->x > xpos && node->x <= xpos);
416 y = stbrp__skyline_find_min_y(c, node, xpos, width, &waste);
417 if (y + height < c->height) {
418 if (y <= best_y) {
419 if (y < best_y || waste < best_waste || (waste == best_waste && xpos < best_x)) {
420 best_x = xpos;
421 STBRP_ASSERT(y <= best_y);
422 best_y = y;
423 best_waste = waste;
424 best = prev;
425 }
426 }
427 }
428 tail = tail->next;
429 }
430 }
431
432 fr.prev_link = best;
433 fr.x = best_x;
434 fr.y = best_y;
435 return fr;
436}
437
438static stbrp__findresult stbrp__skyline_pack_rectangle(stbrp_context *context, int width, int height)
439{
440 // find best position according to heuristic
441 stbrp__findresult res = stbrp__skyline_find_best_pos(context, width, height);
442 stbrp_node *node, *cur;
443
444 // bail if:
445 // 1. it failed
446 // 2. the best node doesn't fit (we don't always check this)
447 // 3. we're out of memory
448 if (res.prev_link == NULL || res.y + height > context->height || context->free_head == NULL) {
449 res.prev_link = NULL;
450 return res;
451 }
452
453 // on success, create new node
454 node = context->free_head;
455 node->x = (stbrp_coord)res.x;
456 node->y = (stbrp_coord)(res.y + height);
457
458 context->free_head = node->next;
459
460 // insert the new node into the right starting point, and
461 // let 'cur' point to the remaining nodes needing to be
462 // stiched back in
463
464 cur = *res.prev_link;
465 if (cur->x < res.x) {
466 // preserve the existing one, so start testing with the next one
467 stbrp_node *next = cur->next;
468 cur->next = node;
469 cur = next;
470 }
471 else {
472 *res.prev_link = node;
473 }
474
475 // from here, traverse cur and free the nodes, until we get to one
476 // that shouldn't be freed
477 while (cur->next && cur->next->x <= res.x + width) {
478 stbrp_node *next = cur->next;
479 // move the current node to the free list
480 cur->next = context->free_head;
481 context->free_head = cur;
482 cur = next;
483 }
484
485 // stitch the list back in
486 node->next = cur;
487
488 if (cur->x < res.x + width)
489 cur->x = (stbrp_coord)(res.x + width);
490
491#ifdef _DEBUG
492 cur = context->active_head;
493 while (cur->x < context->width) {
494 STBRP_ASSERT(cur->x < cur->next->x);
495 cur = cur->next;
496 }
497 STBRP_ASSERT(cur->next == NULL);
498
499 {
500 int count = 0;
501 cur = context->active_head;
502 while (cur) {
503 cur = cur->next;
504 ++count;
505 }
506 cur = context->free_head;
507 while (cur) {
508 cur = cur->next;
509 ++count;
510 }
511 STBRP_ASSERT(count == context->num_nodes + 2);
512 }
513#endif
514
515 return res;
516}
517
518static int STBRP__CDECL rect_height_compare(const void *a, const void *b)
519{
520 const stbrp_rect *p = (const stbrp_rect *)a;
521 const stbrp_rect *q = (const stbrp_rect *)b;
522 if (p->h > q->h)
523 return -1;
524 if (p->h < q->h)
525 return 1;
526 return (p->w > q->w) ? -1 : (p->w < q->w);
527}
528
529static int STBRP__CDECL rect_original_order(const void *a, const void *b)
530{
531 const stbrp_rect *p = (const stbrp_rect *)a;
532 const stbrp_rect *q = (const stbrp_rect *)b;
533 return (p->was_packed < q->was_packed) ? -1 : (p->was_packed > q->was_packed);
534}
535
536#ifdef STBRP_LARGE_RECTS
537#define STBRP__MAXVAL 0xffffffff
538#else
539#define STBRP__MAXVAL 0xffff
540#endif
541
542STBRP_DEF int stbrp_pack_rects(stbrp_context *context, stbrp_rect *rects, int num_rects)
543{
544 int i, all_rects_packed = 1;
545
546 // we use the 'was_packed' field internally to allow sorting/unsorting
547 for (i = 0; i < num_rects; ++i) {
548 rects[i].was_packed = i;
549#ifndef STBRP_LARGE_RECTS
550 STBRP_ASSERT(rects[i].w <= 0xffff && rects[i].h <= 0xffff);
551#endif
552 }
553
554 // sort according to heuristic
555 STBRP_SORT(rects, num_rects, sizeof(rects[0]), rect_height_compare);
556
557 for (i = 0; i < num_rects; ++i) {
558 if (rects[i].w == 0 || rects[i].h == 0) {
559 rects[i].x = rects[i].y = 0; // empty rect needs no space
560 }
561 else {
562 stbrp__findresult fr = stbrp__skyline_pack_rectangle(context, rects[i].w, rects[i].h);
563 if (fr.prev_link) {
564 rects[i].x = (stbrp_coord)fr.x;
565 rects[i].y = (stbrp_coord)fr.y;
566 }
567 else {
568 rects[i].x = rects[i].y = STBRP__MAXVAL;
569 }
570 }
571 }
572
573 // unsort
574 STBRP_SORT(rects, num_rects, sizeof(rects[0]), rect_original_order);
575
576 // set was_packed flags and all_rects_packed status
577 for (i = 0; i < num_rects; ++i) {
578 rects[i].was_packed = !(rects[i].x == STBRP__MAXVAL && rects[i].y == STBRP__MAXVAL);
579 if (!rects[i].was_packed)
580 all_rects_packed = 0;
581 }
582
583 // return the all_rects_packed status
584 return all_rects_packed;
585}
586#endif
587
588/*
589------------------------------------------------------------------------------
590This software is available under 2 licenses -- choose whichever you prefer.
591------------------------------------------------------------------------------
592ALTERNATIVE A - MIT License
593Copyright (c) 2017 Sean Barrett
594Permission is hereby granted, free of charge, to any person obtaining a copy of
595this software and associated documentation files (the "Software"), to deal in
596the Software without restriction, including without limitation the rights to
597use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
598of the Software, and to permit persons to whom the Software is furnished to do
599so, subject to the following conditions:
600The above copyright notice and this permission notice shall be included in all
601copies or substantial portions of the Software.
602THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
603IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
604FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
605AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
606LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
607OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
608SOFTWARE.
609------------------------------------------------------------------------------
610ALTERNATIVE B - Public Domain (www.unlicense.org)
611This is free and unencumbered software released into the public domain.
612Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
613software, either in source code form or as a compiled binary, for any purpose,
614commercial or non-commercial, and by any means.
615In jurisdictions that recognize copyright laws, the author or authors of this
616software dedicate any and all copyright interest in the software to the public
617domain. We make this dedication for the benefit of the public at large and to
618the detriment of our heirs and successors. We intend this dedication to be an
619overt act of relinquishment in perpetuity of all present and future rights to
620this software under copyright law.
621THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
622IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
623FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
624AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
625ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
626WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
627------------------------------------------------------------------------------
628*/
Note: See TracBrowser for help on using the repository browser.