Сглаживание B-сплайнами

Математическое представление тела, составленного из простых геометрических форм (сфер, цилиндров или конусов) несложно. Но очень часто это не так; кузова автомобилей, поверхности самолетов, флюзеляжи и многое другое не так-то просто описать. Процедура, обычно используемая в этих случаях, состоит обычно в следующем:

• поверхность покрывается двумя воображаемыми группами линий; первая идет в продольном направлении, вторая — трансверсальна к первой. Эта сетка линий определяет множество ячеек, каждая из которых (в случае гладкой поверхности), будет ограничена четырьмя гладкими кривыми;
• координаты узлов этой воображаемой сетки измеряются на модели или на наборе чертежей поперечных сечений поверхности;
• с помощью интерполяции (усреднения) математически описываются эти две группы линий, образующие сетку.

Можно строить достаточно гладкие кривые и поверхности с использованием полиномов. Допустим, что мы хотим построить поверхность в виде графика функции z = z(x, y). Линия y = const на этой поверхности будет представлена линией z = z(x), она будет проходить через последовательность точек (x₀, z₀), ..., (x_i, z_i), ..., (x_n, z_n) с x₀ < ... < x_i < ... < x_n. Наша цель — провести через эти точки составную кривую f(x), имеющую следующие свойства:

• на каждом подынтервале x_i-1 <= x <= x_i, i = 1, 2, ..., n функция f(x) является кубическим полиномом;
• ее первые и вторые производные непрерывны в узлах.

Полученная гладкая кривая называется кубическим сплайном. Термин «сплайн» возник по аналогии: это название чертежного инструмента — тонкой металлической линейки, которая может изгибаться так, чтобы проходить через заданные точки. Физически такая кривая минимизирует энергию внутренних напряжений. Математически — имеет минимальную среднеквадратичную кривизну, то есть она наиболее гладкая. Сплайны имеют много приложений в конструировании криволинейных форм. Однако они имеют и некоторые ограничения:

• локальное изменение влечет за собой вычисление заново всего сплайна;
• могут возникать проблемы при аппроксимации прямой, имеющей разрывы вторых производных (например, сопряжения прямой линии и дуги окружности);
• с точки зрения эстетики не всегда приемлемы, так как кривизна поверхности, сконструированной с помощью сплайнов, изменяется иногда неравномерно, что приводит к искажениям (например, причудливые искажения предметов, отраженных от кузова автомобиля).

Первое ограничение можно устранить с помощью B-сплайна. Общая форма полученной в этом случае кривой показана на рис. 20.1.

На этом рисунке сплайн продолжен от его конечных точек x_i-4, x_i прямыми линиями, идущими вдоль оси x. В результате получается кубический сплайн на любом числе отрезков, но он не равен нулю только на четырех из них. Такая функция называется B-сплайном (или фундаментальным сплайном) четвертого порядка (или третьей степени). Про него говорят, что он имеет минимальный носитель (носитель — это число отрезков, на которых сплайн отличен от нуля).

Заметим, что кубический B-сплайн полностью определяется множеством узлов, на которых он определен, и только одной заданной величиной z. В более общем виде B-сплайн M_mi(x) порядка m (или степени m - 1) на данном множестве узлов везде равен нулю, кроме m последовательных отрезков x_i-m < x < x_i. Опять-таки M_mi(x) определяется множеством узлов и одной величиной z. Принято исключать последнюю степень свободы и фиксировать амплитуду B-сплайна некоторым стандартным образом.

Часто удобно для вычислений использовать нормализованный B-сплайн N_mi(x), связанный с M_mi(x) соотношением N_mi(x) = (x_i - x_i-m)M_mi(x).

Любой сплайн порядка m на множестве узлов x₀, x₁, ..., x_n может быть выражен в виде линейной комбинации B-сплайнов, определенных на том же множестве узлов, расширенном (m - 1) дополнительными узлами на каждом из концов интервала, которые можно выбрать произвольно: x_-m+1, x_-m+2, ..., x_-1 и x_n+1, ..., x_n+m-1. Можно построить m + n - 1 последовательных B-сплайнов на расширенном множестве узлов, каждый из которых отличен от нуля на m последовательных отрезках. Поэтому можно записать:
j(x) = Sc_i * M_mi(x),
где j(x) — любой сплайн степени (m - 1) на первоначальном множестве узлов и M_mi(x) есть B-сплайн на расширенном множестве узлов, отличный от нуля при x_i-m < x < x_i; c_i  суть числовые коэффициенты; суммирование ведется по i = 1, ..., m + n - 1.

Если имеется множество векторов r₀, r₁, ..., r_n, то можно использовать их: r(u) = Sr_i * N_{4, i+1}(u) (суммирование ведется по i = 0, ..., n). Так как имеется (n + 1) векторных коэффициентов, то необходим набор из (n + 1) B-сплайнов. Последняя формула для 0 <= u <= n - 2 является уравнением кривой, образованной кубическими B-сплайнами.

Свойства

Некоторые простейшие свойства следуют из тождества SN_{4, i+1} = 1, 0 <= u <= n - 2, i = 0..n. При u = 0 следует: r(0) = N₄₂(0)(r₁ - r₀). Из этого следует, что если r₀, r₁, .., r_n — вершины некоторой замкнутой ломанной, то кривая, построенная на основе B-сплайна, начинается в r₀ и ее касательная в этой точке имеет направление (r₁ - r₀). Аналогичное утверждение верно и для другого конца. Главное преимущество этого сплайна заключается в том, что изменение одной из вершин влечет за собой изменение только четырех отрезков кривой. Далее, мы также можем построить кривую, аппроксимирующую ломанную с любым желаемым числом сторон. Отрезок сплайна всегда лежит в выпуклой оболочке:

Важным следствием этой выпуклой оболочки является вырождение ее в прямую линию, если 4 последовательные вершины ломанной коллинеарны, значит соответствующий сегмент кривой должен быть прямолинейным.

Имеется еще 2 полезных факта:

• кривая проходит вблизи средней точки каждой стороны, за исключением 1-ой и последней точками;
• при k = 2, ..., n - 2 кривая проходит через точки: 1/6r_k-1 + 2/3r_k + 1/6r_k+1 = 2/3r_k + 1/3(1/2(r_k-1 + r_k+1))

Эти точки, как показано на рис. 20.3, лежат на 1/3 расстояния от r_k на прямой, соединяющей r_k с серединой отрезка между r_k-1 и r_k+1.