Geometrie/Racionální algoritmus de Boor

De Boor algoritmus

Bod na racionální B-spline křivce můžeme stejně jako u racionálních Bézierových křivek spočítat hned dvěma způsoby.

1. Pomocí algoritmu de Boor pro racionální křivky:

Zvolíme-li $u\in \left\langle u_{i},u_{i+1}\right\rangle$, pak bod na racionální B-spline křivce vypočteme opakovanou lineární interpolací:

$P_{i}^{j}\left(u\right)=\left(1-\alpha _{i}^{j}\right)\cdot {\frac {\omega _{i-1}^{j-1}}{\omega _{i}^{j}}}\cdot P_{i-1}^{j-1}+\alpha _{i}^{j}\cdot {\frac {\omega _{i}^{j-1}}{\omega _{i}^{j}}}\cdot P_{i}^{j-1}$,

kde

$\omega _{i}^{j}\left(u\right)=\left(1-\alpha _{i}^{j}\right)\cdot \omega _{i-1}^{j-1}+\alpha _{i}^{j}\cdot \omega _{i}^{j-1}$

a

$\alpha _{i}^{j}={\frac {u-u_{i}}{u_{i+k-j+1}}}$, $i=1-k,\dots ,1$ a $P_{i}^{0}=P_{i}$.

Bod $P_{1}^{k}\left(u\right)=P\left(u\right)$ je hledaný bod racionální B-spline křivky.

Toto rozšíření algoritmu de Boor vzniklo obdobným způsobem jako rozšíření algoritmu de Casteljau pro Bézierovy křivky.

2. Převodem na neracionální křivku a zpětným promítnutím:

Převedeme racionální B-spline na neracionální (o jednu dimenzi výše), provedeme de Boor algoritmus pro neracionální křivku a výsledný bod převedeme (promítneme) zpět.

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

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)
 {
  ParameterCollection u = parametrization;
  int n = ctrlPoly.Count;
  Vector[] points = new Vector[n];
  double[] weight = new double[n];
  for (int i=0;i<n;i++)
  {
   points[i] = ((RichPoint)(ctrlPoly[i])).Locate;
   weight[i] = ((RacionalRichPoint)(ctrlPoly[i])).Weight;
  }
  int l=0;
  while(t>u[l]) l++;
  l--;
  if(l<Degree) l=Degree;
  for(int j=0;j<Degree;j++)
  {
   for(int i=l-Degree+1+j;i<=l;i++)
   {
    double alfa = (t - u[i])/(u[i+Degree-j]-u[i]);
    points[i]=(1-alfa)*points[i-1]+alfa*points[i];
   }
  }
  return points[l];
 }