Codecov Report

Merging #8987 (7fd0b56) into master (f000ac9) will decrease coverage by 0.00%.
The diff coverage is 96.96%.

@@            Coverage Diff             @@
##           master    #8987      +/-   ##
==========================================
- Coverage   98.37%   98.36%   -0.01%     
==========================================
  Files         156      156              
  Lines       20281    20366      +85     
==========================================
+ Hits        19951    20033      +82     
- Misses        330      333       +3     

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

I'll be interested to hear the views of the maintainers on this. I'd like to see further enhancements, notably circles/ellipses in filled and outline form but increased firmware size may be an issue.

I'll be interested to hear the views of the maintainers on this. I'd like to see further enhancements, notably circles/ellipses in filled and outline form but increased firmware size may be an issue.

The framebuf extmod is totally optional though right? If you don't have a display or if your display needs are not performance sensitive, just set MICROPY_PY_FRAMEBUF to 0 and don't compile it in

Or are you thinking there should be even finer-grained controls about what functionality to compile in? Maybe we can add MICROPY_PY_FRAMEBUF_EXTRA for including such advanced drawing routines?

Edit: FWIW the polygon method I'm proposing here re-uses the existing line drawing code, so size increase should be minimal there -- only fill_polygon adds any real new code.

I don't have a view on build options. I'm interested in the maintainers' view because I favour additional enhancements and might submit a PR for ellipse if there is an interest.

Or are you thinking there should be even finer-grained controls about what functionality to compile in?

That thought had occurred to me. framebuf is useful on small devices with, say, monochrome ssd1306 displays. Flash is actually the constraint here since normally framebuf will be frozen. Guess it just depends on how much additional space the extra features will consume?

I'll be interested to hear the views of the maintainers on this.

My view is: we have a framebuf module and it should either be made useful or deleted. I think we should make it useful.

Last year I started writing some stuff for framebuffer graphics, inspired by elements of Peters nanogui . As I felt this was unfinished I did not share it. I first developed it in pure python, with generators. Mathematically it was state of the art, I would say, using Besenham algorithms from https://zingl.github.io/Bresenham.pdf.
My code did circles, ellipses and rounded rectangles all outlined, filled or with prescribed width. Triangles were not finished as I was struggling with getting a good solution for prescribed width. The python code is here:
FramebufGraphics.zip
The ideas are quite clearly understandable in this code, I would say. Two of the same generators (which do the Besenham algorithm), are used for computing the beginning and the end of horizontal lines, which are then drawn with framebuffers hline() function.

Later I did a conversion of this code to viper. I observed considerable speedups, described in the discussion with peter:
https://github.com/peterhinch/micropython-nano-gui/discussions/26
I present the viper code here. The generator stuff is resolved into while loops as there are no generators in viper. Arguments are packed by pairs into integers due to vipers limitations to 4 arguments.
vfb_graphics.zip
The viperized circle function, as an example, then is this:

@micropython.viper
def _vfbg_cir(xy0: int, rw:int, color:int, hline):
    x0 = xy0 >> 16   # unpack 16 bit arguments  x0, y0
    y0 = xy0 & 0xffff
    r = rw >> 16    # unpack 16 bit arguments  r, w : radius, width of outline
    w = rw & 0xffff    
    if w == 0:  # fully filled circle, specify width=1 for outline only
        w = r+1    
    xo, yo = 0 - r, 0
    eo = 2 - 2*r
    old_yo = False
    xi, yi = 0 - r+w, 0  # ri = r-w
    ei = 2 - 2*(r-w)    # ri = r-w
    old_yi = False
    while True:
        # ------------------- outer generator
        while old_yo and xo <= 0:
            s = eo
            if (yo >= s):
                yo += 1
                eo += yo*2+1
                old_yo = False
            if (xo < s or yo < eo):
                xo += 1
                eo += xo*2+1
        old_yo = True
        # -------------------- inner generator
        while old_yi and xi <= 0:
            s = ei
            if (yi >= s):
                yi += 1
                ei += yi*2+1
                old_yi = False
            if (xi < s or yi < ei):
                xi += 1
                ei += xi*2+1
        if old_yi:
            yi += 1
        old_yi = True
        # -------------------- check abort and draw
        if xo > 0:
            break
        if xi > 0:
            hline(x0+xo, y0-yo, 1-2*xo, color)
            hline(x0+xo, y0+yo, 1-2*xo, color)
        else:
            hline(x0+xo, y0-yo, xi-xo, color)
            hline(x0-xi+1, y0-yo, xi-xo, color)
            hline(x0+xo, y0+yo, xi-xo, color)
            hline(x0-xi+1, y0+yo, xi-xo, color)

