Главная
»
Информационные системы
»
Компьютерная геометрия и графика
»
Алгоритмы вычерчивания отрезков
Алгоритмы вычерчивания отрезков
Посколку экран растрового дисплея с электронно-лучевой трубкой (ЭЛТ) можно рассматривать как матрицу дискретных элементов (пикселов), каждый из которых может быть подсвечен, нельзя непосредственно провести отрезок из одной точки в другую. Процесс определения пикселов, наилучшим образом аппроксимирующих заданный отрезок, называется разложением в растр. В сочетании с процессом построчной визуализации изображения он известен как преобразование растровой развертки. Для горизонтальных, вертикальных и наклоненных под углом 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
Простой алгоритм разложения отрезка в растр, описанный в следующем разделе, иллюстрирует применение пошаговых методов.
2. Алгоритмы вычерчивания отрезков прямых линий. Целочисленный алгоритм Брезенхема.
Алгоритм Брезенхэ́ма — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике. Отрезок рисуется между двумя точками — (x0,y0) и (x1,y1), где в этих парах указаны колонка и строка, соответственно, номера которых растут вправо и вниз. Сначала мы будем предполагать, что наша линия идёт вниз и вправо, причём горизонтальное расстояние x1 − x0 превосходит вертикальное y1 − y0, т.е. наклон линии от горизонтали — менее 45°. Наша цель состоит в том, чтобы для каждой колонки x между x0 и x1, определить, какая строка y ближе всего к линии, и нарисовать точку (x,y).Общая формула линии между двумя точками:
Поскольку мы знаем колонку — x, то строка — y — получается округлением к целому следующего значения:
Однако, вычислять точное значение этого выражения нет необходимости, достаточно заметить, что y растёт от y0 и за каждый шаг мы добавляем к x единичку и добавляем к y значение наклона
Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.