20151230

Better 3D graphics on the Arduino: avoiding flickering and tearing

A while ago I purchased a cheap $4 Chinese LCD Arduino shield from Ebay (e.g 1 2 3). The board arrived with no documentation. Disassembling the shield revealed no ICs, indicating that the driver is integrated with the LCD itself. Upon request, the vendor provided an archive containing a few amusingly translated datasheets, as well as a copy of Adafruit's Arduino LCD drivers. Evidently the product is a clone of the Adafruit LCD shields, and uses the ILI9341 LCD driver. I had hoped to use the display to show short animated GIF loops. This is not, in practice, possible. Test animations loaded slowly, with noticeable flicker and vertical tearing. The Arduino does not have enough speed or bandwidth to render full-screen animation frames, but what about 3D vector graphics?



Both optimizing ILI9341 LCD drivers and rendering basic wireframe meshes have been done before. XarkLabs provides an optimized fork of Adafruit's library. Youtube user electrodacus has also implementd an optimize driver for the ILI9341 communicating over SPI. Existing 3D wireframe demonstrations (e.g. 1, 2), even ones using optimized drivers, display a noticeable flicker when the animation updates. This flicker is caused by the delay between when the previous frame is erased and when the new frame is drawn.

Avoiding flicker and tearing There simply isn't enough processing power on the Arduino to render anything significant within one frame length, and isn't enough memory to perform off-screen rendering. The ILI9341 supports a 16-bit RGB color interface with 320x240 pixels, and buffering even a single frame would take 150 kilobytes of memory, compared to the AtMega328's two kilobytes of RAM. The solution is to render animation frames in such a way that the intermediate rendering stages are not noticeable to the human eye. This can be achieved by rendering subsequent frames on top of previous frames without erasing, and then erasing only those pixels that have changed.


3D graphics engine on the Arduino: avoiding flickering and tearing.


Implementing incremental hand-over-hand erasing In order to erase only the pixels that have changed, we need to somehow remember which pixels contain background data, which pixels have been drawn in the current frame, and which pixels need to be erased from the previous frame. Storing a single bit for every pixel would require over 9K of RAM, too much for the AtMega328. At best, one might be able to store a single bit for all pixels within a small 100x100 region. But! the ILI9341 has plenty of RAM to spare. One can store a frame_ID flag in the low-order pixel bits of the color data itself. To erase old frames, inspect the pixel data, and check if the color data belongs to the current or to the previous frame. If it belongs to be previous frame, erase the pixel. This approach works very well, generating smooth, flicker-free 3D wireframe animations.

3D surface rendering: the visibility problem Wireframe rendering is fun, but what about 3D surface rendering? 3D surfaces can overlap themselves, and it is necessary to determine which polygons are in front to properly handle occlusions and overlap. Failure to do so will generate a jumble of triangles, with the back of an object drawn in front of the front and so on. A common solution to this problem is called Z buffering. In Z buffering, every pixel remembers the depth of the polygon drawn to it, and pixels are overwritten only if the new pixel data lies in front of the old. Another approach is to sort the polygons from back to front, and render them in order to an off-screen buffer. Neither solution is possible here, as there is not enough RAM to store either a Z-buffer or an off-screen rendering buffer.

The visibility problem for convex surfaces There is a simple trick to solve the visibility problem for closed convex surfaces, like cubes, spheres, polyhedra, etc. Such surfaces have a front, which is facing the camera, and a back, which is facing away from the camera. To avoid rendering the rear of the object on top of the front, it is sufficient to check whether each polygon faces the camera. This can be done by testing the sign of the z-component of the normal vector to each face. This heuristic is called back-face culling, and it cuts the average rendering time in half as the rear of the object can be skipped entirely.

The visibility problem for non-convex surfaces Non-convex surfaces may contain multiple camera-facing polygons that overlap. The solution is to avoid over-drawing foreground polygons by checking the frame ID bit already stored in the color data. When drawing a new frame, test the frame ID bit for each pixel. If the pixel comes from the previous frame or matches the background color, overwrite it. If this pixel comes from the current frame (i.e. has already been drawn), do not overwrite it. If the faces are drawn front-to-back, this procedure prevents foreground polygons from being overdrawn. Combined with the hand-over-hand approach for erasing the previous frame, this allows for flicker-free rendering of 3D surfaces. The much maligned bubble sort is actually a decent sorting algorithm to use to maintain the polygon drawing order. The code to implement it is small, it operates in-place, and because polygon remain mostly sorted after a small rotation the average runtime remains close to linear.

Modifying the Arduino ILI9341 drivers to support overdraw-avoidance and hand-over-hand erasing Both overdraw-avoidance and hand-over-hand erasing require reading pixel data back from the ILI9341. The Adafruit library version that the vendor provided did not implement reading pixel data for the ILI9341, and existing optimized ILI9341 Arduino drivers were designed for fast writing, not fast reading-and-writing. To achieve performant flicker-free 3D rendering, it was necessary to overhaul the ILI9341 driver. The modified drivers and 3D rendering engine are now hosted online at Github. A few tricks worth noting: (1) Convert I/O operations into direct reads and writes to PORTs and PINs, and combine multiple pin changes into a single PORT write. (2) Sacrifice color accuracy for speed. (3) Terminate commands and data-reads early (e.g. a command to set a screen subregion can be terminated after setting only the lower limit, leaving the upper limit as-is; Reading color data can be terminated after retrieving only the first byte) (4) Reduce flow-control and function call overhead in code "hoptspots" via inlining, converting subroutines to macros, and unrolling loops. (5) Read and write contiguous stretches of display memory at once to avoid the overhead of initiating reading and writing operations. (6) Optimize graphics primitive drawing routines for the Uno and the ILI9341, sacrificing portability in exchange for speed. (7) Forgo bounds-clipping and other luxuries.

Github repository The modifications to Adafruit's drivers necessary for frame-masked erasing and overdraw avoidance were extensive. The graphics primitives drawPixel, drawFastHLine, and drawLine, had to be overhauled read pixel data quickly from the display to supported masked erasing and overdraw avoidance. All other routines had to be extensively optimized to achieve good drawing performance, exhibiting a 4 to 14 fold speedup over the Adafruit drivers. The main demo sketch seen in the videos can be found here. These drivers were specialized for the Atmega and the ILI9341 driver, and are not currently portable. However, much of the data wrangling is handled through macros which could potentially be redefined for other architectures or LCD drivers. Please feel free to borrow from this code, conceptually or literally.

Next steps? There's a lot of room to develop this further as a project. There are plenty of optimization puzzles to solve to accelerate graphics rendering. It would be cool to implement Phong shading, or implement a basic 3D game like Spectre. Supporting other LCD drivers or Arduino models besides the Uno could also be an interesting challenge. And of course, maybe we can eventually return to the problem of rendering animated GIFs on the Arduino.

1 comment: