Separating Axis Theorem and rotated objects

Question

Quick question which hopefully won't require thralling through my code.

I have a working implementation of SAT for 3D collision detection but I'm having some problems with dealing with rotated objects. So what I have done, is every frame I rotate every point in both objects by their rotation quaternions. This feels excessive, especially if I am going to be translating/scaling/rotating every vertex in every object on every frame for the collision detection.

I would hope there's a way of implementing my SAT implementation to work with rotated normals only, and not need the rotated projections to compensate, but that doesn't seem to be working.

Could anyone provide me with a brief explanation with how SAT should be expected to handle rotations? Can we rotate certain points, or perhaps get some sort of post-projection rotation value to skew our projections like we can with translations?

Thanks

Answer 1

The key to any optimisation, is identifying where the bulk of the work is being done.

A simple analysis of your problem reveals the following:

1. A cuboid shape has 8 vertices, three perpendicular axes, and a position.
2. The same cuboid can be rotated around any of these axes.

At the moment, your algorithm is transforming the vertices, then presumably computing resultant axes from the vertices, to perform SAT computations.

You are correct in surmising that there is a computationally less expensive way to do it.

In your cuboid data structure, you only require 3 floats, called half extents. Each value is the distance from the centre of the cuboid, to the edge of it, along one of it's principle axes.

You take the three principle axes, x (1,0,0), y(0,1,0), and z(0,0,1), and rotate them by the objects' transform. (3 vector rotations instead of 8)

Then, you compute the vertices, using the rotated axes and half extents. this is mostly vector addition multiplication, which is inexpensive. This will result in the vertices being rotated, but not translated yet.

Finally, you add the position of the object to each vertex (again, cheap) to get your final translated vertices, in world space.

There are other optimisations that can be done, but this is a good start for you.