Built-in Tool's Tolerance Algorithm

[oblivioncth]

I've begun studying it by seeing how many up-ticks of tolerance it takes for the next pixel to be affected in a gradient (of hue, sat, light, or combinations of them) where each pixel is only 1 higher/lower than the previous, but at the point I've gotten to it seems that the transform for whether a pixel is included or not is not linear (though this in part is most likely due to the rounding that occurs when ticking H/S/L up and down, perhaps I should start with just RGB. And additionally there will be some relative scaling due to the tolerance slider being percentage based)

 

So, given that this means reversing it will take longer, I figured I'd simply ask if I could know what the algorithm paint.net uses for its tolerance level inclusion/exclusion calculations is (i.e. for the magic wand, paint bucket, etc.). This is assuming no anti-aliasing (though that part would be nice too).

 

I'm making a plugin that needs a tolerance slider and I want the behavior to be as close to the standard tools as possible; however, given that the implementation of this feature is potentially something that separates Paint.NET from its competitors, I can understand if whoever knows it would rather not share.

Edited September 17, 2020 by oblivioncth

[MJW]

I believe it's basically the Euclidean ARGB distance.

[oblivioncth]

28 minutes ago, MJW said:

I believe it's basically the Euclidean ARGB distance.

Ah, that's a great starting point. Thanks.

[MJW]

ILSpy disassembly:

// PaintDotNet.Tools.FloodFill.FloodFillAlgorithm
public static byte GetDistance(ColorBgra a, ColorBgra b)
{
	if (a.Bgra == b.Bgra)
	{
		return 0;
	}
	double aRF = ByteUtil.ToScalingDouble(a.R);
	double aGF = ByteUtil.ToScalingDouble(a.G);
	double aBF = ByteUtil.ToScalingDouble(a.B);
	double aAF = ByteUtil.ToScalingDouble(a.A);
	double bRF = ByteUtil.ToScalingDouble(b.R);
	double bGF = ByteUtil.ToScalingDouble(b.G);
	double bBF = ByteUtil.ToScalingDouble(b.B);
	double bAF = ByteUtil.ToScalingDouble(b.A);
	double deltaR = aRF - bRF;
	double sumR = deltaR * deltaR * aAF;
	double deltaG = aGF - bGF;
	double sumG = deltaG * deltaG * aAF;
	double deltaB = aBF - bBF;
	double sumB = deltaB * deltaB * aAF;
	double deltaA = aAF - bAF;
	double sumA = deltaA * deltaA;
	double sumSquared = sumR + sumG + sumB + sumA;
	double sum2 = Math.Sqrt(sumSquared);
	double sum3 = sum2 / 2.0;
	double distance = sum3 * 255.0;
	int distanceInt = (int)Math.Round(distance, MidpointRounding.AwayFromZero);
	byte distanceByte = (byte)distanceInt;
	return Math.Max(1, distanceByte);
}

 

