Curve's Intersection
Hunt Chang 20140101
If you like to know about my way to find the NURBS intersection points, welcome to visit my NURBS-X solutions site.
Hunt Chang 20150407
This is an old website, it may be obsolete and closed by Google. However it will be kept untouched for the record.
What are my solutions?
Bezier curve and its parametric equations have been proved as an effective and efficient math tools to describe and simulate any piece of curved segment and used for computerization as a modern design and animation tool. However, the intersection points problem is also the development bottleneck of the contemporary 2D/3D CAD/CAM tools as there were no effective solution to solve them.
My solutions are not only solved the Quadratic and Cubic Bezier curves' X points problems to reach the contemporary requirement, but I have also pushed its ability into the next degree, QuarticBez, as well. One degree higher means one more level of continuity and a higher level of controllability and the better simulation ability to much more complicated curve form. Also I believed that CubicBez and QuarticBez will be used to cover most of our current and future of design and simulation requirement.
Also, the best things of my solution are, it is based on geometry theory and it is real time operable in any modern PC.
The solutions that I have done:
I have solved all the intersection points in between two degree 2, degree 3 and degree 4 of Bezier curves (or so-called Bernstein curves); and more …. Please find them in the pages of “X of Curves”.
I have solved all of the Self-X points of degree 3 and degree 4 of Bezier curves.
I have proved the Identity problems of QuadraticBez and CubicBez in math, which are about the questions of if any of two Quadratic Bezier curves belong to one parabola or not? and if any of two Cubic Bezier Curves belong to a single degree 3 curve or not? Now, I am still working on how to identify any of two different QuarticBez segments are picked from the same piece of degree 4 curve or not?
The features of my solutions:
My solutions are all general and common to solve the above problems, they are not limited for special cases only.
My solutions are all real-time operable in any modern PC; which means that they are fast and should be the fastest in the whole world now.
The kernel ideas of my solution are all based on algebra and geometry theories. Though I do need two approximation algorithms to run my solutions, but the first one is the Poly-Solver that help me to solve the polynomials in my equations and the other is developed by myself to be used to compensate the precision loss for computational rounding-errors during the general calculation and the prosess of polynomial roots finding.
The calculated results of X point from my solution are very precise, and the precision level can be controlled by setting the threshold value in program. The current threshold for the X (intersection) points in my demo program is set at 1.0e-9.
My solution is not just fast and precise only, it is pretty stable too. There is no un-found X point.
Note:
Bezier curves intersection and self-intersection problems were once believed impossible to be solved by math theory within the past half-century. So, my solutions should be the only one in the whole world that can solve these problems now.
Degree 2 == Quadratic; Degree 3 == Cubic; Degree 4 == Quartic;
Computational Rounding-Errors, is an unavoidable deviation. Especially when we dealing with those Polynomials of degree higher than ten. It is a major reason why I had to find an approxiamation way to compensate the precision loss to make my solutions more precise and reliable.
Deviation threshold == 1.0e-9, means that you can verify the X point’s data from any two responsive set of t values that I presented in the pages of “X of Curves” and their difference of coordinates shall be smaller than the threshold.
No un-found X point, of course this is on my own test. But during my development, I am testing it everyday and it took me over 18 months just for the solution of QuarticBez intersections and the CubicBez part solution exhausted even more of my life.
Key advantages of my solution: Accuracy, Precision & Real-Time Speed
20140115
I was told by two professors the solutions of Bezier curve intersections are already exist in 2012 and this year separately. They told me the problem can be solved by subdivision and resultants. I did Google the www websites and do find some related links but without the detail contents. I wonder if the solutions were already exists then why we haven’t seen any application yet? Why we never heard about any implementation of these methods either? If they are really so good then why those professors are still teaching BezClipping and Fat Line in academics? Are they truly modern solutions for real-time computation or just the kind of concept-solution of thesis? I do not mean to offend but I take the challenge of these existing solutions for their real value of usefulness!
People asked me about what is the difference of my solution from the others recently? How do I speed-up my algorithm for real-time operation? In return, I would like to ask one question too. How do we solve the intersection problem in between a circle and a parametric-curve? I believe many people would say it is pretty simple ... Why? What is the difference of this problem compared with the problem of two curves that intersect with each other?
The difference is, in the former problem we have to deal with one clock only as the circle is in a constant world without time changing, but in the latter one we have to deal with two clocks that tick asynchronously most of the time. So if I just turn off one clock in the two curves then the complicate problem would suddenly changed itself into a simple one, right? I guess this is also the secret reason why, I am the only person in the whole world so far that can solve the self-intersection problem of cubic and quartic Bezier curves in real-time as well.
Why the “INTERSECTIONs” are so important with curves?
It is simply because without knowing how to solve them then we can not calculate the union or intersection of any two 3D curved objects. Also without these calculated results, we are not able to turn an 3D curved design into the machine tool paths then we have no way to produce the object with our modern tooling machines.
Bezier curve equations are actually a group of descriptions of nature curve segments in different degree; and curves are actually the moving behavior of a combination of vectors of force. Also Bezier equation is super fit into our modern computer calculation and drawing technologies for curved object design or curved model building. All these reasons make it an un-replaceable tool. However just because we were stuck on the problems of intersections in between curves and within themselves so its truly usage is very limited so far.
In a summary, it means that though we knew this tool is fantastic to describe and operate CURVES; but if we do not know how to conquer the cross points problem of any two parametric equations then we would have big trouble to control and predict their mutual interactions.
Your solution seems 2D only, how does it related with the 3D problems?
It is true, I have presented all of my data examples in 2D here, but it is also a 3D solution without question. Because of that any 3D Bezier curve is easily projected into a plane to get its 2D curve part, and combine two plane solutions like X-Y and Y-Z back to 3D is just a piece of cake. So turning the 2D answers into 3D combination is a simple process just like solving a problem of two associated equations in one by one order.
Actually the PROJECTION way is a kind of professional talking, if you want to turn a 3D Bezier into 2D one, just drop the z part of coordinate from those control points then you get its 2D curve part on X-Y plane from the original 3D one; simple, right?