Questions about drawing lines

[atruskie]

Hi all,

I draw a lot of non-antialiased lines, and I'd like to get a sense of what expected behavior is so I can file better bug reports.

The basic questions are:

Given a line (particularly a horizontal or vertical one) how do we expect a solid non-antialised pen of varying stroke widths to be drawn?

I've got a set of test cases below which illustrate what I am talking about:

1) Drawing an inset rectangle

Goals: draw a border around the inside edge of a rectangle.

Code:

            public void DrawBorderInset(Pen border, RectangleF rectangle)
            {
                // rounder border thickness
                border = new Pen(
                    border.StrokeFill,
                    MathF.Floor(border.StrokeWidth),
                    border.StrokePattern.ToArray());

                // first round rectangle to nice coordinates
                var rect = Rectangle.Round(rectangle);
                
               // construct point coordinates, offset by pen width inset into rectangle.
                var penOffset = MathF.Floor(border.StrokeWidth / 2.0f);

                float left = rect.Left + penOffset;
                float top = rect.Top + penOffset;
                float right = rect.Right - penOffset - 1;
                float bottom = rect.Bottom - penOffset - 1;

                this.context.Draw(NoAntiAlias, border, RectangleF.FromLTRB(left, top, right, bottom));
            }

This test passes for 1 and 3 px wide pens, but fails on 2px. Test code:

            var rect = new Rectangle(1, 1, 98, 98);
            this.ActualImage.Mutate(x => x.NoAA().DrawBorderInset(new Pen(Color.Red, 2f), rect));

Result (Expected, delta, actual):

Flaw: 3px red border in actual, corners are missing/rounded.

Changing PenOffset too

               var penOffset = MathF.Floor(border.StrokeWidth / 2.0f)+ (strokeWidth % 2f == 0) ? -0.5f : 0);

Which results in (Expected, delta, actual):

2) Drawing a horizontal line

Very similar issue to above.

I have a draw line helper method:

            public void DrawLine(IPen pen, int x1, int y1, int x2, int y2)
            {
                this.DrawLines(pen, new PointF(x1, y1), new PointF(x2,  y2));
            }

Test:

            this.ActualImage.Mutate(x => x.NoAA().DrawLine(TestPenTwo, 0, 50, 100, 50));

Result (Expected, delta, actual):

Adding in that sub-pixel wiggle from above:

            public void DrawLine(IPen pen, int x1, int y1, int x2, int y2)
            {
                this.DrawLines(pen, new PointF(x1, y1 + (strokeWidth % 2f == 0) ? -0.5f : 0), new PointF(x2,  y2 + (strokeWidth % 2f == 0) ? -0.5f : 0));
            }

Summary

• depending on how we expect strokes to be drawn non-antialiased, this may or may not be a bug
• if it is a bug, then it looks like the scanning code is giving equal precedence to fractions of a stroke?

[antonfirsov]

For a proper answer, I need more time to look at these examples and do a deeper analysis to get a 100% understanding on what's happening. Unfortunately, I can't do it now, and I can't give you ETA at the moment :(

In the meanwhile I can share my understanding of the coordinate handling rules I learned while optimizing the scanning code:

1. When drawing shapes, coordinate axes are aligned to pixel boundaries similarly to Skia and unlike GDI/System.Drawing, which places axes to pixel midpoints (ignore the purple lines):

        1.1 When there is no antialiasing, the same rules apply, we calculate everything as if there was antialiasing, then apply a 0.5 threshold for each pixel to decide whether it's colored or not.

2. When a path/stroke is being drawn, this is what happens:
   2.1 The path is being placed on coordinates aligned as in (1)
   2.2 An "extension" of strokeWidth/2 is being applied, and the path is being converted into a polygon
   2.3 A translation of (0.5,0.5) is being applied to the polygon generated in 2.2:

ImageSharp.Drawing/src/ImageSharp.Drawing/Processing/Processors/Drawing/DrawPathProcessor.cs

Line 48 in 3d737b5

var shape = this.Shape.Translate(0.5f, 0.5f);

        2.4 The polygon is being filled according to the rules in 1.

I don't understand why is (2.3) necessary or beneficial. To me it seems like weird exception to a general rule in 1. Skia does not do this when drawing strokes.

@tocsoft: can give an explanation for 2.3? Can you also confirm if my understanding on the 1-2.4 steps is correct?

@atruskie: does 1-2.4 explain what you experience?

[atruskie]

Unfortunately, I can't do it now, and I can't give you ETA at the moment :(

All good. It's a tricky problem. I've written weird rules/rounding effects in wrapper methods that produce the desired effect for me in the meantime

I don't understand why is (2.3) necessary or beneficial. To me it seems like weird exception to a general rule in 1. Skia does not do this when drawing strokes.

It looks like one of my previous bugs (#28) was the cause of this: https://github.com/SixLabors/ImageSharp.Drawing/pull/70/files#diff-514b058a6b8efe2cfa39a06cde2f4865c939e8741da64fa3473eac87f823ad74L46-R50

@atruskie: does 1-2.4 explain what you experience?

Yep

Honestly, I'm having trouble understanding it with a conceptual framework other than my own.

I think of it like filling bins. With one pixel you fill the bin positive to your coordinates. With two, you fill either side. With three you "split" so you fill two bins on the positive side, one negative... and so on in that alternating pattern, straddling the center coordinate.

So yeah, intuitively I think like Skia, I think.

For a line with stroke width 2, from 2,3 to 5,2 in your diagrams, my issue is that three-pixel wide line is drawn

2. When a path/stroke is being drawn, this is what happens:
   2.1 The path is being placed on coordinates aligned as in (1)

2,3 to 5,2

2.2 An "extension" of strokeWidth/2 is being applied, and the path is being converted into a polygon

2,3 to 5,2 --> left: 2, top: 2, right: 5, bottom: 3

2.3 A translation of (0.5,0.5) is being applied to the polygon generated in 2.2:

left: 2.5, top: 2.5, right: 5.5, bottom: 3.5

Which now means that rows 2, 3, and 4 are filled.

I'm am unsure if what you've explained accounts for the missing pixels in the cornering of the rectangle.

---

As an aside, I'd actually really like to file a big suite of tests that test all sorts of line-drawing operations - particularly because fixing one problem often breaks something else, as seen in (maybe) in #28 and #70.

I'm just not confident enough in what the correct behaviors are yet.

[antonfirsov]

the 0.5 pixel offset it to accommodate that when you draw a stroke of 1px along 5,5 -> 5,10 then you will end up with a polygon of 4.5,4.5 - 4.5,9.5 - 5.5,9.5 - 5.5,4.5 and that's not actually what you want, you really want 5,5 - 5,11 - 6,11 - 6,5 its to align the stroke to the pixel boundary rather than the pixel center.

@tocsoft doesn't the same reasoning work for shape filling? It looks like we should either go with GDI-style (pixel center) or Skia-style (pixel boundary) alignment. Mixing the two depending on whether we are drawing shapes or lines seems weird to me. Unless I'm misunderstanding, it might even lead to unexpected inaccuracies when someone is outlining a boundary of a shape.

[antonfirsov]

As an aside, I'd actually really like to file a big suite of tests that test all sorts of line-drawing operations - particularly because fixing one problem often breaks something else.

@atruskie that would be great! I struggled a lot understanding what are our conformance criterias when working on the optimized scanner. But first we need to discuss, clarify and agree on a formal set of rules. I'm very concerned whether the current ones are the best, but I'm far from being an expert enough to make a decision alone at this moment.

I'm am unsure if what you've explained accounts for the missing pixels in the cornering of the rectangle.

I don't know, need to look into it, maybe Scott knows better. I would expect the corner behavior to be configurable, if poossible. So if we stick with the current 1-2.4 rules, there are no bugs except this quoted point?

[antonfirsov]

Shouldn't we just do whatever HTML5 canvas does?

[JimBobSquarePants]

Yep. I think Skia works hard to conform to that behavior.