Jump to content
  • Advertisement
Sign in to follow this  
daniel_i_l

SAT optimization

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 tolerance
static const float cos_89_degree = cos(89 * two_pi / 180.0f); // 1 degree tolerance

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;





something like that... [grin]

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.



// constants
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 tolerance
static const float cos_89_degree = cos(89 * two_pi / 180.0f); // 1 degree tolerance

void 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]; // supports
int VAnum, VBnum;

Vector CA[8], CB[8]; // contacts
int 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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!