use std::time::Duration;
use teksilo_canvas::{Point, Vec2};
use crate::pointer::EventTime;
pub const HISTORY_SIZE: usize = 20;
pub const HORIZON: Duration = Duration::from_millis(100);
pub const MIN_SAMPLE_SIZE: usize = 3;
pub const STOP_GAP: Duration = Duration::from_millis(40);
const DEGREE: usize = 2;
const N: usize = DEGREE + 1;
#[non_exhaustive]
#[derive(Copy, Clone, Debug, PartialEq)]
pub struct VelocityEstimate {
pub pixels_per_second: Vec2,
pub confidence: f32,
pub duration: Duration,
}
#[derive(Copy, Clone, Debug)]
struct Sample {
time: EventTime,
position: Point,
}
#[derive(Clone, Debug)]
pub struct VelocityTracker {
samples: [Option<Sample>; HISTORY_SIZE],
index: usize,
}
impl Default for VelocityTracker {
fn default() -> Self {
Self::new()
}
}
impl VelocityTracker {
pub const fn new() -> Self {
Self {
samples: [None; HISTORY_SIZE],
index: 0,
}
}
pub fn add(&mut self, time: EventTime, position: Point) {
self.index += 1;
if self.index == HISTORY_SIZE {
self.index = 0;
}
self.samples[self.index] = Some(Sample { time, position });
}
pub fn add_coalesced(&mut self, samples: impl IntoIterator<Item = (EventTime, Point)>) {
for (time, position) in samples {
self.add(time, position);
}
}
pub fn clear(&mut self) {
self.samples = [None; HISTORY_SIZE];
self.index = 0;
}
pub fn estimate(&self) -> Option<VelocityEstimate> {
let newest = self.samples[self.index]?;
let mut xs = [0.0f64; HISTORY_SIZE];
let mut ys = [0.0f64; HISTORY_SIZE];
let mut ws = [0.0f64; HISTORY_SIZE];
let mut ts = [0.0f64; HISTORY_SIZE];
let mut count = 0usize;
let mut index = self.index;
let mut previous = newest;
let mut oldest = newest;
while count < HISTORY_SIZE {
let Some(sample) = self.samples[index] else {
break;
};
let age = newest.time.saturating_since(sample.time);
let gap = if sample.time >= previous.time {
sample.time.saturating_since(previous.time)
} else {
previous.time.saturating_since(sample.time)
};
previous = sample;
if age > HORIZON || gap > STOP_GAP {
break;
}
oldest = sample;
xs[count] = f64::from(sample.position.x);
ys[count] = f64::from(sample.position.y);
ws[count] = 1.0;
ts[count] = -(age.as_secs_f64() * 1000.0);
index = if index == 0 { HISTORY_SIZE } else { index } - 1;
count += 1;
}
if count < MIN_SAMPLE_SIZE {
return None;
}
let fx = least_squares_fit(&ts[..count], &xs[..count], &ws[..count])?;
let fy = least_squares_fit(&ts[..count], &ys[..count], &ws[..count])?;
Some(VelocityEstimate {
pixels_per_second: Vec2::new(
(fx.coefficients[1] * 1000.0) as f32,
(fy.coefficients[1] * 1000.0) as f32,
),
confidence: (fx.confidence * fy.confidence) as f32,
duration: newest.time.saturating_since(oldest.time),
})
}
pub fn velocity(&self) -> Vec2 {
self.estimate()
.map(|e| e.pixels_per_second)
.unwrap_or(Vec2::ZERO)
}
pub fn sample_count(&self) -> usize {
self.samples.iter().filter(|s| s.is_some()).count()
}
}
struct PolynomialFit {
coefficients: [f64; N],
confidence: f64,
}
fn least_squares_fit(x: &[f64], y: &[f64], w: &[f64]) -> Option<PolynomialFit> {
let m = x.len();
debug_assert!(m == y.len() && m == w.len());
if !(N..=HISTORY_SIZE).contains(&m) {
return None;
}
let mut a = [[0.0f64; HISTORY_SIZE]; N];
for h in 0..m {
a[0][h] = w[h];
for i in 1..N {
a[i][h] = a[i - 1][h] * x[h];
}
}
let mut q = [[0.0f64; HISTORY_SIZE]; N];
let mut r = [[0.0f64; N]; N];
for j in 0..N {
q[j] = a[j];
for i in 0..j {
let qi = q[i];
let qj = q[j];
let dot: f64 = (0..m).map(|h| qj[h] * qi[h]).sum();
for h in 0..m {
q[j][h] -= dot * qi[h];
}
}
let norm = (0..m).map(|h| q[j][h] * q[j][h]).sum::<f64>().sqrt();
if norm.is_nan() || norm < 1e-6 {
return None;
}
let inverse_norm = 1.0 / norm;
for value in q[j].iter_mut().take(m) {
*value *= inverse_norm;
}
for i in 0..N {
r[j][i] = if i < j {
0.0
} else {
let qj = q[j];
let ai = a[i];
(0..m).map(|h| qj[h] * ai[h]).sum()
};
}
}
let mut wy = [0.0f64; HISTORY_SIZE];
for h in 0..m {
wy[h] = y[h] * w[h];
}
let mut coefficients = [0.0f64; N];
for i in (0..N).rev() {
let qi = q[i];
let mut c: f64 = (0..m).map(|h| qi[h] * wy[h]).sum();
for j in (i + 1..N).rev() {
c -= r[i][j] * coefficients[j];
}
let diagonal = r[i][i];
if diagonal.is_nan() || diagonal.abs() < 1e-12 {
return None;
}
coefficients[i] = c / diagonal;
}
let y_mean = y.iter().sum::<f64>() / m as f64;
let mut sum_squared_error = 0.0f64;
let mut sum_squared_total = 0.0f64;
for h in 0..m {
let mut term = 1.0f64;
let mut err = y[h] - coefficients[0];
for c in coefficients.iter().take(N).skip(1) {
term *= x[h];
err -= term * c;
}
sum_squared_error += w[h] * w[h] * err * err;
let v = y[h] - y_mean;
sum_squared_total += w[h] * w[h] * v * v;
}
let confidence = if sum_squared_total <= 1e-6 {
1.0
} else {
1.0 - (sum_squared_error / sum_squared_total)
};
if !coefficients.iter().all(|c| c.is_finite()) {
return None;
}
Some(PolynomialFit {
coefficients,
confidence,
})
}
#[cfg(test)]
mod tests {
use super::*;
fn constant_velocity(velocity: f32, hz: u64, count: u64) -> VelocityTracker {
let mut t = VelocityTracker::new();
let step_ms = 1000 / hz;
for i in 0..count {
let seconds = (i * step_ms) as f32 / 1000.0;
t.add(
EventTime::from_millis(i * step_ms),
Point::new(0.0, velocity * seconds),
);
}
t
}
#[test]
fn a_constant_velocity_stream_is_estimated_within_one_percent() {
for v in [120.0f32, 600.0, 2400.0, -1800.0] {
let t = constant_velocity(v, 100, 8);
let e = t.estimate().expect("eight samples inside the horizon");
let error = (e.pixels_per_second.y - v).abs() / v.abs();
assert!(
error < 0.01,
"v={v}: estimated {} ({}% off)",
e.pixels_per_second.y,
error * 100.0
);
assert!(
e.pixels_per_second.x.abs() < 1.0,
"a y-only stream must report ~0 on x, got {}",
e.pixels_per_second.x
);
}
}
#[test]
fn a_straight_line_fits_with_full_confidence() {
let t = constant_velocity(500.0, 100, 6);
let e = t.estimate().unwrap();
assert!(
(e.confidence - 1.0).abs() < 1e-3,
"confidence {} for an exact line",
e.confidence
);
}
#[test]
fn fewer_than_three_samples_yields_none() {
let mut t = VelocityTracker::new();
assert_eq!(t.estimate(), None, "an empty tracker has no estimate");
t.add(EventTime::from_millis(0), Point::new(0.0, 0.0));
assert_eq!(t.estimate(), None, "one sample is not an estimate");
t.add(EventTime::from_millis(10), Point::new(0.0, 6.0));
assert_eq!(t.estimate(), None, "two samples are not an estimate");
t.add(EventTime::from_millis(20), Point::new(0.0, 12.0));
assert!(t.estimate().is_some(), "three samples are the minimum");
}
#[test]
fn a_forty_millisecond_gap_clears_the_history() {
let mut t = VelocityTracker::new();
for i in 0..6 {
t.add(
EventTime::from_millis(i * 5),
Point::new(0.0, i as f32 * 30.0),
);
}
assert!(t.estimate().is_some(), "six dense samples estimate fine");
t.add(EventTime::from_millis(75), Point::new(0.0, 150.0));
t.add(EventTime::from_millis(80), Point::new(0.0, 150.0));
assert_eq!(
t.estimate(),
None,
"the pre-gap samples must not be fitted across"
);
}
#[test]
fn a_gap_under_the_stop_threshold_keeps_the_history() {
let mut t = VelocityTracker::new();
t.add(EventTime::from_millis(0), Point::new(0.0, 0.0));
t.add(EventTime::from_millis(39), Point::new(0.0, 39.0));
t.add(EventTime::from_millis(78), Point::new(0.0, 78.0));
let e = t.estimate().expect("39 ms gaps are continuous motion");
assert!(
(e.pixels_per_second.y - 1000.0).abs() < 10.0,
"got {}",
e.pixels_per_second.y
);
}
#[test]
fn the_horizon_drops_stale_samples() {
let mut t = VelocityTracker::new();
for i in 0..30u64 {
t.add(
EventTime::from_millis(i * 5),
Point::new(0.0, i as f32 * 5.0),
);
}
let e = t.estimate().unwrap();
assert!(
e.duration <= HORIZON,
"the fitted window spans {:?}, past the {HORIZON:?} horizon",
e.duration
);
}
#[test]
fn add_coalesced_matches_adding_one_at_a_time() {
let batch: Vec<(EventTime, Point)> = (0..12u64)
.map(|i| {
(
EventTime::from_millis(i),
Point::new(i as f32 * 1.5, i as f32 * -2.5),
)
})
.collect();
let mut one_at_a_time = VelocityTracker::new();
for &(time, position) in &batch {
one_at_a_time.add(time, position);
}
let mut coalesced = VelocityTracker::new();
coalesced.add_coalesced(batch.iter().copied());
assert_eq!(
coalesced.estimate(),
one_at_a_time.estimate(),
"a coalesced batch must not be decimated"
);
}
#[test]
fn clear_forgets_everything() {
let mut t = constant_velocity(500.0, 100, 6);
assert!(t.estimate().is_some());
t.clear();
assert_eq!(t.estimate(), None);
assert_eq!(t.sample_count(), 0);
}
#[test]
fn velocity_reports_zero_when_there_is_no_estimate() {
let t = VelocityTracker::new();
assert_eq!(t.velocity(), Vec2::ZERO);
}
#[test]
fn the_ring_wraps_without_losing_the_newest_samples() {
let mut t = VelocityTracker::new();
for i in 0..60u64 {
t.add(
EventTime::from_millis(i * 4),
Point::new(0.0, i as f32 * 4.0),
);
}
assert_eq!(t.sample_count(), HISTORY_SIZE);
let e = t.estimate().unwrap();
assert!(
(e.pixels_per_second.y - 1000.0).abs() < 10.0,
"got {}",
e.pixels_per_second.y
);
}
#[test]
fn a_degenerate_window_declines_rather_than_returning_nan() {
let mut t = VelocityTracker::new();
for i in 0..6 {
t.add(EventTime::ZERO, Point::new(i as f32, 0.0));
}
assert_eq!(t.estimate(), None);
assert_eq!(t.velocity(), Vec2::ZERO);
}
#[test]
fn a_decelerating_stream_reports_the_release_velocity() {
let mut t = VelocityTracker::new();
for i in 0..6u64 {
let s = i as f32 * 0.01;
t.add(
EventTime::from_millis(i * 10),
Point::new(0.0, 1000.0 * s - 2000.0 * s * s),
);
}
let e = t.estimate().unwrap();
assert!(
(e.pixels_per_second.y - 800.0).abs() < 8.0,
"expected the release velocity 800, got {}",
e.pixels_per_second.y
);
}
#[test]
fn the_documented_velocity_constants_are_the_shipped_ones() {
const PAGE: &str = "kinetic-scrolling.md";
let rows = crate::kinetic::doc_table::rows(PAGE, "### Velocity tracker");
let mut seen = Vec::new();
for row in &rows {
let key = row[0].trim_matches('`').to_string();
let cell = &row[1];
match key.as_str() {
"HISTORY_SIZE" => {
crate::kinetic::doc_table::assert_value(PAGE, cell, HISTORY_SIZE as f64, &key)
}
"HORIZON" => crate::kinetic::doc_table::assert_value(
PAGE,
cell,
HORIZON.as_millis() as f64,
&key,
),
"MIN_SAMPLE_SIZE" => crate::kinetic::doc_table::assert_value(
PAGE,
cell,
MIN_SAMPLE_SIZE as f64,
&key,
),
"STOP_GAP" => crate::kinetic::doc_table::assert_value(
PAGE,
cell,
STOP_GAP.as_millis() as f64,
&key,
),
"fit degree" => {
crate::kinetic::doc_table::assert_value(PAGE, cell, DEGREE as f64, &key)
}
other => panic!(
"docs/kinetic-scrolling.md publishes a velocity row {other:?} that \
this test does not check"
),
}
seen.push(key);
}
assert_eq!(
seen.len(),
5,
"the velocity table lost a row: {seen:?}. The prose below it says \
\"Flutter took all five from Android\"."
);
}
}