# Smooth Monotonic Interpolation

Geraint LuffProducing a smooth, *intuitive* curve from a set of control points.

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.

## The problem

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.

### Monotonic

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.

### Our requirements

So, the curve we want must:

- pass through all the input points
- be smooth (continuous gradient)
- be monotonic within each segment

## Smooth interpolation

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:

### Cubic segments

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:

#### Example code

Here's a C++ class for setting up and evaluating a single cubic segment:

### Choosing gradients

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.

#### Non-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.

## Wrapping up

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

### Results

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!

### C++ Implementation

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.

### VST demo

If you're on Mac, you can try out the above class as an interactive demo:

Alright, that's all for now.