Hangs when drawing a path

[Fenyx4]

Prerequisites

• I have written a descriptive issue title
• I have verified that I am running the latest version of ImageSharp.Drawing
• 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

I had a bug in my code that set some (admittedly unreasonable) paths but when running it appears to get stuck and run forever in FixupIntersectionOrder.

Steps to Reproduce

I made a small project that reproduces it https://github.com/Fenyx4/SixLaborsHang
Probably could be made even smaller but I recreated the exact instance I ran into.

System Configuration

• ImageSharp.Drawing version: 1.0.0-beta15 (and 1.0.0-beta13)
• Other ImageSharp packages and versions:
  Fonts 1.0.0-beta18
  ImageSharp 2.1.3
• Environment (Operating system, version and so on):
  Windows 10
• .NET Framework version:
  3.1
• Additional information:
  Visual Studio 2022 - 17.3.2

[brianpopow]

This reproduction you provided is very big, it will be really hard to debug this in this form. Can you try to make it simpler?

[Fenyx4]

FYI I have been working on trimming this down.

As I trimmed it down I did discover a few things. It does not appear to run forever just a long, long time. Trimmed down versions run around an hour. When I remove some of the lines it drops down to around a minute. So I have been removing lines that don't cause it to drop below 50 minutes.

Oddly some lines I remove have caused the time to increase.

I'll keep working on getting a simpler version that still takes a long time but wanted to let you know the above in case it helps.

[Fenyx4]

Allrighty! Trimmed it down as much as I could and still have it above 50 minutes.

Hope that helps.

[JimBobSquarePants]

Does the hang occur during the PathBuilder.ClosePath operation or during the actual drawing operation?

[Fenyx4]

Actual drawing operation

[tocsoft]

The issue here is in the .GenerateOutline() extension/clipper library.

A much reduced case can be found with

var pathBuilder = new PathBuilder();
var transform = Matrix3x2.CreateRotation(-0.04433158f, new Vector2(948, 640));
pathBuilder.SetTransform(transform);
pathBuilder.AddQuadraticBezier(new PointF(-2147483648, 677), new PointF(-2147483648, 675), new PointF(-2147483648, 675));
IPath path = pathBuilder.Build();

// this line hangs/takes ages inside the 'clipper'
var outline = path.GenerateOutline(2);

this is the entry line that ends up hanging/taking a long time.

ImageSharp.Drawing/src/ImageSharp.Drawing/Shapes/Clipper/clipper.cs

Line 4828 in dc838dc

public void Execute(ref Paths solution, double delta)

[JimBobSquarePants]

Looks like Clipper2 is out! Maybe we could try dropping it in as a replacement?

https://github.com/AngusJohnson/Clipper2/releases/tag/Clipper2_1.0.4

[JimBobSquarePants]

Clipper2 seems to have the same problem. Will need to create an example and submit an issue/PR upstream.

We also cannot use them as a NuGet dependency as the library is not strong named.