Skip to main content

Spline Interpolation

12 replies [Last post]
davidbrowne
Offline
Joined: 2003-06-11
Points: 0

Is the Interpolator that is returned from Interpolators.getSplineInstance() supposed to be compatible with the SMIL standard? This would be important to know for any conversion to or from SVG. From my tests, it seems to be more or less compatible with the Timing Framework's behavior, but not the SMIL standard. Maybe I am missing something.

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
davidbrowne
Offline
Joined: 2003-06-11
Points: 0

Is there a different place that I should have sent the signed SCA to other than the official one? I emailed a scanned copy almost 4 weeks ago, and faxed it in 1 week ago, and I still am not showing up on the list.

Chris Campbell

Hi David,

Sorry for the delays; I don't know what the cause is, but I'm looking
into it right now.

Thanks,
Chris

scenario@javadesktop.org wrote:
> Is there a different place that I should have sent the signed SCA to other than the official one? I emailed a scanned copy almost 4 weeks ago, and faxed it in 1 week ago, and I still am not showing up on the list.
> [Message sent by forum member 'davidbrowne' (davidbrowne)]
>
> http://forums.java.net/jive/thread.jspa?messageID=254048
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@scenegraph.dev.java.net
> For additional commands, e-mail: dev-help@scenegraph.dev.java.net
>

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

campbell
Offline
Joined: 2003-06-24
Points: 0

Hi David,

It seems there was a backlog from winter break, which has now been processed. Your name is now on the list, so we can finally take a look at your code.

Thanks,
Chris

davidbrowne
Offline
Joined: 2003-06-11
Points: 0

Thanks Chris. I hope it is useful to you.

campbell
Offline
Joined: 2003-06-24
Points: 0

Hi David,

I've finally (finally!) committed the code that you contributed, as well as a test case based on the one you posted in this thread. I did some minor code formatting/doc cleanup, as well as renamed the class. Hopefully you and others can pound on it in the coming weeks and will let us know if there are any concerns. Thanks again for the contribution, and sorry for taking so long to get around to this.

Chris

davidbrowne
Offline
Joined: 2003-06-11
Points: 0

No worries, Chris. Glad to help.

Chris Campbell

Hi David,

On Dec 13, 2007, at 4:26 PM, scenario@javadesktop.org wrote:
> Is the Interpolator that is returned from
> Interpolators.getSplineInstance() supposed to be compatible with
> the SMIL standard?

It should be, yes.

> This would be important to know for any conversion to or from
> SVG. From my tests, it seems to be more or less compatible with
> the Timing Framework's behavior, but not the SMIL standard. Maybe
> I am missing something.

Can you provide a testcase that demonstrates the differences that
you're seeing? It's hard to guess what the problem could be otherwise.

Thanks,
Chris

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

davidbrowne
Offline
Joined: 2003-06-11
Points: 0

Hi Chris,

I should first point you to this discussion on the Timing Framework forum, http://forums.java.net/jive/thread.jspa?threadID=33844&tstart=0

The Scene Graph numbers are similar to the Timing Framework numbers, so I am assuming that you are using a similar approach. To quote pepe, "It looks like SplineInterpolator acts as a constant velocity path following algorithm, which is different from what i understood of the smil spec. It actually returns Y based on calculations of the length of the curve instead of 'just' returning the Y of projection of the factor on X axis onto the curve."

Both Mozilla and Batik come pretty close to the SMIL numbers.

Mozilla uses Newton-Raphson on the power series version of the Bezier equation, starting with a reasonable first guess. See section 6.4 of http://brian.sol1.net/svg/report/report.pdf for a more detailed algorithm description.

Batik does not use Newton-Raphson nor does it start with a good first guess. It just iterates until it converges to an answer within a tolerance.

In the code below, I get the SMIL interpolated values (which are admittedly approximate) from the table after Figure 7 at http://www.w3.org/TR/SMIL/animation.html#animationNS-OverviewSpline

