suwako / ShaderPlayground

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