Sign in to follow this  
Drilian

Bezier/Ray intersection

Recommended Posts

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, but it's a bit memory hungry. Any suggestions? Thanks much, Josh

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
It's kind of a pain to implement, but it works really fast and gives great results. Works with any patch with arbitrary degrees in either dimension.

Clicky

karg

Share this post


Link to post
Share on other sites
Thanks for the great answers, guys!

I'll definitely try that two-plane method sometime, but yeah, it sounds like a pain to implement (though it's definitely interesting).

I think, for now, I'm sticking with the meshing that I have. It uses up some extra memory, but it's fast and it's done.

But one of these days I'll definitely try to whip together the two-plane deal. It's cool!

Thanks again!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this