Алгоритмы растровой развертки отрезков
- Цифровой дифференциальный анализатор. Решается дифференциальное уравнение вида dY/dX = Py/Px, где Py = Yk - Yn - приращение координат отрезка по оси Y, а Px = Xk - Xn - приращение координат отрезка по оси X. При этом ЦДА формирует дискретную аппроксимацию непрерывного решения этого дифференциального уравнения. В обычном ЦДА, используемом, как правило, в векторных устройствах, тем или иным образом определяется количество узлов N, используемых для аппроксимации отрезка. Затем за N циклов вычисляются координаты очередных узлов. Получаемые значения Xi, Yi преобразуются в целочисленные значения координаты очередного подсвечиваемого пикселя либо округлением, либо отбрасыванием дробной части. Генератор векторов, использующий этот алгоритм, имеет тот недостаток, что точки могут прописываться дважды, что увеличивает время построения. Кроме того из-за независимого вычисления обеих координат нет предпочтительных направлений и построенные отрезки кажутся не очень красивыми.
-
Алгоритм Брезенхема. Так как приращения координат, как правило, не являются целой степенью двойки, то в ЦДА-алгоритме требуется выполнение деления, что не всегда желательно, особенно при аппаратной реализации. Брезенхем предложил алгоритм, не требующий деления, как и в алгоритме несимметричного ЦДА, но обеспечивающий минимизацию отклонения сгенерированного образа от истинного отрезка, как в алгоритме обычного ЦДА. Основная идея алгоритма состоит в том, что если угловой коэффициент прямой < 1/2, то естественно точку, следующую за точкой (0,0), поставить в позицию (1,0) (рис. а), а если угловой коэффициент > 1/2, то - в позицию (1,1) (рис. б). Для принятия решения куда заносить очередной пиксел вводится величина отклонения Е точной позиции от середины между двумя возможными растровыми точками в направлении наименьшей относительной координаты. Знак Е используется как критерий для выбора ближайшей растровой точки. Если Е < 0, то точное Y-значение округляется до последнего меньшего целочисленного значения Y, т.е. Y-координата не меняется по сравнению с предыдущей точкой. В противном случае Y увеличивается на 1.
- Модифицированный алгоритм Брезенхема. Основная идея алгоритма состоит в том, чтобы для ребер многоугольника устанавливать яркость пикселя пропорционально площади пикселя, попавшей внутрь многоугольника.
2015-05-30
1761
