The BBC Micro:Bit is a single-board computer that aims to help children learn to code. It has 16KB of RAM, a 16MHz processor, and a 25 pixel “screen” (which is just a 5x5 LED array). On their website, they propose lots of fun ideas that you can try.
For some reason, they don’t suggest trying to implement a ray tracer - an algorithm which simulates light rays to render a 3D scene. That may have something to do with the fact that ray tracing is incredibly slow, even on fast computers and Pixar has entire supercomputers dedicated to it. Nonetheless, I like a challenge!
I don’t want to keep you waiting, so here’s the end result. The Micro:Bit is rendering a pyramid, with two bright red sides and two dark red sides. You can turn the camera by tilting, and move it with the buttons.
The remainder of this post discusses more about the Micro:Bit, and explains what a ray tracer actually is and how it works. In my next blog post, I will discuss the actual implementation, and the challenges I faced when optimising such an intensive algorithm for the Micro:Bit.
A :bit more about the Micro:Bit
I apologise for that subheading…
The BBC Micro:Bit is a single-board computer, like a Raspberry Pi or Arduino. It was announced March 2015 and released February 2016, costing under £15. For that, you get a pretty impressive feature list:
- 16MHz ARM Cortex-M0 processor
- 256KB nonvolatile storage and 16KB RAM
- Power via USB or Battery
- 25 LEDs
- Radio & Bluetooth
- 2 programmable buttons
- Accelerometer, Compass, Light & Temperature sensors
- 3 general purpose input/output (GPIO) pins
- 3V 90mA power & ground for accessories
There are many ways to program the Micro:Bit, including:
- Python (actually MicroPython)
- Many other 3rd party programs
In any source language, the user’s program is compiled to a HEX file which contains the ARM assembly code. This assembly code usually interacts with the device abstraction layer which provides a simpler interface for controlling the board’s functionality such as Bluetooth and accelerometer.
Basically everything about the Micro:Bit is open-source and well-documented, so check out their developer site.
What’s a Ray Tracer, Anyway?
A ray tracer is a program which renders a 3D scene by simulating the path of light from a virtual camera. Rather than try and explain it in words, I have created a series of pictures demonstrating the process:
On the left hand side of the scene, we can see the virtual camera.
It sits behind the origin point, and is currently looking straight ahead, in the
The pyramid is made of four triangles. It sits further away from the camera, with two light sides and two dark sides.
Here, we visualise the
view plane - the representation of the screen.
It is a 5x5 grid, which sits 1m away from the camera.
The width of the grid is customisable, and affects how wide of a view the camera has.
Each LED on the Micro:Bit is represented by one cell in the grid.
Now, we simulate the rays. Each of the 25 rays originates at the camera (now hidden) and travels through the center of a grid cell. For higher-quality rendering you could send multiple rays through each pixel, evenly spaced, and average the result.
Some of the rays went through the pyramid. Let’s just keep those, and remove the ones that didn’t hit anything.
Any time a ray hits something, we fill that cell the same colour as the object that the ray hit. This means that if a ray hits the dark side of the pyramid, the cell would get filled in a darker colour. The rays that don’t hit anything get coloured in black, since the camera can’t see anything in that pixel.
Bear in mind that this is the absolute simplest version of ray tracing. More advanced versions simulate the light as it bounces off objects or refracts through glass. They also consider the location of virtual lights within the 3D scene, allowing objects to cast shadows that appear in the resulting renders. Considering that the Micro:Bit already struggled with the simple version, that may have been a bit much to ask.
Frankly, I think this was an outstanding success. It works well enough on the Micro:Bit, it’s accurate, and it works really well as a learning tool. I understand ray tracers much better, and it was a great excuse to play with the Micro:Bit!
Keep an eye out for Part 2 (ETA 10th March), where I discuss how you actually implement a ray tracer, and how I approached programming the Micro:Bit for maximum performance.