use crate::util::round_i32;
const MIN_PALETTE_PIXELS: usize = 32;
const MAX_PALETTE: usize = 254;
const NO_LABEL: u8 = 255;
const MIN_EXACT_SHARE: f32 = 0.85;
const MIN_FLAT_SAMPLE_SHARE: f32 = 0.5;
const MAX_BAND_SHARE: f32 = 0.08;
const MAX_TEXTURED_SHARE: f32 = 0.005;
const MAX_MIX_RESIDUAL_SQ: f32 = 36.0;
const COVERAGE_STEPS: u32 = 15;
pub(crate) fn coverage_steps(distance: f32) -> u32 {
(COVERAGE_STEPS as f32 / distance.max(0.01))
.round()
.clamp(1.0, 255.0) as u32
}
pub(crate) fn band_bytes_ratio(steps: u32) -> f64 {
((steps.max(1) as f64).log2() + 1.0) / 5.0
}
pub(crate) const VARDCT_BYTES_MARGIN: f64 = 1.39;
pub(crate) fn vardct_bytes(rgb: &[u8], width: usize, height: usize, distance: f32) -> f64 {
let px = rgb.as_chunks::<3>().0;
let d = distance.max(0.1);
let cost: [f32; 256] = std::array::from_fn(|v| (1.0 + v as f32 / (4.0 * d)).log2());
let step = |a: [u8; 3], b: [u8; 3]| {
cost[(0..3).map(|k| a[k].abs_diff(b[k])).max().unwrap() as usize] as f64
};
let mut bits = 0.0;
for y in 0..height {
let row = &px[y * width..(y + 1) * width];
for x in 1..width {
bits += step(row[x - 1], row[x]);
}
if y > 0 {
let above = &px[(y - 1) * width..y * width];
for x in 0..width {
bits += step(above[x], row[x]);
}
}
}
1.16 * bits / 8.0 * d.powf(-0.41) as f64
}
struct ColorTable {
keys: Vec<u32>,
values: Vec<u32>,
len: usize,
}
impl ColorTable {
const BITS: u32 = 16;
const EMPTY: u32 = u32::MAX;
fn new() -> Self {
Self {
keys: vec![Self::EMPTY; 1 << Self::BITS],
values: vec![0; 1 << Self::BITS],
len: 0,
}
}
fn slot(&self, key: u32) -> Option<usize> {
let mut i = (key.wrapping_mul(0x9E37_79B1) >> (32 - Self::BITS)) as usize;
loop {
let k = self.keys[i];
if k == key {
return Some(i);
}
if k == Self::EMPTY {
return None;
}
i = (i + 1) & ((1 << Self::BITS) - 1);
}
}
fn key(color: [u8; 3]) -> u32 {
u32::from_be_bytes([0, color[0], color[1], color[2]])
}
fn add(&mut self, color: [u8; 3]) -> bool {
let key = Self::key(color);
let mut i = (key.wrapping_mul(0x9E37_79B1) >> (32 - Self::BITS)) as usize;
loop {
let k = self.keys[i];
if k == key {
self.values[i] += 1;
return true;
}
if k == Self::EMPTY {
if self.len >= 1 << (Self::BITS - 1) {
return false;
}
self.keys[i] = key;
self.values[i] = 1;
self.len += 1;
return true;
}
i = (i + 1) & ((1 << Self::BITS) - 1);
}
}
fn entries(&self) -> impl Iterator<Item = ([u8; 3], usize)> + '_ {
self.keys
.iter()
.zip(&self.values)
.filter(|(k, _)| **k != Self::EMPTY)
.map(|(&k, &v)| (k.to_be_bytes()[1..].try_into().unwrap(), v as usize))
}
fn clear_values(&mut self) {
self.values.fill(Self::EMPTY);
}
fn set(&mut self, color: [u8; 3], value: u32) {
let i = self.slot(Self::key(color)).expect("palette color");
self.values[i] = value;
}
fn get(&self, color: [u8; 3]) -> Option<u32> {
self.slot(Self::key(color))
.map(|i| self.values[i])
.filter(|&v| v != Self::EMPTY)
}
}
pub(crate) struct VectorSplit {
pub(crate) base: Vec<u8>,
pub(crate) layer: Vec<u8>,
pub(crate) coverage: Vec<u8>,
}
pub(crate) fn split(rgb: &[u8], width: usize, height: usize, steps: u32) -> Option<VectorSplit> {
let n = width * height;
if n < 64 * 64 {
return None;
}
let px = rgb.as_chunks::<3>().0;
let mut flat = 0usize;
let mut sampled = 0usize;
for y in (1..height - 1).step_by(8) {
for x in (1..width - 1).step_by(8) {
let i = y * width + x;
let p = px[i];
let same = usize::from(px[i - 1] == p)
+ usize::from(px[i + 1] == p)
+ usize::from(px[i - width] == p)
+ usize::from(px[i + width] == p);
flat += usize::from(same >= 2);
sampled += 1;
}
}
if (flat as f32) < MIN_FLAT_SAMPLE_SHARE * sampled as f32 {
return None;
}
let mut counts = ColorTable::new();
for y in 1..height - 1 {
let row = y * width;
for x in 1..width - 1 {
let i = row + x;
let p = px[i];
let same = usize::from(px[i - 1] == p)
+ usize::from(px[i + 1] == p)
+ usize::from(px[i - width] == p)
+ usize::from(px[i + width] == p);
if same >= 2 && !counts.add(p) {
return None; }
}
}
let min_pixels = MIN_PALETTE_PIXELS.max(n / 10_000);
let mut palette: Vec<([u8; 3], usize)> =
counts.entries().filter(|&(_, c)| c >= min_pixels).collect();
if palette.is_empty() {
return None;
}
palette.sort_unstable_by_key(|&(c, count)| (std::cmp::Reverse(count), c));
palette.truncate(MAX_PALETTE);
let colors: Vec<[f32; 3]> = palette.iter().map(|&(c, _)| c.map(f32::from)).collect();
counts.clear_values();
for (k, &(c, _)) in palette.iter().enumerate() {
counts.set(c, k as u32);
}
let labels: Vec<u8> = px
.iter()
.map(|&p| counts.get(p).map_or(NO_LABEL, |k| k as u8))
.collect();
let mut area = vec![0usize; colors.len()];
let mut exact = 0usize;
for &l in &labels {
if l != NO_LABEL {
area[l as usize] += 1;
exact += 1;
}
}
if (exact as f32) < MIN_EXACT_SHARE * n as f32 {
return None;
}
let dominant = (0..colors.len()).max_by_key(|&k| area[k]).unwrap() as u8;
let mut base = rgb.to_vec();
let mut coverage = vec![0u8; n];
let mut top_of = vec![NO_LABEL; n];
let mut band = 0usize;
let mut textured = 0usize;
let mut top_counts = vec![0usize; colors.len()];
let mut neighbors = [NO_LABEL; 8];
for i in 0..n {
if labels[i] != NO_LABEL {
continue;
}
let (x, y) = (i % width, i / width);
let mut m = 0;
for dy in -1i32..=1 {
for dx in -1i32..=1 {
if dx == 0 && dy == 0 {
continue;
}
let (xx, yy) = (x as i32 + dx, y as i32 + dy);
if xx < 0 || yy < 0 || xx >= width as i32 || yy >= height as i32 {
continue;
}
let l = labels[yy as usize * width + xx as usize];
if l != NO_LABEL && !neighbors[..m].contains(&l) {
neighbors[m] = l;
m += 1;
}
}
}
if m == 0 {
textured += 1;
continue; }
if m == 1 && neighbors[0] != dominant {
neighbors[1] = dominant;
m = 2;
}
let p = px[i].map(f32::from);
let mut best: Option<(f32, u8, u8, f32)> = None; for s in 0..m {
for t in s + 1..m {
let (a, b) = (neighbors[s], neighbors[t]);
let ca = colors[a as usize];
let cb = colors[b as usize];
let d: [f32; 3] = std::array::from_fn(|k| cb[k] - ca[k]);
let dd = d[0] * d[0] + d[1] * d[1] + d[2] * d[2];
if dd < 100.0 {
continue;
}
let c = ((0..3).map(|k| (p[k] - ca[k]) * d[k]).sum::<f32>() / dd).clamp(0.0, 1.0);
let r: f32 = (0..3).map(|k| (p[k] - ca[k] - c * d[k]).powi(2)).sum();
if best.is_none_or(|(br, ..)| r < br) {
best = Some((r, a, b, c));
}
}
}
let Some((r, a, b, c)) = best else {
textured += 1;
continue;
};
if r > MAX_MIX_RESIDUAL_SQ {
textured += 1;
continue; }
let (bottom, top, c_top) = if area[a as usize] >= area[b as usize] {
(a, b, c)
} else {
(b, a, 1.0 - c)
};
let step = round_i32(c_top * steps as f32) as u32;
let base_color = if step == steps { top } else { bottom };
base[i * 3..i * 3 + 3].copy_from_slice(&palette[base_color as usize].0);
if step > 0 && step < steps {
coverage[i] = ((step * 255 + steps / 2) / steps) as u8;
top_of[i] = top;
top_counts[top as usize] += 1;
band += 1;
}
}
if (band as f32) > MAX_BAND_SHARE * n as f32
|| (textured as f32) > MAX_TEXTURED_SHARE * n as f32
{
return None;
}
let fill = (0..colors.len()).max_by_key(|&k| top_counts[k]).unwrap();
let mut layer = Vec::with_capacity(n * 3);
for &t in &top_of {
let k = if t == NO_LABEL { fill } else { t as usize };
layer.extend_from_slice(&palette[k].0);
}
Some(VectorSplit {
base,
layer,
coverage,
})
}