Protokol dan format

Perbedaan antara algoritma DDA dan Bresenham

Perbedaan antara algoritma DDA dan Bresenham

Algoritma Diferensial Digital (DDA) dan algoritma Bresenhams adalah algoritma menggambar garis digital dan digunakan dalam grafik komputer untuk menggambar gambar. Sebelumnya, kami menggunakan analitik analitik untuk menghitung piksel dan dengan demikian gambar garis dimungkinkan. Tetapi metode analitik ini tidak seakurat metode digital yang dengan penggunaan algoritma digital ini sekarang dan seperti setiap bidang, kami telah menemukan metode kualitas yang lebih tinggi dalam grafik komputer juga. Penemuan algoritma ini adalah contoh yang sempurna.  Sebelum kita melanjutkan, mari kita lihat konsep di balik algoritma ini. Meskipun tampaknya di luar ruang lingkup diskusi kita, penting untuk menunjukkan perbedaan dasar antara keduanya. Jika Anda benar -benar terbiasa dengan algoritma, Anda dapat melompat ke perbedaan aktual yang terletak di akhir halaman ini.

Apa itu Digital Diferensial Algoritma (DDA)?

DDA sebagian besar digunakan untuk menggambar garis dalam grafik komputer dan menggunakan nilai nyata sambil memprediksi nilai piksel berikutnya. Mari kita asumsikan nilai piksel awal sebagai (x0, y0) (x0, y0) dan piksel tujuan sebagai (x1, y1) (x1, y1). Kami akan belajar cara menghitung nilai piksel tujuan dari nilai piksel yang diketahui (x0, y0) (x0, y0) seperti di bawah ini.

  • Cara menghitung nilai titik tujuan menggunakan DDA?

Langkah 1: Di sini kita memiliki input (x0, y0) (x0, y0) dan kita harus mengidentifikasi apakah garis berjalan sejajar dengan sumbu x atau sumbu y. Untuk menemukan itu, mari kita sekarang menghitung perbedaan antara nilai piksel awal dan tujuan.

dx = x1 - x0

dy = y1 - y0

Langkah 2: Sekarang, kami telah mengidentifikasi perbedaannya dan kami harus menggambar garis di sepanjang sumbu x jika 'dx' adalah nol sebaliknya, kami harus menggambar garis paralel dengan sumbu y. Berikut adalah perhitungan yang sebenarnya dalam hal bahasa komputer.

if (absolute (dx)> absolute (dy))

Langkah = absolute (dx);

kalau tidak

Langkah = absolute (dy);

Langkah-3: Sekarang, saatnya untuk mengidentifikasi koordinat 'x' yang sebenarnya atau 'y' koordinat nilai piksel untuk menggambar garis.

X increment = dx / (float) langkah;

Y Increment = dy / (float) langkah;

Langkah-4: Ini harus dihitung sampai kami mencapai piksel tujuan. Algoritma DDA melengkapi nilai piksel ke nilai integer terdekat saat melakukan perhitungan. Inilah contoh kode dari apa yang telah kita bahas sekarang.

Untuk (int v = 0; v < Steps; v++)

x = x + x kenaikan;

y = y + y kenaikan;

putpixel (bundar (x), bulat (y));

Kami selesai menggambar garis menggunakan DDA dan mari kita pindah ke Bresenham sekarang!

Apa algoritma Bresenham?

Ini juga merupakan algoritma menggambar garis digital dan diciptakan oleh Bresenham pada tahun 1962 dan itulah sebabnya ia memiliki nama yang sama. Algoritma ini lebih akurat dan menggunakan pengurangan & penambahan untuk menghitung nilai piksel saat menggambar garis. Keakuratan algoritma Bresenham dapat diandalkan saat menggambar kurva & lingkaran juga. Mari kita lihat bagaimana algoritma ini bekerja.

Langkah 1: Algoritma Bresenham mengasumsikan koordinat piksel awal sebagai (xa+1, yA).

