Растровая развёртка окружности

Существует несколько очень простых, но не эффективных способов преобразования окружностей в растровую форму. Например, рассмотрим для простоты окружность с центром в начале координат. Ее уравнение записывается как x² + y² = R². Решая это уравнение относительно y, получим

y = ± .

Чтобы изобразить четвертую часть окружности, будем изменять x с единичным шагом от 0 до R и на каждом шаге вычислять y. Вторым простым методом растровой развертки окружности является использование вычислений x и y по формулам x = R cos α, y = R sin α при пошаговом изменении угла α от 0° до 90°.

Для упрощения алгоритма растровой развёртки стандартной окружности можно воспользоваться её симметрией относительно координатных осей и прямых y = ± x; в случае, когда центр окружности не совпадает с началом координат, эти прямые необходимо сдвинуть параллельно так, чтобы они прошли через центр окружности. Тем самым достаточно построить растровое представление для 1/8 части окружности, а все оставшиеся точки получить симметрией (см. рис. 4.5).

Рис. 4.5. Восьмисторонняя симметрия

Рассмотрим участок окружности из второго октанта x Є [0, R/ ]. Далее опишем алгоритм Брезенхейма для этого участка окружности.

На каждом шаге алгоритм выбирает точку P_i (x_i, y_i), которая является ближайшей к истинной окружности. Идея алгоритма заключается в выборе ближайшей точки при помощи управляющих переменных, значения которых можно вычислить в пошаговом режиме с использованием небольшого числа сложений, вычитаний и сдвигов.

Рассмотрим небольшой участок сетки пикселей, а также возможные способы (от A до E) прохождения истинной окружности через сетку (рис. 4.6).

Предположим, что точка P_i-1была выбрана как ближайшая к окружности при x = x_i-1. Теперь найдем, какая из точек (S_i или T_i) расположена ближе к окружности при x = x_i-1 + 1.

Рис. 4.6. Варианты прохождения окружности через растровую сетку

Заметим, что ошибка при выборе точки P_i (x_i, y_i) была равна

D(P_i) = (x_i²+ y_i²) – R².

Запишем выражение для ошибок, получаемых при выборе точки S_i или T_i:

D(S_i) = [(x_i-1+ 1)² + (y_i-1)²] – R²;

D(T_i) = [(x_i-1+ 1)² + (y_i-1 – 1)²] – R².

Если | D(S_i) | ≥ | D(T_i) |, то T_i ближе к реальной окружности, иначе выбирается S_i.

Введем d_i = | D(S_i) | – | D(T_i) |.

T_i будет выбираться при d_i ≥ 0, в противном случае будет устанавливаться S_i.

Опуская алгебраические преобразования, запишем d_i и d_i+1 для разных вариантов выбора точки S_i или T_i.

D₁ = 3 – 2 R.

Если выбирается S_i (когда d_i < 0), то d_i+1 = d_i + 4 x_i-1 + 6.

Если выбирается T_i (когда d_i ≥ 0), то d_i+1 = d_i + 4 (x_i-1 – y_i-1) + 10.

Существует модификация алгоритма Брезенхейма для эллипса.

Кривые Безье

Кривые Безье были разработаны в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании «Рено» и Полем де Касталье (Кастельжо) из компании «Ситроен», где применялись для проектирования кузовов автомобилей. Благодаря простоте задания и манипуляции, кривые Безье нашли широкое применение в компьютерной графике для представления гладких линий.

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

Кривая Безье это параметрическая кривая, задаваемая выражением:

где P_i – функция компонент векторов опорных вершин, а b_i,n(t) – базисные функции кривой Безье, называемые также полиномами Бернштейна.

где n – степень полинома, i – порядковый номер опорной вершины.

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

Нижний индекс – номер опорной точки, верхний индекс – уровень разбиения. Уравнение n-ого порядка задается

Вид кривой зависит от количества опорных точек. Наиболее часто используются линейные, квадратные, кубические и кривые четвертого порядка.

Линейные кривые

При n = 1 кривая представляет собой отрезок прямой линии, опорные точки P₀ и P₁ определяют его начало и конец. Кривая задаётся уравнением:

B(t) = (1–t) P₀ + t P₁ t Є [0, 1].

Квадратные кривые

Квадратная кривая Безье (n = 2) задаётся 3-я опорными точками: P₀, P₁ и P₂. Кривая задаётся уравнением:

B(t) = (1–t)² P₀ +2t(1-t) P₁ + t²P₂ t Є [0, 1].

Данное уравнение можно получить с помощью метода де Касталье следующим образом. Обозначим опорные точки, как , начало кривой положим в точке P₀ (t = 0) , а конец - в точке P₂ (t = 1); для каждого t Є [0, 1] найдем точку :

,

,

,

таким образом, получим кривую второго порядка.

Точки и лежат на кривых первого порядка (отрезках) соединяющие опорные точки P₀ с P₁ и P₁ c P₂ соответственно. Точки, образующие кривую Безье, лежат на отрезке, соединяющем с пропорционально изменению параметра t (рис. 4.7).

Рис. 4.7. Кривая Безье с тремя опорными точками

Кубические кривые

В параметрической форме кубическая кривая Безье (n = 3) описывается следующим уравнением:

B(t) = (1–t)³ P₀ + 3t(1-t)² P₁ + 3t²(1-t) P₂ + t³ P₃ t Є [0, 1].

Для получения этой формулы используем аналогичным способом метод де Касталье.

Обозначим опорные точки, как , начало кривой положим в точке P₀ (t = 0) , а конец - в точке P₃ (t = 1); для каждого t Є [0, 1] найдем точку :

,

,

,

,

,

,

таким образом, получим кривую третьего порядка (рис. 4.8).

Рис. 4.8. Кривая Безье с четырьмя опорными точками

Четыре опорные точки P₀, P₁, P₂ и P₃, заданные в двух или трехмерном пространстве определяют форму кривой.

Линия берёт начало из точки P₀ направляясь к P₁ и заканчивается в точке P₃ подходя к ней со стороны P₂. То есть кривая не проходит через точки P₁ и P₂, они используются для указания её направления. Длина отрезка между P₀ и P₁ определяет, как скоро кривая повернёт к P₃.

В матричной форме кубическая кривая Безье записывается следующим образом:

где M_B называется базисной матрицей Безье:

Сплайн Безье

Кривые Безье обладают рядом свойств:

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

2. инвариантность относительно аффинных преобразований. Как следствие поворот вокруг точки, масштабирование и изменение пропорций кривой Безье не нарушает ее стабильности;

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

4. если все опорные точки лежат на одной прямой, то кривая Безье вырождается в отрезок, соединяющий эти точки;

5. кривая Безье симметрична, то есть обмен местами между начальной и конечной точками (изменение направления траектории) не влияет на форму кривой;

6. степень многочлена, представляющего кривую в аналитическом виде, на единицу меньше числа опорных точек.

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

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

В математике под сплайном обычно понимают кусочно-заданную функцию, совпадающую с функциями более простой природы на каждом элементе разбиения своей области определения.

В случае с кривыми Безье сплайн обычно составляется из нескольких кубических кривых. Если точка P_n является стыковочной точкой, для соблюдения условия гладкости кривой в ней, необходимо, что бы выполнялось условие коллинеарности с соседними узловыми точками (рис. 4.9).

Рис. 4.9. Соблюдение условия гладкости на стыке кривых Безье

Однако даже такие достаточно развитые средства аппроксимации кривыми Безье не позволяют построить окружность, описываемую параметрически как:

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: