Rozdiel medzi DDA a Bresenhamovým algoritmom

Digitálny diferenciálny algoritmus (DDA) a Bresenhamov algoritmus sú algoritmy na kreslenie digitálnych čiar a používajú sa v počítačovej grafike na kreslenie obrázkov. Predtým sme na výpočet pixelov používali analytické analyzátory, čím sa umožnilo kreslenie čiar. Tieto analytické metódy však nie sú také presné ako digitálne metódy, ktoré s použitím týchto digitálnych algoritmov teraz a rovnako ako v každej oblasti, vymýšľame aj metódy vyššej kvality v počítačovej grafike. Vynález týchto algoritmov je dokonalým príkladom. Skôr ako budeme pokračovať, pozrime sa na koncept týchto algoritmov. Aj keď sa zdá, že je mimo rozsahu našej diskusie, je nevyhnutné poukázať na základné rozdiely medzi nimi. Ak ste s algoritmom skutočne oboznámení, môžete prejsť na skutočné rozdiely, ktoré sa nachádzajú na konci tejto stránky.

Čo je to digitálny diferenciálny algoritmus (DDA)?

DDA sa väčšinou používa na kreslenie čiar v počítačovej grafike a používa skutočné hodnoty pri predpovedaní ďalších hodnôt pixlov. Predpokladajme počiatočnú hodnotu pixla ako (X0, Y0) (X0, Y0) a cieľový pixel ako (X1, Y1) (X1, Y1). Naučíme sa, ako vypočítať cieľové hodnoty pixlov zo známej hodnoty pixelov (X0, Y0) (X0, Y0), ako je uvedené nižšie.

Ako vypočítať hodnotu cieľového bodu pomocou DDA?

Krok 1: Tu máme vstup (X0, Y0) (X0, Y0) a mali by sme zistiť, či priamka beží rovnobežne s osou x alebo osou y. Aby sme to našli, vypočítajme teraz rozdiel medzi počiatočnými a cieľovými hodnotami pixlov.

dx = X1 - X0

dy = Y1 - Y0

Krok 2: Teraz sme zistili rozdiel a mali by sme nakresliť čiaru pozdĺž osi x, ak je „dx“ nula, inak by sme mali nakresliť čiaru rovnobežnú s osou y. Toto je skutočný výpočet z hľadiska počítačového jazyka.

if (absolútne (dx)> absolútne (dy))

Kroky = absolútne (dx);

inak

Kroky = absolútne (dy);

Krok 3: Teraz je čas určiť skutočnú „x“ súradnicu alebo „y“ hodnoty súradníc pixelov, aby ste mohli nakresliť čiaru.

X prírastok = dx / (float) kroky;

Prírastok Y = kroky dy / (float);

Krok 4: Toto sa musí počítať, až kým nedosiahneme cieľový pixel. Pri výpočte algoritmus DDA zaokrúhľuje hodnotu pixla na najbližšiu celočíselnú hodnotu. Tu je ukážka kódu toho, o čom sme diskutovali teraz.

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

x = x + prírastok X;

y = y + Y prírastok;

putpixel (kolo (x), kolo (y));

S DDA sme nakreslili čiaru a teraz sa presunieme k Bresenhamu!

Čo je Bresenhamov algoritmus?

Je to tiež algoritmus digitálneho kreslenia čiar, ktorý vynašiel Bresenham v roku 1962, a preto dostal rovnaké meno. Tento algoritmus je presnejší a použil odčítanie a sčítanie na výpočet hodnoty pixlov pri kreslení čiary. Presnosť Bresenhamovho algoritmu je spoľahlivá aj pri kreslení kriviek a kruhov. Pozrime sa, ako tento algoritmus funguje.

Krok 1: Bresenhamove algoritmy predpokladajú počiatočnú súradnicu pixlov ako (x_{a + 1}, y).

