1/**************************************************************************/
2/* editor_atlas_packer.cpp */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#include "editor_atlas_packer.h"
32
33#include "core/math/geometry_2d.h"
34#include "core/math/vector2.h"
35#include "core/math/vector2i.h"
36
37void EditorAtlasPacker::chart_pack(Vector<Chart> &charts, int &r_width, int &r_height, int p_atlas_max_size, int p_cell_resolution) {
38 int divide_by = MIN(64, p_cell_resolution);
39 Vector<PlottedBitmap> bitmaps;
40
41 int max_w = 0;
42
43 for (int i = 0; i < charts.size(); i++) {
44 const Chart &chart = charts[i];
45
46 //generate aabb
47
48 Rect2i aabb;
49 int vertex_count = chart.vertices.size();
50 const Vector2 *vertices = chart.vertices.ptr();
51
52 for (int j = 0; j < vertex_count; j++) {
53 if (j == 0) {
54 aabb.position = vertices[j];
55 } else {
56 aabb.expand_to(vertices[j]);
57 }
58 }
59
60 Ref<BitMap> src_bitmap;
61 src_bitmap.instantiate();
62 src_bitmap->create((aabb.size + Vector2(divide_by - 1, divide_by - 1)) / divide_by);
63
64 int w = src_bitmap->get_size().width;
65 int h = src_bitmap->get_size().height;
66
67 //plot triangles, using divisor
68
69 for (int j = 0; j < chart.faces.size(); j++) {
70 Vector2i v[3];
71 for (int k = 0; k < 3; k++) {
72 Vector2 vtx = chart.vertices[chart.faces[j].vertex[k]];
73 vtx -= aabb.position;
74 vtx /= divide_by;
75 vtx.x = MIN(vtx.x, w - 1);
76 vtx.y = MIN(vtx.y, h - 1);
77 v[k] = vtx;
78 }
79
80 for (int k = 0; k < 3; k++) {
81 int l = k == 0 ? 2 : k - 1;
82 Vector<Point2i> points = Geometry2D::bresenham_line(v[k], v[l]);
83 for (Point2i point : points) {
84 src_bitmap->set_bitv(point, true);
85 }
86 }
87 }
88
89 //src_bitmap->convert_to_image()->save_png("bitmap" + itos(i) + ".png");
90
91 //grow by 1 for each side
92
93 int bmw = src_bitmap->get_size().width + 2;
94 int bmh = src_bitmap->get_size().height + 2;
95
96 int heights_size = -1;
97 bool transpose = false;
98 if (chart.can_transpose && bmh > bmw) {
99 heights_size = bmh;
100 transpose = true;
101 } else {
102 heights_size = bmw;
103 }
104
105 max_w = MAX(max_w, heights_size);
106
107 Vector<int> top_heights;
108 Vector<int> bottom_heights;
109 top_heights.resize(heights_size);
110 bottom_heights.resize(heights_size);
111
112 for (int x = 0; x < heights_size; x++) {
113 top_heights.write[x] = -1;
114 bottom_heights.write[x] = 0x7FFFFFFF;
115 }
116
117 for (int x = 0; x < bmw; x++) {
118 for (int y = 0; y < bmh; y++) {
119 bool found_pixel = false;
120 for (int lx = x - 1; lx < x + 2 && !found_pixel; lx++) {
121 for (int ly = y - 1; ly < y + 2 && !found_pixel; ly++) {
122 int px = lx - 1;
123 if (px < 0 || px >= w) {
124 continue;
125 }
126 int py = ly - 1;
127 if (py < 0 || py >= h) {
128 continue;
129 }
130
131 if (src_bitmap->get_bit(px, py)) {
132 found_pixel = true;
133 }
134 }
135 }
136 if (found_pixel) {
137 if (transpose) {
138 if (x > top_heights[y]) {
139 top_heights.write[y] = x;
140 }
141 if (x < bottom_heights[y]) {
142 bottom_heights.write[y] = x;
143 }
144 } else {
145 if (y > top_heights[x]) {
146 top_heights.write[x] = y;
147 }
148 if (y < bottom_heights[x]) {
149 bottom_heights.write[x] = y;
150 }
151 }
152 }
153 }
154 }
155
156 String row;
157 for (int j = 0; j < top_heights.size(); j++) {
158 row += "(" + itos(top_heights[j]) + "-" + itos(bottom_heights[j]) + "),";
159 }
160
161 PlottedBitmap plotted_bitmap;
162 plotted_bitmap.offset = aabb.position;
163 plotted_bitmap.top_heights = top_heights;
164 plotted_bitmap.bottom_heights = bottom_heights;
165 plotted_bitmap.chart_index = i;
166 plotted_bitmap.transposed = transpose;
167 plotted_bitmap.area = bmw * bmh;
168
169 bitmaps.push_back(plotted_bitmap);
170 }
171
172 bitmaps.sort();
173
174 int atlas_max_width = nearest_power_of_2_templated(p_atlas_max_size) / divide_by;
175 int atlas_w = nearest_power_of_2_templated(max_w);
176 int atlas_h;
177 while (true) {
178 atlas_h = 0;
179
180 //do a tetris
181 Vector<int> heights;
182 heights.resize(atlas_w);
183 for (int i = 0; i < atlas_w; i++) {
184 heights.write[i] = 0;
185 }
186
187 int *atlas_ptr = heights.ptrw();
188
189 for (int i = 0; i < bitmaps.size(); i++) {
190 int best_height = 0x7FFFFFFF;
191 int best_height_offset = -1;
192 int w = bitmaps[i].top_heights.size();
193
194 const int *top_heights = bitmaps[i].top_heights.ptr();
195 const int *bottom_heights = bitmaps[i].bottom_heights.ptr();
196
197 for (int j = 0; j <= atlas_w - w; j++) {
198 int height = 0;
199
200 for (int k = 0; k < w; k++) {
201 int pixmap_h = bottom_heights[k];
202 if (pixmap_h == 0x7FFFFFFF) {
203 continue; //no pixel here, anything is fine
204 }
205
206 int h = MAX(0, atlas_ptr[j + k] - pixmap_h);
207 if (h > height) {
208 height = h;
209 }
210 }
211
212 if (height < best_height) {
213 best_height = height;
214 best_height_offset = j;
215 }
216 }
217
218 for (int j = 0; j < w; j++) { //add
219 if (top_heights[j] == -1) { //unused
220 continue;
221 }
222 int height = best_height + top_heights[j] + 1;
223 atlas_ptr[j + best_height_offset] = height;
224 atlas_h = MAX(atlas_h, height);
225 }
226
227 // set
228 Vector2 offset = bitmaps[i].offset;
229 if (bitmaps[i].transposed) {
230 SWAP(offset.x, offset.y);
231 }
232
233 Vector2 final_pos = Vector2(best_height_offset * divide_by, best_height * divide_by) + Vector2(divide_by, divide_by) - offset;
234 charts.write[bitmaps[i].chart_index].final_offset = final_pos;
235 charts.write[bitmaps[i].chart_index].transposed = bitmaps[i].transposed;
236 }
237
238 if (atlas_h <= atlas_w * 2 || atlas_w >= atlas_max_width) {
239 break; //ok this one is enough
240 }
241
242 //try again
243 atlas_w *= 2;
244 }
245
246 r_width = atlas_w * divide_by;
247 r_height = atlas_h * divide_by;
248}
249