Omnimaga

General Discussion => Technology and Development => Computer Programming => Topic started by: BlakPilar on March 02, 2012, 08:38:50 pm

Title: [C#] Scan-line flood-fill
Post 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?
Title: Re: [C#] Scan-line flood-fill
Post by: jacobly on March 02, 2012, 08:52:08 pm
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.
Title: Re: [C#] Scan-line flood-fill
Post by: BlakPilar on March 02, 2012, 09:27:14 pm
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)
Title: Re: [C#] Scan-line flood-fill
Post by: jacobly on March 02, 2012, 09:28:59 pm
--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.
:)
Title: Re: [C#] Scan-line flood-fill
Post by: BlakPilar on March 02, 2012, 09:32:29 pm
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?
Title: Re: [C#] Scan-line flood-fill
Post by: jacobly on March 02, 2012, 09:40:41 pm
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.)
Title: Re: [C#] Scan-line flood-fill
Post by: BlakPilar on March 02, 2012, 09:51:47 pm
Ok, but if I have something like this, shouldn't it work the way it's supposed to?

---------
|       |
| ##### |
| #   # |
| # X # |
| #   # |
| ##### |
|       |
---------

---------
|       |
| ##### |
| # # # |
| # # # |
| # # # |
| ##### |
|       |
---------

---------
|       |
| ##### |
| ### # |
| ### # |
| ### # |
| ##### |
|       |
---------

---------
|       |
| ##### |
| ##### |
| ##### |
| ##### |
| ##### |
|       |
---------
Title: Re: [C#] Scan-line flood-fill
Post by: BlakPilar on March 03, 2012, 12:15:39 pm
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.)