Реализация алгоритмов построения отрезков с помощью различных алгоритмов

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное  учреждение высшего профессионального  образования

Юго-Западный государственный университет

 

Кафедра ПО ВТ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

по дисциплине «Компьютерная графика»

 

Реализация  алгоритмов построения отрезков

с помощью  различных алгоритмов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнил:                  ст.гр. ПО-01 Данилов Д.Э.                                                                        

 

Проверил:                                                                                                   Мельник Е.В.

 

 

 

 

 

Курск, 2013 г.

 

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

 

Теоретическая часть.

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

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

Поскольку прямая линия на плоскости описывается  уравнением вида

ax + by + c = 0,

где a,b,c - коэффициенты этого уравнения, то производная dy/dx является постоянной.

Заменив дифференциалы конечными разностями, получим

, (1)

где x₁,y₁ и x₂,y₂ - координаты начальной и конечной точек отрезка.

Ордината  очередного пиксела y_i+1 может быть вычислена по известной ординате предыдущего пиксела y_i следующим образом:

y_i+1 = y_i + Dy

Подставляя Dy из (1), получим

. (2)

В качестве единицы растра выбирается большее  из приращений (Dх  или  Dy), соответственно идем вдоль оси Х или оси У.

 

  Алгоритм по пунктам:

1. Ввод исходных данных Р1 и Р2
2. Вычисление единицы растра

L:=|x₂-x₁|, если |x₂-x₁|≥|у₂-у₁|

L:=|у₂-у₁|, если |x₂-x₁|≤|у₂-у₁|

3. Вычислить шаг:  dx=(x₂-x₁)/L

dy=(y₂-y₁)/L      

4. x:=x₁+0.5*singn(dx)  -задаем начальные значения и инициализируем

y:=y₁+0.5*singn(dy)

 

5. цикл от i=1

до  L+1, шаг 1

инициализация пикселя с координатами E(x);E(y)

x:=x+dx; y:=y+dx

  end

 

Вещественный  алгоритм Брезенхема.

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

0.5 £ Dy/Dx £ 1 (f ³ 0)

0 £ Dy/Dx < 0.5 (f < 0)

Ошибка на очередном шаге вычисляется  как

f_i+1=y_i+1-y_i+1=y_i+m-y_i+1=f_i+m (если y_i+1=y_i)  (4)

В зависимости  от полученного значения ошибки выбирается пиксел с той же ординатой (при f<0) или пиксел с ординатой, на единицу  большей, чем у предыдущего пиксела (при f³0).

Поскольку предварительное значение ошибки вычисляется  заранее, то есть f+m вычислено на предыдущем шаге, то во втором случае останется только вычесть единицу из значения ошибки:

f=f-1.

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

1.Ввод исходных данных x_н,y_н,x_к,y_к.

2.Проверка вырожденности отрезка.  Если отрезок вырожденный, то  высвечивается точка и осуществляется  переход к п.11.

3.Вычисление приращений dx=x_к-x_н и dy=y_к-y_н.

4.Вычисление шага изменения  каждой координаты пиксела:

h_X=Sign(dx), h_Y=Sign(dy).

5.Вычисление модулей приращения  координат:

dx=abs(dx), dy=abs(dy)

6.Вычисление модуля тангенса угла наклона отрезка:

m=dy/dx.

7.Анализ вычисленного значения m и обмен местами dx и dy при m>1:

если m>1, то выполнить

W=dx, dx=dy, dy=W, m=1/m, flag=1;

иначе flag=0 (flag - флаг, определяющий факт обмена местами координат).

8.Инициализация начального значения  ошибки:

f=m-0,5

9.Инициализация начальных значений  координат текущего пиксела:

x=x_н, y=y_н

10.Цикл от i=1 до i=dx+1 с шагом 1:

Высвечивание точки с координатами (x,y).

Вычисление координат и ошибки для следующего пиксела:

Если f³0, то если flag=1, то x=x+h_X

                                        иначе y=y+h_Y;

корректировка ошибки f=f-1

Если f<0, то если flag=1, то y=y+h_Y

                                       иначе x=x+h_X.

Вычисление ошибки f=f+m.

11.Конец.

Целочисленный алгоритм Брезенхема.

Алгоритм  Брезенхема в том виде, как он представлен выше, требует использования арифметики с плавающей точкой и деления(для вычисления углового коэффициента и оценки ошибки). Быстродействие алгоритма можно увеличить, если использовать только целочисленную арифметику и исключить деление. Для этого выражение для инициализации ошибки запишем в виде: f= DY/DX-1/2 и, умножив обе части этого равенства на 2DX, получим:

2DXf=2DY-DX.

Обозначив f1=2DX f, окончательно получим:

f1=2DY-DX 

Тогда подсчет  нового значения ошибки в п.10 «действительного»  алгоритма будет производиться  по формулам:

f1=f1+2DY и f1=f1-2DX.

Оптимизация алгоритма  Брезенхема – прорисовка линии по отрезкам переменной длины.

Идея  оптимизации (алгоритм с переменной длиной отрезков) – это движение с каждой итерацией по неосновной оси и проверка текущего отклонения по основной оси (рис.3.).

