Apa itu algoritma DDA? Bresenham? dan Midpoint

ALGORITMA DDA, BRESENHAM DAN MIDPOINT

1.      ALGORITMA DDA

TITIK DAN GARIS

Persamaan Garis

y = mx + b Persamaan garis menurut koordinat Cartesian adalahdimana m adalah slope/kemiringan garis yang dibentuk dari dua titik, yaitu (x1,y1) dan (x2,y2).Untuk penambahan x sepanjang garis yaitu dx akan mendapatkan penambahan y sebesar : dy = m . dx

Atribut

Atribut dasar untuk garis lurus adalah type (tipe), width (tebal) dan color (warna). Dalam beberapa paket aplikasi grafik, garis ditampilkan dengan menggunakan pilihan pen atau brush . Berikut ini dibicarakan bagaimanafungsi garis dapat mengakomodasi bermacam-macam spesifikasi atribut.

Tipe Garis

Garis mempunyai beberapa linetype (tipe garis) diantaranya solid line (garis tebal), dashed line (garis putus), dan dotted line (garis titik-titik).Algoritma pembentukan garis dilengkapi dengan pengaturan panjang dan jarak yang menampilkan bagian solid sepanjang garis.

Garis putus dibuat dengan memberikan nilai jarak dengan bagian solid yang sama. Garis titik–titik dapat ditampilkan dengan memberikan jarak yang lebih besar dari bagain solid.
Prosedur yang serupa digunakan pula untuk membuat bermacam-macam tipe garis. Untuk mengatur atribut dalam program aplikasi PHIGS menggunakan fungsi: setLinetype (lt)

Di mana parameter it menunjukkan integer positif dengan nilai 1,2,3,4 untuk membuat garis solid, dashed, dotted atau dotted dash. nilai lain untuk parametergaris dapat digunakan untuk menampilkan berbagai macam pola dot dashed. Ketika parameter linetype diatur dalam aplikasi PHIGS, perintah line drawing membuat garis dengan tipe garis tersebut.

Algoritma Pembentukan Garis

Algoritma pembentukan garis menggunakan 3 algoritma :

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

           Algoritma DDA bekerja atas dasar penambahan nilai x dan nilai y. Pada garis lurus, turunan pertaman dari x dan y adalah konstanta. Sehingga untuk memperoleh suatu tampilan turunan dengan ketelitian tinggi, suatu garis dapat dibangkitkan dengan menambah nilai x dan y masing-masing sebesar eΔx dan eΔy, dengan besaran nilai yang sangat kecil. Kondisi ideal ini sukar dicapai, karenanya pendekatan yang mungkin dilakukan adalah berdasarkan piksel-piksel yang bisa diamati / dicapai atau melalui penambahan atau pengurangan nilai x dan y dengan suatu besaran dan membulatkannya ke nilai integer terdekat.

               Contohnya dapat ditunjukkan dengan gambar berikut :

              

               Jika 0 < m < 1      maka    yk + 1 = yk + m

                                                          xk + 1 = xk + 1

               Jika m > 1            maka    xk + 1 = xk + 1/m

                                                          yk + 1 = yk + 1

ALGORITMA GARIS DDA

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

Langkah-langkah membentuk garis menurut algoritma DDA adalah :

1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis

2. Tentukan titik awal yaitu dan titik akhir .

3. Hitung dx = x1- x0 dan dy = y1 – y0

4. Tentukan step = max( |dx| , |dy| )

5. Hitung penambahan koordinat pixel XInc = dx / step dan YInc = dy / step

6. Koordinat selanjutnya (x+XInc, y+yInc)

7. Posisi pada layar ditentukan dengan pembulatan nilai koordinat tersebut

8. Ulangi nomor 6 dan 7 untuk menentukan posisi pixel berikutnya. sampai x=x1dan y=y1.

2.      ALGORITMA BRESENHAM

-          Garis Lurus

Garis lurus dinyatakan dinyatakan dalam persamaan :

y = mx + c                               (1)
dimana : m : gradient dan
c : konstanta.

