[css-color-4] CSS gamut mapping algorithm pseudocode can result in infinite looping for some inputs

[weinig]

The CSS gamut mapping algorithm pseudocode can result in infinite looping for some inputs. As an example, gamut mapping the color oklch(104.4% 0 336) to display-p3 loops indefinitely due to the following steps:

gamut map oklch(104.4% 0 336) to display-p3:

origin_OKLCH -> oklch(104.4% 0 336)
inGamut<display-p3>(origin_OKLCH) -> false

min -> 0
max -> 0

start bisection loop:
    chroma -> 0
    current -> oklch(104.4% 0 336)

    inGamut<display-p3>(current) -> false
    current as display-p3 -> color(display-p3 1.058 1.058 1.058)

    clipped -> (display-p3 1 1 1)
    E -> delta(clipped, current)
          -> clipped as oklab(100% 0 5.96E-8)
          -> current as oklab(104.4% 0 0)
          -> sqrt(((100 / 100) - (104.4 / 100))^2 + (0 - 0)^2 + (5.96E-8 - 0)^2)
          -> 0.04

    0.04 is not less than JND of 0.02, so we loop forever

I added a condition to step 9.4.3 to also check if chroma was 0, making it something like:

        3. if E < JND or chroma is 0 convert clipped to destination and return it as the gamut mapped color

(though, it isn't really necessary to say "convert clipped to destination" since clipped is already in the destination color space by the definition of clip() in step 6.)

I haven't thought too deeply about whether there are any other cases that could infinite loop.

[weinig]

Thinking about this geometrically, I think this can also be fixed by clamping the origin_OKLCH lightness values between 0 and 1, since regardless of hue, the chroma should be reducible to an in gamut value in that lightness range. In practice, this probably means just returning { 1 1 1 origin.alpha } if lightness >= 1 and { 0 0 0 origin.alpha } if lightness is 0.

[facelessuser]

As this is a binary search, I'm surprised that the spec does not mention a restraint on the chroma value that is being altered to prevent the infinite loop. Once the low and high chroma is close enough to consider they've converged, the loop should terminate as bisecting it further may not reduce the delta between them at a certain point.

I'm not sure a restraint needs to be placed on lightness as when the loop kicks out because low and high chroma has essentially converged, if the color is not in gamut, it should be clipped as a final step which will essentially take care of the lightness. It seems that isn't really mentioned in the pseudocode though (maybe the intention had assumed that lightness would always be within an acceptable range?).

I'm not sure if in the future there may be cases where lightness could be greater than 1, but I can definitely see the logic that if lightness was clipped as things stand now, then if chroma bottoms out, you should always have an in gamut color.

[svgeesus]

Once the low and high chroma is close enough to consider they've converged

The algorithm doesn't test for this directly, instead testing for the deltaE between the current and clipped colors. However, that does assume that the only difference between the two is chroma. In the case @weinig mentioned, the chroma difference is almost zero and the deltaE value is entirely due to the lightness difference. So it will never converge.

(maybe the intention had assumed that lightness would always be within an acceptable range?).

Yes. There are algorithms that "toe in" the source black point to the destination blackpoint (black point compensation) but that matters more for HDR (and for print, where the deepest black cannot be assumed to have L=0), and similarly to map the source and destination media whitepoints (again, for HDR). But for RGB SDR, which is what this algorithm is for, then yes the assumption was that

1. the source and destination whitepoints are idential (relative colorimetry)
2. the source and destination blackpoints are identical (no black point compensation)
3. the Lightness values are in range and thus chroma reduction will always converge.

I think this can also be fixed by clamping the origin_OKLCH lightness values between 0 and 1, since regardless of hue, the chroma should be reducible to an in gamut value in that lightness range. In practice, this probably means just returning { 1 1 1 origin.alpha } if lightness >= 1 and { 0 0 0 origin.alpha } if lightness is 0.

I agree that there is no point reducing the chroma for black, colors darker than black, white, and colors lighter than (media) white. We already know the answer. So yes, I think the initial steps should be

1. let origin_OKLCH be origin converted to the OKLCH color space
2. if the Lightness of origin_OKLCH is greater than or equal to 100%, return { 1 1 1 origin.alpha } in destination
3. if the Lightness of origin_OKLCH is less than or equal to 0%, return { 0 0 0 origin.alpha } in destination
4. let inGamut(color) be a function etc etc as before

[facelessuser]

But for RGB SDR, which is what this algorithm is for

Ah, in that case, handling chroma >= 1 and <= 0 should prevent the algorithm from having such breakage. Makes sense. I didn't understand whether this was SDR specific or was meant to allow for HDR in the future, but if chroma is the only changing variable to get it in gamut, this makes sense.

[svgeesus]

Tone mapping, i.e. mapping HDR such that the source peak white maps to destination peak white, the media whites map correctly, and midtones still look like midtones without introducing noticeable hue shifts is significantly more complex than the SDR case. It is an area of active research, and mostly applied to SDR video (or occasionally images).

[svgeesus]

(though, it isn't really necessary to say "convert clipped to destination" since clipped is already in the destination color space by the definition of clip() in step 6.)

I fixed that one as well.