Sign in to follow this  

Swept Sphere AABB tests

This topic is 3572 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm looking for algorithms for sphere aabb sweep tests, but I can't seem to find anything on GD.net or Google (maybe my searching skills are deteriorating??) Does anybody have any good resources for an efficient/quick swept sphere-aabb algorithm?

Share this post


Link to post
Share on other sites
You are essentially looking for a capsule vs aabb test, searching for that on google present you with a wealth of information. To make a good pick you should think about what information you need, is knowing that the objects intersect or not good enought, or do you need penetration depths and such.

Share this post


Link to post
Share on other sites
For swept sphere vs. AABB, a couple of options come to mind:

1. CSO raytracing using GJK

2. 'Manually' raytracing the CSO

The CSO of a sphere and a box is a 'rounded' box. Raytracing this object can be done in a number of ways. The simplest (but least efficient) method would be to raytrace the boxes, finite cylinders, and spheres that form the rounded box, and take the first of any hits that occur. A more efficient method (although I couldn't say for sure that it's the most efficient method) is to use 3D-DDA to walk through the 'zones' of the rounded box, testing the primitive (rectangle, quarter-cylinder, or eighth-sphere) associated with each zone as you go.

I remember working on an implementation of this latter method. I think I finished it, but I'm not sure if I ever finished 'polishing' it.

You might also try geometrictools.com. IIRC, swept sphere vs. box is among the intersection tests included in the Wild Magic intersection library.

Share this post


Link to post
Share on other sites
Cool, maybe if I tell you guys what I'm doing you could point me in the direction of what you think would work best. I'm testing a moving sphere against an octree to get a list of possible triangles to further test against, so I don't need any information on depth penetration e.t.c. I simply need to know whether it has intersected or not.

Out of curiosity, how efficient are capsule-aabb tests compared to similar shapes such as cylinders-aabb?

Share this post


Link to post
Share on other sites
Quote:
Original post by Rajveer
Cool, maybe if I tell you guys what I'm doing you could point me in the direction of what you think would work best. I'm testing a moving sphere against an octree to get a list of possible triangles to further test against, so I don't need any information on depth penetration e.t.c. I simply need to know whether it has intersected or not.
In that case, I wouldn't bother with a swept test (even a Boolean one). I'd just create an AABB large enough to fully contain the object over its path of motion, and test that AABB against the octree.

Share this post


Link to post
Share on other sites
Hmm, I was thinking of doing that, but I'm a bit wary of adding polygons to the list that def won't intersect. I guess the question is would AABB-AABB and more capsule-polygon tests be quicker than capsule-AABB and less capsule-polygon tests? How much slower are capsule-AABBs than AABB-AABB?

As a side note, is there a rough guideline on how much larger my octree nodes should be compared to my object with motion, for reducing the amount of octree usage? Or should I be profiling the code with different sizes?

Share this post


Link to post
Share on other sites

This topic is 3572 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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