g.fillPoly bug?

Hi all,
I am fiddling around with the emulator for BangleJs and found something weird.

g.fillPoly does not fill a concave polygon correctly with the "opening on top", code below.

Is this a bug or did I overlook something obvious?

var poly_1_draw = [50,30,50,20,70,40,70,60,50,80,50,70,60,60,60,40];
var poly_1_fill = [150,30,150,20,170,40,170,60,150,80,150,70,160,60,160,40];
var poly_2_draw = [30,170,50,170,70,190,90,190,100,170,120,170,100,200,60,200];
var poly_2_fill = [140,170,160,170,180,190,200,190,210,170,230,170,210,200,170,200];

g.clear();
g.drawPoly(poly_1_draw,true);
g.fillPoly(poly_1_fill,true);
g.drawPoly(poly_2_draw,true);
g.fillPoly(poly_2_fill,true);

1 Attachment

Hi! I believe you just hit this: https://github.com/espruino/Espruino/issues/1710

Basically it's expected at the moment because the poly fill algorithm works on a scanline basis and so only handles regular polygons.

It's something I plan to improve at some point soon though - it'll likely decrease the rendering speed slightly but it definitely seems like a worthwhile addition.

Oh ok. Thanks.
Yeah, I would expect it to become increasingly interesting for developing new watch faces. :)
I'll stick to individual merged polygons in the meantime then.

Did hit the same issue when developing the graphics for the ui elemets in the ui framework: a drawing of the shape looks perfect... filling it messes it up... reason for it, i guess is, that the 'rounding' - wether to turn on a pixel or not - fails on the + side / edges of the shape relative to the (x) axis. That's one reason. The other is that on low resolution per shape - such as on a Pixl.js - every single pixel matters for how the shape is perceived. I tried to draw the shape and then fill it with a filled shape with dimensions of one less pixle... It helped to a certain extent... but was not cheap... so I dropped the idea and went more for having different sets of vertices to get better results - as much as possible. But as hinted: happens only on low resolution.

