1// Aseprite Document Library
2// Copyright (c) 2001-2017 David Capello
3//
4// This file is released under the terms of the MIT license.
5// Read LICENSE.txt for more information.
6
7#ifdef HAVE_CONFIG_H
8#include "config.h"
9#endif
10
11#include "doc/sort_palette.h"
12
13#include "doc/image.h"
14#include "doc/palette.h"
15#include "doc/remap.h"
16#include "gfx/hsv.h"
17#include "gfx/rgb.h"
18
19#include <algorithm>
20#include <limits>
21
22namespace doc {
23
24using namespace gfx;
25
26namespace {
27
28struct PalEntryWithIndex {
29 int index;
30 color_t color;
31};
32
33struct PalEntryWithIndexPredicate {
34 SortPaletteBy channel;
35 bool ascending;
36
37 PalEntryWithIndexPredicate(SortPaletteBy channel, bool ascending)
38 : channel(channel)
39 , ascending(ascending) {
40 }
41
42 bool operator()(const PalEntryWithIndex& a, const PalEntryWithIndex& b) {
43 const color_t c1 = a.color;
44 const color_t c2 = b.color;
45
46 // Handle cases where, e.g., transparent yellow
47 // is visually indistinguishable from transparent
48 // black. Push 0 alpha toward index 0, regardless
49 // of sort order being ascending or descending.
50 const uint8_t a1 = rgba_geta(c1);
51 const uint8_t a2 = rgba_geta(c2);
52
53 if (a1 == 0 && a2 == 0) {
54 return true;
55 }
56 else if (a1 == 0) {
57 return true;
58 }
59 else if (a2 == 0) {
60 return false;
61 }
62
63 const uint8_t r1 = rgba_getr(c1);
64 const uint8_t g1 = rgba_getg(c1);
65 const uint8_t b1 = rgba_getb(c1);
66
67 const uint8_t r2 = rgba_getr(c2);
68 const uint8_t g2 = rgba_getg(c2);
69 const uint8_t b2 = rgba_getb(c2);
70
71 switch (channel) {
72
73 case SortPaletteBy::RED:
74 return (ascending ? r1 < r2: r2 < r1);
75
76 case SortPaletteBy::GREEN:
77 return (ascending ? g1 < g2: g2 < g1);
78
79 case SortPaletteBy::BLUE:
80 return (ascending ? b1 < b2: b2 < b1);
81
82 case SortPaletteBy::ALPHA:
83 return (ascending ? a1 < a2: a2 < a1);
84
85 case SortPaletteBy::HUE: {
86 const Hsv hsv1(Rgb(r1, g1, b1));
87 const Hsv hsv2(Rgb(r2, g2, b2));
88
89 // When a color is desaturated, its hue
90 // is the quotient of division by zero.
91 // It is not zero, which is red.
92 const int sat1 = hsv1.saturationInt();
93 const int sat2 = hsv2.saturationInt();
94
95 if (sat1 == 0 && sat2 == 0) {
96 const int val1 = hsv1.valueInt();
97 const int val2 = hsv2.valueInt();
98 return (ascending ? val1 < val2: val2 < val1);
99 }
100 else if (sat1 == 0) {
101 return ascending;
102 }
103 else if (sat2 == 0) {
104 return !ascending;
105 }
106
107 const int hue1 = hsv1.hueInt();
108 const int hue2 = hsv2.hueInt();
109 return (ascending ? hue1 < hue2: hue2 < hue1);
110 }
111
112 case SortPaletteBy::SATURATION: {
113 // This could be inlined with
114 // (max(r, g, b) - min(r, g, b)) / max(r, g, b)
115 // but (1.) there is already opportunity for
116 // confusion: HSV and HSL saturation share
117 // the same name but arise from different
118 // calculations; (2.) HSV components can
119 // almost never be compared in isolation.
120 const Hsv hsv1(Rgb(r1, g1, b1));
121 const Hsv hsv2(Rgb(r2, g2, b2));
122 const int sat1 = hsv1.saturationInt();
123 const int sat2 = hsv2.saturationInt();
124 if (sat1 == sat2) {
125 const int val1 = hsv1.valueInt();
126 const int val2 = hsv2.valueInt();
127 return (ascending ? val1 < val2: val2 < val1);
128 }
129 return (ascending ? sat1 < sat2: sat2 < sat1);
130 }
131
132 case SortPaletteBy::VALUE: {
133 const Hsv hsv1(Rgb(r1, g1, b1));
134 const Hsv hsv2(Rgb(r2, g2, b2));
135 const int val1 = hsv1.valueInt();
136 const int val2 = hsv2.valueInt();
137 if (val1 == val2) {
138 const int sat1 = hsv1.saturationInt();
139 const int sat2 = hsv2.saturationInt();
140 return (ascending ? sat1 < sat2: sat2 < sat1);
141 }
142 return (ascending ? val1 < val2: val2 < val1);
143 }
144
145 case SortPaletteBy::LUMA: {
146 // Perceptual, or relative, luminance.
147 // Finds the square for fast approximation
148 // of 2.4 or 2.2 exponent needed to convert
149 // from gamma to linear. Assumes that the
150 // source for palette colors is sRGB.
151 const int lum1 = rgb_luma(r1 * r1, g1 * g1, b1 * b1);
152 const int lum2 = rgb_luma(r2 * r2, g2 * g2, b2 * b2);
153 return (ascending ? lum1 < lum2: lum2 < lum1);
154 }
155
156 case SortPaletteBy::LIGHTNESS: {
157 // HSL Lightness
158 const int mn1 = std::min(r1, std::min(g1, b1));
159 const int mx1 = std::max(r1, std::max(g1, b1));
160 const int light1 = (mn1 + mx1) / 2;
161
162 const int mn2 = std::min(r2, std::min(g2, b2));
163 const int mx2 = std::max(r2, std::max(g2, b2));
164 const int light2 = (mn2 + mx2) / 2;
165
166 return (ascending ? light1 < light2: light2 < light1);
167 }
168
169 default: {
170 ASSERT(false);
171 return false;
172 }
173 }
174 }
175};
176
177} // anonymous namespace
178
179Remap sort_palette(const Palette* palette,
180 const SortPaletteBy channel,
181 const bool ascending)
182{
183 std::vector<PalEntryWithIndex> tmp(palette->size());
184 for (int i=0; i<palette->size(); ++i) {
185 tmp[i].index = i;
186 tmp[i].color = palette->getEntry(i);
187 }
188
189 std::stable_sort(tmp.begin(), tmp.end(), PalEntryWithIndexPredicate(channel, ascending));
190
191 Remap remap(palette->size());
192 for (int i=0; i<palette->size(); ++i)
193 remap.map(tmp[i].index, i);
194
195 return remap;
196}
197
198} // namespace doc
199