(Don't know if there's some reason besides straight-forwardness that the squared value isn't compared to the squared tolerance to avoid the square root.)

[oblivioncth]

7 minutes ago, MJW said:

ISpy disassembly:

// PaintDotNet.Tools.FloodFill.FloodFillAlgorithm
public static byte GetDistance(ColorBgra a, ColorBgra b)
{
	if (a.Bgra == b.Bgra)
	{
		return 0;
	}
	double aRF = ByteUtil.ToScalingDouble(a.R);
	double aGF = ByteUtil.ToScalingDouble(a.G);
	double aBF = ByteUtil.ToScalingDouble(a.B);
	double aAF = ByteUtil.ToScalingDouble(a.A);
	double bRF = ByteUtil.ToScalingDouble(b.R);
	double bGF = ByteUtil.ToScalingDouble(b.G);
	double bBF = ByteUtil.ToScalingDouble(b.B);
	double bAF = ByteUtil.ToScalingDouble(b.A);
	double deltaR = aRF - bRF;
	double sumR = deltaR * deltaR * aAF;
	double deltaG = aGF - bGF;
	double sumG = deltaG * deltaG * aAF;
	double deltaB = aBF - bBF;
	double sumB = deltaB * deltaB * aAF;
	double deltaA = aAF - bAF;
	double sumA = deltaA * deltaA;
	double sumSquared = sumR + sumG + sumB + sumA;
	double sum2 = Math.Sqrt(sumSquared);
	double sum3 = sum2 / 2.0;
	double distance = sum3 * 255.0;
	int distanceInt = (int)Math.Round(distance, MidpointRounding.AwayFromZero);
	byte distanceByte = (byte)distanceInt;
	return Math.Max(1, distanceByte);
}

 

(Don't know if there's some reason besides staright-forwardness that the squared value isn't compred to the squared tolarence  to avoid the square root.)

 

It probably is just so it's simpler, which would explain some of the oddities with it.

 

That tool looks incredibly useful, is it this you were referring to? https://github.com/icsharpcode/ILSpy

 

I'd be interested in using it to see more, particularly what distances are considered included for what percentages.

Edited September 17, 2020 by oblivioncth

[MJW]

2 minutes ago, oblivioncth said:

That tool looks incredibly useful, is it this you were referring to? https://github.com/icsharpcode/ILSpy

 Yes, that's it (I fixed the name in my original comment). It is a really useful tool -- an excellent disassembler.

[Rick Brewster]

Avoiding the Sqrt is fine if you're just trying to compare values to determine which one is closer/farther. In this case we need to know the actual distance, mostly to keep calculations in a linear space instead of a quadratic space.

 

Summing the squares results in a value in the range [0, 4]

Squaring that results in a value in the range [0, 2]

Dividing by 2 leaves us with a values in the range [0, 1]

Multiplying by 255 and rounding gives a range [0, 255]

 

Zero means "equal", which is only allowed if the color values are actually equal. For all other >0 results, it is rounded up to 1 (out of 255).

[oblivioncth]

4 hours ago, Rick Brewster said:

Avoiding the Sqrt is fine if you're just trying to compare values to determine which one is closer/farther. In this case we need to know the actual distance, mostly to keep calculations in a linear space instead of a quadratic space.

 

Summing the squares results in a value in the range [0, 4]

Squaring that results in a value in the range [0, 2]

Dividing by 2 leaves us with a values in the range [0, 1]

Multiplying by 255 and rounding gives a range [0, 255]

 

Zero means "equal", which is only allowed if the color values are actually equal. For all other >0 results, it is rounded up to 1 (out of 255).

 

Thanks for elaborating.

 

I'd assume the tolerance percentage corresponds to this as some simple form of percent difference, but with 0 and 100% as exceptions to match only the exact color and match all colors respectively?

 

Or is it as simple as 0% -> 0 and 100% -> 255?

 

EDIT:

Seems to be a simple scaling of x/100 = y/255 according to the magic wand source (with some additional quadratic shaping from "FastScale()" in its case).

 

Man I wish C++ bytecode could be disassembled with this much detail in-tact . Obviously impossible since C# is interpreted by a VM and C++ is compiled all the way down

Edited September 18, 2020 by oblivioncth
Clarification

[MJW]

6 hours ago, oblivioncth said:

Obviously impossible since C# is interpreted by a VM and C++ is compiled all the way down

 

C# isn't interpreted. It's compiled into an intermediate language, which then compiled at runtime into machine code by the JIT compiler.

[oblivioncth]

30 minutes ago, MJW said:

 

C# isn't interpreted. It's compiled into an intermediate language, which then compiled at runtime into machine code by the JIT compiler.

Ah my mistake. I was under the impression that C# primarily used an interpreter like Java (though that can be implemented as a JIT too) after being compiled to its intermediary, but it seems that C# is always compiled down to native byte-code on the target machine.

[Rick Brewster]

Also, there's a fix going in for 4.2.14 -- you'll notice in the code above that only 1 of the color's alpha value is being used. Super weird. It's been causing trouble.

 

This is the new code. Notice the type of the parameters is now ColorPrgba128Float, which is already converted to float and premultiplied. Also, there was no important reason for using double-precision floats, so this should be faster now that it's using regular single-precision floats.

 

public static byte GetDistance(ColorPrgba128Float x, ColorPrgba128Float y)
{
    if (x == y || (x.A == 0.0f && y.A == 0.0f))
    {
        return 0;
    }

    float deltaR = x.R - y.R;
    float deltaG = x.G - y.G;
    float deltaB = x.B - y.B;
    float deltaA = x.A - y.A;

    float sumSquared = (deltaR * deltaR) + (deltaG * deltaG) + (deltaB * deltaB) + (deltaA * deltaA); // [0, 4]
    float sum2 = (float)Math.Sqrt(sumSquared); // [0, 2]
    float sum = sum2 / 2.0f; // [0, 1]

    float distance = sum * 255.0f;
    int distanceInt = (int)Math.Round(distance, MidpointRounding.AwayFromZero);
    Debug.Assert(distanceInt >= 0 && distanceInt <= 255);

    byte distanceByte = (byte)distanceInt;

    return Math.Max((byte)1, distanceByte);
}

 

[Reptillian]

Needless to say, the new code looks by far more understandable than the old code.

[Rick Brewster]

The old code also has a comment that's basically, "well this was how it was done in 3.5, so yolo ¯\_(ツ)_/¯" even though the code is obviously weird/wrong (mostly due to ignoring y's alpha value)