1

I'm trying to find the intersection between a line segment and a quadratic bezier triangle for my OpenCL real time raytracer.

The main recomendations I've seen 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*D*S*T + 2*E*S*U + B*T^2 + 2*F*T*U + 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!

bubba
  • 43,483
  • 3
  • 61
  • 122
Alan Wolfe
  • 1,259

1 Answers1

4

A quadratic Bezier triangle is actually a Steiner surface, which has an implicit equation of degree 4. So, I would be very surprised if there was a way to do the intersection by solving a quadratic.

To get the implicit equation, you have to eliminate $S$, $T$, $U$. This is possible, but it's not easy. Look up "implicitization" or "resultants", or look at the numerous references in this paper. You might be able to use some of this code. Even if you did this, though, you'd still have to find the roots of a polynomial of degree 4 in order to do the intersection calculation, which is pretty messy. There is a well-known SIGGRAPH paper by Kajiya where he used exactly this approach to do ray-casting on bicubic patches. A bicubic patch has an implicit equation of degree 18, so it's much worse.

The easiest approach is to subdivide the Bezier triangle into planar ones, and then fire rays at these.

bubba
  • 43,483
  • 3
  • 61
  • 122