06. Основные расчетные соотношения и алгоритм Брезенхема для генерации окружности. - p1xelse/CG GitHub Wiki

Генерация окружности/эллипса начинается из точки (0, R) / (0, b).

В случае окружности, требуется вычислить лишь 1/8 от всей дуги, а остальное получить путём отражения на другие участки кривой (поэтому цикл будет идти до точки, где x=y). При генерации 1/8 окружности выбор происходит из двух пикселей, см !53 Аналогично для эллипса, требуется лишь 1/4 (цикл до точки y=0).

Для любого пиксела при выбранном направлении генерации окружности (тот же issue) существует только три варианта выбора следующего пиксела, наилучшим образом аппроксимирующего окружность: горизонтальный пиксел вправо, диагональный вниз и вправо, вертикальный вниз.

В качестве критерия выбора очередного пиксела используется минимум модуля разности квадратов расстояний от центра окружности до пиксела и до идеальной окружности:

В окрестности текущей точки возможны пять вариантов прохождения окружности:

1. между горизонтальным (Xi+1,Yi) и диагональным (Xi+1,Yi-1) пикселами;
2. между горизонтальным (Xi+1,Yi) и другим диагональным Xi+1,Yi+1) пикселами;
3. между вертикальным (Xi,Yi-1) и диагональным (Xi+1,Yi-1);
4. между вертикальным (Xi,Yi-1) и третьим диагональным (Xi-1,Yi-1) пикселами;
5. прохождение точно через диагональный (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, которая проходит через диагональный пиксель.

Алгоритм:

1. Ввод исходных данных R (радиус окружности) и при необходимости Xc, Yc (координаты центра окружности)
   
2. Задание начальных значений текущих координат пикселя X=0, Y=R, параметра D=2(1-R), установка конечного значения ординаты пикселя Yk=0
   
3. Высвечивание текущего пикселя (X, Y)
   
4. Проверка окончания работы: если Y<Yk, то переход к п.11
   
5. Анализ значения параметра D: если D < 0, то переход к п.6; если D = 0, то переход к п.9, иначе переход к п.7
   
6. Вычисление параметра D1 = 2D+2Y-1 и анализ полученного значения: если D1 < 0, то переход к п.8; Если D1>0, то переход к п.9
   
7. Вычисление параметра D2 = 2D-2X-1 и анализ полученного значения; если D2 < 0, то переход к п.9, если D2 > 0, то переход к п.10
   
8. Вычисление новых значений X и D (горизонтальный шаг): X=X+1; D=D+2X+1. Переход к п.3
   
9. Вычисление новых значений X,Y,D (диагональный шаг): X=X+1; Y=Y-1;D=D+2(X-Y+1). Переход к п.3
   
10. Вычисление новых значений Y и D (вертикальный шаг): Y=Y-1;D=D-2Y+1. Переход к п.3
    
11. Конец