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

А.И. Дружинин, В.В. Вихман

Алгоритмы компьютерной графики: Учеб. пособие. – Новосибирск: Изд-во НГТУ, 2003. – 47 с.

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

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

Авторы работы выражают особую благодарность инженерам кафедры вычислительной техники Малявко О.В. и Исаеву А.Р. за оформление учебного пособия.

Новосибирский государственный технический университет, 2003 г.

1. Генерация векторов

Цель: Изучить алгоритмы разложения отрезка в растр:
алгоритм цифрового дифференциального анализатора (ЦДА), алгоритм Брезенхема. Сравнить результаты применения
алгоритмов между собой

Назначение генератора векторов – соединение двух точек изображения отрезком прямой. Далее будут рассмотрены следующие алгоритмы:

· алгоритм ЦДА – цифрового дифференциального анализатора (DDA – Digital Differential Analyser) для генерации векторов – симметричный и несимметричный;

· алгоритм Брезенхема для генерации векторов.

Перед рассмотрением конкретных алгоритмов сформулируем общие требования к изображению отрезка:

· концы отрезка должны находиться в заданных точках;

· отрезки должны выглядеть прямыми;

· яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона;

· построение должно быть быстрое.

Ни одно из этих условий не может быть точно выполнено на растровом дисплее в силу того, что изображение строится из пикселов конечных размеров, а именно:

· концы отрезка в общем случае располагаются на пикселах, лишь наиболее близких к требуемым позициям и только в частных случаях координаты концов отрезка точно совпадают с координатами пикселов;

· отрезок аппроксимируется набором пикселов и лишь в частных случаях вертикальных, горизонтальных и отрезков под 45° они будут выглядеть прямыми, причем гладкими прямыми, без ступенек только для вертикальных и горизонтальных отрезков (рис. 1.1);

· яркость для различных отрезков и даже вдоль отрезка в общем случае различна, так как, например, расстояние между центрами пикселов для вертикального отрезка и отрезка под углом 45° различно (рис. 1.1).

Рис. 1.1. Растровое представление различных векторов

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

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

,

где – приращение координат отрезка по оси Y; – приращение координат отрезка по оси X; X₂, Y₂, X₁,Y₁ – начальная и конечная координаты отрезка.

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

,

.

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

Кроме того, из-за независимого вычисления обеих координат нет предпочтительных направлений и построенные отрезки кажутся не очень красивыми. Субъективно лучше смотрятся вектора с единичным шагом по большей относительной координате (несимметричный ЦДА). Для (при ) это означает, что координата по X направлению должна увеличиться на 1 P_x раз, а координата по Y – направлению должна также P_x раз увеличиться, но на . Т.е. количество узлов аппроксимации берется равным числу пикселов вдоль наибольшего приращения. Для генерации отрезка из точки (X₁,Y₁) в точку (X₂,Y₂) в первом октанте алгоритм несимметричного ЦДА имеет вид:

x – integer;

Вычислить приращения координат:
;
;

Занести начальную точку отрезка
PutPixel (x₁,y₁);

Сгенерировать отрезок
while (x₁ < x₂) {
x₁:= x₁ + 1;
y₁:= y₁ + P_y/P_x;
PutPixel (intl (x₁), intl (y₁));
}

Примечание: intl – приближение к нижнему, т.е. 5.3 = 5; 5.6 = 5; –5.3 = –6; –5.6 = –6.

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

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

Генерация отрезка:

if (abs (x₂ – x₁) >= abs (y₂ – y₁)) then

len:= abs (x₂ – x₁) else

len:= abs (y₂ – y1);

;
;

;

;

i = 1

while (i <= len) {
PutPixel (intl (x), intl (y));
x:= x + P_x;
y:= y+P_y;
i:= i + 1

}

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

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

Брезенхем предложил алгоритм, построенный так, что требуется проверять лишь знак этой ошибки. На рис. 1.3 а,б) это иллюстрируется для отрезка в первом октанте, т.е. для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0,0) больше чем 1/2, то его пересечение с прямой будет расположено ближе к прямой , чем к прямой . Следовательно, точка растра (1,1) лучше апроксимирует ход отрезка, чем точка (1,0). Если угловой коэффициент меньше 1/2, то верно обратное. Для углового коэффициента, равного 1/2 нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1,1). Не все отрезки проходят через точки растра (рис. 1.3 в). Здесь отрезок с тангенсом угла наклона 3/8 сначала проходит через точку растра (0,0) и последовательно пересекает три пиксела. Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной – 1/2.

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

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

Для вычисления Е положим, что рассматриваемый вектор начинается в точке (0,0) и проходит через точку (4, 1.6) (рис. 1.3 в), т.е. имеет положительный наклон, меньший 1.

Из рис. 1.3 в) видно, отклонение для первого шага:

,

поэтому для занесения пиксела выбирается точка (1,0).

