1// stb_rect_pack.h - v1.00 - 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// Fabian Giesen
35//
36// Version history:
37//
38// 1.00 (2019-02-25) avoid small space waste; gracefully fail too-wide rectangles
39// 0.99 (2019-02-07) warning fixes
40// 0.11 (2017-03-03) return packing success/fail result
41// 0.10 (2016-10-25) remove cast-away-const to avoid warnings
42// 0.09 (2016-08-27) fix compiler warnings
43// 0.08 (2015-09-13) really fix bug with empty rects (w=0 or h=0)
44// 0.07 (2015-09-13) fix bug with empty rects (w=0 or h=0)
45// 0.06 (2015-04-15) added STBRP_SORT to allow replacing qsort
46// 0.05: added STBRP_ASSERT to allow replacing assert
47// 0.04: fixed minor bug in STBRP_LARGE_RECTS support
48// 0.01: initial release
49//
50// LICENSE
51//
52// See end of file for license information.
53
54//////////////////////////////////////////////////////////////////////////////
55//
56// INCLUDE SECTION
57//
58
59#ifndef STB_INCLUDE_STB_RECT_PACK_H
60#define STB_INCLUDE_STB_RECT_PACK_H
61
62#define STB_RECT_PACK_VERSION 1
63
64#ifdef STBRP_STATIC
65#define STBRP_DEF static
66#else
67#define STBRP_DEF extern
68#endif
69
70#ifdef __cplusplus
71extern "C" {
72#endif
73
74typedef struct stbrp_context stbrp_context;
75typedef struct stbrp_node stbrp_node;
76typedef struct stbrp_rect stbrp_rect;
77
78#ifdef STBRP_LARGE_RECTS
79typedef int stbrp_coord;
80#else
81typedef unsigned short stbrp_coord;
82#endif
83
84STBRP_DEF int stbrp_pack_rects (stbrp_context *context, stbrp_rect *rects, int num_rects);
85// Assign packed locations to rectangles. The rectangles are of type
86// 'stbrp_rect' defined below, stored in the array 'rects', and there
87// are 'num_rects' many of them.
88//
89// Rectangles which are successfully packed have the 'was_packed' flag
90// set to a non-zero value and 'x' and 'y' store the minimum location
91// on each axis (i.e. bottom-left in cartesian coordinates, top-left
92// if you imagine y increasing downwards). Rectangles which do not fit
93// have the 'was_packed' flag set to 0.
94//
95// You should not try to access the 'rects' array from another thread
96// while this function is running, as the function temporarily reorders
97// the array while it executes.
98//
99// To pack into another rectangle, you need to call stbrp_init_target
100// again. To continue packing into the same rectangle, you can call
101// this function again. Calling this multiple times with multiple rect
102// arrays will probably produce worse packing results than calling it
103// a single time with the full rectangle array, but the option is
104// available.
105//
106// The function returns 1 if all of the rectangles were successfully
107// packed and 0 otherwise.
108
109struct stbrp_rect
110{
111 // reserved for your use:
112 int id;
113
114 // input:
115 stbrp_coord w, h;
116
117 // output:
118 stbrp_coord x, y;
119 int was_packed; // non-zero if valid packing
120
121}; // 16 bytes, nominally
122
123
124STBRP_DEF void stbrp_init_target (stbrp_context *context, int width, int height, stbrp_node *nodes, int num_nodes);
125// Initialize a rectangle packer to:
126// pack a rectangle that is 'width' by 'height' in dimensions
127// using temporary storage provided by the array 'nodes', which is 'num_nodes' long
128//
129// You must call this function every time you start packing into a new target.
130//
131// There is no "shutdown" function. The 'nodes' memory must stay valid for
132// the following stbrp_pack_rects() call (or calls), but can be freed after
133// the call (or calls) finish.
134//
135// Note: to guarantee best results, either:
136// 1. make sure 'num_nodes' >= 'width'
137// or 2. call stbrp_allow_out_of_mem() defined below with 'allow_out_of_mem = 1'
138//
139// If you don't do either of the above things, widths will be quantized to multiples
140// of small integers to guarantee the algorithm doesn't run out of temporary storage.
141//
142// If you do #2, then the non-quantized algorithm will be used, but the algorithm
143// may run out of temporary storage and be unable to pack some rectangles.
144
145STBRP_DEF void stbrp_setup_allow_out_of_mem (stbrp_context *context, int allow_out_of_mem);
146// Optionally call this function after init but before doing any packing to
147// change the handling of the out-of-temp-memory scenario, described above.
148// If you call init again, this will be reset to the default (false).
149
150
151STBRP_DEF void stbrp_setup_heuristic (stbrp_context *context, int heuristic);
152// Optionally select which packing heuristic the library should use. Different
153// heuristics will produce better/worse results for different data sets.
154// If you call init again, this will be reset to the default.
155
156enum
157{
158 STBRP_HEURISTIC_Skyline_default=0,
159 STBRP_HEURISTIC_Skyline_BL_sortHeight = STBRP_HEURISTIC_Skyline_default,
160 STBRP_HEURISTIC_Skyline_BF_sortHeight
161};
162
163
164//////////////////////////////////////////////////////////////////////////////
165//
166// the details of the following structures don't matter to you, but they must
167// be visible so you can handle the memory allocations for them
168
169struct stbrp_node
170{
171 stbrp_coord x,y;
172 stbrp_node *next;
173};
174
175struct stbrp_context
176{
177 int width;
178 int height;
179 int align;
180 int init_mode;
181 int heuristic;
182 int num_nodes;
183 stbrp_node *active_head;
184 stbrp_node *free_head;
185 stbrp_node extra[2]; // we allocate two extra nodes so optimal user-node-count is 'width' not 'width+2'
186};
187
188#ifdef __cplusplus
189}
190#endif
191
192#endif
193
194//////////////////////////////////////////////////////////////////////////////
195//
196// IMPLEMENTATION SECTION
197//
198
199#ifdef STB_RECT_PACK_IMPLEMENTATION
200#ifndef STBRP_SORT
201#include <stdlib.h>
202#define STBRP_SORT qsort
203#endif
204
205#ifndef STBRP_ASSERT
206#include <assert.h>
207#define STBRP_ASSERT assert
208#endif
209
210#ifdef _MSC_VER
211#define STBRP__NOTUSED(v) (void)(v)
212#else
213#define STBRP__NOTUSED(v) (void)sizeof(v)
214#endif
215
216enum
217{
218 STBRP__INIT_skyline = 1
219};
220
221STBRP_DEF void stbrp_setup_heuristic(stbrp_context *context, int heuristic)
222{
223 switch (context->init_mode) {
224 case STBRP__INIT_skyline:
225 STBRP_ASSERT(heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight || heuristic == STBRP_HEURISTIC_Skyline_BF_sortHeight);
226 context->heuristic = heuristic;
227 break;
228 default:
229 STBRP_ASSERT(0);
230 }
231}
232
233STBRP_DEF void stbrp_setup_allow_out_of_mem(stbrp_context *context, int allow_out_of_mem)
234{
235 if (allow_out_of_mem)
236 // if it's ok to run out of memory, then don't bother aligning them;
237 // this gives better packing, but may fail due to OOM (even though
238 // the rectangles easily fit). @TODO a smarter approach would be to only
239 // quantize once we've hit OOM, then we could get rid of this parameter.
240 context->align = 1;
241 else {
242 // if it's not ok to run out of memory, then quantize the widths
243 // so that num_nodes is always enough nodes.
244 //
245 // I.e. num_nodes * align >= width
246 // align >= width / num_nodes
247 // align = ceil(width/num_nodes)
248
249 context->align = (context->width + context->num_nodes-1) / context->num_nodes;
250 }
251}
252
253STBRP_DEF void stbrp_init_target(stbrp_context *context, int width, int height, stbrp_node *nodes, int num_nodes)
254{
255 int i;
256#ifndef STBRP_LARGE_RECTS
257 STBRP_ASSERT(width <= 0xffff && height <= 0xffff);
258#endif
259
260 for (i=0; i < num_nodes-1; ++i)
261 nodes[i].next = &nodes[i+1];
262 nodes[i].next = NULL;
263 context->init_mode = STBRP__INIT_skyline;
264 context->heuristic = STBRP_HEURISTIC_Skyline_default;
265 context->free_head = &nodes[0];
266 context->active_head = &context->extra[0];
267 context->width = width;
268 context->height = height;
269 context->num_nodes = num_nodes;
270 stbrp_setup_allow_out_of_mem(context, 0);
271
272 // node 0 is the full width, node 1 is the sentinel (lets us not store width explicitly)
273 context->extra[0].x = 0;
274 context->extra[0].y = 0;
275 context->extra[0].next = &context->extra[1];
276 context->extra[1].x = (stbrp_coord) width;
277#ifdef STBRP_LARGE_RECTS
278 context->extra[1].y = (1<<30);
279#else
280 context->extra[1].y = 65535;
281#endif
282 context->extra[1].next = NULL;
283}
284
285// find minimum y position if it starts at x1
286static int stbrp__skyline_find_min_y(stbrp_context *c, stbrp_node *first, int x0, int width, int *pwaste)
287{
288 stbrp_node *node = first;
289 int x1 = x0 + width;
290 int min_y, visited_width, waste_area;
291
292 STBRP__NOTUSED(c);
293
294 STBRP_ASSERT(first->x <= x0);
295
296 #if 0
297 // skip in case we're past the node
298 while (node->next->x <= x0)
299 ++node;
300 #else
301 STBRP_ASSERT(node->next->x > x0); // we ended up handling this in the caller for efficiency
302 #endif
303
304 STBRP_ASSERT(node->x <= x0);
305
306 min_y = 0;
307 waste_area = 0;
308 visited_width = 0;
309 while (node->x < x1) {
310 if (node->y > min_y) {
311 // raise min_y higher.
312 // we've accounted for all waste up to min_y,
313 // but we'll now add more waste for everything we've visted
314 waste_area += visited_width * (node->y - min_y);
315 min_y = node->y;
316 // the first time through, visited_width might be reduced
317 if (node->x < x0)
318 visited_width += node->next->x - x0;
319 else
320 visited_width += node->next->x - node->x;
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 // if it can't possibly fit, bail immediately
354 if (width > c->width || height > c->height) {
355 fr.prev_link = NULL;
356 fr.x = fr.y = 0;
357 return fr;
358 }
359
360 node = c->active_head;
361 prev = &c->active_head;
362 while (node->x + width <= c->width) {
363 int y,waste;
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
366 // bottom left
367 if (y < best_y) {
368 best_y = y;
369 best = prev;
370 }
371 } else {
372 // best-fit
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)) {
376 best_y = y;
377 best_waste = waste;
378 best = prev;
379 }
380 }
381 }
382 prev = &node->next;
383 node = node->next;
384 }
385
386 best_x = (best == NULL) ? 0 : (*best)->x;
387
388 // if doing best-fit (BF), we also have to try aligning right edge to each node position
389 //
390 // e.g, if fitting
391 //
392 // ____________________
393 // |____________________|
394 //
395 // into
396 //
397 // | |
398 // | ____________|
399 // |____________|
400 //
401 // then right-aligned reduces waste, but bottom-left BL is always chooses left-aligned
402 //
403 // This makes BF take about 2x the time
404
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)
411 tail = tail->next;
412 while (tail) {
413 int xpos = tail->x - width;
414 int y,waste;
415 STBRP_ASSERT(xpos >= 0);
416 // find the left position that matches this
417 while (node->next->x <= xpos) {
418 prev = &node->next;
419 node = node->next;
420 }
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) {
424 if (y <= best_y) {
425 if (y < best_y || waste < best_waste || (waste==best_waste && xpos < best_x)) {
426 best_x = xpos;
427 STBRP_ASSERT(y <= best_y);
428 best_y = y;
429 best_waste = waste;
430 best = prev;
431 }
432 }
433 }
434 tail = tail->next;
435 }
436 }
437
438 fr.prev_link = best;
439 fr.x = best_x;
440 fr.y = best_y;
441 return fr;
442}
443
444static stbrp__findresult stbrp__skyline_pack_rectangle(stbrp_context *context, int width, int height)
445{
446 // find best position according to heuristic
447 stbrp__findresult res = stbrp__skyline_find_best_pos(context, width, height);
448 stbrp_node *node, *cur;
449
450 // bail if:
451 // 1. it failed
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;
456 return res;
457 }
458
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);
463
464 context->free_head = node->next;
465
466 // insert the new node into the right starting point, and
467 // let 'cur' point to the remaining nodes needing to be
468 // stiched back in
469
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;
474 cur->next = node;
475 cur = next;
476 } else {
477 *res.prev_link = node;
478 }
479
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;
487 cur = next;
488 }
489
490 // stitch the list back in
491 node->next = cur;
492
493 if (cur->x < res.x + width)
494 cur->x = (stbrp_coord) (res.x + width);
495
496#ifdef _DEBUG
497 cur = context->active_head;
498 while (cur->x < context->width) {
499 STBRP_ASSERT(cur->x < cur->next->x);
500 cur = cur->next;
501 }
502 STBRP_ASSERT(cur->next == NULL);
503
504 {
505 int count=0;
506 cur = context->active_head;
507 while (cur) {
508 cur = cur->next;
509 ++count;
510 }
511 cur = context->free_head;
512 while (cur) {
513 cur = cur->next;
514 ++count;
515 }
516 STBRP_ASSERT(count == context->num_nodes+2);
517 }
518#endif
519
520 return res;
521}
522
523static int rect_height_compare(const void *a, const void *b)
524{
525 const stbrp_rect *p = (const stbrp_rect *) a;
526 const stbrp_rect *q = (const stbrp_rect *) b;
527 if (p->h > q->h)
528 return -1;
529 if (p->h < q->h)
530 return 1;
531 return (p->w > q->w) ? -1 : (p->w < q->w);
532}
533
534static int rect_original_order(const void *a, const void *b)
535{
536 const stbrp_rect *p = (const stbrp_rect *) a;
537 const stbrp_rect *q = (const stbrp_rect *) b;
538 return (p->was_packed < q->was_packed) ? -1 : (p->was_packed > q->was_packed);
539}
540
541#ifdef STBRP_LARGE_RECTS
542#define STBRP__MAXVAL 0xffffffff
543#else
544#define STBRP__MAXVAL 0xffff
545#endif
546
547STBRP_DEF int stbrp_pack_rects(stbrp_context *context, stbrp_rect *rects, int num_rects)
548{
549 int i, all_rects_packed = 1;
550
551 // we use the 'was_packed' field internally to allow sorting/unsorting
552 for (i=0; i < num_rects; ++i) {
553 rects[i].was_packed = i;
554 }
555
556 // sort according to heuristic
557 STBRP_SORT(rects, num_rects, sizeof(rects[0]), rect_height_compare);
558
559 for (i=0; i < num_rects; ++i) {
560 if (rects[i].w == 0 || rects[i].h == 0) {
561 rects[i].x = rects[i].y = 0; // empty rect needs no space
562 } else {
563 stbrp__findresult fr = stbrp__skyline_pack_rectangle(context, rects[i].w, rects[i].h);
564 if (fr.prev_link) {
565 rects[i].x = (stbrp_coord) fr.x;
566 rects[i].y = (stbrp_coord) fr.y;
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*/
629