SRL Archive - Help

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 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..

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;

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

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?

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

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

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

From: Ogre
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.

From: Nava2
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 ?

From: Wizzup?
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

From: Zyt3x
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.

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.

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

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.

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;
    }

From: 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;
    }

The version I posted uses an array as a stack.

My version cooks breakfast!

From: R0b0t1
My version cooks breakfast!

This settles it. I vote for R0b0t1's version.

Sorry Nava2 :( <3

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.

From: 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.

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. :)

From: Nava2
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.