- •Параметрические Кривые: Обзор
- •Примеры
- •Касательный Вектор и Касательная
- •Примеры
- •Нормальный Вектор и Кривизна
- •Кривизна
- •Еще примеры
- •Почему Направляющая Тройка Важна?
- •Вопросы Непрерывности
- •Проблемы с Параметрическим Представлением
- •Параметризация По Длине Дуги
- •Геометрическая Непрерывность
- •Рациональные Кривые
- •Рациональные Формы Стандартных Кривых
- •Теоремы Объединения [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, проходящей по исходным точкам, - это метод глобальной интерполяции. Почему интерполяция "глобальная", станет ясно позже на этой странице.
Пусть есть n+1 исходных точек d0, d1, ..., dn и нужно по ним провести кривую B-spline степени p, где p <= n - это входные данные. С помощью метода, обсужденного в Выборе Параметров и Получении Узлового Вектора, можно выбрать набор значений параметров t0, t1, ..., tn. Заметьте, что количество параметров равно количеству исходных точек, потому что параметр tk соответствует исходной точке dk. Из этих параметров вычисляется узловой вектор из m + 1 узлов, где m = n + p + 1. Таким образом, у нас есть узловой вектор и степень, и единственная недостающая деталь - это набор из n+1 контр. точек! Глобальная интерполяция - это простой способ нахождения этих контр. точек.
Нахождение Решения
Пусть желаемая интерполированная кривая B-spline степени p следующая:
Эта кривая B-spline имеет n + 1 неизвестных контр. точек. Так как параметр tk соответствует исходной точке dk, то, подставляя tk в вышеуказанное уравнение, получим следующее:
Так как в вышеуказанном уравнении n + 1 базисных функций B-spline (т.e. N0,p(u), N1,p(u), N2,p(u), ... и Nn,p(u), и n + 1 параметр (т.e. t0, t1, t2, ... и tn), то , подставив эти tk в Ni,p(u) получим (n+1)2 значений. Эти значения можно записать в виде матрицы N размера (n+1)×(n+1), в которой k-й ряд содержит значения N0,p(u), N1,p(u), N2,p(u), ... и Ni,p(u) для tk, как показано ниже:
Давайте также соберем векторы dk и pi в дае матрицы D и P следующим образом:
Здесь будем считать, что исходная точка dk является вектором в s-мерном пространстве (т.e. dk = [ dk1, ... , dks]) и стоит в k-м ряду матрицы D. Аналогично, считаем pi вектором в s-мерном пространстве (т.e. pi = [ pi1, ... , pis]) и что она находится в i-м ряду матрицы P. Заметьте, что в трехмерном пространстве s = 3, а на плоскости s = 2. Также заметьте, что матрицы D и P - обе размера (n+1)×s. Затем, нетрудно проверить, что соотношение между значениями dk и ti преобразуется к такому более простому виду:
Так как матрица D содержит исходные точки и матрица N получены вычислением базисных функций B-spline по данным параметрам, то D и N - обе известны, а неизвестно только P. Так как это просто система линейных уравнений с неизвестным P, то, решая относительно P, получим контр. точки и желаемая интерполированная кривая B-spline станет доступной. Таким образом, задача интерполяции кривой решена!
Алгоритм
Матрицы D и P - не являются матрицами-столбцами, но это не большая проблема. Можно решать систему по столбцам. Говоря точнее, пусть i-й столбец D и i-й столбец P будут di и pi, соответственно. Из вышеуказанной системы линейных уравнений, получаем следующее:
Затем, решая относит. pi из N и di даст i-й столбец P. Проделываем это для каждого i в пределах от 0 до h, и получим в итоге P. Таким образом, все контр. точки найдены. Как вы, наверное, заметили, это очень неэффективно. К счастью, многие вычислительные библиотеки имеют процедуры решения систем линейных уравнений, которые подходят для эффективного решения уравнения D = N.P. Получается, провести кривую B-spline по n+1 точкам не так уж сложно. Оно сводится к решению системы линейных уравнений. Следующий алгоритм объединяет все сказанное:
Вход: n+1 исходных точек d0, ..... dn и степень p Выход: Кривая B-spline степени p, содержащая все эти исходные точки в данном порядке. Алгоритм:
Выбираем метод для нахождения набора из n+1 параметров t0, ..., tn; Заодно получим и узловой вектор U; for i := 0 to n do
for j := 0 to n do
Вычисляем [Evaluate] Nj,p(ti) и ставим в ряд i и столбец j матрицы N;
/* матрица N найдена */ for i := 0 to n do
Помещаем исходную точку di в ряд i матрицы D;
/* матрица D построена */ Решаем систему уравнений и находим P из D = N.P Ряд i матрицы P - это контр. точка pi; Контр. точки p0, ..., pn, узловой вектор U и степень p определяют интерполированную кривую B-spline;
Ниже, на рисунке (а), показан пример. Здесь 9 исходных точек, показаны черным. Найденные контр. точки показаны синим. Маленькие красные точки на интерполированной кривой - это точки, соответствующие узлам, вычисленным по методу длины хорды. В этом случае, эти "узловые точки" находятся довольно близко к исходным точкам и контр. ломаная также проходит близко к исходной, хоть и не всегда. Например, на рисунке (b), исходная и контрольная ломаные очень отличаются.
|
|
(a) |
(b) |
Важно отметить, что матрица N целиком положительна и окружена полосой с половиной ширины меньше [banded with a semi-bandwidth less than] p (т.e. Ni,p(tk) = 0, если |i - k| >= p), если узлы вычисляются по среднему значению от p последовательных параметров. Это было доказано de Boor в 1978 г. Подробности в Получении Узлового Вектора. Это значит, что система линейных уравнений, полученная по вышеизложенному алгоритму, может быть решена методом исключения Гаусса без вращения [центрирования ? pivoting].