Требования, предъявляемые к алгоритмам вычерчивания отрезков. Пошаговый алгоритм разложения отрезка в растр. Разложение в растр по методу цифрового дифференциального анализатора.
Процесс нахождения пикселей, наилучшим образом аппроксимирующих заданный отрезок, называется разложением отрезка в растр.
Требования
- отрезки должны выглядеть прямыми; начинаться и заканчиваться в заданных точках
- яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона
- алгоритмы должны работать быстро
Первое требование в силу дискретной природы растрового дисплея выполнено всегда быть не может. Можно лишь добиться того, что визуально (человеческим глазом) отрезок будет восприниматься прямым. Решение этой задачи может достигаться путем увеличения разрешающей способности экрана дисплея и применения методов устранения ступенчатости.
Второму требованию удовлетворяют также только горизонтальные, вертикальные и наклоненные под углом в 45 отрезки. Однако вертикальные и горизонтальные отрезки по сравнению с отрезками, расположенными под 45 , будут выглядеть ярче, так как расстояние между соседними пикселами у них меньше, чем у наклонных отрезков. Обеспечение постоянной яркости вдоль отрезка требует высвечивания очередного пиксела яркостью, зависящей от расстояния между пикселами, вычисление которого производится с использованием операций извлечения квадратного корня и умножения. Использование этих операций существенно замедляет работу алгоритма, поэтому второе требование остается, как правило, невыполненным.
|
|
|
Удовлетворение третьего требования достигается путем сведения к минимуму вычислительных операций, использования операций над целочисленными данными, а также реализацией алгоритмов на аппаратном или микропрограммном уровне.
Базовые алгоритмы могут использовать численные и инкрементные (пошаговые) методы. В численных методах построения кривых и отрезков используется уравнение кривой (отрезка) и частные производные. Обычно исследуются точки пересечения кривой с горизонтальными линиями (y = n, где n-константа). В пошаговых методах на каждом шаге вычисляется направление элементарного движения от текущей точки к следующей. При этом удается использовать целочисленную арифметику и избежать выполнения операций умножения и деления.
Первый алгоритм вычерчивания отрезков - по методу цифрового дифференциального анализатора (ЦДА) - использует достаточно общий принцип, известный в математике: изучение какого-либо явления на основе дифференциального уравнения или системы таких уравнений, описывающей это явление.
В рассматриваемых здесь алгоритмах большее из приращений (ΔX или ΔY) выбирается в качестве единицы растра, а приращение вдоль другой координатной оси подлежит определению. Если же поступить по-другому (меньшее из приращений взять равным единице), то отрезок на экране может получиться "дырявым", то есть состоящим из отдельных точек, не расположенных вплотную друг к другу.
|
|
|
Алгоритмы Брезенхема разложения отрезков в растр. Простой алгоритм Брезенхема. Целочисленный алгоритм Брезенхема. Общий алгоритм Брезенхема
Работа алгоритма Брезенхема основывается на использовании понятия ошибка.
Ошибкой здесь называется расстояние между действительным положением отрезка и ближайшим пикселом сетки растра, который аппроксимирует отрезок на очередном шаге.
Согласно алгоритму на каждом шаге одна из координат - либо x, либо y (в зависимости от угла наклона отрезка) изменяется на единицу, изменение другой координаты (на ноль или единицу) определяется в процессе работы и зависит от значения ошибки. Таким образом, выбирается пиксел, ближе расположенный к идеальному отрезку. Поскольку при реализации алгоритма на ЭВМ удобнее анализировать не само значение ошибки, а ее знак, то истинное значение ошибки смещается на -0.5.
Простой алгоритм Брезенхема
- Ввод исходных данных Xн,Yн,Xк,Yк
- Проверка вырожденности отрезка. Если отрезок вырожденный, то высвечивается точка и осуществляется переход к п.8
- Вычисление приращений dX=Xк-Xн и dY=Yк-Yн.
- Вычисление модуля тангенса угла наклона отрезка: m=dY/dX
- Инициализация начального значения ошибки: f=m-0,5
- Инициализация начальных значений координат текущего пиксела: X=Xн, Y=Yн
- Цикл от i=1 до i=dX+1 с шагом 1:
- Высвечивание точки с координатами (X,Y)
- Если f<0, то
a) Y++
b) f-- - Вычисление ошибки f=f+m
- X++
|
|
|
Дата добавления: 2019-01-14; просмотров: 466; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!