splines/
spline.rs

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

splines/
spline.rs