Untuk menggambarkan piksel-piksel dalam garis lurus, parameter yang digunakan tergantung dari gradient, jika besarnya gradient diantara 0 dan 1, maka digunakan sumbu x sebagai parameter dan sumbu y sebagai hasil dari fungsi, sebaliknya, bila gradient melebihi 1, maka sumbu y digunakan sebagai parameter dan sumbu x sebagai hasil dari fungsi, hal ini bertujuan untuk menghindari terjadinya gaps karena adanya piksel yang terlewatkan. Hasil dari fungsi biasanya merupakan bilangan real, sedangkan koordinat pixel dinyatakan dalam bilangan integer (x,y), maka diperlukan operasi pembulatan kedalam bentuk integer terdekat. Penggambaran garis lurus dengan metode diatas dimulai dengan operasibilangan real untuk menghitung gradient m dan konstanta c.

m = (y2 – y1 ) / (x2-x1)          (2)
c = y1 / m* x1*                       (3)

Operasi bilangan real berikutnya adalah menghitung nilai y dengan persamaan (1) Untuk mendapatkan koordinat piksel (x,y), untuk setiapnilai x, dari =x1 sampai x=x2, operasi inilah yang perlu dihindari,karena operasi ini memerlukan waktu operasi yang besar.

Algoritma Bresenham untuk Penggambaran Garis

Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel yang menggunakan persamaan (1), dengan cara menggantikan operasi bilangan real perkalian dengan operasi penjumlahan, yang kemudian dikenal dengan Algoritma Bresenham. Pada algoritma bresenham, nilai y kedua dan seterusnya, dihitung dari nilai y sebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap. Perbaikan algoritma ini ternyata tidak menghasilkan perbaikan yang cukup siginifikan. Perbaikan berikutnya dilakukan dengan cara menghilangkan operasi bilangan real dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan real, terutama pada penambahan dan pengurangan.

ALGORITMA GARIS BRESSENHAM
Prosedur untuk menggambar kembali garis dengan membulatkan nilai x atau y ke bilangan integer memerlukan waktu. serta variabel x,y maupun m memerlukan bilangan real karena kemiringan merupakan nilai pecahan.Bressenham mengembangkan algoritma klasik yang lebih menarik, karena hanya menggunakan perhitungan matematik dengan bantuan bilangan integer. Dengan demikian tidak perlu membulatkan nilai posisi pixel setiap waktu. Langkah-langkahnya adalah sebagai berikut:
1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan salah satu titik disebelah kiri sebagai titik awal (x0,y0) dan titik lainnya sebagai titik akhir (x1,y1)
3. Hitung dx, dy, 2dx dan 2dy-2dx
4. Hitung parameter P0 = 2dy – dx
5. Untuk setiap xk sepanjang garis dimulai dengan k=0
§ Bila Pk < 0 maka titik selanjutnya adalah (xk+1, yk) dan Pk+1=Pk+2dy
§ Bila tidak maka titik selanjutnya adalah (xk+1, yk+1) dan Pk+1=Pk+2dy-2dx
6. Ulangi nomor 5 untuk menentukan posisi pixel selanjutnya sampai x=x1 dan y=y1

3.      ALGORITMA MIDPOINT

Algoritma Midpoint untuk Penggambaran Garis

Algoritma midpoint dikembangkan oleh Pitteway pada tahun 1967.

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 positif 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:

1. Gambar piksel pertama (x1,y1). Hitung variabel penentu dengan persamaan (3).
2. 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.
3. Plot piksel pada posisi (x, y).
4. Ulangi langkah mulai langkah kedua, sampai piksel terakhir (x2,y2).

-          Lingkaran

Kurva lingkaran dinyatakan dinyatakan dalam persamaan :

*(x-xc) ^2 + (y-yc) ^2 = r ^2 *          (9)

dimana : (xc,yc) : koordinat titik pusat lingkaran
r : jari-jari lingkaran


Untuk menggambarkan piksel-piksel dalam kurva lingkaran, dapat digunakan sumbu x dari x = (xc-r) sampai x = (xc+r) sebagai parameter dan sumbu y sebagai hasil dari persamaan (10)

