Усовершенствование Алгоритма
Вышеизложенный алгоритм не очень эффективен. Возьмем расчет первого цикла for, в котором вычисляется столбец d промежуточных исходных точек q0d, q1d, ..., qed из столбца d исходных точек d0d, d1d, ..., dmd. Для этого столбца, мы вписываем кривую B-spline степени p в m+1 исходных точек по e+1 контр. точкам. Как обсуждалось в Глобальной Аппроксимации Кривых, неизвестные контр. точки вычисляются при помощи решения системы линейных уравнений (NTN)P=Q для некоторой матрицы Q, где матрица N определяется так:
Матрицы P и Q изменяются, когда мы движемся от столбца к столбцу; а N не меняется. Отсюда, если мы будем просто выполнять первый цикл for в нашем алгоритме, то будем решать систему линейных уравнений n+1 раз с одним и тем же N. Это неэффективно и надо исправить.
Чтобы ускориться, используем LU-разложение NTN при вычислении первого столбца исходных точек. Для всех последующих столбцов мы будем делать только прямую и обратную подстановку (вычисление корней в треугольной матрице - прим. перев.) Аналогично, при вычислении рядов промежуточных исходных точек, применяем LU-разложение только для первого ряда.
Простое Сравнение
Далее показана сетка из шести рядоа и пяти столбцов. Используем ее для иллюстрации различий между интерполяцией и аппроксимацией. Рисунки слева и справа соответственно показывают поверхности до и после перемещения.
Первые два ряда показывают результаты глобальной интерполяции с использованием метода длины хорды для нахождения параметров и узловых векторов. Степень интерполирванной поверхности равна (3,3). Красные и синие кривые - это узловые кривые (т.e. изопараметрические кривые в узлах). Указанная исходная точка немного изменяет свое положение, но синяя узловая кривая изменяется резко. Разница между поверхностями еще больше. Перемещение исходной точки вправо дает большую выпуклость слева и выемку позади этой красной кривой.
Последние два ряда иллюстрируют глобальную аппроксимацию. Количество контр. точек в направлениях u и v равны соответственно 5 и 4. Очевидно, что влияние изменения положения исходной точки на форму аппроксимированной поверхности не такое сильное.
|
До перемещения |
После перемещения |
Интерполяция: Кривые |
|
|
Интерполяция: Поверхность |
|
|
Аппроксимация: Кривые |
|
|
Аппроксимация: Поверхность |
|
|
