Писание структуры и алгоритма программы

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

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

Задания к лабораторной работе №2.

писание структуры и алгоритма программы - student2.ru

нализ задачи

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

· Обычный алгоритм ЦДА - алгоритм цифрового дифференциального анализатора (DDA - Digital Differential Analyzer)

· Несимметричный алгоритм ЦДА

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

· Алгоритм генерации окружности Брезенхема

Общие требования к изображению отрезка:

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

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

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

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

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

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

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

Рассмотрим принцип действия первого алгоритма:

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

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

dY/dX=Py/Px

где

Py = Yk - Yn - приращение координат отрезка по оси Y

Px = Xk - Xn - приращение координат отрезка по оси X.

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

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

X₀ = X_n; X_i₊₁ = X_i + Px/N.

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

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

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

Несимметричный ЦДА

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

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

Px= x2 - x1;

Py= y2 - y1;

· Занести начальную точку отрезка

PutPixel (x1, y1);

· Сгенерировать отрезок

while (x1 < x2) {

x1:= x1 + 1.0;

y1:= y1 + Py/Px;

PutPixel (x1, y1);

}

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

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

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

писание структуры и алгоритма программы - student2.ru

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

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

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

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

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-й.

писание структуры и алгоритма программы - student2.ru

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

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

(X+1)²

(Y-1)²

R²

Dd < 0

di =|Dg| - |Dd|

di <= 0 - выбор горизонтального пиксела Pg

di > 0 - выбор диагонального пиксела Pd

Dd > 0

si=|Dd| - |Dv|

si < 0 - выбор диагонального пиксела Pd

si > 0 - выбор вертикального пиксела Pv

Dd = 0

выбор диагонального пиксела Pd.

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

Генерация пунктирной, жирной линии

Для того, чтобы при выводе можно было менять атрибуты пера, необходимо:

v Функция проверки необходимости вывода данной точки, для создания пунктирной линии с заданным шагом

v Процедура вывода сложной геометрической фигуры – набора точек с центром в указанной точке.

v Совместить процедуру проверки и процедуру вывода на экран.

писание структуры и алгоритма программы

Основной модуль

Разработанная структура имеет структуру, изображенную на рис.3.1.

Лабораторная 1

Лабораторная 2

Задание 1

Задание 2