Fix rasterizing artifacts: offset vector operations inside InternalPath so they center around zero

[tocsoft]

To prevent issues around imprecise floating point maths on large numbers we should offset all points as they are processed into the InternalPath precalulation data so that all values are a close to zero as possible. Then after calling InternalPath.FindIntersection and similar methods we apply the reverse offset into the correct space the original points applied to.

The will reduce potential issues that can arise by the increased imprecision that occurs the further floating point values are away from zero.

SixLabors/Shapes#43 provided a bandaid fix by using double instead of a floats for some operations thus providing a simple fix for large shapes but offsetting will provide us with an algorithm that will support not just large shapes but ones with large offsets from zero.

[antonfirsov]

Note: looks like there is valuable input in the discussion under #15.

[JimBobSquarePants]

Can someone explain why the issue in #15 only occurs with antialiasing on? I would assume (naively) that calculating intersections is something that occurs before we draw the ant aliased line?

[tocsoft]

Synopsis of issue:
The precision issue causes individual intersections for individual subpixel divisions to be missed this causing the rasterizer to render the inside as the outside etc.

Details
The way our rasterizer works is for every pixel we divide it into multiple subpixels... for anti-aliased drawing this is driven from GraphicsOptions.AntialiasSubpixelDepth for with a minimum of 4, for non-anti-aliased drawing with have 4 subpixels.

now for each subpixel row we perform an intersection check with the path and determine for each subpixel on that line whether they are inside or outside the path.

We aggregate all the subpixels per pixel so that there is a level per subpixel of how much of it is inside vs outside the shape.

When anti-aliasing is turned on that value is converted in to a blend percentage amount.
With anti-aliasing turned off a threshold is applied and if 50% of the pixel is inside then it is filled with a 100% blend amount.

now because we don't have a threshold amount in anti-alias then even a single subpixel triggering the intersection miss would cause it to render an output but with non-anti-aliased then it would have to be over 50% of the scanlines per pixel row to cause a visible output.

So inconclusion non-anti-aliasing is technically effected if just has much higher probability of hiding it.

[JimBobSquarePants]

Man... I don't get rasterizing at all...

Currently reading this. http://nothings.org/gamedev/rasterize/

[JimBobSquarePants]

I think we should have a serious look at this implementation. It's well documented and appears to have excellent performance and quality characteristics.
http://mlab.uiah.fi/~kkallio/antialiasing/

It's interesting enough that team behind Blend2d is looking at it also. https://gitter.im/blend2d/blend2d?at=5ea0228e71a34b0149013568

It also holds out well under extreme scrutiny here
https://cairo.cairographics.narkive.com/bcO9xhdC/survey-of-polygon-rasterization-techniques

[antonfirsov]

Collecting some GeoJson inputs for testing:

https://github.com/ebrelsford/geojson-examples/blob/master/nyc_council_districts.geojson
https://github.com/SixLabors/ImageSharp/files/3499397/states.txt
https://github.com/PublicaMundi/MappingAPI/blob/master/data/geojson/countries.geojson
https://github.com/datasets/geo-countries/blob/master/data/countries.geojson
https://github.com/scdoshi/us-geojson/blob/master/geojson/region/West.geojson
https://github.com/scdoshi/us-geojson/blob/master/geojson/state/AK.geojson
https://github.com/scdoshi/us-geojson/blob/master/geojson/state/TX.geojson

[antonfirsov]

@tocsoft I believe the only real solution to achieve robustness here is to simplify polygons before rendering, removing sub-pixel details which are not visible, and only result in numerical artifacts.

There is a simple (but O(n^2)) algorithm to achieve this:
https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

An example implementation:
https://github.com/imshz/simplify-net/blob/master/src/Simplifynet.CSharpPortable/SimplifyUtility.cs

[antonfirsov]

For example, zooming into the US map artifacts and the original polygon, the island on the left contains unnecessary details.
(Note: the code in #15 (comment) is producing some vertical distortion compared to the GeoJson viewer screenshot.)

[JimBobSquarePants]

@antonfirsov Did you see the optimized implementation of the Peucker algorithm linked at the bottom of the Wiki?

http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/hershberger92speeding.pdf

[antonfirsov]

@JimBobSquarePants good point, haven't noticed, thanks!

O(n*log(n)) seems much better. Wondering if code in the appendix is robust enough.

[antonfirsov]

New issue to track in same topic: #106