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 \left\langle u_{i},u_{i+1}\right\rangle$,

$N_{i}^{0}\left(u\right)=0$, pro $u\not \in \left\langle u_{i},u_{i+1}\right\rangle$,

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

$U=\left(u_{0},u_{1},\dots ,u_{k},u_{k+1},\dots ,u_{m-k},\dots ,u_{m}\right)$,

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\leq i\leq 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=\left(u_{0},u_{1},\dots ,u_{m}\right)$,

kde

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

Nezáporná hodnota

$N_{i}^{k}\left(u\right)\geq 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 \left\langle u_{0},u_{m}\right\rangle$

Lokální vlastnost

$N_{i}^{k}\left(u\right)\neq 0$ pro $u\in \left\langle u_{i},u_{i+k+1}\right\rangle$

Okrajový uzlový vektor

Pro uzlový vektor $(\underbrace {u_{0},\dots ,u_{0}} _{k+1},\underbrace {u_{m},\dots ,u_{m}} _{k+1})$, tzv. okrajový uzlový vektor, platí:

$N_{i}^{k}\left(u\right)=B_{i}^{k}\left(u\right)={k \choose i}\cdot u_{i}\cdot {\left(1-u\right)}_{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'\left(u_{0}\right)={\frac {k\cdot \left(P_{1}-P_{0}\right)}{u_{k+1}}}$, $P'\left(u_{m}\right)={\frac {k\cdot \left(P_{n}-P_{n-1}\right)}{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 \left\langle u_{i},u_{i+1}\right\rangle ,k\leq i\leq 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 \left\langle u_{i},u_{i+k+1}\right\rangle$ 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 $\left\langle u_{i},u_{i+k+1}\right\rangle$. 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 \left\langle u_{i},u_{i+k+1}\right\rangle$. 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

void ComputeKnotVector(int n, int k)
 {
  parametrization = new ParameterCollection();
  for(int i=0; i<=n+k+1; i++)
  {
   if(i<=k) parametrization.Insert(i,0);
   else
    if(i>n) parametrization.Insert(i,n-k+1);
   else
    parametrization.Insert(i,i-k);
  }
 }

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

private double BasisFunction(int k, int i, ParameterCollection u, double t)
 {
  if(k==0)
  {
   if((u[i]<=t) && (t<=u[i+1]))
    return 1;
   else
    return 0;
  }
  else
  {
   double memb1, memb2;
   if(u[i+k]==u[i])
    memb1 = 0;
   else
    memb1 = ((t-u[i])/(u[i+k]-u[i]))*BasisFunction(k-1, i, u, t);
   if(u[i+k+1]==u[i+1])
    memb2 = 0;
   else
    memb2 = ((u[i+k+1]-t)/(u[i+k+1]-u[i+1]))*BasisFunction(k-1, i+1, u, t);
   return memb1+memb2;
  }
 }

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

public override Vector GetPoint(double t)
 {
  Vector ret = new Vector();
  for (int i = 0;i<ctrlPoly.Count;i++)
  {
   ret+=BasisFunction(Degree,i, parametrization,t)*((RichPoint)ctrlPoly[i]).Locate;
  }
  return ret;
 }