[css-color-4] Gamut mapping pseudocode is confusing

[nex3]

The sample pseudocode for gamut mapping is confusing, particularly in step 18 (the "while" loop). There are cases where the pseudocode doesn't say whether the loop should continue looping, but it's not clear whether that means it should terminate or implicitly continue (since 18 says "repeat the following steps"). This is made more confusing by the fact that sometimes the pseudocode does explicitly say to continue.

For example, if at step 18.3 min_inGamut is false and inGamut(current) is true, neither condition in 18.3 nor 18.4 will match, and there's no explicit indication what should happen. I tried checking the Color.js implementation as a reference, but it seems that it runs step 4 incorrectly in this case. What is the correct behavior here?

[nex3]

I'm going to assume that the answer for that particular example is that if min_inGamut is false and inGamut(current) is true, the loop should terminate and return clipped immediately because otherwise no change is actually made to the loop parameters so the loop would continue indefinitely. But that also feels strange, because clipped hasn't been reassigned since the last update to min or max. Either way, the pseudocode should probably make this explicit.

[romainmenke]

I tried implementing it and it got stuck in that while loop.

const JND = 0.02;
const EPSILON = 0.0001;

export function mapGamut(
	startOKLCH: Color,
	toDestination: (x: Color) => Color,
	fromDestination: (x: Color) => Color,
): Color {

	// 11. set current to origin_Oklch
	const current = startOKLCH;

	// 12. set clipped to clip(current)
	let clipped = clip(toDestination(current));

	// 13. set E to delta(clipped, current)
	let E = deltaEOK(OKLCH_to_OKLab(fromDestination(clipped)), OKLCH_to_OKLab(current));

	// 14. if E < JND
	if (E < JND) {
		// 14.1. return clipped as the gamut mapped color
		return clipped;
	}

	// 15. set min to zero
	let min = 0.0;
	// 16. set max to the Oklch chroma of origin_Oklch
	const max = current[1];
	// 17. let min_inGamut be a boolean that represents when min is still in gamut, and set it to true
	let min_inGamut = true;

	// 18. while (max - min is greater than epsilon) repeat the following steps
	while ((max - min) > EPSILON) {
		// 18.1. set chroma to (min + max) / 2
		const chroma = (min + max) / 2.0;
		// 18.2. set the chroma component of current to chroma
		current[1] = chroma;
		// 18.3. if min_inGamut is true and also if inGamut(current) is true, set min to chroma and continue to repeat these steps
		if (min_inGamut && inGamut(toDestination(current))) {
			min = chroma;
			continue;
		}

		// 18.4. otherwise, if inGamut(current) is false carry out these steps:
		// 18.4.1. set clipped to clip(current)
		clipped = clip(toDestination(current));
		// 18.4.2. set E to delta(clipped, current)
		E = deltaEOK(OKLCH_to_OKLab(fromDestination(clipped)), OKLCH_to_OKLab(current));

		// 18.4.3. if E < JND
		if (E < JND) {
			// 18.4.3.1 if (JND - E < epsilon) return clipped as the gamut mapped color
			if ((JND - E) < EPSILON) {
				return clipped;
			}

			// 18.4.3.2 otherwise,
			// 18.4.3.2.1 set min_inGamut to false
			min_inGamut = false;
			// 18.4.3.2.2 set min to chroma
			min = chroma;
			continue;
		}
	}

	// 19. return clipped as the gamut mapped color
	return clip(toDestination([...current]));
}

Whereas my implementation based on a previous version of the pseudo code seemed to work as expected :

const JND = 0.02;
const EPSILON = 0.00001;

export function mapGamut(
	startOKLCH: Color,
	toDestination: (x: Color) => Color,
	fromDestination: (x: Color) => Color,
): Color {

	const current = startOKLCH;

	let min = 0.0;
	let max = current[1];

	while ((max - min) > EPSILON) {
		const chroma = (min + max) / 2.0;
		current[1] = chroma;

		const converted = toDestination(current);
		if (inGamut(converted)) {
			min = chroma;
			continue;
		}

		const clipped = clip(converted);
		const delta_e = deltaEOK(OKLCH_to_OKLab(fromDestination(clipped)), OKLCH_to_OKLab(current));
		if (delta_e < JND) {
			return clipped;
		}

		max = chroma;
	}

	return clip(toDestination([...current]));
}

[facelessuser]

@romainmenke It's a binary search, your first example is missing the else:

                // 18.4.3. if E < JND
		if (E < JND) {
			...
		}
                else {
                        max = chroma;
                }

I was responsible for the changes that helped speed up the algorithm, so I can speak to the intention of the algorithm even if the prose is confusing.

The intention was, assuming the color is out of gamut, to return a color just under the JND. Obviously, if the color starts out under the JND, the color is just clipped and returned, if not, we use a binary search to narrow down on a color just under the JND. The JND is our target, or better put, as close to the JND while not going over.

It is expensive to check if the color is in gamut on every iteration, so we stop doing it once we know the lower of the search is no longer in gamut. At that point, we can assume all iterations are out of gamut.

So we set the min to the current chroma if we know the lower bound is still in gamut and the current iteration is in gamut. If we ever get a color below the JND that is out of gamut, we set the min to chroma and we then know the minimum is no longer in gamut and we can stop doing in_gamut checks.

In short, once min_inGamut is false, we no longer need to check if the color is in gamut, we know it isn't. Then we can focus on bisecting to get as close to the JND as the threshold allows. Then we set min to chroma if we are below the JND and max to chroma if we are above. Once we are close enough to the JND, we kick out of the loop.

The only two exit conditions from the loop: if we get within the threshold of the JND, so JND - E < EPSILON or when the min and max are too close to each other while ((max - min) > EPSILON). There are no other exits.

[facelessuser]

@nex3 I was involved in ensuring the Color.js approach was implemented according to the intention of the spec. I won't deny though that the spec, as it is currently written, requires the reader to infer the intention which is not ideal.

otherwise, if inGamut(current) is false carry out these steps

This statement mentions "if the color is inGamut(current) is false", but if min_inGamut is false, we can assume the color is not in gamut even if we have not performed an explicit inGamut() check. So, yes, this is confusing and should be rephrased.

[nex3]

So if I'm understanding correctly, step 4 should probably just say "otherwise, carry out these steps:" since it should trigger if min_inGamut is false or if inGamut(current) is false (with the expectation that in practice min_inGamut = false implies inGamut(current) = false anyway). Is that right?

[facelessuser]

So if I'm understanding correctly, step 4 should probably just say "otherwise, carry out these steps:"

I believe that would be correct.

[svgeesus]

step 4 should probably just say "otherwise, carry out these steps:"

Done.