From 342403a02f8063903d0f38327430721d4d0ae331 Mon Sep 17 00:00:00 2001 From: Matt Strapp Date: Mon, 20 Sep 2021 18:15:14 -0500 Subject: do ass1 --- .../docs/html/stb__rect__pack_8h_source.html | 1484 ++++++++++---------- 1 file changed, 742 insertions(+), 742 deletions(-) (limited to 'dev/MinGfx/docs/html/stb__rect__pack_8h_source.html') diff --git a/dev/MinGfx/docs/html/stb__rect__pack_8h_source.html b/dev/MinGfx/docs/html/stb__rect__pack_8h_source.html index 2d2f39e..a93d957 100644 --- a/dev/MinGfx/docs/html/stb__rect__pack_8h_source.html +++ b/dev/MinGfx/docs/html/stb__rect__pack_8h_source.html @@ -1,742 +1,742 @@ - - - - - - - -MinGfx Toolkit: src/stb_rect_pack.h Source File - - - - - - - - - - - - -
-
- - - - - - -
-
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
-
- - - - - + + + + + + + +MinGfx Toolkit: src/stb_rect_pack.h Source File + + + + + + + + + + + + +
+
+ + + + + + +
+
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
+
+ + + + + -- cgit v1.2.3