Bezier Intersection

• The reason that limited my solving capability is because I need tool to dump out the raw polynomial equations for higher degree Bez-X problems solving (for which I have not foud any adaptable solution from current soft market yet).

Why Bezier curve?

• Nature, Simple and intuitive

• Control flexibility

• Fast computation

Bezier curve’s basic form and formula

My interest about CURVE is focused on the practical usage on CAD and CAM. So I would suggest that we concentrate on the most common used low degrees of Bezier formulas of below, and you can see they are simle and pretty easy to be calculated by computer.

If you are interested about the whole picture of Bezier curves, please take references from the Wikipedia's links here, Bezier curve.

Bezier curve is Nature curve:

If you throw a stone to sky, it flys with a parabolic curve up and down to the ground finally. The parabolic curve you saw is a most common and familiar example of a Bezier curve of degree 2 to us. 

So, if you draw a Bez2 curve, you can deem it as a moving particle started from Pa which moving to the direction of Pb in 2D space as a linear VECTOR, Lab; and this Lab is pushed away by another linear VECTOR, Lbc, then you get your Bez2 curve, Vabc.

In other words, a moving particle that moved in a parabolic path, Quadratic Bezier Curve path, can also be described as a curled VECTOR, Vabc (started from Lab and move to the direction of Lbc).
   Lab = Pa + (Pb - Pa) * t == Pa * (1 - t) + Pb * t
   Vabc = Lab + (Lbc - Lab) * t == Vab * (1 - t) + Vbc * t

Again, a Cubic Bezier Curve Equation can be legally described as
   Vabcd = Vabc + (Vbcd - Vabc) * t == Vabc * (1 - t) + Vbcd * t

So on and so forth, we can describe all of the rest of higher degree of Bez-curve in the same linear style.

Interesting Property 2

If you convert a Bezier curve into its polynomial form, then you can dump out its control-points easily.

Take the above two sets of expressions as examples, the coefficient of c0 is just the coordinate of pa, and then you can get pb out from the coefficient of c1 easily and et cetera.

So any polynomial of single variable with real-coefficients can be switched back and forth into a one-diemensional Bezier curve form.

If you think it deeper, you would find out that every Single variable with Real coefficients polynomial is also an one-dimentional Bezier curve, just like this form below:

As you can see, if you combined any two of Single-Variable-Polynomials then you can get a 2D Bezier Curve, and if you combined any three of them then the synthetic curve will be 3D.

What are Bezier cuurve’s Problems?

It is pretty common that we use Line, Arc, Curve as our design tool to draw the engineer-drawing, and it is also common for us to handle the intersection-points problems that generated by these primitive tools for CAD/CAM application.

Before my solution, there is one major difficulty emerged in the practical usage of Bezier curve. As we knew how to solve the intersection in between Line, Arc, Oval, Hyperbola and etc, but we don't have a convincible and reliable way to solve the intersection-points of Bezier curves?

Especially Bezier curves are living in the parametric domain!

• How to find out the Intersection-Point(s) in between two Bezier curves? 

• How to find out the Self-Intersection-Point(s) within a Bezier curve?
  A 2D cubic degree Bezier curve or higher may have Self-X point(s).

• How to simulate a data sample of 2D curve-segment with Bezier curve automatically?

For the first two INTERSECTION problems, I have solved the most common parts of them, like Quadratic, Cubic and Quartic degrees, in the year of 2014. 

Regarding to the Self-Intersection part, I have solved them for both Cubic and Quartic degrees. 

For the Intersections in between two curves of same-degree, the topmost degree I can solve is Quartic-by-Quartic (Bez4 X Bez4); and the upmost mixed-degrees is Quartic-by-Quintic (Bez4 X Bez5).

To the last Simulating problem, there are certain good algorithms, and most of them are based on Least-Square-regression data analysis.

Personally, I am focusing on how to reverse-engineering a common used Bezier curve with degree + 2 data samples (ex. it means to find out a cubic Bezier curve equation with 5 points of data in the order of t0 < ta < tb < tc < t1, and ta, tb, tc are all unknown).  Because I believe this kind of method is a required tool to decompose a piece of continuous-curve that looks like NURBS.

Bezier curve and Nurbs

The most common Bezier curve is Cubic degree Bezier curve, because it can offer both tangential and curvature continuous (so called G2 continuity) at any point of the curve itself. However, this is the common understanding of the most of people today, who knows about tomorrow?

In Bezier curve category, a higher degree curve is smoother than a lower degree one, but it also spends more CPU-cycles to calculate and draw it onto screen or printer. So it is the reason why Cubic Bezier curve becomes the best optimization tool for the designer.

However, Nurbs just like Bezier curve, is very difficult to calculate the intersection-points in between two curves.

But, the good news is I found the way to convert Nurbs into PolyBez curve, and actually after conversion the resulted PolyBez is fully equal to its original Nurbs in math. 

So if you wish to find out the intersection-points in between two Nurbs curves, you can still count on my solutions of Bez-X.

Please visit my Nurbs-2022 website to get a detail reference.

Features of my X solution

Before I presented my Bezier intersection-points solution on my old website in 2015, there were just a few algorithms like Bezier-Clipping and Geometric-Intervals to solve the X-points of Bezier curves, and they are all using approximation methods with bad efficincy. 

My solutions are different, and they should be the first set of general solutions in the whole world to solve the X-points of Bezier curves via direct and precise math methods.

• My solutions were solved by both geometric and algebra properties of Bezier curves.

• The final solutions of mine are all in the form of polynomial equations which were derived from a bunch of simultaneous parametric equations of different degrees of Bezier curves.
  Ex, the Bez-X solution of two Cubic-Bezier curves is a 9 degree polynomial, and the Bez-X solution in between a Quadratic-Bezier and a Quintic-Bezier is a 10 degree polynomial.
  So if there are any X-points in between the two curves of your question, my equations won’t be missed any of them in anyway.

• The same property of above is also true to the Self-X solutions of Bezier curves of my solutions.

• My solutions are all robust, reliable and real time.
  Please watch the demo video to make the judgement by yourself.

• Since I have learned to solve the X-points in between Bezier curves, it is much easier for me to solve the X-points in between Bezier curve and the other primitive geometry shapes like Line, Arc, Oval, Hyperbola and etc.

The barrier to my research progress so far

As I mentioned above, yes, I have set up a paradigm to solve the intersection points in between two parametric equations. In theory, I shall capable to solve Bez5 X Bez5 (Quintic degree of Bezier curve) or Bez6 X Bez6 or even higher degree ...

However the truth is, I have not found any suitable software to dump out the whole series of 25 degree of polynomial for the solution of Bez5 X Bez5 (this is the major problem I am facing, but there are still a few more). So either I have to wait for a new software or I shall spend time to write a specified math tool for my own use.

Anyway it takes time, and the new math tool is not the first priority of mine now.