1// Aseprite Document Library
2// Copyright (c) 2020-2022 Igara Studio S.A.
3// Copyright (c) 2001-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 "doc/palette.h"
13
14#include "base/base.h"
15#include "doc/image.h"
16#include "doc/palette_gradient_type.h"
17#include "doc/remap.h"
18#include "gfx/hsv.h"
19#include "gfx/rgb.h"
20
21#include <algorithm>
22#include <limits>
23#include <cmath>
24
25namespace doc {
26
27using namespace gfx;
28
29enum class FitCriteria {
30 OLD,
31 RGB,
32 linearizedRGB,
33 CIEXYZ,
34 CIELAB
35};
36
37Palette::Palette()
38 : Palette(0, 256)
39{
40}
41
42Palette::Palette(frame_t frame, int ncolors)
43 : Object(ObjectType::Palette)
44{
45 ASSERT(ncolors >= 0);
46
47 m_frame = frame;
48 m_colors.resize(ncolors, doc::rgba(0, 0, 0, 255));
49 m_modifications = 0;
50}
51
52Palette::Palette(const Palette& palette)
53 : Object(palette)
54 , m_comment(palette.m_comment)
55{
56 m_frame = palette.m_frame;
57 m_colors = palette.m_colors;
58 m_modifications = 0;
59}
60
61Palette::Palette(const Palette& palette, const Remap& remap)
62 : Object(palette)
63 , m_comment(palette.m_comment)
64{
65 m_frame = palette.m_frame;
66
67 resize(palette.size());
68 for (int i=0; i<size(); ++i)
69 setEntry(remap[i], palette.getEntry(i));
70
71 m_modifications = 0;
72}
73
74Palette::~Palette()
75{
76}
77
78Palette& Palette::operator=(const Palette& that)
79{
80 m_frame = that.m_frame;
81 m_colors = that.m_colors;
82 m_names = that.m_names;
83 m_filename = that.m_filename;
84 m_comment = that.m_comment;
85
86 ++m_modifications;
87 return *this;
88}
89
90Palette* Palette::createGrayscale()
91{
92 Palette* graypal = new Palette(frame_t(0), 256);
93 for (int c=0; c<256; c++)
94 graypal->setEntry(c, rgba(c, c, c, 255));
95 return graypal;
96}
97
98void Palette::resize(int ncolors)
99{
100 ASSERT(ncolors >= 0);
101
102 m_colors.resize(ncolors, doc::rgba(0, 0, 0, 255));
103 ++m_modifications;
104}
105
106void Palette::addEntry(color_t color)
107{
108 resize(size()+1);
109 setEntry(size()-1, color);
110}
111
112bool Palette::hasAlpha() const
113{
114 for (int i=0; i<(int)m_colors.size(); ++i)
115 if (rgba_geta(getEntry(i)) < 255)
116 return true;
117 return false;
118}
119
120bool Palette::hasSemiAlpha() const
121{
122 for (int i=0; i<(int)m_colors.size(); ++i) {
123 int a = rgba_geta(getEntry(i));
124 if (a > 0 && a < 255)
125 return true;
126 }
127 return false;
128}
129
130void Palette::setFrame(frame_t frame)
131{
132 ASSERT(frame >= 0);
133
134 m_frame = frame;
135}
136
137void Palette::setEntry(int i, color_t color)
138{
139 ASSERT(i >= 0 && i < size());
140
141 m_colors[i] = color;
142 ++m_modifications;
143}
144
145void Palette::copyColorsTo(Palette* dst) const
146{
147 dst->m_colors = m_colors;
148 ++dst->m_modifications;
149}
150
151int Palette::countDiff(const Palette* other, int* from, int* to) const
152{
153 int c, diff = 0;
154 int min = std::min(this->m_colors.size(), other->m_colors.size());
155 int max = std::max(this->m_colors.size(), other->m_colors.size());
156
157 if (from) *from = -1;
158 if (to) *to = -1;
159
160 // Compare palettes
161 for (c=0; c<min; ++c) {
162 if (this->m_colors[c] != other->m_colors[c]) {
163 if (from && *from < 0) *from = c;
164 if (to) *to = c;
165 ++diff;
166 }
167 }
168
169 if (max != min) {
170 diff += max - min;
171 if (from && *from < 0) *from = min;
172 if (to) *to = max-1;
173 }
174
175 return diff;
176}
177
178bool Palette::isBlack() const
179{
180 for (std::size_t c=0; c<m_colors.size(); ++c)
181 if (getEntry(c) != rgba(0, 0, 0, 255))
182 return false;
183
184 return true;
185}
186
187void Palette::makeBlack()
188{
189 std::fill(m_colors.begin(), m_colors.end(), rgba(0, 0, 0, 255));
190 ++m_modifications;
191}
192
193// Creates a linear ramp in the palette.
194void Palette::makeGradient(int from, int to)
195{
196 int r, g, b, a;
197 int r1, g1, b1, a1;
198 int r2, g2, b2, a2;
199 int i, n;
200
201 ASSERT(from >= 0 && from < size());
202 ASSERT(to >= 0 && to < size());
203
204 if (from > to)
205 std::swap(from, to);
206
207 n = to - from;
208 if (n < 2)
209 return;
210
211 r1 = rgba_getr(getEntry(from));
212 g1 = rgba_getg(getEntry(from));
213 b1 = rgba_getb(getEntry(from));
214 a1 = rgba_geta(getEntry(from));
215
216 r2 = rgba_getr(getEntry(to));
217 g2 = rgba_getg(getEntry(to));
218 b2 = rgba_getb(getEntry(to));
219 a2 = rgba_geta(getEntry(to));
220
221 for (i=from+1; i<to; ++i) {
222 r = r1 + (r2-r1) * (i-from) / n;
223 g = g1 + (g2-g1) * (i-from) / n;
224 b = b1 + (b2-b1) * (i-from) / n;
225 a = a1 + (a2-a1) * (i-from) / n;
226
227 setEntry(i, rgba(r, g, b, a));
228 }
229}
230
231void Palette::makeHueGradient(int from, int to)
232{
233 int r1, g1, b1, a1;
234 int r2, g2, b2, a2;
235 int i, n;
236
237 ASSERT(from >= 0 && from < size());
238 ASSERT(to >= 0 && to < size());
239
240 if (from > to)
241 std::swap(from, to);
242
243 n = to - from;
244 if (n < 2)
245 return;
246
247 r1 = rgba_getr(getEntry(from));
248 g1 = rgba_getg(getEntry(from));
249 b1 = rgba_getb(getEntry(from));
250 a1 = rgba_geta(getEntry(from));
251
252 r2 = rgba_getr(getEntry(to));
253 g2 = rgba_getg(getEntry(to));
254 b2 = rgba_getb(getEntry(to));
255 a2 = rgba_geta(getEntry(to));
256
257 gfx::Hsv hsv1(gfx::Rgb(r1, g1, b1));
258 gfx::Hsv hsv2(gfx::Rgb(r2, g2, b2));
259
260 double h1 = hsv1.hue();
261 double s1 = hsv1.saturation();
262 double v1 = hsv1.value();
263
264 double h2 = hsv2.hue();
265 double s2 = hsv2.saturation();
266 double v2 = hsv2.value();
267
268 if (h2 >= h1) {
269 if (h2-h1 > 180.0)
270 h2 = h2 - 360.0;
271 }
272 else {
273 if (h1-h2 > 180.0)
274 h2 = h2 + 360.0;
275 }
276
277 gfx::Hsv hsv;
278 for (i=from+1; i<to; ++i) {
279 double t = double(i - from) / double(n);
280 hsv.hue(h1 + (h2 - h1) * t);
281 hsv.saturation(s1 + (s2 - s1) * t);
282 hsv.value(v1 + (v2 - v1) * t);
283 int alpha = int(a1 + double(a2 - a1) * t);
284 gfx::Rgb rgb(hsv);
285 setEntry(i, rgba(rgb.red(), rgb.green(), rgb.blue(), alpha));
286 }
287}
288
289int Palette::findExactMatch(int r, int g, int b, int a, int mask_index) const
290{
291 for (int i=0; i<(int)m_colors.size(); ++i)
292 if (getEntry(i) == rgba(r, g, b, a) && i != mask_index)
293 return i;
294
295 return -1;
296}
297
298bool Palette::findExactMatch(color_t color) const
299{
300 for (int i=0; i<(int)m_colors.size(); ++i) {
301 if (getEntry(i) == color)
302 return true;
303 }
304 return false;
305}
306
307//////////////////////////////////////////////////////////////////////
308// Based on Allegro's bestfit_color
309
310static std::vector<uint32_t> col_diff;
311static uint32_t* col_diff_g;
312static uint32_t* col_diff_r;
313static uint32_t* col_diff_b;
314static uint32_t* col_diff_a;
315
316void Palette::initBestfit()
317{
318 col_diff.resize(4*128, 0);
319 col_diff_g = &col_diff[128*0];
320 col_diff_r = &col_diff[128*1];
321 col_diff_b = &col_diff[128*2];
322 col_diff_a = &col_diff[128*3];
323
324 for (int i=1; i<64; ++i) {
325 int k = i * i;
326 col_diff_g[i] = col_diff_g[128-i] = k * 59 * 59;
327 col_diff_r[i] = col_diff_r[128-i] = k * 30 * 30;
328 col_diff_b[i] = col_diff_b[128-i] = k * 11 * 11;
329 col_diff_a[i] = col_diff_a[128-i] = k * 8 * 8;
330 }
331}
332
333// Auxiliary function for rgbToOtherSpace()
334static double f(double t)
335{
336 if (t > 0.00885645171)
337 return std::pow(t, 0.3333333333333333);
338 else
339 return (t / 0.12841855 + 0.137931034);
340}
341
342// Auxiliary function for findBestfit()
343static void rgbToOtherSpace(double& r, double& g, double& b, FitCriteria fc)
344{
345 if (fc == FitCriteria::RGB)
346 return;
347 double Rl, Gl, Bl;
348 // Linearization:
349 r = r / 255.0;
350 g = g / 255.0;
351 b = b / 255.0;
352 if (r <= 0.04045)
353 Rl = r / 12.92;
354 else
355 Rl = std::pow((r + 0.055) / 1.055, 2.4);
356 if (g <= 0.04045)
357 Gl = g / 12.92;
358 else
359 Gl = std::pow((g + 0.055) / 1.055, 2.4);
360 if (b <= 0.04045)
361 Bl = b / 12.92;
362 else
363 Bl = std::pow((b + 0.055) / 1.055, 2.4);
364 if (fc == FitCriteria::linearizedRGB) {
365 r = Rl;
366 g = Gl;
367 b = Bl;
368 return;
369 }
370 // Conversion lineal RGB to CIE XYZ
371 r = 41.24564*Rl + 35.75761 * Gl + 18.04375 * Bl;
372 g = 21.26729*Rl + 71.51522 * Gl + 7.2175 * Bl;
373 b = 1.93339*Rl + 11.91920 * Gl + 95.03041 * Bl;
374 switch (fc) {
375
376 case FitCriteria::CIEXYZ:
377 return;
378
379 case FitCriteria::CIELAB: {
380 // Converting CIEXYZ to CIELAB:
381 // For Standard Illuminant D65:
382 // const double xn = 95.0489;
383 // const double yn = 100.0;
384 // const double zn = 108.884;
385 double xxn = r / 95.0489;
386 double yyn = g / 100.0;
387 double zzn = b / 108.884;
388 double fyyn = f(yyn);
389
390 double Lstar = 116.0 * fyyn - 16.0;
391 double aStar = 500.0 * (f(xxn) - fyyn);
392 double bStar = 200.0 * (fyyn - f(zzn));
393
394 r = Lstar;
395 g = aStar;
396 b = bStar;
397 return;
398 }
399 }
400}
401
402int Palette::findBestfit(int r, int g, int b, int a, int mask_index) const
403{
404 ASSERT(r >= 0 && r <= 255);
405 ASSERT(g >= 0 && g <= 255);
406 ASSERT(b >= 0 && b <= 255);
407 ASSERT(a >= 0 && a <= 255);
408
409 FitCriteria fc = FitCriteria::OLD;
410
411 if (fc == FitCriteria::OLD) {
412 ASSERT(!col_diff.empty());
413
414 r >>= 3;
415 g >>= 3;
416 b >>= 3;
417 a >>= 3;
418
419 // Mask index is like alpha = 0, so we can use it as transparent color.
420 if (a == 0 && mask_index >= 0)
421 return mask_index;
422
423 int bestfit = 0;
424 int lowest = std::numeric_limits<int>::max();
425 int size = std::min(256, int(m_colors.size()));
426
427 for (int i=0; i<size; ++i) {
428 color_t rgb = m_colors[i];
429
430 int coldiff = col_diff_g[((rgba_getg(rgb)>>3) - g) & 127];
431 if (coldiff < lowest) {
432 coldiff += col_diff_r[(((rgba_getr(rgb)>>3) - r) & 127)];
433 if (coldiff < lowest) {
434 coldiff += col_diff_b[(((rgba_getb(rgb)>>3) - b) & 127)];
435 if (coldiff < lowest) {
436 coldiff += col_diff_a[(((rgba_geta(rgb)>>3) - a) & 127)];
437 if (coldiff < lowest && i != mask_index) {
438 if (coldiff == 0)
439 return i;
440
441 bestfit = i;
442 lowest = coldiff;
443 }
444 }
445 }
446 }
447 }
448
449 return bestfit;
450 }
451
452 if (a == 0 && mask_index >= 0)
453 return mask_index;
454
455 int bestfit = 0;
456 double lowest = std::numeric_limits<double>::max();
457 int size = m_colors.size();
458 // Linearice:
459 double x = double(r);
460 double y = double(g);
461 double z = double(b);
462
463 rgbToOtherSpace(x, y, z, fc);
464
465 for (int i=0; i<size; ++i) {
466 color_t rgb = m_colors[i];
467 double Xpal = double(rgba_getr(rgb));
468 double Ypal = double(rgba_getg(rgb));
469 double Zpal = double(rgba_getb(rgb));
470 // Palette color conversion RGB-->XYZ and r,g,b is assumed CIE XYZ
471 rgbToOtherSpace(Xpal, Ypal, Zpal, fc);
472 double xDiff = x - Xpal;
473 double yDiff = y - Ypal;
474 double zDiff = z - Zpal;
475 double aDiff = double(a - rgba_geta(rgb)) / 128.0;
476
477 double diff = xDiff * xDiff + yDiff * yDiff + zDiff * zDiff + aDiff * aDiff;
478 if (diff < lowest) {
479 lowest = diff;
480 bestfit = i;
481 }
482 }
483 return bestfit;
484}
485
486int Palette::findMaskColor() const
487{
488 int size = m_colors.size();
489 for (int i = 0; i < size; ++i) {
490 if (m_colors[i] == 0)
491 return i;
492 }
493 return -1;
494}
495
496void Palette::applyRemap(const Remap& remap)
497{
498 Palette original(*this);
499 for (int i=0; i<size(); ++i)
500 setEntry(remap[i], original.getEntry(i));
501}
502
503void Palette::setEntryName(const int i, const std::string& name)
504{
505 if (i >= int(m_names.size()))
506 m_names.resize(i+1);
507 m_names[i] = name;
508}
509
510const std::string& Palette::getEntryName(const int i) const
511{
512 if (i >= 0 && i < int(m_names.size()))
513 return m_names[i];
514 else {
515 static std::string emptyString;
516 return emptyString;
517 }
518}
519
520} // namespace doc
521