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

З апишем уравнение окружности в неявном виде f(x, y) = x² + y² – R². Эта кривая разбивает плоскость на 3 части (см. рис.):

f(x, y) < 0 – внутренняя -

f(x, y) = 0 – граничная область

f (x, y) > 0 – внешняя +

Окружность выпукла во всех своих точках и имеет центральную симметрию. Что это означает? Можно выполнить растеризацию только части окружности и результат распространить отражением на остальные части.

Поместим центр окружности в начало координат. А величину радиуса R считаем целым числом.

Функцию f(x, y) можно рассматривать как целевую функцию процедуры поиска пикселей, отвечающих линии окружности.

Сумма значений целевой функции в двух проверяемых точках (назовём их узловыми) есть критерий близости узловых точек к линии окружности. Точки S и T лежат по разные стороны линии f(x, y) = 0 и значения функции f(x, y) в точках S и T будут иметь разные знаки (противоположные).

Сумма f(S)+f(T) в этом алгоритме играет ту же роль, что и разность расстояний s – t до прямой в алгоритме Брезенхема её растеризации.

Найдём значения f(x, y) в узлах S и T

f_sⁱ⁺¹ = (x_i + 1)² + (y_i - 1)² – R²

f_Tⁱ⁺¹ = (x_i + 1)² + y_i ² – R²

и найдём значения целевой функции

f_STⁱ⁺¹ = |f_Sⁱ⁺¹| - |f_Tⁱ⁺¹| = f_Sⁱ⁺¹ + f_Tⁱ⁺¹ = 2x_i² + 2y_i² + 4x_i – 2y_i – 2R² +3.

Для начальной точки x₀ = 0, y₀ = R целевая функция имеет значение f_STⁱ⁼¹ = 3 – 2R.

Направление перемещения в алгоритме должно выбираться так, что бы на каждом шаге уменьшалось абсолютное значение целевой функции. В данном случае целевая функция имеет квадратичную форму и для неё можно предложить пошаговый инкрементный алгоритм вычисления. Пока целевая функция f_ST отрицательна надо продвигаться по оси X и выбирать узел T, а если f_ST положительна надо выбрать узел S.

Алгоритмическая форма записи:

T: if (f_STⁱ ≤ 0), then (x = x+1, y) =>

S: if (f_STⁱ > 0), then (x = x+1, y = y - 1).

В алгебраической форме алгоритм записывают так:

если f_STⁱ ≤ 0, то f_i+1 = f_i + 4x_i + 6

если f_STⁱ > 0, то f_i+1 = f_i + 4(x_i – y_i) + 10

Структурная схема алгоритма показана на следующем рисунке.

4. Типы пространств и системы координат их.

При создании и последующем преобразовании (редактировании) изображений в зависимости от задачи (от того, что нам надо сделать) или от этапа работы выбирают различные типы пространств. Каждое пространство при этом определяют своей системой координат.

Дадим короткое определение наиболее часто используемым пространствам в компьютерной графике.

1 Пространство объекта . В этом пространстве выполняют моделирование и описание объекта, его формы и его размеров. Этот процесс производят в локальной собственной системе координат – ЛСК. Моделирование выполняется безотносительно того, где будет размещён объект на сцене, как его будут ориентировать или масштабировать. Можно провести здесь аналогию с 3-D моделью или рабочим чертежом детали, которые позже будут перенесены в другое пространство и объеденены с другими объектами.

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

3 Видовое пространство, это пространство ассоциируют с виртуальным наблюдателем (иначе с камерой, например, с видоискателем в камере фотоаппарата при его наведении на фотографируемый объект). Видовое пространство можно представить и как определённую проекцию сцены, или ее часть на экран, например, фронтальную или аксонометрическую. Посредством видового пространства описывают ту часть сцены, которая доступна для просмотра и работы в видовом окне. Здесь также присутствует своя система координат – система координат камеры СКК или СК_К.

4 Ещё одно пространство – собственно плоскость – экранное пространство. В нём отражают аксонометрические или перспективные проекции объектов на плоскость поверхности монитора или другой носитель изображения. Здесь своя система координат: СКЭ или СК_э – экранная.

5 Отметим дополнительно UVW параметрическое пространство. Оно применяется при математическом моделировании сложных кривых и поверхностей, например, NURBS – объектов, или для задания UVW – координат текстурирования поверхностей.