Geometrie/Algoritmus de Boor

De Boor algoritmus

De Boor algoritmus pro výpočet bodu B-spline křivky je zobecněním algoritmu de Casteljau pro Bézierovy křivky. Pro $u\in \left\langle u_{l},u_{l+1}\right\rangle$ vypočítáme bod na B-spline křivce opakovanou lineární interpolací:

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

kde

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

Bod $P_{l}^{k}=P\left(u\right)$ je hledaný bod na B-spline křivce.

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];
  for (int i=0;i<n;i++)
  {
   points[i] = ((RichPoint)(ctrlPoly[i])).Locate;
  }
  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];
 }