use pltrs_core::Point;
use pltrs_font::{ScanOutline, ScanPointKind};
use super::mono::split_cubic as split_coordinate;
const ONE_PIXEL: i64 = 256;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Fixed {
x: i64,
y: i64,
}
fn mul_fix(a: i64, b: i64) -> i64 {
let ab = a * b;
(ab + 0x8000 - i64::from(ab < 0)) >> 16
}
#[derive(Clone, Copy, Debug)]
pub(super) struct GlyphTransform {
xx: i64,
xy: i64,
yx: i64,
yy: i64,
dx: i64,
dy: i64,
}
impl GlyphTransform {
pub(super) fn new(angle: f64, pen: Point) -> Self {
Self::with_effects(angle, 0.0, 1.0, pen)
}
pub(super) fn with_effects(angle: f64, slant: f64, extend: f64, pen: Point) -> Self {
let (sin, cos) = angle.to_radians().sin_cos();
let (c, s) = (65536.0 * cos, 65536.0 * -sin);
let (sc, cc) = (65536.0 * sin, 65536.0 * cos);
let fixed = |v: f64| v.round_ties_even() as i64;
Self {
xx: fixed(c * extend + s * 0.0),
xy: fixed(c * (extend * slant) + s),
yx: fixed(sc * extend + cc * 0.0),
yy: fixed(sc * (extend * slant) + cc),
dx: (pen.x * 64.0).round() as i64,
dy: (pen.y * 64.0).round() as i64,
}
}
pub(super) fn transform(&self, x: i64, y: i64) -> (i64, i64) {
(
mul_fix(x, self.xx) + mul_fix(y, self.xy) + self.dx,
mul_fix(x, self.yx) + mul_fix(y, self.yy) + self.dy,
)
}
}
pub(super) fn is_axis_aligned(angle: f64) -> bool {
let transform = GlyphTransform::new(angle, Point::ORIGIN);
(transform.yx == 0 && transform.xx != 0) || (transform.xx == 0 && transform.yx != 0)
}
fn left_shift(a: i64, b: u32) -> i64 {
((a as u64) << b) as i64
}
#[derive(Default)]
struct Flattener {
contours: Vec<Vec<(i64, i64)>>,
current: Option<Fixed>,
}
impl Flattener {
fn move_to(&mut self, p: Fixed) {
self.contours.push(vec![(p.x, p.y)]);
self.current = Some(p);
}
fn line_to(&mut self, p: Fixed) {
match self.contours.last_mut() {
Some(contour) if self.current.is_some() => contour.push((p.x, p.y)),
_ => return self.move_to(p),
}
self.current = Some(p);
}
fn conic_to(&mut self, control: Fixed, to: Fixed) {
let Some(p0) = self.current else {
return self.move_to(to);
};
let (bx, by) = (control.x - p0.x, control.y - p0.y);
let (ax, ay) = (to.x - control.x - bx, to.y - control.y - by);
let mut d = ax.abs().max(ay.abs());
if d <= ONE_PIXEL / 4 {
return self.line_to(to);
}
let mut shift: u32 = 16;
loop {
d >>= 2;
shift -= 1;
if d <= ONE_PIXEL / 4 || shift == 0 {
break;
}
}
let count = 0x10000_u32 >> shift;
let (mut rx, mut ry) = (left_shift(ax, 2 * shift), left_shift(ay, 2 * shift));
let mut qx = left_shift(bx, shift + 17).wrapping_add(rx);
let mut qy = left_shift(by, shift + 17).wrapping_add(ry);
rx = rx.wrapping_mul(2);
ry = ry.wrapping_mul(2);
let (mut px, mut py) = (left_shift(p0.x, 32), left_shift(p0.y, 32));
for _ in 0..count {
px = px.wrapping_add(qx);
py = py.wrapping_add(qy);
qx = qx.wrapping_add(rx);
qy = qy.wrapping_add(ry);
self.line_to(Fixed {
x: px >> 32,
y: py >> 32,
});
}
}
fn cubic_to(&mut self, c1: Fixed, c2: Fixed, to: Fixed) {
let Some(p0) = self.current else {
return self.move_to(to);
};
let mut stack: Vec<[Fixed; 4]> = vec![[to, c2, c1, p0]];
while let Some(arc) = stack.pop() {
let flat = |a: i64, b: i64, c: i64| (a - 3 * b + c).abs() <= ONE_PIXEL / 2;
let is_flat = flat(2 * arc[0].x, arc[1].x, arc[3].x)
&& flat(2 * arc[0].y, arc[1].y, arc[3].y)
&& flat(arc[0].x, arc[2].x, 2 * arc[3].x)
&& flat(arc[0].y, arc[2].y, 2 * arc[3].y);
if is_flat || stack.len() >= 16 {
self.line_to(arc[0]);
} else {
let (first, second) = split_cubic(arc);
stack.push(first);
stack.push(second);
}
}
}
}
fn split_cubic(arc: [Fixed; 4]) -> ([Fixed; 4], [Fixed; 4]) {
let split = |v: [i64; 4]| -> [i64; 7] {
let mut base = [v[0], v[1], v[2], v[3], 0, 0, 0];
split_coordinate(&mut base);
base
};
let xs = split(arc.map(|p| p.x));
let ys = split(arc.map(|p| p.y));
let at = |i: usize| Fixed { x: xs[i], y: ys[i] };
([at(0), at(1), at(2), at(3)], [at(3), at(4), at(5), at(6)])
}
#[derive(Clone, Copy)]
struct Tagged {
x: i64,
y: i64,
kind: ScanPointKind,
}
impl Tagged {
fn upscaled(self) -> Fixed {
Fixed {
x: left_shift(self.x, 2),
y: left_shift(self.y, 2),
}
}
fn halfway(self, other: Self) -> Self {
Self {
x: (self.x + other.x) >> 1,
y: (self.y + other.y) >> 1,
kind: ScanPointKind::On,
}
}
}
pub(super) fn freetype_contours(
outline: &ScanOutline,
transform: &GlyphTransform,
) -> Option<Vec<Vec<(i64, i64)>>> {
let points: Vec<Tagged> = outline
.points
.iter()
.map(|point| {
let (x, y) = transform.transform(point.x, point.y);
Tagged {
x,
y,
kind: point.kind,
}
})
.collect();
let mut flattener = Flattener::default();
let mut start = 0;
for &end in &outline.contour_ends {
decompose(points.get(start..end)?, &mut flattener)?;
start = end;
}
Some(flattener.contours)
}
fn decompose(contour: &[Tagged], flattener: &mut Flattener) -> Option<()> {
let (&first, &last) = (contour.first()?, contour.last()?);
let mut limit = contour.len() - 1;
let mut next = 1;
let start = match first.kind {
ScanPointKind::Cubic => return None,
ScanPointKind::Conic => {
next = 0;
if last.kind == ScanPointKind::On {
limit -= 1;
last
} else {
first.halfway(last)
}
}
ScanPointKind::On => first,
};
flattener.move_to(start.upscaled());
while next <= limit {
let point = contour[next];
next += 1;
match point.kind {
ScanPointKind::On => flattener.line_to(point.upscaled()),
ScanPointKind::Conic => {
let mut control = point;
loop {
let Some(&to) = contour.get(next).filter(|_| next <= limit) else {
flattener.conic_to(control.upscaled(), start.upscaled());
return Some(());
};
next += 1;
match to.kind {
ScanPointKind::On => {
flattener.conic_to(control.upscaled(), to.upscaled());
break;
}
ScanPointKind::Conic => {
flattener.conic_to(control.upscaled(), control.halfway(to).upscaled());
control = to;
}
ScanPointKind::Cubic => return None,
}
}
}
ScanPointKind::Cubic => {
let second = contour.get(next).filter(|p| p.kind == ScanPointKind::Cubic);
let second = *second.filter(|_| next <= limit)?;
next += 1;
let to = if next <= limit { contour[next] } else { start };
flattener.cubic_to(point.upscaled(), second.upscaled(), to.upscaled());
if next > limit {
return Some(());
}
next += 1;
}
}
}
flattener.line_to(start.upscaled());
Some(())
}
#[cfg(test)]
mod tests {
use pltrs_font::{Dropouts, ScanPoint, ScanRules};
use super::*;
fn outline(points: &[(i64, i64, ScanPointKind)]) -> ScanOutline {
ScanOutline {
points: points
.iter()
.map(|&(x, y, kind)| ScanPoint { x, y, kind })
.collect(),
contour_ends: vec![points.len()],
rules: ScanRules {
high_precision: false,
dropouts: Dropouts::Simple { stubs: false },
},
}
}
fn contours(points: &[(i64, i64, ScanPointKind)], angle: f64) -> Vec<Vec<(i64, i64)>> {
freetype_contours(&outline(points), &GlyphTransform::new(angle, Point::ORIGIN))
.expect("a valid outline")
}
use ScanPointKind::{Conic, Cubic, On};
#[test]
fn quarter_turns_are_axis_aligned() {
for angle in [0.0, 90.0, 180.0, 270.0, -90.0, 360.0] {
assert!(is_axis_aligned(angle), "{angle}");
}
for angle in [30.0, 45.0, 135.0, 89.0] {
assert!(!is_axis_aligned(angle), "{angle}");
}
}
#[test]
fn effects_slant_and_extend_the_rotation() {
let plain = GlyphTransform::new(30.0, Point::ORIGIN);
let same = GlyphTransform::with_effects(30.0, 0.0, 1.0, Point::ORIGIN);
assert_eq!(plain.transform(64, 64), same.transform(64, 64));
let slanted = GlyphTransform::with_effects(0.0, 0.25, 2.0, Point::new(1.0, 2.0));
assert_eq!(slanted.transform(64, 64), (2 * 64 + 32 + 64, 64 + 128));
}
#[test]
fn flat_conics_are_lines() {
let contours = contours(&[(0, 0, On), (64, 6, Conic), (128, 0, On)], 0.0);
assert_eq!(contours, [vec![(0, 0), (512, 0), (0, 0)]]);
}
#[test]
fn curved_conics_end_exactly_on_their_end_point() {
let contours = contours(&[(0, 0, On), (640, 1280, Conic), (1280, 0, On)], 0.0);
let [contour] = contours.as_slice() else {
panic!("one contour, got {contours:?}");
};
assert_eq!(contour.len(), 1 + 16 + 1);
assert_eq!(contour[16], (20 * 256, 0));
}
#[test]
fn implied_points_lie_between_transformed_control_points() {
let points = [(0, 0, On), (64, 1, Conic), (128, 0, Conic), (192, 0, On)];
let turned = contours(&points, 180.0);
let upright = contours(&points, 0.0);
let mirrored: Vec<(i64, i64)> = upright[0].iter().map(|&(x, y)| (-x, -y)).collect();
assert_ne!(turned[0], mirrored);
assert!(turned[0].contains(&(-96 * 4, -4)), "{:?}", turned[0]);
}
#[test]
fn contours_may_start_at_a_control_point() {
let starts_off = contours(&[(64, 64, Conic), (128, 0, On), (0, 0, On)], 0.0);
let starts_on = contours(&[(0, 0, On), (64, 64, Conic), (128, 0, On)], 0.0);
assert_eq!(starts_off[0][0], (0, 0));
assert_eq!(starts_off[0].last(), starts_on[0].last());
}
#[test]
fn cubics_are_bisected() {
let contours = contours(
&[(0, 0, On), (0, 640, Cubic), (640, 640, Cubic), (640, 0, On)],
0.0,
);
let contour = &contours[0];
assert!(contour.len() > 8);
assert_eq!(contour[contour.len() - 2], (10 * 256, 0));
assert!(
contour
.iter()
.all(|&(_, y)| (0..=7 * 256 + 128).contains(&y))
);
}
#[test]
fn malformed_contours_are_refused() {
let transform = GlyphTransform::new(0.0, Point::ORIGIN);
let lone_cubic = outline(&[(0, 0, On), (64, 64, Cubic), (128, 0, On)]);
assert!(freetype_contours(&lone_cubic, &transform).is_none());
let cubic_start = outline(&[(0, 0, Cubic), (64, 64, Cubic), (128, 0, On)]);
assert!(freetype_contours(&cubic_start, &transform).is_none());
}
}