Algoritma Teori Menggambar Garis

Suatu garis dapat ditarik dari sembarang titik yang koordinat-kordinatnya diketahui. Maka suatu garis sebenarnya merupakan kumpulan titik yang letaknya berdampingan dan sangat dekat, sehingga yang terlihat hanyalah sepasan titik yang bisa disebut sebagai titik ujung dan titik pangkal.

Dalam grafik komputer proses untuk menghidupkan sejumlah piksel untuk membentuk suatu garis disebut dengan pembangkitan vektor.

Beberapa persyaratan yang perlu di perhatikan pada layar tampilan adlah garis harus terlihat lurus, garis harus berakhir pada titik yang tepat, garis harus mempunyai titik kerapatan yang tetap untuk warna latar belakang yang berbeda.

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 riel, 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 operasi bilangan riil untuk menghitung gradient m dan konstanta c.

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

c = y1 ? m* x1 (3)

Operasi bilangan riil 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

Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel yang menggunakan persamaan (1), dengan cara menggantikan operasi bilangan riel 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 riel dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan riel, terutama pada penambahan dan pengurangan.

Algoritma Midpoint untuk Penggambaran Garis

Algoritma midpoint dikembangkan oleh Pitteway pada tahun 1967. Pada gambar 1, 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 diantara 0 dan 1, maka piksel berikutnya adalah pada posisi titik p atau titik q.

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:

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).

Algoritma DDA

DDA(digital differebtial analyser) mengunakan cara yang sama seperti halnya pada saat menghitung persamaan diferensial biasa.

dy =delta y/delta x dx

Garis yang dihasilkan dari algoritma DDA:

- algoritma DDA simetris

-algoritma DDA sederhana