QBX: Border Fill Algorithm

In paint programs, a common operation is Flood Fill. You pick a colour, click on a region, and that region is "flooded" with that colour. Every adjacent pixel of the same colour is replaced by your new colour.

In QuickBASIC, there is a statement PAINT which provides a related function, but it is different in a subtle but very important way: It doesn't paint as long as it sees pixels of the same colour, it paints up until a specified border. It doesn't matter what pixels it is replacing. This is a related operation called a Border Fill.

It cannot be overstated: Border Fill is much trickier to implement than Flood Fill!

But, for QBX to faithfully execute QuickBASIC code, it needed a Border Fill algorithm that was reliable and fast.

The implementation of QBX's Border Fill uses an interesting data structure: It tracks a subset of a 2D area as a series of intervals using an Interval Set structure built on a B-Tree. The B-Tree can very quickly enumerate all elements whose keys are greater than or equal to a specified key. The intervals are placed into the tree using their right edges as the key. It is then possible to test whether a given coordinate is in the set or not by enumerating the intervals whose right edge is greater than or equal to the given coordinate. This immediately eliminates all sets that come before it, and the enumeration will either find an interval that contains the point, or it will find an interval that comes after the point -- in which case all future intervals also come after the point. Fast algorithms for intersecting intervals are also possible.

The initial implementation tried very hard to maintain a traditional queue of spans needing to be processed, but I just couldn't get it perfect. There was always some edge case that would either fail to paint or enter an infinite loop, processing areas it had already processed. I came to the conclusion that this was because:

• Spans in the queue to be processed don't get merged together if they're adjacent, and
• When advancing to a new scan and trying to expand left or right, the expansions are queued as independent entries (because they have different propagation flags)

But, it suddenly occurred to me that the merging problem could be solved with the existing interval set implementation I was already using to track which parts were processed, and that once I did that, there were no propagation flags any more, which meant that the extension could simply be processed as part of the span it came from, rather than being queued independently.

So, I reworked it to do exactly that, and that solved all the problems.