pixie_anim_lib/quant/
zeng.rs

1//! Zeng Palette Reordering.
2//!
3//! Reorders palette indices to improve LZW compression by ensuring
4//! visually similar colors have adjacent indices.
5
6use crate::quant::Palette;
7
8/// Reorders the palette using a greedy TSP approximation.
9/// Returns (new_palette, index_mapping) where index_mapping[old_idx] = new_idx.
10pub fn reorder_palette(palette: &Palette) -> (Palette, Vec<u8>) {
11    let colors = &palette.colors;
12    if colors.is_empty() {
13        return (Palette { colors: Vec::new() }, Vec::new());
14    }
15
16    let mut new_colors = Vec::with_capacity(colors.len());
17    let mut mapping = vec![0u8; colors.len()];
18    let mut visited = vec![false; colors.len()];
19
20    // Start with the first color (usually the most significant from K-Means)
21    let mut current_idx = 0;
22    new_colors.push(colors[current_idx]);
23    visited[current_idx] = true;
24    mapping[current_idx] = 0;
25
26    for i in 1..colors.len() {
27        let mut min_dist = u32::MAX;
28        let mut next_idx = 0;
29
30        let current_color = colors[current_idx];
31
32        for (j, &color) in colors.iter().enumerate() {
33            if !visited[j] {
34                let dr = current_color.r as i32 - color.r as i32;
35                let dg = current_color.g as i32 - color.g as i32;
36                let db = current_color.b as i32 - color.b as i32;
37                let dist = (dr * dr + dg * dg + db * db) as u32;
38
39                if dist < min_dist {
40                    min_dist = dist;
41                    next_idx = j;
42                }
43            }
44        }
45
46        visited[next_idx] = true;
47        mapping[next_idx] = i as u8;
48        new_colors.push(colors[next_idx]);
49        current_idx = next_idx;
50    }
51
52    (Palette { colors: new_colors }, mapping)
53}
pixie_anim_lib/quant/zeng.rs

pixie_anim_lib/quant/
zeng.rs
