Perbezaan antara Algoritma DDA dan Bresenham
Share
Algoritma Berbeza Digital (DDA) dan Algoritma Bresenhams adalah algoritma penggambaran garisan digital dan digunakan dalam grafik komputer untuk membuat gambar. Sebelum ini, kami telah menggunakan penganalisis analitik untuk mengira piksel dan dengan itu lukisan garis telah dibuat. Tetapi kaedah analitikal ini tidak tepat seperti kaedah digital yang menggunakan algoritma digital ini dan dengan setiap bidang, kami telah mencipta kaedah kualiti yang lebih tinggi dalam grafik komputer juga. Ciptaan algoritma ini adalah contoh yang sempurna. Sebelum kita meneruskan, mari kita lihat konsep di sebalik algoritma ini. Walaupun kelihatannya dari skop perbincangan kita, adalah penting untuk menunjukkan perbezaan asas antara kedua-dua. Jika anda benar-benar biasa dengan algoritma, anda boleh melompat ke perbezaan sebenar yang terletak di hujung halaman ini.
Apakah Algoritma Berbeza Digital (DDA)?
DDA kebanyakannya digunakan untuk menarik garis dalam grafik komputer dan menggunakan nilai sebenar semasa meramalkan nilai pixel seterusnya. Marilah kita menganggap nilai piksel awal sebagai (X0, Y0) (X0, Y0) dan piksel destinasi sebagai (X1, Y1) (X1, Y1). Kami akan mempelajari cara mengira nilai piksel destinasi dari nilai piksel yang diketahui (X0, Y0) (X0, Y0) seperti di bawah.
- Bagaimana untuk mengira nilai mata destinasi menggunakan DDA?
Langkah 1: Di sini kita mempunyai input (X0, Y0) (X0, Y0) dan kita harus mengenal pasti sama ada garis itu berjalan selari dengan paksi-x atau paksi-y. Untuk mencari itu, mari kita sekarang hitung perbezaan antara nilai awal dan destinasi piksel.
dx = X1 - X0
dy = Y1 - Y0
Langkah-2: Sekarang, kita telah mengenal pasti perbezaan tersebut dan kita harus melukis garis di sepanjang paksi-x jika 'dx' adalah sifar sebaliknya, kita harus menarik garisan selari dengan paksi-y. Inilah pengiraan sebenar dari segi bahasa komputer.
jika (mutlak (dx)> mutlak (dy))
Langkah = mutlak (dx);
lain
Langkah = mutlak (dy);
Langkah-3: Sekarang, sudah tiba masanya untuk mengenal pasti koordinat sebenar 'x' atau nilai koordinat piksel 'y' untuk menarik garisan.
X increment = dx / (float) langkah;
Y increment = dy / (float) langkah;
Langkah-4: Ini perlu dikira sehingga kita mencapai piksel destinasi. Algoritma DDA melupuskan nilai piksel ke nilai integer terdekat ketika melakukan pengiraan. Berikut adalah contoh kod yang telah dibincangkan sekarang.
Untuk (int v = 0; v < Steps; v++)
x = x + X kenaikan;
y = y + Y kenaikan;
Putpixel (Pusingan (x), Pusingan (y));
Kami selesai dengan melukis garis menggunakan DDA dan marilah kita pergi ke Bresenham sekarang!
Apakah Algoritma Bresenham?
Ia juga merupakan algoritma lukisan garis digital dan dicipta oleh Bresenham pada tahun 1962 dan itulah sebabnya ia mempunyai nama yang sama. Algoritma ini lebih tepat dan ia menggunakan pengurangan & penambahan untuk mengira nilai piksel semasa melukis garis. Ketepatan algoritma Bresenham boleh dipercayai semasa melukis lengkung & bulatan juga. Marilah kita melihat bagaimana algoritma ini berfungsi.
Langkah 1: Algoritma Bresenham menganggap koordinat piksel awal sebagai (xa + 1, ya).
Langkah-2: Ia secara automatik mengira nilai piksel seterusnya sebagai (xa + 1, ya + 1), Di sini 'a' adalah nilai tambahan dan algoritma mengira dengan menambah atau menolak persamaan-persamaan yang telah dibentuk.
Algoritma ini mengira nilai-nilai yang tepat tanpa pembulatan dan kelihatan lebih mudah juga!
- Contoh Numerik Algoritma Bresenham:
Mari kita pertimbangkan mata (0,0) dan (-8, -4) dan marilah kita melukis garis antara titik-titik ini dengan menggunakan algoritma Bresenham.
Memandangkan data, (x1, y1) = (0, 0) dan (x2, y2) = (-8, -4).
Marilah kita mengira nilai perbezaan seperti di bawah.
Δx = x2-x1 = -8-0 = 8
Oleh itu, nilai tambahan untuk x = Δx / x2 = 8 / -8 = -1.
Δy = y2-y1 = -4-0 = 4
Oleh itu, nilai tambahan untuk y = Δy / y2 = 4 / -4 = -1.
Keputusan Variabel = e = 2 * (Δy) - (Δx)
Oleh itu, e = 2 * (4) - (8) = 8-8 = 0
Dengan pengiraan di atas, marilah kita tabulasi nilai yang dihasilkan. Nilai koordinat y diselaraskan berdasarkan pemboleh ubah keputusan dan kita hanya mengabaikan perhitungannya di sini.
| Pixel | x | y | Pemboleh ubah 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 |
Perbezaan antara Algoritma DDA & Bresenham:
- Pengiraan aritmetik:
DDA menggunakan nilai sebenar dalam pengiraannya dengan penggunaan mata terapung. Nilai piksel atau titik seterusnya ditentukan dengan persamaan kebezaan
X increment = dx / (float) langkah-langkah
Y increment = dy / (float) langkah
Di sini tiada pemalar tetap digunakan tetapi dalam titik tetap algoritma Bresenham digunakan dalam pengiraan aritmetik. Algoritma Bresenham menggunakan aritmetik Integer, tidak seperti DDA.
- Jenis operasi yang digunakan:
DDA menyelesaikan persamaan pembezaan dengan operasi pendaraban dan pembahagian. Anda dapat melihat perkara yang sama di sini, langkah X increment = dx / (float). Algoritma Bresenham menggunakan operasi penambahan dan penolakan dan anda boleh melihat sama di sini dalam persamaan pengiraan nilai piksel seterusnya (xa + 1, ya + 1). Aritmetik lebih mudah di Bresenham apabila dibandingkan dengan DDA.
- Kecekapan:
Seperti yang telah dibincangkan sebelumnya, algoritma Bresenham menggunakan aritmetik yang lebih mudah daripada DDA dan menghasilkan keputusan yang cekap.
- Kelajuan: Oleh kerana DDA menggunakan integer titik terapung bersama-sama dengan operasi pendaraban & pembahagian, ia agak perlahan sedangkan algoritma Bresenham menggunakan hanya aritmetik integer bersama dengan penambahan & penolakan sahaja. Ini sangat mengurangkan masa yang diambil untuk pengiraannya dan dengan itu ia lebih cepat daripada DDA.
- Ketepatan: Walaupun DDA menggunakan nilai terapung, ketepatan DDA tidak lebih baik daripada Bresenham. Pelbagai faktor mempengaruhi konsep ini dan oleh itu, Bresenham lebih tepat daripada DDA.
- Membundung: Lihat saja pengiraan DDA di sini.
X increment = dx / (float) langkah-langkah
Anda dapat melihat 'float' dan oleh itu ia tidak mengulang nilai-nilai sedangkan algoritma Bresenham mengetepikan nilai-nilai ke integer terdekat. Oleh itu, nilai yang digunakan adalah lebih mudah dalam algoritma Bresenham.
- Apa yang menarik?
DDA mampu menarik bulatan dan lengkung selain menggambar garis. Algoritma Bresenham juga mampu menarik semua yang disebutkan di atas dan ketepatannya benar-benar lebih tinggi daripada DDA. Begitu juga, algoritma Bresenham boleh menghasilkan lengkung cekap daripada yang dihasilkan oleh DDA. Kedua-dua algoritma ini boleh menarik segitiga dan poligon.
- Yang mahal?
Memandangkan DDA termasuk pembulatan juga, ia lebih mahal daripada penggunaan algoritma Bresenham.
- Yang merupakan algoritma yang dioptimumkan?
Dari perbincangan kami di atas, sangat jelas bahawa algoritma Bresenham adalah satu pengoptimuman dari segi kelajuan, kos, dan penggunaan operasi.
Marilah kita melihat perbezaan dalam bentuk jadual.
| S.No | Perbezaan dalam | Algoritma Berbeza Digital | Algoritma Bresenham |
| 1. | Kenapa nama itu? | Hanya kerana ia merupakan persamaan digital persamaan, ia telah mendapat nama. | Ia dicipta oleh J.E. Bresenham pada tahun 1962 dan dengan itu namanya. |
| 2. | Pengiraan | Ia melibatkan pengiraan yang lebih sukar. | Pengiraan yang digunakan adalah lebih mudah. |
| 3. | Jenis operasi yang digunakan | Ia menggunakan perkalian dan bahagian. Persamaan pembezaan sampel yang digunakan di sini adalah langkah-langkah Xincrement = dx / (float), Langkah Yincrement = dy / (float).
| Ia menggunakan penambahan dan penolakan. Pengiraan sampel di sini boleh dilambangkan seperti (xa + 1, ya + 1). |
| 4. | Nilai pengiraan aritmetik | Ia menggunakan nilai terapung. | Ia hanya menggunakan nilai integer. |
| 5. | Kecekapan | Keputusan aritmetik kompleks dalam kecekapan yang lebih rendah. | Keputusan aritmetik yang sederhana menghasilkan lebih banyak kecekapan. |
| 6. | Kelajuan | Penggunaan operasi pendaraban dan pembahagian memerlukan banyak masa untuk proses pengiraannya. | Penggunaan operasi penambahan dan penolakan mengambil masa yang lebih rendah daripada DDA. |
| 7. | Ketepatan | Ia kurang tepat. | Ia lebih tepat. |
| 8. | Bulat | Ia menggunakan nilai-nilai sebenar dan tidak pernah melupuskan nilai-nilai. | Ia melupuskan nilai kepada nilai integer yang terdekat. |
| 9. | Keupayaan menggambar | Ia mampu menarik garis, lingkaran, dan lengkung tetapi dengan ketepatan yang lebih rendah. Kita juga boleh menarik segitiga dan poligon dengan algoritma ini. | Ia mampu menarik garis, lingkaran, dan lengkung dengan kecekapan yang lebih tinggi. Segitiga dan poligon juga boleh ditarik dengan algoritma ini. |
| 10. | Kos pengiraan | Ia mahal kerana ia melibatkan pembulatan juga. | Penggunaan algoritma Bresenham lebih murah daripada DDA. |
| 11. | Algoritma yang dioptimumkan | Ia bukan algoritma yang dioptimumkan | Ia adalah algoritma yang dioptimumkan. |
Kami telah menangani setiap kemungkinan yang mungkin antara algoritma DDA dan Bresenham. Ia mungkin kelihatan berulang-ulang tetapi terdapat beberapa alasan yang sah untuk menyebut perkara itu sekali lagi dan anda akan mengetahui apabila anda memahami sepenuhnya. Sekiranya anda masih merasakan ada kekaburan, sila tinggalkan komen kami. Marilah kita belajar bersama dengan berkongsi pengetahuan yang betul!
