Here's something that's not directly audio-related, but comes up a lot in user interfaces for audio tools. The user specifies a set of "control points", and you have to extend those points into a smooth curve mapping one value to another:
This is a friendly interface for the user, useful for things like envelopes (mapping time to amplitude/etc.) or EQs (mapping frequency to amplitude). But in those cases, the curve just being "smooth" isn't enough.
Let's define a segment as the section of the curve between two adjacent control points.
Here are a couple of things we don't want:
Overshoot is particularly problematic when our control points are at or near 0, and our mapped value (e.g. amplitude) shouldn't really go below 0. But neither of these really look like the curve the user wanted.
The mathematical terms for what we want is a monotonic function between the two points, meaning the gradient of each segment can either be
This property means the curve can't have any peaks or dips that aren't exactly at a control point. This is nicely intuitive - when the user wants a peak/dip, they'll tell you exactly where it should be.
So, the curve we want must:
- pass through all the input points
- be smooth (continuous gradient)
- be monotonic within each segment
Let's tackle the first two requirements to start with: smoothly passing through all the input points.
In order to be smooth, the gradient for the end of one segment must match the gradient at the start of the next. A straightforward way to achieve this is to just decide what that gradient should be:
The segments could be any type of curve, but a common choice is cubic polynomials. With two (control) points and two (chosen) gradients, there is a unique cubic solution:
Let's call our start/end coordinates
We can solve for the cubic coefficients above using some basic calculus and some simultaneous equations - but the solution ends up a bit neater if we define a temporary variable:
This gives us the coefficients:
Here's a C++ class for setting up and evaluating a single cubic segment:
Given a set of points, how do we choose the gradients? There's no single "correct" answer - but this means we can pick a property which feels like it should be true, and see if we can construct a rule to make it true.
Let's say that we have an existing set of points which are following a quadratic curve. Our interpolation should be able to reconstruct this exactly:
This is enough to decide the gradient for each point: we fit a quadratic using the points on either side, and read the gradient from that.
We won't work through the steps here - this is the result:
You'll also need to decide what to do with the first and last points (because either
Smooth (non-monotonic) results
This gives us a smooth interpolated result between our control points:
Other ways to choose gradients
That's just one way to choose the gradient - you could instead take the average of the straight-line slopes on either side:
Or you could weight the straight-line slopes based on the output value (
Each method will produce a different curve:
Because we choose a single gradient for each point (shared by adjacent segments), the results are always smooth - but we still can end up with overshoot or extra peaks/dips. So let's deal with that!
Making the segments monotonic
It turns out we can make each segment monotonic with two simple constraints:
Flat gradient at peaks/dips
When one of the control points is a local maximum/minimum, we want to make sure the curve produces a minimum/maximum exactly on that point. So let's give those points a gradient of 0:
But this on its own isn't sufficient:
Limiting the gradients
Non-minimum/maximum points can also cause overshoot if their gradients are too steep:
We can handle this by limiting the gradient:
This gradient limit also (conveniently) guarantees that there are no intermediate peaks/dips inside the segment:
So that's all we need to get monotonic cubic segments.
While the flat gradient for peaks/dips is a universal requirement, the gradient limits are specific to the fact that our segments are cubics. The 3x gradient for cubics conveniently also guarantees no intermediate points/dips.
But you might choose a different family of curves for your segments - at which point you'll need a different set of gradient constraints.
So, to get a smooth curve with monotonic cubic segments:
- Choose a gradient for each point, with any method you like
- For all minimum/maximum control points, set their gradient to 0
- For all other points, apply the 3× limit
- Generate cubic segments as normal
Here's a look at this algorithm in action:
The curve itself is always smooth, but compared to the non-monotonic version, it doesn't respond quite as evenly when we move the control points - segments will suddenly bump up against one of our two gradient constraints (flat-peaks or the 3× limit).
But it's still neat!
Here's a header-only C++ implementation of this algorithm. Just set up the object, and add your points:
This class also supports "corner nodes" (which have a different gradient on each side) by adding in the same x/y co-ordinates twice in a row.
If you're on Mac, you can try out the above class as an interactive demo:
Alright, that's all for now.