Geometrie/B–spline křivka

B-spline křivky

B-spline křivky poprvé zavádí N. Lobachevský již v 19. století. V roce 1946 I. J. Schoenberg použil B-spline pro vyhlazování statistických dat a dává tím základy pro moderní teorii spline aproximací. M. Cox a C. de Boor objevili nezávisle na sobě v roce 1972 rekurentní vztah pro výpočet B-spline. Tato teorie byla poté použita pro výpočet parametrických B-spline křivek.

Obecná B-spline křivka stupně $k$ je určena rovnicí:

$P(u)=\sum _{i=0}^n{P}_i\cdot N_i^k(u)$,

kde

$P_i$ jsou polohové vektory vrcholů řídícího polygonu (de Boor body),

$N_i^k(u)$ jsou normalizované bázové funkce stupně $k$ (někdy se nazývají de Boor funkce).

Analytické vlastnosti de Boor bázových funkcí

Pro de Boor bázové funkce platí tyto analytické vlastnosti ([PIE 85]; [HOS 89]):

Rekurentní vztah:

$N_i^k\left(u\right)=\frac{u-u_i}{u_{i+k}-u_i}\cdot N_i^{k-1}\left(u\right)+\frac{u_{i+k+1}-u}{u_{i+k+1}-u_{i+1}}\cdot N_{i+1}^{k-1}\left(u\right)$,

kde

$N_i^0\left(u\right)=1$, pro $u\in ⟨u_i,u_{i+1}⟩$,

$N_i^0\left(u\right)=0$, pro $u\in ̸⟨u_i,u_{i+1}⟩$,

Hodnoty parametrů $u_j$ se obvykle nazývají uzly. Pak hovoříme o tzv. uzlovém vektoru parametrů:

$U=(u_0,u_1,\dots ,u_k,u_{k+1},\dots ,u_{m-k},\dots ,u_m)$,

kde

$u_i<u_{i+1},m=n+k+1$.

Uzlový vektor se nazývá neperiodický (neuniformní), jestliže platí:

$u_0=\dots =u_k$ a $u_{m-k}=\dots =u_m$.

Pokud pro dva sousední parametry platí:

$u_{i+1}-u_i=konst.$ pro $k\le i\le m-k-1$,

pak hovoříme o uniformní parametrizaci. Pokud nebude řečeno jinak, budeme dále uvažovat neperiodickou (neuniformní) parametrizaci.

Pro uzavřenou B-spline křivku bude pro uzlový vektor $U$ platit:

$U=(u_0,u_1,\dots ,u_m)$,

kde

$u_i<u_{i+1},m=n$.

Nezáporná hodnota

$N_i^k\left(u\right)\ge 0$ pro všechny hodnoty $i,k,u$.

(Nerovnost lze dokázat matematickou indukcí z uvedeného rekurentního vztahu.)

Jednotkový součet

$\sum _{i=0}^n{N}_i^k\left(u\right)=1$ pro $u\in ⟨u_0,u_m⟩$

Lokální vlastnost

$N_i^k\left(u\right)\ne 0$ pro $u\in ⟨u_i,u_{i+k+1}⟩$

Okrajový uzlový vektor

Pro uzlový vektor $(\underset{k+1}{\underbrace{u_0,\dots ,u_0}},\underset{k+1}{\underbrace{u_m,\dots ,u_m}})$, tzv. okrajový uzlový vektor, platí:

$N_i^k\left(u\right)=B_i^k\left(u\right)=(\genfrac{}{}{0ex}{}{k}{i})\cdot u_i\cdot {(1-u)}_{k-i}$.

Geometrické vlastnosti B-spline křivek

Z definice B-spline křivky a z analytických vlastností bázových funkcí vyplývají tyto základní geometrické vlastnosti B-spline křivek ([BÖH 77]; [COH 77]; [PIE 85]; [HOS 89]):

Koncové podmínky

Pro neperiodický uzlový vektor platí, že B-spline křivka prochází počátečním a koncovým vrcholem řídícího polygonu a dotýká se počáteční a koncové hrany řídícího polygonu:

