You re-wrote my PR so that I can no longer pass the polygon coordinates a list of lists/list of tuples 👎

I'm trying to be very responsive feedback on my original PR, why not discuss changes there?

You re-wrote my PR so that I can no longer pass the polygon coordinates a list of lists/list of tuples 👎

I'm trying to be very responsive feedback on my original PR, why not discuss changes there?

I'm just trying to do what I can do as a maintainer to get your code merged as quickly and easily as possible without making you duplicate the effort that I just spent my Friday evening on. Not trying to diminish your work or anything and I'm sorry that it seems that way! I'm glad to see these features added to framebuf.

These two features represent an extremely significant code size increase (+1132 bytes total) and merging this is not an easy decision. I spent a good chunk of time discussing this with Damien today and then more time trying to optimise the two PRs. Sure I can turn all that work into a bunch of comments on your PR and then go backwards-and-forwards on it for the next days/weeks but I'd still need to make a PR for the first two commits, and now we'd have three PRs to wrangle.

I definitely agree that list-of-lists or lists-of-tuples is syntactically convenient, but I don't feel that it's worth either the code size or the runtime RAM cost.

Ellipse goes like a bat out of hell now. Using the same script and test conditions, times are

• Line draw 306μs
• Filled 666μs (!)

Just a quick note on the efficiency of the array.array approach, further to what @dpgeorge said in #8987.
Because this uses mp_get_buffer, it also works with anything else that supports the buffer protocol. So for small polygons (coordinates less than 256), you can use bytes, and in particular a literal bytes string, which means you get to use a const string and have no copies at all. If your code is frozen, it means your polygon data will be drawn from ROM.

So for example, the "M" polygon from the test cases could be written as:

poly = const(b'\x00\x14\x03\x14\x03\n\x06\x11\t\n\t\x14\x0c\x14\x0c\x03\t\x03\x06\n\x03\x03\x00\x03')

Obviously this isn't great for readability, but if your program has a number of polygons then these can be generated programatically.

Ellipse goes like a bat out of hell now.

Thanks for testing @peterhinch !

You re-wrote my PR so that I can no longer pass the polygon coordinates a list of lists/list of tuples -1
I'm trying to be very responsive feedback on my original PR, why not discuss changes there?

I'm just trying to do what I can do as a maintainer to get your code merged as quickly and easily as possible without making you duplicate the effort that I just spent my Friday evening on. Not trying to diminish your work or anything and I'm sorry that it seems that way! I'm glad to see these features added to framebuf.

These two features represent an extremely significant code size increase (+1132 bytes total) and merging this is not an easy decision. I spent a good chunk of time discussing this with Damien today and then more time trying to optimise the two PRs. Sure I can turn all that work into a bunch of comments on your PR and then go backwards-and-forwards on it for the next days/weeks but I'd still need to make a PR for the first two commits, and now we'd have three PRs to wrangle.

I definitely agree that list-of-lists or lists-of-tuples is syntactically convenient, but I don't feel that it's worth either the code size or the runtime RAM cost.

Thanks -- this is all important context that I was missing!

As an outside contributor I am asked to sign off on submissions, so it seemed against the spirit of that policy to merge something different to what I signed off on without at least some explanation of what was going on. :-)

As an outside contributor I am asked to sign off on submissions, so it seemed against the spirit of that policy to merge something different to what I signed off on without at least some explanation of what was going on. :-)

Yes this is a very good point. I just left the commits with the original author (of course) but didn't think about the sign off. Our main intention here is that the sign off is conveying that the contribution meets the licence requirements and the code doesn't have any encumbrances.

This is actually something we do all the time (make changes to commits during merge while preserving the author/signoff), although usually the changes are minor or squashes/rebases. @dpgeorge we should probably clarify this particular scenario.

@jimmo I now have prototype rounded rectangle (filled and outline) C code. Naturally this is dependent on .ellipse: I'll submit a PR once this one is merged.

The idea of shapes in ROM is excellent. On a typical display all shapes are likely to be small enough to fit in a bytes instance. Writers of traditional arcade games should have a field day.

[EDIT] Deleted the rest. My enthusiasm had got ahead of my brain :)

Hi @jimmo this morning I tested this series of patches on my ESP32 device and have a couple of comments.

Because I have to take the extra steps of flattening my point lists and converting it to an array.array() I lose about 10ms per frame when rendering a scene of 104 triangles -- this no big deal, I can probably claw back some performance by refactoring my application to avoid this extra work.

Much more concerning to me are the visual defects that have been introduced:

Compare with the behaviour of my original PR:

