Sign in to follow this  

OBB vs OBB using SAT

This topic is 4380 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

In 2D which axes do I need to test? Also what’s the most efficient way of getting the projection of the box on to an axis assuming all I have is the 4 points and the orientation of the box?

Share this post


Link to post
Share on other sites
Quote:
Original post by Grain
In 2D which axes do I need to test?
Only the "face" axes. That is, you need to test two axes per OBB: these axes being perpendicular to the sides of the OBB; which, of course, in 2D is the same as saying they're parallel to the sides of the OBB.

Quote:
Also what’s the most efficient way of getting the projection of the box on to an axis assuming all I have is the 4 points and the orientation of the box?
It depends on how you represent the orientation. Usually, you wouldn't have both orientation and the 4 vertices; typically you have center point, orientation, and extents. The reason you typically don't have an explicit vertex representation for the OBBs is that you'd have to rotate all the vertices as the OBB is rotated, whereas with the center+orientation+extents representation you only update the orientation.

In 2D I would have an OBB look like the struct below, and the projected radius onto a given axis is computed by the function GetProjectedRadius():


struct OBB {
Point2D c; // Center
Vector2D u[2]; // x and y axis
float e[2]; // Extents
}

float GetProjectedRadius(OBB o, Vector2D d)
{
return o.e[0]*Abs(Dot(d, o.u[0])) + o.e[1]*Abs(Dot(d, o.u[1]));
}




The whole function could look something like this:


// Helper function
bool SeparatedOnAxis(OBB a, OBB b, Vector2D d)
{
// Get projected distance between OBB centers
float r = Abs(Dot(a.c - b.c, d));

return GetProjectedRadius(a, d) + GetProjectedRadius(b, d) < r;
}

bool TestOBBOBB(OBB a, OBB b)
{
// Exit early if not overlapping
if (SeparatedOnAxis(a, b, a.u[0])) return false;
if (SeparatedOnAxis(a, b, a.u[1])) return false;
if (SeparatedOnAxis(a, b, b.u[0])) return false;
if (SeparatedOnAxis(a, b, b.u[1])) return false;
// Must be overlapping
return true;
}




This is all untested code that I just typed in here so there may be typos, but the idea should hopefully be clear.

Note that all the radii that are computed in the code are actually not the "real" radii, but multiplied by the length of the projection axes. However, as all the values that go into the comparison are multiplied by the same length value there's no need to normalize the projection axis vector as k*a < k*b if a < b, assuming k is positive (which a length is). Of course, in this particular case, the orientation axes -- and therefore the projection axes -- are most likely unit length. However, in the 3D case we must also project onto all pairwise cross products of the orientation axes, which aren't necessarily unit length.

Hope this helps.

[Edited by - Christer Ericson on December 18, 2005 7:19:14 PM]

Share this post


Link to post
Share on other sites
Excellent, thanks. However my boxes have 4 extents. Meaning the lower and upper sides can be different distances from the center as can the left and right sides. How would I get the projected radius with 4 different extents?

Share this post


Link to post
Share on other sites
Quote:
Original post by Grain
Excellent, thanks. However my boxes have 4 extents. Meaning the lower and upper sides can be different distances from the center as can the left and right sides. How would I get the projected radius with 4 different extents?
Ah, okay. That's not what you would typically call an OBB (a box having orthogonal sides). Lets call it a (convex) bounding quad.

So, a bounding quad is equivalent to having a struct BQuad defined as such

struct BQuad {
Point2D p[3]; // Four pts defining a convex CCW quad
};





/* THIS SPACE LEFT BLANK BY THE ~16-LINE FIXED-HEIGHT CODE BLOCK CRAPNESS! */



where we will assume the points are arranged counterclockwise (or clockwise, doesn't matter, the important thing is that we assume a certain ordering and write the code accordingly).

You can test two BQuads for overlap like so

bool TestBQuadBQuad(BQuad a, BQuad b)
{
// No intersection if BQuad a lies fully outside any edge of BQuad b
for (int j = 3, i = 0; i < 4; j = i, i++)
if (IsOutsideHalfplane(a, Perp(b.p[j] - b.p[i]), b.p[i])) return false;
// No intersection if BQuad b lies fully outside any edge of BQuad a
for (int j = 3, i = 0; i < 4; j = i, i++)
if (IsOutsideHalfplane(b, Perp(a.p[j] - a.p[i]), a.p[i])) return false;
// Otherwise must intersect
return true;
}



with the following support functions:

// Compute counterclockwise perpendicular to input vector
Vector2D Perp(Vector2D v)
{
return Vector2D(-y, x);
}

// Test if BQuad outside halfplane specified by (n, p)
bool IsOutsideHalfplane(BQuad a, Vector2D n, Point2D p)
{
for (int i = 0; i < 4; i++)
if (Dot2D(a.p[i] - p, n) < 0.0f) return false;
return true;
}



Again, this is untested code so you might have to correct typos, etc.

Note that the reason we typically project the bounding objects onto the candidate separating axis is to utilize object symmetry in order to make the calculations cheaper. Here, because there is no symmetry to utilize (i.e. you don't know anything about the structure of the quads), you cannot really simplify the math beyond testing all four vertices for each candidate axis.

Also, because opposite sides of the quads aren't (necessarily) parallel, we need to test 8 different separating axis, compared to the 4 needed for a 2D OBB vs. OBB case (as I showed before).

Hope this helps now! ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by Grain
Excellent, thanks. However my boxes have 4 extents. Meaning the lower and upper sides can be different distances from the center as can the left and right sides.
If you mean that the box is rectangular but off-center, then I would think you could use the standard OBB SAT test with a few minor adjustments. However, if the boxes are arbitrary convex quads, you'll have to use the general method given by Christer.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
If you mean that the box is rectangular but off-center, then I would think you could use the standard OBB SAT test with a few minor adjustments. However, if the boxes are arbitrary convex quads, you'll have to use the general method given by Christer.
Hmm.. I didn't even consider that the OP's description might entail an offcenter box. In that case, you definitely can use the standard OBB SAT test (you simply compute centered centers from the box boundaries and use these new centers in the SAT calculations instead of the stored offcenter centers).

As always, the quality of an answer that you get is directly proportional to the quality of information you provide upfront. If none of the now three(!) solutions presented apply to the OP's problem, the best thing here would be for the OP to post what his "OBB" struct looks like (with clear comments indicating what the various member variables are, and why they're there).

Share this post


Link to post
Share on other sites
Quote:
Original post by Christer Ericson
Quote:
Original post by jyk
If you mean that the box is rectangular but off-center, then I would think you could use the standard OBB SAT test with a few minor adjustments. However, if the boxes are arbitrary convex quads, you'll have to use the general method given by Christer.
Hmm.. I didn't even consider that the OP's description might entail an offcenter box. In that case, you definitely can use the standard OBB SAT test (you simply compute centered centers from the box boundaries and use these new centers in the SAT calculations instead of the stored offcenter centers).
Yes that’s what I meant. Sorry if I wasn’t clear. And now that you explained it, it seams painfully obvious to simply re compute the center.

Anyway thanks again.

Share this post


Link to post
Share on other sites

This topic is 4380 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this