Глобальная Интерполяция Поверхностей

Путсь у нас есть m+1 рядов и n+1 столбцов исходных точек d_ij (0 <= i <= m и 0 <= j <= n) и нужно найти поверхность B-spline степени (p,q), содержащую все из них. Аналогично случаю кривых, имеем исходные точки и степени p и q в качетстве исходных данных. Чтобы определить кривую B-spline, нам нужно два узловых вектора U и V, по одному на каждое направление, и набор контр. точек. Как и в случае с кривыми, количества контрольных и исходных точек равны (т.e. (m+1)×(n+1) контр. точек в m+1 рядах и n+1 столбцах). С помощью метода, обсуждавшегося в Параметрах и Узловых Векторах для Поверхностей, мы можем вычислить два набора параметров: s_c (0 <= c <= m) в направлении u и t_d (0 <= d <= n) в направлении v, устанавливая e и f в m и n, соответственно. Мы также получим узловые векторы U и V соответственно для направлений u и v. Таким образом, все, что остается сделать - это найти нужные контр. точки!

Поиск Решения

Теперь нам нужно найти интерполированную поверхность B-spline степени (p,q). Так как у нас есть узловые векторы, параметры, степени и исходные точки, то единственная недостающая часть - это (m+1)×(n+1) контр. точек.

Пусть дана такая поверхность B-spline:

Так как она содержит все исходные точки и так как параметры s_c и t_d соответствуют исходной точке d_cd, то, подставив u=s_c и v=t_d в уравнение поверхности, получим:

Так как N_i,p(s_c) не зависит от индекса j, то можно вынести этот член из суммирования по j:

Если рассмотреть внутреннее выражение, то видно, что индекс i есть только в p_ij. Таким образом, можно взять для удобства новое обозначение:

Говоря точнее, если i фиксирована в одном и том же значении, то q_id - это точка, вычисленная для t_d, на кривой B-spline степени q, определенной по n+1 "неизвестным" контр. точкам i-го ряда из p (т.e. p_i0, p_i1, ..., p_in). Подставляя q_id в вышеуказанное уравнение d_cd, получим

Таким образом, исходная точка d_cd - это точка, вычисленная для s_c, кривой B-spline степени p, определенной по m+1 "неизвестным" контр. точкам столбца d из q (т.e., q_0d, q_0d, ..., q_md). Повторяя это для каждого c (0 <= c <= m), получим d-й столбец исходных точек (т.e. d_0d, d_1d, ..., d_md) из d-го столбца q (т.e. q_0d, q_1d, ..., q_md) и параметров s₀, s₁, ..., s_m. Так как исходные точки d_0d, d_1d, ..., d_md, степень p и параметры s₀, s₁, ..., s_m известны, то это уравнение обозначает

Найти d-й столбец контр. точек q_0d, q_1d, ..., q_md по данным: степени p, параметрам s₀, s₁, ..., s_m и d-му столбцу исходных точек.

Получается, это задача интерполяции кривой! То есть, можно применить глобальную интерполяцию кривой к каждому столбцу исходных точек, чтобы получить столбцы контр. точек q_cd. Так как имеется n+1 столбцов исходных точек, то получим n+1 столбцов q.

Теперь, мы можем использовать ту же самую идею, но применять ее к уравнению q_id, которое показано еще раз ниже. В этом уравнении, исходные точки ряда i из q (т.e. q_i0, q_i1, ..., q_in)- это точки на кривой B-spline, вычисленные для t₀, t₁, ..., t_n, степени q, определенной по n+1 неизвестным контр. точкам p_i0, p_i1, ..., p_in. Таким образом, применяя интерполяцию кривой со степенью q и параметрами t₀, t₁, ..., t_n к ряду i из q, получим i ряд искомых контр. точек!

Когда найдем все ряды контр. точек, то эти контр. точки, вместе с двумя узловыми векторами и степенями p и q, определят интерполированную поверхность B-spline степени (p,q) для данных исходных точек. Таким образом, интерполяция поверхности B-spline состоит из (m+1) + (n+1) интерполяций кривой! Вот обобщение всех необходимых шагов:

Вход: (m+1)×(n+1) исходных точек d_ij и степень (p,q); Выход: Поверхность B-spline степени (p,q), содержащая все исходные точки; Алгоритм:

Вычисляем параметры в направлении u s₀, s₁, ..., s_m и узловой вектор U; Вычисляем параметры в направлении v t₀, t₁, ..., t_n и узловой вектор V; for d := 0 to n do /* для столбца d */

begin /* вычисляем "промежуточные исходные точки" q */

Применяем интерполяцию кривой к столбцу d исходных точек (т.e. d_0d, d_1d, ... d_md), используя

• степень p

• параметры s₀, s₁, ..., s_m

• узловой вектор U

Результат - столбец d "промежуточных исходных точек" q_0d, q_1d, ..., q_md

end

for c := 0 to m do /* для ряда c */

begin /* вычисляем искомые контр. точки p */

Применяем интерполяцию кривой к ряду c из q (т.e., q_c0, q_c1, ... q_cn), используя

• степень q

• параметры t₀, t₁, ..., t_n

• узловой вектор V

Результат - ряд c искомых контр. точек p_c0, p_c1, ..., p_cn

end

Найденные (m+1)×(n+1) контр. точек p_ij, степень (p,q) и узловые векторы U и V определяют интерполированную поверхность B-spline степени (p,q) для данных исходных точек.