Алгоритмы компьютерной графики

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

Рис. 1.3 Восьмисвязность
Известны также четырехсвязные алгоритмы (рис. 1.4).

Рис. 1.4. Четырехсвязность

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