Cubic spline

[danburzo]

I dislike asking this question without having the proper vocabulary for it, but I was experimenting with reproducing Photoshop's Curves interface using D3 modules.

After reading up on some of the math, experimenting with polynomial interpolation (and experiencing Runge's phenomenon with it), I came back to a cubic spline interpolation — using a package that implements this algorithm — that gave me the correct result.

Pictured below, in combination with a clamped linear scale, and in comparison with some curves available in d3-shape:

• Would such a spline interpolator be a good addition to d3-interpolate?
• Is it called something specific? (I'm a bit lost among the various types of splines...)

Also, reading through the original implementation of this spline, it also mentions it being a natural spline, and I have found that in some situations, D3's curveNatural matches this implementation, but in others they diverge, further clouding my understanding of terms :D

[mbostock]

This should be a d3-shape issue rather than a d3-interpolate issue.

I believe the difference is that the other interpolation method you mention assumes that y is a function of x, whereas in the D3 implementation, a 2D parameterized spline is used (x and y are both functions of t). So with the D3 interpolation it is valid to have multiple values of y for the same x, as you see in your example image where the blue line curves left from (0,0) before curving right again.

Seems reasonable to consider a new curveCubicX implementation for this case.

[danburzo]

Thank you for the clarifications. I will move the issue over to d3-shape, and read more about how it might be implemented.

(Initially I wanted to log the issue there, but to my mind the curves from d3-shape were not readily available to use as interpolators, since their purpose is to generate Bézier curves for SVG rather than be used as t ↦ x_t, t ↦ y_t functions?)

[danburzo]

(Moved the issue here: d3/d3-shape#118)

[mbostock]

Well sure, it depends on what you’re asking for.

If you want to draw the spline, then I’d suggest a new curve implementation in d3-shape (which can be used to render to SVG or Canvas or anything else that understands piecewise cubic Béziers).

If you want to evaluate points along the spline for a given t in [0, 1], then you probably want an interpolator here in d3-interpolate, along the lines of d3.interpolateBasis. See an example usage here:

https://bl.ocks.org/mbostock/048d21cf747371b11884f75ad896e5a5

An interpolator can be used to draw the spline, but it’s pretty inefficient; the example above generators 1,000 samples along each spline and then draws a simple piecewise linear curve. Likewise a curve can be used to sample points along the spline, but that’s also inefficient since you need to go through an SVG API such as getPointAtLength.

[andreasplesch]

Smooth interpolation is useful outside of drawing curves. What would it take to translate the curve styles to interpolators ? I think the curves are mostly based on the svg native bezier curves. However, I think beziers can be represented as cubic splines: http://www.joshbarczak.com/blog/?p=730, others. So there may be a generic way to link spline interpolators to the curves. Let's first assume there is bezierPoints2splineControlpoints () function. Then see how it would be plugged into the curve factories.

[andreasplesch]

Perhaps this is already done somewhere outside of d3 ?

[andreasplesch]

https://github.com/d3/d3-shape/blob/acb6053eae36fe6dcdb0b62fe2691bee2acc511b/src/curve/basis.js does the inverse, eg. converts basis splines to Bezier.

[andreasplesch]

interpolateBasis() is uniform B-Spline. It looks like it would be easiest to just add interpolateBezier() with the Bezier basis functions,