# SAT optimization

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

## Recommended Posts

Hi, i finally finished implementing the SAT collision test for OBB's the way that it was explained to me here: http://www.gamedev.net/community/forums/topic.asp?topic_id=414703 and it wroks pretty well. It was mentioned in that thread that after getting it to work, there are various things that you can do to make it run faster. How is this done? What good optimizations are there? Thanks.

##### Share on other sites
Optimising col det is all a question of priority. There is no point looking at the code, and seeing a expensive calcualtion, and optimise it to death if it's not used that often and is nowhere near your bottleneck. That's just a waste of time.

If you are concerned about the SAT part itself, the detection, Dave Eberly compiled a table of optimised calculations for OBB / OBB and OBB / triangles. The individual axis tests are chopped down to the lowest possible number of maths operations.

This should the the calculations that are performed most of the time, and where you should focus your optimisations. If you have two thousand boxes, they will not all touch each other at some point in time. So the rejection test (the 15 SAT axis tests) is the most used part of the code.

The MTD calculation can't really be that much optimised. It's just a linear search through 15 values at the end.

Second expensive part would be the support calculation function. But that, you can't do much more that dot product the boxes' directions with the MTD direction you found, to find what feature is most aligned with the MTD direction. If you found a face, reconstrcuting the face's polygon should be very straight forward. Not much optimisation you can do there.

Third is the clipping. Note that the case where you need to clip features (edge / face, face / face), should not occur often. If they do, then there is something wrong (your physics engine doesn not put objects to sleep for example). Then, clipping can be optimised, since it's square vs square at most, but really, it's more like an exercise for the brain than anything else. It's just something for you to work out.

##### Share on other sites
Thanks, the part of code that i was most worried about was the support calculation function. First of all, to check if it's a face i calculate the cross product of each of the 3 Directions of the OBB with the collision normal, if it's close to zero then i know that there's a face either in that direction or in the opposite direction, since the face normal should be in the opposite direction of the collision normal i then calculate the dot product of the direction with the collision normal - if it's bigger than zero that i flip the direction around and this is the face normal. in pesudocode:
bool FaceIntersect(body, CollisionNormal, &supports){  Directions = body.directions;  for (i=0; i<numberOfdirections; ++i)  {      cross = CollisionNormal X Directions;      if(cross<0.005)       {         FaceNormal = Directions;          dot = CollisionNormal * Directions;         if(dot>0)            FaceNormal *= -1;         supports = CalculateFaceFromNormal(FaceNormal)         return true;      }   }   return false;}

to calculate the four corners of a face from the face normal i used the other two direction vectors as i explained here:
http://www.gamedev.net/community/forums/topic.asp?topic_id=419438
To check for an edge collision i used basiclly the same function just with a dot product instead of the cross. if the dot is smaller than 0 then there're 4 possible edges in this direction. to then calculate the correct edge from the edge direction and collision normal i did something similar to what i did to find the four corners of the face - this is also described in the link above.
Is these tests good and fast? how can i make them better?
Thanks.

##### Share on other sites
I think you could just stick with dot products. I also assume you want to find the face the most towards the direction.

Box : P, D[3], e[3]; // position, directions, extents.
Result V[4], NumV; // the support points, that form either, a face, an edge or a vertex

static const float pi = atan(1.0f) * 4.0f;static const float two_pi = pi * 2.0f;static const float cos_1_degree  = cos(1  * two_pi / 180.0f); // 1 degree tolerancestatic const float cos_89_degree = cos(89 * two_pi / 180.0f); // 1 degree tolerancefloat d[3];// detect face supportsfor(int i = 0; i < 3; i ++){    // calculate dot first    d = Direction * D;    // we have a face parallel to the normal of collision    if(fabs(d) >= cos_1_degree)    {         int j = (i + 1) % 3;        int k = (i + 2) % 3;        // centre of face        Vector Cen = P + D * sgn(d) * e;           // the four vertices        V[0] = Cen - D[j] * e[j] - D[k] * e[k];        V[1] = Cen - D[j] * e[j] + D[k] * e[k];        V[2] = Cen + D[j] * e[j] + D[k] * e[k];        V[3] = Cen + D[j] * e[j] - D[k] * e[k];        Vnum = 4;        return true;        }}// detect edgesfor(int i = 0; i < 3; i ++){    // perpendicular edge to the direction    if (fabs(d) <= cos_89_degrees)    {        int j = (i + 1) % 3;        int k = (i + 2) % 3;        // centre of edge        Vector Cen = P;        Cen += D[j] * sgn(d[j]) * e[j];        Cen += D[k] * sgn(d[k]) * e[k];        // edge        V[0] = Cen - D * e;        V[1] = Cen + D * e;        Vnum = 2;        return true;    }}// vertex...V[0] = P;V[0] += D[0] * sgn(d[0]) * e[0];V[0] += D[1] * sgn(d[1]) * e[1];V[0] += D[2] * sgn(d[2]) * e[2];Vnum = 1;return true;

