## Zen and the art of cublic spline interpolation

Centripidity
Posts: 137
Joined: Sun Jan 22, 2023 5:18 am
Location: Melbourne
Contact:

### Re: Zen and the art of cublic spline interpolation

ColinP wrote: Tue Jun 06, 2023 8:15 pm I've never heard of the Atlantic International University. It seems a bit strange that you can download a first class 1,263 page book for free so I'm not going to post a link.
According to Wikipedia, "Atlantic International University, Inc. (AIU) is an unaccredited private for-profit distance learning university based in Honolulu, Hawaii." If the Atlantic University is in Hawaii I can only hope they don't run a course in Geography. UrbanCyborg
Posts: 528
Joined: Mon Nov 15, 2021 9:23 pm

### Re: Zen and the art of cublic spline interpolation

Colin, the way I'd imagine you'd use Bézier curves in your application would be to join them end to end; so long as the derivative into each side of a join point is identical, they'll still be C1 continuous. Then, the end points would be your interpolation points.

Reid
Cyberwerks Heavy Industries
ColinP
Posts: 843
Joined: Mon Aug 03, 2020 7:46 pm

### Re: Zen and the art of cublic spline interpolation

UrbanCyborg wrote: Wed Jun 07, 2023 8:03 am Colin, the way I'd imagine you'd use Bézier curves in your application would be to join them end to end; so long as the derivative into each side of a join point is identical, they'll still be C1 continuous. Then, the end points would be your interpolation points.

Reid
Right, thanks Reid. I think I understand. Although one source of confusion is the terminological difference between Bezier control points P1 and P2 (that don't lie on the line) and the end points P0 and P4 which do whereas in the Hermite spline all points are control points and they are all on the line.

According to this...

https://en.wikipedia.org/wiki/Composite ... zier_curve

...to achieve C1 in cubic Bezier P4 must be 2P3 - P2.

I'm not sure this has any advantages over the Hermite approach. It doesn't seem as simple conceptually as the method I'm already using at least. But that doesn't mean a lot sometimes complex solutions are much more efficient than simple ones.

To be honest I've run out of time on this as I have like 22 items on my to do list and I've already spent ages on this tiny aspect of the project.

I'm currently looking at fonts...
UrbanCyborg
Posts: 528
Joined: Mon Nov 15, 2021 9:23 pm

### Re: Zen and the art of cublic spline interpolation

Yeah, I wasn't suggesting that you abandon a solution you already had working in favor of one that might be better. I was just tossing out information. I believe I know the other van Dam and Foley book you mentioned, but it's not shelved with my pile of preferred texts, so I may not have it. Been a long while since I've had to do any graphics work, although it's what I always got hired for, no matter which position I applied for. As soon as they see that on your resume, that's all they want to know. I was a lot more interested in Audio and AI, but there was generally only one such position, even at a large outfit, and not much turnover in it.

Reid
Cyberwerks Heavy Industries
ColinP
Posts: 843
Joined: Mon Aug 03, 2020 7:46 pm

### Re: Zen and the art of cublic spline interpolation

Here's a very slightly modified version of the source code. Unfortunately the tabs are still messed up by the forum software.

Code: Select all

``````import java.util.Arrays;

// cubic spline interpolation

public class CubicSpline
{
// constructor for immutable instance
// precomputes tangents for subsequent calls to interpolate()
// yInputs is an array of at least two Y values that represent the control points (aka nodes)
// the x values are implicit integers equidistant from 0 to the length of yInputs - 1
// if monotone is true the tangents are adjusted to prevent non-monotonic artifacts
// i.e. overshoot that doesn't seem appropriate given the input data
// but in practice it can be safely set to false to speed things up
// note the yInput data does not need to be monotonic

public CubicSpline( double[] yInputs, boolean monotone )
{
// n is the number of control points
int n = yInputs.length;

// make our own copy to decouple from the outside world...
y = Arrays.copyOf( yInputs, n );

double[] d = new double[ n - 1 ];      // temp array of slopes
m = new double[ n ];    // array of tangents

// calc slopes...
for( int i = 0; i < n - 1; i++ )
d[ i ] = y[ i + 1 ] - y[ i ];    // the change in y

// calc tangets...
m[ 0 ] = d[ 0 ];
for( int i = 1; i < n - 1; i++ )
m[ i ] = ( d[ i - 1 ] + d[ i ] ) * 0.5;   // the average of the slopes
m[ n - 1 ] = d[ n - 2 ];

// optionally modify tangents to preserve monotonicity...
if( monotone )
{
for( int i = 0; i < n - 1; i++ )
{
if( d[ i ] == 0 )
{
// zero slope
m[ i ] = 0;
m[ i + 1 ] = 0;
}
else
{
// non-zero slope
double a = m[ i ] / d[ i ];
double b = m[ i + 1 ] / d[ i ];
double h = Math.hypot( a, b );
if( h > 9 )
{
double t = 3 / h;
m[ i ] = t * a * d[ i ];
m[ i + 1 ] = t * b * d[ i ];
}
}
}
}
}

// interpolate f( x ) for precomputed values using cubic Hermite spline interpolation
// 0 <= x <= number of y values - 1
// out of bounds x handled safely by clamping
// results pass exactly through every control point

public double interpolate( double x )
{
// handle limits...
if( x <= 0 )
return y[ 0 ];

int maxIndex = y.length - 1;
if( x >= maxIndex )
return y[ maxIndex ];

// array index is integer part of x...
int i = (int) Math.floor( x );

// difference is fractional part of x...
double t = x - i;

// compute the cubic Hermite spline interpolation...

// h00( t ) * y0 +
// h10( t ) * m0 +
// h01( t ) * y1 +
// h11( t ) * m1

// where the basis functions are the following polynomials...
// h00( t ) == 2t^3 - 3t^2 + 1
// h10( t ) == t^3 - 2t^2 + t
// h01( t ) == -2t^3 + 3t^2
// h11( t ) == t^3 - t^2

// these can be rearranged as follows...
// h00( t ) == ( 1 + 2 * t ) * ( 1 - t ) ^ 2
// h10( t ) == t * ( 1 - t) ^ 2
// h01( t ) == t ^ 2 * ( 3 - 2 * t )
// h11( t ) == t ^ 2 * ( t - 1 )

// and coded efficiently like so...

return ( y[ i ] * ( 1 + 2 * t ) + m[ i ] * t ) * ( 1 - t ) * ( 1 - t )
+ ( y[ i + 1 ] * ( 3 - 2 * t ) + m[ i + 1 ] * ( t - 1 ) ) * t * t;
}

private double[] m;     // array of tangents
private double[] y;     // array of y values

}
``````

The difference is that CubicSpline objects are now immutable. In other words they can only be created, they can't be modified. This approach might seem a little alien to veterans like me obsessed with efficiency but I'm increasingly moving to immutable coding as it's automatically thread-safe. (And in practice the previous precompute() method wasn't particularly memory efficient anyway!)

