Derivative access patterns for curves

[mweatherley]

Objective

• For curves that also include derivatives, make accessing derivative information via the Curve API ergonomic: that is, provide access to a curve that also samples derivative information.
• Implement this functionality for cubic spline curves provided by bevy_math.

Ultimately, this is to serve the purpose of doing more geometric operations on curves, like reparametrization by arclength and the construction of moving frames.

Solution

This has several parts, some of which may seem redundant. However, care has been put into this to satisfy the following constraints:

• Accessing a Curve that samples derivative information should be not just possible but easy and non-error-prone. For example, given a differentiable Curve<Vec2>, one should be able to access something like a Curve<(Vec2, Vec2)> ergonomically, and not just sample the derivatives piecemeal from point to point.
• Derivative access should not step on the toes of ordinary curve usage. In particular, in the above scenario, we want to avoid simply making the same curve both a Curve<Vec2> and a Curve<(Vec2, Vec2)> because this requires manual disambiguation when the API is used.
• Derivative access must work gracefully in both owned and borrowed contexts.

HasTangent

We introduce a trait HasTangent that provides an associated Tangent type for types that have tangent spaces:

pub trait HasTangent {
    /// The tangent type.
    type Tangent: VectorSpace;
}

(Mathematically speaking, it would be more precise to say that these are types that represent spaces which are canonically parallelized. )

The idea here is that a point moving through a HasTangent type may have a derivative valued in the associated Tangent type at each time in its journey. We reify this with a WithDerivative<T> type that uses HasTangent to include derivative information:

pub struct WithDerivative<T>
where
    T: HasTangent,
{
    /// The underlying value.
    pub value: T,

    /// The derivative at `value`.
    pub derivative: T::Tangent,
}

And we can play the same game with second derivatives as well, since every VectorSpace type is HasTangent where Tangent is itself (we may want to be more restrictive with this in practice, but this holds mathematically).

pub struct WithTwoDerivatives<T>
where
    T: HasTangent,
{
    /// The underlying value.
    pub value: T,

    /// The derivative at `value`.
    pub derivative: T::Tangent,

    /// The second derivative at `value`.
    pub second_derivative: <T::Tangent as HasTangent>::Tangent,
}

In this PR, HasTangent is only implemented for VectorSpace types, but it would be valuable to have this implementation for types like Rot2 and Quat as well. We could also do it for the isometry types and, potentially, transforms as well. (This is in decreasing order of value in my opinion.)

CurveWithDerivative

This is a trait for a Curve<T> which allows the construction of a Curve<WithDerivative<T>> when derivative information is known intrinsically. It looks like this:

/// Trait for curves that have a well-defined notion of derivative, allowing for
/// derivatives to be extracted along with values.
pub trait CurveWithDerivative<T>
where
    T: HasTangent,
{
    /// This curve, but with its first derivative included in sampling.
    fn with_derivative(self) -> impl Curve<WithDerivative<T>>;
}

The idea here is to provide patterns like this:

let value_and_derivative = my_curve.with_derivative().sample_clamped(t);

One of the main points here is that Curve<WithDerivative<T>> is useful as an output because it can be used durably. For example, in a dynamic context, something that needs curves with derivatives can store something like a Box<dyn Curve<WithDerivative<T>>>. Note that CurveWithDerivative is not dyn-compatible.

SampleDerivative

Many curves "know" how to sample their derivatives instrinsically, but implementing CurveWithDerivative as given would be onerous or require an annoying amount of boilerplate. There are also hurdles to overcome that involve references to curves: for the Curve API, the expectation is that curve transformations like with_derivative take things by value, with the contract that they can still be used by reference through deref-magic by including by_ref in a method chain.

These problems are solved simultaneously by a trait SampleDerivative which, when implemented, automatically derives CurveWithDerivative for a type and all types that dereference to it. It just looks like this:

pub trait SampleDerivative<T>: Curve<T>
where
    T: HasTangent,
{
    fn sample_with_derivative_unchecked(&self, t: f32) -> WithDerivative<T>;
    // ... other sampling variants as default methods
}

The point is that the output of with_derivative is a Curve<WithDerivative<T>> that uses the SampleDerivative implementation. On a SampleDerivative type, you can also just call my_curve.sample_with_derivative(t) instead of something like my_curve.by_ref().with_derivative().sample(t), which is more verbose and less accessible.

In practice, CurveWithDerivative<T> is actually a "sealed" extension trait of SampleDerivative<T>.

Adaptors

SampleDerivative has automatic implementations on all curve adaptors except for FunctionCurve, MapCurve, and ReparamCurve (because we do not have a notion of differentiable Rust functions).

For example, CurveReparamCurve (the reparametrization of a curve by another curve) can compute derivatives using the chain rule in the case both its constituents have them.

Testing

TODO: Some tests using curve adaptors together with derivatives.

---

Showcase

This development allows derivative information to be included with and extracted from curves using the Curve API.

let points = [
    vec2(-1.0, -20.0),
    vec2(3.0, 2.0),
    vec2(5.0, 3.0),
    vec2(9.0, 8.0),
];

// A cubic spline curve that goes through `points`.
let curve = CubicCardinalSpline::new(0.3, points).to_curve().unwrap();

// Calling `with_derivative` causes derivative output to be included in the output of the curve API.
let curve_with_derivative = curve.with_derivative();

// A `Curve<f32>` that outputs the speed of the original.
let speed_curve = curve_with_derivative.map(|x| x.derivative.norm());

---

Questions

• ~~Maybe we should seal WithDerivative or make it require SampleDerivative (i.e. make it unimplementable except through SampleDerivative).~~ I decided this is a good idea.
• ~~Unclear whether VectorSpace: HasTangent blanket implementation is really appropriate. For colors, for example, I'm not sure that the derivative values can really be interpreted as a color. In any case, it should still remain the case that VectorSpace types are HasTangent and that HasTangent::Tangent: HasTangent.~~ I think this is fine.
• Infinity bikeshed on names of traits and things.

Future

• Faster implementations of SampleDerivative for cubic spline curves.
• Implement HasTangent for:
  • Rot2/Quat
  • Isometry types
  • Transform, maybe
• Implement derivatives for easing curves.
• Marker traits for continuous/differentiable curves. (It's actually unclear to me how much value this has in practice, but we have discussed it in the past.)
• Blanket HasTangent over tuples and make derivatives "just work" on ZipCurve and GraphCurve.