Detect&find intersection ray vs. cubic bezier triangle

Question

While writing a model editor, besides enabling raytracing I can think about couple of operations where I'd like to find an very good approximation about the intersection point between a ray and a triangular bezier patch.

How to do this? I know couple of ways but likely there's better ones.

Exact use-cases: I might want to use one bezier triangle patch as a reference surface for drawing detailed shapes with mouse. I might too want to pinpoint a splitting-point from such patch.

If there's C source code for it, I might like to see that too. Perhaps even use it instead of rolling my own code.

Answer 1

I'm not familiar with triangular bezier patch, but if it can always be contained within a triangle then, if the ray intersects the triangle, it must intersect the curve inside it too.

If the above is true, then you can search the curve between the two vertices whose side intersects the ray for a point that is close enough to the ray. I guess you can do binary search on the curve parameter in this region to get that point.

Answer 2

I'd suggest that you implement Triangular Bezier Clipping (PDF).

However, another possibility would be to convert your triangular patch to a tensor-product Bezier patch. The advantage of doing this is that there is a lot more support for tensor-product Beziers so you're more likely to find some code that you can use. The conversion is simple:

• View your triangular patch as a series of n+1 rows of control points (where n is the degree)
  • The first row has 1 control point, and each row has 1 more control point than the last
• Now, treat each row as a Bezier curve of the appropriate degree (degree 0 to degree n)
• Degree elevate each row to degree n
  • Each row will now have n+1 control points, forming an n+1 by n+1 grid of control points
• This grid of points, taken as a degree n by n Bezier patch, is an identical surface to your triangle

For just finding points of intersection this should work just fine. However, your tensor-product patch is degenerate (you have coincident points at one end) so you might find that you're introducing some numerical problems as you approach the degenerate corner. Also, mapping back to the triangular domain might make things like texture mapping a little extra tricky. So I'd suggest you use the more direct Triangular Bezier Clipping if you don't mind a bit of implementation.