Krok 2: Automaticky vypočíta nasledujúcu hodnotu pixla ako (x_{a + 1}, y_{a + 1}), Tu „a“ je inkrementálna hodnota a algoritmus ju vypočíta pridaním alebo odčítaním rovníc, ktoré vytvoril.

Tento algoritmus počíta presné hodnoty bez zaokrúhľovania a tiež vyzerá ľahšie!

Numerický príklad Bresenhamovho algoritmu:

Pozrime sa teraz na body (0,0) a (-8, -4) a pomocou Bresenhamovho algoritmu nakreslite čiaru medzi týmito bodmi..

Dané údaje (x1, y1) = (0, 0) a (x2, y2) = (-8, -4).

Vypočítajme teraz diferenciálne hodnoty.

Ax = x2-x1 = -8-0 = 8

Preto inkrementálna hodnota pre x = ∆x / x2 = 8 / -8 = -1.

? Y = y2-y1 = -4-0 = 4

Preto inkrementálna hodnota pre y = ∆y / y2 = 4 / -4 = -1.

Premenná rozhodnutia = e = 2 * (∆y) - (∆x)

Preto e = 2 * (4) - (8) = 8-8 = 0

Pri vyššie uvedenom výpočte si zoberieme do úvahy výsledné hodnoty. Hodnoty súradníc y sú upravené na základe rozhodovacej premennej a my tu iba ignorujeme jej výpočet.

pixel	X	y	Premenná rozhodnutia
(0,0)	0	0	0
(-1,0)	-1	0	Hodnota
(-2, -1)	-2	-1	0
(-3, -1)	-3	-1	Hodnota
(-4, -2)	-4	-2	0
(-5, -2)	-5	-2	Hodnota
(-6, -3)	-6	-3	0
(-7, -3)	-7	-3	Hodnota
(-8, -4)	-8	-4	0

Rozdiely medzi DDA a Bresenhamovým algoritmom:

Aritmetický výpočet:

DDA používa pri výpočtoch skutočné hodnoty s využitím plávajúcich bodov. Hodnoty nasledujúceho pixla alebo bodu sa určia pomocou diferenciálnych rovníc

Prírastok X = dx / (float) krokov

Prírastok Y = kroky dy / (float)

Tu sa nepoužívajú žiadne pevné konštanty, ale v Bresenhamovom algoritme sa v aritmetických výpočtoch používajú pevné body. Na rozdiel od DDA používa Bresenhamov algoritmus celé číslo.

Typ použitej operácie:

DDA rieši diferenciálne rovnice pomocou násobenia a delenia. Môžete si to všimnúť tu, X prírastok = dx / (float) krokov. Bresenhamov algoritmus používa operácie sčítania a odčítania a to isté si môžete všimnúť tu v nasledujúcej rovnici výpočtu hodnoty pixelov (x_{a + 1}, y_{a + 1}). Aritmetika je v Bresenhame jednoduchšia v porovnaní s DDA.

účinnosť:

Ako sme už diskutovali, Bresenhamov algoritmus používa jednoduchšiu aritmetiku ako DDA a vedie k efektívnym výsledkom.

rýchlosť: Pretože DDA používa celé čísla s pohyblivou rádovou čiarkou spolu s operáciami množenia a delenia, je pomerne pomalší, zatiaľ čo Bresenhamov algoritmus používa iba celé aritmetické číslo spolu so sčítaním a odčítaním. To výrazne skracuje čas potrebný na jeho výpočty, a teda rýchlejšie ako DDA.
presnosť: Aj keď DDA používa hodnoty s pohyblivou rádovou čiarkou, presnosť DDA nie je tak lepšia ako Bresenhamova. Tento koncept ovplyvňuje celý rad faktorov, a preto je Bresenham's presnejší ako DDA.
Zaokrúhľovanie: Stačí sa pozrieť na výpočet DDA tu.

Prírastok X = dx / (float) krokov

