Mon Apr 22 01:10:00 2019 UTC, by Dimitri Sabadie —
feed

Oh hello there! It’s been a while since I wrote on here. My last article was posted on February 25th and then I decided it was time to blog more about what I do. Especially, I think I will try to blog more often, even if it’s about trivial things, as long as I share my thoughts.

So today, I’m going to talk about the splines crate. And more specifically, the splines-1.0.0-rc.1 release candidate I uploaded today on crates.io.

Maybe you’re wondering what a spline is, in the first place. A spline is a mathematic curve that is defined by several polynomials. You can picture them mentally by several small and simple curves combined to each others, giving the curve an interesting shape and properties. Now why we want splines is easy to understand: imagine a curve, something smooth and a bit complex (maybe even with loops). Now, imagine you want to make an object move along that curve. How do you represent that curve and how to you “make something advance along it?”

Splines are defined by several “control points”, also known “keys”, “knots” or whatever makes sense
to you. Those are just points of interest that will have a direct impact on how the curve will bend
and behave. Most of control points have the interesting property that the curve **will** pass
through them, allowing you to define points you want your object to pass by, for instance. Not all
control points have that property, though.

Now all the magic happens with those control points: when you want to sample a value at a given
control point, you just get back the value carried by this control point… but when you want to
sample in between two control points, for instance, you get back an *interpolated value*. That
interpolation is the key to why we want splines. Several interpolation mechanisms exist and I’m sure
you know at least two:

**Constant interpolation**: it means that given two control points, sampling at the first control point or any part between the control points will give you the carried value of the first control point. You will get the carried value of the second control point if you sample at its sampling value. That might be like a useless feature but it is very handy when designing and implementing “stop-by” movement with camera.**Linear interpolation**: this one you might know it, especially if you attended math courses at high-school. Linear interpolation is often referred to as “drawing a straight line”. And typically, “everything linear” can often graphed with a straight line! Thank about linear complexity (*O(n)*) and what it looks like on a graph. Linear interpolation that gives you a strict blending of arguments depending at which distance you sample from them. If sample at`t = 0`

, you get 100% of the first value and 0% of the second value. If you sample at`t = 0,5`

, you get an equal amount of both value (so you get the mean between both value). At`t = 1`

, you get 0% of the first value and 100% of the second value. Simple but really useful.**Cosine interpolation**: this one is known by people who are used to animation, graphics, motion design, etc. Cosine interpolation gives you a smoother interpolation than the linear one and provides a first derivative that is more interesting (i.e. it translates to*acceleration*).- Others: splines provide you with some other interpolation modes and some (that I really want!) are missing. For instance, cubic Bézier interpolation is something I want and that I already have coded in the Haskell version of the splines crate. It should be easy to add but so far, no one has asked for them and I don’t need them, so… ;)

Keep in mind that a spline is a just an abstractio mathematical object and that you can use it for lots of concepts and situations. For instance, in demoscene productions of mine, I use splines for camera movement, animation transitions, color-blending and more!

The splines crate has been around for some time now and I received some feedback from people on the GitHub page asking for more features. Basically, the crate can now:

- Support failible sampling more sanely (instead of panicking on some very trick situations, you
get a
`None`

). - Support for polymorphic sampling types (you have
`f32`

but also`f64`

or whatever).

I think something interesting to dissect in this blog article is the last feature about polymorphic sampling types and what I had to do in order to make it happen. Also, this is highly correlated to a design choice I have made months ago: supporting foreign crates to interpolate specific types is done inside the splines crate, not in other crates. I will discuss why just bellow.

Basically, in splines, prior to `1.0.0`

, a spline was polymorphic type mapping a key of type `f32`

to a control point of type `Key<V>`

, `V`

being the carried value. You then manipulate a `Spline<V>`

.
The problem with that is whenever someone wants to use a different time, like, `f64`

or something of
their own.

My first solution was to turn the spline type to `Spline<T, V>`

. That would allow people to use both
`f32`

and `f64`

as sampling type. The problem kicks in with the code handling those sampling values.
For instance, for the `Interpolation::Cosine`

interpolation mode, I need to take the cosine of a
value which type is either `f32`

or `f64`

. How can we do that in a generic and polymorphic maneer?

num-traits to the rescue!

Yeah, so was my first thoughts. I then re-wrote most of the interpolating code using num-traits…
and then decided to tackle all the feature gates. Because, I haven’t told you yet, but splines has
several feature gates allowing you to use, e.g., implement the `Interpolate`

trait for some famous
crates’ types (nalgebra, cgmath), enable serde serialization, etc. One feature gate that is
important to me as a demoscener is the `"std"`

feature gate, that, if not defined, makes the
splines crate compile with the `no_std`

feature.

And here comes the first problems. The num-traits has a trait that isn’t compatible with `no_std`

,
the `Float`

