1// Aseprite Render Library
2// Copyright (c) 2019-2022 Igara Studio S.A.
3// Copyright (c) 2001-2018 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 "render/quantization.h"
13
14#include "doc/image_impl.h"
15#include "doc/layer.h"
16#include "doc/octree_map.h"
17#include "doc/palette.h"
18#include "doc/primitives.h"
19#include "doc/remap.h"
20#include "doc/sprite.h"
21#include "render/dithering.h"
22#include "render/error_diffusion.h"
23#include "render/ordered_dither.h"
24#include "render/render.h"
25#include "render/task_delegate.h"
26
27#include <algorithm>
28#include <limits>
29#include <map>
30#include <memory>
31#include <vector>
32
33namespace render {
34
35using namespace doc;
36using namespace gfx;
37
38Palette* create_palette_from_sprite(
39 const Sprite* sprite,
40 const frame_t fromFrame,
41 const frame_t toFrame,
42 const bool withAlpha,
43 Palette* palette,
44 TaskDelegate* delegate,
45 const bool newBlend,
46 RgbMapAlgorithm mapAlgo,
47 const bool calculateWithTransparent)
48{
49 if (mapAlgo == doc::RgbMapAlgorithm::DEFAULT)
50 mapAlgo = doc::RgbMapAlgorithm::OCTREE;
51
52 PaletteOptimizer optimizer;
53 OctreeMap octreemap;
54
55 // Transparent color is needed if we have transparent layers
56 int maskIndex;
57 if ((sprite->backgroundLayer() && sprite->allLayersCount() == 1) ||
58 !calculateWithTransparent)
59 maskIndex = -1;
60 else if (sprite->colorMode() == ColorMode::INDEXED)
61 maskIndex = sprite->transparentColor();
62 else {
63 ASSERT(sprite->transparentColor() == 0);
64 maskIndex = 0; // For RGB/Grayscale images we use index 0 as the transparent index by default
65 }
66
67 // TODO check if how this is used in OctreeMap, if as a RGBA value
68 // or as an index (here we are using it as an index).
69 const color_t maskColor = (sprite->backgroundLayer()
70 && sprite->allLayersCount() == 1) ? DOC_OCTREE_IS_OPAQUE:
71 sprite->transparentColor();
72
73 if (!palette)
74 palette = new Palette(fromFrame, 256);
75
76 // Add a flat image with the current sprite's frame rendered
77 ImageRef flat_image(Image::create(IMAGE_RGB,
78 sprite->width(), sprite->height()));
79
80 render::Render render;
81 render.setNewBlend(newBlend);
82
83 // Feed the optimizer with all rendered frames
84 for (frame_t frame=fromFrame; frame<=toFrame; ++frame) {
85 render.renderSprite(flat_image.get(), sprite, frame);
86
87 switch (mapAlgo) {
88 case RgbMapAlgorithm::RGB5A3:
89 optimizer.feedWithImage(flat_image.get(), withAlpha);
90 break;
91 case RgbMapAlgorithm::OCTREE:
92 octreemap.feedWithImage(flat_image.get(), withAlpha, maskColor);
93 break;
94 default:
95 ASSERT(false);
96 break;
97 }
98
99 if (delegate) {
100 if (!delegate->continueTask())
101 return nullptr;
102
103 delegate->notifyTaskProgress(
104 double(frame-fromFrame+1) / double(toFrame-fromFrame+1));
105 }
106 }
107
108 switch (mapAlgo) {
109
110 case RgbMapAlgorithm::RGB5A3: {
111 // Generate an optimized palette
112 optimizer.calculate(palette, maskIndex);
113 break;
114 }
115
116 case RgbMapAlgorithm::OCTREE:
117 // TODO check calculateWithTransparent flag
118
119 if (!octreemap.makePalette(palette, palette->size())) {
120 // We can use an 8-bit deep octree map, instead of 7-bit of the
121 // first attempt.
122 octreemap = OctreeMap();
123 for (frame_t frame=fromFrame; frame<=toFrame; ++frame) {
124 render.renderSprite(flat_image.get(), sprite, frame);
125 octreemap.feedWithImage(flat_image.get(), withAlpha, maskColor , 8);
126 if (delegate) {
127 if (!delegate->continueTask())
128 return nullptr;
129
130 delegate->notifyTaskProgress(
131 double(frame-fromFrame+1) / double(toFrame-fromFrame+1));
132 }
133 }
134 octreemap.makePalette(palette, palette->size(), 8);
135 }
136 break;
137 }
138
139 return palette;
140}
141
142Image* convert_pixel_format(
143 const Image* image,
144 Image* new_image,
145 PixelFormat pixelFormat,
146 const Dithering& dithering,
147 const RgbMap* rgbmap,
148 const Palette* palette,
149 bool is_background,
150 color_t new_mask_color,
151 rgba_to_graya_func toGray,
152 TaskDelegate* delegate)
153{
154 if (!new_image)
155 new_image = Image::create(pixelFormat, image->width(), image->height());
156 new_image->setMaskColor(new_mask_color);
157
158 // RGB -> Indexed with ordered dithering
159 if (image->pixelFormat() == IMAGE_RGB &&
160 pixelFormat == IMAGE_INDEXED &&
161 dithering.algorithm() != DitheringAlgorithm::None) {
162 std::unique_ptr<DitheringAlgorithmBase> dither;
163 switch (dithering.algorithm()) {
164 case DitheringAlgorithm::Ordered:
165 dither.reset(new OrderedDither2(is_background ? -1: new_mask_color));
166 break;
167 case DitheringAlgorithm::Old:
168 dither.reset(new OrderedDither(is_background ? -1: new_mask_color));
169 break;
170 case DitheringAlgorithm::ErrorDiffusion:
171 dither.reset(new ErrorDiffusionDither(is_background ? -1: new_mask_color));
172 break;
173 }
174 if (dither)
175 dither_rgb_image_to_indexed(
176 *dither, dithering,
177 image, new_image, rgbmap, palette, delegate);
178 return new_image;
179 }
180
181 // RGB/Indexed -> Gray
182 if ((image->pixelFormat() == IMAGE_RGB ||
183 image->pixelFormat() == IMAGE_INDEXED) &&
184 new_image->pixelFormat() == IMAGE_GRAYSCALE) {
185 if (!toGray)
186 toGray = &rgba_to_graya_using_luma;
187 }
188
189 color_t c;
190 int r, g, b, a;
191
192 switch (image->pixelFormat()) {
193
194 case IMAGE_RGB: {
195 const LockImageBits<RgbTraits> srcBits(image);
196 LockImageBits<RgbTraits>::const_iterator src_it = srcBits.begin(), src_end = srcBits.end();
197
198 switch (new_image->pixelFormat()) {
199
200 // RGB -> RGB
201 case IMAGE_RGB:
202 new_image->copy(image, gfx::Clip(image->bounds()));
203 break;
204
205 // RGB -> Grayscale
206 case IMAGE_GRAYSCALE: {
207 LockImageBits<GrayscaleTraits> dstBits(new_image, Image::WriteLock);
208 LockImageBits<GrayscaleTraits>::iterator dst_it = dstBits.begin();
209#ifdef _DEBUG
210 LockImageBits<GrayscaleTraits>::iterator dst_end = dstBits.end();
211 ASSERT(toGray);
212#endif
213
214 for (; src_it != src_end; ++src_it, ++dst_it) {
215 ASSERT(dst_it != dst_end);
216 *dst_it = (*toGray)(*src_it);
217 }
218 ASSERT(dst_it == dst_end);
219 break;
220 }
221
222 // RGB -> Indexed
223 case IMAGE_INDEXED: {
224 LockImageBits<IndexedTraits> dstBits(new_image, Image::WriteLock);
225 LockImageBits<IndexedTraits>::iterator dst_it = dstBits.begin();
226#ifdef _DEBUG
227 LockImageBits<IndexedTraits>::iterator dst_end = dstBits.end();
228#endif
229
230 for (; src_it != src_end; ++src_it, ++dst_it) {
231 ASSERT(dst_it != dst_end);
232 c = *src_it;
233
234 r = rgba_getr(c);
235 g = rgba_getg(c);
236 b = rgba_getb(c);
237 a = rgba_geta(c);
238
239 if (a == 0)
240 *dst_it = (new_mask_color == -1? 0 : new_mask_color);
241 else if (rgbmap)
242 *dst_it = rgbmap->mapColor(c);
243 else
244 *dst_it = palette->findBestfit(r, g, b, a, new_mask_color);
245 }
246 ASSERT(dst_it == dst_end);
247 break;
248 }
249 }
250 break;
251 }
252
253 case IMAGE_GRAYSCALE: {
254 const LockImageBits<GrayscaleTraits> srcBits(image);
255 LockImageBits<GrayscaleTraits>::const_iterator src_it = srcBits.begin(), src_end = srcBits.end();
256
257 switch (new_image->pixelFormat()) {
258
259 // Grayscale -> RGB
260 case IMAGE_RGB: {
261 LockImageBits<RgbTraits> dstBits(new_image, Image::WriteLock);
262 LockImageBits<RgbTraits>::iterator dst_it = dstBits.begin();
263#ifdef _DEBUG
264 LockImageBits<RgbTraits>::iterator dst_end = dstBits.end();
265#endif
266
267 for (; src_it != src_end; ++src_it, ++dst_it) {
268 ASSERT(dst_it != dst_end);
269 c = *src_it;
270
271 g = graya_getv(c);
272
273 *dst_it = rgba(g, g, g, graya_geta(c));
274 }
275 ASSERT(dst_it == dst_end);
276 break;
277 }
278
279 // Grayscale -> Grayscale
280 case IMAGE_GRAYSCALE:
281 new_image->copy(image, gfx::Clip(image->bounds()));
282 break;
283
284 // Grayscale -> Indexed
285 case IMAGE_INDEXED: {
286 LockImageBits<IndexedTraits> dstBits(new_image, Image::WriteLock);
287 LockImageBits<IndexedTraits>::iterator dst_it = dstBits.begin();
288#ifdef _DEBUG
289 LockImageBits<IndexedTraits>::iterator dst_end = dstBits.end();
290#endif
291
292 for (; src_it != src_end; ++src_it, ++dst_it) {
293 ASSERT(dst_it != dst_end);
294 c = *src_it;
295 a = graya_geta(c);
296 c = graya_getv(c);
297
298 if (a == 0)
299 *dst_it = (new_mask_color == -1? 0 : new_mask_color);
300 else if (rgbmap)
301 *dst_it = rgbmap->mapColor(c, c, c, a);
302 else
303 *dst_it = palette->findBestfit(c, c, c, a, new_mask_color);
304 }
305 ASSERT(dst_it == dst_end);
306 break;
307 }
308 }
309 break;
310 }
311
312 case IMAGE_INDEXED: {
313 const LockImageBits<IndexedTraits> srcBits(image);
314 LockImageBits<IndexedTraits>::const_iterator src_it = srcBits.begin(), src_end = srcBits.end();
315
316 switch (new_image->pixelFormat()) {
317
318 // Indexed -> RGB
319 case IMAGE_RGB: {
320 LockImageBits<RgbTraits> dstBits(new_image, Image::WriteLock);
321 LockImageBits<RgbTraits>::iterator dst_it = dstBits.begin();
322#ifdef _DEBUG
323 LockImageBits<RgbTraits>::iterator dst_end = dstBits.end();
324#endif
325
326 for (; src_it != src_end; ++src_it, ++dst_it) {
327 ASSERT(dst_it != dst_end);
328 c = *src_it;
329
330 if (!is_background && c == image->maskColor())
331 *dst_it = rgba(0, 0, 0, 0);
332 else {
333 const uint32_t p = palette->getEntry(c);
334 if (is_background)
335 *dst_it = rgba(rgba_getr(p), rgba_getg(p), rgba_getb(p), 255);
336 else
337 *dst_it = p;
338 }
339 }
340 ASSERT(dst_it == dst_end);
341 break;
342 }
343
344 // Indexed -> Grayscale
345 case IMAGE_GRAYSCALE: {
346 LockImageBits<GrayscaleTraits> dstBits(new_image, Image::WriteLock);
347 LockImageBits<GrayscaleTraits>::iterator dst_it = dstBits.begin();
348#ifdef _DEBUG
349 LockImageBits<GrayscaleTraits>::iterator dst_end = dstBits.end();
350 ASSERT(toGray);
351#endif
352
353 for (; src_it != src_end; ++src_it, ++dst_it) {
354 ASSERT(dst_it != dst_end);
355 c = *src_it;
356
357 if (!is_background && c == image->maskColor())
358 *dst_it = graya(0, 0);
359 else {
360 c = palette->getEntry(c);
361 *dst_it = (*toGray)(c);
362 }
363 }
364 ASSERT(dst_it == dst_end);
365 break;
366 }
367
368 // Indexed -> Indexed
369 case IMAGE_INDEXED: {
370 LockImageBits<IndexedTraits> dstBits(new_image, Image::WriteLock);
371 LockImageBits<IndexedTraits>::iterator dst_it = dstBits.begin();
372#ifdef _DEBUG
373 LockImageBits<IndexedTraits>::iterator dst_end = dstBits.end();
374#endif
375
376 for (; src_it != src_end; ++src_it, ++dst_it) {
377 ASSERT(dst_it != dst_end);
378 c = *src_it;
379
380 if (!is_background && c == image->maskColor())
381 *dst_it = new_mask_color;
382 else {
383 c = palette->getEntry(c);
384 r = rgba_getr(c);
385 g = rgba_getg(c);
386 b = rgba_getb(c);
387 a = rgba_geta(c);
388
389 if (rgbmap)
390 *dst_it = rgbmap->mapColor(r, g, b, a);
391 else
392 *dst_it = palette->findBestfit(r, g, b, a, new_mask_color);
393 }
394 }
395 ASSERT(dst_it == dst_end);
396 break;
397 }
398
399 }
400 break;
401 }
402 }
403
404 return new_image;
405}
406
407//////////////////////////////////////////////////////////////////////
408// Creation of optimized palette for RGB images
409// by David Capello
410
411void PaletteOptimizer::feedWithImage(const Image* image,
412 const bool withAlpha)
413{
414 feedWithImage(image, image->bounds(), withAlpha);
415}
416
417void PaletteOptimizer::feedWithImage(const Image* image,
418 const gfx::Rect& bounds,
419 const bool withAlpha)
420{
421 uint32_t color;
422
423 if (withAlpha)
424 m_withAlpha = true;
425
426 ASSERT(image);
427 switch (image->pixelFormat()) {
428
429 case IMAGE_RGB:
430 {
431 const LockImageBits<RgbTraits> bits(image, bounds);
432 auto it = bits.begin(), end = bits.end();
433
434 for (; it != end; ++it) {
435 color = *it;
436 if (rgba_geta(color) > 0) {
437 if (!withAlpha)
438 color |= rgba(0, 0, 0, 255);
439
440 m_histogram.addSamples(color, 1);
441 }
442 }
443 }
444 break;
445
446 case IMAGE_GRAYSCALE:
447 {
448 const LockImageBits<GrayscaleTraits> bits(image, bounds);
449 auto it = bits.begin(), end = bits.end();
450
451 for (; it != end; ++it) {
452 color = *it;
453
454 if (graya_geta(color) > 0) {
455 if (!withAlpha)
456 color = graya(graya_getv(color), 255);
457
458 m_histogram.addSamples(rgba(graya_getv(color),
459 graya_getv(color),
460 graya_getv(color),
461 graya_geta(color)), 1);
462 }
463 }
464 }
465 break;
466
467 case IMAGE_INDEXED:
468 ASSERT(false);
469 break;
470
471 }
472}
473
474void PaletteOptimizer::feedWithRgbaColor(color_t color)
475{
476 m_histogram.addSamples(color, 1);
477}
478
479void PaletteOptimizer::calculate(Palette* palette, int maskIndex)
480{
481 bool addMask;
482
483 if ((palette->size() > 1) &&
484 (maskIndex >= 0 && maskIndex < palette->size())) {
485 palette->resize(palette->size()-1);
486 addMask = true;
487 }
488 else
489 addMask = false;
490
491 // If the sprite has a background layer, the first entry can be
492 // used, in other case the 0 indexed will be the mask color, so it
493 // will not be used later in the color conversion (from RGB to
494 // Indexed).
495 int usedColors = m_histogram.createOptimizedPalette(palette);
496
497 if (addMask) {
498 palette->resize(usedColors+1);
499
500 Remap remap(palette->size());
501 for (int i=0; i<usedColors; ++i)
502 remap.map(i, i + (i >= maskIndex ? 1: 0));
503
504 palette->applyRemap(remap);
505
506 if (maskIndex < palette->size())
507 palette->setEntry(maskIndex, rgba(0, 0, 0, (m_withAlpha ? 0: 255)));
508 }
509 else {
510 palette->resize(std::max(1, usedColors));
511 }
512}
513
514} // namespace render
515