Razlika med DDA in Bresenhamovim algoritmom
Share
Digitalni diferencialni algoritem (DDA) in Bresenhamsov algoritem sta algoritma za risanje digitalnih črt in se uporabljata v računalniški grafiki za risanje slik. Prej smo za izračun pikslov uporabljali analitične analizatorje in s tem so bile možne črte risb. Toda te analitične metode niso tako natančne kot digitalne metode, ki z uporabo teh digitalnih algoritmov zdaj in kot na vsakem področju izmišljamo bolj kakovostne metode tudi v računalniški grafiki. Izum teh algoritmov je odličen primer. Preden nadaljujemo, si poglejmo koncept teh algoritmov. Čeprav se zdi, da ne spada v obseg naše razprave, je treba poudariti osnovne razlike med tema dvema. Če resnično poznate algoritme, lahko skočite na dejanske razlike, ki se nahajajo na koncu te strani.
Kaj je digitalni diferencialni algoritem (DDA)?
DDA se večinoma uporablja za risanje črt v računalniški grafiki in uporablja realne vrednosti, medtem ko napoveduje naslednje vrednosti pikslov. Predpostavimo, da je začetna vrednost slikovnih pik kot (X0, Y0) (X0, Y0) in ciljna slikovna pika kot (X1, Y1) (X1, Y1). Spoznali bomo, kako izračunati ciljne vrednosti pikslov iz znane vrednosti pikslov (X0, Y0) (X0, Y0), kot je navedeno spodaj.
- Kako izračunati vrednost ciljne točke s pomočjo DDA?
Korak 1: Tu imamo vhod (X0, Y0) (X0, Y0) in morali bi ugotoviti, ali premica poteka vzporedno z osjo x ali y. Da bi to ugotovili, izračunajmo razliko med začetno in ciljno vrednostjo slikovnih pik.
dx = X1 - X0
dy = Y1 - Y0
2. korak: Zdaj smo ugotovili razliko in morali smo potegniti črto vzdolž osi x, če je 'dx' nič, drugače bi morali potegniti črto vzporedno z osjo y. Tu je dejanski izračun glede na računalniški jezik.
če (absolutno (dx)> absolutno (dy))
Koraki = absolutni (dx);
drugače
Koraki = absolutni (dy);
3. korak: Zdaj je čas, da določimo dejanske 'x' koordinate ali 'y' vrednosti slikovnih pik, da narišemo črto.
Povečanje X = koraki dx / (float);
Povečanje Y = dy / (float) koraki;
4. korak: To je treba izračunati, dokler ne pridemo do ciljnega piksla. Algoritem DDA zaokroži vrednost pikslov na najbližjo celoštevilčno vrednost, medtem ko opravi računanje. Tu je vzorec kode, o čemer smo zdaj razpravljali.
Za (int v = 0; v < Steps; v++)
x = x + X prirast;
y = y + Y povečanje;
putpixel (Round (x), Round (y));
Končali smo z risanjem črte s pomočjo DDA in pojdimo naprej k Bresenhamovi!
Kaj je Bresenhamov algoritem?
Je tudi algoritem za risanje digitalnih linij, izumil ga je Bresenham leta 1962 in zato je dobil isto ime. Ta algoritem je natančnejši in je pri risanju črte uporabil odštevanje in seštevanje za izračun vrednosti slikovnih pik. Natančnost Bresenhamovega algoritma je zanesljiva tudi pri risanju krivulj in krogov. Poglejmo, kako deluje ta algoritem.
Korak 1: Bresenhamovi algoritmi prevzamejo začetno koordinato pikslov kot (x)a + 1, ya).
2. korak: Samodejno izračuna naslednjo vrednost piksla kot (x)a + 1, ya + 1), Tu je 'a' prirastna vrednost in algoritem jo izračuna tako, da doda ali odšteje enačbe, ki jih je oblikoval.
Ta algoritem izračuna natančne vrednosti brez zaokroževanja in izgleda tudi lažje!
- Numerični primer Bresenhamovega algoritma:
Zdaj razmislimo o točkah (0,0) in (-8, -4) in narišimo črto med temi točkami z Bresenhamovim algoritmom.
Glede na podatke, (x1, y1) = (0, 0) in (x2, y2) = (-8, -4).
Zdaj izračunajmo diferencialne vrednosti, kot so spodaj.
∆x = x2-x1 = -8-0 = 8
Zato je prirastna vrednost za x = ∆x / x2 = 8 / -8 = -1.
∆y = y2-y1 = -4-0 = 4
Zato je prirastna vrednost za y = ∆y / y2 = 4 / -4 = -1.
Spremenljivka odločitve = e = 2 * (∆y) - (∆x)
Zato je e = 2 * (4) - (8) = 8-8 = 0
Z zgornjim izračunom tabeliramo dobljene vrednosti. Vrednosti y-koordinate prilagajamo na podlagi spremenljivke odločitve in pri tem samo ignoriramo njeno izračunavanje.
| Pixel | x | y | Spremenljivka odločitve |
| (0,0) | 0 | 0 | 0 |
| (-1,0) | -1 | 0 | Vrednost |
| (-2, -1) | -2 | -1 | 0 |
| (-3, -1) | -3 | -1 | Vrednost |
| (-4, -2) | -4 | -2 | 0 |
| (-5, -2) | -5 | -2 | Vrednost |
| (-6, -3) | -6 | -3 | 0 |
| (-7, -3) | -7 | -3 | Vrednost |
| (-8, -4) | -8 | -4 | 0 |
Razlike med Algoritmom DDA in Bresenhamom:
- Aritmetični izračun:
DDA pri svojih izračunih uporablja realne vrednosti z uporabo plavajočih točk. Naslednje vrednosti pik ali točk se določijo z diferencialnimi enačbami
Korak X = koraki dx / (float)
Korak Y = koraki dy / (float)
Tu niso uporabljene fiksne konstante, v Bresenhamovem algoritmu pa se v aritmetičnih izračunih uporabljajo fiksne točke. Bresenhamov algoritem uporablja aritmetiko Integer, za razliko od DDA.
- Vrsta uporabljene operacije:
DDA rešuje diferencialne enačbe z operacijami množenja in deljenja. Tu lahko opazite isto, koraki X = dx / (float). Bresenhamov algoritem uporablja operacije seštevanja in odštevanja in isto lahko opazite tukaj v njegovi naslednji enačbi za računanje vrednosti pikslov (xa + 1, ya + 1). Aritmetika je pri Bresenhamovih enostavnejša v primerjavi z DDA.
- Učinkovitost:
Kot smo že omenili, Bresenhamov algoritem uporablja enostavnejšo aritmetiko kot DDA in prinaša učinkovite rezultate.
- Hitrost: Ker DDA uporablja cela števila s plavajočo vejico skupaj z operacijami množenja in deljenja, je razmeroma počasnejša, medtem ko Bresenhamov algoritem uporablja samo celoštevilčno aritmetiko, skupaj z dodatki in odštevanji. To znatno skrajša čas, potreben za njegove izračune, in s tem hitreje kot DDA.
- Natančnost: Čeprav DDA uporablja vrednosti s plavajočo vejico, natančnost DDA ni tako boljša kot Bresenhamova. Na ta koncept vplivajo različni dejavniki, zato so Bresenhamovi natančnejši od DDA.
- Zaokrožitev: Samo poglejte izračun DDA tukaj.
Korak X = koraki dx / (float)
Lahko bi opazili 'float' in zato ne zaokroži vrednosti, medtem ko Bresenhamov algoritem zaokroži vrednosti na najbližje celo število. Zato so uporabljene vrednosti v Bresenhamovem algoritmu preprostejše.
- Kaj potegne?
DDA lahko poleg risanja črt risuje kroge in krivulje. Bresenhamov algoritem lahko tudi nariše vse zgoraj omenjeno in njegova natančnost je resnično večja kot pri DDA. Podobno bi lahko Bresenhamov algoritem ustvaril učinkovite krivulje, kot jih je ustvaril DDA. Oba algoritma lahko tudi narišeta trikotnike in mnogokotnike.
- Kar je drago?
Ker DDA vključuje tudi zaokroževanje, je dražje od uporabe Bresenhamovega algoritma.
- Kar je optimiziran algoritem?
Iz naše zgornje razprave je jasno, da je Bresenhamov algoritem optimiziran glede hitrosti, stroškov in uporabe operacij.
Poglejmo si razlike v tabeli.
| S. št | Razlike v | Digitalni diferencialni algoritem | Bresenhamov algoritem |
| 1. | Zakaj ime? | Samo zato, ker je digitalna implementacija enačb dobila ime. | Izumil jo je J. E. Bresenham leta 1962 in od tod tudi ime. |
| 2. | Izračuni | Vključuje strožje izračune. | Uporabljeni izračuni so res preprostejši. |
| 3. | Vrste uporabljenih operacij | Uporabljala je množenja in delitve. Vzorec diferencialnih enačb, uporabljenih tukaj, so Xincrement = dx / (float) koraki, Yincrement = dy / (float) koraki.
| Uporablja seštevanja in odštevanja. Vzorčni izračun tukaj lahko označimo kot (x)a + 1, ya + 1). |
| 4. | Aritmetične vrednosti računanja | Uporablja vrednosti s plavajočo vejico. | Uporablja samo celotne vrednosti. |
| 5. | Učinkovitost | Kompleksna aritmetika povzroči manjšo učinkovitost. | Preprostejša aritmetika povzroči večjo učinkovitost. |
| 6. | Hitrost | Uporaba pomnoževalnih in delitvenih operacij zahteva veliko časa za njene računske procese. | Uporaba postopkov seštevanja in odštevanja traja manj časa kot DDA. |
| 7. | Natančnost | Točnost je manjše. | Natančneje je. |
| 8. | Zaokrožitev | Uporablja resnične vrednosti in jih nikoli ne zaokroži. | Vrednosti zaokroži na najbližje celoštevilčne vrednosti. |
| 9. | Sposobnost risanja | Znal je risati črte, kroge in krivulje, vendar z manjšo natančnostjo. S tem algoritmom lahko narišemo celo trikotnike in mnogokotnike. | Z večjo učinkovitostjo lahko riše črte, kroge in krivulje. S tem algoritmom je mogoče narisati tudi trikotnike in poligone. |
| 10. | Stroški izračunov | Je drago, saj vključuje zaokroževanje. | Uporaba Bresenhamovega algoritma je cenejša od DDA. |
| 11. | Optimiziran algoritem | To ni optimiziran algoritem | Gre za optimiziran algoritem. |
Obravnavali smo vsako možno razliko med DDA in Bresenhamovim algoritmom. Morda se zdi, da se ponavlja, vendar obstaja nekaj utemeljenih razlogov, da bi te točke znova omenili, in vedeli bi, ko jih boste popolnoma razumeli. Če še vedno menite, da obstaja dvoumnost, nam pišite komentar. Učimo se skupaj z ustreznim znanjem!
