Hmm, so your flood fill algorithm just traces around the edge of the region until it is all filled? Nice...
I am curious, will it work properly if you have a setup like an hourglass but at the middle (where it is narrow) you have 1 empty pixel with a black pixel on either side?

EDIT: Ah, I see the screenies, now >.>

Hmm, so your flood fill algorithm just traces around the edge of the region until it is all filled? Nice...
I am curious, will it work properly if you have a setup like an hourglass but at the middle (where it is narrow) you have 1 empty pixel with a black pixel on either side?

EDIT: Ah, I see the screenies, now >.>

Yeah, the algorithm traces the edges and only fills in a pixel if it is positive that filling that pixel will not block off another area to fill. If it is unsure, it places a markat that "questionable" pixel indicating the direction it was heading and continues to trace the edges until it comes back to the mark.

If it reaches the mark and the mark is pointing in the direction that it was already heading, then it knows filling that pixel will still allow it to get to the other side.

However, if it reaches the mark and the mark is pointing in a different direction, then there must be some sort of a loop that turns it back onto itself, meaning it wouldn't be able to reach the other side if it filled the pixel.

To eliminate this loop, it turns around and starts backtracking around the loop. Once it reaches another "questionable" pixel in that loop, a second mark is placed on that pixel. It keeps backtracking until it runs into one of the two marks.

If it runs into the second mark before the first mark, it knows the place where it gets turned around on itself must be further into the loop, so it turns around and backtracks again, finding the NEXT "questionable" pixel.

But if it reaches the first mark before the second it knows that filling the pixel at the second mark will get rid of the loop without blocking off the rest of the map. So it fills in the pixel at the second mark, removes both marks, and continues as usual from where the second mark was.


Hope that explanation helps clarify how the algorithm works. It's certainly easier than trying to interpret that pseudocode.


Edit:

In those screenshots, the screen is being updated 4-5 times per frame, so the program is spending most of the time updating the screen. Also, I haven't even started optimizing the code, and I have some ideas for how to optimize the algorithm. In fact, filling a blank screen from the center without updating the screen currently takes only 10 seconds (That's 24x faster than the screenshot ).

Edit: Updating every 256'th frame looks like this:

What about updating every Xth time it paints, not every Xth frame? That might go even faster.

So, uh, I came up with my own algorithm and implemented it in Grammer code. Needless to say, even when updating every frame, it was about as fast as Jacobly's. My calc has crashed so it'll take me a bit to reprogram it, but I wrote down the pseudo code. Before I post it, I want to double check on a few things:
It uses 2 fixed buffers (the graph screen and another 768-byte buffer)
It does not trace around the edge like your code

The code is very simple and you will see why it is fast. I didn't know if using another buffer was okay or not for your implementation.

If you ever wanted to add grayscale support then you'd need another buffer, meaning 3 buffers...that's a lot of memory to keep track of... The whole point is that this algorithm uses no extra memory other than what is in the routine itself.

only one mark is ever placed at a time. yeah.

I'm not sure if this counts to necroposting, but because I need something like that atm I'm now curious to see Xeda's algorithm.

Looks nice Xeda. I think someone should do a drawing program with that kind of algorithm.