Digitální diferenciální analyzátor (grafický algoritmus) - Digital differential analyzer (graphics algorithm)

v počítačová grafika, a digitální diferenciální analyzátor (DDA) je hardware nebo software používaný pro interpolace z proměnné přes interval mezi počátečním a koncovým bodem. DDA se používají pro rasterizace čar, trojúhelníků a mnohoúhelníků. Mohou být rozšířeny na nelineární funkce, jako je správné mapování textury perspektivy, kvadratické křivky a projíždějící voxely.

Ve své nejjednodušší implementaci pro lineární případy jako např řádky, algoritmus DDA interpoluje hodnoty v intervalu výpočtem pro každé x_i rovnice x_i = x_{i − 1} + 1, r_i = y_{i − 1} + m, kde m je sklon linky. Tento sklon lze vyjádřit v DDA následovně:

${displaystyle m = {frac {y_ {m {end}} - y_ {m {start}}} {x_ {m {end}} - x_ {m {start}}}}}$

Ve skutečnosti by rovnice měly splňovat všechny dva po sobě následující body (x, y) ležící na tomto úsečce.

Výkon

Metodu DDA lze implementovat pomocí plovoucí bod nebo celé číslo aritmetický. Nativní implementace s plovoucí desetinnou čárkou vyžaduje jedno přidání a jednu operaci zaokrouhlování na interpolovanou hodnotu (např. Souřadnice x, y, hloubka, barevná složka atd.) A výsledek výstupu. Tento proces je efektivní pouze tehdy, když FPU s rychlým přidáním a zaokrouhlováním bude k dispozici.

The pevný bod celočíselná operace vyžaduje dvě přidání na výstupní cyklus a v případě přetečení dílčí části jeden další přírůstek a odčítání. Pravděpodobnost přetečení dílčí části je úměrná poměru m interpolovaných počátečních a koncových hodnot.

DDA jsou velmi vhodné pro implementaci hardwaru a lze je pipetovat pro maximální propustnost.

Algoritmus

Lineární DDA začíná výpočtem menšího z dy nebo dx pro jednotkový přírůstek druhého. Poté je v jedné souřadnici vzorkována čára v jednotkových intervalech a pro druhou souřadnici jsou určeny odpovídající celočíselné hodnoty nejblíže dráze čáry.

Pokud vezmeme v úvahu přímku s kladným sklonem, je-li sklon menší nebo roven 1, vzorkujeme v intervalech jednotky x (dx = 1) a počítáme postupné hodnoty y jako

${displaystyle y_ {k + 1} = y_ {k} + m}$

${displaystyle x_ {k + 1} = x_ {k} +1}$

Dolní index k přebírá celočíselné hodnoty začínající od 0, pro 1. bod a zvyšuje se o 1, dokud není dosaženo koncového bodu. Y hodnota je zaokrouhlena na nejbližší celé číslo, aby odpovídalo pixelu obrazovky.

U přímek se sklonem větším než 1 obrátíme roli xay, tj. Vzorkujeme na dy = 1 a vypočítáme po sobě jdoucí hodnoty x jako

${displaystyle x_ {k + 1} = x_ {k} + {frac {1} {m}}}$

${displaystyle y_ {k + 1} = y_ {k} +1}$

Podobné výpočty se provádějí k určení pozic obrazových bodů podél linie se záporným sklonem. Pokud je tedy absolutní hodnota sklonu menší než 1, nastavíme dx = 1 if ${displaystyle x_ {m {start}}$ tj. počáteční extrémní bod je vlevo.

Program

Program algoritmu DDA v Turbo C ++:

 1 #zahrnout <graphics.h> 2  3 #zahrnout <iostream.h> 4 #zahrnout <math.h> 5 #zahrnout <dos.h> 6 #zahrnout <conio.h> 7  8 prázdnota hlavní( ) 9 {10   plovák X, y, x1, y1, x2, y2, dx, dy, krok;11   int i, gd = ZJISTIT, gm;12   Initgraph(&gd, &gm, "C:TURBOC3BGI ");13   14   cout << "Zadejte hodnotu x1 a y1:";15   cin >> x1 >> y1;16   cout << "Zadejte hodnotu x2 a y2:";17   cin >> x2 >> y2;18   19   dx = (x2 - x1);20   dy = (y2 - y1);21   -li (břišní svaly(dx) >= břišní svaly(dy))22     krok = břišní svaly(dx);23   jiný24     krok = břišní svaly(dy);25   dx = dx / krok;26   dy = dy / krok;27   X = x1;28   y = y1;29   i = 1;30   zatímco (i <= krok) {31     putpixel(X, y, 5);32     X = X + dx;33     y = y + dy;34     i = i + 1;35     zpoždění(100);36   }37   getch();38   closegraph();39 }

Viz také

• Bresenhamův liniový algoritmus je algoritmus pro vykreslování řádků.
• algoritmus přírůstkové chyby
• Lineární algoritmus Xiaolin Wu je algoritmus pro vyhlazení řádků

Reference

http://www.museth.org/Ken/Publications_files/Museth_SIG14.pdf

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Červen 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

• Alan Watt: 3D počítačová grafika, 3. vydání 2000, s. 184 (rastrování hran). ISBN  0-201-39855-9