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

Построение эллипса

Каноническое уравнение эллипса

(X - Xс)^2   (Y - Yс)^2
---------- + ----------  =  1
   a^2           b^2
или
 X^2    Y^2
 --- +  ---  =  1
 a^2    b^2

где Xс,Yс - координаты центра, `a и b' - полуоси эллипса

Параметрическое уравнение эллипса

X = Xc + a * cos(t)
Y = Yc + b * sin(t)

где Xс,Yс - координаты центра, a и b' - полуоси эллипса, t - параметр (0 < t < 2pi`).

Метод средней точки для построения эллипса

В этом случае подход аналогичен тону, который использовался при растровом изображении окружности. Если известны параметры a, b и (Xc, Yc), можно определить координаты точек (X, Y) эллипса в стандартном положении с центром в начале координат, после этого сместить все точки так, чтобы получился эллипс с центром в точке (Xc, Yc). Если потребуется изобразить эллипс в нестандартном положении, можно развернуть его вокруг центральной точки, чтобы переориентировать большую и малую оси в нужном направлении.

Рассмотрим изображения эллипсов в стандартном положении.

Метод средней точки для эллипса применяется в обеих частях первого квадранта. На рис. показано, как первый квадрант делится на части согласно тангенсу угла наклона эллипса для которого b < a.

Rx = a, Ry = b

• При обработке этого квадранта в той части, где тангенс угла наклона кривой меньше 1, выполняются единичные шаги в направлении X, то есть X + 1
• А затем в той части, где величина тангенса угла наклона больше 1, выполняются единичные шаги в направлении Y, то есть Y + 1

Области 1 и 2 (рис.) можно обрабатывать различными способами:

1. Можно начать с точки (0, b) и двигаться по часовой стрелке по эллиптической траектории в первом квадранте, а затем перейти от единичного шага по X к единичному шагу по Y, когда тангенс угла наклона станет меньше -1.
2. Можно начать с точки (a, 0) и выбирать точки в направлении против часовой стрелки, перейдя от единичного шага по Y к единичному шагу по X, когда танине угла наклона станет больше –1.

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

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

Функция эллипса

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

F(X, Y) = a^2 * X^2 + b^2 * Y^2 - a^2 * b^2

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

Таким образом, функция эллипса F(X, Y) является параметром принятия решения в алгоритме средней точки. В каждой точке выборки определяется следующий пиксель на эллиптической траектории в соответствии со знаком функции эллипса, которая вычисляется в средней точке между двумя возможными положениями пикселей.

Начиная с точки (0, b), выполняются единичные шаги по x до тех пор, пока не будет достигнута граница между областью 1 и 2 (рис.). Затем единичные шаги по Y на оставшейся части кривой в первом квадранте. На каждом шаге проверить значение тангенса угла наклона кривой

dy       2 * B^2 * X
-- =  -  -----------
dx       2 * A^2 * Y

Выход за пределы области 1, когда dx < dy

Область 1

Предположив, было выбрано положение (X, Y), найдем следующее положение на эллиптической траектории, вычислив параметр принятия решения в этой средней точке:

P1 = F(X + 1, Y - 1/2) = b^2 * (X + 1)^2 + a^2 * (Y - 1/2)^2 - a^2 * b^2 

• Если P1 < 0, средняя точка находится внутри эллипса, тогда пиксель в строке развертки Y будет ближе к границе эллипса.
• В противном случае средняя точка лежит за пределами эллипса или на его границе, и выбирается пиксель в строке развертки Y - 1.

Область 2

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

P2 = F(X + 1/2, Y - 1) = b^2 * (X + 1/2)^2 + a^2 * (Y - 1)^2 - a^2 * b^2

• Если P2 > 0, средняя точка находится за пределами эллипса, и выбирается пиксель с координатой X.
• Если P2 <= 0, средняя точка расположена либо внутри эллипса, либо на его границе, и выбирается пиксель с координатой X + 1.

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

1. Ввести A, B и координаты центра эллипса (Xс, Yс), 
   а затем найти первую точку эллипса с центром 
    в начале координат: (X, Y) = (0, B)
2. Вычислить начальное значение параметра
    принятия решения в области 1: 
    P1 = B^2 - A^2 * (B - 1/4)
3. Высвечивание текущего пикселя (X + Xc, Y + Yc).
4. Пока 2 * B^2 * X < 2 * A^2 * Y. (Область 1)
   Для каждого значения X в области 1 провести следующую проверку.
   Если P1 < 0 то следующая точка вдоль (X + 1 , Y):
      X = X + 1
      P1 = P1 + B^2 * 2 * X + B^2 
   Иначе (X + 1 , Y - 1):
      X = X + 1
      Y = Y - 1
      P1 = P1 + B^2 * 2*X - A^2 * 2 * Y + B^2     
   Переход к п.3
8. Найти начальное значение параметра принятия решения в области 2:
   P2 = A^2 - B^2 * (A - 1/4)
