Flood Fill on 3D Image

Flood Fill merupakan teknik mengarsir yang menggunakan analogi menuangkan cat warna di satu titik yang kemudian cat tersebut akan bergerak meluas hingga merata (menutupi seluruh area yang dibatasi). cat akan meluberi daerah yang memiliki predikat sama (warna yang sama, atau bukan warna tertentu). Adapun jika digunakan predikat bukan warna tertentu maka dikenal sebagai variannya yaitu boundary fill. titik awal warna dituang dinamakan dengan titik bakar.

Pada kuliah grafika komputer, dan buku teksnya. Algoritma Floodfill dideskripsikan secara rekursif sbb

{menggunakan predikat warna sama dengan warna titik bakar}
procedure floodfill(p:point, i:image; newcolor:color);
var
   oldcolor : color;
begin
   oldcolor := i.pixel[p.x][p.y];
   i.pixel[p.x][p.y] := newcolor;
   {i.pixel[neighbor.x][neighbor.y]=oldcolor merupakan predikat sebagai syarat rekurens}
   {tetangga kiri}
   if (p.x > i.left_bound) and (i.pixel[p.x-1][p.y]=oldcolor) then floodfill(point(p.x-1, p.y), i, newcolor);
  {tetangga kanan}
  if (p.x < i.right_bound) and (i.pixel[p.x+1][p.y]=oldcolor) then floodfill(point(p.x+1, p.y), i, newcolor);
  {tetangga atas}
  if (p.y > i.top_bound) and (i.pixel[p.x][p.y-1]=oldcolor) then floodfill(point(p.x, p.y-1), i, newcolor);
  {tetangga bawah}
  if (p.y < i.bottom_bound) and (i.pixel[p.x][p.y+1]=oldcolor) then floodfill(point(p.x, p.y+1), i, newcolor);
end;

Algoritma di atas merupakan contoh generik untuk citra 2D. Untuk citra 3D algoritma di atas dapat diperluas dengan ekspresi yang sama, yang berbeda hanyalah rekursif tetangganya yang bertambah yaitu tetangga depan dan tetangga belakang.

{menggunakan predikat warna sama dengan warna titik bakar}
procedure floodfill(p:point3d, i:image; newcolor:color);
var
   oldcolor : color;
begin
   oldcolor := i.pixel[p.x][p.y][p.z];
   i.pixel[p.x][p.y][p.z] := newcolor;
   {i.pixel[neighbor.x][neighbor.y][neighbor.z]=oldcolor merupakan predikat sebagai syarat rekurens}
   {tetangga kiri}
   if (p.x > i.left_bound) and (i.pixel[p.x-1][p.y][p.z]=oldcolor) then floodfill(point(p.x-1, p.y,p.z), i, newcolor);
  {tetangga kanan}
  if (p.x < i.right_bound) and (i.pixel[p.x+1][p.y][p.z]=oldcolor) then floodfill(point(p.x+1, p.y,p.z), i, newcolor);
  {tetangga atas}
  if (p.y > i.top_bound) and (i.pixel[p.x][p.y-1][p.z]=oldcolor) then floodfill(point(p.x, p.y-1,p.z), i, newcolor);
  {tetangga bawah}
  if (p.y < i.bottom_bound) and (i.pixel[p.x][p.y+1][p.z]=oldcolor) then floodfill(point(p.x, p.y+1,p.z), i, newcolor);
  {tetangga depan}
  if (p.z > i.front_bound) and (i.pixel[p.x][p.y][p.z-1]=oldcolor) then floodfill(point(p.x, p.y,p.z-1), i, newcolor);
  {tetangga belakang}
  if (p.z < i.rear_bound) and (i.pixel[p.x][p.y][p.z+1]=oldcolor) then floodfill(point(p.x, p.y,p.z+1), i, newcolor);
end;

