Fill and Stroke polygon

[andersmelander]

To the best of my knowledge it isn't currently possible to fill and stroke a polygon in one go.

Currently in order to draw a filled polygon with a stroke one has to:

1. Render the polygon outline with the desired stroke: PolylineFS(...)
2. Negative offset the polygon with half the stroke width to produce the inner polygon: Grow(...)
3. Fill the inner polygon: PolygonFS(...)

While this might appear to work fine there are several problems:

• There's a seam between the stroke and the fill: The pixel coverage doesn't add up to 100%.
  For example the following polygon (stroke: 1px clBlack32, fill: clWhite32):
  Raw image:
  Rendered on top of checkerboard (slightly visible inside border):
  
  Rendered on top of red layer (notice how the red bleeds through inside border):
  
• Another problem is that there's no guarantee that the shape produced by Grow() or TClipperOffset actually matches the inner polygon of the shape produced by PolylineFS since they're produced by different implementation that are probably based on different algorithms.

I know that Mattias at one point mentioned the possibility of having VPR handle both filling and stroking, but as far as I can tell this feature never materialized.

I propose that functionality be added that combines fill and stroke to produce 100% pixel coverage within the polygon.

Note that I'm aware that the problem can be avoided when using purely opaque colors by simply not offsetting the inner polygon, but for semitransparent colors it is required.

[AngusJohnson]

I propose that functionality be added that combines fill and stroke to produce 100% pixel coverage within the polygon.

I'm not able to reproduce the problem you've described.
This is what I'm seeing using the following code ...

  pp := MakePath([25,2, 35,12, 20,20]);
  PolygonFS(bmp, pp, clWhite32, pfAlternate);
  PolylineFS(bmp, pp, clBlack32, true, 1.0);

[andersmelander]

I don't know if I'm super sensitive but I can see it in your example too. The pixels marked with blue are all on the inside and should not have been blended with the background. If you examine the RGB you can see their colors' got red in them:

Anyway if you think about the problem you really don't need to reproduce it. It's inherent in the way we do filled, stroked polygons.
If there was no problem then the order of PolygonFS/PolylineFS wouldn't matter. As it is now you have to do PolygonFS and then PolylineFS and that doesn't work for semitransparent colors.

Try with a fat, semitransparent stroke and the more important problem should be evident: The fill is visible through the stroke. [edit] If you offset the fill, like I mentioned in the problem description, to avoid this you'll see the seam problem more clearly.

[AngusJohnson]

I don't know if I'm super sensitive but I can see it in your example too.

You must have amazing eyes to spot the slightest bleed-through occurring there :).

If there was no problem then the order of PolygonFS/PolylineFS wouldn't matter.

I'm not following your logic. In theory, brush polygons could fill just up to the inner boundaries of outlining strokes, but you'd have to dispense with anti-aliasing. However that won't be an acceptable option until screen pixels get a lot smaller. In the meantime, attempting to brush fill just up to the inner boundaries of outline strokes would look silly since anti-aliasing would guarantee background bleed-through. The only viable solution (with anti-aliasing ) is continue with the current approach - ie rendering stroke and brush polygons with sufficient overlap so background bleed-through is avoided interiorly (and brush filling exterior to strokes is also avoided). And while some overlap between stroke and brush fill is necessary, the order of polygon vs stroke rendering surely does matter as it will affect the perceived stroke thickness.

Anyhow, I'm still not seeing that there's a problem (at least with my inferior eyes :)).

Edited: See solution below.

[andersmelander]

You must have amazing eyes

Oh, thank you :-* but maybe my monitor is just better calibrated...

In theory, brush polygons could fill just up to the inner boundaries of outlining strokes, but you'd have to dispense with anti-aliasing.

No. If you do scan line conversion of both the fill and the stroke in one go, then there will be no seam. This I believe was also what Matthias envisioned.
Take this filled and stroked circle for example:

