# Cubic Spline Interpolation

10 replies [Last post]
fmulder145
Offline
Joined: 2009-05-14

I am currently using Java3D and need to create a smooth curve in 3-Space. I have 3 to 4 known points in 3-Space and I would like to interpolate a smooth curve on these points - using cubic splines?

Does Java3D have a class for this already? If not (or even if so), can anyone help me with this problem?

Thank you.

gmiecznik

Hi,

I came accross this piece of code while search for curve interpolation. I
still cannot figure out how you interpolate on a series of [i,y(i)] values.
Am I supposed to call xySplineFn(double xA[], double trueX)?
What are xA[]? I appears that you only process 4 elements of xA only. How do
you do it across, say 100 points?

Thank you

Don Casteel wrote:
>
> For 3D spline interpolation I useÂ 3 seperate 1D spline curves, one for
> each X,Y, and Z values.
> Â
> All you need to do is create 3 instances of the Spline class andÂ solve for
> the same value ofÂ "t" in each of them.....
>
> X=fx(t)
> Y=fy(t)
> Z=fz(t)
>
> It works very well andÂ it's actually muchÂ faster thanÂ calculating all
> threeÂ dimensions at the same time.
>
> The attachedÂ class could be easilyÂ added toÂ with a new constructor and
> method that would accept a Point3D array and return a point, but I just
> use it as is.
>
> Don CasteelÂ
>
>
> FreelanceÂ PortfolioÂ Â  Deviant Art Home
> Deviant Art Gallery
> Project HomeÂ
>
>
>
>
> ________________________________
> To: interest@java3d.dev.java.net
> Sent: Sunday, May 31, 2009 5:50:49 AM
> Subject: Re: Cubic Spline Interpolation
>
> I also looking for a java routine that emulates the interp2 matlab
> function; I found many interpolation class but all for y=f(x) curves and
> nothing for z=f(x,y) surfaces. Previously I was used matlab interp2 with
> the default method, cubic spline interpolation, that is sufficient for my
> precision/performance requirements. Could you send me your code even if it
> is incomplete?
>
> Many thanks for your help.
> [Message sent by forum member 'capolise' (capolise)]
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net
> For additional commands, e-mail: interest-help@java3d.dev.java.net
>
>
>
> public class Spline {
> private double y[];
> private double y2[];
>
> /**
> * The constructor calculates the second derivatives of the interpolating
> function
> * at the tabulated points xi, with xi = (i, y[i]).
> * Based on numerical recipes in C,
> http://www.library.cornell.edu/nr/bookcpdf/c3-3.pdf .
> * @param y Array of y coordinates for cubic-spline interpolation.
> */
> public Spline(double y[]) {
> this.y = y;
> int n = y.length;
> y2 = new double[n];
> double u[] = new double[n];
> for (int i = 1; i < n - 1; i++) {
> y2[i] = -1.0 / (4.0 + y2[i - 1]);
> u[i] = (6.0 * (y[i + 1] - 2.0 * y[i] + y[i - 1]) - u[i - 1]) / (4.0 +
> y2[i - 1]);
> }
> for (int i = n - 2; i >= 0; i--) {
> y2[i] = y2[i] * y2[i + 1] + u[i];
> }
> }
>
> /**
> * Returns a cubic-spline interpolated value y for the point between
> * point (n, y[n]) and (n+1, y[n+1), with t ranging from 0 for (n, y[n])
> * to 1 for (n+1, y[n+1]).
> * @param n The start point.
> * @param t The distance to the next point (0..1).
> * @return A cubic-spline interpolated value.
> */
> public double fn(int n, double t) {
> return t * y[n + 1] - ((t - 1.0) * t * ((t - 2.0) * y2[n] - (t + 1.0) *
> y2[n + 1])) / 6.0 + y[n] - t * y[n];
> }
>
> public double xySplineFn(double xA[], double trueX)
> {
> double X=trueX;
> double Y=0.0;
> double T=trueX/3.0+0.3333333333;
> int count=0;
> // System.out.println("y[]= " + y[0] + "," + y[1] + "," + y[2] + "," +
> y[3]);
> do
> {
> double aTinv = 1.0-T;
> double xC=(
> xA[0]*1.0*Math.pow(T,3.0)+
> xA[1]*3.0*Math.pow(T,2.0)*Math.pow(aTinv,1.0)+
> xA[2]*3.0*Math.pow(T,1.0)*Math.pow(aTinv,2.0)+
> xA[3]*1.0*Math.pow(aTinv,3.0)
> );
> T+=(xC-T)/2.0;
> X=(T-0.3333333333)*3.0;
> //System.out.println("count= " + count++ + "\tT= " + T + "\ttrueX= " +
> trueX + "\tx= " + X + "\txC= " + xC);
> }while(Math.pow(X-trueX,2.0)>0.0001);
>
> Y=(
> y[0]*1.0*Math.pow(1.0-T,3.0)+
> y[1]*3.0*Math.pow(1.0-T,2.0)*Math.pow(T,1.0)+
> y[2]*3.0*Math.pow(1.0-T,1.0)*Math.pow(T,2.0)+
> y[3]*1.0*Math.pow(T,3.0)
> );
> // System.out.println("Spline value of Y=" + Y + " at T= " + T);
> return Y;
> }
> }
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net
> For additional commands, e-mail: interest-help@java3d.dev.java.net
>

