GR32 (TBitmap32) 에서 Flood Fill

2010/11/15 - [PROG.] - GR32 (TBitmap32) 에서 Gradient Fill 에 이어서 Flood Fill 을 구현해 봅니다.

마찬가지로 GDI 함수로는 알파값이 누락 되기 때문에... 

1) 4 방향 FloodFill

procedure JnFloodFill1(BMP: TBitmap32; const X, Y: Integer; const AColor: TColor32);
var
  C: TColor32;
begin
  C := BMP.Pixel[X,Y];

  BMP.Pixel[X,Y] := AColor;

  if BMP.Pixel[X - 1, Y] = C then JnFloodFill1(BMP, X - 1, Y, AColor);
  if BMP.Pixel[X + 1, Y] = C then JnFloodFill1(BMP, X + 1, Y, AColor);
  if BMP.Pixel[X, Y - 1] = C then JnFloodFill1(BMP, X, Y - 1, AColor);
  if BMP.Pixel[X, Y + 1] = C then JnFloodFill1(BMP, X, Y + 1, AColor);
end;

가장 간단하게 생각할 수 있는 코드 입니다. 4방향을 탐색하면서 재귀호출을 합니다.

문제는 Stack Overflow 가 발생한다는 점.

델파이는 Tail Recursive Optimization 을 지원하지 않기 때문에 재귀호출로는 암만 고민을 하고 수정해봐야 헛일입니다. 지원한다해도 위의 코드 그대로는 안되겠죠.

델파이 프리즘은 TAILCALL 컴파일 지시자를 지원합니다.  다만 현재로서는 닷넷 기반의 델파이 프리즘은 그닥 내키지 않기 때문에 다른 방법을 써야 합니다. 이것 때문에 VC, GCC로 개발한다는것도 배보다 배꼽이 더 큰 격이죠.

2) 4 방향 FloodFill - Stack 사용

procedure JnFloodFill2(BMP: TBitmap32; const X, Y: Integer; const AColor: TColor32);
var
  C: TColor32;
  Stack: TStack;

    procedure Sub_Push(const APxPos: Integer);
    begin
      BMP.Bits[APxPos] := AColor;
      Stack.Push(Pointer(APxPos));
    end;

    procedure Sub_Check;
    var
      nPos, N: Integer;
    begin
      nPos := DWORD(Stack.Pop);

      N := nPos - 1;
      if BMP.Bits[N] = C then Sub_Push(N);

      N := nPos + 1;
      if BMP.Bits[N] = C then Sub_Push(N);
      
      N := nPos - BMP.Width;
      if BMP.Bits[N] = C then Sub_Push(N);

      N := nPos + BMP.Width;
      if BMP.Bits[N] = C then Sub_Push(N);
    end;

begin
  Stack := TStack.Create;
  try
    C := BMP.Pixel[X, Y];

    Sub_Push(X + Y * BMP.Width);
    while Stack.Count > 0 do
      Sub_Check;
  finally
    Stack.Free;
  end;
end;

재귀 호출을 없애고 TStack 을 사용했습니다.

GoTo 문으로도 작성이 가능할까요?.... 별로 하고 싶지 않습니다...;;

여기서는 속도에 문제가 좀 있습니다.

TStack 은 사실상 TList 이고, 이 놈은 매번 메모리를 늘였다 줄였다 하거든요

3) 4 방향 FloodFill - Array 사용

procedure JnFloodFill3(BMP: TBitmap32; const X, Y: Integer; const AColor: TColor32);
var
  C: TColor32;
  Stack: PIntegerArray;
  Index: Integer;

    procedure Sub_Push(const APxPos: Integer);
    begin
      BMP.Bits[APxPos] := AColor;
      Inc(Index);
      Stack[Index] := APxPos;
    end;

    procedure Sub_Check;
    var
      nPos, N: Integer;
    begin
      nPos := Stack[Index];
      Dec(Index);

      N := nPos - 1;
      if BMP.Bits[N] = C then Sub_Push(N);
      N := nPos + 1;
      if BMP.Bits[N] = C then Sub_Push(N);
      N := nPos - BMP.Width;
      if BMP.Bits[N] = C then Sub_Push(N);
      N := nPos + BMP.Width;
      if BMP.Bits[N] = C then Sub_Push(N);
    end;

begin
  Index := -1;
  C := BMP.Pixel[X, Y];

  GetMem(Stack, BMP.Width * BMP.Height);
  try
    Sub_Push(X + Y * BMP.Width);
    while Index > -1 do
      Sub_Check;
  finally
    FreeMem(Stack);
  end;
end

똑같은 코드를 TStack 대신 배열로 잡았습니다. 처음 한번만 넉넉하게 메모리를 잡아 줍니다.

이젠 불필요하게 메모리를 만지지 않겠죠.

이렇게 하니 속도가 조금 개선 되네요.

물론 그래봐야 재귀호출 보다는 느리니, 최적화된 재귀호출에 비해서도 느리겠죠...;

테스트 결과

1), 2), 3) 순서대로 200x200 사이즈의 BOX 내부에 FloodFill한 결과입니다.

1)번에서 스택 오버플로가 발생하지 않도록 기준점을 정중앙으로 잡았습니다.

1 ms 정도 느리지만 무시하고 그냥 씁시다......;;;

FloodFill.zip