Конспект Лекций Лекция 1 Введение в компьютерную геометрию и графику Основные направления компьютерной графики

Вид материала

Содержание

Лекция 10 Базовые растровые алгоритмы Алгоритмы вывода прямой линии
Положительные черты алгоритма прямого вычисления координат
Инкрементные алгоритмы
Если dx>0, то incX:=1

Подобный материал:

1 2 3 4 5 6 7 8 9 10 11

Лекция 10

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

Алгоритмы вывода прямой линии

Пусть заданы координаты (x1,y1) и (x2,y2) концов отрезка прямой линии. Для вывода линии необходимо закрасить в определенный цвет все пикселы вдоль линии. Для того чтобы закрасить каждый пиксел, необходимо знать его координаты.

Наиболее просто нарисовать отрезок горизонтальной линии (y1=y2): для x от x1 до x2 с шагом 1 закрашиваются соседние пикселы (x, y1). (Эта операция достаточно проста и применяется в алгоритмах закрашивания полигонов.)

Аналогично изображается отрезок вертикальной линии.

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

Прямое вычисление координат. Пусть заданы координаты конечных точек отрезка. Координаты внутренней точки отрезка вычисляются следующим образом:

x=f(y): x=x₁+(y-y₁)(x₂-x₁)/(y₂-y₁)

или

y=F(x): y=y₁+(x-x₁)(y₂-y₁)/(x₂-x₁).

В зависимости от угла наклона прямой выполняется цикл по оси x (если |x₂-x₁|>|y₂-y₁|) или по оси y (в противном случае).

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

k=(y₂-y₁)/(x₂-x₁), yy=y₁-x₁*k.

В цикле вычисляется y=yy+x*k.

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

k=(y₂-y₁)/(x₂-x₁), y=y₁.

Для x от x₁ до x₂ с шагом 1 вычисляется y=y+k.

С учетом того, что вычисление дробей в компьютере происходит с определенной погрешностью, возможно ситуация, когда на последнем шаге цикла x окажется не равным x₂. Это необходимо учитывать при использовании алгоритма.

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

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

Недостатки:

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

Инкрементные алгоритмы

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

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

Один из вариантов алгоритма Брезенхэма ([12, с. 100-101]):

xerr:=0; yerr:=0;

dx:=x2-x1; dy:=y2-y1;

Если dx>0, то incX:=1;

dx=0, то incX:=0;

dx<0, то incX:=-1;

Если dy>0, то incY:=1;

dy=0, то incY:=0;

dy<0, то incY:=-1;

dx:=|dx|; dy:=|dy|;

Если dx>dy, то d:=dx иначе d:=dy;

x:=x1; y:=y1;

Закрасить пиксел с координатами (x, y);

Выполнить d раз цикл:

xerr:=xerr+dx;

yerr:=yerr+dy;

Если xerr>=d, то xerr:=xerr-d, x:=x+incX;

Если yerr>=d, то yerr:=yerr-d, y:=y+incY;

Закрасить пиксел с координатами (x, y).

Рассмотрим пример работы приведенного выше алгоритма Брезенхэма для отрезка (2;3) - (8;6). Этот алгоритм восьмисвязный, т.е. при вычислении приращений координат для перехода к соседнему пикселу возможны восемь случаев:

	2	3	4	5	6	7	8		incY=-1
3
4								incX=-1	incX=1
5
6
									incY=1

Известны также четырехсвязные алгоритмы. Они более просты, но генерируют менее качественное изображение линий за большее количество тактов работы. Для приведенного примера четырехсвязный алгоритм работает 10 тактов, а восьмисвязный - только 7: