КГ Лекция 04. Растровая графика.Базовые алгоритмы машинной графики. Построение окружностей

Построение окружности

Самый простой подход к построению окружности может заключаться в использовании ее уравнения

Каноническое уравнение окружности

a = Xc, b = Yc, C(a, b)

(X - Xс)^2 + (Y - Yс)^2 = R^2
или
X^2 + Y^2 = R^2

где Xс,Yс - координаты центра, R - радиус окружности

Параметрическое уравнение окружности

X = Xс + R*cos(t) 
Y = Yс + R*sin(t)

где Xс,Yс - координаты центра, R - радиус окружности, t - параметр (0 < t < 2pi).

При этом, учитывая тот факт, что шаг изменения аргумента должен составлять величину t = 1 / R, рассчитать для каждого значения параметра t значения координат соответствующих точек окружности и соединить их затем отрезками прямых. Такой путь требует довольно большого количества вычислений.

Метод средней точки для построения окружности

Линия разбивается на единичные интервалы и на каждом шаге определяются координаты пикселей, которые находятся ближе всего к заданной окружности.

При известном радиусе R и координатах центра окружности на экране (Xc, Yc) вначале можно организовать алгоритм таким образом, чтобы рассчитать координаты пикселей вокруг окружности с центром в начале координат (0, 0).
После того каждое рассчитанное положение (X, Y) перемещается в соответствующую ему точку на экране для чего:
- Xc прибавляется к X
- Yc прибавляется к Y
На дуге окружности от X = 0 до X = Y в первом квадрате тангенс угла наклона кривой меняется 0 до 1.

Tаким образом, в этом октанте можно брать 1 шаг в положительном направлении координаты X и на основе параметра принятия решения определять, какой из пикселей в каждом столбце находится ближе по вертикали к заданной окружности. После этого из соображений симметрии находятся координаты пикселей в остальных семи октантах.

Функция окружности

Чтобы воспользоваться методом средней точки, зададим функцию окружности как

F(X, Y) = X^2 + Y^2 - R^2

Любая точка (X, Y), которая лежит на окружности радиуса R , удовлетворяет уравнению F(X, Y) = 0.
Если точка находится внутри круга, то функция окружности будет иметь отрицательное значение F(X, Y) < 0.
Если точка лежит за пределами круга, значение функции окружности будет положительным F(X, Y) > 0.

Проверка принадлежности точки выполняется на каждое этапе выборки для средних положений между пикселями вблизи заданной окружности. Таким образом, функция окружности – это параметр принятия решении в алгоритме средней точки, и для этой функции можно установить операции приращения, как это было сделано для алгоритма построения прямой линии.

Средняя точка между двумя возможными пикселями в точке выборки Xk + 1.

Предположим, что мы поставили точку в пикселе с координатами (Xk, Yk). Нужно определить, какой из двух пикселей ближе к заданной окружности – с координатами (Xk + 1, Yk) или (Xk + 1, Yk – 1).

Алгоритм метода средней точки для построения окружности

(Построение 1/8 в области положительных значений, Y + 1 или X - 1 и Y + 1)
1. Ввести радиус R и координаты центра окружности (Xc, Yc)
   затем задать координаты первой точки на окружности, 
   центр которой находится в начале координат:
   (X, Y) = (R, 0)
2. Найти исходное значение параметра принятия решения:
   P = 5/4 – R # P = 1 - R (целочисленный)
3. Высвечивание текущего пикселя (X + Xc, Y + Yc)
4. Проверка окончания работы: 
   если X >= Y, то переход к п.7
5. Для каждого значения X выполнить следующую проверку:
   - Если P < 0, то следующая точка на окружности будет (X + 1 , Y):
     Y = Y + 1
     P = P + 2*Y + 1
     Переход к п.3
   - Иначе следующей точкой на окружности будет (X + 1, Y – 1):
     Y = Y + 1
     X = X - 1
     P = P + 2*Y + 1 – 2*X
     Переход к п.3
