Number of Quadratic Bezier Curve-Ray Intersections

Question

Given some quadratic bezier curve $B(t)$ and some ray $R$ is there an equation to calculate the number of intersections between the two. (For my application I only need to consider 2d space).

Answer 1

After a suitable choice of coordinate system, you can assume that the ray is the positive $x$-axis.

Let $A, B, C$ be the control points of the quadratic Bézier curve, and let $A = (a_x,a_y)$, $B=(b_x,b_y)$, $C=(c_x,c_y)$. Let $n$ be the number of intersections.

A lot of intersection testing depends on the fact that the curve lies inside the triangle $ABC$. Or, if you want a tighter check, the curve lies inside the trapezoid with corners $A$, $\tfrac12(A+B)$, $\tfrac12(C+B)$, and $C$.

If $a_x<0$, $b_x<0$, and $c_x<0$, then $n=0$.

If $a_y, b_y, c_y$ all have the same sign, then $n=0$.

If $a_y$ and $c_y$ have opposite signs, then $n=0$ or $n=1$. To distinguish, you have to find quadratic roots. See below.

If $a_y$ and $c_y$ have the same sign, and this is different from the sign of $b_y$, then $n=0, 1$, or $2$. To distinguish, you have to calculate quadratic roots. See below.

Quadratic solving. To find intersections with the entire $x$-axis, you need to solve the equation $(1-t)^2 a_y + 2t(1-t)b_y + t^2c_y = 0$ for $t$, and check that $t \in [0,1]$. Then, to find intersections with the ray, check whether the intersection points you found have $x>0$ or not.

In many cases, you end up solving the quadratic. All the special-case testing is just speed-ups to avoid doing this. If clean simple code is more important than speed, you could just ignore all the speed-ups.

Answer 2

We have $B(t) = b_0 + b_1 t + b_2 t^2 $ and $ R(s) = r_0 + r_1 s $, where $b_0, b_1, b_2 , r_0, r_1 $ are 2D vectors, and we want solutions to $B(t) = R(s)$

So we have the equation:

$ b_0 + b_1 t + b_2 t^2 = r_0 + r_1 s $

To solve these coupled equations, eliminate $s$ by pre-multiplying (dot product) by a vector that is perpendicular to $r_1$. Let this vector be $r_2$ then,

$ r_2 \cdot b_0 + (r_2 \cdot b_1) t + (r_2 \cdot b_2) t^2 = r_2 \cdot r_0 + 0 $

where the $0$ at the end comes from the fact that $r_2 \cdot r_1 = 0$

Now we can solve this last equation using the quadratic formula, and this will give the solutions of the intersection.