DDA linjealgoritm

DDA-linjealgoritmen [1] rastrar linjesegmentet mellan två givna punkter med hjälp av flyttals- eller heltalsberäkningar .

Algoritm

Låt segmentet ges av ändarnas reella koordinater ; . Raster ( heltal ) koordinater för slutpunkterna blir avrundade värden för de initiala koordinaterna: , ; , [2] . $(x_{1},y_{1})$ $(x_{2},y_{2})$ $x_{{{\mathrm {start}}}}=\operatörsnamn {runda}(x_{1})$ $y_{{{\mathrm {start}}}}=\operatörsnamn {runda}(y_{1})$ $x_{{{\mathrm {end}}}}=\operatörsnamn {runda}(x_{2})$ $y_{{{\mathrm {end}}}}=\operatörsnamn {runda}(y_{2})$

Det större antalet, eller , ökat med 1 tas som antalet steg i rastreringscykeln. $(x_{({\mathrm {slut))))-x_{{{\mathrm {start))))))$ $(y_{({\mathrm {slut))))-y_{({\mathrm {start)))))$ $L$

I början av cykeln tilldelas de reella hjälpvariablerna och de initiala koordinaterna för början av segmentet: ; . Vid varje steg i slingan inkrementeras dessa reella variabler ; . Rasterkoordinaterna som produceras vid varje steg är resultatet av avrundning av motsvarande verkliga värden och . $x$ $y$ $x=x_{1}$ $y=y_{1}$ $(x_{{{\mathrm {end}}}}-x_{{{\mathrm {start}}}})/L$ $(y_{{{\mathrm {end}}}}-y_{{{\mathrm {start}}}})/L$ $x$ $y$

Användningen av beräkningar med reella tal och endast en enda användning av avrundning för att slutligen få värdet på rasterkoordinaten bestämmer algoritmens höga noggrannhet och låga hastighet.

En modifierad DDA-linjealgoritm används för att rastrera cirklar.

Anteckningar

↑ Förkortningen DDA i namnet på denna datorgrafikalgoritm kommer från engelskan. digital differentialanalysator - digital differentialanalysator .
↑ Generellt sett, om de verkliga koordinaterna för ändarna av segmentet anges i något logiskt koordinatsystem, så bestäms motsvarande rasterkoordinater baserat på omräkningsreglerna som fastställts för ett speciellt par av koordinatsystem: logiskt och skärm.

Se även

Litteratur

Rogers D. Algoritmiska grunder för datorgrafik . - M . : Mir, 1989. - S. 50 -54. — ISBN 5-03-000476-9 .

Länkar

Chirikov SV Algoritmer för datorgrafik (metoder för rastrering av kurvor). Lärobok - St Petersburg: SPbGITMO (TU), 2001. - 120 sid.
Segmentrasterisering. DDA-linjealgoritm.
McCrea PG, Baker PW Om DDA-cirkelgenerering för datorgrafik. IEEE Trans. på datorer. - 1975. - V.C-24. - P. 1109-1110