*y = yc +- sqrt(r ^2 – (x-xc) ^2 *      (10)

Algoritma ini memerlukan waktu operasi yang besar, karena mengandung operasi bilangan riel perkalian maupun eksponential, dan menghasilkan posisi koordinat piksel yang tidak merata, karena terjadinya gaps yang disebabkan adanya perubahan gradient.
Untuk menghindari posisi koordinat piksel yang tidak merata, koordinat piksel (x,y) dinyatakan dengan menggunakan koordinat polar dalam persamaan (11)

*x = xc + r cos q *                              (11a)
*y = yc + r sin q *                              (11b)

Persamaan (11) diatas mengandung operasi bilangan riel perkalian untuk mendapatkan koordinat piksel (x,y), untuk setiap nilai x, dari x = (xc-r) sampai x = (xc+r), operasi inilah yang perlu dihindari, karena operasi ini memerlukan waktu operasi yang besar.

Algoritma Midpoint untuk Menggambar Lingkaran
Komputasi untuk membuat kurva lingkaran dimulai dengan mengidentifikasi bagian-bagian dari lingkaran yang dapat ditentukan dengan menggunakan sifat simetri, hal ini dilakukan dengan cara membagai lingkaran dengan masing-masing mempunyai sudut sebesar 45° , sehingga dalam sebuah lingkaran dibagi menjadi 8 bagian. Sebagai contoh, digambarkan bagian dari lingkaran dari sudut 90° sampai 45° . Seperti pada algoritma midpoint untuk garis lurus, maka pada setiap tahapan, terdapat 2 koordinat piksel yang harus dipilih yaitu (x+1, y) atau (x+1, y-1).

Langkah berikutnya, adalah menyatakan persamaan lingkaran dan fungsi untuk menentukan variabel penentu. Persamaan lingkaran dengan pusat (0,0) dinyatakan dalam persamaan (12).

*f(x, y) = x*x + y+y – r*r = 0 *         (12)

Fungsi f(x, y) persamaan (12) akan bernilai positif jika titik (x,y) diluar lingkaran, dan bernilai negatif jika titik (x,y) didalam lingkaran. Fungsi untuk variabel penentu dan increment dinyyatakan dalam persamaan (13), (14), dan (15).

g(x, y) = (x + 1) (x + 1) + (y – 1/2) (y – 1/2) – r*r                 (13)
*DeltaG1 = 2x + 3                                                                  (14)
*DeltaG2 = 2x – 2y + 5                                                          (15)

Berbeda dengan nilai dari increment pada algoritma garis lurus yang bernilai konstan, pada kurva lingkaran, increment tidak konstan. Terlihat bahwa komputasi increment memerlukan operasi perkalian, tetapi operasi perkalian dapat diubah dengan cara komputasi nilai increment secara increment pula, sehingga diperlukan 2 komputasi increment dalam setiap piksel yang diproses. Secara umum, kurva polinomial orde n memerlukan n level increment. Pada titik awal (x1,y1), komputasi variabel penentu mempunyai bagian bilangan riel, sehingga operasi bilangan integer tidak dapat digunakan secara langsung.

Dalam praktek hal ini diselesaikan dengan cara menambahkan nilai 1/4 pada variable penentu. Hal ini tidak mempengaruhi perubahan tanda bilangan, karena operasi yang dilakukan adalah operasi bilangan integer, sehingga menghasilkan operasi yang lebih cepat.
Panjang garis atau banyak piksel dalam garis lurus sangat berpengaruh terhadap perbandingan performance antara sebuah algoritma dengan algoritma yang lain, hal ini disebabkan adanya perbedaan waktu operasi yang berada didalam perulangan sepanjang pembuatan piksel, dan waktu operasi yang berada pada sebelumnya. Panjang jari-jari dalam lingkaran tidak berpengaruh terhadap perbandingan performance antara sebuah algoritma dengan algoritma yang lain, hal ini menunjukkan perbandingan waktu operasi yang berada didalam perulangan sepanjang pembuatan piksel, dan waktu operasi yang berada pada sebelumnya berimbang.
Algoritma dengan dasar operasi bilangan integer memberikan waktu operasi yang lebih cepat dibandingkan dengan algoritma dengan dasar operasi bilangan riel, hal ini ditunjukkan dengan waktu komputasi algoritma DDA, algoritma Bresenham dan algoritma Midpoint yang lebih cepat, baik pada pembuatan garis lurus maupun lingkaran dibandingan waktu komputasi dengan algoritma yang menggunakan dasar operasi bilangan riel. Algoritma midpoint memberikan waktu operasi tercepat diantara algoritma penggambaran garis lurus yang telah menggunakan dasar operasi bilangan integer, seperti algoritma DDA, algoritma Bresenham. Jadi algoritma Midpoint merupakan algoritma yang cocok untuk penggambaran grafik yang menuntut kecepatan sebagai hal yang diutamakan.

Postingan di atas juga ada dalam bentuk .docx . Dapat didownload disini