1// Aseprite Render Library
2// Copyright (c) 2019-2022 Igara Studio S.A.
3// Copyright (c) 2017 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/ordered_dither.h"
13
14#include "render/dithering.h"
15#include "render/dithering_matrix.h"
16
17#include <algorithm>
18#include <limits>
19#include <vector>
20
21namespace render {
22
23// Base 2x2 dither matrix, called D(2):
24int BayerMatrix::D2[4] = { 0, 2,
25 3, 1 };
26
27static int colorDistance(int r1, int g1, int b1, int a1,
28 int r2, int g2, int b2, int a2)
29{
30 int result = 0;
31
32 // The factor for RGB components came from doc::rba_luma()
33 if (a1 && a2) {
34 result += int(std::abs(r1-r2) * 2126 +
35 std::abs(g1-g2) * 7152 +
36 std::abs(b1-b2) * 722);
37 }
38
39 result += (std::abs(a1-a2) * 20000);
40 return result;
41}
42
43OrderedDither::OrderedDither(int transparentIndex)
44 : m_transparentIndex(transparentIndex)
45{
46}
47
48doc::color_t OrderedDither::ditherRgbPixelToIndex(
49 const DitheringMatrix& matrix,
50 const doc::color_t color,
51 const int x,
52 const int y,
53 const doc::RgbMap* rgbmap,
54 const doc::Palette* palette)
55{
56 // Alpha=0, output transparent color
57 if (m_transparentIndex >= 0 &&
58 doc::rgba_geta(color) == 0)
59 return m_transparentIndex;
60
61 // Get the nearest color in the palette with the given RGB
62 // values.
63 int r = doc::rgba_getr(color);
64 int g = doc::rgba_getg(color);
65 int b = doc::rgba_getb(color);
66 int a = doc::rgba_geta(color);
67 doc::color_t nearest1idx =
68 (rgbmap ? rgbmap->mapColor(r, g, b, a):
69 palette->findBestfit(r, g, b, a, m_transparentIndex));
70
71 doc::color_t nearest1rgb = palette->getEntry(nearest1idx);
72 int r1 = doc::rgba_getr(nearest1rgb);
73 int g1 = doc::rgba_getg(nearest1rgb);
74 int b1 = doc::rgba_getb(nearest1rgb);
75 int a1 = doc::rgba_geta(nearest1rgb);
76
77 // Between the original color ('color' parameter) and 'nearest'
78 // index, we have an error (r1-r, g1-g, b1-b). Here we try to
79 // find the other nearest color with the same error but with
80 // different sign.
81 int r2 = r - (r1-r);
82 int g2 = g - (g1-g);
83 int b2 = b - (b1-b);
84 int a2 = a - (a1-a);
85 r2 = std::clamp(r2, 0, 255);
86 g2 = std::clamp(g2, 0, 255);
87 b2 = std::clamp(b2, 0, 255);
88 a2 = std::clamp(a2, 0, 255);
89 doc::color_t nearest2idx =
90 (rgbmap ? rgbmap->mapColor(r2, g2, b2, a2):
91 palette->findBestfit(r2, g2, b2, a2, m_transparentIndex));
92
93 // If both possible RGB colors use the same index, we cannot
94 // make any dither with these two colors.
95 if (nearest1idx == nearest2idx)
96 return nearest1idx;
97
98 doc::color_t nearest2rgb = palette->getEntry(nearest2idx);
99 r2 = doc::rgba_getr(nearest2rgb);
100 g2 = doc::rgba_getg(nearest2rgb);
101 b2 = doc::rgba_getb(nearest2rgb);
102 a2 = doc::rgba_geta(nearest2rgb);
103
104 // Here we calculate the distance between the original 'color'
105 // and 'nearest1rgb'. The maximum possible distance is given by
106 // the distance between 'nearest1rgb' and 'nearest2rgb'.
107 int d = colorDistance(r1, g1, b1, a1, r, g, b, a);
108 int D = colorDistance(r1, g1, b1, a1, r2, g2, b2, a2);
109 if (D == 0)
110 return nearest1idx;
111
112 // We convert the d/D factor to the matrix range to compare it
113 // with the threshold. If d > threshold, it means that we're
114 // closer to 'nearest2rgb' than to 'nearest1rgb'.
115 d = matrix.maxValue() * d / D;
116 int threshold = matrix(y, x);
117
118 return (d > threshold ? nearest2idx:
119 nearest1idx);
120}
121
122OrderedDither2::OrderedDither2(int transparentIndex)
123 : m_transparentIndex(transparentIndex)
124{
125}
126
127// New ordered dithering algorithm using the best match between two
128// indexes to create a mix that can reproduce the original RGB
129// color.
130//
131// TODO it's too slow for big color palettes:
132// O(W*H*P) where P is the number of palette entries
133//
134// Some ideas from:
135// http://bisqwit.iki.fi/story/howto/dither/jy/
136//
137doc::color_t OrderedDither2::ditherRgbPixelToIndex(
138 const DitheringMatrix& matrix,
139 const doc::color_t color,
140 const int x,
141 const int y,
142 const doc::RgbMap* rgbmap,
143 const doc::Palette* palette)
144{
145 // Alpha=0, output transparent color
146 if (m_transparentIndex >= 0 &&
147 doc::rgba_geta(color) == 0) {
148 return m_transparentIndex;
149 }
150
151 // Get RGBA values
152 const int r = doc::rgba_getr(color);
153 const int g = doc::rgba_getg(color);
154 const int b = doc::rgba_getb(color);
155 const int a = doc::rgba_geta(color);
156
157 // Find the best palette entry for the given color.
158 const int index =
159 (rgbmap ? rgbmap->mapColor(r, g, b, a):
160 palette->findBestfit(r, g, b, a, m_transparentIndex));
161
162 const doc::color_t color0 = palette->getEntry(index);
163 const int r0 = doc::rgba_getr(color0);
164 const int g0 = doc::rgba_getg(color0);
165 const int b0 = doc::rgba_getb(color0);
166 const int a0 = doc::rgba_geta(color0);
167
168 // Find the best combination between the found nearest index and
169 // an alternative palette color to create the original RGB color.
170 int bestMix = 0;
171 int altIndex = -1;
172 int closestDistance = std::numeric_limits<int>::max();
173 for (int i=0; i<palette->size(); ++i) {
174 if (i == m_transparentIndex)
175 continue;
176
177 const doc::color_t color1 = palette->getEntry(i);
178 const int r1 = doc::rgba_getr(color1);
179 const int g1 = doc::rgba_getg(color1);
180 const int b1 = doc::rgba_getb(color1);
181 const int a1 = doc::rgba_geta(color1);
182
183 // Find the best "mix factor" between both palette indexes to
184 // reproduce the original RGB color. A possible algorithm
185 // would be to iterate all possible mix factors from 0 to
186 // maxMixValue, but this is too slow, so we try to figure out
187 // a good mix factor using the RGB values of color0 and
188 // color1.
189 int maxMixValue = matrix.maxValue();
190
191 int mix = 0;
192 int div = 0;
193 // If Alpha=0, RGB values are not representative for this entry.
194 if (a && a0 && a1) {
195 if (r1-r0) mix += 2126 * maxMixValue * (r-r0) / (r1-r0), div += 2126;
196 if (g1-g0) mix += 7152 * maxMixValue * (g-g0) / (g1-g0), div += 7152;
197 if (b1-b0) mix += 722 * maxMixValue * (b-b0) / (b1-b0), div += 722;
198 }
199 if (a1-a0) mix += 20000 * maxMixValue * (a-a0) / (a1-a0), div += 20000;
200 if (mix) {
201 if (div)
202 mix /= div;
203 mix = std::clamp(mix, 0, maxMixValue);
204 }
205
206 const int rM = r0 + (r1-r0) * mix / maxMixValue;
207 const int gM = g0 + (g1-g0) * mix / maxMixValue;
208 const int bM = b0 + (b1-b0) * mix / maxMixValue;
209 const int aM = a0 + (a1-a0) * mix / maxMixValue;
210 const int d =
211 colorDistance(r, g, b, a, rM, gM, bM, aM)
212 // Don't use an alternative index if it's too far away from the first index
213 + colorDistance(r0, g0, b0, a0, r1, g1, b1, a1) / 10;
214
215 if (closestDistance > d) {
216 closestDistance = d;
217 bestMix = mix;
218 altIndex = i;
219 }
220 }
221
222 // Using the bestMix factor the dithering matrix tells us if we
223 // should paint with altIndex or index in this x,y position.
224 if (altIndex >= 0 && matrix(y, x) < bestMix)
225 return altIndex;
226 else
227 return index;
228}
229
230void dither_rgb_image_to_indexed(
231 DitheringAlgorithmBase& algorithm,
232 const Dithering& dithering,
233 const doc::Image* srcImage,
234 doc::Image* dstImage,
235 const doc::RgbMap* rgbmap,
236 const doc::Palette* palette,
237 TaskDelegate* delegate)
238{
239 const int w = srcImage->width();
240 const int h = srcImage->height();
241
242 algorithm.start(srcImage, dstImage, dithering.factor());
243
244 if (algorithm.dimensions() == 1) {
245 const doc::LockImageBits<doc::RgbTraits> srcBits(srcImage);
246 doc::LockImageBits<doc::IndexedTraits> dstBits(dstImage);
247 auto srcIt = srcBits.begin();
248 auto dstIt = dstBits.begin();
249
250 for (int y=0; y<h; ++y) {
251 for (int x=0; x<w; ++x, ++srcIt, ++dstIt) {
252 ASSERT(srcIt != srcBits.end());
253 ASSERT(dstIt != dstBits.end());
254 *dstIt = algorithm.ditherRgbPixelToIndex(
255 dithering.matrix(), *srcIt, x, y, rgbmap, palette);
256
257 if (delegate) {
258 if (!delegate->continueTask())
259 return;
260 }
261 }
262
263 if (delegate) {
264 delegate->notifyTaskProgress(
265 double(y+1) / double(h));
266 }
267 }
268 }
269 else {
270 auto dstIt = doc::get_pixel_address_fast<doc::IndexedTraits>(dstImage, 0, 0);
271 const bool zigZag = algorithm.zigZag();
272
273 for (int y=0; y<h; ++y) {
274 if (zigZag && (y & 1)) { // Odd row: go from right-to-left
275 dstIt += w-1;
276 for (int x=w-1; x>=0; --x, --dstIt) {
277 ASSERT(dstIt == doc::get_pixel_address_fast<doc::IndexedTraits>(dstImage, x, y));
278 *dstIt = algorithm.ditherRgbToIndex2D(x, y, rgbmap, palette);
279 if (delegate) {
280 if (!delegate->continueTask())
281 return;
282 }
283 }
284 dstIt += w+1;
285 }
286 else { // Even row: go fromo left-to-right
287 for (int x=0; x<w; ++x, ++dstIt) {
288 ASSERT(dstIt == doc::get_pixel_address_fast<doc::IndexedTraits>(dstImage, x, y));
289 *dstIt = algorithm.ditherRgbToIndex2D(x, y, rgbmap, palette);
290
291 if (delegate) {
292 if (!delegate->continueTask())
293 return;
294 }
295 }
296 }
297 if (delegate) {
298 delegate->notifyTaskProgress(
299 double(y+1) / double(h));
300 }
301 }
302 }
303
304 algorithm.finish();
305}
306
307} // namespace render
308