Polar stroking: new theory and methods for stroking paths

[JimBobSquarePants]

Motivation

Almost all of the time we spend drawing polygons is taken up by offsetting and clipping the polygon to the given pen width. To be considered a first-class alternative to System.Drawing and SkiaSharp we must vastly improve the performance.

I've been doing some research in the area, and it appears that people at Nvidia have been working on an incredibly robust and performant solution to the problem of path stroking.

At the following link they present videos, documents and a CPU based implementation of an algorithm that can also be implemented on the GPU should we ever choose to follow that path (pun intended).

Abstract + Videos
https://dl.acm.org/doi/abs/10.1145/3386569.3392458

Paper
kilgard2020.pdf

I've attached a copy of the zip file containing an updated project file as the original has device specific paths for the boost library includes that are required for the demonstration program.

polar-stroking.zip

It's going to take a significant amount of effort to implement this in C# and I personally lack the skills to do it so will be looking for a lot of help.

Thoughts @SixLabors/core

Input from the community is most welcome.

[antonfirsov]

I agree that there is a lot of space for improvement for stroking, but we should be very careful not to jump into conclusions about the superiority of a particular algorithm without having it understood and compared to alternatives. After taking a brief look at the material linked, I don't see any data about how fast does their tessellation algorithm perform compared to offsetting / clipping.

[antonfirsov]

Regardless of my previous comment, I'm also curious about AGG-s approach. Took a look at the article linked from @hypeartist 's
#295 (reply in thread) -- it doesn't go into details re stroking much, but looks like AGG is also doing some sort of stroke-to-fill.

[hypeartist]

Can you, guys, push me into where inside ISD the actual drawing impl is?

[JimBobSquarePants]

Absolutely!

All line stroking falls through the OutlinePathExtensions class. The extensions are called via Pen instances If you follow that through you will see ClipperOffset, PolygonOffsetter, and PolygonClipper are used to offset the path and clip it. PolygonScanner performs the rasterization.

[JimBobSquarePants]

@hypeartist Did you ever have a look at this? If so, did you see anything obvious in our implementation that you would suggest we look at?

I'm looking at your AGG code just now and not sure how portable some of it is as it's all a bit beyond me.

[JimBobSquarePants]

@hypeartist Do you have your sample code that you used to benchmark available. I'd like to start at the top and work down.

[hypeartist]

I'm assuming there's no hardware acceleration on the blending for your AGG code also

No such things in there atm. So I think there is quite some room for optimization possibilities.

[hypeartist]

Hey, James (both of you, actually). I'm sorry for being unresponsive. The end of the year was kinda hell busy at work. And now I'm on NY holidays and away from keyboard for a week or so. If you can wait I will provide you with any examples needed next week. пн, 1 янв. 2024 г. в 06:17, James Jackson-South ***@***.***>:

…

@hypeartist <https://github.com/hypeartist> Do you have your sample code that you used to benchmark available. I'd like to start at the top and work down. — Reply to this email directly, view it on GitHub <#295 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AA23HHCQBZSLYQJUPPRONEDYMITEZAVCNFSM6AAAAAA46IQMJOVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TSOBVHEYTK> . You are receiving this because you were mentioned.Message ID: ***@***.*** .com>

[JimBobSquarePants]

No problem at all!! 😀

[hypeartist]

@JimBobSquarePants Hi there!
Here is the demo solution I've used for benching AGG vs SKIA vs GDIP. Clicking on the screen will iterate though engines showing message box with timings. AGG will be rendered directly to the screen while SKIA and GDIP to files. (Since the initially the app is AGG-centric it would take some effort to render to the screen anything other than AGG buffer and I was lazy)
AggSharp_Test.zip

[JimBobSquarePants]

Thanks for this @hypeartist !! It looks like ConvStroke is the key here. If we can use a version of this instead of our current outliner we should be able to avoid most of the work we're doing now with the clipper port and continue to use our existing fast rasterizer.

It's going to take me a few weeks just to unwind this at best so if you, @antonfirsov, or anyone else reading this fancies having a crack please let me know.

[hypeartist]

Don't know if it could help, but still

[JimBobSquarePants]

Yeah thanks, I've got the fundamentals in my head of how it works. It's really more about time constraints and what happens when I mess up the port (which I will). I've got so much to do to ship the next version and I don't know how I'll manage it.

[antonfirsov]

I tried the demo and the AggSharp code seems to be the slowest.
The AggSharp test seems to be the slowest, but idk what is being benchmarked. As a next setep IMO someone needs to benchmark only the tessellation code (illustrated above) on it's own, and compare it to PolygonClipper's offsetter, and acquire a good understanding of the algorithm.

Looking at the implementation, it looks inefficient and prone to accumulate errors with the differential increments it's making with tesselation steps. Eg. Ellipse.cs:

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public override PathCommand Vertex(ref double x, ref double y)
{
	if (_step == _num)
	{
		++_step;

		return PathCommand.EndPoly | (PathCommand)(PathFlags.Close | PathFlags.Ccw);
	}

	if (_step > _num)
		return PathCommand.Stop;

	var angle = _step / (double)_num * Constants.Misc.PiMul2;
	if (_cw)
		angle = Constants.Misc.PiMul2 - angle;

	x = _x + Math.Cos(angle) * _rx;
	y = _y + Math.Sin(angle) * _ry;
	_step++;

	return _step == 1 ? PathCommand.MoveTo : PathCommand.LineTo;
}

[JimBobSquarePants]

This is the kind of insight I simply do not have. 😔

[JimBobSquarePants]

The more I look into this the more I see the sheer scope of the work involved. It seems more like a complete rewrite which I cannot do.

@antonfirsov Is there a reason why we don't split the work done by PolygonScanner into batches?

[hypeartist]

@JimBobSquarePants @antonfirsov Don't know if you, guys, have seen this or not, but still:
https://gasiulis.name/parallel-rasterization-on-cpu/ (https://github.com/aurimasg/blaze/tree/main)

[hypeartist]

is there a quality gap between the original C++ AGG polygon stroker and the C# port

It's almost 1-1 port, so I assume there shouldn't be any 'quality gap'

[JimBobSquarePants]

Oooh! That does look interesting. I’m no C++ guy though so would struggle with a port if it could be integrated.

[hypeartist]

@JimBobSquarePants Just a bit of show-off:

[JimBobSquarePants]

I'm going to need a lot of help. 2.5x slower than System.Drawing on my machine plus I still haven't figured out how to fix the ghosting. I really need to try porting that other rasterizer. 😔

BenchmarkDotNet v0.13.10, Windows 11 (10.0.22631.3085/23H2/2023Update/SunValley3)
11th Gen Intel Core i7-11370H 3.30GHz, 1 CPU, 8 logical and 4 physical cores
.NET SDK 8.0.200-preview.23624.5
  [Host]   : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2
  ShortRun : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2

Job=ShortRun  IterationCount=3  LaunchCount=1
WarmupCount=3

| Method         | Mean    | Error    | StdDev   |
|--------------- |--------:|---------:|---------:|
| DrawImageSharp | 1.855 s | 0.0426 s | 0.0023 s |