I'm here to talk to you about graphics programming in Python on an embedded microcontroller,
which is hilarious because I'm none of these things, I'm not a graphics programmer, I'm
not a Python programmer and I'm not an embedded programmer, so we'll see how this goes.
It's for that reason I just, you know, I can't emphasise enough this part of the talk description,
this is not an instructional talk, this is just what I did.
So there's some background, EMF camp is this weekend camping festival for hackers and makers
and it's in a similar vein to the chaos communication camp and the Dutch hacker festival, you know,
there's robots and lasers and geodesic domes and things, it's great fun if you get the
opportunity to go, I highly recommend it and it's a bit of a tradition of these style
of events to give the attendees electronic event badges and the aim of these is to give
attendees opportunity to play with some hardware that they might not have come across before.
These are the two most recent badges from EMF camp, the one on the left here.
If I told you they had, they put a SIM card on it and a GSM modem and then they set up
an onsite cell phone network, you'll understand why it's made to look like a Nokia Engage,
but it's got all of the usual like peripherals and sensors and things on there as well like
accelerometers and humidity and temperature and things and because it runs micropycin
it allows people to easily get started with experimenting with that kind of hardware.
The one on the right there is the newest one, these photographs aren't to scale by the
way, let me just hold them up for comparison, the newest one is much smaller.
The reasons for that you might guess is because of the silicon shortage that's been caused
by fire, flood and plague as you might expect, but it's still a lovely device.
The one on the left here you can see, you might recognise this as a version of the settlers
of Ketan, I spent a lot of time trying to isolate small parts of the screen to redraw
because the update speed on that screen was so slow, it was almost, it's almost unusable
for anything in real time.
So when I got my hands on the new one this year I obviously wanted to see what this one
could do.
And so the first thing I wanted to do was to just try and glitter full screen of pixels
to the device using the display driver directly and let's talk about 70 milliseconds which
is already orders of magnitude faster than the old badge.
If I draw to an off-screen buffer instead that's way faster, but you know if you're
doing that you then you have to get into the business of implementing your own drawing
functions for primitives and I didn't really want to do that.
That is ominous foreshadowing by the way.
But I did discover that MicroPython has this frame buff module which provides you with
an off-screen frame buffer and also some drawing functions which is great.
So 41 milliseconds, I thought that was fair compromise, that's a good start.
Now I've got a baseline for how fast I can draw to the screen.
So obviously what this is about is drawing 3D things to the screen of this device and
so this is just here to, in case you don't know this is basically, I guess this is 3D
rasterization 101, this is like the minimum we have to do in order to get 3D points onto
the screen.
You know we start with our vertex coordinates and then that's multiplied by the model matrix
to get into world space and then you multiply that by the view matrix to get the view space
and then by the projection matrix you get the clip space and then the clip space allows
you to see which vertices will be eclipped by the edges of the screen or not.
So then once we know we've got the list of vertices we want to render then we can do
the perspective division to bring that into normalize device coordinate space or NDC space.
The perspective division is just the part that makes the further away points closer
together so it gives you that illusion of 3D.
And then we've got to convert the normalize device coordinates which are like between
minus one and one to screen space which is like our pixel coordinates.
And so when I was doing this, these, to render these eight points on the screen from a cube
it was pretty, it wasn't too bad 53 seconds and then if you like join those up to create
your cube wireframe it's not that much, not that much slower there's 12 triangles there
obviously.
The next step is to then start filling in these triangles you want to draw solid shapes after
all, annoyingly there's no method or no function for doing that in the frame buff module for
MicroPython.
There is in the display driver but as I mentioned like using the display driver directly is
much slower because we're making many more calls to hardware and you know we're setting
pins high and low and stuff for every time we want to draw something and we just want
to do that once when we blip the whole thing to the screen.
And yeah so frame buff doesn't provide a like polygon or polygon fill method and so
I do have to get into the business of writing these sort of functions myself after all.
So yeah the display driver itself does have these methods so obviously that's the first
place I looked for implementation clues, they have a polygon and a fill polygon method
only obviously there are problems with it and it's a little bit rubbish here's the figure
on the left there is just using the outline polygon method and then the second one here
is where I've tried to draw in a filled polygon over the top of the wireframe polygon and
you can see it just doesn't quite match up.
And so reading the code there is it seems to be implementing like quite a well known
or well documented fill polygon method and there's a link to the website where this algorithm
is described and that also supplies a reference implementation so I was able to like copy the
reference implementation to see if that if the display drivers implementation was different
and it isn't it's exactly the same it looks like the display drivers inherited the same
problems that we're in the reference implementation and you'll notice that it's not only incorrect
on this side but like the left edge here is completely different to this edge here so
it's like over drawing on this side and not drawing enough on that side.
A lot of the problems with it were sort of like rounding errors and like floating point
to integer truncation and that sort of thing which I've managed to mostly fix except for
this really annoying pixel down here that I just couldn't get and when I submitted because
I wanted to submit like this enhancement to the frame buff module upstream to the micro
platform project and so we spent a few days scratching our heads over this to try and figure
out what we could do we were initially we proposed just drawing the outline again on top of that
on top of the filled polygon just to like sweep it under the rug but eventually we
managed to figure out a much better way of doing it we just like try to detect when these
stray pixels were we're going to happen and then fill them in explicitly instead of letting
the algorithm do it oh yeah I you know these it was quite it's pretty obvious that the
algorithm I think was developed by a physicist or a mathematician because in the article
that describes the algorithm it says and I'm quoting here the detecting points on the
polygon edge will deliver unpredictable results but that is quote not generally a problem
because quotes the edge of the polygon is infinitely thin now my polygons have an edge
of one pixel so this is obviously why we had to like it fix the problems of it anyway now
we can draw arbitrary polygons to the screen and let's see what that looks like this is
the cube here again which is like basically you know the hello world of 3d graphics programming
and it seems to work pretty well 66 milliseconds there but you can see on the on the left hand
screenshot there that's not the inside it looks like you're looking at the inside of
the cube but it's just because we are drawing the back face of the back of the cube on top
of the front face of the front of the cube so as part of this 3d rasterization process
that you've now got to do like back face calling which is more maths added on to that pipeline
you know you've got to take the you've got to calculate the normal vector of the face
which is the direction the face is facing and then compute the dot product of that with
the direction you're looking so that you can know if the face if the triangle is facing
you or not and then just don't bother drawing the ones that aren't facing you but yeah that's
much it's just more maths so it adds more time and oh yeah get the occasional like really
long frame and that coincides with a garbage collection I guess we'll talk a bit more about
that in a bit yeah so like there's some really low hanging fruit things we can do to improve
the performance initially which is basically amounts to being smarter about the algorithms
we use we pre-calculate the normals instead of calculating them every frame which for
like static model like this makes total sense and yeah avoid doing the perspective division
if we can help it because it's like part of the I'd implemented it as part of the matrix
multiplication process and usually it's a and usually it's a no op unless you're multiplying
it by the perspective matrix and only then is it doing something so we can just avoid
doing those those divisions at all on you know on every vertex in every face in every
frame that's quite a lot of time saved but it does mean I can add more things to it and
make it do extra work like you know add as rudimentary lighting model and make the cube
nice looking by adding shading and whatnot and the what I'm trying to do basically is
to keep the rendering time below 100 milliseconds as well because that seems like a good target
to have if I can do that then I get like a reasonable performance of 10 frames per second
and so this is although this is this works well that's within that target it's close
to that target so I want to try something a bit more complex so I download a model of
the industry standard teapot and try and render that this is about 240 faces 240 triangles
and this obviously completely destroyed my 100 millisecond time limit so I've got to
think of I had to think of more ways to make this faster and the obvious way is to rewrite
all the hottest math functions in C as a micro Python native module the two ones that are
called the most often are like the matrix vector matrix multiplying method and the dot
product method and yeah you can see that more than cuts the time in half and with the success
of that it's pretty clear I should write rewrite all of the math in C because you know if I've
got the bonnet up I might as well and but that you know that brings the time right down
to a glorious glorious glorious six frames per second but yeah like as a general strategy
if you find yourself calling a method you know 12 1200 times a frame it's probably a good
target to be to be pushed down into the native layer so yeah a note on writing a native code
for micro Python there's really two ways of doing it there's the what is called the external
C modules which is basically C code that you write there's a module exposed to the Python
runtime those are compiled directly into the firmware which is a bit suboptimal because
I yeah it would be nice if I didn't require other people who have these devices to reflash
the firmware every time I changed this program so the other way of doing it is to write what
they call a native module which allows your application to supply native code as an MPY
file and then that can be dynamically loaded by your application at runtime which is much
nicer the way of doing it so obviously that's what I wanted to do but I did come across
problems when I tried to build the native code because I'd used a floating point division
in there for the perspective division step of the pipeline I got this problem which is
a linker error from the expressive tool chain for the ESP32 I'd love to know why this happens
and if anyone from expressive is here I'd love to know if it's fixed in a newer version
as well but it seems like it can't link this software implementation of floating point
division so obviously what I did was I downloaded the source for their tool chain and found
the assembly implementation of this method to add into my project which also didn't
work the micro Python build system wasn't prepared to accept that but that was an easy
fix and that was actually the first change I got accepted into micro Python they were
very good they're very good at or in my experience they're very good at accepting patches and
then once I got that building I got it to just cause my application to crash I'm not
sure why this happens but there seems to be like a reference to the native stuff that
gets collected erroneously by the garbage collection and I spent a lot of time like
trying to reduce my object allocations you know in the frames but all that did was just
like push out the crash to further in the future so you know I had to settle for compiling
my maths functions directly into the firmware there's some other things I did to try and
make it faster the big one is trying to reduce object insatiations it's super costly in
Python and wherever you can pre-allocate like lists and arrays and things and then just
reuse them I initially wanted to have like a lot of my classes to be totally immutable
as a good programmer I am but they just totally wasn't feasible so I just you know you just
have to mutate when you do calculations on your vertices just mutate one of the operands
and send it back that way you can also the other thing I found that saved some time was
reducing crossing reducing the amount of times that we cross from Python into native code
and back again I found I was doing like lots of the same operation to vertices and matrices
so if I could just send them all as one batch in a single function call into the native
side then that made it perform a lot quicker I think there's a lot of function and stack
manipulation overhead there that you save and also pass arrays and not lists into the
native functions as well especially for this kind of stuff where we know that the data
that we're passing our floats or whatever you know ahead of time what type is in your
array which means you can make some assumptions that my Python can't make and when and when
you manipulate this the data objects in a native side you can like skip a bunch of like
type safe stuff you can just write directly to the to the data structure which is useful
and also I this wrong surprise me as well that I well I don't know if it's surprising
maybe it's obvious to people who are veteran Python Easter's but I didn't expect to a native
the libc qsort function to be so much faster than the sort function in Python but I was
if you look at the if you look at this this picture here you can see that some parts of
the teapot are drawn on top of that should be occluded drawn on top of the body of the
teapot so what I had to do was Z sort the faces so that we draw the faces from from
back to front and that's what I was doing I was what I was using the list sort method
for here but just like implementing this sorting this face sorting as a native function as
well was like as it says it's 100 times faster and the other thing that was made a measurable
difference as well was locally caching object references in your functions as well so like
instead of if you're using an object value more than once instead of doing self food
self food self food just have yeah just created a local reference a local variable in their
function and use that instead so there's some like dereferencing overheads there that is
quite significant that we're saving and so after applying all of this sort of stuff this
is the final result or the results so far I'm pretty happy with it getting the teapot
model down to under 100 milliseconds per frame was really pleasing and yeah I'm pretty happy
with the performance so what can this be used for honestly this was a this this was just
a fun way to spend a few weekends after the festival had happened but you know it seems
to be performing enough the way you could do some kind of like small 3d game like a
lunar lander or something like that or you know make yourself a Jurassic Park style 3d
user interface for your home automation but really the chief lesson for me I think was
that the the best way to get involved with a project like micro python was to just start
using it and eventually you come across some kind of limitation that probably your best
place to overcome because you know you're the one who's trying to solve the problem
you've got the vested interest in it you have you know all of the information is currently
paged into your brain so yeah and then the the micro python people were extremely helpful
in helping me whip up whip my year contributions into shape so yeah thanks to them for helping
me get involved in micro python and thanks to you for listening I can try and answer
questions but I'm not super expert on anything I've been talking about hi and thanks for
your talk I had a question about the ESP 2 that you were implementing on this did you
ever look at using like the dual core setup to try to sort of accelerate any of the mass
but that is a good question and someone has mentioned this to me before but when I was
writing this I was actually unaware that it had more than one core so I haven't yet but
it's a great idea thanks very much for your talk if you're interested in micro python
in the building a there is a stance about micro python and also a stand by pine 64 who make
like smartwatch that can run micro python and stuff