The algorithm uses about half a byte per pixel and saves the path it follows. That kind of implies that the stack is still there and present, it’s just bounded to the number of pixels, and could actually be modified to just use a bounded area of the heap. But conceptually it’s easier to follow the way the paper was written. Neat.

▲

kragen 4 hours ago | parent | next [-]

In a sense it uses half a byte per pixel, but Nils M Holm's suggested implementation is to reserve 16 colors for the flood-fill algorithm, because you don't need to remember the color of the pixels you're flood-filling, so you can overwrite them with the flood-fill algorithm's state. The path is saved in those same 16 colors. This reduces your available color space, assuming 8-bit color, from 256 colors to 240 colors, which means you get 7.91-bit color instead of 8-bit color. So it actually only uses 0.09 bits per pixel, which at 1024×768 is 9154 bytes.

If you were to instead use a bounded area of the heap with 4 bits per pixel, as you are suggesting, your bound would be 393216 bytes.

However, it's not totally clear that that's the right way to account for it, because if you have a 256-color image that you have to reduce to 240 colors to have space for this algorithm, there isn't an obvious way to get back the lost colors by storing 9154 bytes somewhere else. You might be able to do something like pick the least popular 16 colors from the image (which occupy a maximum of 49152 pixels and usually less), store a bitmap telling where they were (98304 bytes), store the colors of the marked pixels into a 24576-byte array, replace them with some neutral color, run the flood fill, and then restore the colors. But, while that uses significantly less than 393216 bytes, it still uses a lot more than 9154 bytes, and it's probably pretty slow on the kind of computer where you'd be trying to do something like this.

At the other extreme, if your 256-color image actually only used the 216 "web-safe" colors (#000, #003, #006, ... #030, #033, etc.), you'd already have 16 leftover colors available. And freeing up 16 colors on a 16-bit or 24-bit TrueColor display would damage the image quality only imperceptibly.

▲

hyperhello 3 hours ago | parent [-]

I remember Mario Paint on Super Nintendo visibly flood-filling an area, but a computer that paints in modern image formats is probably not going to mind temporary allocation of a few hundred K. There are some fun opportunities to optimize, though, like checking a cache line of pixels at a time, or maybe tiling the image in 16-pixel squares using the same algorithm, and then cleaning up the edges.

	▲	Jtsummers 3 hours ago \| parent [-]
		The author of the submitted article has written about working in constrained environments. The algorithm he describes would be suitable for that kind of environment, where a few hundred K may not be available, or not without jumping through hoops to make it available. https://t3x.org/#wyorc - One example, this is a book on writing a compiler targeting Z80 processors.

▲

taneq 6 hours ago | parent | prev [-]

The pixels are effectively being turned into a linked list using the special values as ‘pointers’. This list is used as a stack, and the current position is the stack pointer.

I don’t think they explain the backtracking part very well, and they should have used an example that fills a non-rectangular area so it actually demonstrates the whole algorithm.

It’s a neat trick if you have spare values to use as markers, though. :)