06. Основные расчетные соотношения и алгоритм Брезенхема для генерации окружности. - chrislvt/CG GitHub Wiki
Генерация окружности/эллипса начинается из точки (0, R) / (0, b).
В случае окружности, требуется вычислить лишь 1/8 от всей дуги, а остальное получить путём отражения на другие участки кривой (поэтому цикл будет идти до точки, где x=y). При генерации 1/8 окружности выбор происходит из двух пикселей, см !53 Аналогично для эллипса, требуется лишь 1/4 (цикл до точки y=0).
Для любого пиксела при выбранном направлении генерации окружности (тот же issue) существует только три варианта выбора следующего пиксела, наилучшим образом аппроксимирующего окружность: горизонтальный пиксел вправо, диагональный вниз и вправо, вертикальный вниз.
В качестве критерия выбора очередного пиксела используется минимум модуля разности квадратов расстояний от центра окружности до пиксела и до идеальной окружности:
В окрестности текущей точки возможны пять вариантов прохождения окружности:
- между горизонтальным (Xi+1,Yi) и диагональным (Xi+1,Yi-1) пикселами;
- между горизонтальным (Xi+1,Yi) и другим диагональным Xi+1,Yi+1) пикселами;
- между вертикальным (Xi,Yi-1) и диагональным (Xi+1,Yi-1);
- между вертикальным (Xi,Yi-1) и третьим диагональным (Xi-1,Yi-1) пикселами;
- прохождение точно через диагональный (Xi+1,Yi-1) пиксел.
По аналогии с ошибкой в алгоритме построения отрезков выберем и здесь некоторую величину, анализ знака которой позволит выбрать нужный пиксел.
Такой величиной D является разность квадратов расстояний от центра окружности до диагонального (Xi+1,Yi-1) пиксела и до идеальной окружности:
При Di < 0, нам подходят только кривые 1 и 2:
Параметр (если первый модуль > 0, а второй < 0)
Если D1 > 0, то должны выбрать диагональный пиксель, иначе при D1 <= 0 - горизонтальный
При Di > 0, нам подходят кривые 3, 4:
Параметр (если первый модуль > 0, а второй < 0)
Если D2 > 0, то выбираем вертикальный пиксель, иначе при D2 <= 0 - диагональный
Начальное значение D для x=0, y=R будет равно:
При Di = 0, подходит кривая 5, которая проходит через диагональный пиксель.
Алгоритм:
- Ввод исходных данных R (радиус окружности) и при необходимости Xc, Yc (координаты центра окружности)
- Задание начальных значений текущих координат пикселя X=0, Y=R, параметра D=2(1-R), установка конечного значения ординаты пикселя Yk=0
- Высвечивание текущего пикселя (X, Y)
- Проверка окончания работы: если Y<Yk, то переход к п.11
- Анализ значения параметра D: если D < 0, то переход к п.6; если D = 0, то переход к п.9, иначе переход к п.7
- Вычисление параметра D1 = 2D+2Y-1 и анализ полученного значения: если D1 < 0, то переход к п.8; Если D1>0, то переход к п.9
- Вычисление параметра D2 = 2D-2X-1 и анализ полученного значения; если D2 < 0, то переход к п.9, если D2 > 0, то переход к п.10
- Вычисление новых значений X и D (горизонтальный шаг): X=X+1; D=D+2X+1. Переход к п.3
- Вычисление новых значений X,Y,D (диагональный шаг): X=X+1; Y=Y-1;D=D+2(X-Y+1). Переход к п.3
- Вычисление новых значений Y и D (вертикальный шаг): Y=Y-1;D=D-2Y+1. Переход к п.3
- Конец