4. Требования, предъявляемые к алгоритмам вычерчивания отрезков. Пошаговый алгоритм разложения отрезка в растр. Разложение в растр по методу цифрового дифференциального анализатора.
Процесс нахождения пикселей, наилучшим образом аппроксимирующих заданный отрезок, называется разложением отрезка в растр.
Требования
- отрезки должны выглядеть прямыми; начинаться и заканчиваться в заданных точках
- яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона
- алгоритмы должны работать быстро
Первое требование в силу дискретной природы растрового дисплея выполнено всегда быть не может. Можно лишь добиться того, что визуально (человеческим глазом) отрезок будет восприниматься прямым. Решение этой задачи может достигаться путем увеличения разрешающей способности экрана дисплея и применения методов устранения ступенчатости.
Второму требованию удовлетворяют также только горизонтальные, вертикальные и наклоненные под углом в 45 отрезки. Однако вертикальные и горизонтальные отрезки по сравнению с отрезками, расположенными под 45 , будут выглядеть ярче, так как расстояние между соседними пикселами у них меньше, чем у наклонных отрезков. Обеспечение постоянной яркости вдоль отрезка требует высвечивания очередного пиксела яркостью, зависящей от расстояния между пикселами, вычисление которого производится с использованием операций извлечения квадратного корня и умножения. Использование этих операций существенно замедляет работу алгоритма, поэтому второе требование остается, как правило, невыполненным.
Удовлетворение третьего требования достигается путем сведения к минимуму вычислительных операций, использования операций над целочисленными данными, а также реализацией алгоритмов на аппаратном или микропрограммном уровне.
Базовые алгоритмы могут использовать численные и инкрементные (пошаговые) методы. В численных методах построения кривых и отрезков используется уравнение кривой (отрезка) и частные производные. Обычно исследуются точки пересечения кривой с горизонтальными линиями (y = n, где n-константа). В пошаговых методах на каждом шаге вычисляется направление элементарного движения от текущей точки к следующей. При этом удается использовать целочисленную арифметику и избежать выполнения операций умножения и деления.
Первый алгоритм вычерчивания отрезков - по методу цифрового дифференциального анализатора (ЦДА) - использует достаточно общий принцип, известный в математике: изучение какого-либо явления на основе дифференциального уравнения или системы таких уравнений, описывающей это явление.
В рассматриваемых здесь алгоритмах большее из приращений (ΔX или ΔY) выбирается в качестве единицы растра, а приращение вдоль другой координатной оси подлежит определению. Если же поступить по-другому (меньшее из приращений взять равным единице), то отрезок на экране может получиться "дырявым", то есть состоящим из отдельных точек, не расположенных вплотную друг к другу.