--
View this message in context: http://www.nabble.com/Cubic-Spline-Interpolation-tp23547741p24884399.html
Sent from the java.net - java3d interest mailing list archive at Nabble.com.

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

Don Casteel

Appologies thatÂ it isn't as clear as it could be.

To use the class, first createÂ theÂ Spline from an array of values of any length using the constructor:Â
Spline mySpline = new Spline(myDoubleArray);
ThenÂ simply query the spline for a value at any point along the spline.
queryValue = mySpline.fn(ptNumInt,Â dist);
What is likely throwing you off is "ptNumInt" and "dist". Say your array had 100 values, and you want to know the spline value at say 57.34523. you would use
queryValue = mySpline.fn(57,Â 0.34523);
Translated: "give me the interpolated value atÂ 0.34523 (or 34.523%)Â theÂ way betweenÂ values 57 and 58 of myDoubleArray"

It's a little tougher to figure out with say 1270 values in the original array, because a query at 57.34523 has to be pre-calculated to (1270.0*57.34523)/100.0 = 728.284421 resulting in a query of:
queryValue = mySpline.fn(728,Â 0.284421);
>"give me the interpolated value atÂ 0.284421 (or 28.4421%)Â theÂ way betweenÂ values 728 and 729 of myDoubleArray"
Not very intuitive I know... I didn't write the original code (and was too lazy to change it).

One thing to keep in mind is these are 1-dimensional splines, it's best to think of the array values as evenly spaced, instead of trying to make sense of it as irregularly spaced points in space.

I hope this helps
Â
Don CasteelÂ

FreelanceÂ PortfolioÂ Â  Deviant Art Home
Deviant Art Gallery
Project HomeÂ

________________________________
From: gmiecznik
To: interest@java3d.dev.java.net
Sent: Sunday, August 9, 2009 12:20:35 AM
Subject: Re: Cubic Spline Interpolation

Hi,

I came accross this piece of code while search for curve interpolation. I
still cannot figure out how you interpolate on a series of [i,y(i)] values.
Am I supposed to call xySplineFn(double xA[], double trueX)?
What are xA[]? I appears that you only process 4 elements of xA only. How do
you do it across, say 100 points?

Thank you

