search

SixLabors / ImageSharp.Drawing

:pen: Extensions to ImageSharp containing a cross-platform 2D polygon manipulation API and drawing operations.
https://sixlabors.com/products/imagesharp-drawing/
Other
282 stars 38 forks source link

Hangs when drawing a path #244

Open Fenyx4 opened 2 years ago

Fenyx4 commented 2 years ago

Prerequisites

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

brianpopow commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

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

Hope that helps.

JimBobSquarePants commented 2 years ago

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

Fenyx4 commented 2 years ago

Actual drawing operation

tocsoft commented 2 years ago

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. https://github.com/SixLabors/ImageSharp.Drawing/blob/dc838dc5d82d5e143bcf7e14b15bb6c172dd1314/src/ImageSharp.Drawing/Shapes/Clipper/clipper.cs#L4828

JimBobSquarePants commented 2 years ago

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 commented 1 year ago

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.