Взаимосвязь кубического сплайна и кривой Безье...

[knkd]

Взаимосвязь кубического сплайна и кривой Безье... третьего порядка.

Кто-нибудь мог бы объяснить популярно взаимосвязь между этими кривыми?
По сути ведь, кривая Безье является кубическим сплайном, с необычным способом задания.

Идея в том, что с помощью Cairo, хочется рисовать плавные кривые.
Но кривые в нём задаются в виде опорных точек кривых Безье, а исходные данные для рисования - в виде точек через которые должна пройти кривая.
Аппроксимация точек кубическими сплайнами, задача тривиальная, но вот в плане перехода после этого к кривым Безье, как раз и заминка.

[profrotter]

Кривая Безье является параметрической кривой, рассматривается как совокупность своих элементарных фрагментов. Фрагмент кривой Безье порядка $n$ описывается выражением:

$$\overrightarrow{r}_{i}(t)=\sum\limits_{k=0}^nB_{k}^n(t)\overrightarrow{P}_k^{(i)}$$

где $\overrightarrow{r}_{i}(t)$ - радиус-вектор точек фрагмента, $B_{k}^n(t)$ - многочлен Бернштейна; $\overrightarrow{P}_k$ - опорные векторы; $t\in\left[0,1\right]$ - параметр.
В случае кривой третьего порядка

$$\overrightarrow{r}_{i}(t)=(((1-t)\overrightarrow{P}_0^{(i)}+3t\overrightarrow{P}_1^{(i)})(1-t)+3t^2\overrightarrow{P}_2^{(i)})(1-t)+t^3\overrightarrow{P}_3^{(i)}$$

Элементраный фрагмент кривой Безье третьего порядка определяется четырмя опорными векторами. При заданной совокупности опорных векторов $\overrightarrow{P}_n,n=0,...,N-1$ кривая Безье формируется так, что первый фрагмент строится на векторах $\overrightarrow{P}_0, \overrightarrow{P}_1, \overrightarrow{P}_2, \overrightarrow{P}_3$, то есть:

$\overrightarrow{P}_0^{(0)}=\overrightarrow{P}_0$,
$\overrightarrow{P}_1^{(0)}=\overrightarrow{P}_1$,
$\overrightarrow{P}_2^{(0)}=\overrightarrow{P}_2$,
$\overrightarrow{P}_3^{(0)}=\overrightarrow{P}_3$.

Следующий фрагмент на $\overrightarrow{P}_3, \overrightarrow{P}_4, \overrightarrow{P}_5, \overrightarrow{P}_6$, то есть

$\overrightarrow{P}_0^{(1)}=\overrightarrow{P}_3$,
$\overrightarrow{P}_1^{(1)}=\overrightarrow{P}_4$,
$\overrightarrow{P}_2^{(1)}=\overrightarrow{P}_5$,
$\overrightarrow{P}_3^{(1)}=\overrightarrow{P}_6$.

И тд.
Кривая Безье является непрерывной, однако её гладкость зависит от расположения опорных векторов:
1. Кривая имеет непрерывную касательную ($G^1$ - гладкая), если вершины векторов $\overrightarrow{P}_{3n-1}, \overrightarrow{P}_{3n}, \overrightarrow{P}_{3n+1}$ лежат на одной прямой.
2. Кривая имеет непрерывный вектор кривизны ,($G^2$ - гладкая) если вершины векторов $\overrightarrow{P}_{3n-2}, \overrightarrow{P}_{3n-1}, \overrightarrow{P}_{3n}, \overrightarrow{P}_{3n+1}, \overrightarrow{P}_{3n+2}$ лежат в одной плоскости.

Кривая Безье, таким образом, может являться сплайн-кривой только при определённом расположении вершин опорных векторов.

При построении кубической сплайн-кривой каждый её фрагмент также строится на 4-х опорных векторах, но формирование кривой соверешенно иное:
первый фрагмент строится на векторах $\overrightarrow{P}_0, \overrightarrow{P}_1, \overrightarrow{P}_2, \overrightarrow{P}_3$, то есть:

$\overrightarrow{P}_0^{(0)}=\overrightarrow{P}_0$,
$\overrightarrow{P}_1^{(0)}=\overrightarrow{P}_1$,
$\overrightarrow{P}_2^{(0)}=\overrightarrow{P}_2$,
$\overrightarrow{P}_3^{(0)}=\overrightarrow{P}_3$.

Следующий фрагмент на $\overrightarrow{P}_1, \overrightarrow{P}_2, \overrightarrow{P}_3, \overrightarrow{P}_4$, то есть:

$\overrightarrow{P}_0^{(1)}=\overrightarrow{P}_1$,
$\overrightarrow{P}_1^{(1)}=\overrightarrow{P}_2$,
$\overrightarrow{P}_2^{(1)}=\overrightarrow{P}_3$,
$\overrightarrow{P}_3^{(1)}=\overrightarrow{P}_4$.

И тд.
В случае кубической сплайн-кривой независимо от расположения опорных векторов обеспечивается $C^2$ - гладкость.
Существует метод преобразования опорных векторов кубической сплайн-кривой в набор опорных векторов для кривой Безье, обеспечивающий их совпадение. Подробнее см. Шикин Е.В., Плис А.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. - М.: ДИАЛОГ-МИФИ, 1996.

Для определения опорных векторов по заданным точкам, через которые должна проходить кривая Безье, предлагаю следующее. Обозначим $\overrightarrow{r}_m, m=0,...,M-1$ - радиус-векторы исходных точек. Первый элементарный фрагмент кривой Безье будет проходить через вершины $\overrightarrow{r}_0,\overrightarrow{r}_1,\overrightarrow{r}_2,\overrightarrow{r}_3$. Потребуем, чтобы первый вектор соответствовал значению параметра $t=0$, второй вектор $t=\frac 1 3$, третий $t=\frac 2 3$, четвёртый $t=1$:

$\overrightarrow{r}_{0}(0)=$\overrightarrow{r}_0
$\overrightarrow{r}_{0}(\frac 1 3)=$\overrightarrow{r}_1
$\overrightarrow{r}_{0}(\frac 2 3)=$\overrightarrow{r}_2
$\overrightarrow{r}_{0}(1)=$\overrightarrow{r}_3

Причём, с учётом общих свойств кривых Безье, $\overrightarrow{P}_0^{(0)}=\overrightarrow{r}_0$ и $\overrightarrow{P}_3^{(0)}=\overrightarrow{r}_3$.
Решая записанную систему линейных уравнений получим опорные векторы $\overrightarrow{P}_0^{(0)}, \overrightarrow{P}_1^{(0)}, \overrightarrow{P}_2^{(0)}, \overrightarrow{P}_3^{(0)}$.
Опорные векторы следующего элементарного фрагмента $\overrightarrow{P}_0^{(1)}, \overrightarrow{P}_1^{(1)}, \overrightarrow{P}_2^{(1)}, \overrightarrow{P}_3^{(1)}$ определяются из аналогичной системы уравнений:

$\overrightarrow{r}_{1}(0)=$\overrightarrow{r}_3
$\overrightarrow{r}_{1}(\frac 1 3)=$\overrightarrow{r}_4
$\overrightarrow{r}_{1}(\frac 2 3)=$\overrightarrow{r}_5
$\overrightarrow{r}_{1}(1)=$\overrightarrow{r}_6,

причём $\overrightarrow{P}_0^{(1)} = \overrightarrow{P}_3^{(0)}=\overrightarrow{r}_3$ и $\overrightarrow{P}_3^{(1)}=\overrightarrow{r}_6$
и тд.

[Алексей К.]

knkd в сообщении #404021 писал(а):

Взаимосвязь кубического сплайна и кривой Безье... третьего порядка.

Кто-нибудь мог бы объяснить популярно взаимосвязь между этими кривыми?

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

$$x(t)=a_0+a_1t+a_2t^2+a_3t^3,\quad y(t)=b_0+b_1t+b_2t^2+b_3t^3.$$

Эти два способа задания кривой эквивалентны, от одного можно перейти к другому, более удобному в конкретном контексте.

Цитата:

Аппроксимация точек кубическими сплайнами, задача тривиальная, но вот в плане перехода после этого к кривым Безье, как раз и заминка.

А это ещё тривиальнее: на каждой дуге сплайна (я не добавляю этой индексации) Вам надо перейти от

$$x(t)=a_0+a_1t+a_2t^2+a_3t^3\quad\text{к}\quad x(t)=x_0(1-t)^3+3x_1(1-t)^2t+3x_2(1-t)t^2+x_3t^3,$$

и аналогично для $y$. Что довольно легко: распишите вторую правую часть и приравняйте к первой, т.е. приравняйте коэффициенты при одинаковых степенях $t$. Найденные $(x_1,y_1)$ и $(x_2,y_2)$ будут Вашими новыми контрольными точками на данном куске сплайна.

Если, конечно, я Вас правильно понял. Уж больно смущает эта странная фраза:

Цитата:

По сути ведь, кривая Безье является кубическим сплайном, с необычным способом задания.

[ewert]

Кривая Безье -- это не сплайн. Во-первых, это лишь кусочек сплайна. Во-вторых, сплайн в обычном понимании -- это скалярная функция, а кривая Безье задаётся векторной.

[knkd]

ewert в сообщении #416646 писал(а):

Кривая Безье -- это не сплайн. Во-первых, это лишь кусочек сплайна.

Я неудачно выразился.

В общем задача решена, всем спасибо за помощь.