Finding Catmull-Rom Spline and Line intersection. Part 2: Mathematical approach
As far as I can tell there’s no open-source solution out there for this problem to date. Maybe it’s trivial for those with significant mathematical knowledge, but for those who are just starting to get familiar with the foundations of splines this problem may just seem too intimidating. As a result they might resort to a much worse solution they’re comfortable with. So did I at first.
So let this article be a guide for a solution. I will explain the math and also provide an implementation in Java using the libGDX library.
That said if you’re a least bit interested I’d recommend you trying to solve this for youself. All you need is some basic understanding of the Catmull-Rom Spline equation and the Line equation. As a hint I recommend reading this post. Though it actually contains a flaw it will put you on the right track.
Since the first release of this article Bit Barrel Media did a C# implementation based on this and also included it in the Math3D Unity wiki. :)
Catmull-Rom formula
To determine a point on the Catmull-Rom Spline we need the 4 sorrounding control points (P0, P1, P2, P3 , predefined), a knot parameter (alpha, predefined) and a value in range of 0–1 (t) that will tell which point of the Spline we’ll get.
The formula can be written as:
q(t) = alpha * ((2*P1) + (-P0+P2) * t + (2*P0–5*P1 + 4*P2 — P3) * t² + (-P0 + 3*P1–3*P2 + P3) * t³))
Which (if we disregard the predefined values) is a simple Cubic equation:
a*t³ + b*t² + c*t + d = 0
Where
a = alpha*(-P0 + 3*P1–3*P2 + P3)
b = aplha*(2*P0–5*P1 + 4*P2 — P3)
c = alpha * (-P0+P2)
d = aplha * (2*P1)
Our points (P0–3) consist of two variables: the x and y coordinates. They’re independent so we can handle them separately. Let’s say:
x = a1*t³ + b1*t² + c1*t + d1
y = a2*t³ + b2*t² + c2*t + d2
Where e.g. ‘a1’ is ‘a’ with the x coordinates substituted for each P point and ‘a2’ is ‘a’ with the y coordinates substituted for each P point and so on with b, c and d.
Line formula
Ax+By+C=0
Not much to see here, move along…
Combined formula
Substituting the values of x and y from the separated Spline formula into the Line formula we’ll get:
A*(a1*t³ + b1*t² + c1*t + d1) + B*(a2*t³ + b2*t² + c2*t + d2) + C = 0
Rearranged:
(A*a1 + B*a2)*t³ + (A*b1 + B*b2)*t² + (A*c1 + B*c2)*t + (A*d1 + B*d2 + C) = 0
This is again a Cubic equation, combined from the Line’s and the Spline’s equation. If you solve this you can get up to 3 real roots for t.
You remember that t is ranged from 0 to 1, right? Choose those that fit, substitute them into the Spline formula we first talked about and you have the intersection point(s).
If none of them fits they don’t intersect. If more than one fits there’s more than one intersection (3 possible with a knot as seen on the uniform spline here). In case you only need one intersection point you should examine all possibilities and make a conscious decision (e.g. take first/last point on the Line/Spline) otherwise the outcome might be random.
Multiple spans
The above solution is simplified to a Spline with 4 control points (1 span). What about Splines that has more spans?
You have to do the same calculation for all spans using their 4 surrounding control points. Keep in mind that there may be intersections in every span.
Implementation
The code (alongside with other Catmull-Rom utilities) is available on GitHub. The Span class takes care of the math, it takes values needed from the Line class’ interface. Finally, the Spline class’ intersect(Line) method will gather the results. There’s a desktop demo where you can try it for yourself.
Originally published at my old blog on October 17, 2016.
