Minggu, 10 Oktober 2010

Algoritma Bresenham





Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel yang menggunakan persamaan y = mx + c, 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. 





  • Sumbu vertikal memperlihatkan posisi scan line.
  • Sumbu horizontal memperlihatkan kolom pixel
  • 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.

Algoritma Bresenham







Po = 2 Δy - Δx

Langkah-langkah membuat garis dengan Bresenham :
  1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
  2. Tentukan salah satu titik di sebelah kiri sebagai titi awal, yaitu (x0,y0) dan titik lainnya sebgai titik akhir (x1,y1).
  3. Hitung dx,dy,2dx dan 2dy-2dx.
  4. Hitung parameter P0 = 2dy-dx
  5. Untuk setiap Xk sepanjang jalur garis, dimulai dengan k=0,bila pk <0,>k+1, yk), dan Pk+1 = Pk+2dybila tidak, maka titik selanjutnya adalah (xk+1,yk+1), dan Pk+1 = Pk+2dy-2dx
  6. Ulangi langkah no 5 untuk menentukan posisi pixel selanjutnya, sampai x = x1 dan y = y1.

Carta air bagi algoritma Bresenham :

Contoh dan penyelesaian dengan Algoritma Bresenham

1. Inputkan 2 titik hujung garis lurus (X 0,Y 0)dan (X n,Y n). katakan titik tersebut ialah (2,2) dan (6,4)










2. Plotkan titik awal iaitu (X0,Y 0)














3. Kemudian kira pemalar-pemalar berikut :






4. Seterusnya cari nilai pemalar penentu berpandukan nilai pemalar diatas



5. Pada setiap kedudukan persampelan Xk(di sepanjang laluan garis lurus) bermula daripada k=0, uji nilai pemalar tertentu                                  


  • Jika Pk<0, Plotkan titik (Xk+1,Y k)
              Pk+1 = Pk + 2 deltay
                                        

  • Jika Pk>0, Plotkan titik (Xk+1,Y k+1)
              Pk+1 = Pk + 2 deltay - 2 deltax





























































    • 6. Ulang langkah 5 sebanyak Δx kali. Hasilnya :





    Sumber :
    Diposting oleh 3KA01-KELOMPOK BERMAIN di 06.43

    1 komentar:

    Langganan: Posting Komentar (Atom)