78375

БАЗОВЫЕ РАСТРОВЫЕ АЛГОРИТМЫ

Лекция

Информатика, кибернетика и программирование

Алгоритм вывода окружности. В следующем разделе рассматривается алгоритм Брезенхема для генерации окружности. Алгоритм Брезенхема для генерации окружности. Наибольшее внимание разумеется уделено окружности.

Русский

2015-02-07

419 KB

1 чел.

ТЕМА № 7. БАЗОВЫЕ РАСТРОВЫЕ АЛГОРИТМЫ

Алгоритм вывода прямой линии. Алгоритм вывода окружности. Алгоритм вывода эллипса. Алгоритмы вывода фигур. Алгоритмы закрашивания (простейший алгоритм закрашивания, волновой алгоритм, алгоритм закрашивания линиями). Заполнение прямоугольников. Заполнение круга. Алгоритм вывода толстой и пунктирной линии.

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

Поскольку экран растрового дисплея с электронно-лучевой трубкой (ЭЛТ) можно рассматривать как матрицу дискретных элементов (пикселов), каждый из которых может быть подсвечен, нельзя непосредственно провести отрезок из одной точки в другую. Процесс определения пикселов, наилучшим образом аппроксимирующих заданный отрезок, называется разложением в растр. В сочетании с процессом построчной визуализации изображения он известен как преобразование растровой развертки. Для горизонтальных, вертикальных и наклоненных под углом 45°. отрезков выбор растровых элементов очевиден. При любой другой ориентации выбрать нужные пикселы труднее, что показано на рис.1.

Рис.1.1. Разложение в растр отрезков прямых.

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

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

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

Простой пошаговый алгоритм

позиция = начало

шаг = приращение

1. if позиция - конец < точность then 4

if позици > конец then 2

if позиция < конец then 3

2. позиция = позиция - шаг

go to 1

3. позиция = позиция + шаг

go to 1

4. finish

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

Хотя алгоритм Брезенхема был первоначально разработан для цифровых графопостроителей, однако он в равной степени подходит для использования растровыми устройствами с ЭЛТ. Алгоритм выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат - либо x, либо y (в зависиимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (на 0 или 1) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние мы назовем ошибкой.

Алгоритм построен так, что требуется проверить лишь знак этой ошибки. На рис.3.1 это иллюстрируется для отрезка в первом октанте, т.е. для отрезка с угловым коэффициентом, лежащим в диапазоне от 0 до 1. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0,0) больше, чем 1/2, то пересечение с прямой x = 1 будет расположено ближе к прямой y = 1, чем к прямой y = 0. Следовательно, точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0). Если угловой коэффициент меньше 1/2, то верно обратное. для углового кэффициента, равного 1/2, нет какого либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1,1).

Рис. 3.1. Основная идея алгоритма Брезенхема.

Не все отрезки проходят через точки растра. Подобная ситуация иллюстрируется рис.3.2, где отрезок с тангенсом угла наклона 3/8 сначала походит через точку растра (0,0) и последовательно пересекает три пиксела. Также иллюстрируется вычисление ошибки при представлении отрезка дискретными пикселами.

Рис.3.2. График ошибки в алгоритме Брезенхема.

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

e = e + m

где m - угловой коэффициент. В нашем случае при начальном значении ошибки -1/2

e = 1/2 + 3/8 = -1/8

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

e = -1/8 + 3/8 = 1/4

в следующей точке растра (2,0). Теперь е положительно, значит отрезок пройдет выше средней точки. Растровый элемент (2,1) со следующей по величине координатой у лучше аппроксимирует положение отрезка. Следовательно у увеличивается на 1. Прежде чем рассматривать следующий пиксел, необходимо откорректировать ошибку вычитанием из нее 1. Имеем

e = 1/4 - 1 = -3/4

Заметим, что пересечение вертикальной прямой x = 2 с заданным отрезком лежит на 1/4 ниже прямой у = 1. Еслиже перенести отрезок 1/2 вниз, мы получим как раз величину -3/4. Продолжение вычислений для следующего пиксела дает