$P\left(u_0\right)=P_0$, $P\left(u_m\right)=P_n$

$P^{\prime }\left(u_0\right)=\frac{k\cdot (P_1-P_0)}{u_{k+1}}$, $P^{\prime }\left(u_m\right)=\frac{k\cdot (P_n-P_{n-1})}{1-u_{m-k-1}}$.

Konvexní obal

Všechny body B-spline křivky leží v konvexním obalu množiny, která je určena de Boor body $P_0,\dots ,P_n$ Přesněji řečeno, oblouk křivky $P\left(u\right)$ pro $u\in ⟨u_i,u_{i+1}⟩,k\le i\le m-k-1$ leží v konvexním obalu vrcholů $P_{i-k},\dots ,P_i$.

De Boor algoritmus

Viz [[../Algoritmus de Boor/]]

Volba stupně B-spline křivky

Stupeň Bézierovy křivky je pevně určen počtem vrcholů řídícího polygonu, zatímco obecná B-spline křivka umožňuje volbu stupně výsledné křivky. Na obrázku je zobrazeno několik B-spline křivek, které jsou určeny stejným řídícím polygonem.

Je zvolena uniformní neperiodická parametrizace a pro $k=0,\dots ,n$ platí:

pro $k=0$ dostáváme pouze body řídícího polygonu,

pro $k=1$ dostáváme právě řídící polygon,

pro zvyšující se stupeň se B-spline křivka vzdaluje od řídícího polygonu,

pro $k=n$ dostaneme křivku stejného tvaru jako Bézierova křivka pro daný polygon.

Význam uzlového vektoru

Výsledná křivka je pro $u\in ⟨u_i,u_{i+k+1}⟩$ polynomem stupně $k$. Má tedy na tomto intervalu spojité všechny derivace. V uzlech $u_i$ se mění reprezentace B-spline křivky -– vystupuje z ní jeden bázový spline a vstupuje jiný; uzly tedy působí jako "přepínač".

Lokální změna tvaru

Lokální vlastnost je zajištěna tím, že bázové funkce $N_i^k\left(u\right)$ nabývají nenulových hodnot jen na intervalu $⟨u_i,u_{i+k+1}⟩$. To znamená, že změníme-li polohu jednoho de Boor bodu $P_i$, pak se změní pouze ta část B-spline křivky, pro kterou $u\in ⟨u_i,u_{i+k+1}⟩$. Tato změna ovlivní $k+1$ segmentů křivky. Čím je tedy stupeň B-spline křivky vyšší, tím se změní při změně jednoho bodu řídícího polygonu větší část křivky, přičemž pro $k=n$ dojde ke změně celé křivky.

Výpočet Bézierových bodů z de Boor polygonu

Mějme dánu kubickou B-spline křivku de Boor polygonem $D_0,\dots ,D_m$. Pak pomocí podmínek $C^2$ spojitosti lze velice jednoduše z daných de Boor bodů určit Bézierovy body $P_0,\dots ,P_n$.

Vícenásobné body

Tvar B-spline křivky ovlivňují tzv. vícenásobné body řídícího polygonu.

Invariance

Mezi důležité vlastnosti B-spline křivek patří invariance vůči otáčení, posunutí a změně měřítka. Afinní transformaci křivky pak můžeme provést tak, že této transformaci podrobíme vrcholy řídícího polygonu a k nim pak sestrojíme novou křivku.

Algoritmizace

ComputeKnotVector(int n, int k)

Spočítá uzlový vektor.

Parametry:

• n - počet kontrolních bodů mínus 1
• k - stupeň de Boor bázové funkce

BasisFunction(int k, int i, ParameterCollection u, double t)

Spočítá a vrátí hodnotu normalizované bázové funkce stupně k.

Parametry:

• k - stupeň de Boor bázové funkce
• i - index polohového vektoru vrcholu řídícího polygonu
• u - uzlový vektor
• t - parametr

Vector GetPoint(double t)

Přetížená metoda třídy Curve. Spočítá a vrátí bod na křivce.

Parametry:

• t - parametr výpočtu