9. Высвечивание текущего пикселя (X + Xc, Y + Yc).
10. Пока Y >= 0 (Область 2)
   В каждой точке Y в области 2 выполнить следующую проверку. 
   Если P2 < 0, следующей точкой эллипса с центром в точке (0, 0) будет (X, Y + 1):
      Y = Y + 1 
      P2 = P2 + 2 * A^2 * Y + A^2 
   Иначе (X + 1, Y - 1):
      X = X - 1
      Y = Y + 1
      P2 = P2 +  2 * A^2 * Y – 2 * B^2 * X + A^2
   Переход к п.9
11. Для обеих областей найти симметричные точки в остальных трех квадрантах.
12. Конец

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

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

Рассмотрим непосредственно алгоритм :

Для построения растровой развертки эллипса с осями, параллельными осям координат, и радиусами a, b воспользуемся каноническим уравнением X^2 / a^2 + Y^2 / b^2 = 1, которое перепишем в виде f(x, y) ≡ b^2 * X^2 + a^2 * Y2^ – a^2 * b^2 = 0.

В отличие от окружности, для которой было достаточно построить одну восьмую ее часть, а затем воспользоваться свойствами симметрии, эллипс имеет только две оси симметрии, поэтому придется строить одну четверть всей фигуры. За основу возьмем дугу, лежащую между точками (0, b) и (a, 0) в первом квадранте координатной плоскости.

В каждой точке (X, Y) эллипса существует вектор нормали, задаваемый градиентом функции f. Дугу разобьём на две части: первая – с углом между нормалью и горизонтальной осью больше 45 (тангенс больше 1) и вторая – с углом, меньшим 45.

Движение вдоль дуги будем осуществлять по часовой стрелке, начиная с точки (0, b). Вдоль всей дуги координата является монотонно убывающей функцией от X, но в первой части она убывает медленнее, чем растет аргумент, а во второй - быстрее. Поэтому при построении растрового образа в первой части будем увеличивать X на единицу и искать соответствующее значение Y, а во второй - сначала уменьшать значение Y на единицу и определять соответствующее значение X.

Направление нормали соответствует вектору

              / delta_F   delta_F \
grad(X, Y) = (  ------- , -------  ) = (2 * b^2 * X, 2 * a^2 * Y)
              \ delta_X   delta_Y /

Отсюда находим тангенс угла наклона вектора нормали:

    a^2 * Y
t = ------- = 1
    b^2 * X

Приравнивая его единице, получаем, что координаты точки деления дуги на вышеуказанные части удовлетворяют равенству b^2 * X = a^2 * Y. Поэтому критерием того, что мы переходим ко второй области в целочисленных координатах, будет соотношение

a^2 * (2 * Y - 1/2) <= 2 * b^2 * (X + 1),

или, переходя к целочисленным операциям,

a^2 * (2 * Y - 1) <= 2 * b^2 * (X + 1).

Случай А

При перемещении вдоль первого участка дуги мы из каждой точки переходим либо по горизонтали, либо по диагонали, и критерий такого перехода напоминает тот, который использовался при построении растрового образа окружности. Находясь в точке (X, Y), мы будем вычислять значение delta = f(X + 1, Y - 1/2). Если это значение меньше нуля, то дополнительная точка (X + 1, Y - 1/2) лежит внутри эллипса, следовательно, ближайшая точка растра есть (X + 1, Y), в противном случае это точка (X + 1, Y - 1)

Случай B

На втором участке дуги возможен переход либо по диагонали, либо по вертикали, поэтому здесь сначала значение координаты y уменьшается на единицу, затем вычисляется delta = f(X + 1/2, Y - 1) и направление перехода выбирается аналогично предыдущему случаю.

Итог

Остается оптимизировать вычисление параметра delta, умножив его на 4 и представив в виде функции координат точки.

Тогда для первой половины дуги имеем

delta(X, Y) = b^2 * (2X + 1)^2 +  4*a^2 * (Y + 1) - 4 * a^2 * b^2
delta(X + 1, Y) = delta(X, Y) + 4 * b^2 * (2X + 3)
delta(X + 1, Y + 1) = delta(X, Y) + 4 * b^2 * (2X + 3) - 8 * a^2 * (Y - 1) 

Для второй половины дуги получим:

delta(X, Y) = b^2 * (2X + 1)^2 + 4 * a^2 * (Y + 1) - 4 * a^2 * b^2
delta(X, Y - 1) = delta(X, Y) + 4 * a^2 * (2Y + 3)
delta(X + 1, Y - 1) = delta(X, Y) + 4 * a^2 * (2Y + 3) - 8 * b^2 * (X + 1)

Все оставшиеся дуги эллипса строятся параллельно: после получения очередной точки (X, Y), можно инициализировать ещё три точки с координатами (-X, Y), (X, -Y), (-X, -Y).

То есть:

1. X1 = Xc + X; Y1 = Yc + Y
2. X2 = Xc - X; Y2 = Yc + Y
3. X3 = Xc - X; Y3 = Yc - Y
4. X4 = Xc + X; Y4 = Yc - Y

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

(алгоритм переписывал сам, возможно есть недочеты, не уверен на счет диагонального шага - Ссылка)

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

Достоинства алгоритма

• высокая скорость работы
• минимальное потребление памяти
• значительная схожесть построенного эллипса с эллипс, нарисованным на непрерывной поверхности
• использование исключительно целочисленной арифметики

Недостатки

• необходима достаточная разрядность переменных при достаточно больших значениях a и b.