Geometrie/Racionální B–spline křivka

Z Wikiknih

Přejít na: navigace, hledání

Obsah

[editovat] Racionální B-spline křivky

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

P\left(u\right)=\frac{\sum^n_{i=0}P_i\cdot\omega_i\cdot N^k_i\left(u\right)}{\sum^n_{i=0} \omega_i\cdot N^k_i\left(u\right)},

kde

Pi jsou body řídícího polygonu (tzv. de Boor body),
ωi jsou váhové parametry jednotlivých bodů \omega_i\ge 0,
N^k_i\left(u\right) jsou normalizované B-spline bázové funkce stupně k.

Rovnici racionální B-spline křivky můžeme upravit na tvar:

P\left(u\right)=\sum^n_{i=0}P_i\cdot R^k_i\left(u\right),

kde

R^k_i\left(u\right) jsou racionální B-spline bázové funkce definované:
R^k_i\left(u\right)=\frac{\omega_i\cdot N^k_i\left(u\right)}{\sum^n_{j=0} \omega_j\cdot N^k_j\left(u\right)}

Racionální B-spline křivky jsou obvykle definovány na neuniformním uzlovém vektoru U=\left(u_0,\dots,u_m\right). Takovým křivkám pak říkáme NURBS křivky (non uniform rational B-spline). Je-li tento vektor neperiodický, pak pro něj platí stejná pravidla jako pro neracionální B-spline křivky.

[editovat] Analytické vlastnosti racionálních bázových funkcí

Pro racionální bázové funkce R^k_i\left(u\right) platí podobné analytické vlastnosti jak pro bázové funkce N^k_i\left(u\right).

Nezáporná hodnota

R^k_i\left(u\right)\ge 0 pro \forall u\in\left\langle u_0,u_m\right\rangle

Jednotkový součet

\sum^n_{i=0} R^k_i\left(u\right)=1 pro u\in \left\langle u_0,u_m\right\rangle

Vlastnost krajních funkcí

R^k_0\left(0\right)=R^k_n\left(1\right)=1

Extrémy

Každá bázová funkce R^k_i\left(u\right) má pro každé i na intervalu \left\langle 0,1\right\rangle právě jedno maximum.

Lokální vlastnost

R^k_i\left(u\right)\ne 0 pro u\in\left\langle u_i,u_{i+k+1}\right\rangle

Zobecnění

Funkce R^k_i\left(u\right) jsou zobecněním funkcí N^k_i\left(u\right), pro i=0,\dots,n a ω = 1 platí

R^k_i\left(u\right)=N^k_i\left(u\right)

Pro uzlové vektory a váhy platí:

U=\left(0,0,0,1,2,3,3,3\right) \left(\omega_0,\dots,\omega_4\right)=\left(1,4,1,1,1\right) pro obrázek vlevo
U=\left(0,0,0,1,2,3,3,3\right) \left(\omega_0,\dots,\omega_4\right)=\left(1,1,0.3,1,1\right) pro obrázek vpravo

[editovat] Geometrické vlastnosti racionálních B-spline křivek

Geometrické vlastnosti pro racionální B-spline křivky jsou zobecněním vlastností neracionálních B-spline křivek.

[editovat] Koncové podmínky

Pokud uvažujeme neperiodický uzlový vektor ve tvaru

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

pak platí, že racionální B-spline křivka stupně k prochází počátečním a koncovým bodem řídícího polygonu a dotýká se v těchto bodech jeho první a poslední hrany.

Mezi počtem uzlů m, stupněm křivky k a počtem bodů řídícího polygonu křivky \left(n+1\right) platí následující vztah:

m = n + k + 1

[editovat] Konvexní obal

Jsou-li všechny váhové parametry nezáporné, pak pro u\in\left\langle u_i,u_{i+1}\right\rangle,k\le i\le \left(m-k-1\right) leží bod P\left(u\right) v konvexním obalu množiny, která je určena body P_{i-k},\dots,P_i.

[editovat] Invariance vůči transformacím

Racionální B-spline křivky jsou invariantní vůči afinním transformacím, NURBS křivky jsou také invariantní vůči projektivnímu promítání.

[editovat] Průsečík přímky (ve 2D) nebo roviny (ve 3D) s křivkou

