Цифровой дифференциальный анализатор

С помощью ЦДА решается дифференциальное уравнение отрезка, имеющее вид:

где Py = Yk - Yn - приращение координат отрезка по оси Y, а Px = Xk - Xn - приращение координат отрезка по оси X.

При этом ЦДА формирует дискретную аппроксимацию непрерывного решения этого дифференциального уравнения.

В обычном ЦДА, используемом, как правило, в векторных устройствах, тем или иным образом определяется количество узлов N, используемых для аппроксимации отрезка. Затем за N циклов вычисляются координаты очередных узлов:

Получаемые значения X_i, Y_i преобразуются в целочисленные значения координаты очередного подсвечиваемого пиксела либо округлением, либо отбрасыванием дробной части.

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

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

Аппаратная реализация этого алгоритма изложена в пункте 8.1 первой части курса.

Субъективно лучше смотрятся вектора с единичным шагом по большей относительной координате (несимметричный ЦДА). Для Px > Py (при Px, Py > 0) это означает, что координата по X направлению должна увеличиться на 1 Px раз, а координата по Y-направлению должна также Px раз увеличиться, но на Py/Px.

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

Для генерации отрезка из точки (x1,y1) в точку (x2,y2) в первом октанте (Px і Py і 0) алгоритм несимметричного ЦДА имеет вид:

1. Вычислить приращения координат:
Px= x2 - x1;
Py= y2 - y1;

2. Занести начальную точку отрезка
PutPixel (x1, y1);

3. Сгенерировать отрезок
while (x1 < x2) {
x1:= x1 + 1.0;
y1:= y1 + Py/Px;
PutPixel (x1, y1);
}

Пример генерации отрезка по алгоритму несимметричного ЦДА приведен на рис..

В Приложении 2 приведена программа V_DDA, реализующая данный алгоритм.

Так как приращения координат, как правило, не являются целой степенью двойки, то в ЦДА-алгоритме (см. предыдущий пункт) требуется выполнение деления, что не всегда желательно, особенно при аппаратной реализации.

Рис. 0.2.2: Генерация отрезка несимметричным ЦДА