Graphics.fillPoly glitch

[nebbishhacker]

g.fillPoly sometimes produces extraneous horizontal lines when two adjacent points in the list are almost, but not quite, horizontally aligned.

Test case:

g.clear();
g.fillPoly([120, 40,
            200, 200,
            170, 200,
            120, 100,
            70, 180, // line starts at this point and extends to the right
            40, 179]);

Result:

Bug was discovered while working on an SVG to bangle draw call converter :)

[gfwilliams]

Thanks - we recently 'improved' the fillPoly algorithm so it looks like there's still something odd here.

Just for reference, here's the outline:

[gfwilliams]

Ok, so I'm looking at this and I can make the poly fill more reliable, but then it effectively cuts off the top pixel.

This is the poly fill from https://alienryderflex.com/polygon_fill/ but in JS:

g.clear();

function fillPoly(a) {
  var polyCorners = 0;
  var polyX=[],polyY=[];
  for (var i=0;i<a.length;i+=2) {
    polyX[polyCorners]=a[i];
    polyY[polyCorners]=a[i+1];
    polyCorners++;
  }
  
  var  nodes, pixelX, pixelY, i, j, swap ;

  //  Loop through the rows of the image.
  for (pixelY=0; pixelY<30; pixelY++) {
    var nodeX=[];
  
    //  Build a list of nodes.
    nodes=0; j=polyCorners-1;
    for (i=0; i<polyCorners; i++) {
      if (polyY[i]<pixelY && polyY[j]>=pixelY
      ||  polyY[j]<pixelY && polyY[i]>=pixelY) {
        nodeX[nodes++]=0|(polyX[i]+(pixelY-polyY[i])/(polyY[j]-polyY[i])
        *(polyX[j]-polyX[i])); }
      j=i; }
    //  Sort the nodes, via a simple "Bubble" sort.
    i=0;
    while (i<nodes-1) {
      if (nodeX[i]>nodeX[i+1]) {
        swap=nodeX[i]; nodeX[i]=nodeX[i+1]; nodeX[i+1]=swap; if (i) i--; }
      else {
        i++; }}
    console.log(pixelY,nodeX);

    //  Fill the pixels between node pairs.
    for (i=0; i<nodes; i+=2) {
        for (pixelX=nodeX[i]; pixelX<nodeX[i+1]; pixelX++) 
          g.fillRect(pixelX*4,pixelY*4,pixelX*4+3,pixelY*4+3); }}
}

fillPoly([ 16, 0, 31, 31, 26, 31, 16, 12, 6, 28, 0, 27 ]);

It's not quite as good as that in reality due to integer arithmetic, but because of the polyY[i]<pixelY you're never filling up to the top pixel. I don't know - maybe that's ok.

One option is to offset what we check against, so effectively for (pixelY=0.5; rather than for (pixelY=0;...

[nebbishhacker]

I wonder if it might still be worth adding that half-pixel offset to what we check against. Right now fillPoly effectively sample from the top-left corner of each pixel. Sampling from the center of each pixel would make intuitive sense to me, and it would match how I've been assuming things would be rendered while working on the font in Inkscape.

Aesthetically, it might improve the appearance of gentle slopes. As of 5d61b67 the poly [1, 1, 30, 2, 30, 4, 1, 3] renders as:

................................
.#..............................
.#############################..
.#############################..
................................

With a half-pixel offset, it would render as:

................................
.##############.................
.#############################..
...............###############..
................................

which looks more "correct" to my eyes.

[gfwilliams]

That sounds like a good plan to me,

So just to be sure you mean basically subtracting 8 here:

Espruino/libs/graphics/graphics.c

Line 438 in 5d61b67

v[i].x = (short)vx;

[nebbishhacker]

Yes, that is precisely what I mean, for both vx and vy.

[gfwilliams]

Thanks - just done. Rendering looks a whole lot more sensible now!