stb_rect_pack.h
Go to the documentation of this file.
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 
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 
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 
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 {
152 };
153 
154 
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 
161 {
162  stbrp_coord x,y;
164 };
165 
167 {
168  int width;
169  int height;
170  int align;
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 
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 
206 STBRP_DEF void stbrp_setup_heuristic(stbrp_context *context, int heuristic)
207 {
208  switch (context->init_mode) {
209  case STBRP__INIT_skyline:
211  context->heuristic = heuristic;
212  break;
213  default:
214  STBRP_ASSERT(0);
215  }
216 }
217 
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 
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;
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
271 static int stbrp__skyline_find_min_y(stbrp_context *, 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 
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 
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 
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 
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 
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 
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 
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
GLboolean GLboolean GLboolean b
GLint y
stbrp_node extra[2]
GLfloat GLfloat p
Definition: glext.h:12687
STBRP_DEF void stbrp_init_target(stbrp_context *context, int width, int height, stbrp_node *nodes, int num_nodes)
GLdouble GLdouble GLdouble w
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:1960
#define STBRP_DEF
Definition: stb_rect_pack.h:61
GLboolean GLboolean GLboolean GLboolean a
unsigned short stbrp_coord
Definition: stb_rect_pack.h:75
stbrp_coord y
stbrp_coord y
#define STBRP_ASSERT(x)
Definition: imgui_draw.cpp:77
const GLubyte * c
Definition: glext.h:12690
STBRP_DEF void stbrp_setup_allow_out_of_mem(stbrp_context *context, int allow_out_of_mem)
GLdouble x
stbrp_node * next
stbrp_coord x
GLint GLsizei GLsizei height
stbrp_node * free_head
GLuint GLfloat x0
Definition: glext.h:9721
STBRP_DEF void stbrp_setup_heuristic(stbrp_context *context, int heuristic)
GLint first
stbrp_coord w
stbrp_node * active_head
STBRP_DEF void stbrp_pack_rects(stbrp_context *context, stbrp_rect *rects, int num_rects)
void next(auto_any_t cur, type2type< T, C > *)
Definition: foreach.hpp:757
GLuint GLfloat GLfloat GLfloat x1
Definition: glext.h:9721
GLdouble GLdouble GLdouble q
stbrp_coord x
static double xpos
Definition: splitview.c:33
GLint GLsizei count
stbrp_coord h
#define NULL
Definition: tinycthread.c:47
int i
GLuint res
Definition: glext.h:8856
GLint GLsizei width


librealsense2
Author(s): Sergey Dorodnicov , Doron Hirshberg , Mark Horn , Reagan Lopez , Itay Carpis
autogenerated on Mon May 3 2021 02:50:10