Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Stefpet

Fill algorithm

This topic is 6928 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What''s the smartest way to fill an area? The image is represented by an array of integers [WIDTH*HEIGHT] where the bounds (border) of the area that should be filled are integers set to 1, the "empty space" is 0. Filling an area in this case means changing the integer value of those points that is visually within the border. Very similar to using fill in a paint program. I''ve got two similar ideas of how to do this. The first is picking a point within the area that should be filled and recursivly (correct english?) check all pixels that is nearby and stop when the border is detected. The other idea is almost identical, but in this case I asume that the area may be split into various of rectangles (the smallest 1x1 pixels though). And then I fill rectangle by rectangle by recursivly finding it''s coordinates. However, it''s just an idea. Basically, my question is... how do I do a fill routine that fill an area (limited by a border which we don''t know how it looks)? Thanks in advance for any comments.

Share this post


Link to post
Share on other sites
Advertisement
I divide the polygon up into triangles, and then draw each triangle using special formulas and algorithms.

PCMCIA - People Can't Memorize Computer Industry Acronyms
ISDN - It Still Does Nothing
APPLE - Arrogance Produces Profit-Losing Entity
SCSI - System Can't See It
DOS - Defunct Operating System
BASIC - Bill's Attempt to Seize Industry Control
IBM - I Blame Microsoft
DEC - Do Expect Cuts
CD-ROM - Consumer Device, Rendered Obsolete in Months
OS/2 - Obsolete Soon, Too.
WWW - World Wide Wait
MACINTOSH - Most Applications Crash; If Not, The Operating System Hangs

Share this post


Link to post
Share on other sites
Hi Stefpet,

The first way you described is a flood-fill algorithm, and its a pretty good way to do it. As you said, you can start from a point you know to be inside the border, and recursively fill each pixel around it if it is not (a)a border pixel, or (b) already filled with that colour.

The thing to watch for is gaps in the border. Especially where it is only one pixel wide, and on an angle like this:

000000010...
000000100...
000001000...
000010000...
000010000...
...
etc

... because if you are checking the eight pixels surrounding each pixel being filled (above, below, left, right, and diagonals), the fill will escape over the boundary by the diagonals (hey, there''s a 0 over there... let''s get ''im! ).

This can easily be extended beyond looking for one type of border... just change the comparison to see if it is the original colour of the first/selected/root point. If it is, fill it, if not, leave it. (this is what a paint program would probably be doing).

I think this (your first idea) way would be the best.
Now go forth and fill

-------------
squirrels are a remarkable source of protein...

Share this post


Link to post
Share on other sites
One of my prof''s talked about a technique of moving left to right across the screen and when you passed a border you started filling and when you passed a border again you stopped filling, and so on only filling on odd passes over borders. Due to the laws of topology, odd areas will be inside a closed area and even areas will be ouside.
There are probably a million ways to fill and recursing is probably best, so this info is completely useless but you read this far so the information is stuck in your brain cells! ha!

Share this post


Link to post
Share on other sites
RotoMuffin, that''s actually a very interesting idea. Especially in the case I''m planning to use it in (it''s not a paint program), I think I will try to experiment a little bit about it and see how it turns out. That method should be a lot faster the the recursive flood-file.

Especially if you detect the borders and then set the whole slot (between the borders) in the array at once instead of setting each integer at a time.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!