Flood Fill, or: The Joy of Resource Constraints

• Optimization
• Algorithms

Robust engineering and programming practices may be vital for a successful embedded business, but they are rarely the reason why people are drawn into the embedded world in the first place. In this article I'll explain, with the help of a concrete example, what made me choose this line of work – and hopefully, bring back some fond memories to you too.

The Wonder Years

There's a famous quip, "The golden age of Science Fiction is twelve". It suggests that the genre is at its best, not necessarily when the "objectively" best books are written, but when the readers' imagination is fresh and wild, their openness to new ideas is high, and their literary standards – let's be honest – aren't. Based on the same principle, I would suggest that the golden age of programming is around sixteen. It certainly was for me, and at that time, programming involved a lot of fun, creative optimizing to deal with limited resources.

I should probably clarify what I mean by "resource constraints". If someone charged me $50 each time I invoked the compiler, that would have been very constraining, for sure, but hardly fun. So, I'll limit the discussion to limitations that can be overcome with "better code": limited RAM, slow CPU and so forth.

To put things in context, it was in the early 90s: Turbo Pascal, i386 and all that. Therefore, the limitations I experienced were laughable compared to what previous generations had to deal with. Nonetheless they were very tangible, and because I had no Internet and almost no one to ask, I had to figure out many things all by myself. I cut my bit-manipulating teeth on monochrome graphics (where each byte represented 8 pixels), implemented various compressions to save diskette space, and so on. It wasn't ground-breaking work by any measure, but it was mine, and I could literally see my efforts paying off.

Jump forward about 20 years: for the kind of small utility or fun programs that I was writing for my PC, all those exciting optimization tricks became irrelevant. Computers were so fast, with so much memory, that the effects became almost imperceptible. Also, gone were the days of direct access to interesting hardware; now I had to jump through the hoops of someone else's APIs and abstractions.

Flooding redux

Then I came across Arduino, and following that, 8-bit microcontrollers in general. As cool as it was to control LEDs and little servo motors, what I really liked about them was that they sent me back to that golden age, of having direct access to hardware and having to think carefully about algorithms and optimizations. Here's a little example from real life: How do you implement a "Flood Fill" algorithm on an MCU with barely 2KB of SRAM?

Imagine a two-dimensional array of bytes, each representing a color so that the entire array represents an image. On that image we have an arbitrarily shaped, single-colored area, that's defined by the image borders and/or different-colored "pixels". Beginning with a coordinate known to be within that area, how do we go about changing the color of the entire area, and nothing else? For example, here's the "before" (left) and "after" of a white flood fill of the black area marked with the small cross:

This well-known problem, common in beginner computer graphics, was solved ages ago. The basic solution is recursive and elegant: First, paint the initial pixel white. Then, for each of the pixels touching it (up, down, left, right), check if it's black – and if it is, simply repeat the process for that pixel. Don't forget the image borders.

It works, but it's rather slow, and can be optimized in several ways. When I was sixteen, I was very proud of myself for (re)discovering some of them. However, these "usual" optimizations don’t address our humble MCU's problem: all of them, except in trivial cases, still require far too much memory. Whether they use regular recursion or substitute it with queues, the MCU's stack will inevitably run out.

This sort of thing happens over and over again in embedded development (at least, the sort of development I do). Unique per-project requirements and limitations exclude many traditional software solutions, so I must reinvent them – this time, not because there's no Internet to ask, but because the Internet doesn't have answers. That's the spice that keeps the job from becoming rote.

A solution

So, how do you Flood Fill without allocating, implicitly or explicitly, a lot of extra SRAM?

The key to the answer lies in what I wrote about the pixel array, where "each [byte is] representing a color". Note that in principle, two values can represent the same color - and even if the specific hardware forbids this, colors can still be very similar to each other, to the point of being indistinguishable to the naked eye. Knowing that, now we just need one color value which is guaranteed not to be in the original image. Luckily, I had that. Do you see where this is going?

Here's the algorithm in its crudest form. Let's call the original color of the target area "A", the unique but indistinguishable color "B", and the final color "C". We start by painting the origin coordinate with "B" (remember, the user can't see this change!) Then we scan the entire pixel array, looking for pixels with color "A" who are touching a pixel with color "B". Whenever we find one, we paint it over with "B". We repeat this process until the scan finds no new pixels to paint. Then we go over the pixel array one last time, replacing all instances of "B" with "C". Done! Almost zero extra memory is required, beyond the display memory which is already allocated. Too slow, you say? It can be improved significantly, for instance by filling up horizontal spans instead of single pixels. I'll leave the other tricks to you.

Fun is still on the menu

I think it's safe to assume that everyone here enjoys a good puzzle, and if that puzzle involves programming, all the better. Unfortunately, the advances in hardware and the spreading of knowledge made such puzzles harder and harder to come by in a business environment: Everything's been done before, usually by people smarter than us, and reinventing wheels for the fun of it makes no economic sense.

However, in the embedded world there still exist niches where we can come up with novel solutions. These solutions do not appear in textbooks or even on StackOverflow, because their circumstances are too unique. The idiosyncratic constraints of each project, and the loopholes we may find hidden in and between them, give us the freedom to stay creative and enjoy this aspect of our work. Do you have similar experiences to share?

Sign in