Happy New Year of 2014 to Eyeryone,
I believe people in this forum all knew about the importance of the role that Bezier curves play in spline, NURB and BezSurface. However have you noticed about what is/are the bottlenecks for the development of Bezier curves application now? The answers are INTERSECTIONs, yes, without knowing how to calculate the X points then we have no way to do intersection or union operation on two curved 3D objects, and we have no way to turn the cyberspace model into the real object via modern tooling equipment.
Actually, there are two intersection problems exists. The first is the intersection in between two curves, and the other is the self-intersection within a single piece of curve that degree higher than 2. But none of them were solved effectively. For the word, effectively, I mean speed, precision and reliable algorithm in computation.
I am lucky; these two problems were both solved by me recently, although not for all of the degrees of Bezier equations, at least my solutions have covered all of the QarticBez and its lower degrees.
Please watch the two examples below,
Blue Curve: degree 4, control points,
P0(371.00, 260.00), P1(724.00, 186.00), P2(48.00, 495.00), P3(661.00, 42.00), P4(413.00, 296.00);
Self Intersection point at:
S0(455.902657442980850, 248.853167930552760); t[0] = 0.092718516351902, t1 = 0.939607166294112;
S1(425.380974977201160, 283.138268801903850); t[2] = 0.407457403839644, t[3] = 0.986605554277053;
S2(426.115425984051290, 250.526806971848490); t[4] = 0.048640611559787, t[5] = 0.636811848725635;
Red Curve: degree 4, control points,
P0(533.00, 295.00), P1(149.00, 123.00), P2(733.00, 540.00), P3(351.00, 9.00), P4(456.00, 341.00);
Self Intersection point at:
S0(439.963577515214870, 277.557110805707680); t[0] = 0.401821150246398, t1 = 0.938865129951906;
S1(437.831998810208860, 257.861134988211750); t[2] = 0.087866243509813, t[3] = 0.909106859723019;
S2(468.462644343283960, 268.197502390556620); t[4] = 0.051304467776450, t[5] = 0.555981559846350;
The Intersection point(s) of these two curves:
X00(466.579459420955800, 267.499484920340930), X01(446.147203725592140, 260.414871422103940), X02(423.097478885403520, 254.080511685652250);
X03(412.344875925004770, 252.398459664892810), X04(402.200583198759660, 254.030751459022160), X05(414.226944475466610, 268.218099973440640);
X06(432.248644542682650, 275.817609058829930), X07(446.804205363685070, 278.239701808838900), X08(468.807649527654010, 250.852412531259940);
X09(469.657927100854070, 264.893519899947020), X10(448.797084053772320, 229.869093268079040), X11(463.077138021720660, 239.574170384463740);
X12(437.858579336712860, 249.356225284822640), X13(440.347959950999670, 236.622242560195560), X14(438.726177908239150, 268.754229943338490);
X15(440.447455920833870, 280.445063745813800);
Blue Curve’s t value(s):
t[00] = 0.245112204267493, t[01] = 0.958045193678799, t[02] = 0.621952566302739;
t[03] = 0.034112962806997, t[04] = 0.024658022585075, t[05] = 0.557038542874050;
t[06] = 0.978212780246328, t[07] = 0.322865367399017, t[08] = 0.127924150406712;
t[09] = 0.228880001849709, t[10] = 0.726393444220495, t[11] = 0.921352319395217;
t[12] = 0.063215326669565, t[13] = 0.695056499474300, t[14] = 0.969448994282444;
t[15] = 0.346019487697714;
Red Curve’s t value(s):
t[00] = 0.053205811926179, t[01] = 0.076488780025450, t[02] = 0.112774162492991;
t[03] = 0.138569474933576, t[04] = 0.189744116269478, t[05] = 0.303263677322753;
t[06] = 0.373052741950167, t[07] = 0.428600031611513, t[08] = 0.646679378477882;
t[09] = 0.575693989027728, t[10] = 0.793832717980899, t[11] = 0.703150938171656;
t[12] = 0.892120696978707, t[13] = 0.854664994695693, t[14] = 0.926747138086845;
t[15] = 0.942532240341765;
The second example,
Blue Curve: degree 3, control points,
P0(370.00, 221.00), P1(7.00, 8.00), P2(585.00, 180.00), P3(222.00, 119.00);
Self Intersection point at:
S0(244.646098114262740, 122.699707589739630); t1 = 0.256248871475793, t[2] = 0.977964451416986;
Red Curve: degree 3, control points,
P0(227.00, 163.00), P1(578.00, 9.00), P2(35.00, 209.00), P3(350.00, 122.00);
Self Intersection point at:
S0(277.240427333488360, 140.629231631353920); t1 = 0.055190048669257, t[2] = 0.895248938479235;
The Intersection point(s) of these two curves:
X00(262.081349965615690, 147.460329361805290), X01(299.559189428988250, 130.378114294164820), X02(323.328115372298040, 119.029379523348150);
X03(307.784731939498220, 115.212199932340110), X04(276.755759433939260, 127.483131403575780), X05(253.386659654220780, 138.575718006584620);
X06(258.665112121649940, 144.182296024790960), X07(313.502584100320290, 131.807230832740370), X08(339.987435657623790, 124.747690206191070);
Blue Curve’s t value(s):
t[00] = 0.154822478881377, t[01] = 0.908324265399822, t[02] = 0.588828574592916;
t[03] = 0.536833423698564, t[04] = 0.941070774416274, t[05] = 0.184369457385322;
t[06] = 0.165166932160431, t[07] = 0.883553565814128, t[08] = 0.660541535043594;
Red Curve’s t value(s):
t[00] = 0.036655991421130, t[01] = 0.087151092060734, t[02] = 0.132077316848999;
t[03] = 0.481542394437451, t[04] = 0.582059416854899, t[05] = 0.682353823370885;
t[06] = 0.844353380476236, t[07] = 0.956340747611069, t[08] = 0.989082447477011;
In the above two examples, I have presented the data of intersection points 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. The Bezier equation of Cubic & Quartic should be easy to find via Google or Wikipedia, welcome for anyone to challenge the correctness and precision of these data!
I believe my solution would influence CAD and other tools development to change it into a more advanced level and it will also change the smoothness of curve form that displayed or animated in our screen too. If you feel interested about my work and wish to know how fast my solutions can run? Welcome to visit my site (https://sites.google.com/site/curvesintersection/).
Hunt Chang