Geometrie/B–spline křivka

Z Wikiknih
Skočit na navigaci Skočit na vyhledávání

B-spline křivky[editovat]

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ě je určena rovnicí:

,

kde

jsou polohové vektory vrcholů řídícího polygonu (de Boor body),
jsou normalizované bázové funkce stupně (někdy se nazývají de Boor funkce).

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

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

Rekurentní vztah:

,

kde

, pro ,
, pro ,

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

,

kde

.

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

a .

Pokud pro dva sousední parametry platí:

pro ,

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 platit:

,

kde

.

Nezáporná hodnota

pro všechny hodnoty .

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

Jednotkový součet

pro

Lokální vlastnost

pro

Okrajový uzlový vektor

Pro uzlový vektor , tzv. okrajový uzlový vektor, platí:

.

Geometrické vlastnosti B-spline křivek[editovat]

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[editovat]

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:

,
, .

Konvexní obal

Všechny body B-spline křivky leží v konvexním obalu množiny, která je určena de Boor body Přesněji řečeno, oblouk křivky pro leží v konvexním obalu vrcholů .

De Boor algoritmus[editovat]

Viz Algoritmus de Boor

Volba stupně B-spline křivky[editovat]

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 platí:

pro dostáváme pouze body řídícího polygonu,
pro 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 dostaneme křivku stejného tvaru jako Bézierova křivka pro daný polygon.

Význam uzlového vektoru[editovat]

Výsledná křivka je pro polynomem stupně . Má tedy na tomto intervalu spojité všechny derivace. V uzlech 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[editovat]

Lokální vlastnost je zajištěna tím, že bázové funkce nabývají nenulových hodnot jen na intervalu . To znamená, že změníme-li polohu jednoho de Boor bodu , pak se změní pouze ta část B-spline křivky, pro kterou . Tato změna ovlivní 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 dojde ke změně celé křivky.

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

Mějme dánu kubickou B-spline křivku de Boor polygonem . Pak pomocí podmínek spojitosti lze velice jednoduše z daných de Boor bodů určit Bézierovy body .

Vícenásobné body[editovat]

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

Invariance[editovat]

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[editovat]

ComputeKnotVector(int n, int k)[editovat]

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)[editovat]

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)[editovat]

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;
 }