Žádná přímka (rovina) nemá více průsečíků s křivkou než s jejím řídícím polygonem.

[editovat] De Boor algoritmus

Viz Racionální algoritmus de Boor

[editovat] Modifikace tvaru křivky pomocí váhových parametrů

Obdobně jako u racionálních Bézierových křivek můžeme využít změny hodnot váhových parametrů k modifikaci křivky bez potřeby měnit polohu bodů řídícího polygonu. Zvětšujeme-li hodnotu váhového parametru ωi a ostatní váhové parametry zůstanou beze změny, křivka se více "přimyká" k odpovídajícímu bodu Pi, ovšem vliv změny na tvar křivky je omezen pouze pro u\in\left\langle u_i,u_{i+k+1}\right\rangle, ostatní části zůstanou beze změny.

[editovat] Vyjádření kružnice pomocí racionální B-spline křivky

Jak bylo řečeno v úvodu, některé kuželosečky, jako jsou elipsa nebo hyperbola, je možné pomocí neracionálních křivek popsat pouze přibližně, proto byly zavedeny křivky racionální. V tomto příkladě ukážeme, jak popsat kružnici pomocí racionální B-spline křivky.

Vektorová rovnice pro kružnici, která je určena sedmi vrcholy řídícího polygonu, je následující:

P\left(u\right)=\frac{\sum^6_{i=0}\omega_i\cdot P_i\cdot N^2_i\left(u\right)}{\sum^6_{i=0}\omega_i\cdot N^2_i\left(u\right)}=\sum^6_{i=0} P_i\cdot R^2_i \left(u\right),

kde

uzlový vektor je U=\left(0,0,0,\frac{1}{3},\frac{1}{3},\frac{2}{3},\frac{2}{3},1,1,1\right)
a váhový vektor je \left(\omega_0,\dots,\omega_6\right) = \left(1,\frac{1}{2},1,\frac{1}{2},1,\frac{1}{2},1\right).

Vektorová rovnice pro kružnici, která je určena devíti vrcholy řídícího polygonu, je:

P\left(u\right)=\frac{\sum^8_{i=0}\omega_i\cdot P_i\cdot N^2_i\left(u\right)}{\sum^8_{i=0}\omega_i\cdot N^2_i\left(u\right)}=\sum^8_{i=0} P_i\cdot R^2_i\left(u\right),

kde

uzlový vektor je U=\left(0,0,0,\frac{1}{4},\frac{1}{4},\frac{1}{2},\frac{1}{2},\frac{3}{4},\frac{3}{4},1,1,1\right)
a váhový vektor je \left(\omega_0,\dots,\omega_8\right)=\left(1,\frac{\sqrt{2}}{2},1,\frac{\sqrt{2}}{2},1,\frac{\sqrt{2}}{2},1,\frac{\sqrt{2}}{2},1\right).


[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 stupňe 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();
 double denom = 0;
 for (int i = 0;i<ctrlPoly.Count;i++)
 {
  ret+=BasisFunction(Degree,i,parametrization,t)*((RacionalRichPoint)ctrlPoly[i]).
   Locate*((RacionalRichPoint)ctrlPoly[i]).Weight;
  denom+=((RacionalRichPoint)ctrlPoly[i]).Weight*BasisFunction(Degree,i, parametrization,t);
 }
 return ret*(1/denom);
}

[editovat] RichPoint CreateRichPoint()

Přetížená metoda třídy Curve. Spočítá a vrátí řídící bod pro křivku s váhovým koeficientem. RacionalRichPoint je jako RichPoint, ale počítá s váhou bodu.

public override RichPoint CreateRichPoint()
{
 double t=0;
 if (ctrlPoly.Count>0) t=((RacionalRichPoint)ctrlPoly[0]).T;
 foreach (RacionalRichPoint p in ctrlPoly)
 {
  if (p.T>t) t=p.T;
 }
 RacionalRichPoint rp=new RacionalRichPoint(new RichPoint(new Vector(0,0), t+1), 1);
 return rp;
}
Citováno z „http://cs.wikibooks.org/wiki/Geometrie/Racion%C3%A1ln%C3%AD_B%E2%80%93spline_k%C5%99ivka“