Having wasted lots of time over the years chasing bizarre bugs caused by thread-safety issues (including this week, when I finally got around to implementing automation braking in Adroit Custom and found the previous version of this code falling over) and being unhappy with the messy and sometimes inefficient aspects of managing synchronization, I've very recently come around to the opinion that immutabilty is a fantastic idea.

It's not a particularly neat concept in old fashined languages like C++ because it relies heavily on high-quality automatic garbage collection to keep things clean and C++ doesn't even have automatic garbage collection never mind high-quality automatic garbage collection.

If you have to manage the heap yourself then conventional concurrent mechanisms like locking or manually dealing with atomic pointers is probably still the way to go but I've recently realised that Java's GC is incredibly good. You'd not use this particular CubicSpline implementation for sample-rate interpolation but I just did a test actually creating a new CublicSpline object 48,000 times per second and VM seems to not bat an eyelid. One might expect the GC to struggle but it doesn't appear to have much impact on performance. Although I've not left it running for hours so maybe my opinion will change in future but the memory load goes down as well as up when monitored so I don't think there's a pile of unseen garbage building up waiting to clog the system. But as I said before, you wouldn't normally use this precomputation method for sample-rate interpolation anyway.
ColinP
Posts: 843
Joined: Mon Aug 03, 2020 7:46 pm

### Re: Zen and the art of cublic spline interpolation

For anyone thinking what the hell is this guy wittering on about in the post above. In practice what this amounts to is that previously you'd create a CubicSpline object with interpolator = new CubicSpline() once then do the precomputation separately with interpolator.precompute( values, false ). While now you'd use interpolator = new CubicSpline( values, false ) every time.