Perbedaan antara DDA dan Algoritma Bresenham

Digital Differential Algorithm (DDA) dan Bresenhams's Algorithm adalah algoritma menggambar garis digital dan digunakan dalam grafik komputer untuk menggambar. Sebelumnya, kami menggunakan analisis 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 dengan setiap bidang, kami telah menemukan metode kualitas yang lebih tinggi dalam grafik komputer juga. Penemuan algoritma ini adalah contoh sempurna. Sebelum kita melanjutkan, mari kita lihat konsep di balik algoritma ini. Meskipun kelihatannya di luar lingkup pembahasan kita, penting untuk menunjukkan perbedaan mendasar antara keduanya. Jika Anda benar-benar terbiasa dengan algoritme, Anda dapat beralih ke perbedaan sebenarnya yang terletak di akhir halaman ini.

Apa itu Digital Differential Algorithm (DDA)?

DDA sebagian besar digunakan untuk menggambar garis-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). Kita akan belajar bagaimana 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, sekarang mari kita menghitung perbedaan antara nilai piksel awal dan tujuan.

dx = X1 - X0

dy = Y1 - Y0

Langkah 2: Sekarang, kita telah mengidentifikasi perbedaan dan kita harus menggambar garis di sepanjang sumbu x jika 'dx' adalah nol sebaliknya, kita harus menggambar garis sejajar dengan sumbu y. Berikut ini adalah perhitungan aktual dalam hal bahasa komputer.

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

Langkah = absolut (dx);

lain

Langkah = absolut (dy);

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

X kenaikan = dx / (float) langkah;

Y kenaikan = langkah dy / (float);

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

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

x = x + X kenaikan;

y = y + Y kenaikan;

putpixel (Putaran (x), Putaran (y));

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

Apa itu Algoritma Bresenham?

Ini juga merupakan algoritma penggambaran garis digital dan diciptakan oleh Bresenham pada tahun 1962 dan itulah sebabnya ia mendapatkan nama yang sama. Algoritma ini lebih akurat dan digunakan 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 (x_{a + 1}, y_Sebuah).

Langkah 2: Secara otomatis menghitung nilai piksel berikutnya sebagai (x_{a + 1}, y_{a + 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 perhatikan poin (0,0) dan (-8, -4) dan mari kita menggambar garis di antara titik-titik ini menggunakan algoritma Bresenham.

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

Mari kita menghitung nilai diferensial seperti di bawah ini.

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

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

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

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

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

Karenanya, e = 2 * (4) - (8) = 8-8 = 0

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

Pixel	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 DDA & Algoritma Bresenham:

Perhitungan Aritmatika:

DDA menggunakan nilai riil dalam perhitungannya dengan penggunaan floating point. Pixel atau nilai titik berikutnya ditentukan dengan persamaan diferensial

Peningkatan X = langkah dx / (float)

Y increment = langkah dy / (float)

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

Jenis operasi yang digunakan:

DDA memecahkan persamaan diferensial dengan operasi multiplikasi dan divisi. Anda bisa melihat hal yang sama di sini, langkah X kenaikan = dx / (float). Algoritma Bresenham menggunakan operasi penjumlahan dan pengurangan dan Anda dapat melihat hal yang sama di sini dalam persamaan perhitungan nilai piksel berikutnya (x_{a + 1}, y_{a + 1}). Hitungnya 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 perkalian & pembagian, itu relatif lebih lambat sedangkan algoritma Bresenham menggunakan bilangan bulat hanya aritmatika bersama dengan penambahan & pengurangan saja. Ini sangat mengurangi waktu yang dibutuhkan untuk perhitungannya dan karenanya lebih cepat dari DDA.
Ketepatan: Meskipun DDA menggunakan nilai floating point, keakuratan DDA tidak sebagus nilai Bresenham. Berbagai faktor mempengaruhi konsep ini dan oleh karena itu, Bresenham lebih akurat daripada DDA.
Pembulatan: Lihat saja perhitungan DDA di sini.

Peningkatan X = langkah dx / (float)

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

Apa artinya itu?

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

Itu mahal?

Seperti DDA termasuk pembulatan juga, itu 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 dalam	Algoritma Diferensial Digital	Algoritma Bresenham
1.	Kenapa namanya?	Hanya karena itu adalah implementasi digital dari persamaan, ia mendapatkan namanya.	Itu diciptakan oleh J.E. Bresenham pada tahun 1962 dan karenanya namanya.
2.	Perhitungan	Ini melibatkan perhitungan yang lebih keras.	Perhitungan yang digunakan sangat sederhana.
3.	Jenis operasi yang digunakan	Itu digunakan multiplikasi dan divisi. Persamaan diferensial sampel yang digunakan di sini adalah langkah Xincrement = dx / (float), Yincrement = langkah dy / (float).	Ini menggunakan penambahan dan pengurangan. Perhitungan sampel di sini dapat dinotasikan seperti (x_{a + 1}, y_{a + 1}).
4.	Nilai perhitungan aritmatika	Ini menggunakan nilai floating point.	Hanya menggunakan nilai integer.
5.	Efisiensi	Hasil aritmatika yang kompleks menghasilkan efisiensi yang lebih rendah.	Aritmatika yang lebih sederhana menghasilkan efisiensi yang lebih besar.
6.	Kecepatan	Penggunaan operasi multiplikasi dan divisi membutuhkan banyak waktu untuk proses komputasinya.	Penggunaan operasi penjumlahan dan pengurangan membutuhkan waktu lebih sedikit daripada DDA.
7.	Ketepatan	Akurasi lebih rendah.	Itu lebih akurat.
8.	Pembulatan	Ini menggunakan nilai nyata dan tidak pernah membulatkan nilai.	Ini membulatkan nilai ke nilai integer terdekat.
9.	Kemampuan menggambar	Ia mampu menggambar garis, lingkaran, dan kurva tetapi dengan akurasi yang lebih rendah. Kami bahkan dapat menggambar segitiga dan poligon dengan algoritma ini.	Ia mampu menggambar garis, lingkaran, dan kurva dengan efisiensi yang lebih besar. Segitiga dan poligon juga dimungkinkan untuk digambar 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 tampak berulang-ulang tetapi ada beberapa alasan yang sah untuk menyebutkan poin-poin itu lagi dan Anda akan mengetahui kapan Anda memahaminya sepenuhnya. Jika Anda masih merasa ada ambiguitas, silakan tinggalkan kami komentar. Mari kita belajar bersama dengan berbagi pengetahuan yang tepat!

Protokol & Format