Nonuniform Bspl

A real-time solution to find out NURBS intersection points

To find out the intersections of NURBS, I divide it into two parts, the first is its Non-uniform B-spline part and the second is its Rational part.

Over twenty years ago, I was a CAD software sales and I learned that NURBS is an important tool for 2D/3D CAD/CAM design. Later when I found the truth behind that we can only use the NURBS tool for product design but we cannot predict the intervention in between any two objects of NURBS then I realized that the intersection solutions of NURBS is the major bottleneck of this technology. As in our nature environment and among those artificial objects that around us, Curves were everywhere and far more than Arcs in quantity. Unless we can find a real geometric solution to solve NURBS-X problem or a new way in math to describe the nature curve then the whole CAD industry will not get any further significant progress on its geometric designing capability.

Regarding to conquer the NURBS to find out its X-points solution, I category it into two parts, the first is its Non-uniform and Uniform B-spline part, and the second is its Rational part. The reason is simple, because the Non-uniform B-spline part are all composed of Bezier curve segments and the Rational part is much harder to be predicted under the modern geometry knowledge.

Nonuniform B-Spline part

• Below of this page, I am going to discuss the Non-Rational and Non-uniform B-Spline only. Please do not get any RATIONAL thoughts involved here, it means no WEIGHT factor at all.

• Please also forgive me if my math terminology is not correct or precise, it because neither Math nor English is my expertise.

To use my Bezier-X solutions as the NURBS-X solutions directly, my first challenge is how to convert NURBS back to its poly-Bezier form efficiently? You might say that there is already a solution there; Boehm's knot insertion method can do it. Though, I never really tried it as I think the method will eventually walk through De Boor’s algorithm (if I am wrong, please forgive my ignorance) so I think that I had to find my own way out.

Allow me to explain my reason why I do not like to use De Boor’s algorithm. The algorithm is good but with only one drawback that it is recursive; and recursive means slower in computation, especially when you need to calculate a tool-path with hundreds of points within just one Bezier segment. Once under this situation and if you have the choice to use Bezier equation or De Boor’s then which one you would choose?

Knots Equation of NURBS

Before I start to introduce my own NURBS to Bezier's conversion algorithm, let me raise one question first. Under the current math definition what would be the knots pattern of a clamped NURBS of cubic degree? This is what I found for the answer, “For cubic B-Spline, the multiplicity of the first/last knots must be 4 (repeated four times).”, and most textbooks give the same or the similar answer too.

However, in many years ago, I accidently found that any knots pattern of {a,b,b,b,…,d,d,d,e} is a clamped Cubic-NURBS. I have googled it many times in the past and only found one another skeptic like me, http://wiki.mcneel.com/developer/onsuperfluousknot. So does the current definition of the NUMBER of KNOTS is correct or if the KNOTS VECTOR itself is well defined? Frankly I doubt! Since that I am not a well trained mathematician, so I just present my equations here, and let the experts to do the judgment and hope someone can help to finish them for an update on its math definition.

• Quadratic degree

Please take a detail and careful look on the graph below; inside the image I have inserted the extracting equations to convert a NURBS back to the control points of quadratic Bezier of each segment.

Also the same are going on at the images for Cubic and Quartic NURBS too.

• Cubic degree

• Quartic degree

Demo Program

These Knots-Equations of above, seems neat and clean, and they can also offer you a clear understanding about the blur relations in between the knots-vector and control-points of NURBS. However they took me few months of time to calculate and test to come to these final conclusions. If my brief is too much simple here to be understand, please check my demo program for the detail.

Believe me, I really like to tell all of you what I am trying to present at here, but I guess many of you would hate my English express ability. Though some of you have found these equations are used to convert NURBS to its poly-Bezier form in degree 2, 3 and 4, but you may have some questions too. Anyway, I decide to let the program code do the dynamic presentation for me, and please pay a bit attention to my code and match the puzzle with these equations and graphs above, then you may agree that my algorithms are faster and easier than De Boor’s recursive spiral algorithm.

I do not mean to be rude to a senior gentleman. Mr. De Boor’s algorithm is indeed a very smart algorithm that can only be developed by the really smart person. Because every time I trace it, I can truly feel the pain of my headache. So I guess that I shall have no chance to think it through just by myself, and without standing on the shoulder of a giant I would have no way to derive and conclude these equations above.

Finally, if you can be convinced by my Knots Equations, which are capable to convert NURBS into poly-Bezier without problem then you would believe that my Bezier-X solutions are exactly the solutions for NURBS-X too.

Advantage of Knots Equations

• It is much easier to understand than the basis function of B-Spline.

• As it can use Bezier equation to calculate the curve segments of NURBS, so it is much faster.

• If you change the terminology of “Knots Vector” into “Forces Vector” then you would find out, it is more clear and easier to explain the behavior of a curved trajectory of a flying object.

• These equations may help the Non-uniform part of B-Spline starting to join into the real application of our life.

Author declaration:

Since I have searched the world-wide-website many times in last few months and have not found anything similar to my “Knots Equations of NURBS” so far. So I think I am the first one who presents these equations to the world. If anyone who would not agree with me about this point then please provide evidence to prove your claim.

I hereby declare that all the equations and program code in this page and the code page are derived and written by myself without any second or third party got involved.

Also I hereby open these equations to everyone’s free usage for the good purpose. However the copyright is reserved and no one is allowed to bind these equations for any commercial promotion without the prior written consent of mine.

Hunt Chang 20150301