B Spline curves and Beizer curves

Внимание! Этот документ ещё не опубликован.

В этой статье хотел написать всё, что мне известно о кривых и поверхностях типа B-Spline. Доказательства опущены.

В статье затрагиваются определение и свойства следующих вещей:

Полином Бернштейна
Кривая Безье
Б-сплайны
Виды б-сплайнов
Тензорные параметрические поверхности на примере поверхностей Б-сплайн и Безье

Полином Бернштейна

Полином Бернштейна определяется в виде:

. Если посмотреть внимательно на этот полином, то можно увидеть, что он является ничем иным как k-ым членом разложения полином Ньютона с коэффициентами a=t, b=1-t.
Из этого следует, что для всех чисел :

выполнено
Полином является положительно определённым. (Все параметры полинома больше нуля.)

Сплайны

Кривая Безье

Определение

Не рациональная кривая Безье задаётся как:

Здесь:

C(t) – получаемая вершина
t – параметрическое число от 0 до 1, задающее точку на кривой.
Pi – контрольная точка i
Bin – полином Бернштейна с коффициентами i, n

Рациональная кривая Безье задаётся видом:
Здесь фигурируют теже коэффициенты, что и для не рациональной кривой и добавляется один коэффициент:

Wi – вес

Свойтсва не рациональной кривой Безье:

Кривая всегда проходит через начальную и конечную точку
Кривая лежит внутри минимальной объемлющей выпуклой оболочки всех контрольных точек
Касательными к кривой в точках Po и Pn являются прямые, проходящие через точки (Po, P1) и (P(n-1), Pn) соответственно
Произвольная прямая имеет количество пересечений с кривой Безье не большее чем с поли линией, составленной по контрольным точкам.
Для выполнения аффинного преобразования над кривой достаточно выполнить аффинное преобразование над контрольными точками
Обобщением кривой Безье является B-Spline
Степень полинома описывающего кривую по N+1 точкам равна N
Кривая определена для значений u в отрезке [0,1].
При изменении положении одной контрольной точки происходит глобальное перестроение всей кривой. Любая контрольная точка оказывает влияние на форму всей кривой.
Легко получить, что при переносе контрольной точки k на вектор v новое значение кривой в точке t будет вычисляться как: где С(t) – старое значение
Значение производной в точке t вычисляется как: Данная кривая является кривой Безье определённая с помощью n-1 контрольной точки. Эту кривую часто называют годографом кривой C(t).
Для соединения двух кривых Безье, заданными набором контрольных точек:
и ,
при непрерывном соединении до первой производной требуется:
Последняя линия посчитанная в ходе работы алгоритма Де-Кастельи определяет касательную в точке C(u)
Пусть кривая задана через контрольные точки: . Для повышения порядка кривой на единицу без изменения последней можно воспользоваться следующим:
В соответствии с алгоритмом Де-Кастельи может быть легко посчитаны контрольные точки, необходимые для составления двух кривых, являющиеся результатом деления исходной кривой на две части какой-либо точкой, лежащей на кривой. Для этого требуется пройти все шаги алгоритма Де-Кастельи и специальным образом обойти полученные точки.

На интуитивном уровне понятно: что результатом деления исходной кривой, указанной на рисунке, точкой (60) будут две кривые заданные следующими контрольными точками:
- (00, 10, 20, 30, 40, 50, 60)
- (60, 51, 42, 33, 24, 15, 06)

Б-Сплайн (B-Spline, Basic Spline)

Определение

Формальное определение будет дано в конце параграфа. Сейчас будет вестись разговор откуда появилась необходимость появление такого типа кривых.
Данный вид сплайнов является обобщением Кривой Безье.
Область определения T=[0,1] разбивается узлами.
Определение кривой вводится так, что изменении кривой на области [ti, ti+1] никак не повлияет на изменение формы кривой на всей области определения.
Зададим вектор узлов T=

как неубывающую последовательность. Узлы в этой последовательности могут повторяться. Данный вектор разбивает исходную область определения на m узлов.
Зададим контрольные точки D = [

](по аналогии с кривой Безье).
Число p = m - n - 1 называют - степенью b-spline’a. Можно доказать, что это число как раз и равно степени кривой.
Узлы:

называют внутренними (действительными узлами).

Определение б-сплайна вводится так: .
Nip(t) - базисная функция (i, p)
Pi - контрольная точка i

Значение точки кривой в узловой точке C(ti) называют узловой точкой.

Базисная функция Nip рассчитывается по рекуррентным формулам Кокса-де-Бура:

Для понимания того как вводится определения b-spline’а помогут картинки ниже, уточняющие процесс генерации Nip(t)

Виды Б-сплайнов

Если вектор узлов не обладает никакой специфической структурой, то получаемая кривая не будет касаться первого и последнего отрезка полилинии, построенной по контрольным точкам. Такие кривые называют открытыми (open B-Spline).
Если первые p+1 узлов равны нулю и последние p+1 равны 1, то такой Б - сплайн называют периодическим (periodic B-Spline)
Если внутренние узлы равномерно стоят друг от друга с фиксированным шагом, то такой Б - сплайн называют равномерным(uniform B-Spline). Если данное условие не выполняется, то сплайн называют (non-uniform).
Если мы хотим получить кривую, для которой в начальной и конечной точке первый и последний отрезок полилинии, составленнной по контрольным точкам, являлся бы касательной в соответствующих точках первый и последний узел должны быть кратности p+1. Такая кривая будет называться отсечённой. (clamped B-Spline)
При повторении некоторых узлов и контрольных точек генерируемая кривая может стать закрытой. (closed B-spline)

Замечание: Нет устоявшейся терминологии и разные авторы обозначают введённые понятия по разному. А также придают кривым типа closed обязанность иметь равномерный узловой вектор.

В моём опыте встречалась следующая терминология, так что будьте внимательны:

Floating = open
Open = clamped
Periodic = closed

Некоторые операции по работе с Б-Сплайнами

Получение closed B-spline

Один из методов задания closed B-spline из open:
1) Задание вектора узлов как

2) Свернуть первые и последние p контрольных точек:

В свёрнутых точках кривая непрерывна до

Модификация контрольных точек

При передвижении контрольной точки

на вектор v происходит следующее:

Согласно в дальнейшем упомянутом свойству *5* в данном случае, при

поведение кривой не изменится.

Вычисление производной для Б - сплайна

Производная каждой базовой функции вычисляется как:

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

Где:

Таким образом мы получили новый Б - сплайн на один порядок меньше. С новым множеством контрольных точек, но с не изменившимся узловым вектором.

Свойства B-Spline - а

1) Степень полинома описывающего B - Spline равна p
2) Nip(u) является полиномом степени p от u.
3) Значение Nip(u) всегда неотрицательно.
4) для любого p и для любого t на интервале

5) Базовая функция

больше нуля только на отрезке

6) На любом интервале

p+1 базовых наборов функций степени p являются неотрицательными:

7) Clamped кривые всегда проходят через начальную и конечную контрольную точку.
8) Соотношение p = m - n – 1 должно быть выполнено всегда
9) Изменение положения контрольной точки Pi повлияет только на поведение кривой на интервале
10) С(t) непрерывна в узле кратности k до . Если t не определяет узел, то функция в данной точке бесконечно дифференцируема. Таким образом увеличивая кратность узла мы уменьшаем непрерывность.
11) Никакая прямая в пространстве не пересекает кривую больше раз чем пересекает поли линию, если кривая лежит в одной плоскости.
12) Для выполнения аффинного преобразования над кривой достаточно выполнить аффинное преобразование над контрольными точками
13) Если n=p или, что равносильно: если в узловом векторе 2n+2 узлов. А также первые n+1 которых равны 0, а оставшиеся n+1 равны 1.
То: , где правая часть равенства является базовой функцией кривой Безье.

Преимущества и недостатки использования Б - сплайна

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

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

Степень кривой задаётся отдельно
Мы можем изменять положение контрольной точки без глобального изменения кривой

Однако надо помнить о том, что б-сплайны являются полиномами от U, и поэтому не могут воспроизвести множество полезных простых кривых, например окружность. В данном случае требуется использовать NURBS кривые.

Тензорные параметрические поверхности

Поверхность Безье

Определение

(n+1)(m+1) контрольных точек. (Beizer Net, Control Net)
базовые функции степени m, n: Bim(U), Bjn(V). В этом случае говорят, что поверхность имеет порядок (m,n)

Свойства

p(u, v)

Рисование поверхности

Б – сплайн поверхность

Определение

(n+1)(m+1) контрольных точек.
Узловой вектор U, размерности h+1
Узловой вектор V, размерности k+1
Порядок кривой в направлении U: p
Порядок кривой в направлении V: q

Также должны быть выполнены два равенства: h = m+p+1 и k = n+q+1
Так как кривая может быть open, closed, clamped, в таком случае поверхность может обладать для каждого направления соответствующим свойством.

Свойства

p(u, v)

NURBS поверхность определяется как:

8 февраля 2011

Категории: графика, математика

Обновление: 23 марта 2011