Преимущества Использования Кривых b-spline
Для кривых B-spline нужно больше информации (i.e. степень кривой и узловой вектор) и они более сложны в вычислениях по сравнению с кривыми Безье. Но они имеют перед ними много преимуществ. Во-первых, кривая B-spline может сводиться к кривой Безье. Во-вторых, у кривых B-spline есть те же важные свойства, что и у кривых Безье. В-третьих, кривые B-spline имеют бóльшую гибкость в управлении, чем Безье. Например, степень кривой B-spline не зависит от количества контрольных точек. Говоря точнее, мы можем использовать кривые меньших степеней, но по-прежнему много контрольных точек. Можем изменить положение конрольной точки без изменения формы кривой в целом (свойство локального изменения). Так как у кривых B-spline есть свойство сильного огранич. многоугольника, их формой можно управлять точнее. Кроме того, есть и другие техники проектирования и редактирования формы кривой, например, изменение узлов.
Как бы то ни было, следует помнить, что кривые B-spline являются полиномиальными (описываемыми многочленом) кривыми, и поэтому с их помощью нельзя описать некоторые полезные кривые, как например, окружности или эллипсы. Поэтому нужно обобщение B-spline, NURBS. Но об этом позже.
Кривые b-spline: Вычисление Коэффициентов
Хотя алгоритм de Boor является стандартным способом нахождения точки на кривой B-spline, соответствующей данному u, во многих случаях (напр., интерполяция и аппроксимация кривых) нам действительно нужны коэффициенты. Покажем простой способ сделать это.
Дана фиксированая кривая B-spline степени p, построенная по n+1 контрольным точкам p0, p1, ..., pn, и m+1 узлам u0=u1=...=up=0, up+1, up+2, ..., um-p-1, um-p=um-p+1=...= um=1, нам нужно вычислить коэффициенты N0,p(u), N1,p(u), ..., Nn,p(u) для любого данного u на [0,1]. Простейший способ - это использовать следующее рекурсивное выражение:
Тем не менее, это очень затратный по времени процесс. Чтобы найти Ni,p(u), нам нужно вычислить Ni,p-1(u) и Ni+1,p-1(u). Чтобы найти Ni,p-1(u), нам нужно вычислить Ni,p-2(u) и Ni+1,p-2(u). Чтобы найти Ni+1,p-1(u), нам нужно Ni+1,p-2(u) и Ni+2,p-2(u). Как видите Ni+1,p-2(u) участвует дважды, и, в результате, ее рекурсивные вычисления также повторятся. Когда рекурсия идет вглубь, появляется все больше повторяющихся вычислений. Это очень похоже на рекурсивную версию алгоритма de Casteljau, который обсуждался ранее. Следовательно, скорость вычисления очень мала.
Есть простой способ сделать то же самое. Допустим, u лежит на узловом интервале [uk,uk+1). Важное свойство базисных функций B-spline говорит о том, что базисные функции самое большее p+1 степени не равны нулю на [uk,uk+1), а именно: Nk-p,p(u), Nk-p+1,p(u), Nk-p+2,p(u), ..., Nk-1,p(u), Nk,p(u). По определению, единственная ненулевая базисная функция 0 степени на [uk,uk+1) - это Nk,0(u). В итоге, коэффициенты можно найти из Nk,0(u) в треугольной форме в виде веера:
Так как Nk,0(u) = 1 на узловом интервале [uk,uk+1), а другие базисные функции 0 степени равны нулю на [uk,uk+1), мы можем начать с Nk,0(u) и вычислить базисные функции 1 степени Nk-1,1(u) и Nk,1(u). Из этих двух значений 1 степени можно найти значения базисных функций 2 степени Nk-2,2(u), Nk-1,2(u) и Nk,2(u). Этот процесс повторяется, пока не будут найдены все p+1 ненулевых коэффициента.
В этом вычислении, "внутренние" значения, такие как Nk-1,2(u), имеют как соседа справа сверху (т.e. Nk-1,1(u)), так и соседа справа снизу (т.e. Nk,1(u)); значения на границе, идущей по направлению вправо вниз, такие как Nk-1,1(u) имеют только соседа слева снизу (т.e., Nk,0(u)); а значения на границе, идущей по направлению влево вниз, такие как Nk,2(u) имеют только соседа слева сверху (т.e., Nk,1(u)). Таким образом, значения, находящиеся на границе, идущей по направлению вправо вверх (соотв., вправо вниз), исползуют второй (соотв. первый) член рекурсивного уравнения в определении. Только внутренние значения зависят от обоих членов. Основываясь на этом наблюдении, имеем следующий алгоритм:
Вход: n, p, m, u, и m+1 фиксированных узлов { u0, ..., um } Выход: Коэффициенты N0,p(u), N1,p(u), ..., Nn,p(u) в [in] N[0], N[1], ..., N[n] Алгоритм:
Задаем N[0..n] равными 0; // инициализация If u = u0 then // проверяем особые случаи
N[0] = 1.0; return
else u = um then
N[n] = 1.0 return
end if
// теперь u между u0 и um
Пусть u лежит на узловом интервале [uk,uk+1); R[k] := 1.0 // коэффициент 0 степени for d :=1 to p do // изменяем степень d от 1 до p
begin
N[k-d]
=
*
N[(k-d)+1];
// только правый член (юго-западный
угол)
for
i
:= k-d+1
to
k-1
do
// вычисляем значения внутри
N[i]
:=
*
N[i]
+
*
N[i+1];
N[k]
=
*
N[k];
// только левый член (северо-западный
угол)
end
// в массиве N[0..n] нужные коэффициенты.
Вышеизложенный алгоритм не очень эффективен. Его цель - просто и понятно проиллюстрировать смысл вычислений. Массив N[ ] содержит все промежуточные и конечные результаты. Для степени d элемент N[i] хранит значение Ni,d(u), а в конце, N[k-d], N[k-d+1], ..., N[k] содержат все ненулевые коэффициенты. Вычисление начинается с d=1, потому что мы знаем, что единственная ненулевая базисная функция - это Nk,0(u), если u на узловом интервале [uk,uk+1). Внешний цикл изменяет степень d от 1 до p. Первое выражение после begin вычисляет Nk-d,d(u), используя только один член выражения (т.e., его юго-западный сосед в треугольной схеме, Nk-d+1,d-1(u)), внцтренний цикл for вычисляет "внутренние" члены, а последнее выражение во внешнем цикле вычисляет Nk,d(u), используя только один член выражения (т.e., его северо-западный сосед в треугольной схеме, Nk,d-1(u)).
Если вы хорошо разберетесь в этом аалгоритме, сможете ли вы сделать его более эффективным?