trait. I then sat
in front of my computer and thought. I came
to the realization that whatever library I would use for that trait, I would always get my hands
tied by the *contracts of the public interface of that crate*, for a feature that is almost central
to the whole splines crate. It quickly became obvious that I couln’t use num-traits.

Yes, I know about the

`FloatCore`

trait. However, I was stuck with`FloatConst`

right after that and I just wanted to clean the interface.

The monomorphic version of splines is easy to implement for `no_std`

, but now I’m stuck because of
some simple traits? Naaah.

So I decided to write my own traits. Enter: `Additive`

, a simple trait with no content but `Add`

and
`Sub`

as supertraits (and some non-important ones for comprehension here), `One`

, a trait that
provides the neutral element of the multiplication for a given type (i.e. the multiplication monoid)
and the `Linear<T>`

trait, providing linear combinations, mandatory for all kind of interpolations
mentioned earlier.

Those traits have universal implementors so that you don’t have to implement them. And enabling a feature gate for, e.g., cgmath will also implement those traits accordingly in an enough polymorphic way that you shouldn’t have to ever worry about them.

Just a little remark of mine: implementing the support for cgmath was pretty simple and
straight-forward. As feared (because I used this crate), nalgebra was way harder to get right —
and I even decided not to implement the `Point<..>`

type because I’ve been struggling all the
afternoon with error types that reminded me old and dark times with C++ Boost library. I’ve already
discussed that with people from the nalgebra world and none seemed to agree with me that this
crate is *a little bit too overengineered*. For instance, adding the support for nalgebra in
splines also adds several mandatory dependencies — i.e. num-traits and alga. It’s not that bad,
but if you want to play with simple vector spaces, I really do not recommend nalgebra as it’s a
really convoluted library with lots of `type`

aliases and types with infinite counts of type
variables. Maybe it’s just a confirmation bias of mine, because I’ve always used (and written, back
then in C++) linear libraries that were both simple and fast. nalgebra makes me think of this and
this is driving me crazy.
I’m not saying it’s bad. I’m saying it’s not for me and that I wouldn’t recommend it for people
wanting to do simple things — and yes, video game still falls in that *simple things* bag.

So, the design of feature gating in splines. I know it might feel a bit weird to have gates like
`"impl-nalgebra"`

or `"impl-cgmath"`

but to me it makes lots of sense. For a simple reason: a crate
exposes several types and functions via its public API. Everything that is not public is not for a
very good reason. Mostly, *invariants*. An invariant is something that must remain true *before* a
function / morphism / whatever is called and *after*. What happens in between can actually break
that invariant. The idea is that *“If a function breaks internally an invariant, it must restore it
before returning”*, so that the API remains safe to use.

Invariants are central in my way of thinking. Everytime I write some code, everytime I design an
interaction between several piece of algorithms, crates or even cross-language and cross-systems, I
always asks myself *“Am I breaking an invariant here? Is it possible to fuck up a state or a hidden
property somewhere?”*

In Rust, invariants are not a first-class citizen of the language (have a look at how the D
language handles `invariant`

: it’s interesting!). However, they still exist. Imagine this piece of
code:

```
pub struct Even(pub u64);
impl Even {
pub fn new(nth: u64) -> Self {
Even(nth * 2)
}
}
impl Add<u64, Output = Even> for Even {
fn add(self, rhs: u64) -> Output {
Even(self.0 + rhs * 2)
}
}
```

Imagine this is wrapped in a crate `num-even`

. Adding a `u64`

to an `Even`

gives you the nth next
even number. All of this is cool. But there is an invariant. The carried `u64`

by `Even`

must…
remain even. If at some time a user handle a `Even`

with an odd `u64`

inside of it, something has
gone wrong terribly. And with this current implementation, it’s very easy to break such an
invariant. Consider:

```
use num_even::Even;
fn main() {
let mut a = Even::new(1); // the 1st even number
a.0 += 1; // oooooooh, fuuuuuuu-
}
```

I had long heated debates with people on IRC about why this kind of library should be patched. The main argument of people who would think it shouldn’t be patched is “Yeah but we want users to have access to the underlying objects in any way they want.” I think invariants matter most. The patch version is actually a negative diff:

```
pub struct Even(u64);
```

Done. Here, the invariant cannot be broken anymore because people cannot create or modify `Even`

by hand. Constraining is powerful. You should try it. :)

splines holds keys in a `Spline<..>`

that must remain sorted. Hence, you don’t have a direct
access to the keys nor you can mutate them. Mutating keys would imply resorting the keys in a
smart way, which is something I haven’t needed yet.

So, that’s all for me for today. If you have any question about splines, please feel free to open an issue on GitHub. Also, if you’re interested in trying it, please have a look at the splines-1.0.0-rc.1 release candidate. It contains everything you need to get started!

The documentation is not up to date and some is missing, but it should be enough to start.

As always, keep the vibes!