34 #ifndef STB_INCLUDE_STB_RECT_PACK_H
35 #define STB_INCLUDE_STB_RECT_PACK_H
37 #define STB_RECT_PACK_VERSION 1
40 #define STBRP_DEF static
42 #define STBRP_DEF extern
53 #ifdef STBRP_LARGE_RECTS
171 #ifdef STB_RECT_PACK_IMPLEMENTATION
176 #define STBRP_ASSERT assert
181 STBRP__INIT_skyline = 1,
187 case STBRP__INIT_skyline:
198 if (allow_out_of_mem)
219 #ifndef STBRP_LARGE_RECTS
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;
230 context->
width = width;
240 #ifdef STBRP_LARGE_RECTS
241 context->
extra[1].
y = (1<<30);
243 context->
extra[1].
y = 65535;
253 int min_y, visited_width, waste_area;
258 while (node->
next->
x <= x0)
269 while (node->
x < x1) {
270 if (node->
y > min_y) {
274 waste_area += visited_width * (node->
y - min_y);
278 visited_width += node->
next->
x - x0;
280 visited_width += node->
next->
x - node->
x;
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;
292 *pwaste = waste_area;
302 static stbrp__findresult stbrp__skyline_find_best_pos(
stbrp_context *c,
int width,
int height)
304 int best_waste = (1<<30), best_x, best_y = (1 << 30);
305 stbrp__findresult fr;
306 stbrp_node **prev, *node, *tail, **best = NULL;
309 width = (width + c->
align - 1);
310 width -= width % c->
align;
315 while (node->
x + width <= c->width) {
317 y = stbrp__skyline_find_min_y(c, node, node->
x, width, &waste);
326 if (y + height <= c->height) {
328 if (y < best_y || (y == best_y && waste < best_waste)) {
339 best_x = (best == NULL) ? 0 : (*best)->
x;
363 while (tail->
x < width)
366 int xpos = tail->
x - width;
370 while (node->
next->
x <= xpos) {
375 y = stbrp__skyline_find_min_y(c, node, xpos, width, &waste);
376 if (y + height < c->height) {
378 if (y < best_y || waste < best_waste || (waste==best_waste && xpos < best_x)) {
397 static stbrp__findresult stbrp__skyline_pack_rectangle(
stbrp_context *context,
int width,
int height)
400 stbrp__findresult res = stbrp__skyline_find_best_pos(context, width, height);
407 if (res.prev_link == NULL || res.y + height > context->
height || context->
free_head == NULL) {
408 res.prev_link = NULL;
423 cur = *res.prev_link;
424 if (cur->
x < res.x) {
430 *res.prev_link = node;
435 while (cur->
next && cur->
next->
x <= res.x + width) {
446 if (cur->
x < res.x + width)
451 while (cur->
x < context->
width) {
479 static int rect_height_compare(
const void *a,
const void *b)
487 return (p->
w > q->
w) ? -1 : (p->
w < q->
w);
490 static int rect_width_compare(
const void *a,
const void *b)
498 return (p->
h > q->
h) ? -1 : (p->
h < q->
h);
501 static int rect_original_order(
const void *a,
const void *b)
508 #ifdef STBRP_LARGE_RECTS
509 #define STBRP__MAXVAL 0xffffffff
511 #define STBRP__MAXVAL 0xffff
519 for (i=0; i < num_rects; ++i) {
521 #ifndef STBRP_LARGE_RECTS
522 STBRP_ASSERT(rects[i].w <= 0xffff && rects[i].h <= 0xffff);
527 qsort(rects, num_rects,
sizeof(rects[0]), rect_height_compare);
529 for (i=0; i < num_rects; ++i) {
530 stbrp__findresult fr = stbrp__skyline_pack_rectangle(context, rects[i].w, rects[i].h);
535 rects[i].
x = rects[i].
y = STBRP__MAXVAL;
540 qsort(rects, num_rects,
sizeof(rects[0]), rect_original_order);
543 for (i=0; i < num_rects; ++i)
544 rects[i].was_packed = !(rects[i].x == STBRP__MAXVAL && rects[i].y == STBRP__MAXVAL);
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_DEF void stbrp_setup_heuristic(stbrp_context *context, int heuristic)
STBRP_DEF void stbrp_setup_allow_out_of_mem(stbrp_context *context, int allow_out_of_mem)
unsigned short stbrp_coord