I'm trying to find the intersection between a line segment and a quadratic bezier triangle for my OpenCL real time raytracer.
This question Detect&find intersection ray vs. cubic bezier triangle talks about finding the collision point between a ray and a cubic bezier triangle and the main recomendations are to try subdivision, or tensor product bezier patches.
I've read in a few places that when testing a line segment against a quadratic bezier triangle, that you just end up having to solve a quadratic equation, but I haven't found any information on what that equation actually is and am starting to wonder if it's true. My attempts to find it also have come up short so far :P
Does anyone know if this is true or how to solve it besides using subdivision or tensor product bezier patches?
Here's the equation for a quadratic bezier triangle:
AS^2 + 2*DST + 2*ESU + B*T^2 + 2*FTU + C*U^2
Where S,T,U are the parameters to the triangle. You could replace U with (1-S-T) since they are barycentric coordinates.
A,B,C are the corners of the triangle, and D,E,F are the control points along the edges.
Super stumped on this one!
Line segment has parametric equation P = P0+(P1-P0)*v=P0+d*v, where v is parameter [0..1]
To find intersection with brute force, you have to solve system of three quadratic equations like
x0+dx*v=AxS^2 + 2*Dx*S*T + 2*Ex*S*U + Bx*T^2 + 2*Fx*T*U + Cx*U^2
This system has 8 possible solutions, and intersection(s) exists only if resulted v,s,t lie in range 0..1 simultaneously. It's not easy to solve this system (possible approaches - Gröbner basis, numerical methods, and solution process might be numerically unstable). That is why subdivision method is sometimes recommended.