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 (x₀,y₀) dan titik lainnya sebgai titik akhir (x₁,y₁).
3. Hitung d_x,d_y,2_dx dan 2_dy-2_dx.
4. Hitung parameter P₀ = 2_dy-d_x
5. Untuk setiap X_k sepanjang jalur garis, dimulai dengan k=0,bila p_k <0,>k+1, y_k), dan P_k+1 = P_k+2_dybila tidak, maka titik selanjutnya adalah (x_k+1,y_k+1), dan P_k+1 = P_k+2_dy-2_dx
6. Ulangi langkah no 5 untuk menentukan posisi pixel selanjutnya, sampai x = x₁ dan y = y₁.

Carta air bagi algoritma Bresenham :

Contoh dan penyelesaian dengan Algoritma Bresenham

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

2. Plotkan titik awal iaitu (X₀,Y ₀)

3. Kemudian kira pemalar-pemalar berikut :

4. Seterusnya cari nilai pemalar penentu berpandukan nilai pemalar diatas

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

Jika P_k<0, Plotkan titik (X_k+1,Y _k)
          P_k+1 = P_k + 2 deltay
                                    

Jika P_k>0, Plotkan titik (X_k+1,Y _k+1)
          P_k+1 = P_k + 2 deltay - 2 deltax

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

Algoritma DDA (Digital Defferential Analyzer)

DDA atau Digital Diferential Analyzer adalah scan conversion algorithm yang didasari oleh perhitungan berikut :

 Δy = m . Δ x 

  Δx = Δy / m 

Algoritma DDA

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

Langkah-langkah membuat garis dengan DDA :

1. Tentukan 2 buah titik.
2. Tentukan yang menjadi titik awal (X₀,Y₀) dan titik akhir (X₁,Y₁).
3. Hitung Dx dan D_yD_x = X₁-X₀ dan D_y = Y₁ – Y₀
4. Bandingkan Abs(D_x) dan Abs(D_y)Jika Abs(D_x) > Abs(D_y) makaSteps = Abs(D_x) bila tidak Steps = Abs(D_y)
5. Hitung penambahan koordinat pixel, yaitu:X_increment = dx/steps, danY_increment = dy/steps.
6. Koordint selanjutnya, yaituX+X_incrementY+Y_increment
7. Posisi pixel ditentukan dengan pembulatan nilai koordinat tersebut.
8. Ulangi langkah 6 dan 7 untuk posisi selanjutnya sampai X = X₁, Y = Y₁

Carta alir bagi algoritma DDA

Contoh dan penyelesaian penentuan titik dengan Algoritma DDA

1. Inputkan 

2 titik yaitu (2,6) dan (10,2). Mula-mula cari nilai kecerunan garis tersebut.

1. 
   

2. Kemudian, lihat sama ada garis tersebut x₁ < x ₂ yang dilukis dari kiri ke kanan atau x₁ > x ₂ yang di lukis dari kana ke kiri. Nilai kecerunan tadi juga di rujuk.

     Berdasarkan titik yang diberi, kiraanya adalah seperti berikut :

     
     sebagai contoh :

     

Langkah seperti gambar di atas diulang sebanyak 

Δx kali dan hasilnya seperti di bawah ini :