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

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

dY dX

=

Py Px

,

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

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

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

X₀ =   Xn;X_i+1 = X_i + Px/N.

Y₀ =   Yn;Y_i+1 = Y_i + Py/N.

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

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

Субъективно лучше смотрятся вектора с единичным шагом по большей относительной координате (несимметричный ЦДА). Для 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); }

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

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

5.2.2 Алгоритм Брезенхема

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

Брезенхем предложил алгоритм, не требующий деления, но обеспечивающий минимизацию отклонения сгенерированного образа от истинного отрезка. Основная идея алгоритма состоит в том, что если угловой коэффициент прямой < 1/2, то естественно точку, следующую за точкой (0,0), поставить в позицию (1,0) (рис.5.3а), а если угловой коэффициент > 1/2, то - в позицию (1,1) (рис.5.3б). Для принятия решения – куда заносить очередной пиксел – вводится величина отклонения Е точной позиции от середины между двумя возможными растровыми точками в направлении наименьшей относительной координаты. Знак Е используется как критерий для выбора ближайшей растровой точки.

Рис. 5.3 – Алгоритм Брезенхема генерации отрезков

Если Е < 0, то точное Y-значение округляется до последнего меньшего целочисленного значения Y, т.е. Y-координата не меняется по сравнению с предыдущей точкой. В противном случае Y увеличивается на 1.

Этот алгоритм пригоден для случая 0  dY  dX. Для других случаев алгоритм строится аналогичным образом.

На рис.5.4 приведен пример генерации по алгоритму Брезенхема того же самого отрезка, что и показанного на рис. 5.2 для генерации по алгоритму несимметричного ЦДА. Из сравнения рисунков видно, что результаты различны.

Рис. 5.4 – Генерация отрезка по алгоритму Брезенхема

Этот алгоритм удовлетворяет самым строгим требованиям. Он имеет приемлемую скорость и может быть легко реализован на аппаратном или микропрограммном уровне.

Выше было отмечено, что растровая генерация отрезков имеет следующие недостатки:

• неточное расположение начала и конца,

• ступенчатый вид отрезка,

• яркость зависит от наклона и длины.

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

Наиболее заметно ухудшает качество изображения ступенчатость. Имеются следующие способы борьбы со ступенчатостью:

• увеличение пространственного разрешения за счет усовершенствования аппаратуры,

• трактовка пиксела не как точки, а как площадки конечного размера, яркость которой зависит от размера площади пиксела, занятой изображением отрезка,

• "размывание" резкой границы, за счет частичной подсветки пикселов, примыкающих к формируемому отрезку. Понятно, что при этом ухудшается пространственное разрешение изображения.

Существует модифицированный алгоритм Брезенхема, трактующий пиксел как конечную площадку. Основная идея алгоритма состоит в том, чтобы для ребер многоугольника устанавливать яркость пиксела пропорционально площади пиксела, попавшей внутрь многоугольника.

Один из методов "размывания" границы заключается в том, что изображение строится с большим пространственным разрешением, чем позволяет дисплей. При выводе на экран атрибуты пиксела экрана вычисляются усреднением по группе пикселов изображения.