Bresenham's Line Drawing Algorithm

Bresenham line algorithm merupakan algoritma yang menunjukkan pixel mana dalam sebuah gambar raster n-dimensi yang harus ditandai (diwarna) supaya membentuk mendekati garis lurus dari 2 titik. Algoritma ini digunakan untuk menggambar garis pada layar komputer dan hanya menggunakan operasi-operasi matematis bertipe data integer.  Algoritma ini dikembangkan oleh Jack E. B resenham, 1962 di IBM. Algoritma Bresenham juga dikembangkan untuk menampilkan lingkaran, biasa disebut dengan "Bresenham's circle algorithm" atau “midpoint circle algoritm”. Pada tulisan ini akan dijelaskan mengenai algoritma Bresenham untuk menggambar garis dan lingkaran beserta contoh implementasinya menggunakan bahasa pascal.

 Penjelasan Algoritma

Asumsikan y= mx + b merepresentasikan penjumlahan variabel real dari garis yang di plotkan menggunakan pixel dimana dua buah titik (x1, y1) dan (x2, y2) memiliki koordinat integer yang akan dihubungkan dengan garis. Pada gambar dibawah ini, kedua titik tersebut berada di bagian kiri bawah dan kanan atas dari grid pixel (0,0) dan (35,9).

Kita asumsikan bahwa koordinat x-pixel bertambah ke arah kanan dan koordinat y-pixel bertambah ke atas. Pada contoh ini, kita asumsikan bahwa x1<x2 dan y1<y2. Ini merupakan batasan yang diperlukan untuk mendiskripsikan pengaturan umum untuk contoh dibawah ini. Asumsi berikutnya adalah kemiringan m adalah 0 ≤ m ≤ 1. Asumsi ini menjamin bahwa kita bergerak poin demi poin dari kiri ke kanan pada grafik. Y tidak akan pernah bergerak lebih dari 1  pixel dan nilai y bertambah sebagaimana nilai x juga bertambah. Asumsi ini juga penting untuk menjelaskan gagasan dibalik algoritma bresenham ini. Kita akan menggunakan pembagian untuk Δy / Δx untuk menyatakan nilai m.

Untuk membuat alur garis yang akurat, kita melacak akumulasi kesalahan dalam variabel y. Sejak titik pertama (x1, y1), variabel Accumulated y-Error harus di inisialisasi dengan nilai 0. Bersamaan dengan pergerakan garis dari kiri ke kanan, kita akan menentukan increment y dengan 1 hanya ketika nilai akumulasi pada variabel y-error   menjadi lebih besar dari 1/2. Pada kondisi ini, kita hanya akan menghitung point pada alur dimana y-koordinat berbeda dari nilai TrueY banyak 1 pixel.

CurrentY + AccumulatedY Error = TrueY

Atau

AccumulatedY Error = trueY - CurrentY

Diketahui operasi  y = mx + c, jika nilai x bertambah 1, maka nilai y harus naik sebanyak m. Jika nilai y tidak bertambah sama sekali ketika nilai x bertambah 1, maka accumulated error pada y harus ditambahkan sebanyak m. Begitu pula jika y hanya bertambah 1 nilai tanpa menambah nilai x sama sekali, maka nilai accumulated error pada y harus berkurang sebanyak 1.

procedure Bresenham( x1, y1, x2, y2 : integer);

var       AccumulatedYError : real;

Δy, Δx : real;

CurrentX, CurrentY : integer;

FinalX : integer;

begin

AccumulatedYError := 0.0;

CurrentX := x1;

CurrentY := y1;

FinalX := x2;

Δx := ÐrealÑ x2 - x1;

Δy := ÐrealÑ y2 - y1;

repeat

Plot(CurrentX, CurrentY);

CurrentX := CurrentX + 1;

AccumulatedYError := AccumulatedYError + Δx  / Δy ;

if AccumulatedYError > 1 then

begin

CurrentY := CurrentY + 1;

AccumulatedYError := AccumulatedYError - 1.0

end

until CurrentX > FinalX

end;  

Algoritma diatas mengasumsikan bahwa variabel AccumulatedY  Error  dan Δy  dan  Δx semuanya merupakan variabel real floating point. Kita harus menghindari semua nilai decimal dan pembagian supaya algoritma berjalan dengan cepat. Jadi, gunakan variabel dan nilai integer saja.

Menuliskan operasi: AccumulatedY Error = AccumulatedY Error + Δy / Δx

Ekuivalen dengan : Δx . AccumulatedY Error = Δx . AccumulatedY Error + Δy dimana nilai pecahan dihilangkan.

Selanjutnya, kita menghindari perkalian dengan bilangan 2 dan dengan Δx setiap saat melalui perulangan dengan menulis ulang operasi diatas dengan test kondisional:

(2 . Δx . AccumulatedY Error) = (2 . Δx . AccumulatedY Error) + (2 . Δy)

Jika (2 . Δx . AccumulatedY Error) > Δx

Perlu diingat bahwa m dapat ditulis dengan m = Δy / Δx = (y2 – y1) / (x2 – x1).

Dapat diasumsikan bahwa Δy dan Δx adalah integer dimana Δy = y2 – y1 dan Δx = x2 – x1. Kita buat variabel baru yang disebut TwoDxAccumulatedY Error.

- 1/2 ≤ AccumulatedY Error ≤ ½

Berikut adalah implementasi dari algoritma bresenham.

program TESTLINE(Input,Output);

uses dos, crt, bgidriv, bgifont, graph;

var       X1,Y1,X2,Y2 : integer;

grMode : integer;

