B-сплайны

B-сплайны (от англ. basis spline — базисный сплайн) — это параметрические кривые, представляющие собой кусочно-полиномиальные функции, построенные на основе набора контрольных точек и узлового вектора. B-сплайны являются обобщением кривых Безье, позволяя создавать гладкие кривые произвольной степени с локальным управлением формой, что делает их фундаментальным инструментом в компьютерной графике, системах автоматизированного проектирования (САПР) и численном анализе.

История

Первые работы по теории сплайнов относятся к середине XX века. В 1946 году Исаак Шёнберг ввёл понятие сплайна как математического инструмента для интерполяции данных. Однако современная форма B-сплайнов была разработана в 1970-х годах. В 1972 году Карл де Бур и независимо от него Морис Кокс предложили рекурсивный алгоритм вычисления B-сплайнов, известный как алгоритм де Бора — Кокса. В 1974 году Ричард Ризенфельд и Уильям Гордон применили B-сплайны в системах автоматизированного проектирования, что привело к их широкому распространению в инженерной практике. В 1980-х годах B-сплайны стали основой для разработки NURBS (неоднородных рациональных B-сплайнов), которые используются в современных САПР-системах.

Определение и математическая основа

B-сплайн степени \( p \) определяется как параметрическая кривая \( C(t) \), заданная формулой:

\[ C(t) = \sum_{i=0}^{n} N_{i,p}(t) \cdot P_i \]

где:

• \( P_i \) — контрольные точки (векторы в пространстве \( \mathbb{R}^2 \) или \( \mathbb{R}^3 \));
• \( N_{i,p}(t) \) — базисные функции B-сплайна степени \( p \);
• \( t \) — параметр, изменяющийся в диапазоне, заданном узловым вектором.

Узловой вектор

Узловой вектор \( \mathbf{U} = \{ u_0, u_1, \dots, u_m \} \) — это неубывающая последовательность вещественных чисел, где \( m = n + p + 1 \). Узлы делятся на:

• Равномерные — узлы расположены на одинаковом расстоянии друг от друга.
• Неравномерные — узлы могут иметь произвольные расстояния, что позволяет создавать нерегулярные кривые.
• Открытые — первый и последний узлы повторяются \( p+1 \) раз, что гарантирует, что кривая проходит через первую и последнюю контрольные точки.
• Замкнутые — узлы образуют циклическую последовательность для создания замкнутых кривых.

Базисные функции

Базисные функции \( N_{i,p}(t) \) определяются рекурсивно по алгоритму де Бора — Кокса:

1. Для степени \( p = 0 \):

\[ N_{i,0}(t) = \begin{cases} 1, & \text{если } u_i \leq t < u_{i+1}, \\ 0, & \text{иначе} \end{cases} \]

1. Для степени \( p > 0 \):

\[ N_{i,p}(t) = \frac{t - u_i}{u_{i+p} - u_i} N_{i,p-1}(t) + \frac{u_{i+p+1} - t}{u_{i+p+1} - u_{i+1}} N_{i+1,p-1}(t) \]

Эти функции обладают следующими свойствами:

• Неотрицательность: \( N_{i,p}(t) \geq 0 \) для всех \( t \).
• Разбиение единицы: \( \sum_{i=0}^{n} N_{i,p}(t) = 1 \) для \( t \in [u_p, u_{n+1}] \).
• Локальная поддержка: \( N_{i,p}(t) \neq 0 \) только на интервале \( [u_i, u_{i+p+1}] \), что обеспечивает локальное управление формой кривой.

Классификация B-сплайнов

По типу узлового вектора

• Равномерные B-сплайны — узлы расположены с постоянным шагом. Кривая не проходит через первую и последнюю контрольные точки, если не используется открытый узловой вектор.
• Неравномерные B-сплайны — узлы имеют произвольные расстояния, что позволяет контролировать плотность кривой в разных участках.
• Открытые B-сплайны — используются открытые узловые векторы, кривая проходит через первую и последнюю контрольные точки.
• Замкнутые B-сплайны — узлы и контрольные точки образуют цикл, кривая является замкнутой и гладкой.

По степени

• Линейные B-сплайны (степень 1) — кусочно-линейные кривые, состоящие из отрезков прямых.
• Квадратичные B-сплайны (степень 2) — обеспечивают непрерывность первой производной (\( C^1 \)).
• Кубические B-сплайны (степень 3) — наиболее распространённые, обеспечивают непрерывность второй производной (\( C^2 \)), что даёт высокую гладкость.
• B-сплайны высших степеней — используются редко из-за вычислительной сложности и склонности к осцилляциям.