Line width: 10px, feather 5px, both colors 75% alpha (192).
It's anti aliased, there's no seam and the fill and stroke colors blend perfectly.
edit: I just realized that it might not be obvious that the circle is filled with 75% white since the background on this page is also white. Anyhow, view the image in an editor and it should be obvious.
Here's the same bitmap on an opaque yellow background:

It was created with the circle tool in my resource editor and the circle algorithm is implemented with scan line conversion.

Naturally it isn't possible to do scan line conversion with brushed strokes (since the brush can have any shape) but for regular line strokes I can't see why it shouldn't be possible. As far as I know we already do scan line conversion of polylines and polygons.

[AngusJohnson]

Take this filled and stroked circle for example

Anyhow, view the image in an editor and it should be obvious.

This is your semi-transparent image with a red background added ...

where ISTM that overlap and anti-aliasing was still used between brush and stroke. However I think I now understand what you're suggesting. I think you're hoping for direct blending at brush/stroke boundaries rather than blending occurring indirectly via anti-aliasing. I can see that that would be a 'more perfect' solution, but no doubt a lot more work too.

[andersmelander]

ISTM

The International Society of Travel Medicine?

overlap and anti-aliasing was still used between brush and stroke

Yes. The stroke is anti aliased on both sides.
I can see now that there's a bug in the implementation as the alpha should stay at 75% in the boundary where the stroke and fill overlap. Probably using the wrong blend mode. Let me check... Yep. Mixed the colors using Merge - should have used Blend.
Here's a new one:

I think you're hoping for direct blending at brush/stroke boundaries rather than blending occurring indirectly via anti-aliasing.

Exactly.

a lot more work too.

I'm not sure. I'm not well into the inner workings of VPR but I would imagine most of the information required is already available there.

[AngusJohnson]

Here's a new one:

Yes, much better :).

I'm not sure. I'm not well into the inner workings of VPR

I think the principles will be the same irrespective of the implementation. The rasterizer just produces an alpha mask, so the brush and the stroke would each have an alpha mask. Then it's a matter of blending with these 2 masks where the blend function would give the stroke mask preference over the brush mask.

[AngusJohnson]

I've worked out a blend function that works very well ...

function ModifyAlpha(color: TColor32; alpha2: Byte): TColor32; inline;
var
  c: TARGB absolute result;
begin
  result := color;
  c.A := Gr32_Blend.DivTable[c.A, alpha2];
end;

function BlendSpecial(dstColor, color1, color2: TColor32;
  mask1, mask2: byte): TColor32;
var
  c1: TARGB absolute color1;
  c2: TARGB absolute color2;
  res: TARGB absolute Result;
  table, tableInv: System.SysUtils.PByteArray;
begin
  if mask2 = 0 then
  begin
    if mask1 = 0 then Result := dstColor
    else Result := MergeReg(ModifyAlpha(color1, mask1), dstColor)
  end else if mask2 = 255 then
    Result := MergeReg(color2, dstColor)
  else if mask1 = 0 then
    Result := MergeReg(ModifyAlpha(color2, mask2), dstColor)
  else
  begin
    table    := @Gr32_Blend.DivTable[mask2];
    tableInv := @Gr32_Blend.DivTable[not mask2];
    res.A := table[c2.A] + tableInv[c1.A];
    res.R := table[c2.R] + tableInv[c1.R];
    res.G := table[c2.G] + tableInv[c1.G];
    res.B := table[c2.B] + tableInv[c1.B];
    Result := MergeReg(result, dstColor);
  end;
end;

And here's an example of blending overlapping semitransparent colors using the above function.
Note that Color2/Mask2 (in the code above) take precedence over Color1/Mask1.

And this is the same polygon/polyline using the existing overlapping draw method ...

Edit: Here's a very simple example application ...
PolygonEx.zip

[andersmelander]

I'm sorry but I can't see how that helps. You're just using back buffers to construct the filled polygon and I can already do that with just a single buffer. The end user can even do it with layers and the right blend mode.

