closed interpolation outside [0, 1]?

[Fil]

I wanted to use the closed interpolator outside [0,1], so in principle I thought it would be periodic; but in fact its domain is [0, 1 + 1/n], and it "crashes" outside.

Here's how I "fix" this:

culoriClosed = array => {
  const f = culori.interpolateSplineMonotone(d => d, "closed", 1)(array),
    n = array.length - 1,
    k = 1 + 1 / n;
  return t => f(k * (t - Math.floor(t)));
}

now the domain of culoriClosed is [0, 1] (we have a complete curve if t in [0, 1]), and we have f(t + integer) === f(t).

https://observablehq.com/d/f2e94a3321c17726 draws a spiral with -5 < t < 30, and the main domain as a loop, in heavy black.

[Fil]

Oops? This chart left we wondering if this was really a "monotone cubic" interpolator… as it overshoots in X and Y. So I think there is a small mistake here, the function is a standard cubic not a monotone cubic?

[danburzo]

Thanks for bringing this up! I'll have to get back to speed, but the spline should be implemented based on this paper that d3-shape mentions (I don't know why I failed to leave a comment with the reference). It states:

Construct a piecewise cubic interpolation function that passes through N data points in a monotonic way with the slope of the curve changing continuously across the junction points.

The monotone() function here:

culori/src/interpolate/splineMonotone.js

Lines 3 to 18 in a846314

	const monotone = (v0, v1, v2, v3, h, t) => {
	let h2 = h * h;
	let t2 = t * t;
	let t3 = t2 * t;
	let s20 = (v2 - v0) / (2 * h);
	let s31 = (v3 - v1) / (2 * h);
	let s21 = (v2 - v1) / h;
	return (
	((s20 + s31 - 2 * s21) / h2) * t3 +
	((3 * s21 - 2 * s20 - s31) / h) * t2 +
	s20 * t +
	v1
	);
	};

...should implement the equations (1) – (7) from page 445 (3 of 8 in the PDF). However I can't remember how I derived s20 and s31 (which correspond to y'(i) and y'(i+1) from the paper), and I'll have to review the paper and the code to figure out what's going on.

It does indeed seem the code produces a non-monotone result.

As for the initial issue you raised, I had t pinned to [0, 1] in my mind, but it makes sense to offer something better than crashing.

I'll take a look and get back, thanks again!

[danburzo]

In [email protected] the function looks like this:

culori/src/interpolate/splineMonotone.js

Lines 23 to 45 in 8e64a25

	const monotone = (y_im1, y_i, y_ip1, y_ip2, h, t) => {
	let h2 = h * h;
	let t2 = t * t;
	let t3 = t2 * t;
	let s_im1 = (y_i - y_im1) / h;
	let s_i = (y_ip1 - y_i) / h;
	let s_ip1 = (y_ip2 - y_ip1) / h;
	let yp_i =
	(sgn(s_im1) + sgn(s_i)) *
	min(abs(s_im1), abs(s_i), 0.5 * abs((y_ip1 - y_im1) / (2 * h)));
	let yp_ip1 =
	(sgn(s_i) + sgn(s_ip1)) *
	min(abs(s_i), abs(s_ip1), 0.5 * abs((y_ip2 - y_i) / (2 * h)));
	return (
	((yp_i + yp_ip1 - 2 * s_i) / h2) * t3 +
	((3 * s_i - 2 * yp_i - yp_ip1) / h) * t2 +
	yp_i * t +
	y_i
	);
	};

(I changed the variables a bit so I can better keep track of i-1, i, etc.)

Basically I had forgotten to apply equation (11) from the paper.

I still need to add some tests for the spline, but adding it to the Observable notebooks seems to indicate the problem is fixed.
Note that this particular spline, in the way it's implemented here, is only applicable to evenly spaced values along the x axis, so the drawing looks a bit weird now.

[Fil]

Excellent, thanks a lot! Indeed this is how the monotone spiral is supposed to look if we use it for the parametrized curve (x(t), y(t)).

