Bezier/Ray intersection

Drilian · 2004-11-30T22:52:22+00:00

Is there a good, fast way to calculate the intersection between a cubic Bezier patch and a ray, without making the bezier into mesh and generating a quadtree of bounding boxes (with quads as leaves)? Google hasn't been my friend in this regard. The SSX article on Gamasutra about their terrain mentions that doing collision against bezier patches is mathematically simple, but they don't touch on that part of things (not in the article's scope). That method works and all, …

Depends. Are you talking about arbitrary Bezier patches or well-constrained, well-defined Bezier patches?

First let's review the Three Ways of Doing Ray Intersections:
- Analytical methods (plug values into a formula, basically)
- Iterative methods (test, refine, repeat)
- Approximation methods (represent the geometry as something easier to intersect; the most common tactic here is polygonization or tesselation)

For arbitrary Bezier patches, analytical methods produce very, very ugly differential equations. I do not believe anyone has found a reliable, general solution for the intersection of a ray with an arbitrary Bezier patch. This leaves us tesselation (which is obviously out) and iteration.

There are some cases, however, where Bezier patches follow good parameters; for example, patches that are functions in two variables [i.e. there is at least one axis along which the patch never "overlaps" itself] can be analytically solved (sort of) by doing some mathematical simplification and accepting some very slight distortions. This is fairly complicated, though, and generally means not actually intersecting Bezier patches per se. This is also not the best route unless you are willing to dig very deep into the mathematics of the curves. Personally, I've only argued (but not even proven) that this approach works for well-constrained patches. I've never had the time or interest to actually come up with a full solution.

The remaining option is iteration. Basically you have two families of iterative solvers you can tackle: root solvers and ray marchers. Again in well-defined situations you can sometimes use methods like Newton/Raphson to find roots of the intersection equation. This is ugly, though, and places very heavy constraints on the patch itself. By the time you subdivide an arbitrary patch heavily enough to have a good chance of being able to even use a root finder (esp. Newton/Raphson) you may as well tesselate to polygons.

So we're back at the point everyone finds themselves reaching eventually with this problem: we either subdivide, or we ray march. Ray marching (in case you aren't familiar with it) is basically just checking the ray at many points along the ray, and seeing if you can find a point that hits (or comes close to hitting) the patch. Usually you can do some guessing to find points that lie on either side of the patch (and also lie on the ray in question, of course) and then bring those points closer to each other until you find an intersection.

There are tricks you can use to discard a lot of wasted calculations in a ray marcher for Bezier patches - but unfortunately (for the best tricks anyways) they again require a lot of the same well-behaved characteristics that are needed for other intersection methods.

Of course this is all based on my 2 year old research work so it is quite possible that I've not been introduced to an effective intersection method for arbitrary Bezier patches. Unless you are very sneaky with your math and optimizations, you'll almost always get better performance from a good solid tesselation and spatial subdivision scheme than trying to handle ray marching on arbitrary patches. The question is really more a matter of memory consumption (as you mentioned) and resulting image quality, although with proper normal filtering a tesselated patch can be very hard to distinguish from a more refined test.

Topic Locked