Рассмотрим  работу оптимизированного алгоритма  Брезенхема на примере. Построим линию в 35 пикселей по X и 10 пикселей по Y. Наклон линии находится в пределах 1/3-1/4, т.е. составляющие линию ряды точек (подотрезки) будут состоять из 3 или 4 пикселей.

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

 

Рис. 4. Алгоритм с переменной длиной отрезков

Сначала на каждый шаг по неосновной оси  ставится, по меньшей мере, три пикселя  вдоль основной. После этого рассчитывается ошибка отклонения на каждом шаге вычисляется  как сумма предыдущей ошибки и  значения выражения mod(Dx/Dy)/Dy (где mod(35/10)=5 - остаток от деления):

f = f + mod(Dx/Dy)/Dy.

Решение о том, ставить ли дополнительный пиксель или нет, принимается  на основе анализа целой части  полученной суммы: пиксель ставится если полученное значение больше или равно единицы и при этом из ошибки вычитается 1. Для рассмотренного примера подотрезки длиной 3 и 4 будут появляться строго друг за другом.

Алгоритм Брезенхема устранения ступенчатости

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

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

Отрезок, тангенс угла наклона m которого лежит  в диапазоне 0<m<1 может при данном значении абсциссы пересечь один или  два пиксела (см. рис.5).

Рис. 5. Алгоритм Брезенхема, учитывающий площадь части пиксела для устранения ступенчатости

В первом случае искомая площадь находится  как сумма площадей прямоугольника S₁ и треугольника S₂:

S=S₁+S₂=y_i*1+1*m/2=y_i+m/2,

где y_i- расстояние между нижней левой вершиной пиксела и точкой пересечения отрезка с левой границей пиксела.

Если отрезок  пересекает два пиксела, то площадь  части нижнего пиксела (S₄) может быть найдена как разность площади всего пиксела и площади треугольника S₃:

где 1-y_i - длина одного катета, (1-y_i)/m - длина другого катета.

Площадь S₅ части верхнего пиксела - треугольника равна

Практика  показывает, что учет площади S₅ позволяет более реалистично представить отрезок, поэтому найдем сумму площадей S₄ и S₅:

S=S₄+S₅=y_i+m/2.

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

В качестве ошибки в данном алгоритме принимается  часть площади пиксела, находящаяся  под отрезком, то есть y_i+m/2. Вычислим значение ошибки при переходе к соседнему пикселу. Если ордината соседнего пиксела не увеличивается, то площадь, находящаяся под отрезком, увеличивается на величину площади прямоугольника со сторонами 1 и m, то есть f=f+m.

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

f=f+m-1.

Поскольку доля площади не может быть отрицательной  величиной, то по сравнению с ранее  рассмотренными алгоритмами Брезенхема необходимо скорректировать величину ошибки, прибавив к ней величину W=1-m. При этом начальное значение ошибки будет равно f=m-0.5+1-m=0.5, а значение ошибки будет лежать в диапазоне 0<f<1.

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

Можно сразу  получить не дробное значение максимальной интенсивности, а ее непосредственное значение, если умножить на максимальное количество уровней интенсивности  следующие величины: тангенс угла наклона m, коэффициент W, ошибку f.

 

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

 

1. Ввод исходных  данных x_н,y_н,x_к,y_к (координаты концов отрезка), I - количество уровней интенсивности.

2. Проверка  вырожденности отрезка. Если отрезок  вырожден, то высвечивание отдельного пиксела и переход к п.13.

3. Вычисление  приращений dx=x_к-x_н и dy=y_к-y_н.

4. Вычисление  шага изменения каждой координаты:

h_X=sign(dx), h_Y=sign(dy).

5. Вычисление  модулей приращения координат:

dx=abs(dx), dy=abs(dy).

6. Вычисление  модуля тангенса угла наклона

m=dy/dx.

7. Анализ  вычисленного значения m и обмен  местами dx и dy при m>1:

если m>1, то выполнить

p=dx; dx=dy; dy=p; m=1/m; flag=1;

если m<1, то flag=0.

(flag - флаг, определяющий факт обмена местами координат).

8. Инициализация  начального значения ошибки f=I/2.

9. Инициализация  начальных значений координат  текущего пиксела:

x=x_н, y=y_н.

10. Вычисление  скорректированного значения тангенса  угла наклона m=m*I и коэффициента W=I-m.

11. Высвечивание  пиксела с координатами (x,y) интенсивностью E(f).

Если f³0, то если flag=1, то x=x+h_X

                                           иначе y=y+h_Y;

корректировка ошибки f=f-1

Вычисление  ошибки f=f+m.

 

12. Цикл от i=1 до i=dx с шагом 1:

Если f<W, то

если flag=0, то x=x+h_X;

если flag=1, то y=y+h_Y;

f=f+m.

Если f>W, то если flag=1, то x=x+h_X,

                                             иначе y=y+h_Y, f=f-W.

Высвечивание  пиксела с координатами (x,y) интенсивностью E(f).

13. Конец.

 

Данный  алгоритм, как и в предыдущем случае, можно тем же приемом преобразовать  к целочисленному виду. Умножив на 2DX, получим измененные выражения для вычисления ошибки f1:

начальное значение ошибки f1=DX1,

а текущее  значение будет вычисляться как f1=f1+2DY или f1=f1-2DX1+2DY1, где DX1= DX*I и DY1= DY*I.