Intersect Line vs Quadratic Bezier Triangle

2
votes

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!

1
c++mathraytracingbezier
As this concerns finding a formula, rather than the C++ algorithm of same, possibly better asked on math.stackexchange.com? - Jongware

1 Answers

0
votes

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.