1// stb_rect_pack.h - v0.99 - 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.99 (2019-02-07) warning fixes
38// 0.11 (2017-03-03) return packing success/fail result
39// 0.10 (2016-10-25) remove cast-away-const to avoid warnings
40// 0.09 (2016-08-27) fix compiler warnings
41// 0.08 (2015-09-13) really fix bug with empty rects (w=0 or h=0)
42// 0.07 (2015-09-13) fix bug with empty rects (w=0 or h=0)
43// 0.06 (2015-04-15) added STBRP_SORT to allow replacing qsort
44// 0.05: added STBRP_ASSERT to allow replacing assert
45// 0.04: fixed minor bug in STBRP_LARGE_RECTS support
46// 0.01: initial release
47//
48// LICENSE
49//
50// See end of file for license information.
51
52//////////////////////////////////////////////////////////////////////////////
53//
54// INCLUDE SECTION
55//
56
57#ifndef STB_INCLUDE_STB_RECT_PACK_H
58#define STB_INCLUDE_STB_RECT_PACK_H
59
60#define STB_RECT_PACK_VERSION 1
61
62#ifdef STBRP_STATIC
63#define STBRP_DEF static
64#else
65#define STBRP_DEF extern
66#endif
67
68#ifdef __cplusplus
69extern "C" {
70#endif
71
72typedef struct stbrp_context stbrp_context;
73typedef struct stbrp_node stbrp_node;
74typedef struct stbrp_rect stbrp_rect;
75
76#ifdef STBRP_LARGE_RECTS
77typedef int stbrp_coord;
78#else
79typedef unsigned short stbrp_coord;
80#endif
81
82STBRP_DEF int stbrp_pack_rects (stbrp_context *context, stbrp_rect *rects, int num_rects);
83// Assign packed locations to rectangles. The rectangles are of type
84// 'stbrp_rect' defined below, stored in the array 'rects', and there
85// are 'num_rects' many of them.
86//
87// Rectangles which are successfully packed have the 'was_packed' flag
88// set to a non-zero value and 'x' and 'y' store the minimum location
89// on each axis (i.e. bottom-left in cartesian coordinates, top-left
90// if you imagine y increasing downwards). Rectangles which do not fit
91// have the 'was_packed' flag set to 0.
92//
93// You should not try to access the 'rects' array from another thread
94// while this function is running, as the function temporarily reorders
95// the array while it executes.
96//
97// To pack into another rectangle, you need to call stbrp_init_target
98// again. To continue packing into the same rectangle, you can call
99// this function again. Calling this multiple times with multiple rect
100// arrays will probably produce worse packing results than calling it
101// a single time with the full rectangle array, but the option is
102// available.
103//
104// The function returns 1 if all of the rectangles were successfully
105// packed and 0 otherwise.
106
107struct stbrp_rect
108{
109 // reserved for your use:
110 int id;
111
112 // input:
113 stbrp_coord w, h;
114
115 // output:
116 stbrp_coord x, y;
117 int was_packed; // non-zero if valid packing
118
119}; // 16 bytes, nominally
120
121
122STBRP_DEF void stbrp_init_target (stbrp_context *context, int width, int height, stbrp_node *nodes, int num_nodes);
123// Initialize a rectangle packer to:
124// pack a rectangle that is 'width' by 'height' in dimensions
125// using temporary storage provided by the array 'nodes', which is 'num_nodes' long
126//
127// You must call this function every time you start packing into a new target.
128//
129// There is no "shutdown" function. The 'nodes' memory must stay valid for
130// the following stbrp_pack_rects() call (or calls), but can be freed after
131// the call (or calls) finish.
132//
133// Note: to guarantee best results, either:
134// 1. make sure 'num_nodes' >= 'width'
135// or 2. call stbrp_allow_out_of_mem() defined below with 'allow_out_of_mem = 1'
136//
137// If you don't do either of the above things, widths will be quantized to multiples
138// of small integers to guarantee the algorithm doesn't run out of temporary storage.
139//
140// If you do #2, then the non-quantized algorithm will be used, but the algorithm
141// may run out of temporary storage and be unable to pack some rectangles.
142
143STBRP_DEF void stbrp_setup_allow_out_of_mem (stbrp_context *context, int allow_out_of_mem);
144// Optionally call this function after init but before doing any packing to
145// change the handling of the out-of-temp-memory scenario, described above.
146// If you call init again, this will be reset to the default (false).
147
148
149STBRP_DEF void stbrp_setup_heuristic (stbrp_context *context, int heuristic);
150// Optionally select which packing heuristic the library should use. Different
151// heuristics will produce better/worse results for different data sets.
152// If you call init again, this will be reset to the default.
153
154enum
155{
156 STBRP_HEURISTIC_Skyline_default=0,
157 STBRP_HEURISTIC_Skyline_BL_sortHeight = STBRP_HEURISTIC_Skyline_default,
158 STBRP_HEURISTIC_Skyline_BF_sortHeight
159};
160
161
162//////////////////////////////////////////////////////////////////////////////
163//
164// the details of the following structures don't matter to you, but they must
165// be visible so you can handle the memory allocations for them
166
167struct stbrp_node
168{
169 stbrp_coord x,y;
170 stbrp_node *next;
171};
172
173struct stbrp_context
174{
175 int width;
176 int height;
177 int align;
178 int init_mode;
179 int heuristic;
180 int num_nodes;
181 stbrp_node *active_head;
182 stbrp_node *free_head;
183 stbrp_node extra[2]; // we allocate two extra nodes so optimal user-node-count is 'width' not 'width+2'
184};
185
186#ifdef __cplusplus
187}
188#endif
189
190#endif
191
192

source code of gtk/gsk/gl/stb_rect_pack.h