Add similarity search for colors when palette is full

1 files changed, 32 insertions, 10 deletions

diff --git a/src/main.c b/src/main.c
index 65dc94d..ae4cf76 100644
--- a/src/main.c
+++ b/src/main.c
@@ -105,14 +105,39 @@ extract_tile(Tiles *tiles, Palette *palette, Image *img,
 
             Color clr = rgb15(red, green, blue);
             bool found = false;
-            // TODO: If the palette is full, find the closest perceived
-            // color instead.
-            for (size_t p = 0; p < palette->capacity; ++p) {
-                if (clr == palette->data[p]) {
-                    pal_index = p;
-                    found = true;
-                    break;
+            // Brute force search, but since the palette size will likely be
+            // small, shouldn't be a big problem.
+            if (palette->size < palette->capacity) {
+                // If the palette is not full try to find if the color is
+                // already stored.
+                for (size_t p = 0; p < palette->capacity; ++p) {
+                    if (clr == palette->data[p]) {
+                        pal_index = p;
+                        found = true;
+                        break;
+                    }
                 }
+            } else {
+                // If the palette is full, find the closest perceived color
+                // instead.
+                size_t best_index = 0;
+                double best_distance = 1e99;
+                for (size_t p = 0; p < palette->capacity; ++p) {
+                    Color pal_clr = palette->data[p];
+                    int pal_red = pal_clr & 0x1F;
+                    int pal_green = (pal_clr >> 5) & 0x1F;
+                    int pal_blue = (pal_clr >> 10) & 0x1F;
+                    double r = (pal_red - red);
+                    double g = (pal_green - green);
+                    double b = (pal_blue - blue);
+                    double distance = r * r * 0.3 + g * g * 0.59 + b * b * 0.11;
+                    if (distance < best_distance) {
+                        best_distance = distance;
+                        best_index = p;
+                    }
+                }
+                pal_index = best_index;
+                found = true;
             }
             if (!found) {
                 palette->data[palette->size++] = clr;
@@ -217,9 +242,6 @@ main(int argc, char *argv[]) {
         .capacity = n_tiles,
     };
 
-    // NOTE: We are going to brute-force this for now. Checking if the color is
-    // in the palette and add it to the next slot if possible. In the future we
-    // may want to use a hash-table instead.
     int pal_idx = 1;
     int offset_x = 0;
     int offset_y = 0;