Razlika između DDA i Bresenhamovog algoritma
Share
Digitalni diferencijalni algoritam (DDA) i Bresenhamsov algoritam algoritmi su za crtanje digitalnih linija i koriste se u računalnoj grafici za crtanje slika. Prije smo koristili analitičke analizatore za izračunavanje piksela i na taj način su omogućeni crteži linija. Ali ove analitičke metode nisu tako precizne kao digitalne metode koje pomoću ovih digitalnih algoritama sada i kao i na svakom polju izmišljamo kvalitetnije metode i u računalnoj grafici. Izum ovih algoritama je savršen primjer. Prije nego što nastavimo, pogledajmo koncept koji stoji iza ovih algoritama. Iako se čini da nije u dosegu naše rasprave, ključno je istaknuti osnovne razlike između to dvoje. Ako ste doista upoznati s algoritmima, možete skočiti do stvarnih razlika koje se nalaze na kraju ove stranice.
Što je digitalni diferencijalni algoritam (DDA)?
DDA se uglavnom koristi za crtanje linija u računalnoj grafici i koristi stvarne vrijednosti pri predviđanju sljedeće vrijednosti piksela. Pretpostavimo da je početna vrijednost piksela kao (X0, Y0) (X0, Y0), a odredišna piksela kao (X1, Y1) (X1, Y1). Naučit ćemo kako izračunati odredišne vrijednosti piksela iz poznate vrijednosti piksela (X0, Y0) (X0, Y0) kao niže.
- Kako izračunati vrijednost odredišne točke pomoću DDA?
Korak 1: Ovdje imamo ulaz (X0, Y0) (X0, Y0) i trebali bismo identificirati radi li linija paralelno s osi x ili y. Da bismo to utvrdili, izračunajmo sada razliku između početne i odredišne vrijednosti piksela.
dx = X1 - X0
dy = Y1 - Y0
Korak 2: Sada smo identificirali razliku i trebali bismo povući crtu duž osi x ako je 'dx' jednaka nuli, trebali bismo povući liniju paralelnu s osi y. Evo stvarnog izračuna u odnosu na računalni jezik.
ako je (apsolutno (dx)> apsolutno (dy))
Koraci = apsolutni (dx);
drugo
Koraci = apsolutni (dy);
Korak 3: Sada je vrijeme da se utvrdi stvarna 'x' koordinata ili 'y' vrijednosti piksela koordinate kako bi se povukla crta.
X-korak = dx / (plutajući) koraci;
Y priraštaj = dy / (plutajući) koraci;
Korak-4: To se mora izračunati dok ne dođemo do odredišnog piksela. Algoritam DDA zaokružuje vrijednost piksela na najbližu cjelobrojnu vrijednost tijekom računanja. Evo uzorka koda onoga što smo sada raspravljali.
Za (int v = 0; v < Steps; v++)
x = x + X priraštaj;
y = y + Y priraštaj;
putpixel (Round (x), Round (y));
Završili smo s crtanjem crteća pomoću DDA i neka se prijeđe na Bresenhamovu!
Što je Bresenhamov algoritam?
To je i algoritam za crtanje digitalnih linija, a izumio ga je Bresenham 1962. godine i zbog toga je dobio isto ime. Ovaj je algoritam precizniji i koristio je oduzimanje i zbrajanje za računanje vrijednosti piksela tijekom crtanja crte. Točnost Bresenhamovog algoritma pouzdana je i pri crtanju krivulja i krugova. Pogledajmo kako funkcionira ovaj algoritam.
Korak 1: Bresenhamovi algoritmi pretpostavljaju početnu koordinatu piksela kao (xa + 1, y).
Korak 2: Automatski izračunava sljedeću vrijednost piksela kao (x)a + 1, ya + 1), Ovdje je "a" inkrementalna vrijednost i algoritam je izračunava dodavanjem ili oduzimanjem jednadžbi koje je stvorio.
Ovaj algoritam izračunava točne vrijednosti bez zaokruživanja, a izgleda i lakše!
- Numerički primjer Bresenhamovog algoritma:
Razmotrimo sada točke (0,0) i (-8, -4) i povucimo crtu između tih točaka pomoću Bresenhamovog algoritma.
S obzirom na podatke, (x1, y1) = (0, 0) i (x2, y2) = (-8, -4).
Sada ćemo izračunati diferencijalne vrijednosti kao što je dolje navedeno.
Δx = x2-x1 = -8-0 = 8
Stoga je inkrementalna vrijednost za x = ∆x / x2 = 8 / -8 = -1.
Δy = Y2-y1 = -4-0-4
Stoga je inkrementalna vrijednost za y = ∆y / y2 = 4 / -4 = -1.
Varijabla odluke = e = 2 * (∆y) - (∆x)
Stoga je e = 2 * (4) - (8) = 8-8 = 0
Pomoću gornjeg izračuna izračunajmo rezultirajuće vrijednosti. Vrijednosti y-koordinate podešavaju se na temelju varijable odluke, a mi ovdje samo ignoriramo njeno izračunavanje.
| Pixel | x | y | Varijabla odluke |
| (0,0) | 0 | 0 | 0 |
| (-1,0) | -1 | 0 | Vrijednost |
| (-2, 1) | -2 | -1 | 0 |
| (-3, 1) | -3 | -1 | Vrijednost |
| (-4, -2) | -4 | -2 | 0 |
| (-5, -2) | -5 | -2 | Vrijednost |
| (-6, -3) | -6 | -3 | 0 |
| (-7-3) | -7 | -3 | Vrijednost |
| (-8, -4) | -8 | -4 | 0 |
Razlike između DDA i Bresenhamovog algoritma:
- Aritmetički proračun:
DDA u svojim izračunima koristi stvarne vrijednosti s uporabom plutajućih točaka. Sljedeće vrijednosti piksela ili točke određuju se diferencijalnim jednadžbama
Korak X = dx / (plutajući) koraci
Korak Y = korak dy / (plutaju)
Ovdje se ne koriste fiksne konstante, ali u Bresenhamovom algoritmu su fiksne točke korištene u aritmetičkim izračunima. Bresenhamov algoritam koristi aritmetiku Integer, za razliku od DDA.
- Vrsta korištene operacije:
DDA rješava diferencijalne jednadžbe operacijama množenja i dijeljenja. To možete primijetiti i ovdje, X korak = dx / (plutajući) koraci. Bresenhamov algoritam koristi operacije dodavanja i oduzimanja i to možete primijetiti ovdje u njegovoj sljedećoj jednadžbi izračunavanja vrijednosti piksela (xa + 1, ya + 1). Aritmetika je u Bresenhamu jednostavnija u odnosu na DDA.
- učinkovitost:
Kao što smo ranije raspravljali, Bresenhamov algoritam koristi jednostavniju aritmetiku od DDA i rezultira učinkovitim rezultatima.
- Ubrzati: Kako DDA koristi brojeve s pomičnom zarezom zajedno s operacijama množenja i dijeljenja, usporedno je sporiji, dok Bresenhamov algoritam koristi samo cijelu aritmetiku zajedno sa zbrajanjem i oduzimanjem. Ovo znatno smanjuje vrijeme potrebno za njegove proračune, a samim tim i brže od DDA.
- Točnost: Iako DDA koristi vrijednosti s pomičnim zarezom, točnost DDA nije bolja od Bresenhamove. Različiti čimbenici utječu na ovaj koncept i, prema tome, Bresenhamovi su precizniji od DDA.
- Zaokruživanje: Samo pogledajte izračun DDA ovdje.
Korak X = dx / (plutajući) koraci
Mogli ste primijetiti 'plutaju' i zato on ne zaokružuje vrijednosti dok Bresenhamov algoritam zaokružuje vrijednosti na najbliži cijeli broj. Stoga su korištene vrijednosti jednostavnije u Bresenhamovom algoritmu.
- Što to crta?
DDA može crtati krugove i krivulje osim crtanja linija. Bresenhamov algoritam također je u stanju izvući sve gore spomenuto i njegova je točnost stvarno veća od DDA. Slično tome, Bresenhamov algoritam mogao bi smisliti učinkovite krivulje od onih koje je proizveo DDA. Oba algoritma mogu crtati trokute i poligone.
- Što je skupo?
Kako DDA uključuje i zaokruživanje, to je skuplje od korištenja Bresenhamovog algoritma.
- Što je optimizirani algoritam?
Iz naše gornje rasprave jasno je da je Bresenhamov algoritam optimiziran u pogledu brzine, troškova i korištenja operacija.
Pogledajmo razlike u tabelarnom obliku.
| S.No | Razlike u | Digitalni diferencijalni algoritam | Bresenhamov algoritam |
| 1. | Zašto ime? | Upravo zbog toga što je digitalna implementacija jednadžbi dobila je ime. | Izumio ga je J. E. Bresenham 1962. godine i otuda je i ime. |
| 2. | izračunavanje | To uključuje strože računanje. | Računanja koja se koriste stvarno su jednostavnija. |
| 3. | Vrste korištenih operacija | Koristila je množenja i podjele. Jednadžbe uzorka diferencijalne jednadžbe korištene ovdje su Xincrement = dx / (float) koraci, Yincrement = dy / (plutajući) koraci.
| Koristi zbrajanje i oduzimanje. Ovdje se može izračunati uzorak kao xa + 1, ya + 1). |
| 4. | Aritmetičke vrijednosti računanja | Koristi vrijednosti s pomičnim zarezom. | Koristi samo cjelobrojne vrijednosti. |
| 5. | efikasnost | Složena aritmetika rezultira u manjoj učinkovitosti. | Jednostavnija aritmetika rezultira većom učinkovitošću. |
| 6. | Ubrzati | Upotreba operacija množenja i dijeljenja zahtijeva mnogo vremena za njegove procese računanja. | Upotreba operacija zbrajanja i oduzimanja zahtijeva manje vremena nego DDA. |
| 7. | Točnost | Manje je točnosti. | Točnije je. |
| 8. | Zaokruživanje | Koristi stvarne vrijednosti i nikada ih ne zaokružuje. | Zaokružuje vrijednosti na najbliže cjelobrojne vrijednosti. |
| 9. | Sposobnost crtanja | Može crtati linije, krugove i krivulje, ali s manjom preciznošću. Pomoću ovog algoritma možemo čak i nacrtati trokute i poligone. | Moguće je crtati linije, krugove i krivulje s većom učinkovitošću. Uz pomoć ovog algoritma mogu se također nacrtati trokuti i poligoni. |
| 10. | Troškovi izračuna | Skupo je, jer uključuje i zaokruživanje. | Upotreba Bresenhamovog algoritma jeftinija je od DDA. |
| 11. | Optimizirani algoritam | To nije optimizirani algoritam | To je optimizirani algoritam. |
Bavili smo se svim mogućim razlikama između DDA-e i Bresenhamovog algoritma. Možda se čini da se ponavlja, ali postoji neki valjan razlog da te točke ponovno spominjete i da biste to saznali kada je potpuno razumijete. Ako i dalje smatrate da postoji nejasnoća, ostavite nam komentar. Naučimo zajedno dijeljenjem odgovarajućeg znanja!