Môžete si všimnúť 'float', a preto nezaokrúhľuje hodnoty, zatiaľ čo Bresenhamov algoritmus zaokrúhľuje hodnoty na najbližšie celé číslo. Použité hodnoty sú preto v Bresenhamovom algoritme jednoduchšie.

Čo to kreslí?

DDA je schopný kresliť kruhy a krivky mimo kresliacich čiar. Bresenhamov algoritmus je tiež schopný nakresliť všetky vyššie uvedené a jeho presnosť je skutočne vyššia ako u DDA. Podobne by Bresenhamov algoritmus mohol prísť s účinnými krivkami, ako sú tie, ktoré vytvára DDA. Oba algoritmy dokážu tiež kresliť trojuholníky a polygóny.

Čo je drahé?

Keďže DDA zahŕňa aj zaokrúhlenie, je to drahé ako použitie Bresenhamovho algoritmu.

Čo je optimalizovaný algoritmus?

Z našej diskusie je zrejmé, že Bresenhamov algoritmus je optimalizovaný z hľadiska rýchlosti, nákladov a využívania operácií..

Pozrime sa na rozdiely v tabuľkovej podobe.

S.No	Rozdiely v%	Digitálny diferenciálny algoritmus	Bresenhamov algoritmus
1.	Prečo meno?	Len preto, že išlo o digitálnu implementáciu rovníc, dostala meno.	Vynašiel ho J.E. Bresenham v roku 1962 a odtiaľ názov.
2.	výpočty	Zahŕňa to tvrdšie výpočty.	Použité výpočty sú skutočne jednoduchšie.
3.	Druhy použitých operácií	Využívalo násobenia a delenia. Vzorové diferenciálne rovnice, ktoré sa tu používajú, sú kroky Xincrement = dx / (float), Yincrement = dy / (float) kroky.	Využíva prírastky a odčítania. Výpočet vzorky tu možno označiť ako (x_{a + 1}, y_{a + 1}).
4.	Aritmetické výpočtové hodnoty	Používa hodnoty s pohyblivou rádovou čiarkou.	Používa iba celočíselné hodnoty.
5.	efektívnosť	Komplexné aritmetické výsledky vedú k menšej účinnosti.	Jednoduchšie aritmetické výsledky vedú k väčšej účinnosti.
6.	rýchlosť	Použitie operácií násobenia a delenia si vyžaduje veľa času na výpočtové procesy.	Použitie operácií sčítania a odčítania trvá kratšie ako DDA.
7.	presnosť	Je menšia presnosť.	Je to presnejšie.
8.	Zaokrúhľovanie	Používa skutočné hodnoty a nikdy zaokrúhľuje hodnoty.	Zaokrúhľuje hodnoty na najbližšie celé čísla.
9.	Schopnosť kreslenia	Je schopný kresliť čiary, kruhy a krivky, ale s menšou presnosťou. Týmto algoritmom dokážeme dokonca kresliť trojuholníky a polygóny.	Je schopný kresliť čiary, kruhy a krivky s väčšou účinnosťou. Pomocou tohto algoritmu je možné tiež kresliť trojuholníky a polygóny.
10.	Náklady na výpočty	Je to drahé, pretože zahŕňa aj zaokrúhlenie.	Použitie Bresenhamovho algoritmu je lacnejšie ako DDA.
11.	Optimalizovaný algoritmus	Nejde o optimalizovaný algoritmus	Je to optimalizovaný algoritmus.

Zaoberali sme sa všetkými možnými rozdielmi medzi DDA a Bresenhamovým algoritmom. Môže sa to zdať dokonca opakujúce sa, existuje však nejaký platný dôvod na to, aby ste sa o týchto bodoch znova zmienili a vedeli by ste, keď to úplne pochopíte. Ak máte stále pocit, že nejasnosti existujú, zanechajte nám prosím komentár. Učme sa spolu zdieľaním správnych znalostí!

Protokoly a formáty