Лабораторная работа № 5. Растровые алгоритмы

Растровые алгоритмы

Ц е л ь р а б о т ы: овладение методами разложения в растр отрезков и кривых второго порядка.

Задание к работе

1. Изучить алгоритмы вычерчивания отрезков (метод цифрового дифференциального анализатора и метод Брезенхема).

2. Составить программу для вывода на экран отрезка.

3. Подобрать тестовые данные для построения различно ориентированных отрезков.

4. Изучить алгоритмы Брезенхема для генерации окружности и эллипса.

5. Составить программу для построения окружности. Учесть коэффициент сжатия изображения.

6. Составить программу для построения эллипса.

Содержание отчета

1. Постановка задачи.

2. Спецификации подпрограмм.

3. Описание основных алгоритмов.

4. Тексты программ.

5. Наборы тестовых данных для построения отрезка.

6. Ответы на контрольные вопросы.

Методические указания

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

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

где 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);}

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

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

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

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

Рисунок 2.2 - Алгоритм Брезенхема генерации отрезков

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

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

Из рис. 2.2в видно, отклонение для первого шага: Е₁ = Py/Px – 1/2 < 0,

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

Отклонение для второго шага вычисляется добавлением приращения Y-координаты для следующей X-позиции (см. рис. 2в): Е₂ = Е₁ + Py/Px > 0,

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

Отклонение для третьего шага: Е₃ = Е₂ + Py/Px < 0,

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

Суммируя и обозначая большими буквами растровые точки, а маленькими – точки вектора, получаем: Е₁ = y₁ – 1/2 = dY/dX – ½.

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

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

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

X = x1; Y = y1;

Px = x2 – x1; Py = y2 – y1;

E = 2*Py – Px; I = Px;

PutPixel(X, Y); /* Первая точка вектора */

while (i= i – 1 ³ 0)

{ if (E ³ 0)

{ X = X + 1; Y = Y + 1; E = E + 2*(Py – Px); }

Else X = X + 1; E = E + 2*Py;

PutPixel(X, Y); /* Очередная точка вектора */ }

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

Во многих областях приложений, таких как, например, системы автоматизированного проектирования машиностроительного направления, естественными графическими примитивами, кроме отрезков прямых и строк текстов, являются и конические сечения, т.е. окружности, эллипсы, параболы и гиперболы. Наиболее употребительным примитивом, естественно, является окружность. Один из наиболее простых и эффективных алгоритмов генерации окружности разработан Брезенхемом. Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).

Окружность с центром в начале координат описывается уравнением:

X² + Y² = R².

Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пикселя точку растра P_i(X_i, Y_i), ближайшую к истинной окружности, так чтобы ошибка:

E_i(P_i) = (X_i² + Y_i²) – R² была минимальной.

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

Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.

Проанализируем возможные варианты занесения i + 1-й точки, после занесения i-й.

Рисунок 2.3 - Варианты расположения очередного пикселя окружности

При генерации окружности по часовой стрелке после занесения точки (X_i, Y_i) следующая точка может быть (см. рис. 2.4а) либо Pg = (X_i+1, Y_i) – перемещение по горизонтали, либо Pd = (X_i+1, Y_i-1) – перемещение по диагонали, либо Pv = (X_i, Y_i-1) – перемещение по вертикали.

Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности: |Dg| = | (X+1)² + Y² – R² |

|Dd| = | (X+1)² + (Y-1)² – R² |

|Dv| = | X² + (Y-1)² – R² |

Выбирается и заносится та точка, для которой это значение минимально.

Выбор способа расчета определяется по значению Dd. Если Dd < 0, то диагональная точка внутри окружности. Это варианты 1-3. Если Dd > 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности.

Контрольные вопросы:

1. Общие требования к алгоритмам построения отрезка.

2. Принцип, положенный в основу алгоритма Брезенхема для построения линий.

3. Алгоритм Брезенхема для построения отрезка.

4. Алгоритм Брезенхема для построения окружности.

Поиск по сайту: