Nonuniform B-Spline basis function and Direct 2D

• Download executable
• Download source code

1. What has been done?

   I've developed a small and quite nice app that visualizes B-Spline support functions. You can move knots so that the B-Spline adjusts automatically and see how it behaves on non uniform knots, and turn on and off important features like Bezier polygon, de Boor points. The application has been written in Direct2D which was discussed later. Numerically stable and correct algorithms have been implemented to evaluate B-Spline function.

2. What is B-Spline?

   A short definition of B-Spline can be found here. Generally B-spline is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. A fundamental theorem states that every spline function of a given degree, smoothness, and domain partition, can be represented as a linear combination of B-splines of that same degree and smoothness, and over that same partition[1]. The term B-spline was coined by Isaac Jacob Schoenberg and is short for basis spline[2]. B-splines can be evaluated in a numerically stable way by the de Boor algorithm. Efficient  B-Spline functions are evaluated by de Boor algorithm and Bernstein polynomial basis.

3. The following gallery is presenting different B-Spline N³ basis function in different configurations:

   

4. Handling drawing in direct 2D

   According to the latest Microsoft articles and guides, I've handled drawing in Direct 2D. A short introduction about Direct 2d can be found here. I couldn't see any major runtime differences between GDI (ew. GDI+) drawing in Win32 and Direct2D. Drawing in Direct2D forces you to do some additional work like managing extra classes and structures for instance: only to have line coloured what is irreasonable. So if you draw only some simple charts like this one or lines without antialiasing, probably you better stick to some old good folks like GDI+ rather than Direct2D. If you use massive drawing on GUI, then start thinking about writing your app in .NET (WPF) and port only some crucial code to C++ DLL. Painting in unmanaged Direct2D is good if you're limited to Win32 API and want to gain maximum performance out of simple graphics like charts (direct2D uses GPU for rendering). Ask yourself when your application got hung on a chart… Mine never hung on it. There is a bit of code overhead to start with Direct2D drawing. Firstly, you've to create resources (like in normal DirectX), that  means that you create ID2D1Factory object. Then, whatever you do: either choose color brush for your font or axis or choose line axis style you have to provide appropriate struct which in most is filled by the main ID2D1Factory object. Overall you don't get DX10 equivalent for 2D. There are no structures, no shaders, no direct input. It would be hard to create a game like pacman in Direct2D because it’s very limited API.

5. Algorithms
   • Evaluation of de Boor points

     void BSplineApp::ComputeDeBoorPoints(){
     for(int i=0;i<KNOTS;++i)
     {
     if(i!=2)
     deBoorPoints[i].y = .0f;
     else
     deBoorPoints[i].y = 1.0f;if(i==0||i==KNOTS-1)
     deBoorPoints[i].x = knots[i];
     else
     deBoorPoints[i].x = (knots[i-1]+knots[i]+knots[i+1])/3.0f;
     }}

   • Evaluation of Bezier points while previously having computed de Boor points:

     void BSplineApp::ComputeBezierPoints()
     {
     ComputeDeBoorPoints();
     deBoorPoints[0].x = deBoorPoints[0].y = .0f;
     for(int i=0;i div_t div_result;
     div_result = div(i,CUBIC_SPLINE_DEGREE);
     Assert((div_result.quot+1)<=KNOTS);
     float intervalWidth = knots[div_result.quot+1]-knots[div_result.quot];
     float a = intervalWidth*div_result.rem/CUBIC_SPLINE_DEGREE;
     bezierPoints[i].x = knots[div_result.quot]+a;float deBoorDiffX = 
     	deBoorPoints[div_result.quot+1].x-deBoorPoints[div_result.quot].x;
     float deBoorDiffY = deBoorPoints[div_result.quot+1].y-deBoorPoints
     			[div_result.quot].y;
     float ax = i==0?0:bezierPoints[i].x - deBoorPoints[div_result.quot].x;
     bezierPoints[i].y = ax *deBoorDiffY/deBoorDiffX + 
     			deBoorPoints[div_result.quot].y;
     }
     for(int i=3;i float y = (bezierPoints[i+1].y-bezierPoints[i-1].y)/
     	(bezierPoints[i+1].x-bezierPoints[i-1].x)*
     	(bezierPoints[i].x-bezierPoints[i-1].x);
     bezierPoints[i].y = bezierPoints[i-1].y + y;
     }
     }

   • Evaluation of B-Spline value:

     inline float Divide(float a ,float b)
     {
     if(a==.0f && b==.0f)
     return .0f;
     if(b==0)
     return a;
     return a/b;
     }float BSplineApp::GetSplineValue(const float & t,int i,int n)
     {
     if(n==0)
     {
     if(knots[i-1]<=t && t return 1;
     else return 0;
     }return Divide((t-knots[i-1]),(knots[i+n-1]-knots[i-1]))*
     	GetSplineValue(t,i,n-1)+Divide((knots[i+n]-t),
     	(knots[i+n]-knots[i]))*GetSplineValue(t,i+1,n-1);
     } 

     Evaluation of B-Spline is done with accordance to recurrent definition of B-Spline as it is written in Wikipedia.

6. Source code and executable

   You can download the source code (C++ in VS 2010 but easily convertible to previous versions of VS) and executable to run it.

   • Executable
   • Source code

Filed under: CodeProject, DirectX 10, Geometry Modelling Tagged: Geometry Modelling, HLSL

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)