- •Параметрические Кривые: Обзор
- •Примеры
- •Касательный Вектор и Касательная
- •Примеры
- •Нормальный Вектор и Кривизна
- •Кривизна
- •Еще примеры
- •Почему Направляющая Тройка Важна?
- •Вопросы Непрерывности
- •Проблемы с Параметрическим Представлением
- •Параметризация По Длине Дуги
- •Геометрическая Непрерывность
- •Рациональные Кривые
- •Рациональные Формы Стандартных Кривых
- •Теоремы Объединения [Uniformization]
- •Построение Кривых Безье
- •Что, если область u не [0.1]?
- •Краткий Итог
- •Нахождение точки на Кривой Безье: Алгоритм De Casteljau's
- •Вычисления
- •Рекурсивное Представление
- •Кривые Безье Касательны к их Первому и Последнему Сегменту.
- •Объединение Двух Кривых Безье с соблюдением c1-Непрерывности
- •Соотношение Между Производной и Алгоритмом de Casteljau
- •Производные Высших Порядков [Higher Derivatives]
- •Разбиение Кривой Безье
- •Зачем Это Нужно, блин ? [Why Do We Need Curve Subdivision?]
- •Базисные Функции b-spline: Определение
- •Два Важных Замечания
- •Какое Значение Имеют Коэффициенты?
- •Базисные Функции b-spline: Важные Свойства
- •Ni,p(u) - это многочлен p-й степени от u
- •Неотрицательность -- Для всех I, p и u, Ni,p(u) неотрицательно
- •Влияние Множественных УзлоFf
- •Примеры Вычислений
- •Простые Узлы
- •Множественные Узлы
- •Кривые b-spline: Определение
- •Кривые b-spline: Важные Свойства
- •Преимущества Использования Кривых b-spline
- •Кривые b-spline: Вычисление Коэффициентов
- •Кривые b-spline: Перемещение Контрольных Точек
- •Некоторые Полезные Следствия Свойства Сильного Ограничивающего Многоугольника
- •Кривые b-spline: Изменение Узлов
- •Замечание о Множественных Узлах
- •Производные Кривой b-spline
- •Фиксированные Кривые b-spline
- •Производные Высших Порядков
- •Nurbs: Мотивация
- •Nurbs: Определение
- •Два Прмых Следствия [Two Immediate Results]
- •Геометрическая Интерпретация.
- •Nurbs: Важные Свойства
- •Важные Свойства Базисных Функций nurbs
- •Неотрицательность -- для всех I и p, Ri,p(u) неотрицательно
- •Важные Свойства Кривых nurbs
- •Кривая nurbs p(u) - это кусочная кривая, каждый компонент которой - это рациональная кривая степени p
- •Фиксированная кривая nurbs p(u) проходит через две крайние контр. Точки p0 и pn
- •Nurbs: Изменение Весов
- •Углубленное Рассуждение
- •Кривые b-spline/nurbs: Введение Узла
- •Введение Одиночного Узла
- •Пример 1: Введение Узла на Узловом Интервале
- •Пример 2: Введение Узла в Существующем Простом Узле
- •Пример 3: Введение Узла в Существующем Множественном Узле
- •Введение Узла для Кривых nurbs
- •Кривые b-spline/nurbs: Множественное Введение Узла
- •Замечание (Наблюдение) I: Коэффициенты для Вычисления Новых Контр. Точек
- •Замечание [Наблюдение] II: Вычисление Новых Контрольных Точек
- •Вычислить первый столбец, второй столбец, ... И h-ый столбец;
- •Новым набором контр. Точек будут те, что ограничены пунктирным многоугольником.
- •Отсечение Углов
- •Алгоритм De Boor
- •Алгоритм De Boor для Кривых nurbs
- •Основные Понятия
- •Параметрические Поверхности
- •Неявные Поверхности
- •Особенности
- •Поверхности Безье: Построение [Construction]
- •Базисные Функции
- •Поверхности [Tensor] Произведения
- •Поверхности Безье: Важные Свойства
- •Изопараметрические Кривые
- •Граничные [Boundary] Кривые
- •Направление u и направление V
- •Поверхности [Tensor] Произведения: Возвращаемся к теме
- •Поверхности b-spline: Построение
- •Базисные Функции
- •Фиксированные, Закрытые и Открытые Поверхности b-spline
- •Поверхности b-spline: Важные Свойства
- •Выбор Параметров : Обзор [Parameter Selection Overview]
- •Метод Длины Хорды
- •Центростремительный Метод
- •Получение Узлового Вектора
- •Универсальный Метод
- •Параметры и Узловые Векторы для Поверхностей
- •Глобальная Интерполяция Кривых
- •Нахождение Решения
- •Алгоритм
- •Влияние Параметров и Узлов
- •Влияние Степени
- •Почему Этот метод Назывется Глобальным?
- •Глобальная Аппроксимация Кривых
- •Значение Наименьшей Площади
- •Поиск Решения
- •Алгоритм
- •Влияние Степени и Количества Контрольных Точек
- •Почему Этот Метод Глобальный?
- •Глобальная Интерполяция Поверхностей
- •Поиск Решения
- •Почему Этот Метод Глобальный?
- •Глобальная Аппроксимация Поверхностей
- •Поиск Решения
- •Усовершенствование Алгоритма
- •Простое Сравнение
Отсечение Углов
Как упоминалось ранее, введение узла - это процесс отсечения углов. Например, допустим, у нас есть кривая B-spline степени 6 и нам нужно ввести узел u дважды в узел u10 множественности 2. Зависящие контр. точки - это p10, p9, ..., p4, since k = 10, p = 6 and k-p = 4. Так как множественность u10 равна 2, имеем s = 2 и u10 и p9 неизменны. Первое введение дает p8,1, p7,1, p6,1 и p5,1, и углы в p7, p6 и p5 отсекаются. Новый набор контр. точек содержит p0 to p4, p5,1, p6,1, p7,1, p8,1, p8, p9, p10, .....
Второе введение дает p8,2, p7,2 и p6,2. Таким образом, углы в p7,1 и p6,1 отсекаются и новый набор контр. точек - это точки от p0 до p4, p5,1, p6,2, p7,2, p8,2, p8,1, p8, p9, p10, .....
Алгоритм De Boor
Алгоритм de Boor - это обобщение алгоритма de Casteljau. Он дает быстрый и численно стабильный способ нахождения точки на кривой B-spline для данного u на области определения.
Вспомним из свойства множественных узлов, что увеличение множественности внутреннего узла уменьшает количество ненулевых базисных функций в этом узле. Фактически, если множественность этого узла равна k, то в этом узле существует самое большее p - k + 1 ненулевых базисных функций. Следовательно, в узле множественности p будет всего одна ненулевая базисная функция, значение которой в этом узле равно единице (свойство деления единства). Пусть этот узел будет ui. Если u равно ui, то из-за того, что Ni,p(u) не равно нулю на [ui,ui+1), точка на кривой p(u) будет зависеть от ровно одной контр. точки pi. Говоря точнее, имеем p(u) = Ni,p(u) pi = pi!
Так какая точка обладает таким интересным и немного странным свойством? Все просто: если узел 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 раз); Копируем зависимые контр. точки pk-s, pk-s-1, pk-s-2, ..., pk-p+1 и pk-p в новый массив и обозначаем их как pk-s,0, pk-s-1,0, pk-s-2,0, ..., pk-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 ) pi,r = (1 - ai,r) pi-1,r-1 + ai,r pi,r-1
end
pk-s,p-s - это точка p(u).
На следующей диаграмме слева, все pi,0 находятся в левом столбце. Из нулевого столбца и коэффициентов ai,1 можно найти значения pi,1. Из этого первого столбца и коэффициентов ai,2 получаем второй столбец и т.д. Так как в нулевом столбце (k-s)-(k-p)+1 = p-s+1 точек, и так как в каждом столбце на одну точку меньше, чем в предыдущем, то нужно p-s столбцов, чтобы уменьшить количество точек в столбце до единицы. Вот почему последняя точка - это pk-s,p-s. Диаграмма справа показывает процесс отсечения углов.
Хотя этот процесс выглядит похожим на тот, что в алгоритме de Casteljau, на самом деле они очень отличаются. Во-первых, в алгоритме de Casteljau точки деления вычисляются с помощью пары чисел 1 - u и u, которые не меняются в течение всего расчета, тогда как в алгоритме de Boor эти пары чисел различны и зависят от номера столбца и номера контр. точки. Во-вторых, алгоритм de Casteljau можно использовать для разделения кривой, тогда как промежуточные контр. точки, полученные при помощи алгоритма de Boor, не подходят для этой цели. В-третьих, в алгоритме de Boor только p+1 зависимых контр. точек участвуют в вычислениях, тогда как в алгоритме de Casteljau используются все контр. точки. Так как контр. точки от pk-p до pk определяют огранич. многоугольник, который содержит отрезок кривой на узловом интервале [uk, uk+1), то вычисление по алгоритму de Boor идет в пределах соответствующего огранич. многоугольника.
Пример
Возьмем кривую B-spline 3 степени (т.e. p = 3), определяемую 7-ю контр. точками p0, ..., p6 (т.e. n = 6), и следующим узловым вектором из 11 узлов (т.e. m = 10):
u0 = u1 = u2 = u3 |
u4 |
u5 |
u6 |
u7 = u8 = u9 = u10 |
0 |
0.25 |
0.5 |
0.75 |
1 |
Основываясь на этой информации, мы можем вычислить p(0.4). Для алгоритма de Boor это эквивалентно трехкратному введению u = 0.4. Так как u = 0.4 не в существующем узле, s = 0 и u = 0.4 на [u4, u5), то зависимые контр. точки - это p4, p3, p2 и p1. Вот схема вычисления:
Давайте вычислим второй столбец. Участвующие коэффициенты a :
a4,1 = (u - u4) / ( u4+3 - u4) = 0.2 a3,1 = (u - u3) / ( u3+3 - u3) = 8/15 = 0.53 a2,1 = (u - u2) / ( u2+3 - u2) = 0.8
Таким образом, первый столбец вычисляется следующим образом:
p4,1 = (1 - a4,1)p3,0 + a4,1p4,0 = 0.8p3,0 + 0.2p4,0 p3,1 = (1 - a3,1)p2,0 + a3,1p3,0 = 0.47p2,0 + 0.53p3,0 p2,1 = (1 - a2,1)p1,0 + a2,1p2,0 = 0.2p1,0 + 0.8p2,0
Чтобы вычислить второй столбец, нам нужны следующие коэффициенты:
a4,2 = (u - u4) / (u4+3-1 - u4) = 0.3 a3,2 = (u - u3) / (u3+3-1 - u3) = 0.8
Точки равны
p4,2 = (1 - a4,2) p3,1 + a4,2p4,1 = 0.7p3,1 + 0.3p4,1 p3,2 = (1 - a3,2) p2,1 + a3,2p3,1 = 0.2p2,1 + 0.8p3,1
В итоге, так как a4,3 = (u - u4)/ (u4+3-2 - u4) = 0.6, конечная точка равна
p4,3 = (1 - a4,3)p3,2 + a4,3p4,2 = 0.4p3,2 + 0.6p4,2
Это точка на кривой, соответствующая u = 0.4.
Пожалуйста, заметьте, что u в этом примере не равно узлу. Если u - это узел, то вычисления будут проще, потому что в них будет участвовать меньше контр. точек.