use crate::utils::{f64_compare, TValue, TValueType};
use super::*;
impl Bezier {
pub fn euclidean_to_parametric(&self, ratio: f64, error: f64) -> f64 {
let total_length = self.length(None);
self.euclidean_to_parametric_with_total_length(ratio, error, total_length)
}
pub fn euclidean_to_parametric_with_total_length(&self, euclidean_t: f64, error: f64, total_length: f64) -> f64 {
if euclidean_t < error {
return 0.;
}
if 1. - euclidean_t < error {
return 1.;
}
let mut low = 0.;
let mut mid = 0.5;
let mut high = 1.;
let result_likely_closer_to_start = euclidean_t < 0.5;
let subdivisions_proportional_to_likely_length = ((euclidean_t - 0.5).abs() * DEFAULT_LENGTH_SUBDIVISIONS as f64).round().max(1.) as usize;
while low < high {
mid = (low + high) / 2.;
let current_length = if result_likely_closer_to_start {
let trimmed = self.trim(TValue::Parametric(0.), TValue::Parametric(mid));
trimmed.length(Some(subdivisions_proportional_to_likely_length))
} else {
let trimmed = self.trim(TValue::Parametric(mid), TValue::Parametric(1.));
let trimmed_length = trimmed.length(Some(subdivisions_proportional_to_likely_length));
total_length - trimmed_length
};
let current_euclidean_t = current_length / total_length;
if f64_compare(current_euclidean_t, euclidean_t, error) {
break;
} else if current_euclidean_t < euclidean_t {
low = mid;
} else {
high = mid;
}
}
mid
}
pub(crate) fn t_value_to_parametric(&self, t: TValue) -> f64 {
match t {
TValue::Parametric(t) => {
assert!((0.0..=1.).contains(&t));
t
}
TValue::Euclidean(t) => {
assert!((0.0..=1.).contains(&t));
self.euclidean_to_parametric(t, DEFAULT_EUCLIDEAN_ERROR_BOUND)
}
TValue::EuclideanWithinError { t, error } => {
assert!((0.0..=1.).contains(&t));
self.euclidean_to_parametric(t, error)
}
}
}
pub(crate) fn unrestricted_parametric_evaluate(&self, t: f64) -> DVec2 {
let t_squared = t * t;
let one_minus_t = 1. - t;
let squared_one_minus_t = one_minus_t * one_minus_t;
match self.handles {
BezierHandles::Linear => self.start.lerp(self.end, t),
BezierHandles::Quadratic { handle } => squared_one_minus_t * self.start + 2. * one_minus_t * t * handle + t_squared * self.end,
BezierHandles::Cubic { handle_start, handle_end } => {
let t_cubed = t_squared * t;
let cubed_one_minus_t = squared_one_minus_t * one_minus_t;
cubed_one_minus_t * self.start + 3. * squared_one_minus_t * t * handle_start + 3. * one_minus_t * t_squared * handle_end + t_cubed * self.end
}
}
}
pub fn evaluate(&self, t: TValue) -> DVec2 {
let t = self.t_value_to_parametric(t);
self.unrestricted_parametric_evaluate(t)
}
pub fn compute_lookup_table(&self, steps: Option<usize>, tvalue_type: Option<TValueType>) -> Vec<DVec2> {
let steps = steps.unwrap_or(DEFAULT_LUT_STEP_SIZE);
let tvalue_type = tvalue_type.unwrap_or(TValueType::Parametric);
(0..=steps)
.map(|t| {
let tvalue = match tvalue_type {
TValueType::Parametric => TValue::Parametric(t as f64 / steps as f64),
TValueType::Euclidean => TValue::Euclidean(t as f64 / steps as f64),
};
self.evaluate(tvalue)
})
.collect()
}
pub fn length(&self, num_subdivisions: Option<usize>) -> f64 {
match self.handles {
BezierHandles::Linear => (self.start - self.end).length(),
_ => {
let lookup_table = self.compute_lookup_table(Some(num_subdivisions.unwrap_or(DEFAULT_LENGTH_SUBDIVISIONS)), Some(TValueType::Parametric));
let approx_curve_length: f64 = lookup_table.windows(2).map(|points| (points[1] - points[0]).length()).sum();
approx_curve_length
}
}
}
pub fn project(&self, point: DVec2, options: Option<ProjectionOptions>) -> f64 {
let options = options.unwrap_or_default();
let ProjectionOptions {
lut_size,
convergence_epsilon,
convergence_limit,
iteration_limit,
} = options;
let lut = self.compute_lookup_table(Some(lut_size), Some(TValueType::Parametric));
let (minimum_position, minimum_distance) = utils::get_closest_point_in_lut(&lut, point);
let lut_size_f64 = lut_size as f64;
let minimum_position_f64 = minimum_position as f64;
let mut left_t = (minimum_position_f64 - 1.).max(0.) / lut_size_f64;
let mut right_t = (minimum_position_f64 + 1.).min(lut_size_f64) / lut_size_f64;
let mut final_t = left_t;
let mut distance;
let mut new_minimum_distance = minimum_distance + 1.;
let mut previous_distance;
let mut iteration_count = 0;
let mut convergence_count = 0;
let mut distances: [f64; NUM_DISTANCES] = [
point.distance(lut[(minimum_position as i64 - 1).max(0) as usize]),
0.,
0.,
0.,
point.distance(lut[lut_size.min(minimum_position + 1)]),
];
while left_t <= right_t && convergence_count < convergence_limit && iteration_count < iteration_limit {
previous_distance = new_minimum_distance;
let step = (right_t - left_t) / (NUM_DISTANCES as f64 - 1.);
let mut iterator_t = left_t;
let mut target_index = 0;
for (step_index, table_distance) in distances.iter_mut().enumerate().take(4) {
if step_index == 0 {
distance = *table_distance;
} else {
distance = point.distance(self.evaluate(TValue::Parametric(iterator_t)));
*table_distance = distance;
}
if distance < new_minimum_distance {
new_minimum_distance = distance;
target_index = step_index;
final_t = iterator_t
}
iterator_t += step;
}
if distances[NUM_DISTANCES - 1] < new_minimum_distance {
new_minimum_distance = distances[NUM_DISTANCES - 1];
final_t = right_t;
}
left_t = (final_t - step).max(0.);
right_t = (final_t + step).min(1.);
distances[0] = distances[if target_index == 0 { 0 } else { target_index - 1 }];
distances[NUM_DISTANCES - 1] = distances[(target_index + 1).min(NUM_DISTANCES - 1)];
iteration_count += 1;
if previous_distance - new_minimum_distance < convergence_epsilon {
convergence_count += 1;
} else {
convergence_count = 0;
}
}
final_t
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_evaluate() {
let p1 = DVec2::new(3., 5.);
let p2 = DVec2::new(14., 3.);
let p3 = DVec2::new(19., 14.);
let p4 = DVec2::new(30., 21.);
let bezier1 = Bezier::from_quadratic_dvec2(p1, p2, p3);
assert_eq!(bezier1.evaluate(TValue::Parametric(0.5)), DVec2::new(12.5, 6.25));
let bezier2 = Bezier::from_cubic_dvec2(p1, p2, p3, p4);
assert_eq!(bezier2.evaluate(TValue::Parametric(0.5)), DVec2::new(16.5, 9.625));
}
#[test]
fn test_compute_lookup_table() {
let bezier1 = Bezier::from_quadratic_coordinates(10., 10., 30., 30., 50., 10.);
let lookup_table1 = bezier1.compute_lookup_table(Some(2), Some(TValueType::Parametric));
assert_eq!(lookup_table1, vec![bezier1.start(), bezier1.evaluate(TValue::Parametric(0.5)), bezier1.end()]);
let bezier2 = Bezier::from_cubic_coordinates(10., 10., 30., 30., 70., 70., 90., 10.);
let lookup_table2 = bezier2.compute_lookup_table(Some(4), Some(TValueType::Parametric));
assert_eq!(
lookup_table2,
vec![
bezier2.start(),
bezier2.evaluate(TValue::Parametric(0.25)),
bezier2.evaluate(TValue::Parametric(0.50)),
bezier2.evaluate(TValue::Parametric(0.75)),
bezier2.end()
]
);
}
#[test]
fn test_length() {
let p1 = DVec2::new(30., 50.);
let p2 = DVec2::new(140., 30.);
let p3 = DVec2::new(160., 170.);
let p4 = DVec2::new(77., 129.);
let bezier_linear = Bezier::from_linear_dvec2(p1, p2);
assert!(utils::f64_compare(bezier_linear.length(None), p1.distance(p2), MAX_ABSOLUTE_DIFFERENCE));
let bezier_quadratic = Bezier::from_quadratic_dvec2(p1, p2, p3);
assert!(utils::f64_compare(bezier_quadratic.length(None), 204., 1e-2));
let bezier_cubic = Bezier::from_cubic_dvec2(p1, p2, p3, p4);
assert!(utils::f64_compare(bezier_cubic.length(None), 199., 1e-2));
}
#[test]
fn test_project() {
let bezier1 = Bezier::from_cubic_coordinates(4., 4., 23., 45., 10., 30., 56., 90.);
assert_eq!(bezier1.project(DVec2::ZERO, None), 0.);
assert_eq!(bezier1.project(DVec2::new(100., 100.), None), 1.);
let bezier2 = Bezier::from_quadratic_coordinates(0., 0., 0., 100., 100., 100.);
assert_eq!(bezier2.project(DVec2::new(100., 0.), None), 0.);
}
}