66#ifndef STB_INCLUDE_STB_RECT_PACK_H
67#define STB_INCLUDE_STB_RECT_PACK_H
69#define STB_RECT_PACK_VERSION 1
72#define STBRP_DEF static
74#define STBRP_DEF extern
87#define STBRP__MAXVAL 0x7fffffff
205#ifdef STB_RECT_PACK_IMPLEMENTATION
208#define STBRP_SORT qsort
213#define STBRP_ASSERT assert
217#define STBRP__NOTUSED(v) (void)(v)
218#define STBRP__CDECL __cdecl
220#define STBRP__NOTUSED(v) (void)sizeof(v)
226 STBRP__INIT_skyline = 1
232 case STBRP__INIT_skyline:
243 if (allow_out_of_mem)
265 for (i=0; i < num_nodes-1; ++i)
266 nodes[i].next = &nodes[i+1];
268 context->
init_mode = STBRP__INIT_skyline;
272 context->
width = width;
282 context->
extra[1].
y = (1<<30);
291 int min_y, visited_width, waste_area;
295 STBRP_ASSERT(first->
x <= x0);
299 while (node->
next->
x <= x0)
302 STBRP_ASSERT(node->
next->
x > x0);
305 STBRP_ASSERT(node->
x <= x0);
310 while (node->
x < x1) {
311 if (node->
y > min_y) {
315 waste_area += visited_width * (node->
y - min_y);
319 visited_width += node->
next->
x - x0;
321 visited_width += node->
next->
x - node->
x;
324 int under_width = node->
next->
x - node->
x;
325 if (under_width + visited_width > width)
326 under_width = width - visited_width;
327 waste_area += under_width * (min_y - node->
y);
328 visited_width += under_width;
333 *pwaste = waste_area;
343static stbrp__findresult stbrp__skyline_find_best_pos(
stbrp_context *c,
int width,
int height)
345 int best_waste = (1<<30), best_x, best_y = (1 << 30);
346 stbrp__findresult fr;
350 width = (width + c->
align - 1);
351 width -= width % c->
align;
352 STBRP_ASSERT(width % c->
align == 0);
363 while (node->
x + width <= c->width) {
365 y = stbrp__skyline_find_min_y(c, node, node->
x, width, &waste);
374 if (y + height <= c->height) {
376 if (y < best_y || (y == best_y && waste < best_waste)) {
387 best_x = (best ==
NULL) ? 0 : (*best)->
x;
411 while (tail->
x < width)
414 int xpos = tail->
x - width;
416 STBRP_ASSERT(xpos >= 0);
418 while (node->
next->
x <= xpos) {
422 STBRP_ASSERT(node->
next->
x > xpos && node->
x <= xpos);
423 y = stbrp__skyline_find_min_y(c, node, xpos, width, &waste);
424 if (y + height <= c->height) {
426 if (y < best_y || waste < best_waste || (waste==best_waste && xpos < best_x)) {
428 STBRP_ASSERT(y <= best_y);
445static stbrp__findresult stbrp__skyline_pack_rectangle(
stbrp_context *context,
int width,
int height)
448 stbrp__findresult res = stbrp__skyline_find_best_pos(context, width, height);
456 res.prev_link =
NULL;
471 cur = *res.prev_link;
472 if (cur->
x < res.x) {
478 *res.prev_link = node;
483 while (cur->
next && cur->
next->
x <= res.x + width) {
494 if (cur->
x < res.x + width)
499 while (cur->
x < context->
width) {
500 STBRP_ASSERT(cur->
x < cur->
next->
x);
517 STBRP_ASSERT(count == context->
num_nodes+2);
524static int STBRP__CDECL rect_height_compare(
const void *a,
const void *b)
532 return (p->
w > q->
w) ? -1 : (p->
w < q->
w);
535static int STBRP__CDECL rect_original_order(
const void *a,
const void *b)
544 int i, all_rects_packed = 1;
547 for (i=0; i < num_rects; ++i) {
552 STBRP_SORT(rects, num_rects,
sizeof(rects[0]), rect_height_compare);
554 for (i=0; i < num_rects; ++i) {
555 if (rects[i].w == 0 || rects[i].h == 0) {
556 rects[i].
x = rects[i].
y = 0;
558 stbrp__findresult fr = stbrp__skyline_pack_rectangle(context, rects[i].w, rects[i].h);
569 STBRP_SORT(rects, num_rects,
sizeof(rects[0]), rect_original_order);
572 for (i=0; i < num_rects; ++i) {
574 if (!rects[i].was_packed)
575 all_rects_packed = 0;
579 return all_rects_packed;
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)
STBRP_DEF int stbrp_pack_rects(stbrp_context *context, stbrp_rect *rects, int num_rects)
@ STBRP_HEURISTIC_Skyline_BF_sortHeight
@ STBRP_HEURISTIC_Skyline_BL_sortHeight
@ STBRP_HEURISTIC_Skyline_default