6. Найти симметричные точки в остальных семи октантах
7. Конец

Алгоритм Брезенхема для построения окружности

Другим, более простым и эффективным, путем является использование алгоритма Брезенхема для генерации окружности.

Чтобы построить полную окружность, достаточно сгенерировать ее одну восьмую часть. Остальные части получаются затем путем симметричного отражения относительно определенной прямой. Так, отражая одну восьмую часть, построенную в первом октанте для углов в диапазоне 0-45 , относительно прямой с уравнением Y = X, получим одну четвертую часть, лежащую в первом квадранте. Отразив эту четверть относительно прямой X = 0, получим одну вторую часть, лежащую выше оси абсцисс, наконец, отразив эту полуокружность относительно прямой Y = 0, получим полную окружность.

Рассмотрим построение части окружности, лежащей в первом квадранте. Предположим, что центр окружности лежит в начале координат, ее радиус равен R, ось абсцисс направлена вправо, ось ординат - вверх. Пусть алгоритм начинает работу в точке с координатами X = 0, Y = R, тогда он заканчивает работу в точке X = R, Y = 0. При таком направлении построения окружности Y как функция аргумента X будет являться монотонно убывающей (Y^2 = R^2 - X^2).

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

Горизонтальный пиксел вправо
Диагональный вниз и вправо
Bертикальный вниз

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

mh = |(X_i + 1)^2 + (Y_i)^2 - R^2|
md = |(X_i + 1)^2 + (Y_i - 1)^2 - R^2|
mv = |(X_i)^2 + (Y_i - 1)^2 - R^2|

Где:

mh, md, mv - искомые величины расстояний для горизонтального, диагонального и вертикального направлений соответственно,
X_i, Y_i - координаты текущего пикселя.

Разность между квадратами расстояний от центра окружности до диагонального пикселя (X_i + 1, Y_i - 1) и от центра до точки на окружности R^2 равна (Критерий)

delta_i = (X_i + 1)^2 + (Y_i - 1)^2  - R^2
(местный аналог ошибки)

Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего пиксела желательно использовать только знак ошибки, а не ее величину.

Случае выбора пикселя

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

между горизонтальным (X_i + 1, Y_i) и диагональным (X_i + 1, Y_i - 1) пикселями;
между горизонтальным (X_i + 1, Y_i) и вторым диагональным (X_i + 1, Y_i + 1) пикселями;
между вертикальным (X_i, Y_i - 1) и диагональным (X_i + 1, Y_i - 1);
между вертикальным (X_i, Y_i - 1) и третьим диагональным (X_i - 1, Y_i - 1) пикселями;
прохождение точно через диагональный (X_i + 1, Y_i - 1) пиксель.

Отрицательное значение delta_i может быть только в том случае, когда диагональный пиксел (X_i + 1, Y_i - 1) лежит внутри окружности, то есть это случаи 1 и 2 и следует выбирать горизонтальный (X_i + 1, Y_i) или диагональный (X_i + 1, Y_i - 1) пиксель.

Случай 1

Рассмотрим СЛУЧАЙ 1 и вычислим разность расстояний, то есть

d1 = mh - md =|(X_i + 1)^2 + Y_i^2 - R^2| - |(X_i + 1)^2 + (Y_i - 1)^2 - R^2|

При mh < md, d1 < 0 и в этом случае расстояние до горизонтального пикселя меньше, чем до диагонального, поэтому выбирается горизонтальный пиксель (X_i + 1, Y_i).
При mh > md, d1 > 0 и в этом случае расстояние до диагонального пикселя меньше, чем до горизонтального, поэтому выбирается диагональный пиксель (X_i + 1, Y_i - 1).
При mh = md, d1 = 0 и можно выбирать либо горизонтальный, либо диагональный пиксель. Для определенности выберем горизонтальный пиксель (X_i + 1, Y_i).

Для сокращения вычислений упростим выражение (d1). При этом следует учесть, что для случая 1 mh > 0, а md < 0, так как горизонтальный пиксель лежит вне окружности, а диагональный внутри окружности. Таким образом, можно записать:

