Jump to content

Built-in Tool's Tolerance Algorithm


Recommended Posts

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 by oblivioncth
Link to post
Share on other sites

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.)

Link to post
Share on other sites
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 by oblivioncth
Link to post
Share on other sites

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).

The Paint.NET Blog: https://blog.getpaint.net/

Donations are always appreciated! https://www.getpaint.net/donate.html

forumSig_bmwE60.jpg

Link to post
Share on other sites
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 by oblivioncth
Clarification
Link to post
Share on other sites
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.

Link to post
Share on other sites
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.

Link to post
Share on other sites

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);
}

 

The Paint.NET Blog: https://blog.getpaint.net/

Donations are always appreciated! https://www.getpaint.net/donate.html

forumSig_bmwE60.jpg

Link to post
Share on other sites

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)

The Paint.NET Blog: https://blog.getpaint.net/

Donations are always appreciated! https://www.getpaint.net/donate.html

forumSig_bmwE60.jpg

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...