Note:
- This article is going to demonstrate to readers about how to draw or set a NURBS curve (either uniform or non-uniform) without the requirement of any existing NURBS library.
- The readers here only need a basic knowledge about how to use OpenGL and freeglut to draw an Arc or a circle, that’s all.
- Actually NURBS can be drawn with OpenGL or without OpenGL. The reason to use OpenGL here is because the author will show you a group of newly derived KNOTS-EQUATIONs as the key algorithm, which needs a function of OpenGL for verification purpose only.
NURBS and Bezier
As NURBS are used in many CG or Solid CAD applications, so many programmers wish to add its functionalities into their own apps but there were almost no SIMPLE open library available in the www world. So if you would like to understand what its inside really is, maybe you would like to share the NURBS interpretation of mine.
Some of you may consider that NURBS is complicate because it has some variation forms like Uniform/Non-uniform/Rational/Non-rational. However, if you give me five to ten minutes, I will show you NURBS is as simple as Bezier curve. No matter it is Uniform or Non-uniform, NURBS is just made by one or a bunch of Bezier curve; and if you bear with me, what you need to know about NURBS math is just the Bezier-series-equations. To save your time to remember or find those common used equations of Bezier, I have enclosed them in figure 1 below.
Figure 1, two sets of common used Bezier equations
NURBS’ Programming
Before we jump into the NURBS programming, I like to emphasize one more time, a NURBS curve is actually one or many pieces of Bezier curve(s) that connected with each other in one by one order and under certain math bonding rule. Two or more Bezier curves connected one by one in Microsoft’s terminology is called Poly-Bezier. So NURBS is just a subset of polyBez under the bonding rule of Knots-array and NURBS Basis function.
Later you will see, Knots array, is a group of digits (int of float) which made the shape of NURBS vary besides its Control-points. It means there are actually two major variables are controlling the shape of NURBS, one is its Control-points and the other is its Knots-array. However, certain patterns of Knots may make a specific Bezier curve segment invalid. So if you wish to manage the NURBS in your flying code, the first thing you need is a tool to map each segment of the composite-Bezier-curves (polyBez) with a dynamic record, what I am using is a BitAry class. You can check it in the source code by yourself, what we need to know now is the reason why we need it.
For the next, what we have to prepare for an active NURBS are three data arrays for Knots, two data arrays for Control-Points and one data array of polyBez-control-points. Just make them prepared like I did below.
std::vector<Vec2D> CtrlPts;
std::vector<Vec2D> RingPts;
std::vector<double> coreNuts;
std::vector<double> OpenNuts;
std::vector<double> RingNuts;
std::vector<Vec2D> BezPts;
Ok, you may wonder how many NURBS are we going to draw? Why 3-knots[] + 2-Ctrls[] + 1-BezPts[]? The reason is simple, you need a basis of knots-array as the core; an OpenNuts[] to draw the open-formed curve of NURBS, and once if you want to make your curve connected with its head and tail to form a RING then you will need the RingNuts[]; both of the OpenNuts[] and the RingNuts[] are based on your core, coreNuts[]. In such an arrangement, you will have the flexibility to change whatever you want or need for the curve form dynamically, and your program would get the free power to fly along any reasonable NURBS path as well.
Also for the two sets of Control-Points; the first CtrlPts[] is used to form the Open-NURBS and your core record of Control-Points, and the second RingPts[] is used for the closed form of Ring-NURBS.
Oh, there is one major issue I forgot to tell, we are going to draw NURBS via a polyBez structure. It means that we must have the ability to convert the NURBS-control-points into Bezier-control-points first. Yes you are right, this is the exact reason why we need BezPts[].
Why we need so many arrays for just one NURBS?
Figure 3, CtrlPts[] vs. RingPts[]
Figure 4, Ring-Contorl-Points needed for a Ring-NURBS
Ok, after you are set then I will start to show you a picture about the relationship in between the KNOTS-array and the CONTROL-points.
5-1
5-2
5-3
Figure 5, the relationship in between Control-points and Knots.
The relationship of Control-points versus Knots of the above three pictures may be the first time to be seen by the world, I do not know the reason why they were not shown in books or the other media before, anyway this is my interpretation.
KNOTS Equations
Next, I will show you my KNOTS EQUATIONS that used to help us converting NURBS into PolyBez and of course the converted PolyBez still follows the math bonding rules of NURBS. You may question me why we should use some equations that never heard before? Why we don’t use something that existed already? I guess besides my method there may be only one existing way to convert NURBS back to its polyBez form, and it must walk through the Basis equations of NURBS and you can check it in Wikipedia. The Basis Equation of B-Spline or NURBS is a recursive algorithm in the imaginary space of our mind and in programming too; since it is recursive so it is a bit slower than a straight forward function. Just check my equations below, I believe that you will see my equations are much easier to be understood, and it makes the relationship in between CtrlPts[] and Knots[] much more clear than ever before.
6-1
6-2
6-3
6-4
Figure 6, KNOTS Equations of degree 2, 3 and 4.
Let me take the cubic degree of NURBS as an example to explain the usage of these equations for you,
- First, we normally use a, b, c, and d to represent the four control-points of cubic Bezier curve, but here in my equations I am using v0, b0, c0 and v1 to represent the four control-points of the Bezier segment-0, and v1, b1, c1 and v2 for the segment-1 and so on.
- The cubic Knots equation shows that the variables of bn and cn are both depend on the NURBS-control-points, p0 ~ pn; and vn is a depending variable of bn and c[n-1]. It is also because the calculation of vn needs bn and c[n-1], so when we plan to convert a cubic NURBS into a polyBez form, the total Bezier-control-points we need can be get in these calculation below:
Assume that our target cubic NURBS has n CtrlPts;
then it must be made by (n-3) segments of cubic Bezier curve(s);
so the total Bez3-control-points needed are (n-3)*3+1;
however, we need c[-1] plus b0 for v0 and c[n-1] plus bn for vn, yet cF (first c point) and bL (last b point) are not counted in the number of (n-3)*3+1;
thus the total temporary Bez3-control-points needed for conversion are (n-3)*3+3.
Figure 7
- Ok, please pay a little attention here, this is important. You can see my Knots Equations are all dealing with fractions, and each pair of bn and cn is actually share the same denominator. So what if the denominator is equal to zero? If this is the case for any pair of bn and cn then it means that the pair of bn and cn is invalid or not exist; which means the Bezier curve of segment-n is not exist either. In addition to the variable vn, it is governed by the same math rule too.
- From those equations of KNOTS, you can easily find the fraction-of-forces that created or functioned by those tangled relationship of Knots to the directional vectors (i.e. p[m] – p[n]). Take a look on the following equation then you will get what I am talking about.
Figure 8, tangled Knots.
As soon as you find out the math relationship that governed by these Knots equations then the encoding process into your program is just a trivial issue.
Now you can start to run my program, please check the command list first to find out what you can do with it, and then try the mouse click and dragging the point that you made to see the response of the program. But before you go too far for play, let us go back to the track to finish the Ring-form and Rational part of NURBS.
Knots alignment for Ring of NURBS
As I have mentioned before, form a RING actually uses more control-points than you saw from the picture. If you forgot about the reason why, please check figure 4 once again. The reason why we choose to stick on CtrlPts[] as our kernel and not to use the RingPts[] for the replacement, is because your app user may choose to form a ring and she/he may choose to break it to open again too. So as I have mentioned, NURBS is governed by two major variables, one is its control-points and the other one is its Knots. It is the time now, for us to dig out what would be the knots alignment inside a Ring.
In my opinion, Knot itself is meaningless, and the real meaning is coming from the difference of the two separate Knots that we found in our equations. Though we are getting used to call Knots as Knots-vector, but it is actually a SCALAR never a vector; and in fact the VECTOR is made by the control-points (p[n+1] – p[n]). Because only the coordinate of control-points can give us direction in space and knots are totally nothing to do with the direction or the change of direction.
So, how to arrange the knots variation to form a Ring? Please take a look at the picture below. (I am dumb so I always draw the picture to find out what my problem really is and how to analysis it; and I guess you have also found out that I have difficulty to describe the math relationship of things in English.)
Figure 9, Knots alignment for Ring-NURBS
Rational NURBS
The so-called Rational-Bspline has only one difference from the Non-rational-Bspline, which is its weight factor of each control-point. Please take a quick look on figure-10 below,
Figure 10, Rational Knots Equation
As you can see in figure-10, let me take the cubic ‘bn’ equation as an example. Within its Rational equation there are all scalar besides the control-points, so it is very easy to change a variable used to represent the weight factor to make it looks similar to its Non-rational one once again. Also the new Rational-equation of ‘bn’ can tell us, converting the Non-rational-Knots-Eq into the Rational-Knots-Eq won’t change its control-points of Bezier form, the only thing changed is its weight factor on each Bez-control-point. So, this is a good news to us, no matter you would like to use the Rational or Non-rational form of Knots-Eq, the converting procedure from NURBS to BezPts[] are almost the same.
Figure 11, Rational-Bezier samples
End of introduction
Finally, this is the end of my introduction about how to construct a NURBS curve in its different forms. Since my Knots-Equation is a brand new way to convert NURBS to its poly-Bez forms, maybe some of you won’t trust my math creditability. So be my guest, inside my source code there is a VERIFY command, which use an Open-GL built-in command, gluNurbsCurve(), to draw the NURBS. You can press ‘V’ key at anytime as you wish to check about the curve and to see if the glu- command gives you the same curve as my code or not?
Also that, as soon as you understand the reason why I defined those data storages for the program to handle different forms of NURBS then it would be a easy job to read the source code by yourselves. So I just let the code do the dynamic demo for me, otherwise you may be confused even more by my English expression.
I am fully understand that reading my article is not an exciting activity, but I still hope you can take my source code as a testing-aid to run NURBS, and if you like you can use my code as the basis to develop your own NURBS class; also you may try to simplify it furthermore by taking off the BitAry class via setting up your own rule to generate the non-uniform Knots in certain way. But be warned that it is not an easy job to make a well defined rule for Knots alignment, and wish you a good luck.
I hope these equations, pictures and my code would answer all of your questions about NURBS curve. However, if you really want to ask me a question directly, please use plain English and please forgive me in advance if I cannot answer you immediately; as I am still in the middle of some jobs that I cannot afford the time to hookup on internet all the time.
Further Study of 3D
I believe many of you are interested to put NURBS into 3D usage and would not satisfy with just 2D curves. For such a case, I would recommend you to download and study the source code of “Simple Bezier Patch Example” written by Mr. Rob Bateman (please click into the menu of “OpenGL” to find the specified example code). I do not know him in person, but if you like to understand NURBS surface or Bezier patch thoroughly, then my Knots-Equations plus his code example maybe an express way to walk through.
Problems on definition of Knots of NURBS
- KNOTs are SCALARs not VECTORs.
- The definition of the Multiplicity-of-Knots is incorrect.
I have seen many textbooks make the similar definition as following,
For clamped Bsplines
The first and last knot values are repeated with multiplicity equal to the order (degree+1) shall make the end points pass the control-point.
For cubic Bsplines, the multiplicity of the first/last knots must be 4 (repeated four times).
- Superfluous of Knots.
For example, it is easily to find out from my Knots-Equations, that the k0 and the kL (last element) of Knots array were never used, and if my memory is correct, these two knots were never used by Basis function of Bspline either.
Description
- Regarding to the second point, creating a head and tail clamped NURBS, the multiplicity is just the numbers of Degree, not the Order (degree+1).
As examples, you can test the knots pattern k[] = {a,b,b,b,c,c,c,d} with a cubic 4-points-NURBS, or
k[] = {a,b,b,b,c,d,d,d,e} with a cubic 5-points-NURBS by yourself.
and take a look at these sample figures below,
Figure 12, Cubic NURBS sample of Multiplicity
You can write your own code and use the original OpenGL’s gluNurbsCurve() command to prove them too.
- For the third point, superfluous of Knots, I am not the first one who says so. You can check this link to see McNeel-Wiki to get the same opinion; and I believe the programmer whom implement the gluNurbsCurve() function also knew about this problem long time ago, as most of its actions are correct as well. I guess the reason why this problem was suspended there for so long is just because no one has proof to show that it is wrong until my equations emerged now.
After all, as I am not a well trained mathematician (and I do not even know how to write a math paper correctly), I think it’s the better to leave the Knots definition problems to those experts for remedy. I just tried my best to present what I have learned about at here, and hope they won’t keep teaching the young students with the wrong message anymore.
Suspected bugs of gluNurbsCurve()
Though I use it to verify the implementation of my own derived Knots-Equations, but I found this command sometimes cannot function right. For example, you can check the data patterns of knots that I collected below in your own computer; as I have only tried them with the oldest version of Microsoft’s built-in opengl32.lib and glu32.lib till now.
1. k[]={0,3,5,9,9,9,9,9,11,13,15}; 8-points quadratic-NURBS;
2. k[]={0,3,3,3,3,5,9,9,9,9,9}; 7-points cubic-NURBS;
3. k[]={0,3,3,3,5,5,5,5,5,8,8,8,9}; 9-points cubic-NURBS;
4. k[]={0,3,3,3,5,5,5,5,5,5,8,8,8,9}; 10-points cubic-NURBS;
5. k[]={0,1,3,5,6,7,7,8,9,9,9,9,9,9,19}; 11-points cubic-NURBS;
6. k[]={0,1,2,3,3,3,3,3,3,3,5,8,8,8,9}; 10-points quartic-NURBS;
7. k[]={0,3,3,3,3,3,3,4,5,5,5,8,8,8,9}; 10-points quartic-NURBS;
The gluNurbsCurve() command cannot generate curves for these above examples of knots and some other of similar patterns. I dare not to say it’s definitely the bug of OpenGL foundation or Microsoft, but I think it is worth to be noticed because my equations can generate curves for them.
By the way, it is more than prefer if someone likes to examine my Knots equations or even give them certain kinds of torture tests. However if anyone likes question me about if I am qualified to raise these questions of math definition or bugs of gl-commnad then please check my past works first.
I know that I am nobody, so I will leave it to your judgment for all these information that I have developed so far.
Update on 20150628
For the problem, Knots array is a kind of vector or scalar? I have written an email to ask for the guidance from professor Ching-Kuang Shene of Michigan Technological University, and he told me this,
“The knots are ordered scalars and an ordered scalars form a vector. The term "knot vector" has been used for more than 30 decades, and nearly all NURBS standard textbooks use knot vector.”
So, it is my obligation to post this update to correct my own misinterpretation and thanks a lot for his kind reply to a stranger.
