1// Aseprite Document Library
2// Copyright (c) 2019-2020 Igara Studio S.A.
3// Copyright (c) 2001-2016 David Capello
4//
5// This file is released under the terms of the MIT license.
6// Read LICENSE.txt for more information.
7
8#ifdef HAVE_CONFIG_H
9#include "config.h"
10#endif
11
12#include "doc/algorithm/shrink_bounds.h"
13
14#include "doc/cel.h"
15#include "doc/grid.h"
16#include "doc/image.h"
17#include "doc/image_impl.h"
18#include "doc/layer.h"
19#include "doc/layer_tilemap.h"
20#include "doc/primitives.h"
21#include "doc/primitives_fast.h"
22#include "doc/tileset.h"
23
24#include <thread>
25
26namespace doc {
27namespace algorithm {
28
29namespace {
30
31template<typename ImageTraits>
32bool is_same_pixel(color_t pixel1, color_t pixel2)
33{
34 static_assert(false && sizeof(ImageTraits), "No is_same_pixel impl");
35 return false;
36}
37
38template<>
39bool is_same_pixel<RgbTraits>(color_t pixel1, color_t pixel2)
40{
41 return (rgba_geta(pixel1) == 0 && rgba_geta(pixel2) == 0) || (pixel1 == pixel2);
42}
43
44template<>
45bool is_same_pixel<GrayscaleTraits>(color_t pixel1, color_t pixel2)
46{
47 return (graya_geta(pixel1) == 0 && graya_geta(pixel2) == 0) || (pixel1 == pixel2);
48}
49
50template<>
51bool is_same_pixel<IndexedTraits>(color_t pixel1, color_t pixel2)
52{
53 return pixel1 == pixel2;
54}
55
56template<>
57bool is_same_pixel<BitmapTraits>(color_t pixel1, color_t pixel2)
58{
59 return pixel1 == pixel2;
60}
61
62template<typename ImageTraits>
63bool shrink_bounds_left_templ(const Image* image, gfx::Rect& bounds, color_t refpixel, int rowSize)
64{
65 int u, v;
66 // Shrink left side
67 for (u=bounds.x; u<bounds.x2(); ++u) {
68 auto ptr = get_pixel_address_fast<ImageTraits>(image, u, v=bounds.y);
69 for (; v<bounds.y2(); ++v, ptr+=rowSize) {
70 ASSERT(ptr == get_pixel_address_fast<ImageTraits>(image, u, v));
71 if (!is_same_pixel<ImageTraits>(*ptr, refpixel))
72 return (!bounds.isEmpty());
73 }
74 ++bounds.x;
75 --bounds.w;
76 }
77 return (!bounds.isEmpty());
78}
79
80template<typename ImageTraits>
81bool shrink_bounds_right_templ(const Image* image, gfx::Rect& bounds, color_t refpixel, int rowSize)
82{
83 int u, v;
84 // Shrink right side
85 for (u=bounds.x2()-1; u>=bounds.x; --u) {
86 auto ptr = get_pixel_address_fast<ImageTraits>(image, u, v=bounds.y);
87 for (; v<bounds.y2(); ++v, ptr+=rowSize) {
88 ASSERT(ptr == get_pixel_address_fast<ImageTraits>(image, u, v));
89 if (!is_same_pixel<ImageTraits>(*ptr, refpixel))
90 return (!bounds.isEmpty());
91 }
92 --bounds.w;
93 }
94 return (!bounds.isEmpty());
95}
96
97template<typename ImageTraits>
98bool shrink_bounds_top_templ(const Image* image, gfx::Rect& bounds, color_t refpixel)
99{
100 int u, v;
101 // Shrink top side
102 for (v=bounds.y; v<bounds.y2(); ++v) {
103 auto ptr = get_pixel_address_fast<ImageTraits>(image, u=bounds.x, v);
104 for (; u<bounds.x2(); ++u, ++ptr) {
105 ASSERT(ptr == get_pixel_address_fast<ImageTraits>(image, u, v));
106 if (!is_same_pixel<ImageTraits>(*ptr, refpixel))
107 return (!bounds.isEmpty());
108 }
109 ++bounds.y;
110 --bounds.h;
111 }
112 return (!bounds.isEmpty());
113}
114
115template<typename ImageTraits>
116bool shrink_bounds_bottom_templ(const Image* image, gfx::Rect& bounds, color_t refpixel)
117{
118 int u, v;
119 // Shrink bottom side
120 for (v=bounds.y2()-1; v>=bounds.y; --v) {
121 auto ptr = get_pixel_address_fast<ImageTraits>(image, u=bounds.x, v);
122 for (; u<bounds.x2(); ++u, ++ptr) {
123 ASSERT(ptr == get_pixel_address_fast<ImageTraits>(image, u, v));
124 if (!is_same_pixel<ImageTraits>(*ptr, refpixel))
125 return (!bounds.isEmpty());
126 }
127 --bounds.h;
128 }
129 return (!bounds.isEmpty());
130}
131
132template<typename ImageTraits>
133bool shrink_bounds_templ(const Image* image, gfx::Rect& bounds, color_t refpixel)
134{
135 // Pixels per row
136 const int rowSize = image->getRowStrideSize() / image->getRowStrideSize(1);
137 const int canvasSize = image->width()*image->height();
138 if ((std::thread::hardware_concurrency() >= 4) &&
139 ((image->pixelFormat() == IMAGE_RGB && canvasSize >= 800*800) ||
140 (image->pixelFormat() != IMAGE_RGB && canvasSize >= 500*500))) {
141 gfx::Rect
142 leftBounds(bounds), rightBounds(bounds),
143 topBounds(bounds), bottomBounds(bounds);
144 std::thread left ([&]{ shrink_bounds_left_templ <ImageTraits>(image, leftBounds, refpixel, rowSize); });
145 std::thread right ([&]{ shrink_bounds_right_templ <ImageTraits>(image, rightBounds, refpixel, rowSize); });
146 std::thread top ([&]{ shrink_bounds_top_templ <ImageTraits>(image, topBounds, refpixel); });
147 std::thread bottom([&]{ shrink_bounds_bottom_templ<ImageTraits>(image, bottomBounds, refpixel); });
148 left.join();
149 right.join();
150 top.join();
151 bottom.join();
152 bounds = leftBounds;
153 bounds &= rightBounds;
154 bounds &= topBounds;
155 bounds &= bottomBounds;
156 return !bounds.isEmpty();
157 }
158 else {
159 return
160 shrink_bounds_left_templ<ImageTraits>(image, bounds, refpixel, rowSize) &&
161 shrink_bounds_right_templ<ImageTraits>(image, bounds, refpixel, rowSize) &&
162 shrink_bounds_top_templ<ImageTraits>(image, bounds, refpixel) &&
163 shrink_bounds_bottom_templ<ImageTraits>(image, bounds, refpixel);
164 }
165}
166
167template<typename ImageTraits>
168bool shrink_bounds_templ2(const Image* a, const Image* b, gfx::Rect& bounds)
169{
170 bool shrink;
171 int u, v;
172
173 // Shrink left side
174 for (u=bounds.x; u<bounds.x+bounds.w; ++u) {
175 shrink = true;
176 for (v=bounds.y; v<bounds.y+bounds.h; ++v) {
177 if (get_pixel_fast<ImageTraits>(a, u, v) !=
178 get_pixel_fast<ImageTraits>(b, u, v)) {
179 shrink = false;
180 break;
181 }
182 }
183 if (!shrink)
184 break;
185 ++bounds.x;
186 --bounds.w;
187 }
188
189 // Shrink right side
190 for (u=bounds.x+bounds.w-1; u>=bounds.x; --u) {
191 shrink = true;
192 for (v=bounds.y; v<bounds.y+bounds.h; ++v) {
193 if (get_pixel_fast<ImageTraits>(a, u, v) !=
194 get_pixel_fast<ImageTraits>(b, u, v)) {
195 shrink = false;
196 break;
197 }
198 }
199 if (!shrink)
200 break;
201 --bounds.w;
202 }
203
204 // Shrink top side
205 for (v=bounds.y; v<bounds.y+bounds.h; ++v) {
206 shrink = true;
207 for (u=bounds.x; u<bounds.x+bounds.w; ++u) {
208 if (get_pixel_fast<ImageTraits>(a, u, v) !=
209 get_pixel_fast<ImageTraits>(b, u, v)) {
210 shrink = false;
211 break;
212 }
213 }
214 if (!shrink)
215 break;
216 ++bounds.y;
217 --bounds.h;
218 }
219
220 // Shrink bottom side
221 for (v=bounds.y+bounds.h-1; v>=bounds.y; --v) {
222 shrink = true;
223 for (u=bounds.x; u<bounds.x+bounds.w; ++u) {
224 if (get_pixel_fast<ImageTraits>(a, u, v) !=
225 get_pixel_fast<ImageTraits>(b, u, v)) {
226 shrink = false;
227 break;
228 }
229 }
230 if (!shrink)
231 break;
232 --bounds.h;
233 }
234
235 return (!bounds.isEmpty());
236}
237
238bool shrink_bounds_tilemap(const Image* image,
239 const color_t refpixel,
240 const Layer* layer,
241 gfx::Rect& bounds)
242{
243 ASSERT(layer);
244 if (!layer)
245 return false;
246
247 ASSERT(layer->isTilemap());
248 if (!layer->isTilemap())
249 return false;
250
251 const Tileset* tileset =
252 static_cast<const LayerTilemap*>(layer)->tileset();
253
254 bool shrink;
255 int u, v;
256
257 // Shrink left side
258 for (u=bounds.x; u<bounds.x+bounds.w; ++u) {
259 shrink = true;
260 for (v=bounds.y; v<bounds.y+bounds.h; ++v) {
261 const tile_t tile = get_pixel_fast<TilemapTraits>(image, u, v);
262 const tile_t tileIndex = tile_geti(tile);
263 const ImageRef tileImg = tileset->get(tileIndex);
264
265 if (tileImg && !is_plain_image(tileImg.get(), refpixel)) {
266 shrink = false;
267 break;
268 }
269 }
270 if (!shrink)
271 break;
272 ++bounds.x;
273 --bounds.w;
274 }
275
276 // Shrink right side
277 for (u=bounds.x+bounds.w-1; u>=bounds.x; --u) {
278 shrink = true;
279 for (v=bounds.y; v<bounds.y+bounds.h; ++v) {
280 const tile_t tile = get_pixel_fast<TilemapTraits>(image, u, v);
281 const tile_t tileIndex = tile_geti(tile);
282 const ImageRef tileImg = tileset->get(tileIndex);
283
284 if (tileImg && !is_plain_image(tileImg.get(), refpixel)) {
285 shrink = false;
286 break;
287 }
288 }
289 if (!shrink)
290 break;
291 --bounds.w;
292 }
293
294 // Shrink top side
295 for (v=bounds.y; v<bounds.y+bounds.h; ++v) {
296 shrink = true;
297 for (u=bounds.x; u<bounds.x+bounds.w; ++u) {
298 const tile_t tile = get_pixel_fast<TilemapTraits>(image, u, v);
299 const tile_t tileIndex = tile_geti(tile);
300 const ImageRef tileImg = tileset->get(tileIndex);
301
302 if (tileImg && !is_plain_image(tileImg.get(), refpixel)) {
303 shrink = false;
304 break;
305 }
306 }
307 if (!shrink)
308 break;
309 ++bounds.y;
310 --bounds.h;
311 }
312
313 // Shrink bottom side
314 for (v=bounds.y+bounds.h-1; v>=bounds.y; --v) {
315 shrink = true;
316 for (u=bounds.x; u<bounds.x+bounds.w; ++u) {
317 const tile_t tile = get_pixel_fast<TilemapTraits>(image, u, v);
318 const tile_t tileIndex = tile_geti(tile);
319 const ImageRef tileImg = tileset->get(tileIndex);
320
321 if (tileImg && !is_plain_image(tileImg.get(), refpixel)) {
322 shrink = false;
323 break;
324 }
325 }
326 if (!shrink)
327 break;
328 --bounds.h;
329 }
330
331 return (!bounds.isEmpty());
332}
333
334}
335
336bool shrink_bounds(const Image* image,
337 const color_t refpixel,
338 const Layer* layer,
339 const gfx::Rect& startBounds,
340 gfx::Rect& bounds)
341{
342 bounds = (startBounds & image->bounds());
343 switch (image->pixelFormat()) {
344 case IMAGE_RGB: return shrink_bounds_templ<RgbTraits>(image, bounds, refpixel);
345 case IMAGE_GRAYSCALE: return shrink_bounds_templ<GrayscaleTraits>(image, bounds, refpixel);
346 case IMAGE_INDEXED: return shrink_bounds_templ<IndexedTraits>(image, bounds, refpixel);
347 case IMAGE_BITMAP: return shrink_bounds_templ<BitmapTraits>(image, bounds, refpixel);
348 case IMAGE_TILEMAP: return shrink_bounds_tilemap(image, refpixel, layer, bounds);
349 }
350 ASSERT(false);
351 bounds = startBounds;
352 return true;
353}
354
355bool shrink_bounds(const Image* image,
356 const color_t refpixel,
357 const Layer* layer,
358 gfx::Rect& bounds)
359{
360 return shrink_bounds(image, refpixel, layer, image->bounds(), bounds);
361}
362
363bool shrink_cel_bounds(const Cel* cel,
364 const color_t refpixel,
365 gfx::Rect& bounds)
366{
367 if (shrink_bounds(cel->image(), refpixel, cel->layer(), bounds)) {
368 // For tilemaps, we have to convert imgBounds (in tiles
369 // coordinates) to canvas coordinates using the Grid specs.
370 if (cel->layer()->isTilemap()) {
371 doc::LayerTilemap* tilemapLayer = static_cast<doc::LayerTilemap*>(cel->layer());
372 doc::Tileset* tileset = tilemapLayer->tileset();
373 doc::Grid grid = tileset->grid();
374 grid.origin(grid.origin() + cel->position());
375 bounds = grid.tileToCanvas(bounds);
376 }
377 else {
378 bounds.offset(cel->position());
379 }
380 return true;
381 }
382 else {
383 return false;
384 }
385}
386
387bool shrink_bounds2(const Image* a,
388 const Image* b,
389 const gfx::Rect& startBounds,
390 gfx::Rect& bounds)
391{
392 ASSERT(a && b);
393 ASSERT(a->bounds() == b->bounds());
394
395 bounds = (startBounds & a->bounds());
396
397 switch (a->pixelFormat()) {
398 case IMAGE_RGB: return shrink_bounds_templ2<RgbTraits>(a, b, bounds);
399 case IMAGE_GRAYSCALE: return shrink_bounds_templ2<GrayscaleTraits>(a, b, bounds);
400 case IMAGE_INDEXED: return shrink_bounds_templ2<IndexedTraits>(a, b, bounds);
401 case IMAGE_BITMAP: return shrink_bounds_templ2<BitmapTraits>(a, b, bounds);
402 case IMAGE_TILEMAP: return shrink_bounds_templ2<TilemapTraits>(a, b, bounds);
403 }
404 ASSERT(false);
405 return false;
406}
407
408} // namespace algorithm
409} // namespace doc
410