0 Replies Latest reply on Dec 26, 2013 1:56 AM by hunt_chang

    A Super Fast Solution of intersections for Bezier Curves

    hunt_chang

      Merry Xmas and Happy New Year to everyone,

       

      Last year I had presented my solution here about finding all of the intersection points in between two Cubic Bezier curves plus its self-X, and now I am going to show you my new X points solution for QuarticBez too. Besides that I have also enhanced the precision level of my solutions, all the deviation can be controlled in the level no higher than 1.0e-9, which means my solutions are ready to be used as a stable tool for various kind of application now.

       

      4X4-AMD.png

       

      DataZoom Picture

      Blue Curve: degree 4, control points,
        P0(365.00, 234.00), P1(702.00, 6.00), P2(15.00, 270.00), P3(800.00, 411.00), P4(321.00, 159.00);

       

      Self Intersection point at:
        S0(422.623866578220830, 219.100707365751530);  t[0] = 0.470568235168694, t[1] = 0.928965105280191;
        S1(403.771414449105410, 206.564631127658800);  t[2] = 0.033644311244951, t[3] = 0.946215379164179;
        S2(428.146585044641600, 187.490098585855800);  t[4] = 0.063282793880594, t[5] = 0.384577459709910;


      Red Curve: degree 4, control points,
        P0(289.00, 219.00), P1(619.00, 281.00), P2(433.00, 42.00), P3(244.00, 99.00), P4(566.00, 340.00);


      Self Intersection point at:
        S0(433.839624042999790, 220.171822083503030);  t[0] = 0.169622726530818, t[1] = 0.847996997510708;


      The Intersection point(s) of these two curves:
        X00(373.132669769454200, 228.452384975740300), X01(422.976765319260100, 223.603384644635180), X02(427.328608685923310, 222.394565648216480);
        X03(453.238364069660750, 164.255182274873330), X04(447.975296939753890, 157.993040158902660), X05(423.163860704513580, 206.415509255545150);
        X06(416.528839850635050, 196.830100491660910), X07(454.443486880512640, 243.396391744401060), X08(472.693821439787600, 261.766619105502170);


      Blue Curve's t value(s):
        t[00] = 0.006206970900832, t[01] = 0.482580691766434, t[02] = 0.924118404044710;
        t[03] = 0.115684858451726, t[04] = 0.278944240069076, t[05] = 0.436819858435325;
        t[06] = 0.047883985834167, t[07] = 0.888939387836823, t[08] = 0.847857157064769;


      Red Curve's t value(s):
        t[00] = 0.076900012265960, t[01] = 0.147590072801383, t[02] = 0.155924661830965;
        t[03] = 0.398565884526332, t[04] = 0.426824837981717, t[05] = 0.824218211537170;
        t[06] = 0.806057750545920, t[07] = 0.883703196233528, t[08] = 0.909078781554686;

      4X4z-AMD.png

       

      Header 1
      3X3-AMD.png

      Blue Curve: degree 3, control points,
        P0(315.00, 52.00), P1(29.00, 321.00), P2(367.00, 281.00), P3(293.00, 45.00);

       

      Self Intersection point at:
        S0(298.949925280094930, 67.407618892325132);  t[1] = 0.019529538620305, t[2] = 0.967466278888468;


      Red Curve: degree 3, control points,
        P0(194.00, 95.00), P1(555.00, 261.00), P2(30.00, 88.00), P3(317.00, 114.00);


      Self Intersection point at:
        S0(235.355982130217680, 114.368935343872980);  t[1] = 0.042499014859523, t[2] = 0.843266088117618;


      The Intersection point(s) of these two curves:
        X00(249.020451741775960, 120.965581849421540), X01(300.199405205105680, 147.395573402130050), X02(296.397482594187810, 161.709774790957060);
        X03(238.046489588316890, 134.598419235671570), X04(257.136801594420720, 111.455978116500300), X05(303.881295989673330, 112.905702043116350);


      Blue Curve's t value(s):
        t[00] = 0.095900097495871, t[01] = 0.830834081410266, t[02] = 0.801013743091780;
        t[03] = 0.118159081452121, t[04] = 0.081168420861567, t[05] = 0.894691324927957;


      Red Curve's t value(s):
        t[00] = 0.059034581916642, t[01] = 0.144695830927720, t[02] = 0.455144046486331;
        t[03] = 0.665309525636102, t[04] = 0.908115561552037, t[05] = 0.984051799035192;

       

      In the above two examples, I have presented the data of intersection points in between two curves, self-intersections within each single curve, the coordinates of those X points and their responsible t values and each of their control-points for your reference. Welcome for anyone to challenge the correctness and precision of these data!


      From now on, I believe these solutions that I found would not only enhance our CAD design capability but it would also deeply changing the curve smoothness of those 3D models and their animation show in video and display. If you feel interested about my work and wish to know how fast my solutions can run? Welcome to visit my site at https://sites.google.com/site/curvesintersection/


      Hunt Chang