X of Curves

Rounding-Errors of X points

In June of 2012, I presented my Cubic solutions of X in few forums. Guess there are very few people believed me about my CubicBez solution of X as I just got few responses till now; since I was still working on a problem and the QuarticBez solutions was under brainstorm at then so I just dropped it there.

What was the problem?

The problem was about 5% of the deviation of my Cubic X points were out of the range of 1.0e-9. Because it may be a weakness that people would challenge me, a nobody in curve field. So I think it would be better to solve it by myself before I let it go. I am lucky, I got it solved and I have conquered the X points problems of QuarticBez too.

Why 1.0e-9?

Frankly it is purely by experience. Since I have to deal with polynomials to solve the X points, and when the poly-degree getting higher than the rounding-errors getting more seriously and it is not avoidable. Though the computer's 8-byte-double data type offer us 15~16 digits precision after dot, but when we have to deal with polynomials like QuarticBez X QuarticBez, which is 4x4=16 poly-degrees, facing to a 16 degrees power of polynomial it is truely impossible to maintain all of the answers' precision higher than 1.0e-6 out of a PolySolver. So if I want to get a better precision to create a more reliable solution then I have to count on the other effective measurement and I have made it done.

So let's set the threshold at 1.0e-9 as I can reach it without a problem, and I think if the user do not mind to spend more CPU times then it may still be safely to set the threshold at 1.0e-11; but this is not unlimited. Speaking for the truth, someday during the testing period, I suddenly realized as soon as i am dealing with polynomial then I can not always expect that I can reach the limit precision of the double data type. Because the degree power of a polynomial will bloat up its own rounding-errors; and don't forget Bezier equation is a polynomial itself. (This is a basic math principle, but we always ignored it as we all inclined to be a perfectionist.)

Data won't cheat as it can not be invented via a magic wand!

If people do not believe me about my solutions is because of that I have no name, I have nothing to complain. But if it is because the data seems too good to be true then I really do not know what else I can say? Yes, it is truely unbelievable, when I first saw the answers I got for CubicBez, I do not believe it either for many days. However I can not fabricate so many data with such a kind of precision unless I have a bunch truly decent solutions in hand. Please use a math tool or spreadsheet of your favor then you can easily verify them by yourselves.

Unbelievable speed: Super Fast execution!

Solving the X points of a QuarticBez to QuarticBez set of curves in my program, each round only takes few hundreds of micro-second in average and the test sampling counts I took are normally hundreds to 2k (why 2k in maximum? Since my program has a basic animation function, so the sampling counts are very easy to be accumulated and my old ex-PC do not have a big main memory). These are the data I got from my 4-year-old PC and I have attached the CPU-Z page below for anyone's concern and reference.

The pictures below are just some random performance tests taken from two PC on degree 4X4 and 3X3 intersection points which I did for comparison; and the sampling-count only accumulated under the condition when program found X points.

People asked me about what is my algorithm to solve the X problems? Did I use the way of bi-section or BezClipping? Frankly, the answer is no, I did not use any of them. The way of bi-section is too slow, I did try it on QuadraticBez in long long time ago, but consider to its speed and the complicated logics to implement it to the high degree of Bezier curves, I gave it up. For the BezClip way, I do not think it is easier than bi-section in logic on the implementation; besides that how should I clip a QuarticBez?

Actually, no matter which way you would like to use to solve your problem, eventually you have to face the intricate logics and details; also you have to consider the precision and speed of execution. Without the combination of these 3 issues, clear logic to cover all the detail, precision and speed; I do not believe the code of this sort can be tagged, RELIABLE!

Note:

All of the data deviation threshold were set at 1.0e-9, and all of the control-points, X (intersection) points and those responsive t values of X points were presented in each page for your verification.