OBB vs OBB using SAT
Author
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?
Quote:Original post by GrainOnly 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.
In 2D which axes do I need to test?
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 functionbool 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]
Author
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?
Quote:Original post by GrainAh, okay. That's not what you would typically call an OBB (a box having orthogonal sides). Lets call it a (convex) bounding quad.
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?
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), b.p)) 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), a.p)) return false; // Otherwise must intersect return true;}with the following support functions:
// Compute counterclockwise perpendicular to input vectorVector2D 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 - 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! ;)
Quote:Original post by GrainIf 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.
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.
Quote:Original post by jykHmm.. 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).
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.
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).
Author
Quote:Original post by Christer EricsonYes 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.Quote:Original post by jykHmm.. 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).
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.
Anyway thanks again.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
