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