Omnimaga
General Discussion => Technology and Development => Computer Programming => Topic started by: BlakPilar on March 02, 2012, 08:38:50 pm
-
A while ago on the IRC I asked about flood fill routines, and Runer was kind enough to point me to Lode's recursive scan-line (http://lodev.org/cgtutor/floodfill.html#Recursive_Scanline_Floodfill_Algorithm) routine. I converted it over to C# and tried to get it to work, but I haven't had any success. Note: I only use two colors- black and white.
Here's the PasteBin: http://pastebin.com/WQNjXm4x
Whenever I flood-fill in an empty region it works fine, but once it reaches some other area, it stops. And when I fill inside of a region, it only "floods" down from where I click (see attachment).
Anyone have an idea?
-
One thing I noticed is that current is not updated before every while loop, which is probably what is causing it to stop. More importantly, you fill the scanline before you scan the pixels adjacent to the scanline, so you can no longer use the pixels in the scanline to know how far to go. The easiest thing I can think to do is to record the lowest and highest values of y while you fill the scanline, and later only look at adjacent pixels up to those values.
-
After you mentioned it, I had thought it was just because I wasn't updating current, so I went with a more direct translation. However, now no matter what it just fills everything in <_<
(PasteBin link is still http://pastebin.com/WQNjXm4x)
-
--snip-- More importantly, you fill the scanline before you scan the pixels adjacent to the scanline, so you can no longer use the pixels in the scanline to know how far to go. The easiest thing I can think to do is to record the lowest and highest values of y while you fill the scanline, and later only look at adjacent pixels up to those values.
:)
-
What I got from the original code is after it fills in a scanline it retraces it (while (y1 < buffer.Height && areColorValuesEqual(buffer.GetPixel(x, y1), end))) while checking pixels to the left or right (if (x < buffer.Width - 1 && areColorValuesEqual(buffer.GetPixel(x +/- 1, y1), start))). So technically doesn't it keep track of the highest and lowest for you?
-
Imagine:
-----
| # |
|###|
| |
| X |
| |
|###|
| # |
-----
First, it fills the scanline.
-----
| # |
|###|
| # |
| # |
| # |
|###|
| # |
-----
Then it scans the (now longer) black scanline, and fills adjacent areas.
-----
|###|
|###|
|###|
|###|
|###|
|###|
|###|
-----
Which I don't believe is what you want. :)
Edit: (btw, I'm just going by what your code says, I haven't looked at the algorithm.)
-
Ok, but if I have something like this, shouldn't it work the way it's supposed to?
---------
| |
| ##### |
| # # |
| # X # |
| # # |
| ##### |
| |
---------
---------
| |
| ##### |
| # # # |
| # # # |
| # # # |
| ##### |
| |
---------
---------
| |
| ##### |
| ### # |
| ### # |
| ### # |
| ##### |
| |
---------
---------
| |
| ##### |
| ##### |
| ##### |
| ##### |
| ##### |
| |
---------
-
Never mind. I was thinking about it all last night, and I finally understood what you meant. I did what you said, and it works ;D thank you! (I've also updated the PasteBin if anyone wants to see what it looks like now.)