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