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?

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.

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.

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?

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.

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?