Board index » delphi » FloodFill

2005-07-27 06:14:12 AM
delphi136
Hi,
I just wrote my own FloodFill algorithm (based on earlier
discussion: "Recursion and stack overflow") that fills areas with
no recursion at all and with minimal stack usage. it is speed is
excellent compared to Microsoft Paint: I made a not so big spiral
image (256x256) and filled it with Paint (~2 secs) and my
algorithm (~0.1 sec)!
The only problem I got is that I tried to make a type to a
function (TFillFunc) but when I call a function through the
correct pointer an AV is raised. However when debugging, the
de{*word*81} can evaluate the first while condition that causes the
AV but stepping on it the AV occurs... Can somebody tell me why?
To avoid this I had to duplicate some code and put two more
conditions into the code. I'd be really happy, if they could
be removed.
Thanks,
MikKi
{------------------------------------------------------------------------------
Real fast Flood Fill method
Usage:
BMP : source and destination bitmap to be painted
X,Y : starting coordinates
Mode : specify filling mode:
fmBorder : fills area that has a border of specified color (fill color
is set to border color)
fmbackground: fills area that has a specified background color (fill color
must be different than background color)
BColor : border/background color
FillColor: fill color (ignored in fmBorder mode)
------------------------------------------------------------------------------}
type
PRGB24=^TRGB24;
TRGB24=packed record
B:Byte;
G:Byte;
R:Byte;
end;
TFillMode=(fmBorder, fmBackground);
EFloodFillException=class(Exception);
EColorError=class(EFloodFillException);
procedure FloodFill(BMP:TBitmap; X,Y:Integer; const Mode:TFillMode;
const BColor,FillColor:TColor);
type
TDirection=(dUp, dDown);
TStackEntry=record
Direction:TDirection;
Row :Integer;
X1,X2 :Integer;
end;
TEdge=record
X1,X2:Integer;
end;
TFillFunc=function(const X:Integer;var Point:PRGB24):TEdge;
var
Stack :array[0..16383] of TStackEntry; //special stack
StackSize:Integer; //number of elements in stack
Item :TStackEntry; //top of stack
Pixel :PRGB24; //a pixel to paint
MaxX :Integer;
MaxY :Integer;
LastFill :TEdge; //result (left and right end point) of last line fill
BCol :TRGB24; //converted border color
FCol :TRGB24; //converted fill color
Filler :TFillFunc; //pointer to line filler function - causes AV when using this (why?)
//fills a vertical line (that contains 'Point' pixel)
//stops at border color
function FillLineBorder(const X:Integer;var Point:PRGB24):TEdge;
var
OK:Boolean;
begin
OK:=False;
//fill to left
Result.X1:=X;
while (Result.X1<>-1) and not ((Point^.R=BCol.R) and
(Point^.G=BCol.G) and (Point^.B=BCol.B)) do begin
Point^:=FCol;
dec(Point);
dec(Result.X1);
OK:=True;
end;
inc(Result.X1);
if OK then begin
//only fill to right if needed
Point:=pointer(integer(Point)+3*(X-Result.X1+2));
Result.X2:=X+1;
while (Result.X2<>MaxX) and not ((Point^.R=BCol.R) and
(Point^.G=BCol.G) and (Point^.B=BCol.B)) do begin
Point^:=FCol;
inc(Point);
inc(Result.X2);
end;
dec(Result.X2);
end
else begin
//did not fill anything
Result.X2:=X;
inc(Point);
end;
end;
//fills a vertical line (that contains 'Point' pixel)
//stops at different background color
function FillLineBgcolor(const X:Integer;var Point:PRGB24):TEdge;
var
OK:Boolean;
begin
OK:=False;
//fill to left
Result.X1:=X;
while (Result.X1<>-1) and (Point^.R=BCol.R) and
(Point^.G=BCol.G) and (Point^.B=BCol.B) do begin
Point^:=FCol;
dec(Point);
dec(Result.X1);
OK:=True;
end;
inc(Result.X1);
if OK then begin
//only fill to right if needed
Point:=pointer(integer(Point)+3*(X-Result.X1+2));
Result.X2:=X+1;
while (Result.X2<>MaxX) and (Point^.R=BCol.R) and
(Point^.G=BCol.G) and (Point^.B=BCol.B) do begin
Point^:=FCol;
inc(Point);
inc(Result.X2);
end;
dec(Result.X2);
end
else begin
//did not fill anything
Result.X2:=X;
inc(Point);
end;
end;
begin
//initializations
MaxX:=BMP.Width;
MaxY:=BMP.Height;
BMP.PixelFormat:=pf24bit; //using 24 bit bitmaps for fastest & easiest access
BCol.B:=(BColor shr 16) and $FF;
BCol.G:=(BColor shr 8) and $FF;
BCol.R:=BColor and $FF;
if Mode=fmBorder then begin
FCol:=BCol;
//Filler:=@FillLineBorder; //removed because of AV
end
else begin
FCol.B:=(FillColor shr 16) and $FF;
FCol.G:=(FillColor shr 8) and $FF;
FCol.R:=FillColor and $FF;
if (FCol.B=BCol.B) and (FCol.G=BCol.G) and (FCol.R=BCol.R) then
raise EColorError.Create('FloodFill error: Border color (BColor) and '+
'fill color (FillColor)'#13#10'must be different in fmBackground mode.');
//Filler:=@FillLineBgcolor; //removed because of AV
end;
//fill start line
Pixel:=pointer(integer(BMP.ScanLine[Y])+X*3);
//LastFill:=Filler(X,Pixel); //removed because of AV
if Mode=fmBorder then
LastFill:=FillLineBorder(X,Pixel)
else
LastFill:=FillLineBgcolor(X,Pixel);
//add line to stack as a starting line that needs top be expanded upwards and
//downwards too
Stack[0].Direction:=dDown;
Stack[0].Row:=Y;
Stack[0].X1:=LastFill.X1;
Stack[0].X2:=LastFill.X2;
Stack[1].Direction:=dUp;
Stack[1].Row:=Y;
Stack[1].X1:=LastFill.X1;
Stack[1].X2:=LastFill.X2;
StackSize:=2;
//start flood fill
while StackSize<>0 do begin
//pick last item from stack
dec(StackSize);
Item:=Stack[StackSize];
//process stack item
case Item.Direction of
dUp: Y:=Item.Row-1;
dDown:Y:=Item.Row+1;
end;
if (Y=-1) or (Y=MaxY) then continue; //reached top or bottom of image
//try to fill next line (in specified direction)
X:=Item.X1;
Pixel:=pointer(integer(BMP.ScanLine[Y])+3*X);
while X<=Item.X2 do begin
//next 3 lines removed because of AV
//LastFill:=Filler(X,Pixel);
//while (LastFill.X1>LastFill.X2) and (LastFill.X1<=Item.X2) do
// LastFill:=Filler(LastFill.X1,Pixel);
//if above 3 lines uncomented comment (remove) next 10 lines
if Mode=fmBorder then begin
LastFill:=FillLineBorder(X,Pixel);
while (LastFill.X1>LastFill.X2) and (LastFill.X1<=Item.X2) do
LastFill:=FillLineBorder(LastFill.X1,Pixel);
end
else begin
LastFill:=FillLineBgcolor(X,Pixel);
while (LastFill.X1>LastFill.X2) and (LastFill.X1<=Item.X2) do
LastFill:=FillLineBgcolor(LastFill.X1,Pixel);
end;
X:=LastFill.X2+1;
if LastFill.X1<=Item.X2 then begin
//could fill something ->add to stack
Stack[StackSize].Direction:=Item.Direction;
Stack[StackSize].Row:=Y;
Stack[StackSize].X1:=LastFill.X1;
Stack[StackSize].X2:=LastFill.X2;
inc(StackSize);
//check if we must fill in opposite direction too
if LastFill.X1<Item.X1-1 then begin
//expanded on the left hand size
Stack[StackSize].Direction:=TDirection(1-ord(Item.Direction));
Stack[StackSize].Row:=Y;
Stack[StackSize].X1:=LastFill.X1;
Stack[StackSize].X2:=Item.X1-1;
inc(StackSize);
end;
if LastFill.X2>Item.X2+1 then begin
//expanded on the right hand size
Stack[StackSize].Direction:=TDirection(1-ord(Item.Direction));
Stack[StackSize].Row:=Y;
Stack[StackSize].X1:=Item.X2+1;
Stack[StackSize].X2:=LastFill.X2;
inc(StackSize);
end;
end;
end;
end;
end;
 

I added a tick counter to my test program and run it: it used 16 milliseconds to paint that bitmap (not 0.1 sec!). I am attaching this bitmap to b.p.attachments.
Regards,
MikKi
 

newsgroup...
 

"Miklós Kiss" wrote
--JohnH
 

a place where NNTP is forbidded by the proxy. Until I am not at
home I will be unable to attach the bitmap.
MikKi
 

----- Original Message -----
From: "Miklós Kiss" <XXXX@XXXXX.COM>
Newsgroups: borland.public.delphi.graphics
Sent: Wednesday, July 27, 2005 12:14 AM
Subject: FloodFill
If you change the lines
//Filler:=@FillLineBorder; //removed because of AV
//Filler:=@FillLineBgcolor; //removed because of AV
to
Filler:=FillLineBorder; //removed because of AV
Filler:=FillLineBgcolor; //removed because of AV
(which is the correct syntax) , the compiler will give a compile error
because of this.
So make the function global and use the above syntax.
--
Kees Willem
 

Regards,
MikKi
 

Hi MikKi,
I have studied many knowledge for your post. Thank you very much!
Best regards.
Xiaoguang
"Miklós Kiss" <XXXX@XXXXX.COM>writes
---

Hi MikKi,
I have studied many knowledge from your post. Thank you very much!
Best regards.
Xiaoguang
"Ma Xiaoguang" <XXXX@XXXXX.COM>writes