Add your own alternative version
Stats
425.1K views 11K downloads 103 bookmarked
Posted
2 Feb 2004
Licenced
|
Comments and Discussions
|
|
I liked your page and I studied the code. However, it was too complex for me. So went back to basics and came up with a much smaller code, which is also faster, it has something like 20-30 instructions for every blank neighbor space. I achieve 9 million filled pixels every second, using only 50 lines of code. Here is a demonstration:
youtube.com/watch?v=4hQ1wA4Sl4c&feature=youtu.be
and here is a page where I attempted to explain how it works.
Unity3D marching cubes attempt blog[^]
And the code.
Recursions would be the fastest if they could stay organized.
If you recurse through a grid of data (image) you can store the processing of the recursions in grid format too, because the processed steps represent pixels from the grid, rather than explode the results into a tree format, which is what programmers presume is the only way an recursion can be organized, that is a wrong presumption for floodfills.
No one doubts that you can remap the pixels from a recursion big tree process into a tiny 2d array. You just have to challenge yourself to write 15 lines to sequence the memory usage of the recursion...
The recursions abort on the first line for previously filled pixels,= 1 instruction, The recursions runs about 28 instructions for every fillable neighbor... The recursions act like efficient scan lines which are very easy to write, because the iterations of the recursions fill like dominoes, all rows and all columns in subsequent iterations, very fast.
Normal photo floodfill then takes say 1mn x 28 + 4 million Flops... thats about .5 seconds for an I5.
It uses 3 copies of the image as ram for neighbord previosly memorization. Thats how you use 1 istruction per blank.
Ive done it on 2billion voxels, takes 5 minutes. 2bn x 28 +10bn.... 74bn...Flops
Am i wrong? Sry i dont think thats posdible, and sorry i write unclear recursion memory advice posts!!!!!!!.
Count your versions instructions and laugh at me on you can
You have to copy the picture 2-3 times in copies of itself, but that's your maximum memory footprint: 2-3 times the image only.
One of the picture copies is called checkneighbors and the other is called filled. The recursion then breaks on the first line if the pixel is filled, it fills it if it is empty and checks it's neighbors, and it overwrites the check neighbors array 8 times onto one array XY position, thereby turning 8 recursion branchins into a maximum 1 branch, the recursion is:
1.If a neighbor pixel is marked in the checkedneighbor array, check if the pixel is filled, if yes, break.
2.the pixel is marked as an empty neighbor, and it is empty, fill it, and:
3.check neighbors, and if they are empty, write them to checkneighbors array as requiring a fill/neighbor check.
|
|
|
|
|
Hi,
I really like this idea and am also planning to take a look at Think-A-Tron's and Bond's implementations of Flood Fill. I would like to use this in an open-source plugin and just wanted to ask you if I could. I took a look at the license included in the C++ file but it didn't mention anything regarding modified redistribution so just wanted to check with you.
This code may be used in compiled form in any way you desire. This
file may be redistributed unmodified by any means PROVIDING it is
not sold for profit without the authors written consent, and
providing that this notice and the authors name is included. If
the source code in this file is used in any commercial application
then a simple email would be nice.
I also tried your e-mail but could not reach it and decided to ask you here instead.
Thank you. 
|
|
|
|
|
Hi John,
We would like to use your QuickFill algorithm and get in touch with you about some questions. I have tried your email address listed in the source code, but it doesn't seem to be active/work anymore.
Can you provide me another email address that i can use to contact you.
Thanks,
Alex
|
|
|
|
|
Crash on boot up. Assert violation filelist.cpp.
#ifdef UNICODE
hr = afxGlobalData.ShellCreateItemFromParsingName(lpszPathName, NULL, IID_IShellItem, reinterpret_cast<void**>(&psi));
#else
{
USES_CONVERSION;
LPOLESTR lpWPath = A2W(lpszPathName);
hr = afxGlobalData.ShellCreateItemFromParsingName(lpWPath, NULL, IID_IShellItem, (LPVOID*)&psi);
}
#endif
ENSURE(SUCCEEDED(hr));
Add(psi, strAppID);
#endif
}
Your demo works pretty well. Any idea how to fix it?
|
|
|
|
|
OK. I got it working by simply correcting a few code errors and adding some new file references to the RecentFileList in the app registry. Oddly, this demo automatically loads the test.bmp but needs the RecentFileList entry to do so.
Specifically,
QuickFillDemoView.cpp
static const int LG_MAXMAG = 10;
static const int LG_SELPENWIDTH = 3;
Quantize.cpp (needs scoped references to loop counters)
UINT i = 0;
int i = 0;
Also, the test.bmp provided has line breaks everywhere so the whole bmp is always flood filled. I have tested the app with my own bmp that has unbroken line sections and each section fills independently but, as mentioned,does not persist. One would need to save the partially filled bmp in memory to fill different sections with different colors in a persistent manner. Any code to do this greatly appreciated.
|
|
|
|
|
Glad you solved the crashing issue, since I have not compiled this for some time. The test application is not met to be useful for anything; other than demonstrating what the algorithm can do. The test bitmap was created specifically to test all possible flooding cases and was instrumental in discovering 1 special case that the original algorithm did not take into account.
I will load this up in Visual Studio 2013 and see if there is anything else wrong.
INTP
"Program testing can be used to show the presence of bugs, but never to show their absence." - Edsger Dijkstra
"I have never been lost, but I will admit to being confused for several weeks. " - Daniel Boone
|
|
|
|
|
John,
From the "QuickFill: An efficient flood fill algorithm" is the following text:
"This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below."
Could you please reply to this post privately so I can ask you a more detailed question about acquiring a license to use the code posted in this article?
Thanks,
-Joe
|
|
|
|
|
I just posted a paper on my website, http://www.crbond.com , which describes in detail a flood fill algorithm which only visits each processed pixel once. It supports filling from other bitmaps, tiles, gradient fills, re-bordering, and flooding under text. I was able to avoid the revisiting problem by processing filled line segments, one at a time, and pushing candidate scan areas on an "up" stack or a "down" stack, depending on which side of the current scan line the adjacent test region was on.
C. R. Bond
|
|
|
|
|
The current version of the description of the flood fill algorithm presented on my website includes a proof that only a single visit of each pixel is possible. To my knowledge, no proof of performance for any other method has been presented in the literature. I welcome comments.
|
|
|
|
|
Hi Bond,
I liked your paper. As far as I can tell, your logic is correct and no revisits would occur. You have even given me an idea, that I cannot remember testing, on how I might fix the revisit problem in my code – if I ever have the time.
And now for the “But” that you knew was coming.
History:
At the time I wrote the original version of the QuickFill algorithm, memory was at a premium and the reduction in stack size was as important as speed. I suspect that the floodfill() in Microsoft's old DOS graphics library may have used a method similar to yours. Microsoft's version choked on one of my solid fill tests and I have always assumed that it just ran out of fixed sized stack space. I cannot remember if it locked up or just returned without finishing the job; I suspect the latter.
Efficiency:
The efficiency of your algorithm is tied directly to the size of your stacks. If they where allocated dynamically, as needed, there would be a drop in efficiency while the stacks where growing. But under normal circumstances, a reasonable initial size, that can grow by a fixed amount - if needed, would help reduce possible memory allocation [and copy] hits.
The reason I bring up memory allocation, as opposed to a fixed stack size, is that the size of the stacks required by your algorithm could be quite large. In the test I mentioned above, the number of segments that could be pushed on the stack was in the hundreds, if not more. That is why that method was rejected during the design of the QuickFill algorithm – it did not meet efficient memory usage requirements.
The Test:
If I remember correctly, I created a very large image filled with U shaped boxes, at least 3x2 pixels, spaced 1 or 2 pixels apart. Then set the fill point (seed point) at bottom to see what happened.
I believe this, or something similar, would be a good test for your algorithm, as every one of the openings to each of those boxes will be pushed onto the fill down stack before fill_up() is finished.
Any way, thanks for the post, I found it educational.
- John R. Shaw
INTP
"Program testing can be used to show the presence of bugs, but never to show their absence." - Edsger Dijkstra
"I have never been lost, but I will admit to being confused for several weeks. " - Daniel Boone
|
|
|
|
|
Hi John,
Thanks for the response. Regarding the memory efficiency vs. other considerations, I guess it's too much to expect one algorithm to achieve everything. Anyway, I've written a test program which monitors the pixel visits, stack sizes, etc., and hope to expand the paper to disclose everything I've found. Ideally, a potential requirement for flood fill methods could order the priorities in a way that makes the final selection of a method fairly straightforward.
When I revise the paper to include test data, I'll forward a link to you.
Thanks again,
C. Bond, cbond@ix.netcom.com
|
|
|
|
|
Perhaps I misunderstand something, but consider the following fill beginning at 1, where the numbers are fillable and the Xs aren't:
<br />
X X X X X<br />
X 2 3 4 X<br />
X 1 X 5 X<br />
X 8 7 6 X<br />
X X X X X<br />
As I understand it:
1 would be filled and 8 would be pushed on the down stack.
234 would be filled and 5 would be pushed on the down stack.
Since the top boundary is reached, 5 would be popped and a down scan begun.
5 would be filled.
678 would be filled and 1 would be pushed on the up stack.
Since the bottom boundary is reached, 1 would be popped and an up scan begun.
1 would be revisited.
Since 1 is already filled, 8 would be popped and a down scan begun.
8 would be revisited.
The fill would be complete since 8 is already filled and the stacks are empty.
modified on Monday, June 6, 2011 3:23 AM
|
|
|
|
|
You are correct for the situation you posted and for the explanation I gave in my paper. However, there was a section left out of the paper which explains the stack-checking algorithm which removes visited pixels from the stack.
On reviewing the paper, I found that the text was so poorly done, that I needed to provide graphic examples for situations such as the one you cited. This revision is in preparation and when I repost it, I'll leave a message on this forum.
Sorry for doing most, but not all of the job I set out to do. And thanks for taking the time to dig out an omission.
In short, there is an additional test required following each segment fill which removes overlapping pixels from the stack. The overhead is light, because the stack does not grow very rapidly. I have a version which reports the stack depth and have verified this over dozens of example screens -- including screens with text.
|
|
|
|
|
Hi Bond,
For some reason I cannot load your paper at the moment to see what has changed. Last time we communicated, I tried to find my old revisit test result bitmaps and could not, so I did not tell you about them. Besides, I stripped all the code out that generated them without keeping a copy of it.
I am a visual person, so for revisit testing I created something like a 2D array of integers, that had one value for each pixel in the bitmap. Every time a pixel was read (visited), it would increment the associated value in the 2D array. After the fill was complete, it would generate a bitmap (Think Minesweeper) showing the number of visits - single visits green, revisits red, and unvisited white.
I used this method in a number of ways for testing. I even used it to generate a series of bitmaps, for small fills, that showed each step along the way.
Any way – you get the idea.
Happy coding,
INTP
"Program testing can be used to show the presence of bugs, but never to show their absence." - Edsger Dijkstra
"I have never been lost, but I will admit to being confused for several weeks. " - Daniel Boone
|
|
|
|
|
Hi John,
It may be a few days before I post the complete algorithm for a single-visit flood fill, because I have to squeeze the work between other projects and some graphics are needed to illustrate the stack-test algorithm.
Basically, after each segment fill, the stack is scanned for overlapping pixels. This is facilitated by the fact that the line number, one of the entries on the stack, is known. Overlapping pixels are deleted or suitably trimmed.
For testing, I did exactly as you did: I wrote a special purpose fill routine which increments fillable pixels so revisits could be identified easily. I have confirmed the method with 2D fields consisting of backgrounds with randomly placed barriers or with ASCII text.
I'll try and finish the paper in a timely manner, because I don't like having incomplete or misleading documents or tutorials on my website. However, interested coders can certainly implement a stack scanner themselves if they wish. The paper will offer complete pseudo-code and possible actual C code if I can.
Thanks for all comments, including negative ones which point to the need for improvements. I'll post a notice here when I get things done.
|
|
|
|
|
Yes, I think that revisits can be eliminated by checking the stacks, though the challenge is to do so efficiently enough that the extra checking doesn't outweigh the advantage of avoiding revisits.
John R Shaw references a paper, An Efficient Flood Visit Algorithm, by Anton Treuenfels in Dr. Dobbs that describes one approach. Unfortunately, the paper isn't as clearly written as it it could be, and as I recall, the code contains a few errors. Nevertheless, I think the overall approach is quite good. I haven't yet convinced myself beyond a doubt that Treuenfels's method eliminates revisiting filled pixels, but think it's likely it does.
|
|
|
|
|
Whoops!
I wrote this after seeing the question in my email and posted before seeing that the question was not for me. Oh well - enjoy the information any way.
Unfortunately you did misunderstand, but to be sure I walked through it to double check.
Keep in mind that only filled parent segments are on the stack, along with an indicator (dy) where it may have a child segment. Also that the stack is a stack in name only; it stopped being an actual stack as soon as sorting and line segment culling was added.
First take a look at PushOpposite; it is doing roughly the following;
if ( No parent segment is found on stack ) {
if ( Clipped version of current segment would be a valid child segment )
Push clipped segment
}
else {
if ( We can create any clipped segments that do not overlap any of its parent segments )
Push those clipped segments
if ( Any parent segments from the stack would completely overlap the current segment )
Remove those parent segments from the stack
if ( Any parent segment only partially overlaps the current segment )
Clip that parent segment; so that it is no longer overlapping
}
Now here is what will happen:
Push S1 = { 1, dy = +1 }
Push S2 = { 8, dy = -1 }
Stack = { S1, S2 }
Pop S2
Push S3 = { 1, dy = -1 }
Stack = { S1, S3 }
Pop S3
Push S4 = { 234, dy = -1 }
Push Opposite S5 = { 4, dy = +1 }
Stack = { S1, S4, S5 }
Pop S5
Push S6 = { 5, dy = +1 }
Stack = { S1, S3, S6 }
Pop S6
Push S7 = { 678, dy = +1 }
Push Opposite: Nothing pushed - S1 is popped/removed from stack because we just filled its child
Stack = { S4, S7 }
Pop S7
Pop S4
Stack = {empty}
Finished: Clean up and return result
Let's check your statements:
1) 1 would be filled and 8 would be pushed on the down stack.
No: 1 would be filled and 2 would be pushed on the stack. The parent of 8 is already on the stack.
2) 234 would be filled and 5 would be pushed on the down stack.
Close: 234 would be filled; the top boundary segment and 5 would be pushed on the stack.
3) Since the top boundary is reached, 5 would be popped and a down scan begun.
No: 5 would be popped because it is the next item on the stack.
4) 5 would be filled.
Correct.
5) 678 would be filled and 1 would be pushed on the up stack.
No: 678 would be filled and the bottom boundary segment would be pushed on the stack. Since 1 is a [overlapping] parent of 8 and is already on the stack, it is removed from the stack.
6) Since the bottom boundary is reached, 8 would be popped and a down scan begun.
Close: The bottom boundary is popped and scanned. The parent of 8 is no longer on the stack (See (5) above).
7) 8 would be revisited.
No: We are currently visiting the bottom boundary (See (6) above).
8) Since the bottom boundary is reached, 1 would be popped from the up stack.
No: The top boundary is popped and scanned, neither 1 nor any parent of 1 is on the stack.
9) 1 would be revisited.
No: We are currently visiting the top boundary (See (8) above).
10) The fill would be complete since 1 is already filled and the stacks are empty.
Almost correct: The fill is complete because the stack is empty.
INTP
"Program testing can be used to show the presence of bugs, but never to show their absence." - Edsger Dijkstra
"I have never been lost, but I will admit to being confused for several weeks. " - Daniel Boone
|
|
|
|
|
Actually, I have a question for you. You reference the Dr. Dobbs article An Efficient Flood Visit Algorithm by Anton Treuenfels that claims no revisits, but you mention that a change you made to your code reduced, but didn't eliminate, revisits. Did you use a different method than Treuenfels, or does his method fail to eliminate revisits? If you didn't use Treuenfels's algorithm, did you have a particular reason for not using it?
I'm interested in having a general fill routine that doesn't revisit filled pixels, and have been looking at the Dr. Dobbs article in background mode as a basis for writing a fill routine. I can see why a method that removes duplicate spans from the stack (or whatever memory stucture) could eliminate revisits, but I'm not yet completely convinced Treuenfels's method always succeeds in doing so. At least for me, analyzing when revisits can occur isn't easy.
Thanks,
Think-A-Tron
(Which, in case you wondered, was the name of a toy computer game.)
|
|
|
|
|
Actually, I never tested Treuenfels code to see if it eliminated all revisits. Given my current knowledge and a quick review of the code presented in his article, I do not believe it does. Although this can only be verified by thorough testing.
My algorithm came to me some months after reading the articles cited and is a combination of the ideas presented in both of them; therefore it uses similar methods. At the time I was only concerned about efficiency/speed; because reading and writing directly to video memory can be very expensive. When testing other methods, including Treuenfels's, I simply could not get them to run fast enough to meet my minimum requirements.
For efficient flood filling, using solid colors, an occasional revisit of a single pixel is outweighed by the overall speed. Eliminating all revisits is only required if you need to flood fill an image with a pattern. Since pattern revisits can lead to an infinite loop of pushing and popping the same segment. Although I have analyzed QuickFill many times, it was only through testing that I found all the holes.
If I where going to test Truenfels algorithm, I would insert the code I used in the demo for reading, writing and tracking visits. Then just call it from the QuickFill method, allowing it to be tested with the demo application. That bitmap shown in the demo is not totally random, it covers every case I ever found where a revisit occurred during testing.
It looks like its time for me to revisit this algorithm. This version was actually written specifically for this article and influenced heavily by MFC, so it can be improved.
Happy Coding,
(5th attempt to post - 1st today)
INTP
"Program testing can be used to show the presence of bugs, but never to show their absence." - Edsger Dijkstra
"I have never been lost, but I will admit to being confused for several weeks. " - Daniel Boone
|
|
|
|
|
Thank you for your very helpful answer. I started looking again at the code in Treuenfels' article, and remembered something I'd noticed before but forgotten. The routine that seems to be the key difference between his method and the usual method, "removeoverlap," doesn't make sense to me. From the way many of the dashes in the listing are shown as two dashes, I assume it was converted using OCR, and wonder if there was some error in the conversion.
In any case, even if the particular implementation doesn't work, I'm fairly convinced that it's possible to avoid revisiting filled pixels, and hope to figure out exactly how. My motive is partly aesthetic -- I just think I'd be neat -- but also practical. I have a program that uses a flood fill to count the number of connected pixels with certain properties, and it annoys me to have to do an extra fill to clear 'visited' flags I set in the counting fill.
I'm sure I'll take advantage of your excellent test cases to test any fill method I write. I'll also write a Code Project article, assuming the method's useful enough to be worth sharing.
|
|
|
|
|
Flood fill programmers:
I've updated the paper on my website to include a brief summary of the stack-checking algorithm required to eliminate all revisits. The paper, at http://www.crbond.com also refers to a companion paper which describes the stack checking in further detail. Because the project has taken on aspects of a PhD dissertation, I'm carefully rewriting the description of the required logic so it as as correct as possible.
I apologize for posting here before I had completed the papers, but I didn't expect the magnitude of the text to require so many graphics.
I'll post again when I finally post the companion paper.
|
|
|
|
|
I have a caution: The stack can actually get fairly large, and checking it for overlaps can add substantial overhead. I'm pretty sure that for regions without holes, neither your algorithm without the stack check nor a well-written implementation of the standard scanline fill algorithm revisits already filled pixels. That means for such regions, any overhead to test for overlaps slows down the fill relative to the standard fill.
Let me give an example. Consider the following 10 pixel long, two-line pattern, where Xs represent nonfillable pixels and Os represent fillable pixels:
oooooooxxxoooooooxxxoooooooxxxoooooooxxx
ooxxxoooooooxxxoooooooxxxoooooooxxxooooo
oooooooxxxoooooooxxxoooooooxxxoooooooxxx
ooxxxoooooooxxxoooooooxxxoooooooxxxooooo
oooooooxxxoooooooxxxoooooooxxxoooooooxxx
ooxxxoooooooxxxoooooooxxxoooooooxxxooooo
It turns out that for your method of filling, the maximum combined stack depth when filling this pattern is about equal to one-seventh the number of pixels. For instance:
50 x 50: 352
100 x 100: 1405
400 x 500: 28823
Obviously checking over 28 thousand intervals for intersection with a filled span will have a negative effect on performance. While this example may seem rather contrived, something like it could occur, and even relatively tame examples can produce a stack depth of over a hundred.
BTW, I think there's a small error in your description. I believe the line,
7) if rnew < R-1 push_up(rnew, R, y-1)
should be,
7) if rnew < R-1 push_up(rnew+2, R, y-1).
The pixels at rnew and rnew+1 have already been tested, so they needn't be tested again.
For anyone who wishes to experiment with the algorithm (minus the stack overlap tests), I'll provide my implementation in C#. Please forgive any weakness in the coding style; I wrote it rather quickly, with no great effort at elegance or efficiency. My version is structured slightly differently than the description, but I believe it's functionally the same. The Fill4 routine is passed a delegate function that tests the pixel to see if it needs to be filled, fills it if it does, and returns a boolean that's true if the pixel was filled, and false otherwise. Obviously this sacrifices efficiency for generality.
class FloodFill
{
private int xMin, yMin, xMax, yMax;
TestAndModifyPixel testAndModifyPixel;
public delegate bool TestAndModifyPixel(int x, int y);
public delegate bool TestPixel(int x, int y);
public delegate void ModifyPixel(int x, int y);
public FloodFill()
{
DeallocateMemory();
}
private struct Statistics
{
public int ShadowCount;
public void Clear()
{
ShadowCount = 0;
}
public void IncrementShadowCount()
{
ShadowCount++;
}
}
Statistics Stats = new Statistics();
private bool inUse = false;
public bool InUse
{
get { return inUse; }
private set { inUse = value; }
}
public void SetRange(int XMin, int YMin, int XMax, int YMax)
{
xMin = XMin; yMin = YMin;
xMax = XMax; yMax = YMax;
int ySize = yMax - yMin + 1;
}
private class Shadow
{
public int left, right;
public int y;
public Shadow next, previous;
public Shadow(int myLeft, int myRight, int myY)
{
left = myLeft;
right = myRight;
y = myY;
next = previous = null;
}
public Shadow(int myLeft, int myRight, int myY, Shadow myNext)
{
left = myLeft;
right = myRight;
y = myY;
next = myNext;
previous = null;
}
}
Shadow upShadowsHead;
Shadow upShadows;
Shadow downShadowsHead;
Shadow downShadows;
public void DeallocateMemory()
{
upShadowsHead = new Shadow(0, 0, 0, null);
upShadows = upShadowsHead;
downShadowsHead = new Shadow(0, 0, 0, null);
downShadows = downShadowsHead;
Stats.Clear();
}
public int GetAllocationCount(int which)
{
switch (which)
{
case 0:
return Stats.ShadowCount;
default:
return 0;
}
}
public int ShadowCount
{
get { return Stats.ShadowCount; }
}
int upStackSize = 0;
int downStackSize = 0;
void PushUpShadow(int left, int right, int y)
{
if ((upShadows = upShadows.previous) == null)
{
Stats.IncrementShadowCount();
upShadows = new Shadow(left, right, y, upShadowsHead);
upShadowsHead.previous = upShadows;
upShadowsHead = upShadows;
}
else
{
upShadows.left = left;
upShadows.right = right;
upShadows.y = y;
}
upStackSize++;
}
void PopUpShadow(out int left, out int right, out int y)
{
left = upShadows.left;
right = upShadows.right;
y = upShadows.y;
upShadows = upShadows.next;
upStackSize--;
}
void PushDownShadow(int left, int right, int y)
{
if ((downShadows = downShadows.previous) == null)
{
Stats.IncrementShadowCount();
downShadows = new Shadow(left, right, y, downShadowsHead);
downShadowsHead.previous = downShadows;
downShadowsHead = downShadows;
}
else
{
downShadows.left = left;
downShadows.right = right;
downShadows.y = y;
}
downStackSize++;
}
void PopDownShadow(out int left, out int right, out int y)
{
left = downShadows.left;
right = downShadows.right;
y = downShadows.y;
downShadows = downShadows.next;
downStackSize--;
}
public void Fill4(int seedX, int seedY, TestAndModifyPixel argTestAndModifyPixel)
{
if ((seedX < xMin) || (seedY < yMin) ||
(seedX > xMax) || (seedY > yMax))
return;
InUse = true;
testAndModifyPixel = argTestAndModifyPixel;
if (!LineFill(seedX, seedX, seedY))
{
inUse = false;
return;
}
PushUpShadow(leftNew, rightNew, seedY + 1);
PushDownShadow(leftNew, rightNew, seedY - 1);
while (true)
{
if (upStackSize <= downStackSize)
{
if (downStackSize == 0)
break;
ScanDown();
}
else
{
ScanUp();
}
}
InUse = false;
}
void ScanUp()
{
int left, right, y;
PopUpShadow(out left, out right, out y);
while ((y <= yMax) && LineFill(left, right, y))
{
if (leftNew < left - 1)
PushDownShadow(leftNew, left - 2, y - 1);
if (rightNew > right + 1)
PushDownShadow(right + 2, rightNew, y - 1);
else if (rightNew < right - 1)
PushUpShadow(rightNew + 2, right, y);
left = leftNew;
right = rightNew;
y++;
}
}
void ScanDown()
{
int left, right, y;
PopDownShadow(out left, out right, out y);
while ((y >= yMin) && LineFill(left, right, y))
{
if (leftNew < left - 1)
PushUpShadow(leftNew, left - 2, y + 1);
if (rightNew > right + 1)
PushUpShadow(right + 2, rightNew, y + 1);
else if (rightNew < right - 1)
PushDownShadow(rightNew + 2, right, y);
left = leftNew;
right = rightNew;
y--;
}
}
int leftNew, rightNew;
bool LineFill(int left, int right, int y)
{
int x = left;
while (!testAndModifyPixel(x, y))
{
if (++x > right)
return false;
}
if (x == left)
{
while ((--x >= yMin) && testAndModifyPixel(x, y))
;
leftNew = x + 1;
x = left;
}
else
{
leftNew = x;
}
while ((++x <= xMax) && testAndModifyPixel(x, y))
;
rightNew = x - 1;
return true;
}
}
modified on Friday, July 29, 2011 3:20 AM
|
|
|
|
|
Think-a-Tron:
Thanks for your post. It's probably a good time to 'zoom out' and review the current state of the art (a bit).
You are correct that there are situations, maybe many, where flood-filling does not require any stack checking. Unnecessary behind-the-scenes grinding should be avoided whenever possible. For the case of block graphics on a background, a simpler method is always appropriate.
However, there are situations in which the overhead of communication with the graphics device is very costly. That's one reason for an interest in single-visit methods. It isn't for everyone, or for every situation, but when the penalty for pixel testing is high, it may have advantages. (Note the number of entries in this thread.)
Your contribution is certainly very welcome. There are too many special cases possible to exhaustively test them all and proclaim any particular fill method the best. It all depends on the properties of the playfield and the platform in use. My effort has been simply to devise a single-visit method which is provably correct for any application. If the stack overhead is too high (recall Microsoft's early fill method in their original Paint program), another method, such as yours would be far better.
By the way, your implementation of the scan-and-fill operation and the stack management is very sleek. Good coding always gets high marks, and if you ever decide to tackle the problem of assuring single visits-per-pixel for the general case, you've got a ready-made audience.
|
|
|
|
|
Member 1556069 wrote: Good coding always gets high marks, and if you ever decide to tackle the problem of assuring single visits-per-pixel for the general case, you've got a ready-made audience.
That is true.
INTP
"Program testing can be used to show the presence of bugs, but never to show their absence." - Edsger Dijkstra
"I have never been lost, but I will admit to being confused for several weeks. " - Daniel Boone
|
|
|
|
|
in the simple non-recursive scan line method
replace PUSH(y, left, x1-1, -dy); with PUSH( left, x1-1, y, -dy);
|
|
|
|
|
|
General News Suggestion Question Bug Answer Joke Praise Rant Admin
Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.
|
|