d1 = (X_i + 1)^2 + (Y_i)^2 - R^2 + (X_i + 1)^2 + (Y_i - 1)^2 - R^2

Дополнение до полного квадрата члена Y_i^2 с помощью добавления и вычисления -2*Y_i + 1 дает:

d1 = 2 * [(X_i + 1)^2 + (Y_i - 1)^2 - R^2] + 2 * Y_i - 1

В квадратных скобках стоит по определению delta_i и его подстановка существенно упрощает выражение:

d1 = 2 * (delta_i + Y_i) - 1

Случай 2

В СЛУЧАЕ 2 выбирается горизонтальный пиксель, второй диагональный пиксель (X_i + 1, Y_i + 1) выбран быть не может в силу монотонного убывания функции. Для этого случая mh < 0 и md < 0, поэтому

d1 = R^2 - (X_i + 1)^2 - (Y_i)^2 + (X_i + 1)^2 + (Y_i - 1)^2 - R^2 = 1 - 2 * Y_i

Для первого квадранта 1 < Y_i < R, поэтому d1 = 1 - 2 * Y_i < 0. Таким образом, и в СЛУЧАЕ 2, если `d1 < 0, то выбирается горизонтальный пиксель.

Случай 3

Рассмотрим случай delta_i > 0. Это будет справедливо только в том случае, если диагональный пиксель лежит вне окружности, то есть это случаи 3 и 4 и надо выбирать либо диагональный (X_i + 1, Y_i - 1), либо вертикальный (X_i, Y_i - 1) пиксель.

Рассмотрим СЛУЧАЙ 3 и вычислим разность расстояний:

d2 = md - mv =|(X_i + 1)^2 + (Y_i - 1)^2 - R^2| - |(X_i)^2 + (Y_i - 1)^2 - R^2|

При md < mv, d2 < 0 - расстояние до диагонального пикселя меньше, чем до вертикального, поэтому выбирается диагональный пиксель (X_i + 1, Y_i - 1).
При md > mv, d2 > 0 - расстояние до вертикального пикселя меньше, чем до диагонального, поэтому выбирается вертикальный пиксель (X_i, Y_i - 1).
При md = mv, d2 = 0 и можно выбирать либо диагональный, либо вертикальный пиксель. Для определенности выберем диагональный пиксель (X_i + 1, Y_i - 1).

Для упрощения вычисления выражения (d2) учтем, что для СЛУЧАЯ 3 md > 0, а mv < 0, так как диагональный пиксель лежит вне окружности, а вертикальный внутри окружности.

d2 = (X_i + 1)^2 + (Y_i - 1)^2 - R^2 + (X_i)^2 + (Y_i - 1)^2 - R^2=
   = 2 * [(X_i + 1)^2 + (Y_i - 1)^2 - R^2] - 2 * X_i - 1 
   = 2 * (delta_i - X_i) - 1

Случай 4

В СЛУЧАЕ 4 выбирается вертикальный пиксель, третий диагональный пиксель (X_i - 1, Y_i - 1) выбран быть не может в силу монотонного убывания функции. Для этого случая md > 0 и mv > 0:

d2 = (X_i + 1)^2 + (Y_i - 1)^2 - R^2 - (X_i)^2 - (Y_i - 1)^2 + R^2 
   = 2 * X_i + 1

Для первого квадранта 0 < X_i < R, поэтому d2 = 2 * X_i + 1 > 0. Таким образом, и в СЛУЧАЕ 4 если d2 > 0, то выбирается вертикальный пиксель.

Случай 5

Остается проверить СЛУЧАЙ 5, для которого delta_i = 0, то есть диагональный пиксель лежит точно на окружности.

Вычислим значение d1 = mh - md, учитывая, что mh > 0, а md = 0:

d1 = (X_i + 1)^2 + (Y_i)^2 - R^2 > 0

следовательно, выбирается диагональный пиксель.

Вычислим значение d2 = md - mv, учитывая, что md = 0, mv < 0:

d2 = (X_i)^2 - (Y_i - 1)^2 - R^2 < 0

таким образом, выполняется условие выбора правильного диагонального шага к (X_i + 1, Y_i - 1).

Таким образом, при `delta_i = 0 выполняются те же условия для d1 и d2, как и в ранее рассмотренных случаях.

