2
$\begingroup$

How can I use AABBs (axis-aligned bounding boxes) to determine whether a line segment intersects a segment of a parabola with Bezier coefficients?

I have read a lot of articles talking about intersecting of two polygons or line and polygon. However, I cannot find any articles about intersecting of line and parabola.

I really want to know how to determine if they intersect each other.

$\endgroup$
1
$\begingroup$

If the line does not intersect the bounding box of the parabola segment, you know that the line does not intersect the parabola. Otherwise, further checks may be required.

For example, there is a polynomial (obtained by multiplying the homogeneous coordinates of the line with the adjoint of the matrix of the parabola) which is zero if the line is a tangent to the parabola. If it is not zero, the sign tells us whether the line intersects the parabola or passes it. Or one could write the line as a parametric equation, plug that into the equation of the parabola and examine the discriminant of the resulting quadratic equation.

But all of this is assuming an infinite parabola, whereas a Bézier curve will usually be finite and probably isn't a real parabola either but just approximating one. Which means you'd likely want to put the parametric form of the Bézier curve into the equation of the line, compute the three solutions there and then see which of them are real and in the range $[0,1]$. Solving cubic equations is no fun, but it's probably the appropriate thing to do unless you are really dealing with exact parabolas.

$\endgroup$
1
$\begingroup$

Your parabola can be expressed as a quadratic Bezier curve in the form $$ \mathbf{P}(t) = (1-t)^2 \mathbf{P}_0 +2t(1-t) \mathbf{P}_1 +t^2 \mathbf{P}_2 $$ If your line has equation $ax+by = c$, this can be written in vector form as $$ \mathbf{A} \cdot \mathbf{X} = c $$ Points of intersection occur at values of $t$ that satisfy the equation $$ \mathbf{A} \cdot \mathbf{P}(t) = c $$ Substituting $\mathbf{P}(t)$ from above, you get a quadratic equation for $t$, which you easily solve to get roots $t_1$ and $t_2$. There are three cases to consider:

  • If the roots are imaginary, there is no intersection.

  • If the roots are real and equal, the line is tangent to the parabola.

  • If the roots are real and distinct, there are two intersections with the infinite parabola. To check that these intersections lie on your portion of the parabola, just check that $t_1$ and $t_2$ lie in the interval $[0,1]$.

If you want a quick check ... see if the points $\mathbf{P}_0$, $\mathbf{P}_1$, $\mathbf{P}_2$ all lie on the same side of your line. If they do, the convex hull property of Bezier curves tells you that there can't possibly be any intersections.

No need for any AABB's.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.