2.9. NURBS кривые

В-сплайны используют для построения рациональных кривых линий в форме (2.7.5). Формула для вычисления радиус-вектора рациональной параметрической кривой на основе -сплайнов построенной по вершинам , обладающим весами имеет вид

(2.9.1)

Радиус-вектор кривой равен частному от деления некоторого вектора на вес кривой в данной точке. Каждый из -сплайнов -порядка построен на последовательности из узлов Значения узлов должны образовывать неубывающую последовательность, а в остальном на них не накладывается никаких ограничений. Кривые линии, построенные на множестве не равноотстоящих узлов, называются неоднородными. Параметрическое расстояние между соседними узлами у неоднородных кривых меняется при переходе от узла к узлу. Кривая (2.9.1) в общем случае является неоднородной и рациональной. Кривая (2.9.1) носит имя NURBS кривой, составленное из первых букв ее названия — Non-Uniform, Rational В-Spline (неоднородный рациональный фундаментальный сплайн).

Когда все вершины NURBS кривой имеют равные веса, то формула (2.9.1) для вычисления радиус-вектора кривой на основе -сплайнов примет вид

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

В формуле (2.9.1) для построения совокупности из -сплайнов порядка требуется узлов в случае незамкнутой кривой и узлов в случае замкнутой кривой. Число узлов всегда больше числа вершин, поэтому множество узлов называется расширенным. Воспользуемся той свободой, которую предоставляет нам выбор значений узлов при вычислении -сплайнов. Пусть вершины сплайна (2.9.1) пронумерованы от 1 до n. Пронумеруем узлы, на которых построены -сплайны, от 1 до т. Чтобы незамкнутая NURBS кривая проходила через первую и последнюю вершину, первый В-сплайн должен иметь кратными первые узлов (из узлов, на которых он строится), а последний В-сплайн должен иметь кратными последние узлов (из узлов, на которых он строится). Для построения незамкнутой -раз дифференцируемой NURBS кривой первые узлов должны иметь равные значения: следующие узлов должны образовывать возрастающую последовательность: оставшиеся m узлов должны принимать равные значения:

Для построения замкнутой -раз дифференцируемой NURBS кривой последовательность узлов должна отражать замкнутость: значения первых узлов должны образовывать возрастающую последовательность: следующие m узлов должны идти через интервалы, повторяющие первые интервалов между узлами: . В общем случае параметр NURBS кривой изменяется от значения узла до значения узла . Построенная на таких последовательностях узлов кривая будет иметь непрерывные производные до порядка включительно на всей области определения. Если среди узлов будут кратные, кроме вышеуказанных, то непрерывность соответствующих производных кривой будет нарушена.

Вычисление радиус-вектора кривой.

Для вычисления радиус-вектора NURBS кривой используется следующая схема. По значению параметра t из условия определяется номер отличного от нуля В-сплайна первого порядка и вычисляется его значение, исходя из определения:

Далее, используя рекуррентное соотношение Кокса-Де Бура

последовательно вычисляются все отличные от нуля при данном параметре t В-сплайны до m-го порядка Включительно:

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

и подставляются в формулу (2.9.1), которая примет вид

(2.9.4)

Одновременно с вычислением -сплайнов может проводиться вычисление их производных. Формулы (2.9.2) и (2.9.3) можно считать определением -сплайна. -сплайны являются локальными функциями (имеют малый носитель).

Свойства кривой.

Каждый В-сплайн отличен от нуля только на части области изменения параметра кривой, поэтому при изменении радиус-вектора одной из вершин подлежит пересчету не вся кривая, а только ее часть. -сплайны являются неотрицательными функциями. Сумма значений всех нормированных -сплайнов при любом параметре t NURBS кривой в соответствии со свойством (2.8.24) равна единице: а площадь под любым ненормированным -сплайном удовлетворяет равенству

(2.9.5)

Это равенство получим, переставив операции интегрирования и вычисления разделенной разности. Проинтегрируем усеченную степенную функцию (2.8.17) в указанных пределах

Вычислим разделенную разность полученной функции на последовательности узлов -сплайна. Второе слагаемое правой части на области равно нулю, а первое слагаемое равно полиному степени разделенная разность m-го порядка которого в соответствии со свойством (2.8.12) равна коэффициенту при , т. е. равна что доказывает равенство (2.9.5).

Из (2.9.5) следуют равенства:

NURBS кривая (2.9.1) обладает достаточной гибкостью. Ее можно легко редактировать путем изменения положения вершин. Например, легко можно модифицировать имеющуюся NURBS кривую так, чтобы она проходила через указанную точку или чтобы она касалась указанной кривой в заданной точке.

Производные радиус-вектора кривой.

Используя определение В-сплайна и тот факт, что первая производная усеченной степенной функции по параметру t равна

вычислим первую производную В-сплайна, переставляя дифференцирование и вычисление разделенных разностей

(2.9.6)

Продифференцируем числитель выражения (2.9.1) с учетом (2.9.6) и получим