Подведем итог полученных результатов случаев:

delta_i < 0
   d1 <= 0 выбираем пиксель (X_i + 1, Y_i) -> mh
   d1 > 0 выбираем пиксель (X_i + 1, Y_i - 1) -> md
delta_i>0
   d2 <= 0 выбираем пиксель (X_i + 1, Y_i - 1) -> md
   d2 > 0 выбираем пиксель (X_i, y_i - 1) -> mv
delta_i = 0 выбираем пиксель (X_i + 1, Y_i - 1) -> md

Конечные формулы для расчетов

Теперь остается записать формулы для вычисления координат очередного пиксела и критерия для каждого из трех возможных направлений движения.

При переходе к горизонтальному пикселю:

X_i+1 = X_i + 1
Y_i+1 = Y_i
delta_i+1 = (X_i+1 + 1)^2 + (Y_i+1 - 1)^2 - R^2 =
          = (X_i+1)^2 + (Y_i - 1)^2 - R^2  + 2 * X_i+1 + 1  =
                                      (или + 2 * X_i + 3) 
          = delat_i + 2 * X_i+1 + 1

При переходе к диагональному пикселю:

X_i+1 = X_i + 1
Y_i+1 = Y_i - 1
delta_i+1 = (X_i + 2)^2 + (Yi - 2)^2 - R^2 
          = delta_i + 2 * X_i + 3 - 2 * Y i + 3=
          = delta_i + 2 * X_i+1 - 2 * Y_i+1 + 2

При переходе к вертикальному пикселю:

X_i+1 = X_i
Y_i+1 = Y_i - 1
delta_i+1 = (X_i + 1)^2 + (Yi - 2)^2 - R^2 
          = delta_i - 2 * Yi + 3
          = delta_i - 2 * Y_i+1 + 1

Начальное значение для X = 0, Y = R будет равно:

X_i = 0
Y_i = 1
delta = (X_i + 1)^2 + (Y_i - 1)^2 - R^2 
тогда:  
delta = 1 + (R - 1)^2 - R^2  = 2 * (1 - R)

Алгоритм Брезенхема для генерации окружности в первом квадранте может быть записан в следующем виде:

(1/4 часть круга)
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, то переход к п.7;
   если  D = 0, то переход к п.9. 
6. Вычисление параметра 
   d1 = 2 * D + 2 * Y - 1 
   и анализ полученного значения: 
   если d1 < 0, то переход к п.8;
   если d1 > 0, то переход к п.9.
7. Вычисление параметра 
   d2 = 2 * D - 2 * X - 1 
   и анализ полученного значения: 
   если d2 < 0, то переход к п.9;
   если d2 > 0, то переход к п.10.
8. Вычисление новых значений 
   X и D (горизонтальный шаг): 
   X = X + 1; 
   D = D + 2 * X + 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 - 2 * Y + 1. 
    Переход к п.3.
11. Конец.

Алгоритм Брезенхема для генерации окружности в первом полу-квадранте может быть записан в следующем виде:

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

Примечание

Учет ненулевых координат центра окружности означает фактически выполнение операции переноса, поэтому координаты точек окружности (X1,Y1) будут вычисляться по формулам:

X1 = Xc + X 
Y1 = Yc + Y

Неодинаковые разрешающие способности можно учесть, скорректировав ординату точки окружности путем умножения ее на величину xa/ya (xa, ya - два числа, выдаваемые процедурой GetAspectRatio модуля Graph, их отношение обратно пропорционально отношению разрешающих способностей экрана).

Provide feedback

Saved searches

Use saved searches to filter your results more quickly