По рациональности

• Обычные B-сплайны — нерациональные, основаны на полиномиальных функциях.
• NURBS (неоднородные рациональные B-сплайны) — обобщение, где каждая контрольная точка имеет вес, что позволяет точно представлять конические сечения (окружности, эллипсы, параболы).

Свойства B-сплайнов

1. Локальное управление: изменение положения одной контрольной точки влияет только на часть кривой, ограниченную областью поддержки соответствующей базисной функции.
2. Гладкость: степень непрерывности кривой в узлах равна \( C^{p-k} \), где \( k \) — кратность узла. При отсутствии повторяющихся узлов кривая имеет непрерывность \( C^{p-1} \).
3. Выпуклая оболочка: кривая лежит внутри выпуклой оболочки своих контрольных точек.
4. Инвариантность к аффинным преобразованиям: преобразования (поворот, масштабирование, сдвиг) применяются к контрольным точкам, а не к кривой.
5. Вариация уменьшения: кривая не может пересекать прямую линию чаще, чем её контрольная ломаная.

Применение

Компьютерная графика и анимация

B-сплайны используются для создания гладких траекторий движения объектов, анимации персонажей и моделирования поверхностей. В игровых движках (например, Unity, Unreal Engine) применяются для интерполяции ключевых кадров.

Системы автоматизированного проектирования (САПР)

В САПР (например, AutoCAD, SolidWorks, CATIA) B-сплайны и NURBS являются стандартом для моделирования кривых и поверхностей. Они позволяют инженерам создавать сложные формы автомобилей, самолётов, кораблей и промышленных изделий.

Численный анализ и аппроксимация данных

B-сплайны применяются для интерполяции и сглаживания экспериментальных данных, решения дифференциальных уравнений методом конечных элементов (МКЭ) и в задачах регрессии.

Обработка изображений и сигналов

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

Примеры

Пример 1: Кубический B-сплайн с четырьмя контрольными точками

Пусть заданы четыре контрольные точки \( P_0, P_1, P_2, P_3 \) и открытый равномерный узловой вектор \( \mathbf{U} = \{0, 0, 0, 0, 1, 2, 3, 3, 3, 3\} \). Кривая будет проходить через \( P_0 \) и \( P_3 \), а её форма определяется положением \( P_1 \) и \( P_2 \). Изменение \( P_1 \) влияет только на участок кривой между \( t = 0 \) и \( t = 2 \).

Пример 2: Замкнутый B-сплайн

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

Критика и ограничения

Несмотря на широкое применение, B-сплайны имеют некоторые недостатки:

• Вычислительная сложность: рекурсивный алгоритм де Бора — Кокса требует \( O(p^2) \) операций на точку, что может быть затратно для кривых высокой степени.
• Сложность управления: для точного контроля формы требуется понимание влияния узлового вектора и кратности узлов.
• Отсутствие точности для конических сечений: обычные B-сплайны не могут точно представить окружность или эллипс, что решается использованием NURBS.
• Чувствительность к шуму: при аппроксимации зашумлённых данных B-сплайны могут давать нежелательные осцилляции.

Интересные факты

• B-сплайны являются частным случаем NURBS, которые были стандартизированы в ISO 10303 (STEP) для обмена данными между САПР-системами.
• Алгоритм де Бора — Кокса был независимо открыт двумя математиками в 1972 году, что привело к долгой дискуссии о приоритете.
• В 1989 году компания Silicon Graphics использовала B-сплайны для создания анимации в фильме «Бездна» (режиссёр Джеймс Кэмерон), что стало одним из первых применений сплайнов в киноиндустрии.
• В России B-сплайны активно применяются в системах автоматизированного проектирования судов и самолётов, разработанных в ЦНИИ «Гидроприбор» и ЦАГИ.

Источники

• de Boor, C. (1978). A Practical Guide to Splines. Springer-Verlag.
• Piegl, L., & Tiller, W. (1997). The NURBS Book. Springer.
• Rogers, D. F. (2001). An Introduction to NURBS: With Historical Perspective. Morgan Kaufmann.
• Шёнберг, И. (1946). Contributions to the Problem of Approximation of Equidistant Data by Analytic Functions. Quarterly of Applied Mathematics.
• Farin, G. (2002). Curves and Surfaces for CAGD: A Practical Guide. Morgan Kaufmann.