Алгоритм DDA-линии

Алгоритм DDA-линии растеризует отрезок прямой между двумя заданными точками, используя вычисления в числах с плавающей запятой или целых числах.

Алгоритм

Пусть отрезок задан вещественными координатами концов $(x_1,y_1)$; $(x_2,y_2)$. Растровыми (целочисленными) координатами концевых точек становятся округлённые значения исходных координат: $x_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}=\mathrm{round}(x_1)$, $y_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}=\mathrm{round}(y_1)$; $x_{\mathrm{e}\mathrm{n}\mathrm{d}}=\mathrm{round}(x_2)$, $y_{\mathrm{e}\mathrm{n}\mathrm{d}}=\mathrm{round}(y_2)$.

Большее по абсолютной величине число, $(x_{\mathrm{e}\mathrm{n}\mathrm{d}}-x_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}})$ или $(y_{\mathrm{e}\mathrm{n}\mathrm{d}}-y_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}})$, увеличенное на 1 принимается за количество шагов $L$ цикла растеризации.

В начале цикла вспомогательным вещественным переменным $x$ и $y$ присваиваются исходные координаты начала отрезка: $x=x_1$; $y=y_1$. На каждом шаге цикла эти вещественные переменные получают приращения $(x_{\mathrm{e}\mathrm{n}\mathrm{d}}-x_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}})/L$; $(y_{\mathrm{e}\mathrm{n}\mathrm{d}}-y_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}})/L$. Растровые же координаты, продуцируемые на каждом шаге, являются результатом округления соответствующих вещественных значений $x$ и $y$.

Применение вычислений с вещественными числами и лишь однократное использование округления для окончательного получения значения растровой координаты обусловливают высокую точность и низкое быстродействие алгоритма.

Модифицированный алгоритм DDA-линии применяется для растеризации окружностей.

См. также

• Алгоритмы построения отрезка
• Алгоритм Брезенхэма
• Алгоритм Ву

Литература

• Шаблон:Книга

Ссылки

• Чириков С. В. Алгоритмы компьютерной графики (Методы растрирования кривых). Учебное пособие — СПб: СПбГИТМО(ТУ), 2001. — 120 с.
• Растеризация отрезка. Алгоритм DDA-линии.
• McCrea P. G., Baker P. W. On DDA circle generation for computer graphics. IEEE Trans. on Computers. — 1975. — V. C-24. — P. 1109—1110