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