I'll try and port it to d3-interpolate as well. I'm leaving this issue open since it's initially about the domain for the closed version.

[danburzo]

I've given closed splines further thought and I'm convinced at least the monotone one needs adjustments. What follows is me talking out loud :P

A basis spline can be clamped (the default), open, or closed. It's only for the clamped version that we have the property that t = 0 corresponds to the first color in the array, and t = 1 to the last; in general, a basis spline does not interpolate (pass through) it's control points at all.

Now, for interpolating splines (such as the monotone spline):

• The normal version (can we still call it clamped?) has monotone(0) = colors[0] and monotone(1) = colors[colors.length - 1]
• A closed monotone spline that interpolates the N colors will have to create space for an additional 1/N interval, to connect the first and last colors smoothly — where does it make sense to add the extra segment? at the beginning (meaning monotone(0) = monotone(1) = colors[colors.length - 1]), at the end (monotone(0) = monotone(1) = colors[0]), or half-and-half? (meaning neither of the two conditions are no longer true)

And, since the goal is to be able to swap a linear interpolation with a spline interpolation seamlessly, does that mean that piecewise-linear interpolation also needs a "closed" concept?

And, is "closed" as a term too closely tied to the B-spline? Should it be called cyclical or something to that effect?

Part of my problem with color interpolation is that I can't find a good abstraction to allow all the possible combinations without spelling them out explicitly and duplicating implementations (see #80):

• clamped vs. closed interpolation
• linear vs. spline interpolation
• different interpolation method per channel
• ability to control the normalization of special channels: e.g. for hue, shortest vs. longest path, clockwise, anticlockwise?

[Fil]

1. If you consider a "closed" polygon as having p[n-1] == p[0], the issue of having to "add 1/n" disappears. "Forgetting" to pass the closing value is just a convenience notation.

2. It would certainly be nice to have a closed piecewise-linear function, for completion.

3. "closed" is fine as a term, but (as you've just seen) I view it as meaning "continuous cyclical"—C₂ continuous for the cubic versions.

4. "clamped" is a better term than "default" ; "open" isn't really meaningful except for basis, I think?

5. Some color spaces require a circular interpolation on one dimension (hue), which is not yet available in our system. When hue goes from 350° to 10° it should "interpolate" via 0° (shortest path//geodesic), which basis/cubic/monotone don't have. It might be possible to split this into cos/sin channels, interpolate them and compute the atan2 of the result, but this approach seems a bit heavy-handed :)

6. "Longest path" is a bad name : what you want is to describe a complete journey in the color space. In d3-geo when we do this (for example to describe the equator as a LineString), we never write "take the longest path from [0,0] to [0,0]" but instead say "go from -180 to -90, then 0°, then 90°, then 180°"—and each part of the journey follows a geodesic. (This also solves the question of anti/clockwise.)

[danburzo]

"open" isn't really meaningful except for basis, I think?

I guess parallels from basis splines to other splines are not too far-fetched; in d3-shape they're implemented with the idea that in the open version of an interpolating spline (cardinal, Catmull-Rom), you "sacrifice" the first and last value in the array to be used merely as control points (to adjust the curve's slope at either ends) without having the curve pass through them. That would work equally well for the monotone spline. But yeah, I'm not sure if they're that meaningful / useful when interpolating colors specifically...

Some color spaces require a circular interpolation on one dimension (hue), which is not yet available in our system.

I've tried to solve this by tentatively introducing culori.interpolateHue as a sort of normalization function; for example, the default interpolation in lch looks like this:

	interpolate: {
		h: interpolateLinear(interpolateHue),
		c: interpolateLinear(),
		l: interpolateLinear(),
		alpha: interpolateLinear(interpolateAlpha)
	}

However, the API strikes me as a bit convoluted....

[Fil]

Ah yes https://github.com/Evercoder/culori/blob/master/src/interpolate/hue.js#L20