something like that... [grin]

##### Share on other sites
@The OP: If you're intent on these optimizations, one thing to keep in mind (in case you haven't already incorporated this into your implementation) is that when the minimum axis is a face normal, you already know that the support feature for that box is the face corresponding to that normal, or its opposite. You can easily determine which from the 'side' on which the collision occured with respect to the axis.

Actually, I do it this way not so much for efficiency, but to eliminate the tolerance check when finding the supporting feature 'from scratch' (the fewer tolerances the better, IMO).

##### Share on other sites
Thanks for those tips. Two questions about oliii's code:
If in my program the collision vector is going towards the body that i'm checking, then do i just change all the sgn(..) to -sgn(..)?
and also, don't the directions and the collision normal have to be normalized for this to work? (mst importantly this: fabs(d) >= cos_1_degree)
Thanks!

##### Share on other sites
Box directions should always be normalised. And so is the collision normal. It probably is more practical to slpit up the MTD vector you get with a normalised vector and a depth of intersection value.

And yes, you change the sgn() with -sgn(), or you can just use -Direction as a parameter to the function.

// constantsstatic const float pi = atan(1.0f) * 4.0f;static const float two_pi = pi * 2.0f;static const float cos_1_degree  = cos(1  * two_pi / 180.0f); // 1 degree tolerancestatic const float cos_89_degree = cos(89 * two_pi / 180.0f); // 1 degree tolerancevoid FindSupportPoints(Vector P, Vector D[3], float e[3], Vector Direction, Vector*V, int& Vnum){    float d[3];    // detect face supports    for(int i = 0; i < 3; i ++)    {        // calculate dot first        d = Direction * D;            // we have a face parallel to the normal of collision        if(fabs(d) >= cos_1_degree)        {             int j = (i + 1) % 3;            int k = (i + 2) % 3;            // centre of face            Vector Cen = P + D * sgn(d) * e;               // the four vertices            V[0] = Cen - D[j] * e[j] - D[k] * e[k];            V[1] = Cen - D[j] * e[j] + D[k] * e[k];            V[2] = Cen + D[j] * e[j] + D[k] * e[k];            V[3] = Cen + D[j] * e[j] - D[k] * e[k];            Vnum = 4;            return true;            }    }    // detect edges    for(int i = 0; i < 3; i ++)    {        // perpendicular edge to the direction        if (fabs(d) <= cos_89_degrees)        {            int j = (i + 1) % 3;            int k = (i + 2) % 3;                // centre of edge            Vector Cen = P;            Cen += D[j] * sgn(d[j]) * e[j];            Cen += D[k] * sgn(d[k]) * e[k];                // edge            V[0] = Cen - D * e;            V[1] = Cen + D * e;            Vnum = 2;            return true;        }    }    // vertex...    V[0] = P;    V[0] += D[0] * sgn(d[0]) * e[0];    V[0] += D[1] * sgn(d[1]) * e[1];    V[0] += D[2] * sgn(d[2]) * e[2];    Vnum = 1;    return true;}Vector VA[4], VB[4]; // supportsint VAnum, VBnum;Vector CA[8], CB[8]; // contactsint CAnum, CBnum;FindSupportPoints(PA, DA, ea, -CollisionNormal, VA, VAnum);FindSupportPoints(PB, DB, eb,  CollisionNormal, VB, VBnum);FindContactPoints(CollisionNormal, collisionDepth,                   VA, VAnum, VB, VBnum,                  CA, CAnum, CB, CBnum);

Code is untested, of course. But it's for the general idea.

1. 1
Rutin
36
2. 2
3. 3
4. 4
5. 5

• 12
• 14
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633346
• Total Posts
3011442
• ### Who's Online (See full list)

There are no registered users currently online

×