5 Replies Latest reply on Jul 6, 2012 4:47 AM by Hunt Chang

    Fast and precise INTERSECTION solution of cubic BEZIER curves

    Hunt Chang

      To All,

       

      I guess relaese this information of my solution here may not be adequate, but I really need a way to draw some attention from Dassault. I apologize in advance for anyone feel offended.

       

      Cubic Bezier curve has been invented over fifty years, people are all expecting its great functionality and productivity to be used in CAD/CAM for free form curve design or photo-realistic solid modeling. However I believe its usage was limited as there is no effective way to solve the intersection points problem either in between curve-to-curve or within a curve itself.

       

      Anyway, the problem is a history now. Enclosed are a picture of cubic Bezier curves’ intersection points and certain data related with the two curves that auto-generated by a program of mine. Anyone, who feels interested are all welcome to verify them for the truth.

       

      Again, allow me to emphasize, my solution is fast, precise and by theory; it is not an approach of approximation like bi-section or bez-clipping or ...

       

      Hunt Chang

       

      cBez_X-1.png

       

      Blue Curve control points: P0 (404.000000, 355.000000), P1 (169.000000, 264.000000), P2 (858.000000, 329.000000), P3 (438.000000, 239.000000);

       

      Red Curve control points: P0 (556.000000, 334.000000), P1 (253.000000, 331.000000), P2 (765.000000, 48.000000), P3 (414.000000, 489.000000);
         Self Intersection point at (521.381253777, 332.148294653);  t[1] = 0.844680894, t[2] = 0.042885836;

       

      The Intersection point(s) of those two curves:
        x0(455.734152990, 299.109787062), x1(490.237592592, 250.732158097), x2(542.630905524, 264.568535791), x3(538.123536369, 292.686435169);
      Blue Curve's t value(s):
        t[0] = 0.437206056, t[1] = 0.952837683, t[2] = 0.883884689, t[3] = 0.596112430;
      Red Curve's t value(s):
        t[0] = 0.232537221, t[1] = 0.453969337, t[2] = 0.713303391, t[3] = 0.780607425;


        • Re: Fast and precise INTERSECTION solution of cubic BEZIER curves
          Hunt Chang

          Not convincible? How about one more sample?

          Hunt Chang

          9X.png

          Blue Curve control points: P0 (504.000000, 360.000000), P1 (111.000000, 282.000000), P2 (753.000000, 368.000000), P3 (414.000000, 288.000000);
          Inflection point(s) at (436.247939291, 324.686418634);  t[0] = 0.493948130;

           

          Red Curve control points: P0 (434.000000, 410.000000), P1 (662.000000, 60.000000), P2 (175.000000, 558.000000), P3 (523.000000, 263.000000);
          Self Intersection point at (497.178713708, 284.716993708);  t[1] = 0.219641391, t[2] = 0.973625079;

           

          The Intersection point(s) of those two curves:
            (469.284632332, 352.984190733), (484.205333013, 325.417398792), (491.920199738, 308.486201692), (455.137674488, 298.118444831);
            (424.123514673, 324.385358688), (408.647917012, 339.640827151), (447.698139089, 324.971794242), (423.836163179, 343.202129023);
            (474.615957980, 303.350537381);
          Blue Curve's t value(s):
            t[0] = 0.032102241, t[1] = 0.614547187, t[2] = 0.892283373, t[3] = 0.953489452;
            t[4] = 0.464196010, t[5] = 0.110969242, t[6] = 0.521571699, t[7] = 0.086657188;
            t[8] = 0.924926429;
          Red Curve's t value(s):
            t[0] = 0.063739442, t[1] = 0.105845537, t[2] = 0.139708529, t[3] = 0.428695394;
            t[4] = 0.532211221, t[5] = 0.592534208, t[6] = 0.909201381, t[7] = 0.864858712;
            t[8] = 0.947179525;

            • Re: Fast and precise INTERSECTION solution of cubic BEZIER curves
              Hunt Chang

              To:  R&D experts of Dassault Systemes,

               

              Not to boast myself, but if I do not speak for my own solution then nobody can.

               

              People asked me about what is the better of my solution than the other solutions that already exists?

               

              First off, I guess my solution so far is the only one in the whole-world which solved the intersection points problem of cubic and quadratic Bezier curves accurately by Geometry theory instead of by way of approximation. Frankly the way of approximation has nothing wrong as soon as it can get the correct answer; but compare to the same level of data accuracy or precision, I believe mine is much faster. Although my way to solve the problem is also a complicate process, but it is still fast enough to be operated in real-time even by an AMD Athlon(K5) CPU. May be someone would defy me for bluffing, please take a few minutes of calculation to verify the data I already presented here, just let those data speaking for the truth.

               

              Secondly, cause in each intersection point there must be two ‘t’ values (or more by coincidence) get involved, so we can get (at least) two sets answers of coordinates from each intersection. In theory, when an intersection exists, the two sets of coordinate must be exactly the same, but in reality of computation there are certain deviation exists most of the time. Under a reasonable coordinate setting, my data deviation is always lower than the constant of FLT_EPSILON; actually I had done some random control points location tests, over 97% of my data deviation are lower than 1.0e-10 and only less than 0.3% deviation are within the range of FLT_EPSILON ~ 1.0e-08. Since my solution is by Geometry theory, it means if I change the code to use 16-byte-doulbe-precision format number in the future then the data precision would be double as well; and its extra CPU overhead would be quite small.

               

              To the math experts of Dassault, with the precision level set to 9 digits or higher after decimal point, I CHALLENGE you that my algorithm is faster and accurate than yours on solving the intersection problem of cubic Bezier curves, would you dare to take this challenge?

               

              Lastly, during the very long period I spent to discover this solution, I did find some math properties of the curve that never have been exposed before; actually I count on them to solve the 2D curve intersection puzzle. So, even I do not know what kind of algorithm or strategy you are using to solve the B-spline-surface intersection problem now, but I think my solution or my discovery may offer you a better chance or a different approach to look at that problem.

               

              If you are interested on my solution, feel free to contact me.

              Hunt Chang

                • Re: Fast and precise INTERSECTION solution of cubic BEZIER curves
                  Hunt Chang

                  Quartic X Cubic Bezier Curves

                   

                  C2Q_X.png

                  Blue Curve control points:
                    P0(294.000000, 478.000000), P1(710.000000, 313.000000), P2(461.000000, 159.000000), P3(352.000000, 482.000000);

                   

                  Red Curve control points:
                    P0(321.000000, 445.000000), P1(666.000000, 384.000000), P2(220.000000, 378.000000), P3(663.000000, 80.000000), P4(442.000000, 486.000000);

                   

                  The Intersection point(s) of those two curves:
                    (370.002329784, 435.470577799), (403.556382661, 427.160436924), (460.864511925, 391.115205214), (464.260893656, 308.774187728);
                    (501.914020196, 293.066503440), (496.828922444, 360.676524395);
                  Blue Curve's t value(s):
                    t[0] = 0.948066352, t[1] = 0.104508914, t[2] = 0.183598275, t[3] = 0.705242235;
                    t[4] = 0.587258396, t[5] = 0.257514275;
                  Red Curve's t value(s):
                    t[0] = 0.040947602, t[1] = 0.078958480, t[2] = 0.238408796, t[3] = 0.525974506;
                    t[4] = 0.777083037, t[5] = 0.898521787;

                   

                  ///////////////////////////////////////////////////////////////////////////////////////////////////////////

                  C2Q_X - 1.png

                  Blue Curve control points:
                    P0(346.000000, 226.000000), P1(365.000000, 487.000000), P2(496.000000, 548.000000), P3(329.000000, 238.000000);

                   

                  Red Curve control points:
                    P0(314.000000, 444.000000), P1(685.000000, 339.000000), P2(98.000000, 353.000000), P3(146.000000, 272.000000), P4(516.000000, 436.000000);

                   

                  The Intersection point(s) of those two curves:
                    (389.369694260, 418.874980154), (406.963141873, 410.637760315), (388.486672038, 360.281964254), (366.755538541, 354.242638725);
                    (399.378757587, 387.966095862), (373.797923544, 378.353180514);
                  Blue Curve's t value(s):
                    t[0] = 0.348859330, t[1] = 0.731874858, t[2] = 0.837820609, t[3] = 0.194321812;
                    t[4] = 0.785493970, t[5] = 0.242928969;
                  Red Curve's t value(s):
                    t[0] = 0.066832606, t[1] = 0.092449624, t[2] = 0.321249773, t[3] = 0.363412522;
                    t[4] = 0.910128111, t[5] = 0.885876885;

              • Re: Fast and precise INTERSECTION solution of cubic BEZIER curves
                Kevin De Smet

                I'm not sure how Parasolid handles this, but at least in ACIS, intersections aren't beziér mathemathic.

                Exactly because of what you said, it's not accurate enough.

                 

                You may want to look at this: http://doc.spatial.com/index.php/Intcurve

                  • Re: Fast and precise INTERSECTION solution of cubic BEZIER curves
                    Hunt Chang

                    Dear Mr. Smet,

                     

                    Thanks for your kind response and the information about Parasolid, ACIS and Intcurve. Frankly, I am neither a mathematician nor a mechanical engineer; my major study back to university long time ago was chemical engineering.

                     

                    I have read the link of Intcurve, it seems interesting. Besides the intersection of a cylinder and a spline surface, I think or I hope what I have learned to find out the precise intersection points of Bezier curves may help to extend Intcurve’s functionality to implement methods to solve the intersection in between spline surfaces too. However, I understand this is not just a call of my own.

                     

                    Thanks again,

                    Hunt Chang