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 |
69 | extern "C" { |
70 | #endif |
71 | |
72 | typedef struct stbrp_context stbrp_context; |
73 | typedef struct stbrp_node stbrp_node; |
74 | typedef struct stbrp_rect stbrp_rect; |
75 | |
76 | #ifdef STBRP_LARGE_RECTS |
77 | typedef int stbrp_coord; |
78 | #else |
79 | typedef unsigned short stbrp_coord; |
80 | #endif |
81 | |
82 | STBRP_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 | |
107 | struct 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 | |
122 | STBRP_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 | |
143 | STBRP_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 | |
149 | STBRP_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 | |
154 | enum |
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 | |
167 | struct stbrp_node |
168 | { |
169 | stbrp_coord x,y; |
170 | stbrp_node *next; |
171 | }; |
172 | |
173 | struct 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 [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 | |