Algoritma DDA, Bresenham, dan Midpoint

Algoritma Digital Differential Analyzer (DDA)

            Algoritma  Digital  Differential  Analyzer  (DDA)  adalah  algoritma  pembentukan  garis  berdasarkan  perhitungan  dx maupun  dy  dengan menggunakan  rumus  dy  = m.dx.  Garis  dibuat  dengan  menentukan  dua  endpoint  yaitu  titik  awal  dan  titik  akhir.  Setiap  koordinat titik yang membentuk garis diperoleh dari perhitungan kemudian dikonversikan  menjadi nilai integer.

• Pertama, dalam pembentukan garis tentukan dua titik yang akan dihubungkan terlebih dahulu.

• Kemudian, tentukan titik awal dan titik akhir.

• Hitung hasil perhitungan dari dx = x2 - x1 dan dy = y2 - y1.

• Tentukan step, dengan syarat :

• Jika dx > dy maka step = dx

• Sebaliknya, jika dx < dy, maka step = dy

• Hitung penambahan koordinat pixel dengan permasaan menggunakan :

• x_inc = dx / step

• y_inch = dy / step

• Untuk koordinat selanjutnya yaitu x+x_inc, y+y_inch.

• Hasil perhitungan nilai koordinat dibulatkan.

• Untuk menentukan posisi pixel berikutnya, ikuti kembali langkah 6 dan 7.

Contoh Soal:

Langkah-langkah algoritma DDA:

Untuk menggambarkan algoritma DDA dalam pembentukan suatu garis yang menghubungkan titik (10,10) dan (17,16), pertama-tama ditentukan dx dan dy, kemudian dicari step untuk mendapatkan x_increment dan y_increment.

Δx = x1 — x 0 = 17–10 = 7

Δy = y1 — y0 = 16 -10 = 6

selanjutnya hitung dan bandingkan nilai absolutnya.

|Δx| = 7

|Δy| = 6

karena |Δx| > |Δy|, maka step = |Δx| = 7, maka diperoleh :

x_inc = 7/7= 1

y_inc = 6/7 = 0,86 .

Algoritma Bresenham

Algoritma  Bresenham  merupakan  algoritma  penggambaran  garis  yang  efisien  dengan menggunakan perhitungan incremental integer.   Prinsip dari algoritma Bresenham adalah :

1. Sumbu vertikal memperlihatkan posisi scan line.

1. Sumbu horizontal memperlihatkan kolom pixel

1. Pada  tiap  langkah, penentuan pixel selanjutnya didasari oleh parameter  integer yang nilainya proporsional dengan pengurangan antara vertical separations dari dua posisi  piksel dari nilai actual.

Langkah-langkah algoritma bresenham:

• Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.

• Tentukan salah satu sebagai titik awal (x0,y0) dan titik akhir (x1,y1).

• Hitung dx, dy, 2dy dan 2dy - 2dx

• Hitung parameter : po = 2dy - dx

• Untuk setiap xk sepanjang jalur garis, dimulai dengan k=0

• bila pk < 0 maka titik selanjutnya adalah:

• (xk+1, yk) dan pk+1 = pk + 2dy

• bila tidak, titik selanjutnya adalah:

• (xk+1, yk+1) dan pk+1 = pk + 2dy – 2dx

• Ulangi nomor 5 untuk menentukan posisi pixel berikutnya, sampai x = x1 atau y = y1.  

Algoritma Midpoint

Algoritma midpoint dikembangkan oleh Pitteway pada tahun 1967. Pada gambar, titik abu-abu menyatakan posisi piksel, titik hitam menyatakan posisi piksel yang telah digambar. Berdasarkan piksel ke n yang telah digambar, diperlukan metode untuk menentukan piksel berikut yang akan digambar, karena penggambaran dilakukan dari kiri ke kanan, maka piksel berikutnya harus pada kolom n+1. Karena gradien antara 0 dan 1, maka piksel nerikutnya adalah pada posisi titik p atau titik q.

gambar garis lurus

• Gambar piksel pertama (x1,y1). Hitung variabel penentu dengan persamaan (3).

• Tentukan tanda variabel penentu. Jika variabel penentu bernilai positif, increment x dan y dan tambahkan (a+b) pada vaiabel penentu, sebaliknya increment x dan y dan tambahkan (a) pada variabel penentu.

• Plot piksel pada posisi (x, y).

• Ulangi langkah mulai langkah kedua, sampai piksel terakhir (x2,y2).

y = mx + x (1)

dimana: m = gradient, dan

              c = konstanta

m = (y2 - y1 ) / (x2-x1) (2)

c = y1 – m* x1 (3)

Persamaan garis lurus yang telah dinyatakan dalam persamaan (1) dapat dinyatakan dalam fungsi x,y berikut.

f(x, y) = ax + by + c = 0 (4)

Fungsi f(x,y) dalam persamaan (4), akan memberikan nilai 0 pada setiap titik yang terletak pada garis, dan bernilai positip pada setiap titik yang terletak dibawah garis, dan bernilai negatif pada setiap titik yang terletak diatas garis.

Maka untuk menentukan apakah titik P atau Q sebagai koordinat piksel berikutnya, maka dilakukan dengan cara menghitung nilai fungsi f(x,y) dalam persamaan (4) pada titik P dan titik Q . Jika fungsi f(x,y) tersebut memberikan nilai positif, maka piksel berikutnya adalah Q, sebaliknya piksel berikutnya adalah P.

g(x, y) = f(xn + 1, yn + 1/2) (5)

Fungsi g(x,y) persamaan (5) merupakan variabel penentu, dengan mengevaluasi g (x, y) dapat ditentukan piksel berikutnya yang mana berdasarkan tanda plus atau minus dari hasil fungsi g(x,y).

Untuk mempercepat komputasi fungsi g(x,y), dilakukan dengan cara incremental berdasarkan nilai sebelumnya. Untuk setiap piksel, increment sederhana (DeltaG) dipakai sebagai variabel penentu. Karena hanya ada 2 pilihan piksel pada setiap tahap, maka hanya ada 2 increment yang dapat digunakan. Hal ini dilakukan dengan cara pengurangan nilai g(x,y) yang berurutan dengan menggunakan persamaan 4 dan persamaan 5.

DeltaG = a * DeltaX + b * DeltaY (6)

Dimana DeltaX dan DeltaY adalah increment yang dipakai pada x dan y, yang bernilai 0 atau 1. Bila bergeser 1 piksel ke kanan :

DeltaG1 = a (7)

Bila bergeser 1 piksel ke kanan dan 1 piksel ke atas.

DeltaG2 = a + b (8)

Jadi nilai dari variable penentu dapat dihitung dari nilai sebelumnya dengan cara menambah dengan (a) atau (a+b). Algoritma untuk menggambar garis lurus dari (x1, y1) sampai (x2, y2) dilakukan dengan langkah-langkah sebagai-berikut:

• Gambar piksel pertama (x1,y1). Hitung variabel penentu dengan persamaan (3).
• Tentukan tanda variabel penentu. Jika variabel penentu bernilai positif, increment x dan y dan tambahkan (a+b) pada vaiabel penentu, sebaliknya increment x dan y dan tambahkan (a) pada variabel penentu.
• Plot piksel pada posisi (x, y).
• Ulangi langkah mulai langkah kedua, sampai piksel terakhir (x2,y2).