I will try to come up with a small reproducing test case.

@mbooth101 Your videos aren't visible here.

@mbooth101 Your videos aren't visible here.

Works fine for me. It's just an MP4 file in a HTML5 video tag, so maybe your browser doesn't know how to decode MP4?

In any case you can download the videos for offline viewing by right-clicking -> save link as on these links:

• New broken behaviour: clicky clicky
• Old correct behaviour: clicky clicky

@jimmo Here's a small reproducer for the issue visible in the above video:

import sys
import framebuf
from array import array

def print_buffer(buffer, width, height):
    for row in range(height):
        for col in range(width):
            val = buffer[(row * width) + col]
            sys.stdout.write(" {:02x}".format(val) if val else " ··")
        sys.stdout.write("\n")

t1 = array('h', [40, 0, 20, 68, 62, 40])
t2 = array('h', [40, 0, 0, 16, 20, 68])

w = 70
h = 70
buf = bytearray(w * h)
fbuf = framebuf.FrameBuffer(buf, w, h, framebuf.GS8)

fbuf.poly(0,0,t1,0xff, True)
fbuf.poly(0,0,t2,0xff, True)

print_buffer(buf, w, h)

Something is wacky with the intersection node detection at the corners:

@mbooth101 thanks for the repro!

The problem is this line:

if (py1 != py2 && MIN(py1, py2) <= row && MAX(py1, py2) >= row) {

which I changed from your PR, where it was

if (py1 != py2 && ((py1 > row && py2 <= row) || (py1 <= row && py2 > row))) {

The reason I changed it was that in the existing test cases I noticed the fill wasn't quite reaching the exact bounds of the outline. Notably the last row of the M's and the bottom edge of the hourglass and the star. This is why I added the tests that draws the fill on top of the outline to make this obvious. All the ff in the following snippets are incorrect:

 99 99 99 99 ·· 99 99 99 ·· 99 99 99 99 ·· ·· 99 99 99 99 ·· ·· ff ·· ·· 99 99 99 99 ·· ··
 99 99 99 99 ·· ·· 99 ·· ·· 99 99 99 99 ·· ·· 99 99 99 99 ·· ·· ·· ·· ·· 99 99 99 99 ·· ··
 99 99 99 99 ·· ·· ff ·· ·· 99 99 99 99 ·· ·· 99 99 99 99 ·· ·· ·· ·· ·· 99 99 99 99 ·· ··
 99 99 99 99 ·· ·· ·· ·· ·· 99 99 99 99 ·· ·· ff ff ff ff ·· ·· ·· ·· ·· ff ff ff ff ·· ··
 99 99 99 99 ·· ·· ·· ·· ·· 99 99 99 99 ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ··
 ff ff ff ff ·· ·· ·· ·· ·· ff ff ff ff ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ··
 ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ··
 ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ··

 ·· 99 99 99 99 99 99 99 99 ·· ·· ·· ·· ·· ·· ·· ·· ·· 99 99 99 ·· ·· ·· ·· ·· ·· ·· ·· ··
 ·· ·· 99 99 99 99 99 99 ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· 99 99 99 ·· ·· ·· ·· ·· ·· ·· ·· ··
 ·· ·· 99 99 99 99 99 99 ·· ·· ·· ·· 99 99 99 99 99 99 99 ff 99 99 99 99 99 99 99 ·· ·· ··
 ·· ·· ·· 99 99 99 99 ·· ·· ·· ·· ·· ·· 99 99 99 99 99 99 ·· 99 99 99 99 99 99 ·· ·· ·· ··
 ·· ·· ·· 99 99 99 99 ·· ·· ·· ·· ·· ·· ·· 99 99 99 99 ·· ·· ·· 99 99 99 99 ·· ·· ·· ·· ··

·· 99 99 99 99 99 99 99 99 ·· ·· ·· ·· ·· ·· 99 99 99 ·· ·· ·· 99 99 99 ·· ·· ·· ·· ·· ··
 ·· 99 99 99 99 99 99 99 99 ·· ·· ·· ·· ·· ·· 99 99 ·· ·· ·· ·· ·· 99 99 ·· ·· ·· ·· ·· ··
 99 99 99 99 99 99 99 99 99 99 ·· ·· ·· ·· ·· ff ·· ·· ·· ·· ·· ·· ·· ff ·· ·· ·· ·· ·· ··
 ff ff ff ff ff ff ff ff ff ff ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ··
 ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ·· ··

You can also see this with your repro screenshot above, which includes a pixel at (20, 68). If I revert that line back to the original version, the glitch goes away, but now that pixel isn't drawn.

The new version glitches because the end of one edge and the start of the next edge now both "intersect" with the row and so it duplicates the node. Whereas the original will never include the "bottom" pixel of any edge, which is usually fine because same pixel will be the top of the next edge, except when that next edge is horizontal or going upwards.

In the meantime I've updated this PR to avoid the glitch, but the test cases show the incorrect fill. I suspect we can add some logic to fix this by detecting if the next edge is horizontal or upwards, so I've added a comment to that effect for now.

The reason I changed it was that in the existing test cases I noticed the fill wasn't quite reaching the exact bounds of the outline. Notably the last row of the M's and the bottom edge of the hourglass and the star. This is why I added the tests that draws the fill on top of the outline to make this obvious. All the ff in the following snippets are incorrect:

Aha, that's a good find @jimmo

In the meantime I've updated this PR to avoid the glitch, but the test cases show the incorrect fill. I suspect we can add some logic to fix this by detecting if the next edge is horizontal or upwards, so I've added a comment to that effect for now.

Thanks for fixing the glitch and adding the extra test case -- in the meantime I will have a think about the bottom edge problem

in the meantime I will have a think about the bottom edge problem

@mbooth101 I don't know if you came across this page while writing this code, but it describes the exact same algorithm and the implementation is identical. Note that on the linked page about polygon-in-point, it says

"If the test point is on the border of the polygon, this algorithm will deliver unpredictable results; i.e. the result may be “inside” or “outside” depending on arbitrary factors such as how the polygon is oriented with respect to the coordinate system. (That is not generally a problem, since the edge of the polygon is infinitely thin anyway, and points that fall right on the edge can go either way without hurting the look of the polygon)"

This is exactly our problem.

I spent some time thinking about ways to solve this but then had an embarrassingly simple (and almost zero code size cost) idea -- just always unconditionally draw the outline after completing the fill. Unfortunately this will obviously take a bit of a performance hit, would be keen to see how this affects your demo.

I have updated the PR to do that.

Because I have to take the extra steps of flattening my point lists and converting it to an array.array() I lose about 10ms per frame when rendering a scene of 104 triangles -- this no big deal, I can probably claw back some performance by refactoring my application to avoid this extra work.

Yes, hopefully it is possible to just use array.array through your entire renderer, and I imagine this will considerably improve performance especially if you re-use arrays which will allow you to eliminate almost all heap allocations.

I don't know if this is of interest. The following script runs a "fuzz test" on polygon fill. I ran it against the original PR and against this one as it was before the bug was fixed. The buggy version typically fails almost immediately. The original PR ran for >260K shapes before I cancelled it. I run on an RP2.

import framebuf
from array import array
from random import randint

def print_buffer(fbuf, w, h):
    for x in range(h):
        for y in range(w):
            p = "x" if fbuf.pixel(x, y) else "."
            print(p, end="")
        print()

w = 32
h = 32
c = 16  # centre
buf = bytearray(w * h)
fbuf = framebuf.FrameBuffer(buf, w, h, framebuf.GS8)

nvertices = 10
npoints = nvertices * 2
vmax = 12  # Max X or Y excursion
vmin = -12
np = 0  # Pass and fail count
nf = 0
arr = array('H', (0 for _ in range(npoints)))
while True:
    fbuf.fill(0)
    for k in range(npoints):
        arr[k] = randint(0, vmax-vmin)
    #fbuf.poly(c + vmin, c + vmin, arr, 0xff, True)  # New API
    fbuf.fill_poly(c + vmin, c + vmin, arr, 0xff)  # Old API
    try:
        for x in range(w):
            for y in range(h):
                if fbuf.pixel(x, y):
                    if not (c + vmin <= x <= c + vmax) or not (c + vmin <= y <= c + vmax):
                        print(x, y)
                        raise OSError
    except OSError:
        print("Fail")
        nf += 1
    else:
        np += 1
    print('Count', np, nf)
    if nf:
        fbuf.rect(c + vmin, c + vmin, vmax-vmin + 1, vmax-vmin + 1, 0xff)
        print_buffer(fbuf, w, h)
        break

@mbooth101 Based on the idea that drawing the outline can solve this, I have implemented a more optimised fix for this. The idea is to detect the "lost" pixels during the node calculations, but rather than getting the node list to account for these, just explicitly draw the pixels there (either via setpixel or line).

This adds +72 bytes on PYBV11, but makes filled poly() about 10-15% faster.

Baseline is 32 ms/frame (empty scene no polygons)

• Test 1 with 40 triangles goes from 53 ms/frame to 50 ms/frame (21 ms --> 18 ms for poly)
• Test 2 with 20 stars goes from 49 ms/frame to 47 ms/frame (17 --> 15 ms for poly)

I've put it in a separate commit... we can squash during merge if desired.

It's still not exactly perfect -- there are some pixels along diagonal edges that it misses, but visually it's pretty good.

FWIW, this PR is now at +1204 bytes.

I don't know if this is of interest. The following script runs a "fuzz test" on polygon fill.

Thanks @peterhinch ! I ran this on the current version and no problems.

Codecov Report

Merging #9045 (4c077f2) into master (6f4d424) will increase coverage by 0.00%.
The diff coverage is 99.48%.

@@           Coverage Diff            @@
##           master    #9045    +/-   ##
========================================
  Coverage   98.37%   98.37%            
========================================
  Files         156      156            
  Lines       20310    20424   +114     
========================================
+ Hits        19979    20092   +113     
- Misses        331      332     +1     

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

@mbooth101 Based on the idea that drawing the outline can solve this, I have implemented a more optimised fix for this. The idea is to detect the "lost" pixels during the node calculations, but rather than getting the node list to account for these, just explicitly draw the pixels there (either via setpixel or line).

This adds +72 bytes on PYBV11, but makes filled poly() about 10-15% faster.

Baseline is 32 ms/frame (empty scene no polygons)

* Test 1 with 40 triangles goes from 53 ms/frame to 50 ms/frame (21 ms --> 18 ms for poly)

* Test 2 with 20 stars goes from 49 ms/frame to 47 ms/frame (17 --> 15 ms for poly)

I've put it in a separate commit... we can squash during merge if desired.

Oh great, thanks for putting in the extra work!

In a 104 triangle scene I lose about 3 or 4 ms per frame in my 3D demo with this fix (compared to no fix), which I can live with.

It's still not exactly perfect -- there are some pixels along diagonal edges that it misses, but visually it's pretty good.

I can't see any missing pixels, but triangles that share vertices will overlap by one pixel anyway and hide that -- and where they overlap I don't think I can see any new Z-fighting, so I'd be totally happy to see these 6 commits merged as is 👍

@jimmo Re rounded rect please could you advise how you want to proceed. I have working code, but there is a dependency on ellipse which isn't yet merged.

I'd planned to wait until this PR is merged before submitting a PR, but I guess merging may take a while.

It occurred to me that to save time you might want to include the change in this PR. If so, please let me know what I should do bearing in mind my limited git-fu.

One point re the code. There is a case for checking whether r > min(width, height) // 2 and either throwing a ValueError or constraining r to that value. I took the view that it's not worth spending bytes on a check when the outcome of failure is just an unexpected image.

Thanks @peterhinch

I think it's valuable to be able to support round rect, although we need to consider the trade off against doing it in Python.

Here's a Python version for comparison. It's 242 bytes of bytecode, and it takes 11 ms to outline 60 rectangles (10ms with @native), and 16 ms to fill (14 with @native).

def round_rect(fb, x, y, w, h, r, c, f):
    xpw = x + w
    xpr = x + r
    yph = y + h
    ypr = y + r
    r2 = r * 2
    wmr2 = w - r2
    hmr2 = h - r2
    xpwmr = xpw - r
    yphmr = yph - r
    fb.ellipse(xpwmr, ypr, r, r, c, f, 1)
    fb.ellipse(xpr, ypr, r, r, c, f, 2)
    fb.ellipse(xpr, yphmr, r, r, c, f, 4)
    fb.ellipse(xpwmr, yphmr, r, r, c, f, 8)
    if f:
        fb.rect(xpr, y, wmr2, r + 1, c, True) # top
        fb.rect(x, ypr, w + 1, hmr2, c, True) # middle
        fb.rect(xpr, yphmr, wmr2, r + 1, c, True) # bottom
    else:
        fb.hline(xpr, y, wmr2, c) # top
        fb.vline(x, ypr, hmr2, c) # middle
        fb.vline(xpw, ypr, hmr2, c) # middle
        fb.hline(xpr, yph, wmr2, c) # bottom

I cherry-picked your commit, it's +440 bytes and 7 ms to outline and 11 ms to fill.

I had an idea for a compromise which is a slightly awkward API but smaller and marginally faster. That is to add an optional "expand x/y" parameter to ellipse, which shifts out the four quadrants by this amount and then fills/outlines the gaps as necessary. Implementation is here -- c055a42

So for example, fb.round_rect(10, 10, 80, 30, 10, 0xff, False) becomes fb.ellipse(50, 25, 10, 10, 0xff, False, 0xf, 30, 5).

This is +248 bytes and 4ms to outline and 11 ms to fill.

What do you think @peterhinch ? The API is awkward, and it's a bit weird when you pass a mask that isn't 0xf, although it does let you draw just the top or bottom half of a rounded rect and could probably fix it without much cost to do the quadrants properly.

Ingenious, but odd, not least specifying a rectangle by its centre. As an example of the implications, in micro-gui a user can specify an on-screen Pushbutton object. This can be round, rectangular or a rounded rectangle. All rectangles are positioned relative to their top left corner. With this API normal and rounded rectangles would need to be treated differently with the coordinates of the latter being tweaked before being passed to the C code.

The API is a bit of a value judgement - perhaps worth canvassing the view of @dpgeorge?

One factor in the tradeoff of C vs Python is that a C implementation saves RAM. With the other changes it provides a more complete feature set for FrameBuffer. However I'm surprised that the speed difference is so small - these are all times for 60 shapes?

Ingenious, but odd, not least specifying a rectangle by its centre. As an example of the implications, in micro-gui a user can specify an on-screen Pushbutton object. This can be round, rectangular or a rounded rectangle. All rectangles are positioned relative to their top left corner. With this API normal and rounded rectangles would need to be treated differently with the coordinates of the latter being tweaked before being passed to the C code.

Yes I agree... FWIW I implemented a different version that makes fb.rect() now take an optional radius arg (after the newly added optional fill arg), and then have rect and ellipse share a common "draw expanded ellipse" function. It comes out to +360 bytes.

Another reason that the ellipse-based approach and also this rect->ellipse approach is awkward is because it ultimately involves drawing at a center coordinate, it doesn't work when the width is even...

One factor in the tradeoff of C vs Python is that a C implementation saves RAM.

That's right. And I quoted "242 bytes of bytecode" above, which is just the difference in size of a .mpy file containing this function, but the reality is that slightly more actual RAM will be used to load that code.

However I'm surprised that the speed difference is so small - these are all times for 60 shapes?

Yes, unless I've missed something. The code is

N = 20
R = 60
F = True

t = time.ticks_ms()

for i in range(N):
    for j in range(R):
        #pass
        roundrect(fb, 10, 10, 80, 30, 10, 0xff, F)
        #fb.ellipse(50, 25, 10, 10, 0xff, F, 0xf, 30, 5)
        #fb.round_rect(10, 10, 80, 30, 10, 0xff, F)
    lcd.show_framebuf(buf)

print("outline", time.ticks_diff(time.ticks_ms(), t) // N, "ms per frame")

The baseline (with pass) is 31ms per frame, then the times quoted in the earlier comment are relative to that.

OK, one final alternative to add to the mix...!

This is basically identical to @peterhinch's round rect implementation, except it's implemented by adding an additional radius argument to rect() instead of adding a new round_rect method. Implementation here: 040b389

It comes in at +336 bytes.

@dpgeorge over to you :p

it's implemented by adding an additional radius argument to rect()

FWIW I like that. 👍

Just wanted to say a quick thanks to all of the contributors here; it's great to see framebuf get some attention!

Rebased and added tests for drawing ellipse/poly out of bounds.

Thanks everyone here for the work on these changes and additions. I think what's done here now is a good tradeoff between code size and features.

At this stage I don't think it's worth adding a radius argument to rect(). It's a lot of code size increase for not much gain. Rounded rects can be done in Python using ellipse and rect, albeit a bit slower. The addition of poly() and ellipse() is already a big step forward in features, at a modest code size increase of around +1250 bytes.

There are still other improvements to be made to framebuf (eg 24-bit RGB support), and we need to save bytes for them.

Merged in 470a44b through c616721

@dpgeorge Many thanks for merging this :-)

I want to use the poly method to draw a triangle, what should I do?

Any suggestions are welcome!

I want to use the poly method to draw a triangle, what should I do?

Any suggestions are welcome!

The poly method has been merged, you can find them on a nightly build. Create a framebuf and then use poly - something like:

import framebuf
import array

# Allocate a bytearray sufficiently large to store the pixel data
# This example is mono so 1 bit = 1 pixel, resolution of 24x24
fb = framebuf.FrameBuffer(bytearray(24*24//8), 24, 24, framebuf.MONO_VLSB)

# For efficiency, poly takes an array; define a triangular polygon
tri = array.array('h', [0, 0, 10, 0, 0, 10])
fb.poly(0, 0, tri)

# fb is ready to blit to a monochrome display

Untested, but hopefully that'll get you started!

@mattytrentini

Thanks for your code! ! ! I already understand how to use poly method.