Protokol dan format

Perbezaan antara algoritma DDA dan Bresenham

Perbezaan antara algoritma DDA dan Bresenham

Algoritma Pembezaan Digital (DDA) dan algoritma Bresenhams adalah algoritma lukisan garis digital dan digunakan dalam grafik komputer untuk menarik gambar. Sebelum ini, kami menggunakan penganalisis analitik untuk mengira piksel dan dengan itu lukisan garis dimungkinkan. Tetapi kaedah analisis ini tidak tepat seperti kaedah digital yang dengan penggunaan algoritma digital ini sekarang dan seperti setiap bidang, kami telah mencipta kaedah kualiti yang lebih tinggi dalam grafik komputer juga. Penciptaan algoritma ini adalah contoh yang sempurna.  Sebelum kita meneruskan, marilah kita melihat konsep di sebalik algoritma ini. Walaupun ia kelihatan seperti skop perbincangan kami, adalah penting untuk menunjukkan perbezaan asas antara kedua -dua. Sekiranya anda benar -benar biasa dengan algoritma, anda boleh melompat ke perbezaan sebenar yang terletak di hujung halaman ini.

Apakah Algoritma Pembezaan Digital (DDA)?

DDA kebanyakannya digunakan untuk melukis garis dalam grafik komputer dan menggunakan nilai sebenar sambil meramalkan nilai piksel seterusnya. Marilah kita menganggap nilai piksel awal sebagai (x0, y0) (x0, y0) dan piksel destinasi sebagai (x1, y1) (x1, y1). Kami akan belajar bagaimana untuk mengira nilai piksel destinasi dari nilai piksel yang diketahui (x0, y0) (x0, y0) seperti di bawah.

  • Cara mengira nilai titik tujuan menggunakan DDA?

Langkah 1: Di sini kita mempunyai input (x0, y0) (x0, y0) dan kita harus mengenal pasti sama ada garis berjalan selari dengan paksi x atau paksi y. Untuk mencari itu, marilah kita sekarang mengira perbezaan antara nilai piksel awal dan destinasi.

dx = x1 - x0

dy = y1 - y0

Langkah-2: Sekarang, kami telah mengenal pasti perbezaannya dan kita harus melukis garis di sepanjang paksi x jika 'dx' adalah sifar sebaliknya, kita harus melukis garis 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 'x' sebenar atau 'y' menyelaraskan nilai piksel untuk melukis garis.

X kenaikan = dx / (float) langkah;

Y Peningkatan = Dy / (Float) Langkah;

Langkah-4: Ini mesti dikira sehingga kita mencapai piksel destinasi. Algoritma DDA melengkapkan nilai piksel kepada nilai integer terdekat semasa melakukan pengiraan. Inilah contoh kod dari apa yang telah kita bincangkan sekarang.

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

x = x + x kenaikan;

y = y + y kenaikan;

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

Kami selesai dengan melukis garis menggunakan DDA dan marilah kita beralih ke Bresenham sekarang!

Apakah algoritma Bresenham?

Ia juga merupakan algoritma lukisan garis digital dan dicipta oleh Bresenham pada tahun 1962 dan itulah sebabnya ia mendapat nama yang sama. Algoritma ini lebih tepat dan ia menggunakan penolakan & tambahan untuk mengira nilai piksel semasa melukis garis. Ketepatan algoritma Bresenham boleh dipercayai semasa melukis lengkung & lingkaran juga. Mari kita lihat 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 menambahkan atau menolak persamaan yang telah dibentuk.

Algoritma ini mengira nilai yang tepat tanpa pembulatan dan kelihatan lebih mudah juga!

  • Contoh berangka algoritma Bresenham:

Marilah kita pertimbangkan mata (0,0) dan (-8, -4) dan marilah kita melukis garis antara mata ini menggunakan algoritma Bresenham.

Diberi data, (x1, y1) = (0, 0) dan (x2, y2) = (-8, -4).

Marilah kita mengira nilai pembezaan 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.

Pembolehubah Keputusan = E = 2*(Δy)-(Δx)

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

Dengan pengiraan di atas, marilah kita menabur nilai yang dihasilkan. Nilai koordinat Y diselaraskan berdasarkan pemboleh ubah keputusan dan kami 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 perhitungannya dengan penggunaan titik terapung. Nilai piksel atau titik seterusnya ditentukan dengan persamaan pembezaan

X kenaikan = dx / (float) Langkah

Y Peningkatan = Dy / (Float) Langkah

Di sini tiada pemalar tetap digunakan tetapi di titik tetap algoritma Bresenham digunakan dalam perhitungan aritmetik. Algoritma Bresenham menggunakan aritmetik integer, tidak seperti DDA.

  • Jenis operasi yang digunakan:

