Алгоритмы вычерчивания отрезков

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

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.