bevy_math/curve/
cores.rs

1//! Core data structures to be used internally in Curve implementations, encapsulating storage
2//! and access patterns for reuse.
3//!
4//! The `Core` types here expose their fields publicly so that it is easier to manipulate and
5//! extend them, but in doing so, you must maintain the invariants of those fields yourself. The
6//! provided methods all maintain the invariants, so this is only a concern if you manually mutate
7//! the fields.
8
9use crate::ops;
10
11use super::interval::Interval;
12use core::fmt::Debug;
13use thiserror::Error;
14
15#[cfg(feature = "alloc")]
16use {alloc::vec::Vec, itertools::Itertools};
17
18#[cfg(feature = "bevy_reflect")]
19use bevy_reflect::Reflect;
20
21/// This type expresses the relationship of a value to a fixed collection of values. It is a kind
22/// of summary used intermediately by sampling operations.
23#[derive(Debug, Copy, Clone, PartialEq)]
24#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
25#[cfg_attr(feature = "bevy_reflect", derive(Reflect))]
26pub enum InterpolationDatum<T> {
27    /// This value lies exactly on a value in the family.
28    Exact(T),
29
30    /// This value is off the left tail of the family; the inner value is the family's leftmost.
31    LeftTail(T),
32
33    /// This value is off the right tail of the family; the inner value is the family's rightmost.
34    RightTail(T),
35
36    /// This value lies on the interior, in between two points, with a third parameter expressing
37    /// the interpolation factor between the two.
38    Between(T, T, f32),
39}
40
41impl<T> InterpolationDatum<T> {
42    /// Map all values using a given function `f`, leaving the interpolation parameters in any
43    /// [`Between`] variants unchanged.
44    ///
45    /// [`Between`]: `InterpolationDatum::Between`
46    #[must_use]
47    pub fn map<S>(self, f: impl Fn(T) -> S) -> InterpolationDatum<S> {
48        match self {
49            InterpolationDatum::Exact(v) => InterpolationDatum::Exact(f(v)),
50            InterpolationDatum::LeftTail(v) => InterpolationDatum::LeftTail(f(v)),
51            InterpolationDatum::RightTail(v) => InterpolationDatum::RightTail(f(v)),
52            InterpolationDatum::Between(u, v, s) => InterpolationDatum::Between(f(u), f(v), s),
53        }
54    }
55}
56
57/// The data core of a curve derived from evenly-spaced samples. The intention is to use this
58/// in addition to explicit or inferred interpolation information in user-space in order to
59/// implement curves using [`domain`] and [`sample_with`].
60///
61/// The internals are made transparent to give curve authors freedom, but [the provided constructor]
62/// enforces the required invariants, and the methods maintain those invariants.
63///
64/// [the provided constructor]: EvenCore::new
65/// [`domain`]: EvenCore::domain
66/// [`sample_with`]: EvenCore::sample_with
67///
68/// # Example
69/// ```rust
70/// # use bevy_math::curve::*;
71/// # use bevy_math::curve::cores::*;
72/// // Let's make a curve that interpolates evenly spaced samples using either linear interpolation
73/// // or step "interpolation" — i.e. just using the most recent sample as the source of truth.
74/// enum InterpolationMode {
75///     Linear,
76///     Step,
77/// }
78///
79/// // Linear interpolation mode is driven by a trait.
80/// trait LinearInterpolate {
81///     fn lerp(&self, other: &Self, t: f32) -> Self;
82/// }
83///
84/// // Step interpolation just uses an explicit function.
85/// fn step<T: Clone>(first: &T, second: &T, t: f32) -> T {
86///     if t >= 1.0 {
87///         second.clone()
88///     } else {
89///         first.clone()
90///     }
91/// }
92///
93/// // Omitted: Implementing `LinearInterpolate` on relevant types; e.g. `f32`, `Vec3`, and so on.
94///
95/// // The curve itself uses `EvenCore` to hold the evenly-spaced samples, and the `sample_with`
96/// // function will do all the work of interpolating once given a function to do it with.
97/// struct MyCurve<T> {
98///     core: EvenCore<T>,
99///     interpolation_mode: InterpolationMode,
100/// }
101///
102/// impl<T> Curve<T> for MyCurve<T>
103/// where
104///     T: LinearInterpolate + Clone,
105/// {
106///     fn domain(&self) -> Interval {
107///         self.core.domain()
108///     }
109///     
110///     fn sample_unchecked(&self, t: f32) -> T {
111///         // To sample this curve, check the interpolation mode and dispatch accordingly.
112///         match self.interpolation_mode {
113///             InterpolationMode::Linear => self.core.sample_with(t, <T as LinearInterpolate>::lerp),
114///             InterpolationMode::Step => self.core.sample_with(t, step),
115///         }
116///     }
117/// }
118/// ```
119#[cfg(feature = "alloc")]
120#[derive(Debug, Clone, PartialEq)]
121#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
122#[cfg_attr(feature = "bevy_reflect", derive(Reflect))]
123pub struct EvenCore<T> {
124    /// The domain over which the samples are taken, which corresponds to the domain of the curve
125    /// formed by interpolating them.
126    ///
127    /// # Invariants
128    /// This must always be a bounded interval; i.e. its endpoints must be finite.
129    pub domain: Interval,
130
131    /// The samples that are interpolated to extract values.
132    ///
133    /// # Invariants
134    /// This must always have a length of at least 2.
135    pub samples: Vec<T>,
136}
137
138/// An error indicating that an [`EvenCore`] could not be constructed.
139#[derive(Debug, Error)]
140#[error("Could not construct an EvenCore")]
141pub enum EvenCoreError {
142    /// Not enough samples were provided.
143    #[error("Need at least two samples to create an EvenCore, but {samples} were provided")]
144    NotEnoughSamples {
145        /// The number of samples that were provided.
146        samples: usize,
147    },
148
149    /// Unbounded domains are not compatible with `EvenCore`.
150    #[error("Cannot create an EvenCore over an unbounded domain")]
151    UnboundedDomain,
152}
153
154#[cfg(feature = "alloc")]
155impl<T> EvenCore<T> {
156    /// Create a new [`EvenCore`] from the specified `domain` and `samples`. The samples are
157    /// regarded to be evenly spaced within the given domain interval, so that the outermost
158    /// samples form the boundary of that interval. An error is returned if there are not at
159    /// least 2 samples or if the given domain is unbounded.
160    #[inline]
161    pub fn new(
162        domain: Interval,
163        samples: impl IntoIterator<Item = T>,
164    ) -> Result<Self, EvenCoreError> {
165        let samples: Vec<T> = samples.into_iter().collect();
166        if samples.len() < 2 {
167            return Err(EvenCoreError::NotEnoughSamples {
168                samples: samples.len(),
169            });
170        }
171        if !domain.is_bounded() {
172            return Err(EvenCoreError::UnboundedDomain);
173        }
174
175        Ok(EvenCore { domain, samples })
176    }
177
178    /// The domain of the curve derived from this core.
179    #[inline]
180    pub const fn domain(&self) -> Interval {
181        self.domain
182    }
183
184    /// Obtain a value from the held samples using the given `interpolation` to interpolate
185    /// between adjacent samples.
186    ///
187    /// The interpolation takes two values by reference together with a scalar parameter and
188    /// produces an owned value. The expectation is that `interpolation(&x, &y, 0.0)` and
189    /// `interpolation(&x, &y, 1.0)` are equivalent to `x` and `y` respectively.
190    #[inline]
191    pub fn sample_with<I>(&self, t: f32, interpolation: I) -> T
192    where
193        T: Clone,
194        I: Fn(&T, &T, f32) -> T,
195    {
196        match even_interp(self.domain, self.samples.len(), t) {
197            InterpolationDatum::Exact(idx)
198            | InterpolationDatum::LeftTail(idx)
199            | InterpolationDatum::RightTail(idx) => self.samples[idx].clone(),
200            InterpolationDatum::Between(lower_idx, upper_idx, s) => {
201                interpolation(&self.samples[lower_idx], &self.samples[upper_idx], s)
202            }
203        }
204    }
205
206    /// Given a time `t`, obtain a [`InterpolationDatum`] which governs how interpolation might recover
207    /// a sample at time `t`. For example, when a [`Between`] value is returned, its contents can
208    /// be used to interpolate between the two contained values with the given parameter. The other
209    /// variants give additional context about where the value is relative to the family of samples.
210    ///
211    /// [`Between`]: `InterpolationDatum::Between`
212    pub fn sample_interp(&self, t: f32) -> InterpolationDatum<&T> {
213        even_interp(self.domain, self.samples.len(), t).map(|idx| &self.samples[idx])
214    }
215
216    /// Like [`sample_interp`], but the returned values include the sample times. This can be
217    /// useful when sample interpolation is not scale-invariant.
218    ///
219    /// [`sample_interp`]: EvenCore::sample_interp
220    pub fn sample_interp_timed(&self, t: f32) -> InterpolationDatum<(f32, &T)> {
221        let segment_len = self.domain.length() / (self.samples.len() - 1) as f32;
222        even_interp(self.domain, self.samples.len(), t).map(|idx| {
223            (
224                self.domain.start() + segment_len * idx as f32,
225                &self.samples[idx],
226            )
227        })
228    }
229}
230
231/// Given a domain and a number of samples taken over that interval, return an [`InterpolationDatum`]
232/// that governs how samples are extracted relative to the stored data.
233///
234/// `domain` must be a bounded interval (i.e. `domain.is_bounded() == true`).
235///
236/// `samples` must be at least 2.
237///
238/// This function will never panic, but it may return invalid indices if its assumptions are violated.
239pub fn even_interp(domain: Interval, samples: usize, t: f32) -> InterpolationDatum<usize> {
240    let subdivs = samples - 1;
241    let step = domain.length() / subdivs as f32;
242    let t_shifted = t - domain.start();
243    let steps_taken = t_shifted / step;
244
245    if steps_taken <= 0.0 {
246        // To the left side of all the samples.
247        InterpolationDatum::LeftTail(0)
248    } else if steps_taken >= subdivs as f32 {
249        // To the right side of all the samples
250        InterpolationDatum::RightTail(samples - 1)
251    } else {
252        let lower_index = ops::floor(steps_taken) as usize;
253        // This upper index is always valid because `steps_taken` is a finite value
254        // strictly less than `samples - 1`, so its floor is at most `samples - 2`
255        let upper_index = lower_index + 1;
256        let s = ops::fract(steps_taken);
257        InterpolationDatum::Between(lower_index, upper_index, s)
258    }
259}
260
261/// The data core of a curve defined by unevenly-spaced samples or keyframes. The intention is to
262/// use this in concert with implicitly or explicitly-defined interpolation in user-space in
263/// order to implement the curve interface using [`domain`] and [`sample_with`].
264///
265/// The internals are made transparent to give curve authors freedom, but [the provided constructor]
266/// enforces the required invariants, and the methods maintain those invariants.
267///
268/// # Example
269/// ```rust
270/// # use bevy_math::curve::*;
271/// # use bevy_math::curve::cores::*;
272/// // Let's make a curve formed by interpolating rotations.
273/// // We'll support two common modes of interpolation:
274/// // - Normalized linear: First do linear interpolation, then normalize to get a valid rotation.
275/// // - Spherical linear: Interpolate through valid rotations with constant angular velocity.
276/// enum InterpolationMode {
277///     NormalizedLinear,
278///     SphericalLinear,
279/// }
280///
281/// // Our interpolation modes will be driven by traits.
282/// trait NormalizedLinearInterpolate {
283///     fn nlerp(&self, other: &Self, t: f32) -> Self;
284/// }
285///
286/// trait SphericalLinearInterpolate {
287///     fn slerp(&self, other: &Self, t: f32) -> Self;
288/// }
289///
290/// // Omitted: These traits would be implemented for `Rot2`, `Quat`, and other rotation representations.
291///
292/// // The curve itself just needs to use the curve core for keyframes, `UnevenCore`, which handles
293/// // everything except for the explicit interpolation used.
294/// struct RotationCurve<T> {
295///     core: UnevenCore<T>,
296///     interpolation_mode: InterpolationMode,
297/// }
298///
299/// impl<T> Curve<T> for RotationCurve<T>
300/// where
301///     T: NormalizedLinearInterpolate + SphericalLinearInterpolate + Clone,
302/// {
303///     fn domain(&self) -> Interval {
304///         self.core.domain()
305///     }
306///     
307///     fn sample_unchecked(&self, t: f32) -> T {
308///         // To sample the curve, we just look at the interpolation mode and
309///         // dispatch accordingly.
310///         match self.interpolation_mode {
311///             InterpolationMode::NormalizedLinear =>
312///                 self.core.sample_with(t, <T as NormalizedLinearInterpolate>::nlerp),
313///             InterpolationMode::SphericalLinear =>
314///                 self.core.sample_with(t, <T as SphericalLinearInterpolate>::slerp),
315///         }
316///     }
317/// }
318/// ```
319///
320/// [`domain`]: UnevenCore::domain
321/// [`sample_with`]: UnevenCore::sample_with
322/// [the provided constructor]: UnevenCore::new
323#[cfg(feature = "alloc")]
324#[derive(Debug, Clone)]
325#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
326#[cfg_attr(feature = "bevy_reflect", derive(Reflect))]
327pub struct UnevenCore<T> {
328    /// The times for the samples of this curve.
329    ///
330    /// # Invariants
331    /// This must always have a length of at least 2, be sorted, and have no
332    /// duplicated or non-finite times.
333    pub times: Vec<f32>,
334
335    /// The samples corresponding to the times for this curve.
336    ///
337    /// # Invariants
338    /// This must always have the same length as `times`.
339    pub samples: Vec<T>,
340}
341
342/// An error indicating that an [`UnevenCore`] could not be constructed.
343#[derive(Debug, Error)]
344#[error("Could not construct an UnevenCore")]
345pub enum UnevenCoreError {
346    /// Not enough samples were provided.
347    #[error(
348        "Need at least two unique samples to create an UnevenCore, but {samples} were provided"
349    )]
350    NotEnoughSamples {
351        /// The number of samples that were provided.
352        samples: usize,
353    },
354}
355
356#[cfg(feature = "alloc")]
357impl<T> UnevenCore<T> {
358    /// Create a new [`UnevenCore`]. The given samples are filtered to finite times and
359    /// sorted internally; if there are not at least 2 valid timed samples, an error will be
360    /// returned.
361    pub fn new(timed_samples: impl IntoIterator<Item = (f32, T)>) -> Result<Self, UnevenCoreError> {
362        // Filter out non-finite sample times first so they don't interfere with sorting/deduplication.
363        let mut timed_samples = timed_samples
364            .into_iter()
365            .filter(|(t, _)| t.is_finite())
366            .collect_vec();
367        timed_samples
368            // Using `total_cmp` is fine because no NANs remain and because deduplication uses
369            // `PartialEq` anyway (so -0.0 and 0.0 will be considered equal later regardless).
370            .sort_by(|(t0, _), (t1, _)| t0.total_cmp(t1));
371        timed_samples.dedup_by_key(|(t, _)| *t);
372
373        if timed_samples.len() < 2 {
374            return Err(UnevenCoreError::NotEnoughSamples {
375                samples: timed_samples.len(),
376            });
377        }
378
379        let (times, samples): (Vec<f32>, Vec<T>) = timed_samples.into_iter().unzip();
380        Ok(UnevenCore { times, samples })
381    }
382
383    /// The domain of the curve derived from this core.
384    ///
385    /// # Panics
386    /// This method may panic if the type's invariants aren't satisfied.
387    #[inline]
388    pub fn domain(&self) -> Interval {
389        let start = self.times.first().unwrap();
390        let end = self.times.last().unwrap();
391        Interval::new(*start, *end).unwrap()
392    }
393
394    /// Obtain a value from the held samples using the given `interpolation` to interpolate
395    /// between adjacent samples.
396    ///
397    /// The interpolation takes two values by reference together with a scalar parameter and
398    /// produces an owned value. The expectation is that `interpolation(&x, &y, 0.0)` and
399    /// `interpolation(&x, &y, 1.0)` are equivalent to `x` and `y` respectively.
400    #[inline]
401    pub fn sample_with<I>(&self, t: f32, interpolation: I) -> T
402    where
403        T: Clone,
404        I: Fn(&T, &T, f32) -> T,
405    {
406        match uneven_interp(&self.times, t) {
407            InterpolationDatum::Exact(idx)
408            | InterpolationDatum::LeftTail(idx)
409            | InterpolationDatum::RightTail(idx) => self.samples[idx].clone(),
410            InterpolationDatum::Between(lower_idx, upper_idx, s) => {
411                interpolation(&self.samples[lower_idx], &self.samples[upper_idx], s)
412            }
413        }
414    }
415
416    /// Given a time `t`, obtain a [`InterpolationDatum`] which governs how interpolation might recover
417    /// a sample at time `t`. For example, when a [`Between`] value is returned, its contents can
418    /// be used to interpolate between the two contained values with the given parameter. The other
419    /// variants give additional context about where the value is relative to the family of samples.
420    ///
421    /// [`Between`]: `InterpolationDatum::Between`
422    pub fn sample_interp(&self, t: f32) -> InterpolationDatum<&T> {
423        uneven_interp(&self.times, t).map(|idx| &self.samples[idx])
424    }
425
426    /// Like [`sample_interp`], but the returned values include the sample times. This can be
427    /// useful when sample interpolation is not scale-invariant.
428    ///
429    /// [`sample_interp`]: UnevenCore::sample_interp
430    pub fn sample_interp_timed(&self, t: f32) -> InterpolationDatum<(f32, &T)> {
431        uneven_interp(&self.times, t).map(|idx| (self.times[idx], &self.samples[idx]))
432    }
433
434    /// This core, but with the sample times moved by the map `f`.
435    /// In principle, when `f` is monotone, this is equivalent to [`CurveExt::reparametrize`],
436    /// but the function inputs to each are inverses of one another.
437    ///
438    /// The samples are re-sorted by time after mapping and deduplicated by output time, so
439    /// the function `f` should generally be injective over the set of sample times, otherwise
440    /// data will be deleted.
441    ///
442    /// [`CurveExt::reparametrize`]: crate::curve::CurveExt::reparametrize
443    #[must_use]
444    pub fn map_sample_times(mut self, f: impl Fn(f32) -> f32) -> UnevenCore<T> {
445        let mut timed_samples = self
446            .times
447            .into_iter()
448            .map(f)
449            .zip(self.samples)
450            .collect_vec();
451        timed_samples.sort_by(|(t1, _), (t2, _)| t1.total_cmp(t2));
452        timed_samples.dedup_by_key(|(t, _)| *t);
453        (self.times, self.samples) = timed_samples.into_iter().unzip();
454        self
455    }
456}
457
458/// The data core of a curve using uneven samples (i.e. keyframes), where each sample time
459/// yields some fixed number of values — the [sampling width]. This may serve as storage for
460/// curves that yield vectors or iterators, and in some cases, it may be useful for cache locality
461/// if the sample type can effectively be encoded as a fixed-length slice of values.
462///
463/// [sampling width]: ChunkedUnevenCore::width
464#[cfg(feature = "alloc")]
465#[derive(Debug, Clone)]
466#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
467#[cfg_attr(feature = "bevy_reflect", derive(Reflect))]
468pub struct ChunkedUnevenCore<T> {
469    /// The times, one for each sample.
470    ///
471    /// # Invariants
472    /// This must always have a length of at least 2, be sorted, and have no duplicated or
473    /// non-finite times.
474    pub times: Vec<f32>,
475
476    /// The values that are used in sampling. Each width-worth of these correspond to a single sample.
477    ///
478    /// # Invariants
479    /// The length of this vector must always be some fixed integer multiple of that of `times`.
480    pub values: Vec<T>,
481}
482
483/// An error that indicates that a [`ChunkedUnevenCore`] could not be formed.
484#[derive(Debug, Error)]
485#[error("Could not create a ChunkedUnevenCore")]
486pub enum ChunkedUnevenCoreError {
487    /// The width of a `ChunkedUnevenCore` cannot be zero.
488    #[error("Chunk width must be at least 1")]
489    ZeroWidth,
490
491    /// At least two sample times are necessary to interpolate in `ChunkedUnevenCore`.
492    #[error(
493        "Need at least two unique samples to create a ChunkedUnevenCore, but {samples} were provided"
494    )]
495    NotEnoughSamples {
496        /// The number of samples that were provided.
497        samples: usize,
498    },
499
500    /// The length of the value buffer is supposed to be the `width` times the number of samples.
501    #[error("Expected {expected} total values based on width, but {actual} were provided")]
502    MismatchedLengths {
503        /// The expected length of the value buffer.
504        expected: usize,
505        /// The actual length of the value buffer.
506        actual: usize,
507    },
508
509    /// Tried to infer the width, but the ratio of lengths wasn't an integer, so no such length exists.
510    #[error("The length of the list of values ({values_len}) was not divisible by that of the list of times ({times_len})")]
511    NonDivisibleLengths {
512        /// The length of the value buffer.
513        values_len: usize,
514        /// The length of the time buffer.
515        times_len: usize,
516    },
517}
518
519#[cfg(feature = "alloc")]
520impl<T> ChunkedUnevenCore<T> {
521    /// Create a new [`ChunkedUnevenCore`]. The given `times` are sorted, filtered to finite times,
522    /// and deduplicated. See the [type-level documentation] for more information about this type.
523    ///
524    /// Produces an error in any of the following circumstances:
525    /// - `width` is zero.
526    /// - `times` has less than `2` unique valid entries.
527    /// - `values` has the incorrect length relative to `times`.
528    ///
529    /// [type-level documentation]: ChunkedUnevenCore
530    pub fn new(
531        times: impl IntoIterator<Item = f32>,
532        values: impl IntoIterator<Item = T>,
533        width: usize,
534    ) -> Result<Self, ChunkedUnevenCoreError> {
535        let times = times.into_iter().collect_vec();
536        let values = values.into_iter().collect_vec();
537
538        if width == 0 {
539            return Err(ChunkedUnevenCoreError::ZeroWidth);
540        }
541
542        let times = filter_sort_dedup_times(times);
543
544        if times.len() < 2 {
545            return Err(ChunkedUnevenCoreError::NotEnoughSamples {
546                samples: times.len(),
547            });
548        }
549
550        if values.len() != times.len() * width {
551            return Err(ChunkedUnevenCoreError::MismatchedLengths {
552                expected: times.len() * width,
553                actual: values.len(),
554            });
555        }
556
557        Ok(Self { times, values })
558    }
559
560    /// Create a new [`ChunkedUnevenCore`], inferring the width from the sizes of the inputs.
561    /// The given `times` are sorted, filtered to finite times, and deduplicated. See the
562    /// [type-level documentation] for more information about this type. Prefer using [`new`]
563    /// if possible, since that constructor has richer error checking.
564    ///
565    /// Produces an error in any of the following circumstances:
566    /// - `values` has length zero.
567    /// - `times` has less than `2` unique valid entries.
568    /// - The length of `values` is not divisible by that of `times` (once sorted, filtered,
569    ///   and deduplicated).
570    ///
571    /// The [width] is implicitly taken to be the length of `values` divided by that of `times`
572    /// (once sorted, filtered, and deduplicated).
573    ///
574    /// [type-level documentation]: ChunkedUnevenCore
575    /// [`new`]: ChunkedUnevenCore::new
576    /// [width]: ChunkedUnevenCore::width
577    pub fn new_width_inferred(
578        times: impl IntoIterator<Item = f32>,
579        values: impl IntoIterator<Item = T>,
580    ) -> Result<Self, ChunkedUnevenCoreError> {
581        let times = times.into_iter().collect_vec();
582        let values = values.into_iter().collect_vec();
583
584        let times = filter_sort_dedup_times(times);
585
586        if times.len() < 2 {
587            return Err(ChunkedUnevenCoreError::NotEnoughSamples {
588                samples: times.len(),
589            });
590        }
591
592        if values.len() % times.len() != 0 {
593            return Err(ChunkedUnevenCoreError::NonDivisibleLengths {
594                values_len: values.len(),
595                times_len: times.len(),
596            });
597        }
598
599        if values.is_empty() {
600            return Err(ChunkedUnevenCoreError::ZeroWidth);
601        }
602
603        Ok(Self { times, values })
604    }
605
606    /// The domain of the curve derived from this core.
607    ///
608    /// # Panics
609    /// This may panic if this type's invariants aren't met.
610    #[inline]
611    pub fn domain(&self) -> Interval {
612        let start = self.times.first().unwrap();
613        let end = self.times.last().unwrap();
614        Interval::new(*start, *end).unwrap()
615    }
616
617    /// The sample width: the number of values that are contained in each sample.
618    #[inline]
619    pub fn width(&self) -> usize {
620        self.values.len() / self.times.len()
621    }
622
623    /// Given a time `t`, obtain a [`InterpolationDatum`] which governs how interpolation might recover
624    /// a sample at time `t`. For example, when a [`Between`] value is returned, its contents can
625    /// be used to interpolate between the two contained values with the given parameter. The other
626    /// variants give additional context about where the value is relative to the family of samples.
627    ///
628    /// [`Between`]: `InterpolationDatum::Between`
629    #[inline]
630    pub fn sample_interp(&self, t: f32) -> InterpolationDatum<&[T]> {
631        uneven_interp(&self.times, t).map(|idx| self.time_index_to_slice(idx))
632    }
633
634    /// Like [`sample_interp`], but the returned values include the sample times. This can be
635    /// useful when sample interpolation is not scale-invariant.
636    ///
637    /// [`sample_interp`]: ChunkedUnevenCore::sample_interp
638    pub fn sample_interp_timed(&self, t: f32) -> InterpolationDatum<(f32, &[T])> {
639        uneven_interp(&self.times, t).map(|idx| (self.times[idx], self.time_index_to_slice(idx)))
640    }
641
642    /// Given an index in [times], returns the slice of [values] that correspond to the sample at
643    /// that time.
644    ///
645    /// [times]: ChunkedUnevenCore::times
646    /// [values]: ChunkedUnevenCore::values
647    #[inline]
648    fn time_index_to_slice(&self, idx: usize) -> &[T] {
649        let width = self.width();
650        let lower_idx = width * idx;
651        let upper_idx = lower_idx + width;
652        &self.values[lower_idx..upper_idx]
653    }
654}
655
656/// Sort the given times, deduplicate them, and filter them to only finite times.
657#[cfg(feature = "alloc")]
658fn filter_sort_dedup_times(times: impl IntoIterator<Item = f32>) -> Vec<f32> {
659    // Filter before sorting/deduplication so that NAN doesn't interfere with them.
660    let mut times = times.into_iter().filter(|t| t.is_finite()).collect_vec();
661    times.sort_by(f32::total_cmp);
662    times.dedup();
663    times
664}
665
666/// Given a list of `times` and a target value, get the interpolation relationship for the
667/// target value in terms of the indices of the starting list. In a sense, this encapsulates the
668/// heart of uneven/keyframe sampling.
669///
670/// `times` is assumed to be sorted, deduplicated, and consisting only of finite values. It is also
671/// assumed to contain at least two values.
672///
673/// # Panics
674/// This function will panic if `times` contains NAN.
675pub fn uneven_interp(times: &[f32], t: f32) -> InterpolationDatum<usize> {
676    match times.binary_search_by(|pt| pt.partial_cmp(&t).unwrap()) {
677        Ok(index) => InterpolationDatum::Exact(index),
678        Err(index) => {
679            if index == 0 {
680                // This is before the first keyframe.
681                InterpolationDatum::LeftTail(0)
682            } else if index >= times.len() {
683                // This is after the last keyframe.
684                InterpolationDatum::RightTail(times.len() - 1)
685            } else {
686                // This is actually in the middle somewhere.
687                let t_lower = times[index - 1];
688                let t_upper = times[index];
689                let s = (t - t_lower) / (t_upper - t_lower);
690                InterpolationDatum::Between(index - 1, index, s)
691            }
692        }
693    }
694}
695
696#[cfg(all(test, feature = "alloc"))]
697mod tests {
698    use super::{ChunkedUnevenCore, EvenCore, UnevenCore};
699    use crate::curve::{cores::InterpolationDatum, interval};
700    use alloc::vec;
701    use approx::{assert_abs_diff_eq, AbsDiffEq};
702
703    fn approx_between<T>(datum: InterpolationDatum<T>, start: T, end: T, p: f32) -> bool
704    where
705        T: PartialEq,
706    {
707        if let InterpolationDatum::Between(m_start, m_end, m_p) = datum {
708            m_start == start && m_end == end && m_p.abs_diff_eq(&p, 1e-6)
709        } else {
710            false
711        }
712    }
713
714    fn is_left_tail<T>(datum: InterpolationDatum<T>) -> bool {
715        matches!(datum, InterpolationDatum::LeftTail(_))
716    }
717
718    fn is_right_tail<T>(datum: InterpolationDatum<T>) -> bool {
719        matches!(datum, InterpolationDatum::RightTail(_))
720    }
721
722    fn is_exact<T>(datum: InterpolationDatum<T>, target: T) -> bool
723    where
724        T: PartialEq,
725    {
726        if let InterpolationDatum::Exact(v) = datum {
727            v == target
728        } else {
729            false
730        }
731    }
732
733    #[test]
734    fn even_sample_interp() {
735        let even_core = EvenCore::<f32>::new(
736            interval(0.0, 1.0).unwrap(),
737            // 11 entries -> 10 segments
738            vec![0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0],
739        )
740        .expect("Failed to construct test core");
741
742        let datum = even_core.sample_interp(-1.0);
743        assert!(is_left_tail(datum));
744        let datum = even_core.sample_interp(0.0);
745        assert!(is_left_tail(datum));
746        let datum = even_core.sample_interp(1.0);
747        assert!(is_right_tail(datum));
748        let datum = even_core.sample_interp(2.0);
749        assert!(is_right_tail(datum));
750
751        let datum = even_core.sample_interp(0.05);
752        let InterpolationDatum::Between(0.0, 1.0, p) = datum else {
753            panic!("Sample did not lie in the correct subinterval")
754        };
755        assert_abs_diff_eq!(p, 0.5);
756
757        let datum = even_core.sample_interp(0.05);
758        assert!(approx_between(datum, &0.0, &1.0, 0.5));
759        let datum = even_core.sample_interp(0.33);
760        assert!(approx_between(datum, &3.0, &4.0, 0.3));
761        let datum = even_core.sample_interp(0.78);
762        assert!(approx_between(datum, &7.0, &8.0, 0.8));
763
764        let datum = even_core.sample_interp(0.5);
765        assert!(approx_between(datum, &4.0, &5.0, 1.0) || approx_between(datum, &5.0, &6.0, 0.0));
766        let datum = even_core.sample_interp(0.7);
767        assert!(approx_between(datum, &6.0, &7.0, 1.0) || approx_between(datum, &7.0, &8.0, 0.0));
768    }
769
770    #[test]
771    fn uneven_sample_interp() {
772        let uneven_core = UnevenCore::<f32>::new(vec![
773            (0.0, 0.0),
774            (1.0, 3.0),
775            (2.0, 9.0),
776            (4.0, 10.0),
777            (8.0, -5.0),
778        ])
779        .expect("Failed to construct test core");
780
781        let datum = uneven_core.sample_interp(-1.0);
782        assert!(is_left_tail(datum));
783        let datum = uneven_core.sample_interp(0.0);
784        assert!(is_exact(datum, &0.0));
785        let datum = uneven_core.sample_interp(8.0);
786        assert!(is_exact(datum, &(-5.0)));
787        let datum = uneven_core.sample_interp(9.0);
788        assert!(is_right_tail(datum));
789
790        let datum = uneven_core.sample_interp(0.5);
791        assert!(approx_between(datum, &0.0, &3.0, 0.5));
792        let datum = uneven_core.sample_interp(2.5);
793        assert!(approx_between(datum, &9.0, &10.0, 0.25));
794        let datum = uneven_core.sample_interp(7.0);
795        assert!(approx_between(datum, &10.0, &(-5.0), 0.75));
796
797        let datum = uneven_core.sample_interp(2.0);
798        assert!(is_exact(datum, &9.0));
799        let datum = uneven_core.sample_interp(4.0);
800        assert!(is_exact(datum, &10.0));
801    }
802
803    #[test]
804    fn chunked_uneven_sample_interp() {
805        let core =
806            ChunkedUnevenCore::new(vec![0.0, 2.0, 8.0], vec![0.0, 1.0, 2.0, 3.0, 4.0, 5.0], 2)
807                .expect("Failed to construct test core");
808
809        let datum = core.sample_interp(-1.0);
810        assert!(is_left_tail(datum));
811        let datum = core.sample_interp(0.0);
812        assert!(is_exact(datum, &[0.0, 1.0]));
813        let datum = core.sample_interp(8.0);
814        assert!(is_exact(datum, &[4.0, 5.0]));
815        let datum = core.sample_interp(10.0);
816        assert!(is_right_tail(datum));
817
818        let datum = core.sample_interp(1.0);
819        assert!(approx_between(datum, &[0.0, 1.0], &[2.0, 3.0], 0.5));
820        let datum = core.sample_interp(3.0);
821        assert!(approx_between(datum, &[2.0, 3.0], &[4.0, 5.0], 1.0 / 6.0));
822
823        let datum = core.sample_interp(2.0);
824        assert!(is_exact(datum, &[2.0, 3.0]));
825    }
826}
bevy_math/curve/cores.rs

bevy_math/curve/
cores.rs
