Формула Кокса — де Бура

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

История

Формула была независимо разработана и опубликована двумя математиками в начале 1970-х годов. Американский математик Морис Кокс (Maurice Cox) в 1972 году представил рекуррентное соотношение для вычисления B-сплайнов, а бельгийский математик Карл де Бур (Carl de Boor) — в 1972 году в своей работе, посвященной алгоритмам работы со сплайнами. Де Бур также внес значительный вклад в теорию сплайнов и разработал эффективные алгоритмы для их вычисления, включая алгоритм де Бура для вычисления точки на B-сплайновой кривой.

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

Определение

Формула Кокса — де Бура определяет B-сплайн степени \( p \) (или порядка \( k = p+1 \)) на основе последовательности узлов (knot vector) \( t_0, t_1, \dots, t_{m} \), где \( m \) — количество узлов минус один. B-сплайны степени 0 (кусочно-постоянные функции) задаются непосредственно:

\[ N_{i,0}(u) = \begin{cases} 1, & \text{если } t_i \le u < t_{i+1} \\ 0, & \text{иначе} \end{cases} \]

Для степени \( p > 0 \) используется рекуррентное соотношение:

\[ N_{i,p}(u) = \frac{u - t_i}{t_{i+p} - t_i} N_{i,p-1}(u) + \frac{t_{i+p+1} - u}{t_{i+p+1} - t_{i+1}} N_{i+1,p-1}(u) \]

Здесь:

• \( N_{i,p}(u) \) — значение i-го B-сплайна степени p в точке u.
• \( u \) — параметр (обычно в диапазоне от \( t_p \) до \( t_{m-p} \)).
• \( t_i \) — i-й узел вектора узлов.

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

Свойства

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

• Локальность: значение \( N_{i,p}(u) \) отлично от нуля только на интервале \( [t_i, t_{i+p+1}) \). Это означает, что изменение одного узла или веса влияет только на локальный участок кривой.
• Неотрицательность: все B-сплайны, вычисленные по этой формуле, неотрицательны для любого u.
• Разбиение единицы: для любого u в области определения сумма всех B-сплайнов степени p, определённых на этом интервале, равна 1: \( \sum_{i} N_{i,p}(u) = 1 \).
• Численная устойчивость: рекуррентная формула устойчива к ошибкам округления, что важно для вычислений с плавающей точкой.
• Рекурсивность: для вычисления \( N_{i,p}(u) \) требуется вычислить два B-сплайна степени p-1, каждый из которых, в свою очередь, требует вычисления двух B-сплайнов степени p-2, и так далее до степени 0.

Алгоритм вычисления

На практике вычисление по формуле Кокса — де Бура обычно реализуется рекурсивно или итеративно. Для заданного параметра u и индекса i, соответствующего ненулевому B-сплайну на этом интервале, строится треугольная таблица значений. На нижнем уровне (степень 0) находятся значения \( N_{i,0}(u) \), которые равны 1 для одного интервала и 0 для остальных. Затем последовательно вычисляются значения для степеней 1, 2, ..., p.

Алгоритм де Бура для вычисления точки на B-сплайновой кривой также использует эту формулу, но применяет её к контрольным точкам, а не к самим базисным функциям. Это позволяет вычислить координаты точки на кривой без явного вычисления значений B-сплайнов.

Применение

Формула Кокса — де Бура является основой для множества приложений в науке и технике:

• Системы автоматизированного проектирования (САПР): построение и редактирование кривых и поверхностей (NURBS — неоднородные рациональные B-сплайны) в программах типа AutoCAD, SolidWorks, CATIA.
• Компьютерная графика: моделирование трёхмерных объектов, анимация, создание сглаженных траекторий движения.
• Численные методы: аппроксимация функций, решение дифференциальных уравнений методом конечных элементов (МКЭ), где B-сплайны используются как базисные функции.
• Робототехника: планирование траекторий движения манипуляторов, обеспечивающих плавность и непрерывность.
• Обработка сигналов: фильтрация и интерполяция дискретных данных.

Пример

Рассмотрим простой пример для степени p=1 (линейные B-сплайны) с равномерным вектором узлов \( t = [0, 1, 2, 3] \). Для i=0:

\[ N_{0,0}(u) = \begin{cases} 1, & 0 \le u < 1 \\ 0, & \text{иначе} \end{cases} \] \[ N_{1,0}(u) = \begin{cases} 1, & 1 \le u < 2 \\ 0, & \text{иначе} \end{cases} \]

Тогда по формуле Кокса — де Бура:

\[ N_{0,1}(u) = \frac{u - 0}{1 - 0} N_{0,0}(u) + \frac{2 - u}{2 - 1} N_{1,0}(u) = u \cdot N_{0,0}(u) + (2 - u) \cdot N_{1,0}(u) \]

На интервале [0,1) \( N_{0,1}(u) = u \), на интервале [1,2) \( N_{0,1}(u) = 2 - u \), вне [0,2) — ноль. Это даёт треугольную (куполообразную) функцию, характерную для линейных B-сплайнов.

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

Несмотря на широкое распространение, формула Кокса — де Бура имеет некоторые ограничения:

• Вычислительная сложность: при большом количестве узлов и высокой степени сплайна рекурсивный вызов может приводить к значительному числу операций, хотя для практических задач (степень до 3-5) это не критично.
• Чувствительность к кратности узлов: при наличии кратных узлов (когда несколько узлов совпадают) знаменатели в формуле могут обращаться в ноль, что требует специальной обработки (обнуление соответствующих членов).
• Необходимость правильного выбора вектора узлов: качество аппроксимации и форма кривой сильно зависят от выбора узлов, что требует опыта от пользователя.

Источники

• Cox, M. G. (1972). "The numerical evaluation of B-splines". Journal of the Institute of Mathematics and its Applications, 10(2), 134–149.
• de Boor, C. (1972). "On calculating with B-splines". Journal of Approximation Theory, 6(1), 50–62.
• de Boor, C. (1978). A Practical Guide to Splines. Springer-Verlag.
• Piegl, L., & Tiller, W. (1997). The NURBS Book. Springer-Verlag.
• Rogers, D. F. (2001). An Introduction to NURBS: With Historical Perspective. Morgan Kaufmann.