Цифровой дифференциальный анализатор (графический алгоритм)

В компьютерной графике цифровой дифференциальный анализатор ( DDA ) — это аппаратное или программное обеспечение, используемое для интерполяции переменных в интервале между начальной и конечной точкой. DDA используются для растеризации линий, треугольников и многоугольников. Они могут быть расширены до нелинейных функций, таких как корректное отображение текстур с перспективой , квадратичные кривые и прохождение вокселей .

В своей простейшей реализации для линейных случаев, таких как линии , алгоритм DDA интерполирует значения в интервале, вычисляя для каждого x _i уравнения x _i = x _i−1 + 1, y _i = y _i−1 + m, где m — наклон линии . Этот наклон можно выразить в DDA следующим образом:

${\displaystyle m={\frac {y_{\rm {конец}}-y_{\rm {начало}}}{x_{\rm {конец}}-x_{\rm {начало}}}}}$

Фактически любые две последовательные точки, лежащие на этом отрезке прямой, должны удовлетворять уравнению.

Метод DDA может быть реализован с использованием арифметики с плавающей точкой или целочисленной арифметики. Собственная реализация с плавающей точкой требует одну операцию сложения и одну операцию округления на интерполированное значение (например, координаты x, y, глубина, цветовой компонент и т. д.) и выходной результат. Этот процесс эффективен только тогда, когда будет доступен FPU с быстрой операцией сложения и округления.

Операция с фиксированной точкой требует двух сложений на цикл вывода, а в случае переполнения дробной части — одного дополнительного приращения и вычитания. Вероятность переполнения дробной части пропорциональна отношению m интерполированных начальных/конечных значений.

DDA хорошо подходят для аппаратной реализации и могут быть конвейеризированы для максимальной пропускной способности.

Линейный DDA начинается с вычисления меньшего из dy или dx для единичного приращения другого. Затем линия выбирается с единичными интервалами в одной координате, и соответствующие целочисленные значения, ближайшие к пути линии, определяются для другой координаты.

Рассматривая линию с положительным наклоном, если наклон меньше или равен 1, мы делаем выборку с единичными интервалами x (dx=1) и вычисляем последовательные значения y как

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

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

Нижний индекс k принимает целочисленные значения, начиная с 0 для первой точки, и увеличивается на 1 до тех пор, пока не будет достигнута конечная точка. Значение y округляется до ближайшего целого числа, чтобы соответствовать пикселю экрана.

Для линий с наклоном больше 1 мы меняем роли x и y, т.е. мы делаем выборку при dy=1 и вычисляем последовательные значения x как

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

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

Аналогичные вычисления проводятся для определения позиций пикселей вдоль линии с отрицательным наклоном. Таким образом, если абсолютное значение наклона меньше 1, мы устанавливаем dx=1, если т.е. начальная крайняя точка находится слева.${\displaystyle x_{\rm {начало}}<x_{\rm {конец}}}$

Программа алгоритма DDA на C++ :

#include <graphics.h> #include <iostream.h> #include <math.h> #include <dos.h> #include <conio.h> пустая основная () { плавающий x ,  поплавок y ,  плавающий x1 , y1 ,   плавающий x2 , y2 , dx , dy , шаг ;      int i , gd = ОБНАРУЖИТЬ , gm ;      initgraph ( & gd , & gm , "C: \\ TURBOC3 \\ BGI" );    cout << "Введите значение x1 и y1: " ;   cin >> x1 >> y1 ;     cout << "Введите значение x2 и y2: " ;   cin >> x2 >> y2 ;      dx = ( x2 - x1 );     dy = ( y2 - y1 );     если ( абс ( dx ) >= абс ( dy ))    шаг = абс ( dx );   еще шаг = абс ( dy );   dx = dx / шаг ;     dy = dy / шаг ;     х = х1 ;   у = у1 ;   я = 0 ;   пока ( я <= шаг ) {     putpixel ( раунд ( x ), раунд ( y ), 5 );   х = х + dx ;     у = у + dy ;     я = я + 1 ;     задержка ( 100 ); } получить (); закрытьграф ();}

• Линейный алгоритм Брезенхэма — это алгоритм для рендеринга линий.
• Алгоритм инкрементальной ошибки
• Алгоритм линий Сяолиня У — это алгоритм сглаживания линий.

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

Эта статья включает список ссылок , связанных с ней материалов или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Июнь 2011 г. ) ( Узнайте, как и когда удалять это сообщение )

• Алан Уотт: 3D Computer Graphics , 3-е издание 2000 г., стр. 184 (Растеризация краев). ISBN  0-201-39855-9