mod decompose;
pub(in crate::raster) use decompose::split_cubic;
use pltrs_font::ScanPoint;
use super::RasterError;
const POOL_LONGS: usize = 2048;
const HEADER_LONGS: usize = 5;
const MAX_BEZIER: usize = 32;
pub(super) const FLOW_UP: u8 = 0x08;
pub(super) const OVERSHOOT_TOP: u8 = 0x10;
pub(super) const OVERSHOOT_BOTTOM: u8 = 0x20;
pub(super) const DROPOUT: u8 = 0x40;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct Precision {
bits: u32,
step: i64,
}
impl Precision {
pub(super) const fn new(high: bool) -> Self {
if high {
Self {
bits: 12,
step: 256,
}
} else {
Self { bits: 6, step: 32 }
}
}
pub(super) const fn one(self) -> i64 {
1 << self.bits
}
pub(super) const fn half(self) -> i64 {
self.one() >> 1
}
pub(super) const fn floor(self, x: i64) -> i64 {
x & -self.one()
}
pub(super) const fn ceiling(self, x: i64) -> i64 {
(x + self.one() - 1) & -self.one()
}
pub(super) const fn trunc(self, x: i64) -> i64 {
x >> self.bits
}
const fn frac(self, x: i64) -> i64 {
x & (self.one() - 1)
}
const fn scaled(self, x: i64) -> i64 {
x * (self.one() >> 6) - self.half()
}
const fn is_bottom_overshoot(self, x: i64) -> bool {
self.ceiling(x) - x >= self.half()
}
const fn is_top_overshoot(self, x: i64) -> bool {
x - self.floor(x) >= self.half()
}
pub(super) const fn smart(self, p: i64, q: i64) -> i64 {
self.floor((p + q + self.one() * 63 / 64) >> 1)
}
const fn step(self) -> i64 {
self.step
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct Profile {
pub(super) flags: u8,
pub(super) start: i64,
pub(super) height: i64,
pub(super) offset: i64,
first_crossing: usize,
pub(super) x: i64,
pub(super) next: usize,
contour_first: usize,
}
#[derive(Debug)]
pub(super) struct Profiles {
pub(super) list: Vec<Profile>,
pool: Vec<i64>,
pub(super) turns: Vec<i64>,
}
impl Profiles {
pub(super) fn crossing(&self, profile: &Profile, offset: i64) -> i64 {
usize::try_from(offset)
.ok()
.and_then(|offset| self.pool.get(profile.first_crossing + offset))
.copied()
.unwrap_or(profile.x)
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
struct Vec2 {
x: i64,
y: i64,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Direction {
Unknown,
Ascending,
Descending,
}
pub(super) struct Converter {
precision: Precision,
dropout_control: u8,
min_y: i64,
max_y: i64,
pool: Vec<i64>,
pool_max: usize,
slots: Vec<Profile>,
recorded: Vec<usize>,
current: Option<usize>,
turns: Vec<i64>,
state: Direction,
last: Vec2,
contour_first: Option<usize>,
}
impl Converter {
pub(super) fn new(precision: Precision, dropout_control: u8) -> Self {
Self {
precision,
dropout_control,
min_y: 0,
max_y: 0,
pool: Vec::new(),
pool_max: POOL_LONGS - 1,
slots: Vec::new(),
recorded: Vec::new(),
current: None,
turns: Vec::new(),
state: Direction::Unknown,
last: Vec2::default(),
contour_first: None,
}
}
pub(super) const fn precision(&self) -> Precision {
self.precision
}
pub(super) fn convert(
&mut self,
points: &[ScanPoint],
contour_ends: &[usize],
band: (i64, i64),
flipped: bool,
) -> Result<Profiles, RasterError> {
self.min_y = band.0 * self.precision.one();
self.max_y = band.1 * self.precision.one();
self.pool.clear();
self.pool_max = POOL_LONGS - 1;
self.slots.clear();
self.recorded.clear();
self.current = None;
self.turns.clear();
let mut start = 0;
for &end in contour_ends {
let contour = points.get(start..end).ok_or(RasterError::InvalidOutline)?;
start = end;
self.state = Direction::Unknown;
self.contour_first = None;
self.decompose(contour, flipped)?;
let Some(first) = self.contour_first else {
continue;
};
let current = self.current.ok_or(RasterError::InvalidOutline)?;
if self.precision.frac(self.last.y) == 0
&& (self.min_y..=self.max_y).contains(&self.last.y)
&& self.slots[first].flags & FLOW_UP == self.slots[current].flags & FLOW_UP
{
self.pool.pop();
}
self.end_profile()?;
}
Ok(self.finish())
}
fn finish(&mut self) -> Profiles {
let slot_index = |slot: usize| self.recorded.iter().position(|&s| s == slot);
let mut list: Vec<Profile> = self.recorded.iter().map(|&s| self.slots[s]).collect();
for (index, profile) in list.iter_mut().enumerate() {
let next_slot = self
.recorded
.get(index + 1)
.copied()
.filter(|&next| self.slots[next].contour_first == profile.contour_first)
.unwrap_or(profile.contour_first);
profile.next = slot_index(next_slot).unwrap_or(index);
}
Profiles {
list,
pool: std::mem::take(&mut self.pool),
turns: std::mem::take(&mut self.turns),
}
}
fn full(&self, extra: usize) -> bool {
self.pool.len() + extra >= self.pool_max
}
fn insert_turns(&mut self, bottom: i64, top: i64) -> Result<(), RasterError> {
match self.turns.last_mut() {
None => self.turns.push(top),
Some(highest) if top > *highest => *highest = top,
Some(_) => {}
}
let below = &self.turns[..self.turns.len() - 1];
let at = below.partition_point(|&turn| turn <= bottom);
if at > 0 && below[at - 1] == bottom {
return Ok(());
}
self.pool_max -= 1;
if self.pool_max <= self.pool.len() {
return Err(RasterError::Overflow);
}
self.turns.insert(at, bottom);
Ok(())
}
fn new_profile(&mut self, direction: Direction) -> Result<(), RasterError> {
let current = match self.current {
Some(slot) if self.slots[slot].height == 0 => slot,
_ => {
let first_crossing = self.pool.len() + HEADER_LONGS;
self.pool.resize(first_crossing, 0);
if self.full(0) {
return Err(RasterError::Overflow);
}
self.slots.push(Profile {
flags: 0,
start: 0,
height: 0,
offset: 0,
first_crossing,
x: 0,
next: 0,
contour_first: 0,
});
self.slots.len() - 1
}
};
self.current = Some(current);
let p = self.precision;
let last = self.last;
let mut flags = self.dropout_control;
let start = match direction {
Direction::Ascending => {
flags |= FLOW_UP;
if p.is_bottom_overshoot(last.y) {
flags |= OVERSHOOT_BOTTOM;
}
p.ceiling(last.y)
}
Direction::Descending => {
if p.is_top_overshoot(last.y) {
flags |= OVERSHOOT_TOP;
}
p.floor(last.y)
}
Direction::Unknown => return Err(RasterError::InvalidOutline),
};
let start = start.min(self.max_y).max(self.min_y);
let profile = &mut self.slots[current];
profile.flags = flags;
profile.start = p.trunc(start);
if last.y == start {
self.pool.push(last.x);
}
self.state = direction;
Ok(())
}
fn end_profile(&mut self) -> Result<(), RasterError> {
let slot = self.current.ok_or(RasterError::InvalidOutline)?;
let p = self.precision;
let last_y = self.last.y;
let first_crossing = self.slots[slot].first_crossing;
let Some(height) = self.pool.len().checked_sub(first_crossing) else {
return Err(RasterError::InvalidOutline);
};
if height == 0 {
return Ok(());
}
let profile = &mut self.slots[slot];
let h = height as i64;
profile.height = h;
let (bottom, top) = if profile.flags & FLOW_UP != 0 {
if p.is_top_overshoot(last_y) {
profile.flags |= OVERSHOOT_TOP;
}
profile.offset = 0;
profile.x = self.pool[first_crossing];
(profile.start, profile.start + h)
} else {
if p.is_bottom_overshoot(last_y) {
profile.flags |= OVERSHOOT_BOTTOM;
}
let top = profile.start + 1;
profile.start = top - h;
profile.offset = h - 1;
profile.x = self.pool[first_crossing + height - 1];
(top - h, top)
};
self.insert_turns(bottom, top)?;
let first = *self.contour_first.get_or_insert(slot);
self.slots[slot].contour_first = first;
self.recorded.push(slot);
Ok(())
}
fn turn(&mut self, direction: Direction) -> Result<(), RasterError> {
if self.state != direction {
if self.state != Direction::Unknown {
self.end_profile()?;
}
self.new_profile(direction)?;
}
Ok(())
}
}
#[cfg(test)]
mod tests {
use pltrs_font::ScanPointKind;
use super::*;
fn on(x: i64, y: i64) -> ScanPoint {
ScanPoint {
x,
y,
kind: ScanPointKind::On,
}
}
#[test]
fn precisions_put_pixel_centres_on_whole_units() {
let low = Precision::new(false);
assert_eq!(low.scaled(32), 0);
assert_eq!(
(low.floor(-1), low.ceiling(1), low.trunc(130)),
(-64, 64, 2)
);
let high = Precision::new(true);
assert_eq!(high.scaled(96), 4096);
assert_eq!(high.smart(0, 4096), 0);
assert_eq!(low.smart(-64, 0), -64);
}
#[test]
fn a_square_makes_one_profile_up_and_one_down() {
let square = [on(64, 64), on(192, 64), on(192, 192), on(64, 192)];
let mut converter = Converter::new(Precision::new(false), 1);
let profiles = converter.convert(&square, &[4], (0, 3), false).unwrap();
assert_eq!(profiles.list.len(), 2);
assert_eq!(profiles.turns, vec![1, 3]);
let up = &profiles.list[0];
assert_eq!(up.flags & FLOW_UP, FLOW_UP);
assert_eq!((up.start, up.height), (1, 2));
assert_eq!(profiles.crossing(up, 0), 160);
let down = &profiles.list[1];
assert_eq!((down.start, down.height), (1, 2));
assert_eq!(profiles.crossing(down, 0), 32);
assert_eq!((up.next, down.next), (1, 0));
}
#[test]
fn a_full_pool_overflows() {
let sliver = [on(0, 0), on(64, 0), on(64, 64 * 3000)];
let mut converter = Converter::new(Precision::new(false), 1);
assert_eq!(
converter
.convert(&sliver, &[3], (0, 3000), false)
.unwrap_err(),
RasterError::Overflow
);
assert!(converter.convert(&sliver, &[3], (0, 900), false).is_ok());
}
}