Приложение Ж. Вычисление В-сплайновой кривой по методу Кокса—де Бура

Опишем вычисление В-сплайновой кривой по методу Кокса—де Бура. Для этого мы вычислим координаты В-сплайновой кривой для параметра и в диапазоне tx ≤ и ≤ tl+1. Когда и находится в этом диапазоне, достаточно рассмотреть только Ыц. Распространяя эффект Nl,1 (см. рис 6.5), мы можем заключить, что только функции сопряжения Nl-(k-1)k,..., Nl,k, могут иметь ненулевые значения. Поэтому выражение для Р(u) можно изменить следующим образом:

Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура

Подставляя уравнение (6.32) в уравнение (Ж.1), получаем:

  Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура

где Рiопределяется следующим образом1:

  Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура

Таким образом,  Рil можно интерпретировать как внутреннюю точку разбиения сегмента линии РiРi-1, аналогично алгоритму де Кастильо.

Теперь Ni,k-1 выражается через комбинацию Ni,k_2 и Ni+1,k-2 с помощью формулы (6.32), и это выражение подставляется в уравнение (Ж.2) вместо Ni,k-1. После этого, используя процесс, аналогичный тому, который применялся при выводе уравнения (Ж.2), мы можем получить следующее соотношение:

Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура

где Рi2 определяется следующим образом:

Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура

Иными словами, Рiтакже представляет собой внутреннюю точку разбиения сегмента линии Рil Рli-1.

Повторив ту же процедуру произвольное число раз r, мы получим:

Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура

где

Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура

Рir носит название точки де Бура. Обратите внимание, что под Рi° в выражении (Ж.6) понимается Рi.

Делая в уравнении (Ж.6) подстановку r = (k- 1), получим

  Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура

Поэтому мы можем сказать, что координаты точки, соответствующей значению параметра и в диапазоне t1 ≤ и ≤ tl+l, — это координаты Рlk-1 получаемые путем рекурсивного разбиения сегментов линий между соответствующими точками, начиная с сегмента между двумя исходными задающими точками.

Процесс итеративного вычисления Рlk-1 с использованием уравнения (Ж.6) можно иллюстрировать схематически (рис. Ж.2). Любая точка Рir определяется верхним левым соседом Рi-1r-l и левым соседом Рjr 1, следовательно, новые точки, создаваемые в процессе рекурсии, образуют нижний треугольник с вершиной в Рlk-1. Эта схематическая диаграмма содержит дополнительную полезную информацию. Мы показали, что кривая В-сплайна порядка 3 в процессе применения алгоритма Кокса—де Бура в примере Ж. 1 может быть разделена на две кривые В- сплайна того же порядка. Эту идею можно распространить на кривую В-сплайна любой степени, как и в случае кривых Безье. На самом деле две группы точек на рис. 6.12, окруженные пунктирными линиями, — это задающие точки двух кривых В-сплайна, полученных путем разделения исходной кривой В-сплайна, определенной точками Р0, Р1, .... Рn, в точке, где параметр и принимает значение t1≤u≤ tl+1. Таким образом, кривую В-сплайна любого порядка можно разбить на множество кривых В-сплайна того же проядка, многократно применяя алгоритм Кокса—де Бура, и результирующие задающие многоугольники будут достаточно близко аппроксимировать исходную кривую, как и в случае применения алгоритма де Кастильо для аппроксимации кривой Безье. Такая аппроксимация прямолинейными сегментами может использоваться для вычисления начальных значений точек пересечения между кривыми В-сплайна. Алгоритм Кокса— де Бура может быть реализован на языке С (листинг Ж.1).
Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура
 
Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура
Приложение Ж.  Вычисление В-сплайновой кривой по методу Кокса—де Бура
 

1 Во второй строке (Ж.2) делается подстановкаj = i + 1, а в третьей строке диапазон суммирования сужается, поскольку Nl-k+1,k-1 и Nj+1,k-1 равны нулю в интервале tl и tl+1.