Geometrie/B–spline křivka

Z Wikiknih

Obsah

1 B-spline křivky

[editovat] B-spline křivky

B-spline křivky poprvé zavádí N. Lobanovský 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^n_{i=0}P_i\cdot N^k_i(u)$ ,

kde

P i

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

$N^k_i(u)$ jsou normalizované bázové funkce stupně

k

(někdy se nazývají de Boor funkce).

[editovat] 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^k_i\left(u\right)=\frac{u-u_i}{u_{i+k}-u_i}\cdot N^{k-1}_i\left(u\right)+\frac{u_{i+k+1}-u}{u_{i+k+1}-u_{i+1}}\cdot N^{k-1}_{i+1}\left(u\right)$ ,

kde

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

$N^0_i\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 = k o n s t .

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=\left(u_0,u_1,\dots,u_m\right)$ ,

kde

u i < u i + 1, m = n

.

Nezáporná hodnota

$N^k_i\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^n_{i=0}N^k_i\left(u\right)=1$ pro $u\in\left\langle u_0,u_m\right\rangle$

Lokální vlastnost

$N^k_i\left(u\right)\ne 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},$	$\underbrace{u_m,\dots,u_m})$
$k + 1$	$k + 1$

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

$N^k_i\left(u\right)=B^k_i\left(u\right)={k\choose i}\cdot u_i\cdot{\left(1-u\right)}_{k-i}$ .

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

[editovat] 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\le i\le m-k-1$ leží v konvexním obalu vrcholů $P_{i-k},\dots,P_i$ .

[editovat] De Boor algoritmus

Viz Algoritmus de Boor

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

[editovat] 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č".

[editovat] Lokální změna tvaru

Lokální vlastnost je zajištěna tím, že bázové funkce $N^k_i\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.

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

[editovat] Vícenásobné body

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

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

[editovat] Algoritmizace

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

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

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

Geometrie/B–spline křivka

Z Wikiknih

Obsah

[editovat] B-spline křivky

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

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

[editovat] Koncové podmínky

[editovat] De Boor algoritmus

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

[editovat] Význam uzlového vektoru

[editovat] Lokální změna tvaru

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

[editovat] Vícenásobné body

[editovat] Invariance

[editovat] Algoritmizace

[editovat] ComputeKnotVector(int n, int k)

[editovat] BasisFunction(int k, int i, ParameterCollection u, double t)

[editovat] Vector GetPoint(double t)

Zobrazení

Osobní nástroje

Hledat

Navigace

Tisk/export

Nástroje