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