3KA01-7kurcaci: ALGORITMA GARIS BRESSENHAM. . .

Algoritma garis Bresenham adalah suatu algoritma yang menentukan titik-titik dalam n-dimensi raster harus diplot untuk membentuk pendekatan dekat dengan garis lurus antara dua titik yang diberikan.

Hal ini biasanya digunakan untuk menggambar garis pada layar komputer, karena hanya menggunakan integer penambahan, pengurangan dan pergeseran bit , yang semuanya murah operasi yang sangat dalam arsitektur komputer standar. Ini adalah salah satu algoritma paling awal dikembangkan di bidang komputer grafis . Sebuah ekstensi kecil dengan algoritma asli juga berhubungan dengan lingkaran gambar.

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 (x_0,y₀) dan titik lainnya sebagai titik akhir (x_1,y₁)
3.    Hitung dx, dy, 2dx dan 2dy-2dx
4.    Hitung parameter P₀= 2dy – dx
5.    Untuk setiap x_k sepanjang garis dimulai dengan k=0
o    Bila P_k< 0 maka titik selanjutnya adalah (x_k+1, y_k) dan P_k+1=P_k+2dy
o    Bila tidak maka titik selanjutnya adalah (x_k+1, y_k+1) dan P_k+1=P_k+2dy-2dx
6.    Ulangi nomor 5 untuk menentukan posisi pixel selanjutnya sampai x=x₁ dan y=y₁

Algoritma DDA yang dijelaskan diatas menentukan bahwa pertambahan nilai X dan Y untuk posisi berikutnya yang akan dihidupkan adalah suatu bilangan rill. Pada kenyataannya, operasi menggunakan bilangan integer lebih sederhana dibandingkan operasi menggunakan bilangan rill. Dengan alasan itulah, Bresenham memperkenalkan algoritma yang didasarkan atas bilangan integer. Hal itu juga berkaitan erat dengan keadaan sebenarnya dari suatu layar tampilan.

Pada setiap iterasi algoritma Bresenham, salah satu posisi (X atau Y) diubah nilainya menggunakan 1. Jika nilai salah satu posisi diubah, misalnya X, maka nilai Y bisa diubah, tetapi bisa juga dibuat tetap, berdasarkan suatu nilai ketelitian yang dipakai untuk mencatat jarak antara garis yang sesungguhnya dengan pixel yang akan dihidupkan, dan diukur tegak lurus denagn sumbu yang memiliki pertambahan paling besar. Dengan cara tersebut, jika pertambahan paling besar adalah kearah X, maka nilai ketelitian e ditentukan sejajar dengan sumbu Y, atau sebaliknya.

Dalam setiap iterasi algoritma Bresenham, kemiringan garis, ∆Y/∆X, ditambahkan pada factor kesalah e. sebelumnya penambahan dilaksanakan, tanda bilangan e digunakan untuk menentukan perlu tidaknya penambahan pada nilai y, jika e bernilai positif, berarti garis yang sesungguhnya terletak diatas pixel yang ditinjau sehingga nilai Y ditambah satu. Sebaliknya, jika bernilai negatif, nilai Y tidak perlu ditambah. Berdasarkan algoritma itu, bisa disusun prosedur sederhana menggunakan turbo pascal sebagai berikut: