Tracking Issue for fNN::lerp

[clarfonthey]

Feature gate: #![feature(float_interpolationl)]

This is a tracking issue for the fNN::lerp methods in the standard library.

Public API

impl fNN {
    fn lerp(self, start: Self, end: Self) -> Self;
}

Steps / History

• Earlier feature request: Implement interpolation methods in std #71015
• Earlier (closed) implementation: Linear interpolation (lerp) implementation #71016
• Implementation: Linear interpolation #85925
• Final commenting period (FCP)
• Stabilization PR

Unresolved Questions

• Should we have all of the guarantees of std::lerp from C++?
• What specific mathematical version of lerp should we use?
• Is the calling convention good? Normally the order is lerp(a, b, t) but we have t.lerp(a, b)` here.
• Should we have an inverse lerp method? What should it be called?

[leonardo-m]

Considering this is isn't C++, don't you want to give it a more descriptive name, like "linear_interpolation"?

[camsteffen]

Considering this is isn't C++, don't you want to give it a more descriptive name, like "linear_interpolation"?

In this particular case I think it is good to copy the name. It is associated with this specific formula and the convention is used in other libraries and languages.

I think it is better to not have a self parameter for the same reason min/max functions do not have a self parameter. None of the inputs are self-evidently the "primary" input. a and b are a pair and t is the "other" parameter, but that does not make t "primary". Perhaps you may conceptualize the formula in a way that t feels primary, but that is not the most natural/common way to conceptualize it IMO. I think it is more natural to think of the inputs in the order a, b, t. "Start. End. Position between the two."

[leonardo-m]

In Rust you can write x.min(y).

[camsteffen]

In Rust you can write x.min(y).

Huh TIL 👆

[clarfonthey]

Yeah, lerp is a standard name for this, like signum, min, or max. We don't write out minimum or maximum for those methods. ;)

[CAD97]

Previously on irlo

Should we have all of the guarantees of std::lerp from C++?

Given that a significant part of the advantage to lerp is that it's super fast and trivial, it'll be interesting to sell using an implementation other than the two standard implementations (v0 + t * ( v1 - v0 ) (monotonic) or ( 1 - t ) * v0 + t * v1 (exact for t=1)). Especially on e.g. the GPU, being fast and branchless might be prioritized over being exact, consistent, and monotonic. Exact and consistent are commonly selected for, but monotonicity is rarely considered key, given lerp is typically (in my domain, games) used primarily for visual output, where small deviation doesn't matter much. That said, the given implementation of FMA( FMA( v0, v0, -t ), t, v1 ) (that is, (v0 + (v0 * -t)) + (t * v1)) is promising, as it's basically equivalent to the second, but...

I'm only 90% certain that it's monotonic, but I'm sure that people who care deeply about this will be there to discuss before stabilisation.

It's just f32, so we can check a full series for a given min/max, and... it's not monotonic. As just one example,

Not monotonic: lerp(0.24997729, 0.27129978, 0.9048672) = 0.42967725
             > lerp(0.2499773 , 0.27129978, 0.9048672) = 0.42967722

(Min and max were just chosen randomly here.) My code found 978813 pairs of adjacent float ts that were not monotonic. But that said, I don't think we should care about monotonicity. What actually potentially matters, in my eyes at least, is boundedness; that is, that for any (finite) a, b, t, a <= t.lerp(a, b) && t.lerp(a, b) <= b (flipped if b < a). As far as I've found, this implementation does uphold that requirement.

Is the calling convention good?

According to Wikipedia at least, both (v0, v1, t) and (t, v0, v1) are in use. For method use, t.lerp_between(a, b) seems unambiguous to me, but f32::lerp_between(t, a, b) is ambiguous again. A small survey of existing math/linalg crates' implementations (collected from mint rdeps):

• nalgebra: Vector::lerp(&self, rhs: &Self, t: T) = t * rhs + (1 - t) * self;
• euclid: Length::lerp(self, other: Self, t: T) = (1 - t) * self + t * other;
• glam: vecn::lerp(self, other: vecn, s: f32) = self + ((other - self) * s);
• cgmath: VectorSpace::lerp(self, other: Self, amount: Scalar) = self + ((other - self) * amount);
• kurbo: Vec2::lerp(self, other: Self, t: f64) = self + t * (other - self);
• emath: lerp(range: RangeInclusive<R>, t: T) = (1 - t) * range.start + t * range.end;
• ultraviolet: Lerp::lerp(&self, end: Self, t: T) = self * (1 - t) + end * t;
• vek: provides both Lerp::lerp_unclamped(from: Self, to: Self, factor: Factor) = mul_add(factor, to - from, from); ("using the supposedly fastest but less precise implementation") and Lerp::lerp_unclamped_precise(from: Self, to: Self, factor: Factor) = from * (1 - factor) + to * factor; ("using a possibly slower but more precise operation").

emath has a great solution to use here: RangeInclusive!

That is, use f32::lerp(self, range: RangeInclusive<f32>), so it's called as t.lerp(min..=max) or f32::lerp(t, min..=max). No confusion necessary!

Should we have an inverse lerp method? What should it be called?

As far as I can tell, the only somewhat common name is "inverse lerp" or "linearstep" (in contrast to smoothstep).

[CAD97]

An alternative option is to add lerp to RangeInclusive<fNN> instead of fNN, so that it's RangeInclusive::lerp(min..=max, t) or (min..=max).lerp(t). This would be interesting, but I think potentially problematic for the core/std split? As well as much more difficult to discover.

[koalefant]

The current choice of lerp signature t.lerp(a, b) appears to be unfortunate for two reasons:

First, it is impossible to be consistent with f32 implementation while implementing lerp for custom alebraic types (such as Vec3 or Quat etc.). One would not be able to extend f32 in an another crate to add interpolation of additional types.

[koalefant]

Second, it is inconsistent with most of existing algebraic crates in the ecosystem. As @CAD97 has mentioned above: nalgebra, euclid, glam, cgmath, kurbo, ultraviolet and vek all are using a.lerp(b, t) signature. That is a lot of breaking changes to be done to stay consistent with new std implementation.

[clarfonthey]

Note that there is the unfortunate but possible implementation of requiring a function call style, e.g. f32::lerp(a, b, t), which would not be equivalent to those other implementations but would be much less breaking.

[koalefant]

Note that there is the unfortunate but possible implementation of requiring a function call style, e.g. f32::lerp(a, b, t), which would not be equivalent to those other implementations but would be much less breaking.

One downside is that it would require type names to be stated explicitly, which is not the case with many other methods such as as clamp() or min()/max(). And this only addresses the first issue.

[CAD97]

@koalefant

That is an angle I hadn't realized, and consistent even for using RangeInclusive. v0.lerp(v1, t) can be applied to any custom lerpable type, as they can always implement their own methods. If we want the ecosystem to be able to also use t.lerp(v0, v1), though, we need to use a Lerp trait as an extension point, roughly

trait Lerp {
    fn lerp32(t: f32, v0: Self, v1: Self) -> Self { Self::lerp64(t, v0, v1) };
    fn lerp64(t: f64, v0: Self, v1: Self) -> Self;
}

impl f32 {
    fn lerp<L: Lerp>(self, v0: L, v1: L) -> L { L::lerp32(self, v0, v1) }
}

impl f64 {
    fn lerp<L: Lerp>(self, v0: L, v1: L) -> L { L::lerp64(self, v0, v1) }
}

and it's starting to get kind of messy, due to how overloading works in Rust. Assuming we only lerp between two values of the same type, we effectively want to do double dispatch, on the bitwidth of t and (more importantly) the type of the value being interpolated.

That, at least, speaks to putting the dispatch on the interpolated type. This brings me back to the possibility of providing it as (v0..=v1).lerp(t), as downstream can add trait implementations to add new lerp to different concretizations of RangeInclusive. (Though it makes me wish more that range types were Copy + IntoIterator instead of Iterator... but w/e that ship has sailed long ago.)

Although, on the other hand, the intricacy here makes me wonder whether lerp (for scalars) should live in num, for the same reason num was extracted from the stdlib to begin with.