Is there anyone who know a good Floodfill algorithm? I tried to figure out one myself without any success. Please help me!
Posted on 2001-09-03 03:11:37 by gliptic
I know the lousy flood fill algo, but you could optimize. :)
    [*]Start with a pixel and color on the stack[*]If this pixel equals the color then return[*]Else set pixel to color, and push each pixel and destination color for pixels around this one. And call #1 for each set of pushed valuesYou already knew this most likely. :)

    To optimize it you could keep a history of where you have been and only push pixels that you haven't been to. Also, think about the cache and setting adjacent memory locations.
Posted on 2001-09-03 06:49:36 by bitRAKE
Yes, that's a solution, but not the best solution I think.
Posted on 2001-09-04 01:00:12 by gliptic
Another lousy algorithm off the top of my head (sorry)

instead of points look for line segment from your seed. that way your stack won't have all of the intermediate points... only a slight improvement... some on stack space & about none on speed... it's still general purpose & will work with holes &c.

1) from seed point find Xmin & Xmax while filling the pixels this is your 1st line segment.
2) look for line segments above & below your current line saving end points of the line segments only.

i'd use an 8-neighbor scheme at the edges... that is at the Xmin end of a line segment start looking at the (x-1,y-1) & (x-1,y+1) instead of (x,y-1) & (x,y+1)

but you probobly thought of this one too.

yea I know... lots of hand-waving here... no time to code this suprisingly interesting problem :(
Posted on 2001-09-05 17:49:58 by rafe
If you don't mind converting and optimizing C (HERE) is the flood fill that the allegro library uses. :) What are your ideas, if this isn't the best solution. I'd use MMX and work in horizontal strips. I can think of another fancy method, but it's actually slower than this method. Here are some links on google. :) Here is an interesting improvement. In the case of polygons and such geometric drawing, I'd have the figures filled in the drawing algorithm.
Posted on 2001-09-05 19:00:51 by bitRAKE
Thank you! I think I'll take a closer look at the Allegro source. It seems to be fast.
Posted on 2001-09-06 00:39:29 by gliptic
Some possible (??) slight improvements to Hargreaves routine, in the algorithm not the translation to assembler.

1) You don't need to check the above or below line segments that are up against the parent line segment. This would help eliminate redundant checks to the parent line segment. A similar strategy could apply to BitRake's orginal method.

2) The only time you need to go both directions (East & West) in the extending of new line segments is when a you get a hit at the outer edge. In the 8-neighbor example, if you get a hit @ (x-1, y-1) or (x-1, y+1) then you need to extend (West)

On second thought, this would only buy you the few ticks to check one bit to the West... only saving one iteration per segment, not a huge gain... shouldn't post too early in the morning...


3) Also, there are some, admittedly rare, pathological cases where this method would be a worse that the original method suggested by BitRake, again with the 8-neighbor, if you were filling a checkerboard bit pattern then your stack actually will be bigger.
Posted on 2001-09-06 07:55:13 by rafe
goes like this

assume we are given a point inside the area to flood fill



go left until you hit a margin;

clear_zone_stack;
current_zone:=filled;

LABEL_3:

go_right_one_pixel;
IF current_pixel=empty
fill_the_current_pixel;
IF upper_pixel<>curent_zone
IF current zone=filled
// here we have a clear pixel above
push_the_upper_pixel_into_zone_stack;
ENDIF
XOR current_zone;
ELSE // here we hit right margin
IF zone_stack_is_empty
RETURN
ELSE
pop_a_point_from_zone_stack;
JUMP TO LABEL_3;
ENDIF
ENDIF
JUMP TO LABEL_3


the algo is very fast, and uses low memory because of non recursive version (just zone point stack push/pop) you have to fill in some gaps, mainly the lower zone stack and stuff... but that is exactly the same as the upper zone stack and stuff

a zone stack of about 512 points for Upper stack and the same for lower stack are usually enough

Also you can make pattern fill or fill more pixels at a time to speed up as this algo goes from left to right in a regulated fashion
Posted on 2001-09-25 16:20:41 by BogdanOntanu