DDA linkový algoritmus

Algoritmus čáry DDA [1] rastruje úsečku mezi dvěma danými body pomocí výpočtů s plovoucí desetinnou čárkou nebo celých čísel .

Algoritmus

Nechť segment je dán skutečnými souřadnicemi konců ; . Rastrové ( celočíselné ) souřadnice koncových bodů se stanou zaokrouhlenými hodnotami počátečních souřadnic: , ; , [2] . $(x_{1},y_{1})$ $(x_{2},y_{2})$ $x_{{{\mathrm {start}}}}=\operatorname {round}(x_{1})$ $y_{{{\mathrm {start}}}}=\jméno operátora {round}(y_{1})$ $x_{{{\mathrm {end}}}}=\operatorname {round}(x_{2})$ $y_{{{\mathrm {end}}}}=\jméno operátora {round}(y_{2})$

Větší číslo nebo , zvýšené o 1, se bere jako počet kroků rasterizačního cyklu. $(x_{({\mathrm {konec))))-x_{{{\mathrm {začátek)))))$ $(y_{({\mathrm {konec))))-y_{({\mathrm {začátek)))))$ $L$

Na začátku cyklu jsou pomocné reálné proměnné a přiřazeny počáteční souřadnice začátku segmentu: ; . V každém kroku cyklu jsou tyto reálné proměnné inkrementovány ; . Rastrové souřadnice vytvořené v každém kroku jsou výsledkem zaokrouhlení odpovídajících skutečných hodnot a . $X$ $y$ $x=x_{1}$ $y=y_{1}$ $(x_{{{\mathrm {end}}}}-x_{{{\mathrm {start}}}})/L$ $(y_{{{\mathrm {end}}}}-y_{{{\mathrm {start}}}})/L$ $X$ $y$

Použití výpočtů s reálnými čísly a pouze jedno použití zaokrouhlení pro konečné získání hodnoty rastrové souřadnice určuje vysokou přesnost a nízkou rychlost algoritmu.

K rastrování kruhů se používá upravený algoritmus DDA-line.

Poznámky

↑ Zkratka DDA v názvu tohoto algoritmu počítačové grafiky pochází z angličtiny. digitální diferenciální analyzátor - digitální diferenciální analyzátor .
↑ Obecně řečeno, pokud jsou skutečné souřadnice konců segmentu uvedeny v nějakém logickém souřadnicovém systému, pak jsou odpovídající rastrové souřadnice určeny na základě pravidel přepočtu stanovených pro konkrétní dvojici souřadnicových systémů: logický a rastrový.

Viz také

Literatura

Rogers D. Algoritmické základy počítačové grafiky . - M .: Mir, 1989. - S. 50 -54. — ISBN 5-03-000476-9 .

Odkazy

Chirikov SV Algoritmy počítačové grafiky (Metody rasterizace křivek). Učebnice - Petrohrad: SPbGITMO (TU), 2001. - 120 s.
Rastrování segmentů. DDA-line algoritmus.
McCrea PG, Baker PW Na generování kruhu DDA pro počítačovou grafiku. IEEE Trans. na počítačích. - 1975. - V.C-24. - S. 1109-1110