Zen and the art of cublic spline interpolation

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

Re: Zen and the art of cublic spline interpolation

Post by Centripidity »

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." :lol:

If the Atlantic University is in Hawaii I can only hope they don't run a course in Geography. :D
UrbanCyborg
Posts: 588
Joined: Mon Nov 15, 2021 9:23 pm

Re: Zen and the art of cublic spline interpolation

Post by UrbanCyborg »

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 -- viewforum.php?f=76
ColinP
Posts: 939
Joined: Mon Aug 03, 2020 7:46 pm

Re: Zen and the art of cublic spline interpolation

Post by ColinP »

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: 588
Joined: Mon Nov 15, 2021 9:23 pm

Re: Zen and the art of cublic spline interpolation

Post by UrbanCyborg »

Yeah, I wasn't suggesting that you abandon a solution you already had working in favor of one that might be better. :D 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 -- viewforum.php?f=76
ColinP
Posts: 939
Joined: Mon Aug 03, 2020 7:46 pm

Re: Zen and the art of cublic spline interpolation

Post by ColinP »

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 )
               {
                  // adjust the tangents...
                  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: 939
Joined: Mon Aug 03, 2020 7:46 pm

Re: Zen and the art of cublic spline interpolation

Post by ColinP »

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.
Post Reply

Return to “Module Designer”