Skip to main content

Cubic Spline Interpolation

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

Please Help,

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.

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
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 
>
>
>
>
> ________________________________
> From: "java3d-interest@javadesktop.org"
> 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)]
>
> http://forums.java.net/jive/thread.jspa?messageID=348553
>
> ---------------------------------------------------------------------
> 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
For additional commands, e-mail: interest-help@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 
>
>
>
>
> ________________________________
> From: "java3d-interest@javadesktop.org"
> 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)]
>
> http://forums.java.net/jive/thread.jspa?messageID=348553
>
> ---------------------------------------------------------------------
> 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
For additional commands, e-mail: interest-help@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
For additional commands, e-mail: interest-help@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
For additional commands, e-mail: interest-help@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?

Many thanks for your help.

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 

________________________________
From: "java3d-interest@javadesktop.org"
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)]

http://forums.java.net/jive/thread.jspa?messageID=348553

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net
For additional commands, e-mail: interest-help@java3d.dev.java.net

[att1.html]
[Spline.java]
---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net
For additional commands, e-mail: interest-help@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 

________________________________
From: "java3d-interest@javadesktop.org"
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)]

http://forums.java.net/jive/thread.jspa?messageID=348591

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net
For additional commands, e-mail: interest-help@java3d.dev.java.net

[att1.html]

capolise
Offline
Joined: 2009-05-31

Using individual spline you obtain new Zi values considering only the trend over one direction. For example if I interpolate Z over row I ignore the trend of the values over column.I thought that the interp2 matlab function was capable to generate the new Zi values considering at least the trend over row and over column.