Отклонение для второго шага вычисляется добавлением приращения Y-координаты для следующей X-позиции (рис. 1.3 в):

,

поэтому для занесения пиксела выбирается точка (2,1). Так как отклонение считается от Y-координаты, которая теперь увеличилась на 1, то из накопленного отклонения для вычисления последующих отклонений надо вычесть 1:

E₂ = E₂ – 1

Отклонение для третьего шага:

,

поэтому для занесения пиксела выбирается точка (3,1).

Возможны случаи:

Так как интересует только знак Е, то можно избавиться от деления умножением E на 2*Px:

Таким образом получается алгоритм, в котором используются только целые числа, сложение (умножение на 2 – сдвиг влево или сложение с самими числом):

X = x₁;
Y = y₁;
P_x = x₂ – x₁;
P_y = y₂ – y₁;
E = 2*P_y – P_x;
i = P_x;
PutPixel(X, Y); /* Первая точка вектора */
while (i= i – 1³ 0){
if (E 0){
X= X + 1;
Y= Y + 1;
E= E + 2*(P_y – P_x);
} else
X= X + 1;
E= E + 2*P_y;
PutPixel(X, Y); /* Очередная точка вектора */
}

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

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

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

Задание на лабораторную работу № 1
"Генерация векторов"

1. Центр отрезка находится в середине экрана.

1.1. Разложить в растр отрезок по методу цифрового дифференциального анализатора (ЦДА) с произвольными координатами.

1.2. Разложите в растр отрезок, используя алгоритм Брезенхема с произвольными координатами.

2. Используя разные цвета, разложите в растр отрезок на одной системе координат с помощью метода ЦДА и Брезенхема. Сравните полученные результаты. Сделайте выводы.

3. Нарисуйте "настоящий" отрезок и сравните результаты работы алгоритмов.

4. Сравните алгоритмы ЦДА и Брезенхема. Приведите примеры их сходства и различия.

2. Фильтрация.
Модифицированный алгоритм Брезенхема

Цель: Изучить алгоритмы фильтрации: модифицированный
алгоритм Брезенхема и масочную фильтрацию

2.1. Модифицированный алгоритм Брезенхема

Основная идея алгоритма состоит в том, что для ребер многоугольника устанавливать яркость пиксела пропорционально площади пиксела, попавшей внутрь многоугольника. На рис. 2.1 приведена иллюстрация построения ребра многоугольника с тангенсом угла наклона 11/21.

Рис. 2.1. Устранение ступенчатости ребер многоугольника:

а) генерация ребер без устранения ступенчатости;

б) точное вычисление интенсивности пикселов границы;

в) формирование пикселов границы по модифицированному методу Брезенхема

На рис. 2.1 а) показан результат генерации многоугольника с использованием ранее рассмотренного алгоритма Брезенхема при двухуровневом изображении (пиксел или закрашен или не закрашен). На рис. 2.1 б) показан результат генерации многоугольника с вычислением интенсивности пикселов, через которые проходит ребро многоугольника. Интенсивность вычисляется пропорционально площади части пиксела, попавшей внутрь многоугольника. На рис. 2.1 в) показан результат генерации многоугольника с вычислением интенсивности пиксела, через который проходит ребро многоугольника в соответствии с модифицированным алгоритмом Брезенхема. Суммарная площадь частей для двух пикселов, попавшая внутрь многоугольника, равна (dy + t)/ 2, где t – тангенс угла наклона (рис. 2.2). Если теперь в исходном алгоритме Брезенхема заменить отклонение E на E' = E + (1 – t), то 0 £ E' £ 1) и значение E' будет давать значение той части площади пиксела, которая находится внутри многоугольника.

Рис. 2.2. Устранение ступенчатости за счет учета площади
пикселов, пересекаемых ребром многоугольника

Выполняя преобразование над значением отклонения для первого шага (рис. 2.1), получим, что начальное значение станет равным 1/2.

Максимальное значение отклонения , при превышении которого производится увеличение Y-координаты занесения пикселов, станет равным
(1 – t).

Для того чтобы оперировать не дробной частью максимальной интенсивности, а непосредственно ее значениями достаточно домножить на полное число уровней интенсивности I тангенс угла наклона (t), начальное ( ) и максимальное ( ) значения отклонения.

В результате получается следующий алгоритм, пригодный для случая
0 dY dX:

X = x₁;
Y = y₁;
P_x = x₂ – x₁;
P_y = y₂ – y₁;
t = I*P_y / P_x;
E' = I / 2;

i = P_x;
PutPixel(X, Y, t/2); /* Первая точка вектора */
while (i = i – 1 0){
if ( ){
X= X + 1;
Y= Y + 1;

} else
X = X + 1;
E' = E' + t;
PutPixel(X, Y, E'); /* Очередная точка вектора */
}

Для избавления от вещественной арифметики при манипулировании с можно помножить уже упомянутые величины на 2*P_x.

Не нашли, что искали? Воспользуйтесь поиском по сайту: