De Boor’s Algorithm in C++

October 18, 2009

Here is the c++ code for the De Boor algorithm. It calculates a point C(x) on a B-Spline curve of any degree.

Point deBoor(int k,int degree, int i, double x, double* knots, Point *ctrlPoints)
{   // Please see wikipedia page for detail
	// note that the algorithm here kind of traverses in reverse order
	// comapred to that in the wikipedia page
	if( k == 0)
		return ctrlPoints[i];
	else
	{   
		double alpha = (x-knots[i])/(knots[i+degree+1-k]-knots[i]);
		return (deBoor(k-1,degree, i-1, x, knots, ctrlPoints)*(1-alpha )+deBoor(k-1,degree, i, x, knots, ctrlPoints)*alpha );
	}
}

The Point class is defined as the follow:

class Point
{
public:
	Point(){x=0.;y=0.;z=0.;};
	// copy operator
	Point operator=(const Point pt) ;
	Point operator+(const Point pt) const;
	//Point operator-(const Point pt) const;
	Point operator*(double m) const;
	Point operator/(double m) const;
	double x,y,z;
};

Point Point::operator=(const Point pt)
{
	x = pt.x;
	y = pt.y;
	z = pt.z;
	return *this;
}
Point Point::operator+(const Point pt) const
{
	Point temp;
	temp.x = x + pt.x;
	temp.y = y + pt.y;
	temp.z = z + pt.z;
	return temp;
}
Point Point::operator*(double m) const
{
	Point temp;
	temp.x = x*m;
	temp.y = y*m;
	temp.z = z*m;
	return temp;
}
Point Point::operator/(double m) const
{
	Point temp;
	temp.x = x/m;
	temp.y = y/m;
	temp.z = z/m;
	return temp;
}