Алгоритм De Boor

Алгоритм de Boor - это обобщение алгоритма de Casteljau. Он дает быстрый и численно стабильный способ нахождения точки на кривой B-spline для данного u на области определения.

Вспомним из свойства множественных узлов, что увеличение множественности внутреннего узла уменьшает количество ненулевых базисных функций в этом узле. Фактически, если множественность этого узла равна k, то в этом узле существует самое большее p - k + 1 ненулевых базисных функций. Следовательно, в узле множественности p будет всего одна ненулевая базисная функция, значение которой в этом узле равно единице (свойство деления единства). Пусть этот узел будет u_i. Если u равно u_i, то из-за того, что N_i,p (u) не равно нулю на [ u_i, u_{i +1}), точка на кривой p (u) будет зависеть от ровно одной контр. точки p _i. Говоря точнее, имеем p (u) = N_i,p (u) p _i = p _i!

Так какая точка обладает таким интересным и немного странным свойством? Все просто: если узел u вводится p раз в кривую B-spline/NURBS, то последняя полученная контр. точка - это и есть точка на кривой, соответствующая u. Почему так? После введения u p раз, треуголная схема вычислений даст одну точку. Из-за того, что данная кривая B-spline/NURBS должна проходить через эту новую точку, это и есть точка на кривой, соответствующая u. Заметьте, это подходит и для случая, когда u вводится в существующий узел.

Таким образом, это наблюдение дает нам метод нахождения p (u) на кривой. Мы просто вводим u p раз, и последняя точка - это p (u)!

Взглянем на пример перед тем, как продолжить. Вот кривая NURBS 4 степени с 7 контр. точками. Чтобы вычислить p (0.9), узел u = 0.9 вводится 4 (равно степени) раза. Второй и третий рисунок показывают результаты первого и второго введения узла. Таким образом, добавляются две новых контр. точки вблизи правого нижнего угла. Пожалуяста, заметьте, что контр. ломаная ближе к кривой, чем исходная. Результат третьего введения показан на четвертом рисунке. Мы получили еще одну контр. точку; но точка на кривой еще не пронумерована, так как она еще не является контр. точкой. После четвертого введения это происходит, т.е. p (0.9) становится контр. точкой.

Общий алгоритм введения узла, обсуждавшийся на предыдущей странице, можно легко преобразовать, чтобы он подходил для наших задач. Во-первых, заметьте, что нам нужно ввести u достаточное количество раз, чтобы u стало узлом множественности p. Если u уже является узлом множественности s, то будет достаточно ввести его p - s раз.

Вход: значение u
Выход: точка на кривой, p (u)

Если u лежит на [ u_k, u_{k +1}) и u!= u_k, то берем h = p (т.e. вводим u p раз), а s = 0;
Если u = u_k и u_k - это узел множественности s, то берем h = p - s (т.e. вводим u p - s раз);
Копируем зависимые контр. точки p _k-s, p _{k-s -1}, p _{k-s -2},..., p _{k-p +1} и p _k-p в новый массив и обозначаем их как p _{k-s ,0}, p _{k-s -1,0}, p _{k-s -2,0},..., p _{k-p +1,0};

for r:= 1 to h do

for i:= k-p+r to k-s do

Begin

a_i,r = (u - u_i) / (u_{i+p-r +1} - u_i)
p _i,r = (1 - a_i,r) p _{i -1, r -1} + a_i,r p _{i , r -1}

End

p _k-s,p-s - это точка p (u).

На следующей диаграмме слева, все p _{i ,0} находятся в левом столбце. Из нулевого столбца и коэффициентов a_{i ,1} можно найти значения p _{i ,1}. Из этого первого столбца и коэффициентов a_{i ,2} получаем второй столбец и т.д. Так как в нулевом столбце (k-s)-(k-p)+1 = p-s +1 точек, и так как в каждом столбце на одну точку меньше, чем в предыдущем, то нужно p-s столбцов, чтобы уменьшить количество точек в столбце до единицы. Вот почему последняя точка - это p _{k-s , p-s}. Диаграмма справа показывает процесс отсечения углов.

Хотя этот процесс выглядит похожим на тот, что в алгоритме de Casteljau, на самом деле они очень отличаются. Во-первых, в алгоритме de Casteljau точки деления вычисляются с помощью пары чисел 1 - u и u, которые не меняются в течение всего расчета, тогда как в алгоритме de Boor эти пары чисел различны и зависят от номера столбца и номера контр. точки. Во-вторых, алгоритм de Casteljau можно использовать для разделения кривой, тогда как промежуточные контр. точки, полученные при помощи алгоритма de Boor, не подходят для этой цели. В-третьих, в алгоритме de Boor только p +1 зависимых контр. точек участвуют в вычислениях, тогда как в алгоритме de Casteljau используются все контр. точки. Так как контр. точки от p _k-p до p _k определяют огранич. многоугольник, который содержит отрезок кривой на узловом интервале [ u_k, u_{k +1}), то вычисление по алгоритму de Boor идет в пределах соответствующего огранич. многоугольника.

Пример

Возьмем кривую B-spline 3 степени (т.e. p = 3), определяемую 7-ю контр. точками p ₀,..., p ₆ (т.e. n = 6), и следующим узловым вектором из 11 узлов (т.e. m = 10):

u 0 = u 1 = u 2 = u 3	u 4	u 5	u 6	u 7 = u 8 = u 9 = u 10
	0.25	0.5	0.75

Основываясь на этой информации, мы можем вычислить p (0.4). Для алгоритма de Boor это эквивалентно трехкратному введению u = 0.4. Так как u = 0.4 не в существующем узле, s = 0 и u = 0.4 на [ u ₄, u ₅), то зависимые контр. точки - это p ₄, p ₃, p ₂ и p ₁. Вот схема вычисления:

Давайте вычислим второй столбец. Участвующие коэффициенты a:

a _4,1 = (u - u ₄) / (u ₄₊₃ - u ₄) = 0.2
a _3,1 = (u - u ₃) / (u ₃₊₃ - u ₃) = 8/15 = 0.53
a _2,1 = (u - u ₂) / (u ₂₊₃ - u ₂) = 0.8

Таким образом, первый столбец вычисляется следующим образом:

p _4,1 = (1 - a _4,1) p _3,0 + a _4,1 p _4,0 = 0.8 p _3,0 + 0.2 p _4,0
p _3,1 = (1 - a _3,1) p _2,0 + a _3,1 p _3,0 = 0.47 p _2,0 + 0.53 p _3,0
p _2,1 = (1 - a _2,1) p _1,0 + a _2,1 p _2,0 = 0.2 p _1,0 + 0.8 p _2,0

Чтобы вычислить второй столбец, нам нужны следующие коэффициенты:

a _4,2 = (u - u ₄) / (u _4+3-1 - u ₄) = 0.3
a _3,2 = (u - u ₃) / (u _3+3-1 - u ₃) = 0.8

Точки равны

p _4,2 = (1 - a _4,2) p _3,1 + a _4,2 p _4,1 = 0.7 p _3,1 + 0.3 p _4,1
p _3,2 = (1 - a _3,2) p _2,1 + a _3,2 p _3,1 = 0.2 p _2,1 + 0.8 p _3,1

В итоге, так как a _4,3 = (u - u ₄)/ (u _4+3-2 - u ₄) = 0.6, конечная точка равна

p _4,3 = (1 - a _4,3) p _3,2 + a _4,3 p _4,2 = 0.4 p _3,2 + 0.6 p _4,2

Это точка на кривой, соответствующая u = 0.4.

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

Дата добавления: 2015-10-29