Don Casteel wrote:
>
> For 3D spline interpolation I useÂ 3 seperate 1D spline curves, one for
> each X,Y, and Z values.
> Â
> All you need to do is create 3 instances of the Spline class andÂ solve for
> the same value ofÂ "t" in each of them.....
>
> X=fx(t)
> Y=fy(t)
> Z=fz(t)
>
> It works very well andÂ it's actually muchÂ faster thanÂ calculating all
> threeÂ dimensions at the same time.
>
> The attachedÂ class could be easilyÂ added toÂ with a new constructor and
> method that would accept a Point3D array and return a point, but I just
> use it as is.
>
> Don CasteelÂ
>
>
> FreelanceÂ PortfolioÂ Â  Deviant Art Home
> Deviant Art Gallery
> Project HomeÂ
>
>
>
>
> ________________________________
> To: interest@java3d.dev.java.net
> Sent: Sunday, May 31, 2009 5:50:49 AM
> Subject: Re: Cubic Spline Interpolation
>
> I also looking for a java routine that emulates the interp2 matlab
> function; I found many interpolation class but all for y=f(x) curves and
> nothing for z=f(x,y) surfaces. Previously I was used matlab interp2 with
> the default method, cubic spline interpolation, that is sufficient for my
> precision/performance requirements. Could you send me your code even if it
> is incomplete?
>
> Many thanks for your help.
> [Message sent by forum member 'capolise' (capolise)]
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net
> For additional commands, e-mail: interest-help@java3d.dev.java.net
>
>
>
> public class Spline {
> Â Â Â  private double y[];
> Â Â Â  private double y2[];
>
> Â Â Â  /**
> Â Â Â  * The constructor calculates the second derivatives of the interpolating
> function
> Â Â Â  * at the tabulated points xi, with xi = (i, y[i]).
> Â Â Â  * Based on numerical recipes in C,
> http://www.library.cornell.edu/nr/bookcpdf/c3-3.pdf .
> Â Â Â  * @param y Array of y coordinates for cubic-spline interpolation.
> Â Â Â  */
> Â Â Â  public Spline(double y[]) {
> Â Â Â  Â Â Â  this.y = y;
> Â Â Â  Â Â Â  int n = y.length;
> Â Â Â  Â Â Â  y2 = new double[n];
> Â Â Â  Â Â Â  double u[] = new double[n];
> Â Â Â  Â Â Â  for (int i = 1; i < n - 1; i++) {
> Â Â Â  Â Â Â  Â Â Â  y2[i] = -1.0 / (4.0 + y2[i - 1]);
> Â Â Â  Â Â Â  Â Â Â  u[i] = (6.0 * (y[i + 1] - 2.0 * y[i] + y[i - 1]) - u[i - 1]) / (4.0 +
> y2[i - 1]);
> Â Â Â  Â Â Â  }
> Â Â Â  Â Â Â  for (int i = n - 2; i >= 0; i--) {
> Â Â Â  Â Â Â  Â Â Â  y2[i] = y2[i] * y2[i + 1] + u[i];
> Â Â Â  Â Â Â  }
> Â Â Â  }
>
> Â Â Â  /**
> Â Â Â  * Returns a cubic-spline interpolated value y for the point between
> Â Â Â  * point (n, y[n]) and (n+1, y[n+1), with t ranging from 0 for (n, y[n])
> Â Â Â  * to 1 for (n+1, y[n+1]).Â
> Â Â Â  * @param n The start point.
> Â Â Â  * @param t The distance to the next point (0..1).
> Â Â Â  * @return A cubic-spline interpolated value.
> Â Â Â  */
> Â Â Â  public double fn(int n, double t) {
> Â Â Â  Â Â Â  return t * y[n + 1] - ((t - 1.0) * t * ((t - 2.0) * y2[n] - (t + 1.0) *
> y2[n + 1])) / 6.0 + y[n] - t * y[n];
> Â Â Â  }
> Â Â Â
> Â Â Â  public double xySplineFn(double xA[], double trueX)
> Â Â Â  Â Â Â  {
> Â Â Â  Â Â Â  double X=trueX;
> Â Â Â  Â Â Â  double Y=0.0;
> Â Â Â  Â Â Â  double T=trueX/3.0+0.3333333333;
> Â Â Â  Â Â Â  int count=0;
> //Â Â Â  Â Â Â  System.out.println("y[]= " + y[0] + "," + y[1] + "," + y[2] + "," +
> y[3]);
> Â Â Â  Â Â Â  do
> Â Â Â  Â Â Â  Â Â Â  {
> Â Â Â  Â Â Â  Â Â Â  double aTinv = 1.0-T;
> Â Â Â  Â Â Â  Â Â Â  double xC=(
> Â Â Â  Â Â Â  Â Â Â  Â  xA[0]*1.0*Math.pow(T,3.0)+
> Â Â Â  Â Â Â  Â Â Â  Â  xA[1]*3.0*Math.pow(T,2.0)*Math.pow(aTinv,1.0)+
> Â Â Â  Â Â Â  Â Â Â  Â  xA[2]*3.0*Math.pow(T,1.0)*Math.pow(aTinv,2.0)+
> Â Â Â  Â Â Â  Â Â Â  Â  xA[3]*1.0*Math.pow(aTinv,3.0)
> Â Â Â  Â Â Â  Â Â Â  Â  );
> Â Â Â  Â Â Â  Â Â Â  T+=(xC-T)/2.0;
> Â Â Â  Â Â Â  Â Â Â  X=(T-0.3333333333)*3.0;
> Â Â Â  Â Â Â  Â Â Â  //System.out.println("count= " + count++ + "\tT= " + T + "\ttrueX= " +
> trueX + "\tx= " + X + "\txC= " + xC);
>Â  Â Â Â  Â Â Â  Â Â Â  }while(Math.pow(X-trueX,2.0)>0.0001);
>Â  Â Â Â  Â Â Â  Â Â Â
> Â Â Â  Â Â Â  Y=(
> Â Â Â  Â Â Â  Â  y[0]*1.0*Math.pow(1.0-T,3.0)+
> Â Â Â  Â Â Â  Â  y[1]*3.0*Math.pow(1.0-T,2.0)*Math.pow(T,1.0)+
> Â Â Â  Â Â Â  Â  y[2]*3.0*Math.pow(1.0-T,1.0)*Math.pow(T,2.0)+
> Â Â Â  Â Â Â  Â  y[3]*1.0*Math.pow(T,3.0)
> Â Â Â  Â Â Â  Â  );
> //Â Â Â  Â Â Â  System.out.println("Spline value of Y=" + Y + " at T= " + T);
> Â Â Â  Â Â Â  return Y;
> Â Â Â  Â Â Â  }
> }
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net
> For additional commands, e-mail: interest-help@java3d.dev.java.net
>

