Weird wrong colors in gradients

[jongleur1983]

Prerequisites

• I have written a descriptive issue title
• I have verified that I am running the latest version of ImageSharp
• I have verified if the problem exist in both DEBUG and RELEASE mode
• I have searched open and closed issues to ensure it has not already been reported

Description

This bug has been reported by @Wibble199 in Gitter on Oct, 29th 2019.
The following unit test (adapted from https://pastebin.com/RJQWm0za ) generates gradients with wrong colored pixels. Those pixels are at random(?) positions, not stable across re-running the same code.

[Theory]
[WithBlankImages(200, 200, PixelTypes.Rgb24)]
public void NewIssueTest<TPixel>(
    TestImageProvider<TPixel> provider)
    where TPixel : struct, IPixel<TPixel>
{
    provider.VerifyOperation(
        img =>
        {
            var brush = new PathGradientBrush(
                new[]
                {
                    new PointF(0, 0),
                    new PointF(200, 0),
                    new PointF(200, 200),
                    new PointF(0, 200),
                    new PointF(0, 0)
                },
                new[] { Color.Red, Color.Yellow, Color.Green, Color.DarkCyan, Color.Red });
            img.Mutate(m => m.Fill(brush));
        });
}

Current sample output (two different test runs):

or

The expected result is a smooth gradient between the four colors on the corners instead.

Steps to Reproduce

see code sample above.

While investigating the cause for easier debugging I reduced the maxDegreeOfParallelism to 1 and the issue is gone.
Thus it looks like something going on when applying the brush in parallel.

System Configuration

• ImageSharp version: current master branch
• Other ImageSharp packages and versions: -
• Environment (Operating system, version and so on): Windows 10 Version 1903, Build 18362.418
• .NET Framework version: 4.7.2
• Additional information:

[jongleur1983]

added unit test to reproduce the issue at https://github.com/jongleur1983/ImageSharp/tree/jongleur1983/1044-wrongPixelsInPathGradients :
see commit: jongleur1983@0f91e70

[jongleur1983]

investigations:

• errors don't occur when disabling parallelization
• when adding a debug output line in the this[x,y] accessor of the PathGradientBrushApplicator reduces wrong pixels dramatically, but doesn't solve all. I guess this is due to accidently limiting parallelization due to the System.Console access.
• Even though in my test with a debug output line per pixel access there's much less errors, in my first test run there was at least one, but no pixel has been accessed twice.

[JimBobSquarePants]

I can't spot anything in our code that specifically that would cause thread safety issues, however, IEnumerable<T> is not thread safe. I would assume read operations would be ok but without digging I cannot be sure. My advice would be to remove any Linq usage from the code (It must perform horribly anyway) and use an array instead of a list for PathGradientBrushApplicator<TPixel>.edges.

[jongleur1983]

I'll try, thanks.

[jongleur1983]

Looks like there are some more relatively easy performance and memory improvements possible while removing Linq.
Working on it...

[jongleur1983]

@JimBobSquarePants removing LINQ and using arrays/for-loops doesn't solve the issue itself, yet.
Should be faster though, so I commited the changes to the branch nevertheless.

[JimBobSquarePants]

Very odd. I couldn’t see any other potential areas where multi threading would be an issue.

Thanks for investigating this btw!

[jongleur1983]

You're welcome @JimBobSquarePants - as long as it could have been my "fault", at least I wanted to make sure it's not ;)
Now it's a challenge to solve it, so let's see.

[JimBobSquarePants]

Ignore the above commit message, it doesn't relate to this issue.

[JimBobSquarePants]

@jongleur1983 I had another look at this and I've figured it out.

This buffer which is created once when the edges are created during initialization of the applicator

ImageSharp/src/ImageSharp.Drawing/Processing/PathGradientBrush.cs

Line 136 in 7332e98

private readonly PointF[] buffer;

Is updated during every call to FindIntersection

ImageSharp/src/ImageSharp.Drawing/Processing/PathGradientBrush.cs

Line 164 in 7332e98

int intersections = this.path.FindIntersections(start, end, this.buffer);

I have a fix locally with the following code. I'm curious on your thought regarding using stackalloc?

public Intersection? FindIntersection(PointF start, PointF end, MemoryAllocator allocator)
{
    // TODO: Would this ever be too big for stackalloc?
    using (IMemoryOwner<PointF> memory = allocator.Allocate<PointF>(this.path.MaxIntersections))
    {
        Span<PointF> buffer = memory.Memory.Span;
        int intersections = this.path.FindIntersections(start, end, buffer);

        if (intersections == 0)
        {
            return null;
        }

        buffer = buffer.Slice(0, intersections);

        Intersection? min = null;
        for (int i = 0; i < buffer.Length; i++)
        {
            PointF point = buffer[i];
            var current = new Intersection(point: point, distance: ((Vector2)(point - start)).LengthSquared());

            if (min is null || min.Value.Distance > current.Distance)
            {
                min = current;
            }
        }

        return min;
    }
}

[jongleur1983]

Cool...
Regarding the StackAlloc: I'm not sure how the PathGradientBrush is used exactly. but I don't think it will be a problem in typical situations.

Trying to construct a worst-case example though it could be a big one:
Let's consider someone who wants to draw a color-circle and creates two PathGradientBrushes, each filling a region of half a circle.
1st stop is the circles center point in White, and then on the edges iterating once half through the color circle in as high resolution as possible (let's consider 255 hue values for the color in HSV, so 128 stops for half a circle)
As path.MaxIntersections is upper bound to the number of nodes of the path, in this case it's 128, so we'd have 128 PointF elements in buffer here.

As PointF has 2 floats and thus 8 bytes, that's 128*8=1024 byte - and that's a constructed case I guess not to be a real use case.
BUT: It's not Save as users of course could do any strange stuff here.

[JimBobSquarePants]

Thanks @jongleur1983 that's really useful!

Lets leave it using a pooled buffer for now then just in case. There's a lot of room for improvement performance-wise in the entirety of drawing code so I can revisit the solution when we start tackling that.