56 #ifndef STB_INCLUDE_STB_RECT_PACK_H
57 #define STB_INCLUDE_STB_RECT_PACK_H
59 #define STB_RECT_PACK_VERSION 1
62 #define STBRP_DEF static
64 #define STBRP_DEF extern
71 typedef struct stbrp_context stbrp_context;
72 typedef struct stbrp_node stbrp_node;
73 typedef struct stbrp_rect stbrp_rect;
75 #ifdef STBRP_LARGE_RECTS
76 typedef int stbrp_coord;
78 typedef unsigned short stbrp_coord;
81 STBRP_DEF
int stbrp_pack_rects (stbrp_context *context, stbrp_rect *rects,
int num_rects);
121 STBRP_DEF
void stbrp_init_target (stbrp_context *context,
int width,
int height, stbrp_node *nodes,
int num_nodes);
142 STBRP_DEF
void stbrp_setup_allow_out_of_mem (stbrp_context *context,
int allow_out_of_mem);
148 STBRP_DEF
void stbrp_setup_heuristic (stbrp_context *context,
int heuristic);
155 STBRP_HEURISTIC_Skyline_default=0,
156 STBRP_HEURISTIC_Skyline_BL_sortHeight = STBRP_HEURISTIC_Skyline_default,
157 STBRP_HEURISTIC_Skyline_BF_sortHeight
180 stbrp_node *active_head;
181 stbrp_node *free_head;
196 #ifdef STB_RECT_PACK_IMPLEMENTATION
199 #define STBRP_SORT qsort
204 #define STBRP_ASSERT assert
208 #define STBRP__NOTUSED(v) (void)(v)
210 #define STBRP__NOTUSED(v) (void)sizeof(v)
215 STBRP__INIT_skyline = 1
218 STBRP_DEF
void stbrp_setup_heuristic(stbrp_context *context,
int heuristic)
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;
230 STBRP_DEF
void stbrp_setup_allow_out_of_mem(stbrp_context *context,
int allow_out_of_mem)
232 if (allow_out_of_mem)
246 context->align = (context->width + context->num_nodes-1) / context->num_nodes;
250 STBRP_DEF
void stbrp_init_target(stbrp_context *context,
int width,
int height, stbrp_node *nodes,
int num_nodes)
253 #ifndef STBRP_LARGE_RECTS
254 STBRP_ASSERT(width <= 0xffff && height <= 0xffff);
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;
261 context->heuristic = STBRP_HEURISTIC_Skyline_default;
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);
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);
277 context->extra[1].y = 65535;
279 context->extra[1].next = NULL;
283 static int stbrp__skyline_find_min_y(stbrp_context *c, stbrp_node *first,
int x0,
int width,
int *pwaste)
285 stbrp_node *node = first;
287 int min_y, visited_width, waste_area;
291 STBRP_ASSERT(first->x <= x0);
295 while (node->next->x <= x0)
298 STBRP_ASSERT(node->next->x > x0);
301 STBRP_ASSERT(node->x <= x0);
306 while (node->x < x1) {
307 if (node->y > min_y) {
311 waste_area += visited_width * (node->y - min_y);
315 visited_width += node->next->x - x0;
317 visited_width += node->next->x - node->x;
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;
329 *pwaste = waste_area;
336 stbrp_node **prev_link;
339 static stbrp__findresult stbrp__skyline_find_best_pos(stbrp_context *c,
int width,
int height)
341 int best_waste = (1<<30), best_x, best_y = (1 << 30);
342 stbrp__findresult fr;
343 stbrp_node **prev, *node, *tail, **best = NULL;
346 width = (width + c->align - 1);
347 width -= width % c->align;
348 STBRP_ASSERT(width % c->align == 0);
350 node = c->active_head;
351 prev = &c->active_head;
352 while (node->x + width <= c->width) {
354 y = stbrp__skyline_find_min_y(c, node, node->x, width, &waste);
355 if (c->heuristic == STBRP_HEURISTIC_Skyline_BL_sortHeight) {
363 if (y + height <= c->height) {
365 if (y < best_y || (y == best_y && waste < best_waste)) {
376 best_x = (best == NULL) ? 0 : (*best)->x;
395 if (c->heuristic == STBRP_HEURISTIC_Skyline_BF_sortHeight) {
396 tail = c->active_head;
397 node = c->active_head;
398 prev = &c->active_head;
400 while (tail->x < width)
403 int xpos = tail->x - width;
405 STBRP_ASSERT(xpos >= 0);
407 while (node->next->x <= xpos) {
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) {
415 if (y < best_y || waste < best_waste || (waste==best_waste && xpos < best_x)) {
417 STBRP_ASSERT(y <= best_y);
434 static stbrp__findresult stbrp__skyline_pack_rectangle(stbrp_context *context,
int width,
int height)
437 stbrp__findresult res = stbrp__skyline_find_best_pos(context, width, height);
438 stbrp_node *node, *cur;
444 if (res.prev_link == NULL || res.y + height > context->height || context->free_head == NULL) {
445 res.prev_link = NULL;
450 node = context->free_head;
451 node->x = (stbrp_coord) res.x;
452 node->y = (stbrp_coord) (res.y + height);
454 context->free_head = node->next;
460 cur = *res.prev_link;
461 if (cur->x < res.x) {
463 stbrp_node *next = cur->next;
467 *res.prev_link = node;
472 while (cur->next && cur->next->x <= res.x + width) {
473 stbrp_node *next = cur->next;
475 cur->next = context->free_head;
476 context->free_head = cur;
483 if (cur->x < res.x + width)
484 cur->x = (stbrp_coord) (res.x + width);
487 cur = context->active_head;
488 while (cur->x < context->width) {
489 STBRP_ASSERT(cur->x < cur->next->x);
492 STBRP_ASSERT(cur->next == NULL);
495 stbrp_node *L1 = NULL, *L2 = NULL;
497 cur = context->active_head;
503 cur = context->free_head;
509 STBRP_ASSERT(count == context->num_nodes+2);
516 static int rect_height_compare(
const void *a,
const void *b)
518 const stbrp_rect *p = (
const stbrp_rect *) a;
519 const stbrp_rect *q = (
const stbrp_rect *) b;
524 return (p->w > q->w) ? -1 : (p->w < q->w);
527 static int rect_width_compare(
const void *a,
const void *b)
529 const stbrp_rect *p = (
const stbrp_rect *) a;
530 const stbrp_rect *q = (
const stbrp_rect *) b;
535 return (p->h > q->h) ? -1 : (p->h < q->h);
538 static int rect_original_order(
const void *a,
const void *b)
540 const stbrp_rect *p = (
const stbrp_rect *) a;
541 const stbrp_rect *q = (
const stbrp_rect *) b;
542 return (p->was_packed < q->was_packed) ? -1 : (p->was_packed > q->was_packed);
545 #ifdef STBRP_LARGE_RECTS
546 #define STBRP__MAXVAL 0xffffffff
548 #define STBRP__MAXVAL 0xffff
551 STBRP_DEF
int stbrp_pack_rects(stbrp_context *context, stbrp_rect *rects,
int num_rects)
553 int i, all_rects_packed = 1;
556 for (i=0; i < num_rects; ++i) {
557 rects[i].was_packed = i;
558 #ifndef STBRP_LARGE_RECTS
559 STBRP_ASSERT(rects[i].w <= 0xffff && rects[i].h <= 0xffff);
564 STBRP_SORT(rects, num_rects,
sizeof(rects[0]), rect_height_compare);
566 for (i=0; i < num_rects; ++i) {
567 if (rects[i].w == 0 || rects[i].h == 0) {
568 rects[i].x = rects[i].y = 0;
570 stbrp__findresult fr = stbrp__skyline_pack_rectangle(context, rects[i].w, rects[i].h);
572 rects[i].x = (stbrp_coord) fr.x;
573 rects[i].y = (stbrp_coord) fr.y;
575 rects[i].x = rects[i].y = STBRP__MAXVAL;
581 STBRP_SORT(rects, num_rects,
sizeof(rects[0]), rect_original_order);
584 for (i=0; i < num_rects; ++i) {
585 rects[i].was_packed = !(rects[i].x == STBRP__MAXVAL && rects[i].y == STBRP__MAXVAL);
586 if (!rects[i].was_packed)
587 all_rects_packed = 0;
591 return all_rects_packed;