RU: B-Spline

Геометрические примитивы

B-сплайн

B-сплайном называют тип кривой, широко используемый в машинной графике благодаря совокупности замечательных свойств. Кривая Безье является частным случаем B-сплайна. Обсудим вначале недостатки кривой Безье. Запишем ее параметрическое уравнене в виде ${\bf r}(t)=\sum_{i=0}^n c_i(t){\bf r}_i$, где коэффициенты $c_i(t)$ есть многочлены Бернштейна $B_i^{(n)}(t)$ степени $n$. Степень многочленов однозначно связана с числом опорных точек: по трем точкам мы строим кривую второго порядка, по четырем кривую третьего порядка и т.д. При добавлении новой точки все построение нужно проводить заново. Кроме того, поскольку коэффициенты отличны от нуля на всем интервале $0 < t < 1$, изменение положения одной из опорных точек влияет на форму всей кривой, а не только на область, близкую к этой точке.

В соответствии с этими замечаниями, было бы желательным построить систему функций $c_i(t)$ со следующими свойствами:

• функции непрерывны вместе со своими производными до некоторого порядка;
• каждая функции отлична от нуля только в некоторой области изменения параметра;
• функции неотрицательны: $c_i(t)\geq 0$;
• сумма функций равна единице: $\sum c_i(t) = 1$.

Такие свойства коэффициентов $c_i(t)$ обеспечивают B-сплайны.

Построение B-сплайнов

Пусть в области изменения параметра $t$ введена сетка узлов $t_i$. Будем искать функции $c_i(t)$ с указанными выше свойствами в виде сплайнов, т.е. в виде многочленов на каждом из интервалов сетки параметра. Начнем с построения системы непрерывных функций, не требуя непрерывности производных. В качестве таких функций естественно взять систему вида (B-сплайн первой степени):

(1)

\begin{align} N_i^{(1)}(t) = \left\{ \begin{aligned} \dfrac{t-t_i}{t_{i+1}-t_i} \qquad &\text{при} \qquad t_i \le t \le t_{i+1} \\ \dfrac{t_{i+2}-t}{t_{i+2}-t_{i+1}} \qquad &\text{при} \qquad t_{i+1} \le t \le t_{i+2} \\ 0 \qquad &\text{иначе} \end{aligned} \right. \end{align}

B-сплайн первой степени $N_i^{(1)}(t)$ отличен от нуля только на интервале $[t_i,t_{i+2}]$ (см. рисунок). Обратим внимание на то, что выполнено условие нормировки: при $t_i \leq t \leq t_{i+1}$ имеет место равенство $N_{i-1}^{(1)}(t)+ N_{i}^{(1)}(t)= 1$, а все остальные B-сплайны $N_j^{(1)}(t)$, $j\neq i-1, i$ на этом интервале равны нулю. Производная сплайна первой степени кусочно постоянна.

Если использовать B-сплайны $N_i^{(1)}(t)$ в качестве коэффициентов аппроксимационной кривой, мы получим линейную интерполяцию, при которой точки кривой соединяются отрезками.(2)

\begin{align} \mathbf{r}^{(1)}(t) = N_{i-1}^{(1)}(t)\mathbf{r}_{i-1}+ N_{i}^{(1)}(t)\mathbf{r}_{i} \end{align}

Построим теперь систему непрерывных функций, имеющих непрерывную первую производную и отличных от нуля только на конечных интервалах. Пусть функция $N_i^{(2)}(t)$ (сплайн второй степени) тождественно равна нулю при $t<t_i$. В силу указанных свойств, при $t=t_i$ значения функции и производной должны обращаться в нуль.

Определим ее кроме того таким образом, чтобы значение и первая производная обращались в нуль при $t=t_{i+3}$ (в этом случае функцию $N_i^{(2)}(t)$ можно положить тождественно равной нулю при $t>t_{i+3}$). Определим ее кроме того таким образом, чтобы значение и первая производная обращались в нуль при $t=t_{i+3}$ (в этом случае функцию $N_i^{(2)}(t)$ можно положить тождественно равной нулю при $t>t_{i+3}$)

Условия равенства нулю при $t<t_i$ и $t>t_{i+3}$ мы обеспечим, если положим

(3)

\begin{align} N_i^{(2)}(t) = \frac{t-t_i}{t_{i+2}-t_i}N_i^{(1)}(t)+\frac{t_{i+3}-t}{t_{i+3}-t_{i+1}}N_{i+1}^{(1)}(t) \end{align}

При $t_i \leq t \leq t_{i+1}$ имеет место равенство: $N_{i-2}^{(2)}(t)+ N_{i-1}^{(2)}(t)+N_{i}^{(2)}(t)= 1$, а все остальные сплайны $N_j^{(2)}(t)$, $j\neq i-2, i-1, i$ на этом отрезке равны нулю. Производная сплайна второй степени кусочно линейна.

Сглаживающая кривая (B-кривая), построенная с помощью B-сплайнов второй степени на сетке $t_i$ параметра $t$ по опорным точкам $\mathbf{r}_i$ имеет следующий вид: если $t_i \leq t \leq t_{i+1}$, то

(4)

\begin{align} \mathbf{r}(t) = N_{i-2}^{(2)}(t)\mathbf{r}_{i-2}+ N_{i-1}^{(2)}(t)\mathbf{r}_{i-1}+N_{i}^{(2)}(t)\mathbf{r}_{i} \end{align}

так что для построения B-кривой на интервале $t_i \leq t \leq t_{i+1}$ нужно задать значения опорных точек $\mathbf{r}_{i-2}$, $\mathbf{r}_{i-1}$, $\mathbf{r}_{i}$ и значения узлов сетки параметра $t_{i-2}$, $t_{i-1}$, $t_{i}$, $t_{i+1}$, $t_{i+2}$, $t_{i+3}$ (обращаем внимание, что узлов сетки на 3 больше, чем число опорных точек).

Отметим, что B-кривая, в отличие от кривой Безье, не проходит, вообще говоря, через крайние опорные точки.

В общем случае B-сплайны $N_i^{(n)}(t)$ определяются следующим образом. Пусть на оси $t$ задана сетка $\{t_k\}$. Cплайн $N_i^{(0)}(t)$ нулевой степени отличен от нуля только на интервале $[t_i,t_{i+1})$ и равен на нем единице:

(5)

\begin{align} N_i^{(0)}(t) = \left\{ \begin{aligned} 1 \qquad &\text{при} \qquad t_i \le t < t_{i+1} \\ 0 \qquad &\text{иначе} \end{aligned} \right. \end{align}

B-сплайн $N_i^{(1)}(t)$ первой степени отличен от нуля только на интервале $[t_i,t_{i+2})$ и вычисляется через сплайны нулевой степени:

(6)

\begin{align} N_i^{(1)}(t) = \frac{t-t_i}{t_{i+1}-t_i}N_i^{(0)}(t)+\frac{t_{i+2}-t}{t_{i+2}-t_{i+1}}N_{i+1}^{(0)}(t) \end{align}

так что

(7)

\begin{align} N_i^{(1)}(t) = \left\{ \begin{aligned} (t-t_i)/(t_{i+1}-t_i) \qquad &\text{при} \qquad t_i \le t \le t_{i+1} \\ (t_{i+2}-t)/(t_{i+2}-t_{i+1}) \qquad &\text{при} \qquad t_{i+1} \le t < t_{i+2} \\ 0 \qquad &\text{иначе} \end{aligned} \right. \end{align}

B-сплайн $n$-ой степени $N_i^{(n)}(t)$ отличен от нуля только на $n+1$ интервалах сетки $t_i \le t < t_{i+n+1}$ и вычисляется через сплайны $n-1$-ой степени:

(8)

\begin{align} N_i^{(n)}(t) = \frac{t-t_i}{t_{i+n}-t_i}N_i^{(n-1)}(t)+\frac{t_{i+n+1}-t}{t_{i+n+1}-t_{i+1}}N_{i+1}^{(n-1)}(t) \end{align}

Если знаменатель слагаемого обращается в нуль, то само слагаемое нужно считать равным нулю.

Если определены B-сплайны $N_0^{(n)}(t), N_1^{(n)}(t), N_2^{(n)}(t), \dots, N_M^{(n)}(t)$, то первый из них $N_0^{(n)}(t)$ отличен от нуля при $t_0 \le t \le t_{n+1}$, второй $N_1^{(n)}(t)$ отличен от нуля при $t_1 \le t \le t_{n+2}$, и т.д., $N_M^{(n)}(t)$ отличен от нуля при $t_M \le t \le t_{M+n+1}$. На интервале $[t_i,t_{i+1}]$ отличны от нуля сплайны $n$-ой степени с номерами $i-n, i-n+1, \dots, i-1, i$, т.е. всего $n+1$ сплайнов. Сумма их равна единице.

Таким образом, если заданы $M+1$ сплайнов от $N_0^{(n)}(t)$ до $N_M^{(n)}(t)$, то сетка имеет $n+M+2$ узлов от $t_0$ до $t_{n+M+1}$ (см. рисунок), причем интервалы $[t_n,t_{n+1}], [t_{n+1},t_{n+2}],$ $\dots, [t_{M},t_{M+1}]$ являются полными, в том смысле, что на каждом их них определены $n+1$ сплайнов, и выполнено условие нормировки.

$M$ B-сплайнов $n$-ой степени образуют полную систему на интервале $[t_n,t_{M+1}]$.

B-кривая

Сглаживающая кривая, построенная с помощью B-сплайнов $n$-ой степени по опорным точкам $\{\mathbf{r}_i\}$, $0 \leq i \leq M$ на сетке $\{t_i\}$, $0 \leq i \leq n+M+1$ (еще раз обращаем внимание на то, что число узлов сетки на $n+1$ больше, чем число опорных точек) имеет вид: $\mathbf{r}^{(n)}(t) = \sum_{i=0}^M N_{i}^{(n)}(t)\mathbf{r}_{i}$, где параметр $t$ лежит в диапазоне $t_n \leq t \leq t_{M+1}$.

В отличие от кривой Безье, значение B-кривой зависит не от всех опорных точек, а только от $n+1$ "ближайших". Точнее, если значение параметра лежит в интервале $t_i \leq t < t_{i+1}$, то $\mathbf{r}^{(n)}(t) = \sum_{j=i-n}^i N_{j}^{(n)}(t)\mathbf{r}_{j}$, так что для построения B-кривой на интервале $t_i \leq t \leq t_{i+1}$ нужно задать значения опорных точек $\mathbf{r}_{i-n}$, $\mathbf{r}_{i-n+1}, \ldots$ $\mathbf{r}_{i}$ и значения узлов сетки параметра $t_{i-n}$, $t_{i-n+1}, \ldots$ $t_{i}$, $t_{i+1}$, $t_{i+2}, \ldots$, $t_{i+n+1}$.

Пусть заданы $M+1$ опорных точек и столько же положительных чисел $w_i$ — весовых коэффициентов. Рациональной B-кривой $n$-ой степени или NURBS (NonUniform Rational B-Spline) называется кривая вида

(9)

\begin{align} \label{eq_BSpline11} {\bf r}^{(n)}(t)=\frac{\sum_{i=0}^{M}w_{i}N_i^{(n)}(t){\bf r}_i} {\sum_{i=0}^{M}w_{i}N_i^{(n)}(t)} \end{align}

Рациональная кривая есть отношение двух обычных B-кривых: числитель строится по опорным точкам $w_i\mathbf{r}_i$, а знаменатель по весовым коэффициентам $w_i$. В случае одинаковых весовых коэффициентов NURBS превращается в обычную B-кривую. Весовые коэффициенты дают дополнительные степени свободы для изменения поведения кривой: увеличивая вес $w_i$ вы приближаете кривую к опорной точке $\mathbf{r}_i$.

Граничные узлы

Выше мы видели, что на первых $n$ интервалах сетки $t_0\leq t \leq t_n$ и на последних $n$ интервалах $t_{M+1}\leq t \leq t_{M+n+1}$ система B-сплайнов $N_0^{(n)}(t), N_1^{(n)}(t), N_2^{(n)}(t), \dots, N_M^{(n)}(t)$ не полна, т.е. для ее не выполнено условие $\sum_{i=0}^M N_i^{(n)}(t)=1$. В связи с этим возможны следующие варианты действий:

• не использовать значения параметра из указанных интервалов, т.е. ограничиться интервалом $t_n \leq t \leq t_{M+1}$ значений аргумента;
• доопределить поведение B-сплайнов, что возможно, например, в случае замкнутой кривой;
• сжать указанные интервалы до нулевой длины.

Обсудим подробнее эти варианты.

Если строится замкнутая кривая, то можно наложить условия периодичности, сопоставляя узлу $t_0$ узел $t_{M+1}$, узлу $t_1$ узел $t_{M+2}$ и так далее, узлу $t_n$ узел $t_{M+n+1}$. Другими словами, введем период $T=t_{M+1}-t_0$ и потребуем соответствие узлов: $t{i+M+1}=t_i + T$ и равенство опорных точек $\mathbf{r}_{i+M+1}=\mathbf{r}_i$. В этом случае можно ограничиться диапазоном изменения параметра $t_0\leq t \leq t_{M+1}$ и представлением B-кривой в виде $\mathbf{r}^{(n)}(t) = \sum_{j=i-n}^i N_{j}^{(n)}(t)\mathbf{r}_{j}$ для значений аргумента, принадлежащих отрезку $t\in [t_i, t_{i+1}]$, причем для отрицательных значений индекса $j$ использовать условие периодичности $N_{j}^{(n)}(t)=N_{j+M+1}^{(n)}(t+T)$.

Другой подход состоит в "склеивании" граничных узлов, т.е. в использовании неравномерной сетки, для которой выполнены условия $t_0=t_1=\ldots=t_n$ и $t_{M+1}=t_{M+2}=\ldots=t_{M+n+1}$. В этом случае диапазон изменения параметра $t_0=t_n \leq t \leq t_{M+1}=t_{M+n+1}$ охватывает всю сетку узлов. Совпадение граничных узлов приводит к тому, что B-кривая проходит через первую $\mathbf{r}_0$ и последнюю $\mathbf{r}_{M}$ опорные точки.