As you see it is now 99 % C-like: Conversion to C should be straightforward.
An obstacle for me ATM are real usage of Github and getting acquanted with the style of implementation of C routines into micropython.
Perhaps @mbooth101 or someone else is interested in taking this part of work? I would do it later myself, now that I have some nice examples of code here, but that would take more time and meanwhile someone could endeavor in developing the same unnecessarily.

Given that a circle is a special case of an ellipse, is there a need for a circle routine?

Given that a circle is a special case of an ellipse, is there a need for a circle routine?

If we have a ellipse/arc routine that can draw circles in an obvious way, then that would be a good general purpose function to have. Please submit a PR if you have something @peterhinch

The viper ellipse routine in the above mentioned vfb_graphics.zip is only slightly different from the circle routine presented and thus should be preferred for transformation to C code for reducing code size, I agree. If you @peterhinch have something already finished or a different approach I would love to test and compare.

I have nothing ready - for my GUI's I do circle drawing in Python. I'll tackle an ellipse method in C and submit a PR in due course.

This is my ellipse function converted to C, included is a wrapper so that it compiles to text graphics: Easy to try out.
What annoys me are the many variables in it - this stems from the double generator approach.

#include <stdio.h>

#define X_MAX 50
#define Y_MAX 120

int FrameBuf[X_MAX][Y_MAX];

void hline(int x0, int y0, int l, int color)
{
	if (y0 >= 0 && y0 < Y_MAX)
		for (int x = x0; x < x0 + l; x++)
			if (x >= 0 && x < X_MAX)
				FrameBuf[x][y0] = 1;
}


void ellipse(int x0, int y0, int a, int b, int w, int c)
{
    int ai, bi, xo, yo, dxo, dyo, eo, e2, old_yo, xi, yi, dxi, dyi, ei, old_yi;
    
    if (w == 0) {      // fully filled circle, specify width=1 for outline only
        if (a < b)
            w = a+1;
        else
            w = b+1;
    }
    ai = a-w;
    bi = b-w;
    
    xo = 0-a;                        // ------------------- init generators
    yo = 0;
    dxo = (1+2*xo)*b*b;
    dyo = xo*xo;
    eo = dxo + dyo;
    old_yo = 0;     // False
    xi = 0-a+w;
    yi = 0;
    dxi =(1+2*xi)*bi*bi;
    dyi = xi*xi;
    ei = dxi + dyi;
    old_yi = 0;     // False

    while (1) {        
        while (old_yo && xo <= 0) {  // ------------------- outer generator
            e2 = 2*eo;
            if (e2 >= dxo) {
                xo += 1;
                dxo += 2*b*b;
                eo += dxo;
            }
            if (e2 <= dyo) {
                yo += 1;
                dyo += 2*a*a;
                eo += dyo;
                old_yo = 0;      // False
            }
        }
        if (old_yo && yo < b)
            yo += 1;
        old_yo = 1;              // True
        
        while (old_yi && xi <= 0) {  // ------------------- inner generator
            e2 = 2*ei;
            if (e2 >= dxi) {
                xi += 1;
                dxi += 2*bi*bi;
                ei += dxi;
            }
            if (e2 <= dyi) {
                yi += 1;
                dyi += 2*ai*ai;
                ei += dyi;
                old_yi = 0;      // False
            }
        }
        if (old_yi)
            yi += 1;
        old_yi = 1;              // True
        
        if (xo > 0)  // -------------------- check abort and draw
            break;
        if (xi > 0) {
            hline(x0+xo, y0-yo, 1-2*xo, c);
            hline(x0+xo, y0+yo, 1-2*xo, c);
        } else {
            hline(x0+xo, y0-yo, xi-xo, c);
            hline(x0-xi+1, y0-yo, xi-xo, c);
            hline(x0+xo, y0+yo, xi-xo, c);
            hline(x0-xi+1, y0+yo, xi-xo, c);
        }
    }
}

int main(int argc, char *argv[])
{
	for (int x=0; x < X_MAX; x++)
		for (int y=0; y < Y_MAX; y++)
			FrameBuf[x][y] = 0;
	
//  ellipse(int x0, int y0, int a, int b, int w, int c)
	ellipse(X_MAX/2, Y_MAX/2,  23,    53,    6,     0);
	ellipse(X_MAX/3, Y_MAX/3,  9,    7,    4,     0);
	ellipse(X_MAX/3, 2*Y_MAX/3,  9,    7,    4,     0);
	
	printf("----------------   ASCII-Graphics   ---------------\n\n");
	for (int x=0; x < X_MAX; x++) {
		for (int y=0; y < Y_MAX; y++)
			if (FrameBuf[x][y])
				printf("*");
			else
				printf(".");
		printf("\n");
	}
	
	return 0;
}
				