e = -3/4 + 3/8 = -3/8

Так как е отрицательно, то у не увеличивается. Из всего сказанного следует, что ошибка - это интервал, отсекаемый по оси у рассматриваемым отрезком в каждом растровом элементе (относительно -1/2).

Приведем алгоритм Брезенхема для первого октанта, т.е. для случая 0 =< y =< x.

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

предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают

Integer - функция преобразования в целое

x, y, x, y - целые

е - вещественное

инициализация переменных

x = x1

y = y1

x = x2 - x1

y = y2 - y1

Инициализация с поправкой на половину пиксела

е = y/x - 1/2

начало основного цикла

for i = 1 to x

plot (x,y)

while ( e => 0 )

y = y + 1

e = e - 1

end while

x = x + 1

e = e + y/x

next i

finish

Блок-схема алгоритма приводится на рис.3.3. Пример приведен ниже.

Рис. 3.3. Блок-схема алгоритма Брезенхема.

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

Рассмотрим отрезок проведенный из точки (0,0) в точку (5,5). Разложение отрезка в растр по алгоритму Брезенхема приводит к такому результату:

начальные установки

x = 0

y = 0

x = 5

y = 5

е = 1 - 1/2 = 1/2

результаты работы пошагового цикла

i

Plot

e

x

y

 

 

1/2

0

0

1

(0,0)

 

 

 

 

 

-1/2

0

1

 

 

1/2

1

1

2

(1,1)

 

 

 

 

 

-1/2

1

2

 

 

1/2

2

2

3

(2,2)

 

 

 

 

 

-1/2

2

3

 

 

1/2

3

3

4

(3,3)

 

 

 

 

 

-1/2

3

4

 

 

1/2

4

4

5

(4,4)

 

 

 

 

 

-1/2

5

5

 

 

1/2

5

5

Результат показан на рис.3.4 и совпадает с ожидаемым. Заметим, что точка растра с координатами (5,5) не активирована. Эту точку можно активировать путем изменения цикла for-next на 0 to x. Активацию точки (0,0) можно устранить, если поставить оператор Plot непосредственно перед строкой next i.

Рис. 3.4. Результат работы алгоритма Брезенхема в первом октанте.

В следующем разделе описан общий алгоритм Брезенхема.

4. Общий алгоритм Брезенхема.

Чтобы реализация алгоритма Брезенхема была полной необходимо обрабатывать отрезки во всех октантах. Модификацию легко сделатть, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициепт. Когда абсолютная величина углового коэффициента больше 1, у постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x. Выбор постоянно изменяющейся (на +1 или -1) кооординаты зависит от квадранта (рис.4.1.). Общий алгоритм может быть оформлен в следующем виде:

Обобщенный целочисленный алгоритм Брезенхема квадрантов

предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают

все переменные считаются целыми

Sign - функция, возвращающая -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно

инициализация переменных

x = x1

y = y1

x = abs(x2 - x1)

y = abs(y2 - y1)

s1 = Sign(x2 - x1)

s2 = Sign(y2 - y1)

обмен значений x и y в зависимости от углового коэффициента наклона отрезка

if y < x then

Врем = x

x = y

y = Врем

Обмен = 1

else

Обмен = 0

end if

инициализация  с поправкой на половину пиксела

= 2*y - x

основной цикл

for i = 1 to x

Plot(x,y)

while( =>0)

if Обмен = 1 then

x = x + s1

else

y = y + s2

end if

= - 2*x

end while

if Обмен = 1 then

y = y + s2

else

x = x + s1

end if

= + 2*y

next i

finish

Рис.4.1. Разбор случаев для обобщенного алгоритма Брезенхема.

 

Пример 4.1. обобщенный алгоритм Брезенхема.

Для иллюсрации рассмотрим отрезок из точки (0,0) в точку (-8, -4).

начальные установки

x = 0

y = 0

x = 8

y = 4

s1 = -1

s2 = -1