This has to work for arbitrary bitmaps, and be reasonable performant, so fixing it in a back buffer is IMO not the way to go. I'll have a look at the rasterizer when I get a spare moment but it'll probably be a while before I have time for any serious effort.

[AngusJohnson]

You're just using back buffers to construct the filled polygon and I can already do that with just a single buffer.

Well I guess it could be done with a single 'buffer' as long as you keep the two alpha channels (one for brush and one for stroke) separate in that buffer. But to me that's simply a data storage preference unless I'm missing your point (again). The rasterizing (ie alpha mask construction) of brush and stroke must be done separately (or at least stored separately) so the renderer will know how to blend the respective brush and stroke colors onto the image.

This has to work for arbitrary bitmaps, and be reasonable performant,

I'm not sure what you mean by 'arbitrary bitmaps' but I agree that performance would be an issue (ie using the approach I suggested above).

I'll have a look at the rasterizer

Good luck with that :). I've had a fairly decent look and haven't yet figured out what Mattias does there (and I've written my own rasterizer / renderer for my own graphics library so I have a fairly decent idea of the principles).

[andersmelander]

Here's one way to do it with a single buffer:

1. Normalize the alpha of the two colors used so the range is 0-255 (i.e. the highest alpha is 255).
   This is optional and is just done to lessen rounding errors.
2. Draw first part onto buffer.
3. Draw second part onto buffer using a "special" blend.
4. The special blend is either "over" or "under" operator depending on the order of the parts.
   This is pretty much the same as your precedence blend.
5. Optionally, if we normalized alpha in step 1, restore the alpha range range as part of the blend operation in step 4.
6. Draw buffer onto destination.

Good luck with that :). I've had a fairly decent look and haven't yet figured out what Mattias does

That's a problem. One of the reasons we introduced VPR was that we couldn't fix bugs in the old rasterizer because nobody understood it.
I've just had a peek and, while the principles in it are completely undocumented, it's only about 400 lines of fairly clean code. I'll see if I can find some additional documentation in the archives.

I can see that the way we do the stroke is to take the outline polyline, offset it by half the stroke width and add it to a polypolygon. Take the outline again, offset it by negative half the stroke width, reverse the direction and add it to the polypolygon.
Now in theory all we need to do is to add an extra step to also fill the inner polygon independently of the outer. The problem here is that the anti-aliasing of the stroke and fill rendering might not add up to 100% due to rounding errors. This can be solved by rounding down on the stroke and up on the fill, when calculating the alpha, but that really is a hack.

[dtamade]

Support the proposal

[turborium]

I agree that this is a really sad inherent in most existing libraries

[andersmelander]

The following is the result of an attempt at solving this at the TCanvas32/TCustomBrush level.

I made a custom brush that does fill and stroke in one go. It works under the assumption that the polypolygon being drawn consists of pairs of polygons.
The first polygon is the outer bound and the second the inner bound. So the stroke is made up of both polygons and the fill is the inner polygon. Drawing the polypolygon then simply means that I first draw the stroke and then the fill and that should be it. Since we are using the same polygon the coordinates of the stroke's inner border will be identical to the coordinates of the fill border so the anti-aliasing of the stroke's merge with the anti-aliasing of the fill and produce the result we want. In theory...

Unfortunately reality gets in the way:

1. The inner polygon is not meant to be used as an outline.
   It's meant to be used as an inner polygon so the places where it self-intersects will be hidden by the outer polygon.
   

2. The anti-aliasing is not perfect.
   In order for this to work the anti-aliasing of the border pixels would have to sum up to 100% coverage. So if the stroke color if opaque and the fill color is opaque then the merged color should also be opaque. It isn't so the coverage calculation is apparently imperfect. The cause is most likely a rounding error somewhere in VPR but even if we made the error smaller there still would be no guarantee that the coverage would sum up to 100%. It's simply not possible.