Fill ´er up! [Graphics filling algorithms]

One of the most important and useful ideas in 2D computer graphics is the fill. Simple in concept but powerful in practice, filling is so basic a technique that there´s a fill tool in just about every 2D drawing system sold today. Probably one of the first important uses of fills was to color in 2D cartoon characters, but that´s just the tip of the iceberg. It´s hard to know who wrote the first fill routine, but it may have been Dick Shoup, who implemented a fill technique for his Superpaint system in the mid-1970s. The next big step was Alvy Ray Smith´s 24-bit flood-fill algorithm, which also included tint fill. Change came fast after that point, culminating in the sophisticated filling tools we have today. In this article, I discuss some fill techniques that I´ve cooked up over time to solve different jobs. I focus on techniques for identifying fill pixels