В компьютерной графике , A Цифровой дифференциальный анализатор ( ДВР ) аппаратно или программное обеспечение , используемое для интерполяции из переменных в течение интервала между начальной и конечной точкой. DDA используются для растеризации линий, треугольников и многоугольников. Их можно расширить до нелинейных функций, таких как наложение текстуры с правильной перспективой , квадратичные кривые и обход вокселей .
В своей простейшей реализации для линейных случаев, таких как линии , алгоритм DDA интерполирует значения в интервале, вычисляя для каждого x i уравнения x i = x i − 1 + 1, y i = y i − 1 + m, где m - это наклон линии. Этот наклон можно выразить в DDA следующим образом:
Фактически, любые две последовательные точки (x, y), лежащие на этом отрезке, должны удовлетворять уравнению.
Представление
Метод DDA может быть реализован с использованием арифметики с плавающей запятой или целых чисел . Собственная реализация с плавающей запятой требует одной операции сложения и одной операции округления на каждое интерполированное значение (например, координату x, y, глубину, компонент цвета и т. Д.) И результат вывода. Этот процесс эффективен только тогда, когда доступен FPU с быстрой операцией сложения и округления.
С фиксированной точкой числа операций требует два дополнений за выходной цикл, а в случае дробного переполнения части, одного дополнительного прироста и вычитания. Вероятность переполнения дробной части пропорциональна отношению m интерполированных начальных / конечных значений.
DDA хорошо подходят для аппаратной реализации и могут быть конвейерными для максимальной пропускной способности.
Алгоритм
Линейный DDA начинается с вычисления меньшего из dy или dx для единичного приращения другого. Затем производится выборка линии через единичные интервалы по одной координате, и соответствующие целые числа, ближайшие к траектории линии, определяются для другой координаты.
Рассматривая линию с положительным наклоном, если наклон меньше или равен 1, мы производим выборку через единичные интервалы x (dx = 1) и вычисляем последовательные значения y как
Индекс k принимает целые значения, начиная с 0, для 1-й точки и увеличивается на 1, пока не будет достигнута конечная точка. Значение y округляется до ближайшего целого числа, чтобы соответствовать пикселю экрана.
Для линий с наклоном больше 1 мы меняем роль x и y, т. Е. Выбираем при dy = 1 и вычисляем последовательные значения x как
Аналогичные вычисления выполняются для определения положения пикселей вдоль линии с отрицательным наклоном. Таким образом, если абсолютное значение наклона меньше 1, мы устанавливаем dx = 1, если т.е. начальная крайняя точка находится слева.
Программа
Программа алгоритма DDA на Turbo C ++:
#include #include #include #include #include void main ( ){ float x , плавать y , поплавок x1 , y1 , float x2 , y2 , dx , dy , step ; int i , gd = DETECT , 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 ); если ( abs ( dx ) > = abs ( dy )) шаг = abs ( dx ); еще шаг = abs ( dy ); dx = dx / шаг ; dy = dy / шаг ; х = х1 ; у = у1 ; я = 1 ; while ( i <= step ) { putpixel ( x , y , 5 ); х = х + дх ; y = y + dy ; я = я + 1 ; задержка ( 100 ); } getch (); closegraph ();}
Смотрите также
- Линейный алгоритм Брезенхема - это алгоритм линейного рендеринга.
- алгоритм возрастающей ошибки
- Линейный алгоритм Xiaolin Wu - это алгоритм сглаживания линий.
Рекомендации
http://www.museth.org/Ken/Publications_files/Museth_SIG14.pdf
- Алан Ватт: 3D компьютерная графика , 3-е издание, 2000 г., стр. 184 (Растеризация краев). ISBN 0-201-39855-9