jon lennart berg

Hi guys!

Solved that bloody floodfill thing a lot of us have been bitching about for
a while.
The routine i came up with even fills around corners, where all those other
versions fails
Should also make it very easy to create magic wand routines.
Very slow using pixels[] array, but should run like the wind with scanlines.

Give me some feedback on this, speed etc.

There, that should fill my karma for this week..

Kind regards

Jon Lennart Aasenden,
Norway


Procedure JLAAFloodFill(ABitmap:TBitmap;APos:TPoint;AColor:T Color);
{ JLAA Floodfill.
Bacteria inspired floodfill routine (populate by 4).


- ** Works for both Delphi & Kylix }
Type
TJLAAPixelSlot = Record
Position: TPoint;
Color: TColor;
Valid: Boolean;
End;

PJLAAPixelElement = ^TJLAAPixelElement;
TJLAAPixelElement = Record
Origo: TPoint;
Slots: Array[0..3] of TJLAAPixelSlot;
Dead: Boolean;
End;

var
FGrowColor: TColor;
FPopulation: TList;
FItem: PJLAAPixelElement;
x,cnt: Integer;

Function PointElement(ax,ay:Integer):TColor;
Begin
{$IFDEF LINUX}
With PJLAARGBAArray(ABitmap.Scanline[ay])[ax] do
Result := (r or (g shl 8) or (b shl 16));
{$ENDIF}
{$IFDEF MSWINDOWS}
result:=ABitmap.Canvas.Pixels[ax,ay];
{$ENDIF}
End;

Procedure PlotElement(ax,ay:Integer);
Begin
{$IFDEF LINUX}
With PJLAARGBAArray(ABitmap.Scanline[ay])[ax] do
Begin
r:=Byte(AColor);
g:=Byte(AColor shr 8);
b:=Byte(AColor shr 16);
end;
{$ENDIF}
{$IFDEF MSWINDOWS}
ABitmap.Canvas.Pixels[ax,ay]:=AColor;
{$ENDIF}
End;

Procedure ValidateElement(var Item:PJLAAPixelElement);
var
FEntry: Integer;
FCount: Integer;
sx,sy: Integer;
Begin
{ I avoid using point() since that is slower.
The code below will be automatically optimized by
the delphi compiler }

Item^.Slots[0].Position.x:=Item^.Origo.x;
Item^.Slots[0].Position.y:=Item^.Origo.y-1;
Item^.Slots[0].Valid:=False;

Item^.Slots[1].Position.x:=Item^.Origo.x+1;
Item^.Slots[1].Position.y:=Item^.Origo.y;
Item^.Slots[1].Valid:=False;

Item^.Slots[2].Position.x:=Item^.Origo.x;
Item^.Slots[2].Position.y:=Item^.Origo.y+1;
Item^.Slots[2].Valid:=False;

Item^.Slots[3].Position.x:=Item^.Origo.x-1;
Item^.Slots[3].Position.y:=Item^.Origo.y;
Item^.Slots[3].Valid:=False;

{ Validate that pixels have grow-color and is
not outside the pixmap surface }
FCount:=0;
for FEntry:=0 to 3 do
Begin
{ Get Entry position }
sx:=Item^.Slots[FEntry].Position.x;
sy:=Item^.Slots[FEntry].Position.y;

{ valid position? }
if (sx<0) or (sy<0)
or (sx>=ABitmap.Width)
or (sy>=ABitmap.Height) then
Continue;

{ Get position color value }
Item^.Slots[FEntry].Color:=PointElement(sx,sy);

{ growth color? }
If Item^.Slots[FEntry].Color=FGrowColor then
Begin
Item^.Slots[FEntry].Valid:=True;
PlotElement(sx,sy);
inc(FCount);
end;

End;
{ No valid movements? This flower died }
Item^.Dead:=(FCount=0);
End;

Procedure GrowElement(var Item:PJLAAPixelElement);
var
FElement: Integer;
FSpawn: PJLAAPixelElement;
sx, sy: Integer;
Begin
{ check that we can do this }
If Item^.Dead then
exit;

{ this element is now officially dead (but not burried) }
FItem^.Dead:=True;

for FElement:=0 to 3 do
Begin
{ not a valid growth movement? skip to next }
If not FItem^.Slots[FElement].Valid then
Continue;

{ Create a new growth pixel element
to follow in his ancestorts footsteps..}
New(FSpawn);

sx:=FItem^.Slots[FElement].Position.x;
sy:=FItem^.Slots[FElement].Position.y;

{ flush growth pixel memory }
FSpawn^.Dead:=False;
FSpawn^.Origo.X:=sx;
FSpawn^.Origo.Y:=sy;

{ Plot the first pixel }
PlotElement(sx,sy);

{ calculate element growth movements }
ValidateElement(FSpawn);

{ flower died before it blossomed?
rip it out and try to grow another way }
If FSpawn^.Dead then
Begin
Item^.Slots[FElement].Valid:=False;
Dispose(FSpawn);
Continue;
End;

{ add new element to our population }
Fpopulation.Add(FSpawn);
Item^.Slots[FElement].Valid:=False;
End;
End;

Begin
{ check that we can do this }
If (Assigned(ABitmap)=False)
or (ABitmap.Empty=True) then
exit;

{ Create floodfill population }
FPopulation:=TList.Create;

try
{ Get start position color, this is our grow color }
FGrowColor:=PointElement(Apos.x,Apos.y);

{ not a valid fill area? }
If FGrowColor=AColor then
exit;

{ Plot the first pixel }
If not (Apos.x<0) and not (Apos.y<0)
and not (Apos.x>ABitmap.width)
and not (Apos.y>ABitmap.Height) then
PlotElement(Apos.x,Apos.y) else
exit;

{ Create first growth pixel element }
New(FItem);
FItem^.Dead:=False;
FItem^.Origo.x:=Apos.x;
FItem^.Origo.Y:=Apos.y;

{ validate movements of growth }
ValidateElement(FItem);

{ Add to our population }
FPopulation.Add(FItem);

{ While the soil lives.. }
While FPopulation.Count>0 do
Begin
{ ..plants grow and die }
x:=0;
cnt:=FPopulation.Count;
While (x<cnt) do
Begin
{ Get a growth pixel }
FItem:=PJLAAPixelElement(FPopulation[x]);

{ Not dead? Grow.. grow.. green gigant }
If not FItem^.Dead then
GrowElement(FItem);

{ This element is now dead. burry it } Dispose(FItem); FPopulation.Delete(x);
if cnt>0 then
dec(cnt);
inc(x);
End;
End;
finally
{ Release population pool }
Fpopulation.free;
end;
End;