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

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

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

m={\frac {y_{\rm {end}}-y_{\rm {start}}}{x_{\rm {end}}-x_{\rm {start}}}}

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

Производительность

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

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

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

Алгоритм

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

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

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

x_{k+1}=x_{k}+1

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

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

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

y_{k+1}=y_{k}+1

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

Программа

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

#include <graphics.h>
#include <iostream.h>
#include <math.h>
#include <dos.h>
#include <conio.h>

void main()
{
  float x,
  float y,
  float x1, y1,
  float x2, y2, dx, dy, step;
  int i, gd = DETECT, gm;
  initgraph(&gd, &gm, "C:\\TURBOC3\\BGI");
  
  cout << "Enter the value of x1 and y1: ";
  cin >> x1 >> y1;
  cout << "Enter the value of x2 and y2: ";
  cin >> x2 >> y2;
  
  dx = (x2 - x1);
  dy = (y2 - y1);

  if (abs(dx) >= abs(dy))
    step = abs(dx);
  else
    step = abs(dy);

  dx = dx / step;
  dy = dy / step;
  x = x1;
  y = y1;
  i = 0;

  while (i <= step) {
    putpixel(round(x), round(y), 5);
    x = x + dx;
    y = y + dy;
    i = i + 1;
    delay(100);
  }

  getch();
  closegraph();
}

См. также

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

Ссылки

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

Алан Ватт: 3D компьютерная графика , 3-е издание 2000 г., стр. 184 (Растеризация краев). ISBN 0-201-39855-9