Langkah 2: Secara otomatis menghitung nilai piksel berikutnya sebagai (xa+1, ya+1), Di sini 'a' adalah nilai tambahan dan algoritma menghitungnya dengan menambahkan atau mengurangi persamaan yang telah dibentuknya.

Algoritma ini menghitung nilai yang akurat tanpa pembulatan dan terlihat lebih mudah juga!

  • Contoh numerik dari algoritma Bresenham:

Sekarang mari kita pertimbangkan poin (0,0) dan (-8, -4) dan mari kita menggambar garis antara poin -poin ini menggunakan algoritma Bresenham.

Data yang diberikan, (x1, y1) = (0, 0) dan (x2, y2) = (-8, -4).

Mari kita hitung nilai diferensial seperti di bawah ini.

∆x = x2-x1 = -8-0 = 8

Oleh karena itu, nilai tambahan untuk x = ∆x / x2 = 8 / -8 = -1.

∆y = y2-y1 = -4-0 = 4

Oleh karena itu, nilai tambahan untuk y = ∆y / y2 = 4 / -4 = -1.

Variabel keputusan = e = 2*(∆y)-(∆x)

Oleh karena itu, e = 2*(4)-(8) = 8-8 = 0

Dengan perhitungan di atas, mari kita tabulasi nilai yang dihasilkan. Nilai koordinat-y disesuaikan berdasarkan variabel keputusan dan kami hanya mengabaikan perhitungannya di sini.

Piksel X y                                              Variabel keputusan
(0,0) 0 0 0
(-1,0) -1 0 Nilai
(-2, -1) -2 -1 0
(-3, -1) -3 -1 Nilai
(-4, -2) -4 -2 0
(-5, -2) -5 -2 Nilai
(-6, -3) -6 -3 0
(-7, -3) -7 -3 Nilai
(-8, -4) -8 -4 0

Perbedaan antara algoritma DDA & Bresenham:

  • Perhitungan Aritmatika:

DDA menggunakan nilai nyata dalam perhitungannya dengan penggunaan titik mengambang. Nilai piksel atau titik berikutnya ditentukan dengan persamaan diferensial

X increment = dx / (float) langkah

Y Increment = dy / (float) langkah

Di sini tidak ada konstanta tetap yang digunakan tetapi dalam algoritma poin tetap algoritma Bresenham digunakan dalam perhitungan aritmatika. Algoritma Bresenham menggunakan aritmatika integer, tidak seperti DDA.

  • Jenis operasi yang digunakan:

DDA memecahkan persamaan diferensial dengan operasi perkalian dan pembagian. Anda dapat melihat hal yang sama di sini, x increment = dx / (float) langkah. Algoritma Bresenham menggunakan operasi penambahan dan pengurangan dan Anda dapat melihat hal yang sama di sini dalam persamaan komputasi nilai piksel berikutnya (xa+1, ya+1). Aritmatika lebih sederhana di Bresenham jika dibandingkan dengan DDA.

  • Efisiensi:

Seperti yang telah kita bahas sebelumnya, algoritma Bresenham menggunakan aritmatika yang lebih sederhana daripada DDA dan menghasilkan hasil yang efisien.

  • Kecepatan: Karena DDA menggunakan bilangan bulat floating point bersama dengan operasi multiplikasi & divisi, ia relatif lebih lambat sedangkan algoritma Bresenham menggunakan aritmatika integer hanya bersama dengan penambahan & pengurangan saja. Ini sangat mengurangi waktu yang dibutuhkan untuk perhitungannya dan karenanya lebih cepat dari DDA.
  • Ketepatan: Meskipun DDA menggunakan nilai titik mengambang, keakuratan DDA tidak lebih baik seperti Bresenham. Berbagai faktor mempengaruhi konsep ini dan oleh karena itu, Bresenham lebih akurat daripada DDA.
  • Pembulatan: Lihat saja perhitungan DDA di sini.

X increment = dx / (float) langkah

