Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Алгоритм вывода прямой линии
Поскольку экран растрового дисплея с электронно-лучевой трубкой (ЭЛТ) можно рассматривать как матрицу дискретных элементов (пикселов), каждый из которых может быть подсвечен, нельзя непосредственно провести отрезок из одной точки в другую. Процесс определения пикселов, наилучшим образом аппроксимирующих заданный отрезок, называется разложением в растр. В сочетании с процессом построчной визуализации изображения он известен как преобразование растровой развертки. Для горизонтальных, вертикальных и наклоненных под углом 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
ifi > 0 then 3
if i= 0 then 20
определение случая 1 или 2
2 = 2i + 2уi - 1
if <= 0 then 10
if > 0 then 20
определение случая 4 или 5
3 = 2i + 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}