Intersect Line vs Quadratic Bezier Triangle

Question

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!

Answer 1

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.

Answer 2

when your bezier patch has more than 3 sides, ray-intersection is no longer analytic (even if the splines on the side are only quadratic) and a precise enough iterative approach is significantly slower. Bezier patches are pathetic in terms of performance due to inherent recursion, you may want to do FFT for fourier-patches instead. Shadertoy.com [iq] has various "twisted cube intersection"s (that are not iterated by sphere-tracking==raymarching, which is efficient, but also causes MANY low-precision-cases-artifacts, where ever convergence of iteration is too slow).

yes, triangular-bezierpatch intersections has only analytic quadratic complexity (with quadratic beziers on the borders), but it involves some pre-computation (unless it is already in barycentric coordinates), that significantly lower the resulting precision (barycentric adds 1 division globally, and sums up over all domains)

This was solved (poorly, as in it has 1 error case and too low precision) on shadertoy in opengl in 2019: https://www.shadertoy.com/view/XsjSDt and i optimized it slightly (fixed precision issues, added camera and culling): https://www.shadertoy.com/view/ttjSzw + https://www.shadertoy.com/view/wlSyzd also see, https://www.reddit.com/r/askmath/comments/sfn8mk/analytic_intersection_ray/