Anda dapat melihat 'float' dan karena itu tidak membulatkan nilai -nilai sedangkan algoritma Bresenham melengkapi nilai -nilai ke bilangan bulat terdekat. Oleh karena itu, nilai -nilai yang digunakan lebih sederhana dalam algoritma Bresenham.

  • Apa yang menariknya?

DDA mampu menggambar lingkaran dan kurva selain dari garis menggambar. Algoritma Bresenham juga mampu menggambar semua yang disebutkan di atas dan akurasinya benar -benar lebih tinggi dari pada DDA. Demikian pula, algoritma Bresenham bisa menghasilkan kurva yang efisien daripada yang diproduksi oleh DDA. Kedua algoritma dapat menggambar segitiga dan poligon juga.

  • Yang mahal?

Karena DDA juga menyertakan pembulatan, harganya mahal daripada penggunaan algoritma Bresenham.

  • Yang merupakan algoritma yang dioptimalkan?

Dari diskusi kami di atas, sangat jelas bahwa algoritma Bresenham adalah yang dioptimalkan dalam hal kecepatan, biaya, dan penggunaan operasi.

Mari kita lihat perbedaan dalam bentuk tabel.

S.TIDAK Perbedaan Algoritma Diferensial Digital Algoritma Bresenham
1. Kenapa namanya? Hanya karena itu adalah implementasi digital dari persamaan, itu punya namanya. Itu ditemukan oleh j.E. Bresenham pada tahun 1962 dan karenanya namanya.
2. Perhitungan Itu melibatkan perhitungan yang lebih keras. Perhitungan yang digunakan sangat sederhana.
3. Jenis Operasi yang Digunakan Itu menggunakan multiplikasi dan divisi. Persamaan diferensial sampel yang digunakan di sini adalah xincrement = dx / (float) langkah,

Yintrement = dy / (float) langkah.

 Itu menggunakan penambahan dan pengurangan. Perhitungan sampel di sini dapat dilambangkan seperti (xa+1, ya+1).
4. Nilai komputasi aritmatika Itu menggunakan nilai floating point. Itu hanya menggunakan nilai integer.
5. Efisiensi Hasil aritmatika yang kompleks dalam efisiensi yang lebih rendah. Hasil aritmatika yang lebih sederhana dalam lebih efisiensi.
6. Kecepatan Penggunaan operasi perkalian dan pembagian membutuhkan banyak waktu untuk proses perhitungannya. Penggunaan Operasi Penambahan dan Pengurangan membutuhkan waktu yang lebih rendah dari DDA.
7. Ketepatan Itu lebih rendah dalam akurasi. Itu lebih akurat.
8. Pembulatan Itu menggunakan nilai nyata dan tidak pernah melengkapi nilai -nilai. Itu melengkapi nilai ke nilai integer terdekat.
9. Kemampuan menggambar Ini mampu menggambar garis, lingkaran, dan kurva tetapi dengan akurasi yang lebih rendah. Kita bahkan bisa menggambar segitiga dan poligon dengan algoritma ini. Ini mampu menggambar garis, lingkaran, dan kurva dengan efisiensi yang lebih besar. Segitiga dan poligon juga dimungkinkan untuk ditarik dengan algoritma ini.
10. Biaya perhitungan Itu mahal karena melibatkan pembulatan juga. Penggunaan algoritma Bresenham lebih murah daripada DDA.
11. Algoritma yang dioptimalkan Ini bukan algoritma yang dioptimalkan Ini adalah algoritma yang dioptimalkan.

Kami telah menangani setiap perbedaan yang mungkin antara DDA dan algoritma Bresenham. Bahkan mungkin tampaknya berulang tetapi ada beberapa alasan yang valid untuk menyebutkan poin -poin itu lagi dan Anda akan mengetahui kapan Anda memahaminya sepenuhnya. Jika Anda masih merasa ada ambiguitas, silakan tinggalkan komentar. Mari kita belajar bersama dengan berbagi pengetahuan yang tepat!