algoritma rekursif memang memiliki ekspresi yang sederhana namun seringkali implementasinya terganggu dengan pesan stack overflow yang diakibatkan ukuran stack di heap untuk procedure call yang terbatas. Hal ini dapat diatasi dengan mengubah algoritma di atas menjadi iteratif dan mensimulasikan stack sebagai struktur data eksternal. Apakah kedua hal tersebut sudah cukup? tentu belum, jika mekanisme mencari tetangganya sama persis dengan algoritma rekursif di atas maka justru algoritma versi iteratif lebih buruk performanya. Kita perlu mengoptimasi pencarian tetangga sehingga ukuran untuk stack dapat dikurangi.

Untuk mengurangi pengisian stack tersebut kita dapat mengubah ide dari algoritma di atas dengan cara memusatkan perhatian pada tetangga yang berada di satu sumbu. Misalkan kita perhatikan di sumbu vertikal (sumbu Y), maka kita akan mendapatkan sebuah rentang minimum-maksimum yang memiliki predikat sama. Rentang ini kemudian ditelusuri. Selama menelusuri rentang tersebut, barulah kita memperhatikan tetangga di sumbu lainnya (sumbu X). Karena kita secara konstan menelusuri rentang vertikal maka kita cukup memperhatikan perubahan di tetangga. Kita hanya perlu menyimpan ke stack, tetangga yang baru kita temukan pertama. Tetangga yang letaknya di bawah tetangga tersebut jika memiliki predikat yang sama tidak perlu disimpan karena pasti dikunjungi ketika titik tersebut diproses pertama kali secara vertikal.

Algoritma tersebut diekspresikan dalam kode berikut:

{menggunakan predikat warna sama dengan warna titik bakar}
procedure floodfill(p:point3d, i:image; newcolor:color);
var
   oldcolor : color;
   stpt : stack;// stack of point3d;
   pt : point3d;
   y1, y2, yy : integer;
   span_left, span_right, span_front, span_rear: boolean;
begin
   oldcolor := i.pixel[p.x][p.y];
   stpt.push(p.x,p.y,p.z);
   while not stpt.is_empty() do begin
      pt := stpt.pop();
      y1 := pt.y;
      while (y1 > i.top_bound) and (i.pixel[pt.x][y1-1][pt.z]=oldcolor) do dec(y1);
      y2 := pt.y;
      while (y2 < i.bottom_bound) and (i.pixel[pt.x][y1+1][pt.z]=oldcolor) do inc(y2);
      span_left := false;
      span_right := false;
      span_front := false;
      span_rear := false;
      for yy := y1 to y2 do begin
         if (pt.x > i.left_bound) then begin
            if not span_left and (i.pixel[pt.x-1][yy][pt.z]=oldcolor) then begin
               span_left := true;
               stpt.push(pt.x-1, yy, pt.z);
            end else if span_left and not (i.pixel[pt.x-1][yy][pt.z]=oldcolor) then span_left := false;
         end;
         if (pt.x < i.right_bound) then begin
            if not span_right and (i.pixel[pt.x+1][yy][pt.z]=oldcolor) then begin
               span_right := true;
               stpt.push(pt.x+1, yy, pt.z);
            end else if span_right and not (i.pixel[pt.x+1][yy][pt.z]=oldcolor) then span_right := false;
         end;
         if (pt.z > i.front_bound) then begin
            if not span_front and (i.pixel[pt.x][yy][pt.z-1]=oldcolor) then begin
               span_front := true;
               stpt.push(pt.x, yy, pt.z-1);
            end else if span_front and not (i.pixel[pt.x][yy][pt.z-1]=oldcolor) then span_front := false;
         end;
         if (pt.z < i.rear_bound) then begin
            if not span_rear and (i.pixel[pt.x][yy][pt.z+1]=oldcolor) then begin
               span_rear := true;
               stpt.push(pt.x, yy, pt.z+1);
            end else if span_rear and not (i.pixel[pt.x][yy][pt.z+1]=oldcolor) then span_rear := false;
         end;
         i.pixel[pt.x][yy][pt.z] := newcolor;
      end;
   end;
end;

One comment

  1. sella · Februari 11

    mas flood fill ni bsa kah dimasukkan ke game warna untuk penyebaran warna.a .. pake flash cs6 ?? balas ya mas

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s