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.
NURBS-X Execution Speed Demo
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.
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.