splines/
spline.rs

Help
1//! Spline curves and operations.
2
3#[cfg(feature = "serialization")] use serde_derive::{Deserialize, Serialize};
4#[cfg(not(feature = "std"))] use alloc::vec::Vec;
5#[cfg(feature = "std")] use std::cmp::Ordering;
6#[cfg(feature = "std")] use std::ops::{Div, Mul};
7#[cfg(not(feature = "std"))] use core::ops::{Div, Mul};
8#[cfg(not(feature = "std"))] use core::cmp::Ordering;
9
10use crate::interpolate::{Interpolate, Additive, One, Trigo};
11use crate::interpolation::Interpolation;
12use crate::key::Key;
13
14/// Spline curve used to provide interpolation between control points (keys).
15///
16/// Splines are made out of control points ([`Key`]). When creating a [`Spline`] with
17/// [`Spline::from_vec`] or [`Spline::from_iter`], the keys don’t have to be sorted (they are sorted
18/// automatically by the sampling value).
19///
20/// You can sample from a spline with several functions:
21///
22///   - [`Spline::sample`]: allows you to sample from a spline. If not enough keys are available
23///     for the required interpolation mode, you get `None`.
24///   - [`Spline::clamped_sample`]: behaves like [`Spline::sample`] but will return either the first
25///     or last key if out of bound; it will return `None` if not enough key.
26#[derive(Debug, Clone)]
27#[cfg_attr(feature = "serialization", derive(Deserialize, Serialize))]
28pub struct Spline<T, V>(pub(crate) Vec<Key<T, V>>);
29
30impl<T, V> Spline<T, V> {
31  /// Internal sort to ensure invariant of sorting keys is valid.
32  fn internal_sort(&mut self) where T: PartialOrd {
33    self.0.sort_by(|k0, k1| k0.t.partial_cmp(&k1.t).unwrap_or(Ordering::Less));
34  }
35
36  /// Create a new spline out of keys. The keys don’t have to be sorted even though it’s recommended
37  /// to provide ascending sorted ones (for performance purposes).
38  pub fn from_vec(keys: Vec<Key<T, V>>) -> Self where T: PartialOrd {
39    let mut spline = Spline(keys);
40    spline.internal_sort();
41    spline
42  }
43
44  /// Create a new spline by consuming an `Iterater<Item = Key<T>>`. They keys don’t have to be
45  /// sorted.
46  ///
47  /// # Note on iterators
48  ///
49  /// It’s valid to use any iterator that implements `Iterator<Item = Key<T>>`. However, you should
50  /// use [`Spline::from_vec`] if you are passing a [`Vec`].
51  pub fn from_iter<I>(iter: I) -> Self where I: Iterator<Item = Key<T, V>>, T: PartialOrd {
52    Self::from_vec(iter.collect())
53  }
54
55  /// Retrieve the keys of a spline.
56  pub fn keys(&self) -> &[Key<T, V>] {
57    &self.0
58  }
59
60  /// Number of keys.
61  #[inline(always)]
62  pub fn len(&self) -> usize {
63    self.0.len()
64  }
65
66  /// Check whether the spline has no key.
67  #[inline(always)]
68  pub fn is_empty(&self) -> bool {
69    self.0.is_empty()
70  }
71
72  /// Sample a spline at a given time, returning the interpolated value along with its associated
73  /// key.
74  ///
75  /// The current implementation, based on immutability, cannot perform in constant time. This means
76  /// that sampling’s processing complexity is currently *O(log n)*. It’s possible to achieve *O(1)*
77  /// performance by using a slightly different spline type. If you are interested by this feature,
78  /// an implementation for a dedicated type is foreseen yet not started yet.
79  ///
80  /// # Return
81  ///
82  /// `None` if you try to sample a value at a time that has no key associated with. That can also
83  /// happen if you try to sample between two keys with a specific interpolation mode that makes the
84  /// sampling impossible. For instance, [`Interpolation::CatmullRom`] requires *four* keys. If
85  /// you’re near the beginning of the spline or its end, ensure you have enough keys around to make
86  /// the sampling.
87  pub fn sample_with_key(&self, t: T) -> Option<(V, &Key<T, V>, Option<&Key<T, V>>)>
88  where T: Additive + One + Trigo + Mul<T, Output = T> + Div<T, Output = T> + PartialOrd,
89        V: Interpolate<T> {
90    let keys = &self.0;
91    let i = search_lower_cp(keys, t)?;
92    let cp0 = &keys[i];
93
94    match cp0.interpolation {
95      Interpolation::Step(threshold) => {
96        let cp1 = &keys[i + 1];
97        let nt = normalize_time(t, cp0, cp1);
98        let value = if nt < threshold { cp0.value } else { cp1.value };
99
100        Some((value, cp0, Some(cp1)))
101      }
102
103      Interpolation::Linear => {
104        let cp1 = &keys[i + 1];
105        let nt = normalize_time(t, cp0, cp1);
106        let value = Interpolate::lerp(cp0.value, cp1.value, nt);
107
108        Some((value, cp0, Some(cp1)))
109      }
110
111      Interpolation::Cosine => {
112        let two_t = T::one() + T::one();
113        let cp1 = &keys[i + 1];
114        let nt = normalize_time(t, cp0, cp1);
115        let cos_nt = (T::one() - (nt * T::pi()).cos()) / two_t;
116        let value = Interpolate::lerp(cp0.value, cp1.value, cos_nt);
117
118        Some((value, cp0, Some(cp1)))
119      }
120
121      Interpolation::CatmullRom => {
122        // We need at least four points for Catmull Rom; ensure we have them, otherwise, return
123        // None.
124        if i == 0 || i >= keys.len() - 2 {
125          None
126        } else {
127          let cp1 = &keys[i + 1];
128          let cpm0 = &keys[i - 1];
129          let cpm1 = &keys[i + 2];
130          let nt = normalize_time(t, cp0, cp1);
131          let value = Interpolate::cubic_hermite((cpm0.value, cpm0.t), (cp0.value, cp0.t), (cp1.value, cp1.t), (cpm1.value, cpm1.t), nt);
132
133          Some((value, cp0, Some(cp1)))
134        }
135      }
136
137      Interpolation::Bezier(u) => {
138        // We need to check the next control point to see whether we want quadratic or cubic Bezier.
139        let cp1 = &keys[i + 1];
140        let nt = normalize_time(t, cp0, cp1);
141
142        let value =
143          if let Interpolation::Bezier(v) = cp1.interpolation {
144            Interpolate::cubic_bezier(cp0.value, u, v, cp1.value, nt)
145          } else {
146            Interpolate::quadratic_bezier(cp0.value, u, cp1.value, nt)
147          };
148
149        Some((value, cp0, Some(cp1)))
150      }
151
152      Interpolation::StrokeBezier(input, output) => {
153        let cp1 = &keys[i + 1];
154        let nt = normalize_time(t, cp0, cp1);
155        let value = Interpolate::cubic_bezier(cp0.value, input, output, cp1.value, nt);
156
157        Some((value, cp0, Some(cp1)))
158      }
159
160      Interpolation::__NonExhaustive => unreachable!(),
161    }
162  }
163
164  /// Sample a spline at a given time.
165  ///
166  pub fn sample(&self, t: T) -> Option<V>
167  where T: Additive + One + Trigo + Mul<T, Output = T> + Div<T, Output = T> + PartialOrd,
168        V: Interpolate<T> {
169    self.sample_with_key(t).map(|(v, _, _)| v)
170  }
171
172  /// Sample a spline at a given time with clamping, returning the interpolated value along with its
173  /// associated key.
174  ///
175  /// # Return
176  ///
177  /// If you sample before the first key or after the last one, return the first key or the last
178  /// one, respectively. Otherwise, behave the same way as [`Spline::sample`].
179  ///
180  /// # Error
181  ///
182  /// This function returns [`None`] if you have no key.
183  pub fn clamped_sample_with_key(&self, t: T) -> Option<(V, &Key<T, V>, Option<&Key<T, V>>)>
184  where T: Additive + One + Trigo + Mul<T, Output = T> + Div<T, Output = T> + PartialOrd,
185        V: Interpolate<T> {
186    if self.0.is_empty() {
187      return None;
188    }
189
190    self.sample_with_key(t).or_else(move || {
191      let first = self.0.first().unwrap();
192      if t <= first.t {
193        let second = if self.0.len() >= 2 { Some(&self.0[1]) } else { None };
194        Some((first.value, &first, second))
195      } else {
196        let last = self.0.last().unwrap();
197
198        if t >= last.t {
199          Some((last.value, &last, None))
200        } else {
201          None
202        }
203      }
204    })
205  }
206
207  /// Sample a spline at a given time with clamping.
208  pub fn clamped_sample(&self, t: T) -> Option<V>
209  where T: Additive + One + Trigo + Mul<T, Output = T> + Div<T, Output = T> + PartialOrd,
210        V: Interpolate<T> {
211    self.clamped_sample_with_key(t).map(|(v, _, _)| v)
212  }
213
214  /// Add a key into the spline.
215  pub fn add(&mut self, key: Key<T, V>) where T: PartialOrd {
216    self.0.push(key);
217    self.internal_sort();
218  }
219
220  /// Remove a key from the spline.
221  pub fn remove(&mut self, index: usize) -> Option<Key<T, V>> {
222    if index >= self.0.len() {
223      None
224    } else {
225      Some(self.0.remove(index))
226    }
227  }
228
229  /// Update a key and return the key already present.
230  ///
231  /// The key is updated — if present — with the provided function.
232  ///
233  /// # Notes
234  ///
235  /// That function makes sense only if you want to change the interpolator (i.e. [`Key::t`]) of
236  /// your key. If you just want to change the interpolation mode or the carried value, consider
237  /// using the [`Spline::get_mut`] method instead as it will be way faster.
238  pub fn replace<F>(
239    &mut self,
240    index: usize,
241    f: F
242  ) -> Option<Key<T, V>>
243  where
244    F: FnOnce(&Key<T, V>) -> Key<T, V>,
245    T: PartialOrd
246  {
247    let key = self.remove(index)?;
248    self.add(f(&key));
249    Some(key)
250  }
251
252  /// Get a key at a given index.
253  pub fn get(&self, index: usize) -> Option<&Key<T, V>> {
254    self.0.get(index)
255  }
256
257  /// Mutably get a key at a given index.
258  pub fn get_mut(&mut self, index: usize) -> Option<KeyMut<T, V>> {
259    self.0.get_mut(index).map(|key| KeyMut {
260      value: &mut key.value,
261      interpolation: &mut key.interpolation
262    })
263  }
264}
265
266/// A mutable [`Key`].
267///
268/// Mutable keys allow to edit the carried values and the interpolation mode but not the actual
269/// interpolator value as it would invalidate the internal structure of the [`Spline`]. If you
270/// want to achieve this, you’re advised to use [`Spline::replace`].
271pub struct KeyMut<'a, T, V> {
272  /// Carried value.
273  pub value: &'a mut V,
274  /// Interpolation mode to use for that key.
275  pub interpolation: &'a mut Interpolation<T, V>,
276}
277
278// Normalize a time ([0;1]) given two control points.
279#[inline(always)]
280pub(crate) fn normalize_time<T, V>(
281  t: T,
282  cp: &Key<T, V>,
283  cp1: &Key<T, V>
284) -> T where T: Additive + Div<T, Output = T> + PartialEq {
285  assert!(cp1.t != cp.t, "overlapping keys");
286  (t - cp.t) / (cp1.t - cp.t)
287}
288
289// Find the lower control point corresponding to a given time.
290fn search_lower_cp<T, V>(cps: &[Key<T, V>], t: T) -> Option<usize> where T: PartialOrd {
291  let mut i = 0;
292  let len = cps.len();
293
294  if len < 2 {
295    return None;
296  }
297
298  loop {
299    let cp = &cps[i];
300    let cp1 = &cps[i+1];
301
302    if t >= cp1.t {
303      if i >= len - 2 {
304        return None;
305      }
306
307      i += 1;
308    } else if t < cp.t {
309      if i == 0 {
310        return None;
311      }
312
313      i -= 1;
314    } else {
315      break; // found
316    }
317  }
318
319  Some(i)
320}
splines/spline.rs

splines/
spline.rs
