A group of solutions for the intersection problems of Bezier curves


#1

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


NURBS intersection solution
#2

Hello,
Thanks for this article.
Actually do you know an algorithm that can reduce number of Bezier curves. This algorithm takes two or more curves and merge them to generate just one Bezier curve which keep the same caracteristics as others ( cubic + cubic —> cubic )

Thank you.


#3

Hi there,

Thanks for your question.

I guess you are looking for an algorithm to optimize the data of spline
curves or the nurbs drawing. However, I do not know any existing
algorithm which can do that, but my know-how about how to identify any
two degree 3 of Bezier curve segments either belong to the same piece of
curve or not, may do some help.

As you can understand, if you would like to merge two pieces of
connected curve segment into one, then in theory, they must belong to
the same curve (a longer one). But in practical, it involves how many
digit of precision you are looking for? If you are looking for a lower
or general CAD drawing precision, ex. 2 or 3 digits may be, then you
would have much more choices to simulate the two target segments that
you got into a new one than in the higher precision required condition.
So I guess if anyone would like to develope an algorithm to do the job,
this may be a tip that I can offer now.

If you have any further question about this topic, please leave me a
message on my website.
Hunt Chang