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

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

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

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

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

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

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