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
68 extern "C"
69 {
70 #endif
71
72 typedef struct stbrp_context stbrp_context;
73 typedef struct stbrp_node stbrp_node;
74 typedef struct stbrp_rect stbrp_rect;
75
76 #ifdef STBRP_LARGE_RECTS
77 typedef int stbrp_coord;
78 #else
79 typedef unsigned short stbrp_coord;
80 #endif
81
82 STBRP_DEF int stbrp_pack_rects(stbrp_context *context, stbrp_rect *rects, int num_rects);
83 // Assign packed locations to rectangles. The rectangles are of type
84 // 'stbrp_rect' defined below, stored in the array 'rects', and there
85 // are 'num_rects' many of them.
86 //
87 // Rectangles which are successfully packed have the 'was_packed' flag
88 // set to a non-zero value and 'x' and 'y' store the minimum location
89 // on each axis (i.e. bottom-left in cartesian coordinates, top-left
90 // if you imagine y increasing downwards). Rectangles which do not fit
91 // have the 'was_packed' flag set to 0.
92 //
93 // You should not try to access the 'rects' array from another thread
94 // while this function is running, as the function temporarily reorders
95 // the array while it executes.
96 //
97 // To pack into another rectangle, you need to call stbrp_init_target
98 // again. To continue packing into the same rectangle, you can call
99 // this function again. Calling this multiple times with multiple rect
100 // arrays will probably produce worse packing results than calling it
101 // a single time with the full rectangle array, but the option is
102 // available.
103 //
104 // The function returns 1 if all of the rectangles were successfully
105 // packed and 0 otherwise.
106
107 struct stbrp_rect
108 {
109 // reserved for your use:
110 int id;
111
112 // input:
113 stbrp_coord w, h;
114
115 // output:
116 stbrp_coord x, y;
117 int was_packed; // non-zero if valid packing
118
119 }; // 16 bytes, nominally
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 STBRP_DEF void stbrp_setup_heuristic(stbrp_context *context, int heuristic);
148 // Optionally select which packing heuristic the library should use. Different
149 // heuristics will produce better/worse results for different data sets.
150 // If you call init again, this will be reset to the default.
151
152 enum
153 {
154 STBRP_HEURISTIC_Skyline_default = 0,
155 STBRP_HEURISTIC_Skyline_BL_sortHeight = STBRP_HEURISTIC_Skyline_default,
156 STBRP_HEURISTIC_Skyline_BF_sortHeight
157 };
158
159 //////////////////////////////////////////////////////////////////////////////
160 //
161 // the details of the following structures don't matter to you, but they must
162 // be visible so you can handle the memory allocations for them
163
164 struct stbrp_node
165 {
166 stbrp_coord x, y;
167 stbrp_node *next;
168 };
169
170 struct stbrp_context
171 {
172 int width;
173 int height;
174 int align;
175 int init_mode;
176 int heuristic;
177 int num_nodes;
178 stbrp_node *active_head;
179 stbrp_node *free_head;
180 stbrp_node extra[2]; // we allocate two extra nodes so optimal user-node-count is 'width' not 'width+2'
181 };
182
183 #ifdef __cplusplus
184 }
185 #endif
186
187 #endif
188
189 //////////////////////////////////////////////////////////////////////////////
190 //
191 // IMPLEMENTATION SECTION
192 //
193
194 #ifdef STB_RECT_PACK_IMPLEMENTATION
195 #ifndef STBRP_SORT
196 #include <stdlib.h>
197 #define STBRP_SORT qsort
198 #endif
199
200 #ifndef STBRP_ASSERT
201 #include <assert.h>
202 #define STBRP_ASSERT assert
203 #endif
204
205 #ifdef _MSC_VER
206 #define STBRP__NOTUSED(v) (void)(v)
207 #define STBRP__CDECL __cdecl
208 #else
209 #define STBRP__NOTUSED(v) (void)sizeof(v)
210 #define STBRP__CDECL
211 #endif
212
213 enum
214 {
215 STBRP__INIT_skyline = 1
216 };
217
stbrp_setup_heuristic(stbrp_context * context,int heuristic)218 STBRP_DEF void stbrp_setup_heuristic(stbrp_context *context, int heuristic)
219 {
220 switch (context->init_mode)
221 {
222 case STBRP__INIT_skyline:
223 STBRP_ASSERT(heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight || heuristic == STBRP_HEURISTIC_Skyline_BF_sortHeight);
224 context->heuristic = heuristic;
225 break;
226 default:
227 STBRP_ASSERT(0);
228 }
229 }
230
stbrp_setup_allow_out_of_mem(stbrp_context * context,int allow_out_of_mem)231 STBRP_DEF void stbrp_setup_allow_out_of_mem(stbrp_context *context, int allow_out_of_mem)
232 {
233 if (allow_out_of_mem)
234 // if it's ok to run out of memory, then don't bother aligning them;
235 // this gives better packing, but may fail due to OOM (even though
236 // the rectangles easily fit). @TODO a smarter approach would be to only
237 // quantize once we've hit OOM, then we could get rid of this parameter.
238 context->align = 1;
239 else
240 {
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
stbrp_init_target(stbrp_context * context,int width,int height,stbrp_node * nodes,int num_nodes)252 STBRP_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
stbrp__skyline_find_min_y(stbrp_context * c,stbrp_node * first,int x0,int width,int * pwaste)285 static 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 {
310 if (node->y > min_y)
311 {
312 // raise min_y higher.
313 // we've accounted for all waste up to min_y,
314 // but we'll now add more waste for everything we've visted
315 waste_area += visited_width * (node->y - min_y);
316 min_y = node->y;
317 // the first time through, visited_width might be reduced
318 if (node->x < x0)
319 visited_width += node->next->x - x0;
320 else
321 visited_width += node->next->x - node->x;
322 }
323 else
324 {
325 // add waste area
326 int under_width = node->next->x - node->x;
327 if (under_width + visited_width > width)
328 under_width = width - visited_width;
329 waste_area += under_width * (min_y - node->y);
330 visited_width += under_width;
331 }
332 node = node->next;
333 }
334
335 *pwaste = waste_area;
336 return min_y;
337 }
338
339 typedef struct
340 {
341 int x, y;
342 stbrp_node **prev_link;
343 } stbrp__findresult;
344
stbrp__skyline_find_best_pos(stbrp_context * c,int width,int height)345 static stbrp__findresult stbrp__skyline_find_best_pos(stbrp_context *c, int width, int height)
346 {
347 int best_waste = (1 << 30), best_x, best_y = (1 << 30);
348 stbrp__findresult fr;
349 stbrp_node **prev, *node, *tail, **best = NULL;
350
351 // align to multiple of c->align
352 width = (width + c->align - 1);
353 width -= width % c->align;
354 STBRP_ASSERT(width % c->align == 0);
355
356 node = c->active_head;
357 prev = &c->active_head;
358 while (node->x + width <= c->width)
359 {
360 int y, waste;
361 y = stbrp__skyline_find_min_y(c, node, node->x, width, &waste);
362 if (c->heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight)
363 { // actually just want to test BL
364 // bottom left
365 if (y < best_y)
366 {
367 best_y = y;
368 best = prev;
369 }
370 }
371 else
372 {
373 // best-fit
374 if (y + height <= c->height)
375 {
376 // can only use it if it first vertically
377 if (y < best_y || (y == best_y && waste < best_waste))
378 {
379 best_y = y;
380 best_waste = waste;
381 best = prev;
382 }
383 }
384 }
385 prev = &node->next;
386 node = node->next;
387 }
388
389 best_x = (best == NULL) ? 0 : (*best)->x;
390
391 // if doing best-fit (BF), we also have to try aligning right edge to each node position
392 //
393 // e.g, if fitting
394 //
395 // ____________________
396 // |____________________|
397 //
398 // into
399 //
400 // | |
401 // | ____________|
402 // |____________|
403 //
404 // then right-aligned reduces waste, but bottom-left BL is always chooses left-aligned
405 //
406 // This makes BF take about 2x the time
407
408 if (c->heuristic == STBRP_HEURISTIC_Skyline_BF_sortHeight)
409 {
410 tail = c->active_head;
411 node = c->active_head;
412 prev = &c->active_head;
413 // find first node that's admissible
414 while (tail->x < width)
415 tail = tail->next;
416 while (tail)
417 {
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 {
424 prev = &node->next;
425 node = node->next;
426 }
427 STBRP_ASSERT(node->next->x > xpos && node->x <= xpos);
428 y = stbrp__skyline_find_min_y(c, node, xpos, width, &waste);
429 if (y + height < c->height)
430 {
431 if (y <= best_y)
432 {
433 if (y < best_y || waste < best_waste || (waste == best_waste && xpos < best_x))
434 {
435 best_x = xpos;
436 STBRP_ASSERT(y <= best_y);
437 best_y = y;
438 best_waste = waste;
439 best = prev;
440 }
441 }
442 }
443 tail = tail->next;
444 }
445 }
446
447 fr.prev_link = best;
448 fr.x = best_x;
449 fr.y = best_y;
450 return fr;
451 }
452
stbrp__skyline_pack_rectangle(stbrp_context * context,int width,int height)453 static stbrp__findresult stbrp__skyline_pack_rectangle(stbrp_context *context, int width, int height)
454 {
455 // find best position according to heuristic
456 stbrp__findresult res = stbrp__skyline_find_best_pos(context, width, height);
457 stbrp_node *node, *cur;
458
459 // bail if:
460 // 1. it failed
461 // 2. the best node doesn't fit (we don't always check this)
462 // 3. we're out of memory
463 if (res.prev_link == NULL || res.y + height > context->height || context->free_head == NULL)
464 {
465 res.prev_link = NULL;
466 return res;
467 }
468
469 // on success, create new node
470 node = context->free_head;
471 node->x = (stbrp_coord)res.x;
472 node->y = (stbrp_coord)(res.y + height);
473
474 context->free_head = node->next;
475
476 // insert the new node into the right starting point, and
477 // let 'cur' point to the remaining nodes needing to be
478 // stiched back in
479
480 cur = *res.prev_link;
481 if (cur->x < res.x)
482 {
483 // preserve the existing one, so start testing with the next one
484 stbrp_node *next = cur->next;
485 cur->next = node;
486 cur = next;
487 }
488 else
489 {
490 *res.prev_link = node;
491 }
492
493 // from here, traverse cur and free the nodes, until we get to one
494 // that shouldn't be freed
495 while (cur->next && cur->next->x <= res.x + width)
496 {
497 stbrp_node *next = cur->next;
498 // move the current node to the free list
499 cur->next = context->free_head;
500 context->free_head = cur;
501 cur = next;
502 }
503
504 // stitch the list back in
505 node->next = cur;
506
507 if (cur->x < res.x + width)
508 cur->x = (stbrp_coord)(res.x + width);
509
510 #ifdef _DEBUG
511 cur = context->active_head;
512 while (cur->x < context->width)
513 {
514 STBRP_ASSERT(cur->x < cur->next->x);
515 cur = cur->next;
516 }
517 STBRP_ASSERT(cur->next == NULL);
518
519 {
520 int count = 0;
521 cur = context->active_head;
522 while (cur)
523 {
524 cur = cur->next;
525 ++count;
526 }
527 cur = context->free_head;
528 while (cur)
529 {
530 cur = cur->next;
531 ++count;
532 }
533 STBRP_ASSERT(count == context->num_nodes + 2);
534 }
535 #endif
536
537 return res;
538 }
539
rect_height_compare(const void * a,const void * b)540 static int STBRP__CDECL rect_height_compare(const void *a, const void *b)
541 {
542 const stbrp_rect *p = (const stbrp_rect *)a;
543 const stbrp_rect *q = (const stbrp_rect *)b;
544 if (p->h > q->h)
545 return -1;
546 if (p->h < q->h)
547 return 1;
548 return (p->w > q->w) ? -1 : (p->w < q->w);
549 }
550
rect_original_order(const void * a,const void * b)551 static int STBRP__CDECL rect_original_order(const void *a, const void *b)
552 {
553 const stbrp_rect *p = (const stbrp_rect *)a;
554 const stbrp_rect *q = (const stbrp_rect *)b;
555 return (p->was_packed < q->was_packed) ? -1 : (p->was_packed > q->was_packed);
556 }
557
558 #ifdef STBRP_LARGE_RECTS
559 #define STBRP__MAXVAL 0xffffffff
560 #else
561 #define STBRP__MAXVAL 0xffff
562 #endif
563
stbrp_pack_rects(stbrp_context * context,stbrp_rect * rects,int num_rects)564 STBRP_DEF int stbrp_pack_rects(stbrp_context *context, stbrp_rect *rects, int num_rects)
565 {
566 int i, all_rects_packed = 1;
567
568 // we use the 'was_packed' field internally to allow sorting/unsorting
569 for (i = 0; i < num_rects; ++i)
570 {
571 rects[i].was_packed = i;
572 #ifndef STBRP_LARGE_RECTS
573 STBRP_ASSERT(rects[i].w <= 0xffff && rects[i].h <= 0xffff);
574 #endif
575 }
576
577 // sort according to heuristic
578 STBRP_SORT(rects, num_rects, sizeof(rects[0]), rect_height_compare);
579
580 for (i = 0; i < num_rects; ++i)
581 {
582 if (rects[i].w == 0 || rects[i].h == 0)
583 {
584 rects[i].x = rects[i].y = 0; // empty rect needs no space
585 }
586 else
587 {
588 stbrp__findresult fr = stbrp__skyline_pack_rectangle(context, rects[i].w, rects[i].h);
589 if (fr.prev_link)
590 {
591 rects[i].x = (stbrp_coord)fr.x;
592 rects[i].y = (stbrp_coord)fr.y;
593 }
594 else
595 {
596 rects[i].x = rects[i].y = STBRP__MAXVAL;
597 }
598 }
599 }
600
601 // unsort
602 STBRP_SORT(rects, num_rects, sizeof(rects[0]), rect_original_order);
603
604 // set was_packed flags and all_rects_packed status
605 for (i = 0; i < num_rects; ++i)
606 {
607 rects[i].was_packed = !(rects[i].x == STBRP__MAXVAL && rects[i].y == STBRP__MAXVAL);
608 if (!rects[i].was_packed)
609 all_rects_packed = 0;
610 }
611
612 // return the all_rects_packed status
613 return all_rects_packed;
614 }
615 #endif
616
617 /*
618 ------------------------------------------------------------------------------
619 This software is available under 2 licenses -- choose whichever you prefer.
620 ------------------------------------------------------------------------------
621 ALTERNATIVE A - MIT License
622 Copyright (c) 2017 Sean Barrett
623 Permission is hereby granted, free of charge, to any person obtaining a copy of
624 this software and associated documentation files (the "Software"), to deal in
625 the Software without restriction, including without limitation the rights to
626 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
627 of the Software, and to permit persons to whom the Software is furnished to do
628 so, subject to the following conditions:
629 The above copyright notice and this permission notice shall be included in all
630 copies or substantial portions of the Software.
631 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
632 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
633 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
634 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
635 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
636 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
637 SOFTWARE.
638 ------------------------------------------------------------------------------
639 ALTERNATIVE B - Public Domain (www.unlicense.org)
640 This is free and unencumbered software released into the public domain.
641 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
642 software, either in source code form or as a compiled binary, for any purpose,
643 commercial or non-commercial, and by any means.
644 In jurisdictions that recognize copyright laws, the author or authors of this
645 software dedicate any and all copyright interest in the software to the public
646 domain. We make this dedication for the benefit of the public at large and to
647 the detriment of our heirs and successors. We intend this dedication to be an
648 overt act of relinquishment in perpetuity of all present and future rights to
649 this software under copyright law.
650 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
651 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
652 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
653 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
654 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
655 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
656 ------------------------------------------------------------------------------
657 */
658