What has the most efficient intersection test against an AABB tree - OBB, Cylinder or Capsule?

Question

I'm currently trying to find collisions in 3D between a tighter volume than an AABB and a tree of AABB volumes. I just need to know whether they are intersecting, no closest distance or collision response. An OBB, Cylinder or Capsule would all roughly fit these purposes but Cylinder and Capsule were the first thing I thought of, which I have found little information about detecting intersections online. Am I right in thinking that they would always be more complex to perform Separating Axis Tests on even though they might seem like simpler shapes? I figure by the time I get my head around SAT for curved shapes I could have done the thing with OBBs but I wanted to find out for sure.

Answer 1

Little bit of necromancy here, but somehow it came back to the top of the list already today, and while a comment covers the idea, there aren't any actual answers yet. For the benefit of future readers:

The idea behind using an Axis Aligned Bounding Box, or in the 3D case a bounding cube, is that you can quickly disqualify some number of your potential collisions through a series of relatively cheap comparisons to the effect of if(A.top < B.bottom) continue;

The (hopefully) much smaller set of objects that pass the AABB collision test may then go on to more accurate, but computationally expensive checks. In my experience, the time you save by quickly disqualifying the obvious non-collisions will "almost always"(tm) be greater than the time you "waste" by testing some objects twice. "Usually"(tm) it is significantly greater.

---

For the super serious out there, use of "quotes"(tm) indicates evidence which is, at best, anecdotal, and should not be taken as The Final Word. Special cases abound. If you think you have one, profile it and find out if you're right.

Answer 2

For OBB to cylinder tests, you can use an OBB to line-segment/ray test and expand the OBB by the radius of the cylinder. This produces slight error in the corners but if you can suffer that little bit of accuracy loss, it is a pretty fast and simple way.

In Christer Ericson's book, "Real Time Collision Detection", He details how to test a line or ray against 3 slabs that intersect at the OBB. The OBB is simply a Matrix & 3 half-widths which are used to create the 3 slabs. If the line segment intersects all 3 slabs, you have a collision.

For a cylinder, when you expand the OBB, you expand each slab differently depending on the dot product of the line/ray to face normal times the radius... but for a capsule, you expand all 3 slabs by the radius.

EDIT. Of course, after re-reading your question, I thought your question was less general that it is. Sorry if I gave a mis-directed answer.