DDA menyelesaikan persamaan pembezaan dengan operasi pendaraban dan pembahagian. Anda boleh melihat perkara yang sama di sini, langkah x kenaikan = dx / (terapung). Algoritma Bresenham menggunakan operasi tambahan dan penolakan dan anda dapat melihat yang 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 hasil yang cekap.

  • Kelajuan: Memandangkan DDA menggunakan bilangan bulat titik terapung bersama -sama dengan operasi pendaraban & bahagian, ia agak perlahan manakala algoritma Bresenham menggunakan aritmetik integer hanya bersama dengan penambahan & penolakan sahaja. Ini mengurangkan masa yang diambil untuk pengiraannya dan oleh itu ia lebih cepat daripada DDA.
  • Ketepatan: Walaupun DDA menggunakan nilai titik terapung, ketepatan DDA tidak lebih baik seperti Bresenham. Pelbagai faktor mempengaruhi konsep ini dan oleh itu, Bresenham lebih tepat daripada DDA.
  • Membundarkan: Lihat sahaja pengiraan DDA di sini.

X kenaikan = dx / (float) Langkah

Anda dapat melihat 'terapung' dan oleh itu ia tidak melengkapkan nilai -nilai sedangkan algoritma Bresenham melengkapkan nilai -nilai ke integer terdekat. Oleh itu, nilai yang digunakan adalah lebih mudah dalam algoritma Bresenham.

  • Apa yang menariknya?

DDA mampu melukis bulatan dan lengkung selain dari garis lukisan. Algoritma Bresenham juga mampu melukis semua yang disebutkan di atas dan ketepatannya benar -benar lebih tinggi daripada DDA. Begitu juga, algoritma Bresenham boleh menghasilkan lengkung yang cekap daripada yang dihasilkan oleh DDA. Kedua -dua algoritma boleh menarik segitiga dan poligon juga.

  • Yang mahal?

Sebagai DDA termasuk pembulatan juga, ia mahal daripada penggunaan algoritma Bresenham.

  • Yang merupakan algoritma yang dioptimumkan?

Dari perbincangan kami di atas, sangat jelas bahawa algoritma Bresenham adalah satu yang dioptimumkan dari segi kelajuan, kos, dan penggunaan operasi.

Mari kita lihat perbezaan dalam bentuk jadual.

S.Tidak Perbezaan dalam Algoritma pembezaan digital Algoritma Bresenham
1. Mengapa nama itu? Hanya kerana ia adalah pelaksanaan digital persamaan, ia telah mendapat namanya. Ia dicipta oleh j.E. Bresenham pada tahun 1962 dan oleh itu namanya.
2. Pengiraan Ia melibatkan pengiraan yang lebih sukar. Pengiraan yang digunakan adalah lebih mudah.
3. Jenis operasi yang digunakan Ia menggunakan pendaraban dan bahagian. Persamaan pembezaan sampel yang digunakan di sini ialah langkah xincrement = dx / (terapung),

Langkah -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 titik terapung. Ia hanya menggunakan nilai integer.
5. Kecekapan Hasil aritmetik kompleks dalam kecekapan yang lebih rendah. Aritmetik yang lebih mudah menghasilkan lebih banyak kecekapan.
6. Kelajuan Penggunaan operasi pendaraban dan bahagian memerlukan banyak masa untuk proses pengiraannya. Penggunaan operasi penambahan dan penolakan mengambil masa yang lebih rendah daripada DDA.
7. Ketepatan Ia lebih rendah dalam ketepatan. Lebih tepat.
8. Membundarkan Ia menggunakan nilai sebenar dan tidak pernah membatalkan nilai. Ia melengkapkan nilai ke nilai integer terdekat.
9. Keupayaan lukisan Ia mampu melukis garis, bulatan, dan lengkung tetapi dengan ketepatan yang lebih rendah. Kita juga boleh menarik segitiga dan poligon dengan algoritma ini. Ia mampu melukis garis, bulatan, dan lengkung dengan kecekapan yang lebih tinggi. Segitiga dan poligon juga mungkin 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 perbezaan yang mungkin antara DDA dan algoritma Bresenham. Ia mungkin kelihatan berulang -ulang tetapi ada sebab yang sah untuk menyebut mata -mata itu lagi dan anda akan mengetahui apabila anda memahaminya sepenuhnya. Sekiranya anda masih merasakan bahawa terdapat kekaburan, sila tinggalkan komen kami. Marilah kita belajar bersama dengan berkongsi pengetahuan yang betul!