--
View this message in context: http://www.nabble.com/Cubic-Spline-Interpolation-tp23547741p24884399.html
Sent from the java.net - java3d interest mailing list archive at Nabble.com.

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

[att1.html]

gmiecznik

All ,right, that is clear.

Yet it is still not clear how you would use the xySplineFn method.
Should I use this method for irregularly used points on the x-axis in the
same way as one would use the
fn method for regular intervals?

Thank you
Gregory

--
View this message in context: http://www.nabble.com/Cubic-Spline-Interpolation-tp23547741p24887649.html
Sent from the java.net - java3d interest mailing list archive at Nabble.com.

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

Don Casteel

It's been a long time since I've looked at this, let me find where I used the code and get back to you.

Not being the original author, I may end up having to re-write the class so it makes more sense.

Give me a day or so to get back to you.
Â
Don CasteelÂ

FreelanceÂ PortfolioÂ Â  Deviant Art Home
Deviant Art Gallery
Project HomeÂ

________________________________
From: gmiecznik
To: interest@java3d.dev.java.net
Sent: Sunday, August 9, 2009 9:32:37 AM
Subject: Re: Cubic Spline Interpolation

All ,right, that is clear.

Yet it is still not clear how you would use the xySplineFn method.
Should I use this method for irregularly used points on the x-axis in the
same way as one would use the
fn method for regular intervals?

Thank you
Gregory

--
View this message in context: http://www.nabble.com/Cubic-Spline-Interpolation-tp23547741p24887649.html
Sent from the java.net - java3d interest mailing list archive at Nabble.com.

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

