Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Change the default scheme interpolator? #28

Open
Fil opened this issue Jul 2, 2020 · 19 comments
Open

Change the default scheme interpolator? #28

Fil opened this issue Jul 2, 2020 · 19 comments
Assignees

Comments

@Fil
Copy link
Member

Fil commented Jul 2, 2020

All the interpolators based on an array of 9 or 11 values result in colors that are a bit duller than the original values. Using a Catmull-Rom interpolation (preferably L*a*b, but RGB is almost undistinguishable) would make them all vivid again:

the three bands below represent the array, the current interpolator, and the proposed change for RdYlBu
Capture d’écran 2020-07-02 à 12 06 17

See all the others at https://observablehq.com/@fil/interpolate-colors-with-catmull-rom

The catmull-rom interpolator would be added to d3-interpolate; Matt Deslauriers’s version, which I use here, is coming from the Three.js codebase and operates in 3D. I think we would want to change its API a bit to work for any dimension (at least d = 1, 2, 3), but I haven't checked that part yet.

EDIT: a monotone interpolator seems smaller and faster, with comparable results (see below).

@mbostock
Copy link
Member

mbostock commented Jul 2, 2020

I would like to measure the performance cost (e.g., when rendering a U.S. county choropleth and computing 3,243 colors), but this looks great. I’m guessing that RGB will be faster and if it’s not noticeably different we should favor it.

@Fil
Copy link
Member Author

Fil commented Jul 2, 2020

It seems 2 to 3 times slower https://observablehq.com/@fil/interpolate-colors-with-catmull-rom#speedtest ; lab maybe a bit slower than rgb, but it's not a huge impact. And I haven't yet looked at the catmull-rom implementation (though, coming from three.js, it's probably already very efficient).

@danburzo
Copy link

danburzo commented Jul 2, 2020

It's a bit messy, but I made a notebook to demonstrate monotone spline interpolation. Compared to Catmull-Rom, the monotone spline does not overshoot its control points (avoiding color aberrations), although in practice the two look nearly identical. I'm not sure which spline is faster to compute. You can also notice in the notebook a simple piecewise-linear interpolation in Lab already gets you most of the way there, but it tends to have sharper peaks corresponding to the control points.

@JobLeonard
Copy link

Is the monotone spline the same thing as the centripetal Catmull-Rom spline? That also has the property of avoiding overshoot (I think..) and that it never has self-intersections (unlike the default uniform CR splines)

https://en.wikipedia.org/wiki/Centripetal_Catmull%E2%80%93Rom_spline

@danburzo
Copy link

danburzo commented Jul 2, 2020

I'll steal another Observable notebook to exemplify :-P I've added an alpha slider to @jviide's notebook that takes the Catmull-Rom spline through the uniform (0) to the centripetal (0.5) to chordal (1). While alpha > 0.5 version minimizes the overshoot, it does not preclude it.

Note: I haven't got a good intuition on how 2D parametric vs. 1D Catmull Rom splines relate to each other, or for splines in general, so take this with a grain of salt :P

@Fil
Copy link
Member Author

Fil commented Jul 2, 2020

