1.3. Инкрементные алгоритмы
Брезенхэм предложил подход, позволяющий разрабатывать так называемые инкрементные алгоритмы растеризации. Основной целью при разработке таких алгоритмов было построение циклов вычисления координат на основе только целочисленных операций сложения/вычитания без использования умножения и деления. Были разработаны инкрементные алгоритмы не только для прямых, но и для кривых линий.
Инкрементные алгоритмы выполняются как последовательное вычисление координат соседних пикселов путем добавления приращений координат. Приращения рассчитываются на основе анализа функции погрешности. В цикле выполняются только целочисленные операции сравнения и сложения/вычитания. Достигается повышение быстродействия для вычислений каждого пиксела по сравнению с прямым способом.
Рассмотрим пример работы приведенного выше алгоритма Брезенхэма для отрезка (х1у1 - х2у2) = (2, 3 - 8, 6). Этот алгоритм восьмисвязный, то есть при выполнении приращений координат для перехода к соседнему пикселу возможны восемь случаев (рис. 1.3).
1
Рис. 1.3 Восьмисвязность
Известны также четырехсвязные алгоритмы (рис. 1.4).
2
Рис. 1.4. Четырехсвязность

Четырехсвязные алгоритмы проще, но они генерируют менее качественное изображение линий за большее количество тактов работы. Для приведенного примера четырехсвязный алгоритм работает 10 тактов, а восьмисвязный — только 7.

 

 

Используются технологии uCoz