@Gordon, wanted to raise that a bit back, but knowing what was going on at that time, I shelved it for - may be - looking into it myself... (with slim chance to that happen... ever(?)... :

Update with picture taken from PixlJs:

Attached you see the differences between left an write for all shapes that are not rectangular.

• The (plain) buttons and checkboxes are (overlaid) filled polygons - either beveled (8 vertices) or 'pseude'-round-cornered (12 vertices)
  
• The 'circles' / radio button are filled polygons of up to 16 vertices.
  
  

The 'bad and ugly' is always on the right side...

1 Attachment

Interesting - could be a rounding issue. I know as @allObjects mentioned circles aren't great either.

If anyone wants to have a go at improving fillPoly/fillEllipse then the code's here: https://github.com/espruino/Espruino/blob/master/libs/graphics/graphics.c#L441

You can easily build Espruino 'native' on Linux/Mac/Windows(via Linux subsystem for Windows) and can test using code like this: https://github.com/espruino/Espruino/blob/master/tests/test_graphics_ellipse.js

Or even just a bit of C code all on its own would be appreciated. I can merge it into Espruino as long as it works well (although if you're copying it rather than making your own it'll need to be compatible with MPLv2's license).

@Gordon, the drawing does it perfect - all 4 sides equal... same shape filled messes it up... the drawing uses another rounding - pixel or not to pixel than the fill algorithm to cut of the filling line. The circles above are made with segments... vertices.

I've looked into this: http://alienryderflex.com/polygon_fill/
It looks promising and I got it to work in C#. But I'm not particular good in graphics algorithms nor C.
Also I'm not sure about the licensing thing.
Any thoughts on that?

The 'bad and ugly' is always on the right side...

Can you please share the code to generate that screen.

This is the last test I like to run before creating the pr with the updated code for Ellipses.

Sun 2019.12.08

Good Morning @Raik and Kudos on your effort to get running in C#.

'I'm not particular good in graphics algorithms nor C'

As your effort is running in C#, it seems to me the major hurdle in C is over. Puzzling?

'I'm not sure about the licensing thing'

On which end is your concern? Using a re-written version of the 2007 copyright Darel Rex Finley 'Efficient Polygon Fill Algorithm' code, or your (presumably) re-written version in Javascript that would be part of the Espruino doamin?

@MaBe ( and @Gordon )

Ellipse/Circle implementation will not affect my ui code. Because of the low resolution and relative small size of the shapes - and the performance(?) I use only vertices - and that is 'plenty good' enough (if fill rendering would work as 'expected'/not overshoot):

• 8 corners for check boxes and very small buttons
  
• 12 corners fort buttons
  
• 8..16 'corners' for small to larger radio buttons / circles
  
  

This is the code segment (part of uiExt.js module):

- exports = // ui (generic) ext(ension/utils: vertices(circle,...) find elt/idx in arr,...)
{ mn: "uiExt" // module 'clazz' name - globally unique (used to remove code from cache)
, cvn: [[92,38,38,92,-38,92,-92,38,-92,-38,-38,-92,38,-92,92,-38]
       ,[98,20,83,56,56,83,20,98,-20,98,-56,83,-83,56,-98,20
       ,-98,-20,-83,-56,-56,-83,-20,-98,20,-98,56,-83,83,-56,98,-20]]
, cvs: function(x,y,w) { // circle from vertices by bounding box w/ left, top and width
 var r=w/2,c=[x+r,y+r],z=r/100; return this.cvn[(w<12)?0:1].map((v,i) => c[i&1]+v*z); }
, vs2: function(x,y,x2,y2,p) { // vertices for for chk like shapes ('beveled') corners
 // 4 'beveled corners' = 8 corners defined by 0 and p insetting combinations for x, y
 return [x,y+p, x+p,y, x2-p,y, x2,y+p, x2,y2-p, x2-p,y2, x+p,y2, x,y2-p]; }
, vs3: function(x,y,x2,y2,p,q) { // return vertices for btn like shapes ('round' corners)
 // 12 'round corners' (4x3) defined by 0, p and q insetting combinations for x and y 
 return [ x,y+p,   x+q,y+q,   x+p,y, x2-p,y, x2-q,y+q, x2,y+p,
         x2,y2-p, x2-q,y2-q, x2-p,y2, x+p,y2, x+q,y2-q, x,y2-p]; }

The example is ui_...zip file I sent you a bit ago (.../_sbx/projects/uiExampleAllPixl.js) expecting Espruino Web IDE sandbox folder pointing to .../_sbx where ever you unpack(ed) it). - You can find the zip also here - and with a slightly different (previous version) on http:// http://www.espruino.com/modules/uiExt.js - and http://www.espruino.com/ui | http://www.espruino.com/uiExampleAllPixl

As said earlier: Drawing the polygons with the vertices does just fine... filling messes them up.

(Working on the maze rendering a +-1 in the coordinates has major impact when working with low resolution like Pixle.js.)

`Espruino --- Draw/Fill test w/ Small/low resolution Polygons w/ Vertices`;

`Notices the rendering difference between draw and fill from`;
`   left and right and *EVEN DEPENDING ON POSITION on display`;
var vs2 = function(x,y,x2,y2,p) { // vertices for beveled, chk box like shape
 // 4 'beveled corners' = 8 corners by 0|p inset combinations for x/y corners
 return [x,y+p, x+p,y, x2-p,y, x2,y+p, x2,y2-p, x2-p,y2, x+p,y2, x,y2-p]; };

var c0, c1; // colors
if     ("undefined" != typeof Pixl  ) { c0=0        ;  c1=1;         }
else                                  { c0="#000000";  c1="#FFFFFF"; }

function onInit() {
  `prep display`
  g.clear(); setTimeout(()=>{
  g.setColor(c0);
  g.fillRect(0,0,127,63); c=// canvas (color 0)
  `beveled squares and rectangles drawn and filled with polygon (color 0)`
  g.setColor(c1);
  g.fillRect(8,8,40,53); // frame filled (color 1)
  g.setColor(c0);
  g.drawPoly(vs2(10,10,18,18,1),1); // 9x 9 draw beveled [1] for x and y
  g.drawPoly(vs2(21,10,38,18,1),1); // 9x19 draw beveled [1] for x and y
  g.fillPoly(vs2(10,21,18,29,1),1); // 9x 9 fill beveled [1] for x and y
  g.fillPoly(vs2(21,21,38,29,1),1); // 9x19 fill beveled [1] for x and y
  g.drawPoly(vs2(10,32,18,40,2),1); // 9x 9 draw beveled [2] for x and y
  g.drawPoly(vs2(21,32,38,40,2),1); // 9x19 draw beveled [2] for x and y
  g.fillPoly(vs2(10,43,18,51,2),1); // 9x 9 fill beveled [2] for x and y
  g.fillPoly(vs2(21,43,38,51,2),1); // 9x19 fill beveled [2] for x and y
  `scalable beveled squares w/ borders done with two stacked, filled polygons`
  g.setColor(c1); 
  g.fillRect(45,8,57,53); // frame filled (color 1)
  g.setColor(c0);
  g.fillPoly(vs2(47,21,55,29,1),1); // bot bev'd [1] square separate (color 0)
  g.fillPoly(vs2(47,43,55,51,1),2); // bot bev'd [2] square separate (color 0)
  g.setColor(c1);
  g.drawRect(62,8,74,53); // frame hallow (0 from canvas)
  g.setColor(c1);
  g.fillPoly(vs2(65,22,71,28,1),1); // top bev'd [1] square separate (color 1)
  g.fillPoly(vs2(65,44,71,50,1),2); // top bev'd [2] square separate (color 1)
  g.setColor(c1); 
  g.fillRect(79,8,91,53); // frame filled (color 1)
  g.setColor(c0);
  g.fillPoly(vs2(81,21,89,29,1),1); // bot bev'd [1] square combined (color 0)
  g.fillPoly(vs2(81,43,89,51,1),2); // bot bev'd [2] square combined (color 0)
  g.setColor(c1);
  g.fillPoly(vs2(82,22,88,28,1),1); // top bev'd [1] square combined (color 1)
  g.fillPoly(vs2(82,44,88,50,1),2); // top bev'd [2] square combined (color 1)
  if (c1===1) g.flip(); // for pixle (does bangle need it too?)
  },999);
}
setTimeout(onInit,999); // for dev'n, remove for upload before save()

Most stunning is that even position on display matters... I know that for some displays the dot pattern is not squares but rectangles: 30 vs 36 units - such as Pixl.js' one - and that may play into it... I though think that on so low resolutions / small screens, this should not be taken into account, because this messes heavily with rendering. I know circles are then slightly ellipses... but guess, these displays are not used for CAD / making pictures of it and then noticing that the circle is not exactly a circle... With so low resolution / small shapes, one pixel off is worse than the fraction the pixel to pixel difference in x-axis direction vs y-axis direction:

On Pixle.js, where a button checkbox is as small as 9 pixel in x and y direction and corner happening in space of 2x2 pixels, one pixel off in the corner by rounding (because of considering the 30 vs 36 pixels x vs y size) is 50%... where as the 30 vs 36 is 20% (max 25%, depending from which side you look). The human eye/brain is able to see a circle and a 45 degree bevel, even though it may not exactly by that... but 50% makes the difference between 'seeing' a square with straight vs beveled corners and a circle or a potato (Nothing wrong with potatoes, ...I mean for a food).

NB: I stack / overlay to scale shapes, filled - solid - and 'empty' - borders. I intend same render code for very low resolutions - like 128 vs 240 pixels in width... about very close the same absolute physical size of Pixle.js and 2.8" 240x320 TFT... But I had already to deviate and make the size pick different sets of vertices... and vertices are not exactly cheap in space... (even though there may be some enhancements I could do).

Attached is screen shot from Pixl.js (2) and Bangle.js emulation (1). Results are though exactly the same... (why???? - not same display driver).

3 Attachments

Just so you can test - here's @allObjects' code in the emulator (using the 120x120 gfx mode to double up pixels): https://www.espruino.com/ide/emulator.html?gist=d1b9f19415fe7d58dff5fe8bedf7fbd4&upload

@Raik thanks - that code looks great. It does say public domain, and honestly it's pretty simple and I'm sure I've seen similar pseudocode in a bunch of places. I'll reimplement it for Espruino with the same basic logic (ideally the final rendering stage would use Espruino's fillRect anyway) just to avoid any potential issues.

... I also wonder how hard it'd be to add antialiasing to that. Probably not that painful at all :)

I'll be putting updates to fillPoly on https://github.com/espruino/Espruino/issues/1710

@allObjects I may have discovered why fillPoly isn't doing quite what you expect. I should have remembered this:

https://www.cs.uic.edu/~jbell/CourseNotes/ComputerGraphics/PolygonFilling.html

...avoid drawing pixels twice...

pixels within the boundary of a polygon belong to the polygon

pixels on the left and bottom edges belong to a polygon, but not the pixels on the top and right edges

Could that be the problem? I'm definitely thinking that Espruino should ignore that, but it seems such an expected part of the polygon fill algorithm it may annoy some users?

Attached is screen shot from Bangle.js emulation. Pic from Pixle.js- result is though exactly the same... (why???? - not same display driver).

Actually if you mean http://espruino.com/ide/emulator.html then it is the same display driver. That's the nice thing about it - it really is Espruino running inside the browser :)

@Gorden,

that must be it... but it is obviously not that simple - and costs cycles / memory for code, and so far the differences were minimal to notice with the resolution and most sizes of shapes I used so far (For vector fonts it is though visible, because the font character's nooks an crannies are small shapes... assuming the same filling algorithm(s) is(are) used.)

In my emulator I use canvas and have high resolution and rendering is differently / does alias(?) differently. (The 'bad' thing abut my emulator... or would you call that a simulator?). The difference I felt for drawing horizontal / vertical lines / squares / rectangles /along the x- an y-axes: not the pixel is the coordinate, it is the 'spot' between... because when I render a single pixle line on a coord that is an integer, it shows grey over two pixels... I added 0.5 and then it's different. Also drawing exactly the same line with the background color (black) over a previously white one (showing grey), it does not 'remove' / 'expunge' it: it just gets darker grey!

For vector fonts I use a same sized font from the underlaying infrastructure (browser / os).

For bitmapped fonts I though have same logic as Espruino but without scaling.

I built the emulator/simulator(?) less for the exact look, but more for supporting development of logic, faster round-trips (no upload, slowing by BLE upload). extended debug and i(pseudo) independence from device. For a while I even had code in the project and module files that required by the emulation but were inert / no-ops when running on device. Lucky I got rid of that.

Just tested fillPoly_irregular with BOARD=LINUX

1 Attachment

...weird: 2nd row and 2nd thru last block... algorithms usually fail only once and it is because +/-1]

And most weird is that 2-dots beveled square - in the bottom row - makes it in most left rendering, but fails for all others.

This subject shows that 'Numerische Methoden' are not a simple subject - and I had to take the test twice (first time I ignored the need to be pocket calculator savvy / trained... Know about the concepts and how to apply them is fine, but real life requires to be very fluent in usage...)

Interesting - thanks. Looks like that's not ready to merge then ;)

The original algorithm ignores the topmost (lowest Y) pixel of each edge, which means that when edges join you only get one point. That works great apart from right at the top of the shape when the top scanline gets missed off completely. Thinking about it, I could probably just special-case the topmost scanline and those issues should be solved

Ok, fixed and merged :)

Very nice! :) But it's not yet in the emulator is it?

Not yet, no :)

Ahem, did that break the emulator? Seems to have some kind of y-offset now?

Edit: Nevermind, seems to work again.

g.clear();
g.drawLine(0,0,240,240);
g.drawLine(0,240,240,0);

1 Attachment

Works fine on my side ;)

1 Attachment

Seems to have some kind of y-offset now?

Looks like you'd put it into double-buffered mode - which ends up being 160px high widescreen