[code]
import java.text.NumberFormat;
import com.sun.scenario.animation.Interpolator;
import com.sun.scenario.animation.Interpolators;

public class SplineInterpolationTest
{
private static final NumberFormat nf = NumberFormat.getInstance();
static {
nf.setMinimumFractionDigits(3);
nf.setMaximumFractionDigits(3);
}

private final float x1, y1, x2, y2;
private final float[] smilData;

public static String scaleFrom10To20(float normalizedVal) {
return nf.format(10 + normalizedVal*10);
}

public SplineInterpolationTest(float x1, float y1, float x2, float y2,
float[] smilData) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
this.smilData = smilData;
}

public void runComparison() {
Interpolator splineInterpolator =
Interpolators.getSplineInstance(this.x1, this.y1, this.x2, this.y2);

System.out.println("\nControl points: (" + x1 + ", " + y1 + "), (" + x2 +
", " + y2 + ")");
System.out.println("x\tsecond\tSMIL\tSG");
float increment = 1f / (smilData.length - 1);
for (int i = 0; i < smilData.length; ++i) {
float x = i * increment;
System.out.println(x + "\t" + i + "\t" + nf.format(smilData[i]) + "\t" +
scaleFrom10To20(splineInterpolator.interpolate(x)));
}
}

public static void main(String[] args) {
new SplineInterpolationTest(0f, 0f, 1f, 1f,
new float[]{10f, 12.5f, 15f, 17.5f, 20f}).runComparison();
new SplineInterpolationTest(0.5f, 0f, 0.5f, 1f,
new float[]{10f, 11f, 15f, 19f, 20f}).runComparison();
new SplineInterpolationTest(0f, 0.75f, 0.25f, 1f,
new float[]{10f, 18f, 19.3f, 19.8f, 20f}).runComparison();
new SplineInterpolationTest(1f, 0f, 0.25f, 0.25f,
new float[]{10f, 10.1f, 10.6f, 16.9f, 20f}).runComparison();
}
}
[/code]

Thanks,
David

Chris Campbell

Hi David,

The current Scenario implementation of Interpolators.Spline uses
something called Path behind the scenes, which was written to provide
interpolation for arbitrary n-dimensional Bezier curves. (We also
use Path for spatial interpolation via MotionPath, but the
Interpolators.Spline case is just a trivial 2-dimensional use case.)
Anyway, the basic approach is similar to what was in TimingFramework,
in that we subdivide/flatten the curve and then iterate through the
segments to find the answer. This may not be the right approach for
compatibility with SMIL (nor is it the most optimal). Would you or
someone else like to look into this discrepancy and perhaps suggest a
different implementation? The approach used in the Mozilla paper
might be a good place to start, although I haven't looked at it in
detail.

Thanks,
Chris

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

davidbrowne
Offline
Joined: 2003-06-11
Points: 0

Hi Chris,

Ok, here is an implementation that I am pretty happy with.