I've updated my notebook with a lab monotone; the difference is a little perceptible with the Set or Paired color schemes, but there is no way to say that one is better than the other. And for the schemes we target the difference is invisible. Speed and code footprint are much better, we're now only ~30% slower than the original code (and there's probably a few gains to be made in the implementation). Note that converting a bunch of colors to three arrays names l,a,b is also a good use case for the new transpose.

@Fil Fil changed the title Change the default interpolator to L*a*b Catmull-Rom? Change the default scheme interpolator? Jul 2, 2020
@Fil
Copy link
Member Author

Fil commented Jul 3, 2020

I've tightened up the implementation, and labMonotone is now even faster than the baseline "rgbbasis" (if you discount lab.toString(), which is now the bottleneck).

@Fil
Copy link
Member Author

Fil commented Jul 3, 2020

Added rgbmonotone. I don't have a strong opinion on which one should be the default, everything works globally fine and quickly.

@JobLeonard
Copy link

Well, given that most cases the results are very similar, I think we should look at the cases where it differs a lot:

Accent

Category10

Dark2

I know we're not typically going to interpolate categorical color ranges, but since these interpolators are supposed to work on custom color ranges I'd say these results still provide useful information.

From my POV the RGB options introduce false dark bands in these cases, so I'm in favor of Lab (maybe this is my color blindness though).

@waldyrious
Copy link

waldyrious commented Jul 3, 2020

From my POV the RGB options introduce false dark bands

Agreed. I wonder if the RGB interpolation done in linear (gamma-corrected) mode, as mentioned in d3/d3-interpolate#64. I was under the assumption that the dark bands would not occur if that were the case.

On a separate note, RGB interpolation introduces intermediate colors (e.g. a greenish tone between yellow and blue for the Accent scheme), which Lab doesn't. That's matches our intuitive expectation, but to be fair the Lab interpolation seems to be more accurate here as well.

@Fil
Copy link
Member Author

Fil commented Jul 3, 2020

EDIT: as I was implementing unit tests I realized that the function I used was not monotone but just cubic. It seems good enough for our purposes, but we shouldn't call it monotone cubic (Evercoder/culori#91)

Here's a notebook that shows how it works in 2D and 1D
https://observablehq.com/d/f2e94a3321c17726

@danburzo
Copy link

danburzo commented Jul 3, 2020

As noted in Evercoder/culori#91, it seems I made a mistake in the implementation, but I think I have an idea of what's wrong with it, I'd like to see the effect with a proper monotone interpolator 😅

@mbostock
Copy link
Member

mbostock commented Jul 3, 2020

I agree with @waldyrious and would like to see a version that uses linear-light RGB.

@danburzo
Copy link

danburzo commented Jul 3, 2020

As noted in Evercoder/culori#91, starting with [email protected] the splineMonotone should be fixed. I've added LRGB (still from culori) to my fork of @Fil's notebook, and a monotone spline RGB interpolation. My conclusion is that the monotone spline in RGB is as good as in Lab for the color schemes included in the package, and should avoid the Lab roundtrip penalty. Often the LRGB version seems the most dissimilar from the others (in a bad way), at least on my monitor.

@waldyrious
Copy link

Often the LRGB version seems the most dissimilar from the others (in a bad way), at least on my monitor.

Was it intentional that you didn't include LRGB with monotone interpolation? I was curious to see that one in particular.

@danburzo
Copy link

danburzo commented Jul 3, 2020

@waldyrious I've added it now.

@waldyrious
Copy link

Thanks, that was enlightening. All the spline-based transitions for LRGB and Lab seem quite reasonable to my eyes (nearly indistinguishable, even) for the sequential color schemes.

The differences are notable in the categorical color schemes though. In particular, while avoiding the lightness dips, LRGB still has a tendency to insert new colors between two hues (e.g. purple between blue and pink in Accent, or between red and blue in Set1).

I took the liberty to fork your fork to test the most challenging transitions, and in my humble opinion (perhaps unsurprisingly) the Lab ones seem to be somewhat "truer" to the original schemes. But since this is intended for sequential schemes, I'd say Monotone SRGB should be a perfectly serviceable option for the default interpolator.

@JobLeonard
Copy link

So given that the graphs look so similar, I added @Fil's "perceptually uniform?" code to @danburzo's notebook to see if that might give us some insights on how the different options perform (well, according to the Ciede2000 model, which I guess is just that at the end of the day: a model). On top of that, I felt like the blurring smoothed away too many sharp edges, so I tried to implement a 1D version of the bilateral filter instead (can be toggled though).

Take a look here.

What's particularly interesting to me is that whenever we hit the "middle" of a color (so basically, a control point), the linear interpolators tend to have a sharp "kink" in the graph:

image

@Fil
Copy link
Member Author

Fil commented Jul 9, 2020

Since this is just a default, and the various options (among the best) are almost indistinguishable, my intention at this point is to implement the fastest of them, ie monotone RGB as defined in https://observablehq.com/@fil/interpolate-colors-with-catmull-rom#interpolateRgbMonotone :

interpolateRgbMonotone = colors => {
  const { r, g, b } = transpose(colors.map(d => d3.rgb(d)));
  const R = monotone(r),
    G = monotone(g),
    B = monotone(b);
  return t => d3.rgb(R(t), G(t), B(t));
}

it will need to wait for d3Interpolate.monotone and d3Array.transpose to land.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

No branches or pull requests

5 participants