Quote:Original post by daniel_i_l
Thanks, but if i did it like that wouldn't it be hard to generalize it for other bsic shapes like cylinders, pyramids...?

If I understand what you're saying, the answer is 'not really'.

It's true that because an OBB has certain properties we can use the basis vectors of its transform directly as part of its representation, while for arbitrary polytopes (such as a pyramid), the geometry has to be dealt with differently. In fact, you could approach OBBs in a generic manner by viewing them as a collection of features (vertices, edges, faces), just like any other polytope. But the fact is, OBBs are not arbitrary polytopes, and their specific properties allow for many optimizations (for example, a generic approach would require well over 100 axis tests rather than 15). So you should just accept that OBBs are a special case and implement accordingly :-)

Quote:Original post by daniel_i_l
...if i get my code working with a lot of OBB optimizaations then how'll i add other primitives when i'm ready?

Write some new code :-)

Seriously though, as I mentioned before you could treat all polytopes in a completely uniform manner (with regard to the SAT, that is), by viewing them solely as a collection of features. Then you wouldn't have to write any new code (or at least not much) when adding a new type of polytope.

Here is the problem though. An OBB has the particular properties that:

a) Although there are 6 face normals, there are only three with a unique (non-directed) alignment, so 3 of the face normal tests are wasted.

b) Although there are 12 edges, there are only 3 unique (non-directed) alignments between them, therefore only 3 edges need be considered.

c) With this elimination of unnecessary axis tests, the total number of tests required to determine intersection is 15.

d) Without eliminating these redundant tests, the total number of axis tests required is an impractical 156.

e) Furthermore, there are additional optimizations that can be made due to redundant dot products, common sub-expressions, and so on.

Clearly, it would be foolish to approach an OBB intersection test in a generic manner when the above optimizations are available. I'll also mention that the same ideas apply for AABBs (which can be optimized even further due to the axis-aligned face normals and edges).

So what it comes down to is that if you're interested in getting reasonable performance out of your collision test, you probably won't be able to use the exact same code for an OBB and, say, a tetrahedron.

This post is getting a little long, but I'll throw out a couple more ideas. Depending on the type of test you're performing, it certainly is possible to factor out the bulk of the SAT code and share it between different polytope pairs. And if you don't need to squeeze out every last drop of performance, you can make the test fairly generic - it basically reduces to querying the unique face normals and edges for each shape, and then using a per-polytope projection function along with generic interval test functions to perform the separating axis test.

I can certainly relate to what you're saying about genericity. A project that I began but haven't worked on in a while was a completely generic, template-based collision detection system that was still able to take advantage of the kinds of optimizations discussed above. I got quite a ways with it. It was a very interesting project, but I'm still not sure how useful it is practically. And even as far as I got with it, I still wasn't able to squeeze every possible OBB optimization in there in a generic manner (although I haven't given up yet). So in summary, I think it might be possible to do what you're suggesting (handling all polytopes with the same code) using template metaprogramming techniques, but I wouldn't really recommend going down that road, especially if you're just getting your feet wet with collision detection and response in general.