Intersecting two splines
Spline is an inexhaustible cruse. A simple polynomial with a straightforward geometric interpretation, but there are a myriad of things you can do with it, each of which can involve a unique technical challenge. A long list of topics in this primer demonstrates the point. This time I had to intersect two cubic splines (or two cubic Bézier curves since they are the same thing).
I surveyed (i.e. googled) relevant articles and papers and I’d like to share what I found.
There are mainly two approaches for spline-spline intersections: implicitization and subdivision. The former transforms the problem into a root finding of a polynomial in one variable. The latter finds (an) intersection(s) by recursively subdividing each curve involved into two sub-curves and removing pairs whose bounds don’t intersect at all until they can be properly approximated by lines. This basic subdivision approach is called Bézier subdivision. Interval subdivision is a variation of it, where the subdivision only happens where the tangent is either horizontal or vertical and known to be faster than the basic one. The literature seems to suggest the implicitization should be usually faster than subdivision-based approaches as long as the order of the curves are not too high (≤ 4). It becomes numerically unstable in higher degrees, also.
A third option (although it’s conceptually closer to the subdivision) is Bézier clipping. It iteratively clips one curve to the other’s fat line. A fat line is defined by two parallel lines that tightly encloses the curve’s control hull. This technique is known to be faster than the subdivision approaches. There is even a combo approach called a cocktail algorithm, where a subdivision approach is used to seed an implicitization one, which then computes the final intersections.
I ended up using Bézier subdivision for its simplicity. Another main reason was the availability of a credible implementation I can refer to. “Intersecting Parametric Cubic Curves by Midpoint Subdivision” in Graphics Gems IV explains the algorithm with a C++ implementation. It seems to run fast enough for my use cases, but when a push comes to a shove, I know which direction I should look further into to implement a faster one.
- A Primer on Bézier Curves — 25. Intersections: https://pomax.github.io/bezierinfo/#intersections
- 7.4 Computing the Intersection of Two Bézier Curves in T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes: http://www.tsplines.com/technology/edu/CurveIntersection.pdf
- A Comparison of Three Curve Intersection Algorithms: https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19850020280.pdf
- A cocktail algorithm for planar Bézier curve intersections: https://pdfs.semanticscholar.org/dfbb/c5b9d7e2bbfe1a624ec9f11718517aebac1f.pdf
- C++ code for the article “Intersecting Parametric Cubic Curves by Midpoint Subdivision” in Graphics Gems IV: https://github.com/erich666/GraphicsGems/tree/master/gemsiv/curve_isect
- Algorithms for Intersecting Parametric and Algebraic Curves: http://graphicsinterface.org/wp-content/uploads/gi1992-27.pdf