[code]
/**
*

Description: This is an implementation of a spline interpolator for
* spline animation that tries to follow the specification referenced by
* http://www.w3.org/TR/SMIL/animation.html#animationNS-OverviewSpline
*
* Basically, a cubic Bezier curve is created with start point (0,0) and
* endpoint (1,1). The other two control points (px1, py1) and (px2, py2) are
* given by the user, where px1, py1, px1, and px2 are all in the range [0,1].
* A property of this specially constrained Bezier curve is that it is strictly
* monotonically increasing in both X and Y with t in range [0,1].
*
* The interpolator works by giving it a value for X. It then finds what
* parameter t would generate this X value for the curve. Then this t parameter
* is applied to the curve to solve for Y. As X increases from 0 to 1, t also
* increases from 0 to 1, and correspondingly Y increases from 0 to 1. The
* X-to-Y mapping is not a function of path/curve length.
*

*
* @author David C. Browne
*/
public class BezierInterpolator {
/**
* the coordinates of the 2 2D control points for a cubic Bezier curve,
* with implicit start point (0,0) and end point (1,1) -- each individual
* coordinate value must be in range [0,1]
*/
private final float x1, y1, x2, y2;

/**
* do the input control points form a line with (0,0) and (1,1), i.e.,
* x1 == y1 and x2 == y2 -- if so, then all x(t) == y(t) for the curve
*/
private final boolean isCurveLinear;

/**
* power of 2 sample size for lookup table of x values
*/
private static final int SAMPLE_SIZE = 16;

/**
* difference in t used to calculate each of the xSamples values -- power of
* 2 sample size should provide exact representation of this value and its
* integer multiples (integer in range of [0..SAMPLE_SIZE]
*/
private static final float SAMPLE_INCREMENT = 1f / SAMPLE_SIZE;

/**
* x values for the bezier curve, sampled at increments of 1/SAMPLE_SIZE --
* this is used to find the good initial guess for parameter t, given an x
*/
private final float[] xSamples = new float[SAMPLE_SIZE + 1];

/**
* constructor -- cubic bezier curve will be represented by control points
* (0,0) (px1,py1) (px2,py2) (1,1) -- px1, py1, px2, py2 all in range [0,1]
* @param px1 is x-coordinate of first control point, in range [0,1]
* @param py1 is y-coordinate of first control point, in range [0,1]
* @param px2 is x-coordinate of second control point, in range [0,1]
* @param py2 is y-coordinate of second control point, in range [0,1]
*/
public BezierInterpolator(float px1, float py1, float px2, float py2) {
// check user input for precondition
if (px1 < 0 || px1 > 1 || py1 < 0 || py1 > 1 ||
px2 < 0 || px2 > 1 || py2 < 0 || py2 > 1) {
throw new IllegalArgumentException("control point coordinates must " +
"all be in range [0,1]");
}

// save control point data
x1 = px1;
y1 = py1;
x2 = px2;
y2 = py2;

// calc linearity/identity curve
isCurveLinear = ((x1 == y1) && (x2 == y2));

// make the array of x value samples
if (!isCurveLinear) {
for (int i = 0; i < SAMPLE_SIZE + 1; ++i) {
xSamples[i] = eval(i * SAMPLE_INCREMENT, x1, x2);
}
}
} // BezierInterpolator()

/**
* get the y-value of the cubic bezier curve that corresponds to the x input
* @param x is x-value of cubic bezier curve, in range [0,1]
* @return corresponding y-value of cubic bezier curve -- in range [0,1]
*/
public float interpolate(float x) {
// check user input for precondition
if (x < 0 || x > 1) {
throw new IllegalArgumentException("x must be in range [0,1]");
}

// check quick exit identity cases (linear curve or curve endpoints)
if (isCurveLinear || x == 0 || x == 1) {
return x;
}

// find the t parameter for a given x value, and use this t to calculate
// the corresponding y value
return eval(findTForX(x), y1, y2);
} // interpolate()

/**
* use Bernstein basis to evaluate 1D cubic Bezier curve (quicker and more
* numerically stable than power basis) -- 1D control coordinates are
* (0, p1, p2, 1), where p1 and p2 are in range [0,1], and there is no
* ordering constraint on p1 and p2, i.e., p1 <= p2 does not have to be true
* @param t is the paramaterized value in range [0,1]
* @param p1 is 1st control point coordinate in range [0,1]
* @param p2 is 2nd control point coordinate in range [0,1]
* @return the value of the Bezier curve at parameter t
*/
private float eval(float t, float p1, float p2) {
// Use optimzied version of the normal Bernstein basis form of Bezier:
// (3*(1-t)*(1-t)*t*p1)+(3*(1-t)*t*t*p2)+(t*t*t), since p0=0, p3=1
// The above unoptimized version is best using -server, but since we are
// probably doing client-side animation, this is faster.
float compT = 1 - t;
return t * (3 * compT * (compT * p1 + t * p2) + (t * t));
} // eval()

/**
* evaluate Bernstein basis derivative of 1D cubic Bezier curve, where 1D
* control points are (0, p1, p2, 1), where p1 and p2 are in range [0,1], and
* there is no ordering constraint on p1 and p2, i.e., p1 <= p2 does not have
* to be true
* @param t is the paramaterized value in range [0,1]
* @param p1 is 1st control point coordinate in range [0,1]
* @param p2 is 2nd control point coordinate in range [0,1]
* @return the value of the Bezier curve at parameter t
*/
private float evalDerivative(float t, float p1, float p2) {
// use optimzed version of Berstein basis Bezier derivative:
// (3*(1-t)*(1-t)*p1)+(6*(1-t)*t*(p2-p1))+(3*t*t*(1-p2)), since p0=0, p3=1
// The above unoptimized version is best using -server, but since we are
// probably doing client-side animation, this is faster.
float compT = 1 - t;
return 3 * (compT * (compT * p1 + 2 * t * (p2 - p1)) + t * t * (1 - p2));
} // evalDerivative()

/**
* find an initial good guess for what parameter t might produce the x-value
* on the Bezier curve -- uses linear interpolation on the x-value sample
* array that was created on construction
* @param x is x-value of cubic bezier curve, in range [0,1]
* @return a good initial guess for parameter t (in range [0,1]) that gives x
*/
private float getInitialGuessForT(float x) {
// find which places in the array that x would be sandwiched between,
// and then linearly interpolate a reasonable value of t -- array values
// are ascending (or at least never descending) -- binary search is
// probably more trouble than it is worth here
for (int i = 1; i < SAMPLE_SIZE + 1; ++i) {
if (xSamples[i] >= x) {
float xRange = xSamples[i] - xSamples[i-1];
if (xRange == 0) {
// no change in value between samples, so use earlier time
return (i - 1) * SAMPLE_INCREMENT;
} else {
// linearly interpolate the time value
return ((i - 1) + ((x - xSamples[i-1]) / xRange)) *
SAMPLE_INCREMENT;
}
}
}

// shouldn't get here since 0 <= x <= 1, and xSamples[0] == 0 and
// xSamples[SAMPLE_SIZE] == 1 (using power of 2 SAMPLE_SIZE for more
// exact increment arithmetic)
return 1;
} // getInitialGuessForT()

/**
* find the parameter t that produces the given x-value for the curve --
* uses Newton-Raphson to refine the value as opposed to subdividing until
* we are within some tolerance
* @param x is x-value of cubic bezier curve, in range [0,1]
* @return the parameter t (in range [0,1]) that produces x
*/
private float findTForX(float x) {
// get an initial good guess for t
float t = getInitialGuessForT(x);

// use Newton-Raphson to refine the value for t -- for this constrained
// Bezier with float accuracy (7 digits), any value not converged by 4
// iterations is cycling between values, which can minutely affect the
// accuracy of the last digit
final int numIterations = 4;
for (int i = 0; i < numIterations; ++i) {
// stop if this value of t gives us exactly x
float xT = (eval(t, x1, x2) - x);
if (xT == 0) {
break;
}

// stop if derivative is 0
float dXdT = evalDerivative(t, x1, x2);
if (dXdT == 0) {
break;
}

// refine t
t -= xT/ dXdT;
}

return t;
} // findTForX()

} // class BezierInterpolator
[/code]

Thanks,
David

campbell
Offline
Joined: 2003-06-24
Points: 0

Hi David,

Thanks for digging into this. Unfortunately I didn't see your name on the SCA signatories list:
https://sca.dev.java.net/CA_signatories.htm

and we can't look at your code until you sign the SCA:
https://sca.dev.java.net/

Once you sign, we'd be happy to discuss it more.

Sorry for the hassle,
Chris

davidbrowne
Offline
Joined: 2003-06-11
Points: 0

Chris,

I just emailed my signed scanned copy of the agreement to the sca email address.

David