A FloodFill function

[Ogre]

So I'm trying to make a flood fill function with a tolerance that is "progressive" - meaning that it doesn't relate the target color to the first color, but to the last color it was at.

Here is a comparison (http://i720.photobucket.com/albums/ww209/NoImNotOgre1/floodcomp.jpg) of normal to progressive.

The only real difference in the code is very small


procedure FloodFillProg(SPoint: TPoint; Col, Tol: Integer);
var
thisCol: Integer;
begin
try
thisCol := GetColor(SPoint.x, SPoint.y);
if (SimilarColors(thisCol, Col, Tol)) then
begin
FastSetPixel(bmap, SPoint.x, SPoint.y, clYellow);

if (FastGetPixel(bmap, SPoint.x - 1, SPoint.y) = 0) then
FloodFillProg(Point(SPoint.x - 1, SPoint.y), thisCol, Tol); //thisCol instead of Col

if (FastGetPixel(bmap, SPoint.x + 1, SPoint.y) = 0) then
FloodFillProg(Point(SPoint.x + 1, SPoint.y), thisCol, Tol); //thisCol instead of Col

if (FastGetPixel(bmap, SPoint.x, SPoint.y - 1) = 0) then
FloodFillProg(Point(SPoint.x, SPoint.y - 1), thisCol, Tol); //thisCol instead of Col

if (FastGetPixel(bmap, SPoint.x, SPoint.y + 1) = 0) then
FloodFillProg(Point(SPoint.x, SPoint.y + 1), thisCol, Tol); //thisCol instead of Col
end else
FastSetPixel(bmap, 0, 0, 1);
except
FastSetPixel(bmap, 0, 0, 1);
end;
end;

but it seems to make a good difference.

Anyway, the problem is the speed. It's not nearly fast enough to actually apply it. Nava2 suggested using TMufasaBitmaps to speed it up, and I did, but it didn't seem to help much (am I doing this wrong? :S)

procedure FloodFillProgMufasa(SPoint: TPoint; Col, Tol: Integer);
var
thisCol: Integer;
begin
try
thisCol := Sbmap.FastGetPixel(SPoint.x, SPoint.y);
if (SimilarColors(thisCol, Col, Tol)) then
begin
Tbmap.FastSetPixel(SPoint.x, SPoint.y, thisCol);

if (Tbmap.FastGetPixel(SPoint.x - 1, SPoint.y) = 0) then
FloodFillProgMufasa(Point(SPoint.x - 1, SPoint.y), thisCol, Tol);

if (Tbmap.FastGetPixel(SPoint.x + 1, SPoint.y) = 0) then
FloodFillProgMufasa(Point(SPoint.x + 1, SPoint.y), thisCol, Tol);

if (Tbmap.FastGetPixel(SPoint.x, SPoint.y - 1) = 0) then
FloodFillProgMufasa(Point(SPoint.x, SPoint.y - 1), thisCol, Tol);

if (Tbmap.FastGetPixel(SPoint.x, SPoint.y + 1) = 0) then
FloodFillProgMufasa(Point(SPoint.x, SPoint.y + 1), thisCol, Tol);
end else
Tbmap.FastSetPixel(SPoint.x, SPoint.y, 1);
except
Tbmap.FastSetPixel(SPoint.x, SPoint.y, 1);
end;
end;
where Sbmap and Tbmap are TMufasaBitmap types and Sbmap is a copy of the client
but that's not much faster at all, sometimes it's even slower?

I think a scanline method would have better efficiency but I don't know how you'd make it "progressive"? (maybe I don't understand it right)

Would the only way to speed this up be to make it a plugin? I'm reluctant to do this just because I don't know how :p, the conversion between bitmap types might be hard?, and I don't people to have to download a plugin to use my script.

Edit: how can I get rid of all the extra newlines in the code blocks? I've tried Simba, Scar, and highlight tags..

[Nava2]

procedure FloodFillProgIter(img, progress: TMufasaBitmap; SPoint: TPoint; Col, Tol: Integer);
var
thisCol, index: Integer;
begin
try
index := SPoint.y * img.width + sPoint.x;
thisCol := longword(img.FData[index]); // this may be wrong..
if (SimilarColors(thisCol, Col, Tol)) then
begin
progress.FData[index] := thisCol;

if (progress.FData[index - 1] = 0) then
FloodFillProgIter(img, progress, Point(SPoint.x - 1, SPoint.y), thisCol, Tol);

if (progress.FData[index + 1] = 0) then
FloodFillProgIter(img, progress, Point(SPoint.x + 1, SPoint.y), thisCol, Tol);

if (progress.FData[index - img.width] = 0) then
FloodFillProgIter(img, progress, Point(SPoint.x, SPoint.y - 1), thisCol, Tol);

if (progress.FData[index + img.width] = 0) then
FloodFillProgIter(img, progress, Point(SPoint.x, SPoint.y + 1), thisCol, Tol);
end else
progress.FData[index] := 1;
except
progress.FData[index] := 1;
end;
end;

procedure FloodFillProg(p: TPoint; c, tol: Integer);
var
img, prog: TMufasaBitmap;
begin
Freeze(); // may not speed anything up
img := TMufasaBitmap.create();
img.copyClient() // needs params
prog := TMufasaBitmap.create();
prog.MAKEBLACK; // fast draw clear?

FloodFillProgIter(img, progress, p, c, tol);
Unfreeze();
end;

[Ogre]

Thanks, I didn't realize you could access the data directly like that. I'll test it when I can.

[Ogre]

Okay, so I haven't implemented the faster way of checking the TMufasaBitmap, because I don't know how to.

but I did this in the mean time, hoping it would speed it up because I thought there should be half the calls to a bitmap this way, but it's not faster :<

procedure FloodFillMufasa2(SPoint: TPoint; Col, Tol, thisCol: Integer); //on the first call thisCol should = Col
var
l, nextCol: Integer;
begin
try
//usually there is a necessary FastGetPixel here, but not now!
if (SimilarColors(thisCol, Col, Tol)) then
begin
source.FastSetPixel(SPoint.x, SPoint.y, 1);

nextCol := source.FastGetPixel(SPoint.x - 1, SPoint.y);
if (nextCol > 1) then
FloodFillMufasa2(Point(SPoint.x - 1, SPoint.y), thisCol, Tol, nextCol);

nextCol := source.FastGetPixel(SPoint.x + 1, SPoint.y);
if (nextCol > 1) then
FloodFillMufasa2(Point(SPoint.x + 1, SPoint.y), thisCol, Tol, nextCol);

nextCol := source.FastGetPixel(SPoint.x, SPoint.y - 1);
if (nextCol > 1) then
FloodFillMufasa2(Point(SPoint.x, SPoint.y - 1), thisCol, Tol, nextCol);

nextCol := source.FastGetPixel(SPoint.x, SPoint.y + 1);
if (nextCol > 1) then
FloodFillMufasa2(Point(SPoint.x, SPoint.y + 1), thisCol, Tol, nextCol);

end else
fill.FastSetPixel(SPoint.x, SPoint.y, 0);
except
fill.FastSetPixel(SPoint.x, SPoint.y, 0);
end;
end;

should be faster than

procedure FloodFillMufasa(SPoint: TPoint; Col, Tol: Integer);
var
thisCol: Integer;
begin
try
thisCol := source.FastGetPixel(SPoint.x, SPoint.y);
if (SimilarColors(thisCol, Col, Tol)) then
begin
fill.FastSetPixel(SPoint.x, SPoint.y, thisCol);

if (fill.FastGetPixel(SPoint.x - 1, SPoint.y) = 0) then
FloodFillMufasa(Point(SPoint.x - 1, SPoint.y), thisCol, Tol);

if (fill.FastGetPixel(SPoint.x + 1, SPoint.y) = 0) then
FloodFillMufasa(Point(SPoint.x + 1, SPoint.y), thisCol, Tol);

if (fill.FastGetPixel(SPoint.x, SPoint.y - 1) = 0) then
FloodFillMufasa(Point(SPoint.x, SPoint.y - 1), thisCol, Tol);

if (fill.FastGetPixel(SPoint.x, SPoint.y + 1) = 0) then
FloodFillMufasa(Point(SPoint.x, SPoint.y + 1), thisCol, Tol);
end else
fill.FastSetPixel(SPoint.x, SPoint.y, 1);
except
fill.FastSetPixel(SPoint.x, SPoint.y, 1);
end;
end;

but it seems to actually be slower. can anyone see why?

[Zyt3x]

Putting it in a plugin would also make it a bit faster :)

[Nava2]

For sure, my method works in a plugin. Perhaps this could be included into the TMufasaBitmap object? Thus compiled into the MML.

[Ogre]

Yeah, I know it would be faster in a plugin. I'm just trying to get the algorithm to its most efficient, and

Would the only way to speed this up be to make it a plugin? I'm reluctant to do this just because I don't know how :p, the conversion between bitmap types might be hard?, and I don't people to have to download a plugin to use my script.

[Wizzup?]

For sure, my method works in a plugin. Perhaps this could be included into the TMufasaBitmap object? Thus compiled into the MML.

http://docs.wizzup.org/simba/scriptref/bitmaps.html#floodfillbitmap ?

[Zyt3x]

http://docs.wizzup.org/simba/scriptref/bitmaps.html#floodfillbitmap ?https://github.com/MerlijnWajer/Simba/blob/master/Units/MMLCore/bitmaps.pas#L535

The one Ogre made differs from that function because his does only floodfill in 4 directions (left, right, up, down) instead of 8

[Nava2]

https://github.com/MerlijnWajer/Simba/blob/master/Units/MMLCore/bitmaps.pas search "TMufasaBitmap.FloodFill"

The one Ogre made differs from that function because his does only floodfill in 4 directions (left, right, up, down) instead of 8

Thing is, its the tolerance that makes the difference. I think ogre's method should be implemented through the already optimized method of Raymond.

[Ogre]

Yeah, whether it's 4 directions or 8 doesn't really matter, I guess. I just thought that it was the norm not to jump diagonally in a floodfill function, but for it to be of any use it's going to need to be in a plugin.

[Zyt3x]

Actually... I'd like there to be (at least) two types of FloodFill in Simba... I had to make my own FloodFill function too because Simba's 8-direction FloodFill wasn't what I needed.

It isn't hard to make it work with as many directions as the user inputs actually.. I might make it later tonight

[Nava2]

function TMufasaBitmap.FloodFillTolPts(const startPT: TPoint; const searchCol:
TColor; Tol: Integer): TPointArray;
var
stack: array of record x, yInteger; col: LongWord; end;
SIndex;
currX, currY: Integer;
search: LongWord;
progress: array of TColour;
resLength: Integer;
procedure addToStack(x, y: Integer; colour: LongWord);
var
ind: Integer;
begin
ind := y*w+x;
if (not (progress[ind] = clWhite)) and SimilarColors(LongWord(FData[ind]), colour) then
begin
progress[ind] := clWhite;
stack[sIndex].x := x;
stack[sIndex].y := y;
stack[sIndex].col := colour;
inc(sIndex);
result[resLength] := Point(x,y);
inc(resLength);
end;
end;
begin
ValidatePoint(StartPT.x,StartPT.y);
Search := LongWord(RGBToBGR(SearchCol));
SetAlphaValue(0);
if LongWord(FData[StartPT.y * w + StartPT.x]) <> Search then //Only add items to the stack that are the searchcol.
Exit;
SetLength(Stack,w * h);
SetLength(Result, w*h);
SIndex := 0;
AddToStack(StartPT.x,StartPT.y, searchCol);
while (SIndex >= 0) do
begin;
currX := stack[sIndex].x;
currY := stack[sIndex].y;
search := stack[sIndex].col;
if (currX > 0) then AddToStack(currX - 1, currY, search);
if (currY > 0) then AddToStack(currX, currY - 1, search);
if (currX + 1 < w) then AddToStack(currX + 1, currY, search);
if (currY + 1 < h) then AddToStack(currX, currY + 1, search);
dec(sIndex);
end;

SetLength(Result, resLength);
end;

8 directions is a waste of time. Four is plenty and removes a lot of unnecessary iterations.

[R0b0t1]

Bitch needs to use a stack-based algorithm (yes I know it is Java).



/**
* Flood-fills a contiguous area of an image of color c, starting at Point
* p with color r.
*
* @param img image data array
* @param w width
* @param h height
* @param c color
* @param r replacement color
* @param p point
* @return bounding rectangle of the area filled
*/
public static Rectangle floodFill(int[] img, int w, int h, int c, int r, Point p)
{
if(p.x < 0 || p.y < 0 || p.x > w || p.y > h) return null;
if(c == r || img[(p.y * w) + p.x] != c) return null;

Rectangle ret = new Rectangle(p.x, p.y, 0, 0);

Stack<Point> s = new Stack<Point>();
s.push(p);

Point t;
int y1;
boolean spanLeft, spanRight;

while(!s.isEmpty())
{
t = s.pop();

y1 = t.y;
while(y1 >= 0 && img[(y1 * w) + t.x] == c) y1--;
y1++;

spanLeft = spanRight = false;

while(y1 < h && img[(y1 * w) + t.x] == c)
{
img[(y1 * w) + t.x] = r;

// Push the upper-left corner up if necessary.
// We might need to expand the height, as it is relative.
if(y1 < ret.y)
{
ret.height += y1 - ret.y;
ret.y = y1;
} // Expand the height if necessary.
else if(y1 > ret.y + ret.height)
ret.height = y1 - ret.y;

if(!spanLeft && t.x > 0 && img[(y1 * w) + t.x - 1] == c)
{
s.push(new Point(t.x - 1, y1));

// Push the upper-left corner left if necessary.
// We might need to expand the width, as it is relative.
if(t.x < ret.x)
{
ret.width += ret.x - t.x;
ret.x = t.x;
}

spanLeft = true;
} else if(spanLeft && t.x > 0 && img[(y1 * w) + t.x - 1] != c)
{
spanLeft = false;
}

if(!spanRight && t.x < w - 1 && img[(y1 * w) + t.x + 1] == c)
{
s.push(new Point(t.x + 1, y1));

// Expand height if necessary.
if(t.x > ret.x + ret.width)
ret.width = t.x - ret.x;

spanRight = true;
} else if(spanRight && t.x < w - 1 && img[(y1 * w) + t.x + 1] != c)
{
spanRight = false;
}

y1++;
}
}

ret.width++;
return ret;
}

[Nava2]

Bitch needs to use a stack-based algorithm (yes I know it is Java).



/**
* Flood-fills a contiguous area of an image of color c, starting at Point
* p with color r.
*
* @param img image data array
* @param w width
* @param h height
* @param c color
* @param r replacement color
* @param p point
* @return bounding rectangle of the area filled
*/
public static Rectangle floodFill(int[] img, int w, int h, int c, int r, Point p)
{
if(p.x < 0 || p.y < 0 || p.x > w || p.y > h) return null;
if(c == r || img[(p.y * w) + p.x] != c) return null;

Rectangle ret = new Rectangle(p.x, p.y, 0, 0);

Stack<Point> s = new Stack<Point>();
s.push(p);

Point t;
int y1;
boolean spanLeft, spanRight;

while(!s.isEmpty())
{
t = s.pop();

y1 = t.y;
while(y1 >= 0 && img[(y1 * w) + t.x] == c) y1--;
y1++;

spanLeft = spanRight = false;

while(y1 < h && img[(y1 * w) + t.x] == c)
{
img[(y1 * w) + t.x] = r;

// Push the upper-left corner up if necessary.
// We might need to expand the height, as it is relative.
if(y1 < ret.y)
{
ret.height += y1 - ret.y;
ret.y = y1;
} // Expand the height if necessary.
else if(y1 > ret.y + ret.height)
ret.height = y1 - ret.y;

if(!spanLeft && t.x > 0 && img[(y1 * w) + t.x - 1] == c)
{
s.push(new Point(t.x - 1, y1));

// Push the upper-left corner left if necessary.
// We might need to expand the width, as it is relative.
if(t.x < ret.x)
{
ret.width += ret.x - t.x;
ret.x = t.x;
}

spanLeft = true;
} else if(spanLeft && t.x > 0 && img[(y1 * w) + t.x - 1] != c)
{
spanLeft = false;
}

if(!spanRight && t.x < w - 1 && img[(y1 * w) + t.x + 1] == c)
{
s.push(new Point(t.x + 1, y1));

// Expand height if necessary.
if(t.x > ret.x + ret.width)
ret.width = t.x - ret.x;

spanRight = true;
} else if(spanRight && t.x < w - 1 && img[(y1 * w) + t.x + 1] != c)
{
spanRight = false;
}

y1++;
}
}

ret.width++;
return ret;
}



The version I posted uses an array as a stack.

[R0b0t1]

My version cooks breakfast!

[Zyt3x]

My version cooks breakfast!This settles it. I vote for R0b0t1's version.

Sorry Nava2 :( <3

[Wizzup?]

If you could make a pull request? Please make it a new function, so we can keep the old one as well. I suppose sometimes more directions are useful.

[Nava2]

If you could make a pull request? Please make it a new function, so we can keep the old one as well. I suppose sometimes more directions are useful.

Not really, you are actually doubling over points if you have more directions. Think about if you iterate in all eight, then you get the points, but then when you move to a corner for example, you have to *re-iterate* over the three that were in the previous box.

8 Directions is great for some, but for this is *much* wasted computations.

I can submit a Pull Request in a few days, I'm still in exams.. 4/7 done, tomorrow it will by 5/7. :)

[Wizzup?]

Not really, you are actually doubling over points if you have more directions. Think about if you iterate in all eight, then you get the points, but then when you move to a corner for example, you have to *re-iterate* over the three that were in the previous box.

8 Directions is great for some, but for this is *much* wasted computations.

I can submit a Pull Request in a few days, I'm still in exams.. 4/7 done, tomorrow it will by 5/7. :)

Like you said, great for some. That's why the one with fewer directions should be a different function.