[att1.html]

edwardboszczowski
Offline
Joined: 2006-02-05

Well, Only classses I know, but never has used is CubicSplineCurve, CubicSplineSegment , KBCubicSplineCurve, KBCubicSplineSegment, KBKeyFrame, KBRotPosScaleSplinePathInterpolator, KBSplinePathInterpolator.

By the little I saw they use Kochaneck-Bartels Spline that is good for animation. But there is some APIs that implement other types. Though the only I know is jgeom that implements Surfaces and curves NURBS (Non Uniform Rational BSpline).

I made some classes too for curves and surfaces, but they are incomplete. If you want I can pass to you. The curves implemented are bezier curve hermite curves and bspline uniform and non rational.

capolise
Offline
Joined: 2009-05-31

I also looking for a java routine that emulates the interp2 matlab function; I found many interpolation class but all for y=f(x) curves and nothing for z=f(x,y) surfaces. Previously I was used matlab interp2 with the default method, cubic spline interpolation, that is sufficient for my precision/performance requirements. Could you send me your code even if it is incomplete?

Don Casteel

For 3D spline interpolation I useÂ 3 seperate 1D spline curves, one for each X,Y, and Z values.
Â
All you need to do is create 3 instances of the Spline class andÂ solve for the same value ofÂ "t" in each of them.....

X=fx(t)
Y=fy(t)
Z=fz(t)

It works very well andÂ it's actually muchÂ faster thanÂ calculating all threeÂ dimensions at the same time.

The attachedÂ class could be easilyÂ added toÂ with a new constructor and method that would accept a Point3D array and return a point, but I just use it as is.

Don CasteelÂ

FreelanceÂ PortfolioÂ Â  Deviant Art Home
Deviant Art Gallery
Project HomeÂ

________________________________
To: interest@java3d.dev.java.net
Sent: Sunday, May 31, 2009 5:50:49 AM
Subject: Re: Cubic Spline Interpolation

I also looking for a java routine that emulates the interp2 matlab function; I found many interpolation class but all for y=f(x) curves and nothing for z=f(x,y) surfaces. Previously I was used matlab interp2 with the default method, cubic spline interpolation, that is sufficient for my precision/performance requirements. Could you send me your code even if it is incomplete?

[Message sent by forum member 'capolise' (capolise)]

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

[att1.html]
[Spline.java]
---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

capolise
Offline
Joined: 2009-05-31

Ok, but I have some points to clarify:
1. I have a Z=f(X,Y) function then a (X,Y) domain given by X and Y vector and the correspondant Z that is a matrix of X x Y dimensions.
2. I manually calculate the new Xi and Yi considering the minimum interval on X and Y. This giving me the new domain (Xi,Yi) for which I want to calculate the Zi matrix.

How can I use your class to calculate Zi for the given X,Y,Z,Xi,Yi?

Don Casteel

UnlessÂ my guess at what your trying to do is wrong, select a regularÂ intervalÂ and sampleÂ yourÂ function.

From the resultingÂ group of points extract the x,y, and z values into their respectiveÂ 1D arrays for the individual splines.

The tighter your sampling frequency is, the more points you'll have, and the more accurate the resulting spline will be.

Don CasteelÂ

FreelanceÂ PortfolioÂ Â  Deviant Art Home
Deviant Art Gallery
Project HomeÂ

________________________________
To: interest@java3d.dev.java.net
Sent: Sunday, May 31, 2009 5:07:03 PM
Subject: Re: Cubic Spline Interpolation

Ok, but I have some points to clarify:
1. I have a Z=f(X,Y) function then a (X,Y) domain given by X and Y vector and the correspondant Z that is a matrix of X x Y dimensions.
2. I manually calculate the new Xi and Yi considering the minimum interval on X and Y. This giving me the new domain (Xi,Yi) for which I want to calculate the Zi matrix.

How can I use your class to calculate Zi for the given X,Y,Z,Xi,Yi?
[Message sent by forum member 'capolise' (capolise)]