grDriver : integer;

ErrorCode : integer;

procedure PlotLine(X1,Y1,X2,Y2 : integer);

var       CurrentX, CurrentY : integer;

Xinc, Yinc : integer;

Dx, Dy : integer;

TwoDx, TwoDy : integer;

TwoDxAccumulatedError : integer;

TwoDyAccumulatedError : integer;

begin

Dx := (X2-X1);

Dy := (Y2-Y1);

TwoDx := Dx + Dx;

TwoDy := Dy + Dy;

CurrentX := X1;

CurrentY := Y1;

Xinc := 1;

Yinc := 1;

if Dx<0 then

begin

Xinc := -1; { decrement X's }

Dx := -Dx;

T          woDx := -TwoDx

end;

if Dy<0 then

begin

Yinc := -1;

Dy := -Dy;

TwoDy := -TwoDy

end;

putpixel(X1,Y1,1);

if (Dx<>0) or (Dy<>0) then

begin

if Dy<=Dx then

begin

TwoDxAccumulatedError := 0;

repeat

inc(CurrentX, Xinc);

inc(TwoDxAccumulatedError, TwoDy);

if TwoDxAccumulatedError>Dx then

begin

inc(CurrentY, Yinc);

dec(TwoDxAccumulatedError, TwoDx)

end;

putpixel(CurrentX,CurrentY,1)

until CurrentX=X2

end

else

begin

TwoDyAccumulatedError := 0;

repeat

inc(CurrentY, Yinc);

inc(TwoDyAccumulatedError, TwoDx);

if TwoDyAccumulatedError>Dy then

begin

inc(CurrentX, Xinc);

dec(TwoDyAccumulatedError, TwoDy)

end;

putpixel(CurrentX,CurrentY,1)

until CurrentY=Y2

end

end

end; 

Midpoint Circle Algorithm 

Algoritma midpoint ini merupakan pengembangan dari algoritma bresenham untuk menggambar lingkaran. Ketika menggambar lingkaran dengan menggunakan algoritma ini, kita perlu mengkalkulasi floating point setiap koordinat dimana akan menjadi proses yang lambat apabila banyak objek sekaligus. Metode ini menyajikan cara yang sederhana dalam menggambar lingkaran dengan menggunakan perkiraan dari titik tengah (midpoint) lingkaran.

Untuk setiap titik p(x,y) kita dapat menentukan titik berikutnya (perkiraan) N(x, y+1), NW(x-1,y+1) berdasarkan titik tengah M(x-1/2, y+1). Jika titik M berada didalam lingkaran, Ttik N dekat dengan lingkaran, maka dari itu titik N harus dipilih sebagai titik berikutnya. Sebaliknya, titik NW yang harus dipilih. Untuk mengkalkulasi jarak dari M dapat dihitung dengan rumus Rd = r – Rm. Jika d < 0, maka M berada diluar lingkaran. Jika Rd > 0 maka M berada di dalam lingkaran. Dari rumus x ^ 2 + y ^ 2, dapat kita ketahui bahwa Xm ^ 2 + Ym + 2 – Rm ^ 2 = Xm ^ 2 + Ym ^ 2 – (r – Rd) ^ 2 = 0. Karena titik tengah dekat dengan lingkaran, maka dapat kita abaikan jika Rd > 2. Jadi, jika D(M) > o, Rd < 0, M berada diluar lingkaran, NW yang harus dipilih jika D(M) < 0, Rd > 0, M didalam lingkaran, N harus dipilih. Berikut algoritma dalam bahasa javascript.

var drawCircle = function(ctx , x , y , r){

  var cx = r;

  var cy = 0;

  //Inisialisasi 4 titik atas, bawah, kiri, kanan

  init(ctx,x,y,r);

   

  //Kita hanya perlu mengkalkulasi 1/8 dari lingkaran,

  //Yaitu ketika sudut= 45derajat, cx = xy

  while(cx > cy){

    if(cx*cx + cy*cy -r*r > 0){ // D(M) , if D(M) > 0, NW(x-1,y+1) dipilih

      cx--;

    }

    cy++;

  }

}

Algoritma ini dapat lebih di efektifkan dengan menyederhanakan kalkulasi D(M). Untuk setiap D(M) = D(x-1/2,y) = x^2 - x +1/4 + y^2 -r^2, berikutnya  D(Mnew) = D(x-1/2,y+1) = x^2 - x +1/4 + y^2 +2y +1 - r^2. Jadi kita mendapatkan perbedaan setiap tingkatan dari D(M), dy = 2y +1 dan nilai D(Mnew) = D(M) + 2y + 1. Ketika D(M) > 0, x harus digerakkan juga, jadi D(Mnew) = D(x-3/2,y+1) = x^2 - 3x +9/4 + y^2 +2y + 1 = D(M) -2x +2 +2y +1 . Kita mendapatkan perbedaan ketika x digerakkan : dx = -2x + 2. Untuk algoritma yang sudah di optimalisasi:

 var drawCircle = function(ctx, x, y, r){ 

 // d dimulai dari  D(M) = r^2 - r^2 + r-1/4 = r- 1/4 , tapi dapat di abaikan karena r>1/4

  var d = r;
  var dx = (-2) * r; //dx = -2x +2 , constant move to loop  var dy = 0; //dy = 2y + 1 , constant move to loop   var cx = r;
  var cy = 0;    
  init(ctx,x,y,r);   while(cx > cy){    if(d > 0){      cx--;      d += (-2)*cx + 2;    }    cy++;    d += 2*cy + 1;     mirrowing(ctx,x,y,cx,cy);  }}