где — индексы отличных от нуля В-сплайнов порядка при заданном параметре . В равенстве (2.9.7) использовались свойства Действительно, для заданной последовательности узлов и при любом параметре t, принадлежащем области определения кривой, среди В-сплайнов m-го порядка отличны от нуля только В-сплайнов (пусть их индексы равны ), а среди В-сплайнов порядка отличны от нуля В-сплайнов (их индексы, соответственно, равны . Мы видим, что первая производная сплайн-функции m-го порядка представляет собой аналогичную сплайн-функцию, порядок и число вершин которой на единицу меньше.

Вершины вычисляются по формуле

(2.9.8)

Продолжая дифференцирование, можно найти производную требуемого порядка для числителя выражения (2.9.1):

где

Для производных знаменателя (2.9.1) получим выражение, аналогичное

где

Радиус-вектор NURBS кривой (2.9.1) вычисляется как частное от деления двух функций параметра кривой f, поэтому при вычислении производной NURBS кривой правую часть (2.9.1) следует рассматривать как сложную функцию. Первая производная радиус-вектора NURBS кривой равна

где

Аналогично вычисляются производные NURBS кривой более высокого порядка

Производные второго и третьего порядка определены равенствами (2.7.10), (2.7.11). Можно заметить, что радиус-вектор точки и ее вес или в формулах NURBS кривой выступают как единое целое.

Алгоритм Де Бура.

Преобразуем числитель выражения (2.9.1), используя формулу (2.8.32.1), следующим образом:

(2.9.11)

где — индексы отличных от нуля В-сплайнов порядка при заданном параметре . В преобразовании (2.9.11), как и при выводе равенства (2.9.7), использовались свойства при заданном параметре t. Мы свели сумму m слагаемых к сумме слагаемых и понизили на единицу порядок В-сплайнов в этой сумме. Величины вычисляются по формуле

Продолжим упрощение числителя выражения (2.9.1) аналогичным образом и получим

(2.9.12)

Для знаменателя выражения (2.9.1) получим аналогичное выражение

(2.9.13)

Мы пришли к выводу, что положение точки NURBS кривой (2.9.1) для заданного параметра может быть определено по формуле

с помощью рекуррентных соотношений

(2.9.15)

которые начинаются со значений . Эти соотношения являются обобщением алгоритма Де Кастелье и называются алгоритмом Де Бура. Алгоритм вычисления радиус-вектора точки NURBS кривой для параметра иллюстрирует рис. 2.9.1:

Рис. 2.9.1. Алгоритм Де Бура

Вставка узлов. У заданной NURBS кривой порядка можно увеличить число характеристических точек, сохранив неизменной ее форму и параметрическую длину. Для этого применяется вставка дополнительных узлов. Вставим дополнительный узел t в последовательность узлов Пусть значение t расположено между значениями узлов и т.е. удовлетворяет неравенствам . Используя алгоритм Де Бура, можно показать, что кривая не изменится, если величины заменить на величины (см. рис. 2.9.1).

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

Узел t может быть вставлен многократно (максимальная кратность равна . Если узел t вставляется к раз, то величины нужно заменить на величины (см. рис. 2.9.1).

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

Примеры.

Для незамкнутой NURBS кривой мы будем использовать следующие значения узлов. Пусть первые m узлов имеют значения, равные нулю: следующие узлов принимают целочисленные

Рис. 2.9.2. Набор В-сплайнов порядка для незамкнутой NURBS кривой значения от 1 до оставшиеся узлов принимают значение Для замкнутой NURBS кривой мы будем использовать равноотстоящие значения

Рис. 2.9.3. Набор B-сплайнов 4-го порядка для замкнутой NURBS кривой узлов: Параметр NURBS кривой изменяется в пределах: что для незамкнутой кривой есть — а для замкнутой кривой есть . Параметризация с равноотстоящими

Сплайны с равномерной параметризацией Шёнберг назвал кардинальными.

На рис. 2.9.2 показан полный набор В-сплайнов 4-го порядка (кубических) для 9 вершин, построенных на расширенном множестве узлов

Рис. 2.9.4. NURBS кривые и их характеристические ломаные линии

Параметр t сплайна (2.9.1), построенного на данном множестве узлов, принимает значения на отрезке .

Рис. 2.9.5. Влияние порядка на форму NURBS кривой

Для замкнутой NURBS кривой используется последовательность равноотстоящих узлов:

Рис. 2.9.6. Влияние веса точки на форму NURBS кривой

На рис. 2.9.3 показан полный набор В-сплайнов 4-го порядка для 6 вершин, построенных на расширенном множестве узлов —3, —2, —1, О, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

Все В-сплайны для замкнутой кривой похожи друг на друга. Параметр t сплайна (2.9.1), построенного на данном множестве узлов, принимает значения на отрезке .

На рис. 2.9.4 показаны незамкнутый и замкнутый сплайны и их характеристические ломаные, построенные по описанным выше последовательностям узлов. У незамкнутой кривой крайние точки совпадают. Как и кривая Безье, NURBS кривая не проходит через свои вершины за исключением крайних точек для незамкнутой кривой.

На рис. 2.9.5 по одним и тем же восьми вершинам построены NURBS кривые 2-го, 4-го, 6-го и 8-го порядка. На рисунке мы наблюдаем, что чем выше порядок кривой, тем она более гладкая. NURBS кривая второго порядка совпадает со своей характеристической ломаной линией.

На рис. 2.9.6 показано влияние веса вершины на форму кривой 6-го порядка. Чем больше вес вершины, тем ближе к ней проходит NURBS кривая. В общем случае вес вершины может быть нулевым и даже отрицательным.

NURBS представление ломаной линии.

Если построить NURBS кривую (2.9.1) по вершинам на последовательности узлов на базе В-сплайнов второго порядка , то она совпадет с ломаной линией (2.4.1). Область изменения параметра NURBS кривой в этом случае равна В-сплайны второго порядка пропорциональны разделенным разностям второго порядка, вычисленным на последовательности узлов для функции . В-сплайны второго порядка определяются равенством

Мы видим, что представляют собой кусочно-линейные функции, принимающие значения В-сплайны (2.9.16) для шести вершин показаны на рис. 2.9.7.

Рис. 2.9.7. В-сплайны второго порядка

Замкнутую ломаную линию как частный случай NURBS кривой (2.9.1) можно построить на последовательности узлов Область изменения параметра NURBS кривой в этом случае равна

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

Отрезок прямой может быть представлен в виде NURBS кривой (2.9.1)

по двум вершинам на последовательности узлов и на базе В-сплайнов второго порядка

Кривая Безье как частный случай NURBS кривой.

Нормированные В-сплайны определения 4 (см. §2.8) в частном случае последовательности узлов совпадают с базисными функциями Бернштейна NURBS кривая (2.9.1), записанная в виде

(2.9.17)

совпадает с рациональной кривой Безье (2.7.2). Это происходит, когда число вершин на единицу больше порядка В-сплайна Область изменения параметра NURBS кривой в этом случае равна

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

Рис. 2.9.8. Функции Бернштейна — частный случай В-сплайнов

Вспомним, что коэффициенты Бернштейна связаны рекуррентным соотношением

Мы получим все коэффициенты Бернштейна, начав вычисления с В-сплайны связаны рекуррентным соотношением

(2.9.18)

где только а остальные В-сплайны нулевого порядка равны нулю.

Из приведенных формул видно, что коэффициенты Бернштейна и В-сплайны вычисляются совершенно одинаково, что доказывает их равенство. Из сказанного следует, что нормированные В-сплайны определения 1 в частном случае последовательности узлов совпадают с базисными функциями Бернштейна Этим доказывается, что кривые Безье являются частным случаем NURBS кривой. В-сплайны порядка на последовательности узлов показаны на рис. 2.9.8.

NURBS представление кривой второго порядка.

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

Рис. 2.9.9. Эллиптическая NURBS кривая

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

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

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

Рис. 2.9.10. NURBS кривая с кратными узлами

Веса характеристических точек равны: . Последовательность узлов имеет вид Если мы хотим, чтобы параметрическая длина кривой, показанной на рис. 2.9.9, была равна , то вместо указанной выше последовательности узлов можно использовать последовательность:

NURBS кривая может иметь изломы в точках с кратными узлами. Изломы возникают, когда соответствующие соседние вершины не расположены на одной прямой. На рис. 2.9.10 приведена та же эллиптическая NURBS кривая, но с измененными положениями точек .

NURBS кривая (2.9.1) обобщает все рассмотренные выше кривые — отрезок прямой, ломаная линия, кривая Безье, конические сечения могут быть описаны в виде NURBS кривой. По своей природе NURBS кривая представляет собой линейную комбинацию кусочно-полиномиальных функций заданной степени, она позволяет строить кривые заданного порядка гладкости.

NURBS представление кубического сплайна.

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

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

(2.9.19)

Используя формулы (2.9.2) и (2.9.3), определим, что для каждого значения параметра отличны от нуля только три В-сплайна четвертого порядка:

(2.9.20)

и два В-сплайна третьего порядка:

(2.9.21)

После подстановки (2.9.20) и (2.9.21) в (2.9.19) система уравнений для определения вершин примет вид

(2.9.22)

где

Матрица системы уравнений (2.9.22) является трехдиагональной.

Для замкнутого кубического сплайна система уравнений (2.9.19) упрощается, так как в ней исчезнут второе и предпоследнее уравнения, определяющие производные кривой на краях. Число вершин , NURBS кривой будет равно числу заданных точек . Последовательность узлов будет иметь вид (плюс циклическое расширение).

Интерполяция.

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

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

составленной из значений В-сплайнов, вычисленных в точках не равен нулю, если среди точек нет совпадающих. Ни одна из строк матрицы (2.9.24) не является нулевой, так как при любом значении параметра хотя бы один из В-сплайнов не равен нулю. Ни одна из строк матрицы (2.9.24) не является линейной комбинацией остальных строк матрицы. Совокупность В-сплайнов любого порядка представляет собой чебышевскую систему на их совокупной области определения.

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