Should be interesting to see something more concise.

I think we should discuss circle/ellipse drawing algorithms elsewhere - perhaps in an RFC.

To return to this PR I think it should be evaluated (and hopefully merged) on its merits, regardless of future framebuf enhancements. The PR can readily be used to draw a filled circle or ellipse with a little Python code; this would be hard with the existing set of primitives.

I have tested the PR on an RP2 with ili9341 display and it works well. I have an animation which slowly rotates a filled re-entrant shape. In the past I've seen rasterisation algorithms croak under these circumstances. This works fine.

My only question for the team is over the API.

The use of a list of lists is both Pythonic and intuitive but it precludes the use of pre-allocated storage. An alternative might be to use an array (perhaps of half-words) holding [x0, y0, x1, y1...xn, yn]. Not as user friendly but in some applications more RAM efficient.

I think we should discuss circle/ellipse drawing algorithms elsewhere

+1. A separate PR with an initial implementation would suffice.

The use of a list of lists is both Pythonic and intuitive but it precludes the use of pre-allocated storage. An alternative might be to use an array (perhaps of half-words) holding [x0, y0, x1, y1...xn, yn]. Not as user friendly but in some applications more RAM efficient.

You can preallocate lists (of lists). You could also use tuples (of tuples). If the entries are small ints (which they most likely will be) then it's about the same memory use as an array of ints.

But I do agree that an array would be more memory efficient if it uses half words (or bytes for small shapes). It's not that unfriendly, eg: array('h', [-10, 0, 100, 20, ...]).

Regarding the name polygon and fill_polygon: maybe it could be poly and fill_poly to match the shorthand rect that's already used?

And maybe putting the x/y first in the arg list also makes it more consistent with the other drawing methods? poly(x, y, coords, col), maybe?

I have done some further testing trying to fill ridiculous objects such as [[40, 0], [0, 0], [0, 40], [40, 40], [-40, 40//2], [40, 0]] and worse. The code coped well with no crashes or failures. It also seems to be pixel perfect.

You can preallocate lists (of lists).

In that case I favour the list of lists on grounds of user friendliness.

I was envisaging applications that allocated storage which was then used to render successive objects having the same number of vertices. For example the same shape transformed by scaling or rotation.

@peterhinch Thanks for testing the code, I also tried to capture some edge cases in the included tests, such as self-intersecting polygons and some degenerate cases.

Regarding the name polygon and fill_polygon: maybe it could be poly and fill_poly to match the shorthand rect that's already used?

And maybe putting the x/y first in the arg list also makes it more consistent with the other drawing methods? poly(x, y, coords, col), maybe?

@dpgeorge I made both of these suggested changes in the latest revision of the patchset -- thanks for the feebback :-)

If the entries are small ints (which they most likely will be) then it's about the same memory use as an array of ints.

Actually this is not true: the current list-of-lists approach requires quite a lot more memory than an array. Eg [[0, 0], [0, 10], [10, 10], [10, 0]] needs 1 list of length 4 and 4 lists of length 2, which is 10 GC blocks, which is 160 bytes. The equivalent array storing 16-bit numbers needs only 2 GC blocks, or 32 bytes.

I think it would be good to support an array with the coordinates. The question is whether it's easy to support a list-of-lists and an array without much increase in code size? Then the user can choose the best approach for their case (list or array).

I think it would be good to support an array with the coordinates. The question is whether it's easy to support a list-of-lists and an array without much increase in code size? Then the user can choose the best approach for their case (list or array).

I will investigate supporting both ways when I get some time later in the day. Thanks again for the review

You could have a helper function like (schematically) get_poly_point(obj, size_t idx, mp_int_t *x, mp_int_t *y) which allowed obj to be a tuple/list or a pointer to raw memory (eg from an array.array), and then it extracted the next point based on the type.

Hi @dpgeorge, it turned out not to be too difficult to support both ways so I did that, along with extra test cases to cover it and extra detail in the documentation.

Please consider re-reviewing the latest revision of the patchset.

Merged in 04a655c via #9045.

Thank you @mbooth101 for working on this!

Superceded by #9045