Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Алгоритм De Boor

Читайте также:
  1. CRC-алгоритмы обнаружения ошибок
  2. VII. Алгоритмы продаж
  3. Алгоритм 4. Транспонування бази даних
  4. Алгоритм 5. Пошук автофильтром
  5. Алгоритм Apriori
  6. Алгоритм De Boor для Кривых NURBS

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

Вспомним из свойства множественных узлов, что увеличение множественности внутреннего узла уменьшает количество ненулевых базисных функций в этом узле. Фактически, если множественность этого узла равна k, то в этом узле существует самое большее p - k + 1 ненулевых базисных функций. Следовательно, в узле множественности p будет всего одна ненулевая базисная функция, значение которой в этом узле равно единице (свойство деления единства). Пусть этот узел будет ui. Если u равно ui, то из-за того, что Ni,p (u) не равно нулю на [ ui, ui +1), точка на кривой p (u) будет зависеть от ровно одной контр. точки p i. Говоря точнее, имеем p (u) = Ni,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 лежит на [ uk, uk +1) и u!= uk, то берем h = p (т.e. вводим u p раз), а s = 0;
Если u = uk и uk - это узел множественности 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

ai,r = (u - ui) / (ui+p-r +1 - ui)
p i,r = (1 - ai,r) p i -1, r -1 + ai,r p i , r -1

End

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

На следующей диаграмме слева, все p i ,0 находятся в левом столбце. Из нулевого столбца и коэффициентов ai ,1 можно найти значения p i ,1. Из этого первого столбца и коэффициентов ai ,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 определяют огранич. многоугольник, который содержит отрезок кривой на узловом интервале [ uk, uk +1), то вычисление по алгоритму de Boor идет в пределах соответствующего огранич. многоугольника.

Пример

Возьмем кривую B-spline 3 степени (т.e. p = 3), определяемую 7-ю контр. точками p 0,..., p 6 (т.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 4, u 5), то зависимые контр. точки - это p 4, p 3, p 2 и p 1. Вот схема вычисления:

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

a 4,1 = (u - u 4) / (u 4+3 - u 4) = 0.2
a 3,1 = (u - u 3) / (u 3+3 - u 3) = 8/15 = 0.53
a 2,1 = (u - u 2) / (u 2+3 - u 2) = 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 4) / (u 4+3-1 - u 4) = 0.3
a 3,2 = (u - u 3) / (u 3+3-1 - u 3) = 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 4)/ (u 4+3-2 - u 4) = 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; просмотров: 232 | Нарушение авторских прав


Читайте в этой же книге: Кривые B-spline: Вычисление Коэффициентов | Кривые B-spline: Перемещение Контрольных Точек | Некоторые Полезные Следствия Свойства Сильного Ограничивающего Многоугольника | NURBS: Определение | Важные Свойства Кривых NURBS | NURBS: Изменение Весов | Углубленное Рассуждение | Введение Одиночного Узла | Пример 2: Введение Узла в Существующем Простом Узле | Введение Узла для Кривых NURBS |
<== предыдущая страница | следующая страница ==>
Замечание [Наблюдение] II: Вычисление Новых Контрольных Точек| Алгоритм De Boor для Кривых NURBS

mybiblioteka.su - 2015-2024 год. (0.011 сек.)