Обмен = 0

е = 0

результаты работы пошагового цикла

i

Plot

е

x

y

 

 

0

0

0

1

(0,0)

 

 

 

 

 

-16

0

-1

 

 

-8

-1

-1

2

(-1,-1)

 

 

 

 

 

0

-2

-1

3

(-2,-1)

 

 

 

 

 

-16

-2

-2

 

 

-8

-3

-2

4

(-3,2)

 

 

 

 

 

0

-4

-2

5

(-4,2)

 

 

 

 

 

-16

-4

-3

 

 

-8

-5

-3

6

(-5,-3)

 

 

 

 

 

0

-6

-3

7

(-6,-3)

 

 

 

 

 

-16

-6

-4

 

 

-8

-7

-4

8

(-7,-4)

 

 

 

 

 

0

-8

-4

 

Рис.4.2. Результат работы обобщенного алгоритма Брезенхема в третьем квадранте.

На рис. 4.2 продемонстрирован результат. Сравнение с рис. 2.2 показывает, что результаты работы двух алгоритмов отличаются.

В следующем разделе рассматривается алгоритм Брезенхема для генерации окружности.

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

В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений, т. е. окружностей, эллипсов, парабол, гипербол, было посвящено значительное число работ . Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему . Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями, как это показано на рис. 5.1. Если сгенерирован первый октант (от 0 до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис. 5.1 приведены двумерные матрицы соответствующих преобразований.

Рис. 5.1. Генерация полной окружности из дуги в первом октанте.

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке х = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргументам (рис. 5.2). Аналогично, если исходной точкой является у = 0, х == R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке х = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.

Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис. 5.3 эти направления обозначены соответственно mH, mD, mV. Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из

mH = |(xi + 1)2 + (yi)2 -R2|

mD = |(xi + 1)2 + (yi -1)2 -R2|

mV = |(xi )2 + (yi -1)2 -R2|

Рис. 5.2. Окружность в первом квадранте.

 

Рис.5.3. Выбор пикселов в первом квадранте.

Вычисления можно упростить, если заметить, что в окрестности точки (xi,yi,) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис. 5.4.

Рис. 5.4. Пересечение окружности и сетки растра.

Разность между квадратами расстояний от центра окружности до диагонального пиксела (xi, + 1, уi - 1) и от центра до точки на окружности R2 равна

i = (xi + 1)2 + (yi -1)2 -R2 

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

При i < 0 диагональная точка (xi, + 1, уi - 1) находится внутри реальной окружности, т. е. это случаи 1 или 2 на рис. 5.4. Ясно, что в этой ситуации следует выбрать либо пиксел (xi, + 1, уi), т. е. mH, либо пиксел (xi, + 1, уi - 1), т. е. mD. Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях:

 = |(xi + 1)2 + (yi )2 -R2| - |(xi + 1)2 + (yi -1)2 -R2|

При  < 0 расстояние от окружности до диагонального пиксела больше, чем до горизонтального. Напротив, если  > 0, расстояние до горизонтального пиксела больше. Таким образом,

при  <= 0 выбираем mH в (xi, + 1, уi - 1)

при  > 0 выбираем mD в (xi, + 1, уi - 1)

При  = 0, когда расстояние от окружности до обоих пикселов одинаковы, выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины , можно сократить, если заметить, что в случае 1

(xi + 1)2 + (yi )2 -R2 >= 0

(xi + 1)2 + (yi -1)2 -R2 < 0

так как диагональный пиксел (xi, + 1, уi - 1) всегда лежит внутри окружности, а горизонтальный (xi, + 1, уi ) - вне ее. Таким образом,  можно вычислить по формуле

= (xi + 1)2 + (yi )2 -R2 + (xi + 1)2 + (yi -1)2 -R2

Дополнение до полного квадрата члена (yi )2 с помощью добавления и вычитания - 2yi + 1 дает

= 2[(xi + 1)2 + (yi -1)2 -R2] + 2yi - 1

В квадратных скобках стоит по определению i и его подстановка

= 2( i + yi ) - 1

существенно упрощает выражение.

Рассмотрим случай 2 на рис. 5.4 и заметим, что здесь должен быть выбран горизонтальный пиксел (xi, + 1, уi), так как .у является монотонно убывающей функцией. Проверка компонент  показывает, что

(xi + 1)2 + (yi )2 -R2 < 0

(xi + 1)2 + (yi -1)2 -R2 < 0

поскольку в случае 2 горизонтальный (xi, + 1, уi) и диагональный (xi, + 1, уi -1) пикселы лежат внутри окружности. Следовательно,  < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (xi, + 1, уi).

Если i > 0, то диагональная точка (xi, + 1, уi -1) находится вне окружности, т. е. это случаи 3 и 4 на рис. 5.4. В данной ситуации ясно, что должен быть выбран либо пиксел (xi, + 1, уi -1), либо (xi, , уi -1). Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального mD и вертикального mV пикселов,

т. е. ' = |(xi + 1)2 + (yi -1)2 -R2| - |(xi)2 + (yi -1)2 -R2 |

При' < 0 расстояние от окружности до вертикального пиксела (xi, , уi -1) больше и следует выбрать диагональный шаг к пикселу (xi, + 1, уi -1). Напротив, в случае' > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (xi, , уi -1). Таким образом,

при ' <= 0 выбираем mD в (xi +1, , уi -1)

при ' > 0 выбираем mV в (xi, , уi -1)

Здесь в случае ' = 0, т. е. когда расстояния равны, выбран диагональный шаг.

Проверка компонент ' показывает, что

(xi )2 + (yi -1)2 -R2 >= 0

(xi + 1)2 + (yi -1)2 -R2 < 0

поскольку для случая 3 диагональный пиксел (xi +1, уi -1) находится вне окружности, тогда как вертикальный пиксел (xi, , уi -1) лежит внутри ее. Это позволяет записать ' в виде

' = (xi +1)2 + (yi -1)2 -R2 + (xi )2 + (yi -1)2 -R2

Дополнение до полного квадрата члена (xi)2 с помощью добавления и вычитания 2xi + 1 дает

' = 2[(xi +1)2 + (yi -1)2 -R2] - 2xi - 1

Использование определения i приводит выражение к виду

' = 2( i - xi )- 1

Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (xi, уi -1), так как у является монотонно убывающей функцией при возрастании х. 

Проверка компонент ' для случая 4 показывает, что

(xi +1)2 + (yi -1)2 -R2 > 0

(xi )2 + (yi -1)2 -R2 > 0

поскольку оба пиксела находятся вне окружности. Следовательно, ' > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор mV. 

Осталось проверить только случай 5 на рис. 5.4, который встречается, когда диагональный пиксел (xi, , уi -1) лежит на окружности, т. е. i = 0. Проверка компонент  показывает, что

(xi +1)2 + (yi)2 -R2 > 0

(xi +1)2 + (yi -1)2 -R2 = 0

Следовательно,  > 0 и выбирается диагональный пиксел (xi +1 , уi -1) . Аналогичным образом оцениваем компоненты ' : 

(xi +1)2 + (yi -1)2 -R2 = 0

(xi +1)2 + (yi -1)2 -R2 < 0

и ' < 0, что является условием выбора правильного диагонального шага к (xi +1 , уi -1) . Таким образом, случай i = 0 подчиняется тому же критерию, что и случай i < 0 или i > 0. Подведем итог полученных результатов:

i < 0

 <= 0 выбираем пиксел (xi +1 , уi ) - mH 

 > 0 выбираем пиксел (xi +1 , уi -1) - mD

i > 0

' <= 0 выбираем пиксел (xi +1 , уi -1) - mD

' > 0 выбираем пиксел (xi , уi -1)- mV 

i = 0 выбираем пиксел (xi +1 , уi -1) - mD

Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг mH к пикселу (xi + 1, уi). Обозначим это новое положение пиксела как (i + 1). Тогда координаты нового пиксела и значение i равны

xi+1 = xi +1

yi+1 = yi

i+1 = (xi+1 +1)2 + (yi+1 -1)2 -R2 i + 2xi+1+ 1

Аналогично координаты нового пиксела и значение i для шага mD к пикселу (xi + 1, уi -1) таковы:

xi+1 = xi +1

yi+1 = yi -1

i+1 = i + 2xi+1 - 2yi+1 +2

То же самое для шага mV к (xi, уi -1)

xi+1 = xi

yi+1 = yi -1

i+1 = i - 2yi+1 +1

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

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

все переменные - целые

инициализация переменных

xi = 0

yi = R

i = 2(1 - R)

Предел = 0

1 Plot (xi, yi

if yi <= Предел then 4 

Выделение случая 1 или 2, 4 или 5, или 3

if i < 0 then 2 

ifi > 0 then 3 

ifi= 0 then 20

определение случая 1 или 2

2 = 2i + 2уi - 1

if <= 0 then 10

if > 0 then 20

определение случая 4 или 5

3 = 2i + 2хi - 1

if <= 0 then 20 

if > 0 then 30

выполнение шагов 

шаг к mH

10 хi = хi + 1

i = i+ 2хi + 1

gо to 1 

шаг mD

20 хi = хi + 1

yi = yi + 1

i = i+ 2хi - 2уi+ 2

gо to 1 

4 finish

Переменная предела устанавливается в нуль для окончания работы алгоритма на горизонтальной оси, в результате генерируется окружность в первом квадранте. Если необходим лишь один из октантов, то второй октант можно получить с помощью установки Предел = Integer (R/sqrt(2)), а первый - с помощью отражения второго октанта относительно прямой у = х (рис. 5.1). Блок-схема алгоритма приводится на рис. 5.5.

Рис. 5.5. Блок-схема пошагового алгоритма Брезенхема для генерации окружности в первом квадранте.

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

Рассмотрим окружность радиусом 8 с центром в начале координат. Генерируется только первый квадраннт.

начальные установки

x = 0

y = 8

= 2(1-8) = -14

Предел = 0

Пошаговое выполнение основного цикла

1 Plot (0,8)

yi > Предел (продолжать)

i < 0 go to 2

2 go to 10

10 x = 0+1 = 1

i = -14 +2 + 1 = -11

go to 1

1 Plot (1,8)

yi > Предел (продолжать)

i < 0 go to 2

2 go to 10

10 x = 1+1 = 1

i = -11 +2(2) + 1 = -6

go to 1

1 Plot (2,8)

...

Продолжать

Результаты всех последовательных проходов алгоритма сведены в таблицу. Список пикселов выбранных алгоритмов состоит из (0,8), (1,8), (2,8), (3,7), (4,7), (5,6), (6,5), (7,4), (7,3), (8,2), (8,1), (8,0).

 

Plot

i

'

x

y

 

-14

 

 

0

8

(0,8)

 

 

 

 

 

 

-11

-13

 

0

8

(1,8)

 

 

 

 

 

 

-6

-7

 

2

8

(2,8)

 

 

 

 

 

 

-12

3

 

3

7

(3,7)

 

 

 

 

 

 

-3

11

 

4

7

(4,7)

 

 

 

 

 

 

-3

7

 

5

6

(5,6)

 

 

 

 

 

 

1

5

 

6

5

(6,5)

 

 

 

 

 

 

9

 

-11

7

4

(7,4)

 

 

 

 

 

 

4

 

3

7

3

(7,3)

 

 

 

 

 

 

18

 

-7

8

2

(8,2)

 

 

 

 

 

 

17

 

19

8

1

(8,1)

 

 

 

 

 

 

18

 

17

8

0

(8,0)

 

 

 

 

 

алгоритм завершен.

Результаты показаны на рис.5.6. вместе с реальной окружностью. Алгоритм легко обобщается для других квадрантов или дуг окружностей.

Рис. 5.6. Результаты работы пошагового алгоритма Брезенхема генерации окружности.

 


Алгоритмы растровой графики

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

Рис. 28. Растеризация отрезка прямой линии.

Термин “пиксел” образован от английского pixel (picture element - элемент изображения)  - то есть точка на экране. Будем считать, что пикселы имеют целочисленные координаты. На первый взгляд кажется, что эта задача имеет простое решение. Пусть конечные точки отрезка имеют целочисленные координаты, и уравнение прямой, содержащей отрезок: . Не нарушая общности, будем также считать, что тангенс угла наклона прямой лежит в пределах от 0 до 1. Тогда для изображения отрезка на растре достаточно для всех целых , принадлежащих отрезку, выводить на экран точки с координатами . Однако в этом методе присутствует операция умножения . Хотелось бы иметь алгоритм без частого использования операции умножения вещественных чисел. Избавиться от операции умножения можно следующим образом. Поскольку , то один шаг по целочисленной сетке на оси  будет соответствовать . Отсюда получаем, что  будет увеличиваться на величину . Итерационная последовательность выглядит следующим образом:

,  

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

Для вывода формул алгоритма Брезенхема рассмотрим рис. 29.

Рис. 29. Рисование отрезков прямых по методу Брезенхема.

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

, ,

 

.

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

Пусть на предыдущем шаге , тогда  и . Если же на предыдущем шаге , то и .

Осталось узнать как вычислить . Так как при :

, .

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

Procedure Bresenham(x1,y1,x2,y2,Color: integer);

var

dx,dy,incr1,incr2,d,x,y,xend: integer;

begin

 dx:= ABS(x2-x1);

 dy:= Abs(y2-y1);

 d:=2*dy-dx;  {начальное значение для d}

 incr1:=2*dy;  {приращение для d<0}

 incr2:=2*(dy-dx); {приращение для d>=0}

  if x1>x2 then  {начинаем с точки с меньшим знач. x}

 begin

 x:=x2;

 y:=y2;

 xend:=x1;

end

else

begin

 x:=x1;

 y:=y1;

 xend:=x2;

end;

PutPixel(x,y,Color); {первая точка отрезка}

 While x<xend do

 begin

x:=x+1;

  if d<0 then

    d:=d+incr1  {выбираем нижнюю точку}

  else

begin

 y:=y+1;

 d:=d+incr2; {выбираем верхнюю точку, y-возрастает}

end;

  PutPixel(x,y,Color);

 end;{while}

end;{procedure}

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

.

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

 


 

А также другие работы, которые могут Вас заинтересовать

45298. Классификация опорных сетей радиодоступа. Характеристики систем радиодоступа. Регламент радиосвязи РФ: содержание, виды радиосвязи, службы, выделение полос. Федеральные, региональные и международные стандарты системы радиосвязи 914 KB
  Классификация опорных сетей радиодоступа. Характеристики систем радиодоступа. Под сетью радиодоступа понимают радиальнозоновую сеть радиосвязи предназначенную для предоставления услуг связи с качеством не уступающим качеству проводных систем связи. В состав сети радиодоступа входят базовые станции коммутационное оборудование К вспомогательные технические средств и программное обеспечение с помощью которых формируется территориальная зона на которой возможны подключения через радиоинтерфейс абонентских станций: В систему...
45299. Классификация радиорелейных линий связи. РРЛ прямой видимости: принципы построения, методы разделения каналов 75.5 KB
  РРЛ прямой видимости: принципы построения методы разделения каналов. Тропосферные РРЛ. Радиорелейные линии РРЛ представляют собой цепочку приемопередающих радиостанций оконечных промежуточных узловых которые осуществляют последовательную многократную ретрансляцию прием преобразование усиление и пе редачу передаваемых сигналов. Классификация радиорелейных линий В зависимости от используемого вида распространения радиоволн РРЛ можно разделить на две группы: прямой видимости и тропосферные.
45300. Спутниковые системы связи. Принцип действия, классификация. Примеры спутниковых систем связи 47.5 KB
  Спутниковые системы связи. Примеры спутниковых систем связи. СС отличаются орбитами спутников: формой круговая эллиптическая высота над Землёй наклон к экватору экваториальные полярные наклонные. На ней несколько сотен спутников что потребовало международного регулирования.
45301. Классификация и особенности транкинговых систем связи. Системы подвижной радиосвязи: принципы построения и функционирования, диапазоны частот, методы аналоговой и цифровой модуляции, методы кодирования, управление в СПС 104.5 KB
  Используемый частотный диапазон 400 450 800 900 1800 1900 МГц 2. Возможность роуминга Эстафетная передача Принцип выбора базовой станции с наибольшим уровнем сигнала MPS800 усовершенствованная мобильная телефонная служба диапазон частот 800МГц. Система работает в диапазоне 824894 МГц и имеет 666 дуплексных каналов при ширине полосы каждого канала 30КГц. Диапазон частот 825890 МГц.
45302. Характеристики систем подвижной связи. Стандарт сотовых систем связи (ССС). Пути усовершенствования ССС 45 KB
  Характеристики систем подвижной связи. Стандарт сотовых систем связи ССС. Системы подвижной радиосвязи предназначены для связи между движущимся абонентом и абонентом ТФОП или между двумя движущимися абонентами. Виды систем связи подвижной службы К основным видам ССПС относятся: региональные мобильные системы наземной связи; глобальные мобильные системы спутниковой связи; системы персонального радиовызова СПРВ.
45303. Стандарт GSM: услуги, архитектура, назначение узлов MSC, кодирование и модуляция, интерфейсы, каналы сигнализации и трафика, хэндовер, протоколы, частотный план структура кадров трафика и управления, речевое кодирование 1.08 MB
  Стандарт GSM: услуги архитектура назначение узлов MSC кодирование и модуляция интерфейсы каналы сигнализации и трафика хэндовер протоколы частотный план структура кадров трафика и управления речевое кодирование. Система сотовой связи стандарта GSM. Разработка GSM началась в 1982 году группой из 26 Европейских национальных телефонных компаний. В 1989 году Европейский Телекоммуникационный Институт Стандартов ETSI взял ответственность за дальнейшее развитие GSM.
45304. Стандарт CDMA: услуги, архитектура, кодирование и модуляция, прямые и обратные каналы трафика и управления, хэндовер и управление мощностью, борьба с многолучевостью. Кодирование в прямом и обратном каналах. Достоинства и недостатки CDMA 4.39 MB
  Стандарт CDM: услуги архитектура кодирование и модуляция прямые и обратные каналы трафика и управления хэндовер и управление мощностью борьба с многолучевостью. Достоинства и недостатки CDM. CDM англ. 1995 год – коммерческая эксплуатация первой СПС с CDM.
45305. Перспективный план нумерации для ЕСЭ РФ. Отличия нумерации в СПС, нумерация в GSM. Перспективы развития плана нумерации 342.1 KB
  Перспективный план нумерации для ЕСЭ РФ. Отличия нумерации в СПС нумерация в GSM. Перспективы развития плана нумерации. Под системой нумерации понимается совокупность правил позволяющих идентифицировать сети их фрагменты а также вызывающих и вызываемых пользователей.
45306. Сотовые сеты связи третьего поколения. Концепция, отличительные черты, услуги. Основные стандарты, их характеристика, пути развития. Цели проекта IMT-2000 92.86 KB
  Радиоинтерфейсы: IMTDS – использует DSCDM и FDD IMTMC – использует MCCDM и FDD IMTTC – использует TDM CDM и TDD IMTSС – использует TDM и FDD IMTFT – MCTDM и FDD TDD IMT dvnced – для систем связи с одновременной передачей нескольких ортогональных несущих OFDM и FDD. Характеристика систем 3 поколения Системы основанные на CDM WCDM: Разработана японской фирмой REB. Сети GSM не могут быть модернизированы для работы с WCDM хотя например GPRS может многократно транслироваться через сеть CDM. Отличия от CDM One – отсутствие...