20
\$\begingroup\$

Say you have two Bounding Box Objects each of them storing the current vertices of the box in a vector with all the vertices of the object rotated and translated relative to a common axis.

Here is an image to illustrate my problem:

How can I work out if the two OBB's are overlapping any links to help explain the solution to the problem would be welcome. Nothing too convoluted please...

\$\endgroup\$
17
\$\begingroup\$

An OBB is a convex hull. A convex hull is a 3D shape that has no "crannies" on its surface. Every "bump" (vertex) on the convex hull protrudes outward, never inward. If you slice a plane through a convex hull you will get (only one) convex polygon. If you are inside a convex hull and fire a laser pointing outward you will only punch through the hull's surface once (never twice).

The Separating Axis Theorem test can be used to detect collision of convex hulls. The SAT test is simple. It works in 2D and 3D. Although the pictures below will be in 2D, they could just as easily be applied to 3D.

Concept

This is the key concept you're using with SAT:

  • Two shapes only intersect if they have overlap when "projected" onto every normal axis of both shapes.

"Projection" of a shape onto a 1D vector looks like this (what I call "crushing")

A shape with red verts, and an axis

enter image description here

"Projecting the shape to the axis" means dropping a perpendicular from each point on the shape just to land on the axis. You can think of this as "crushing" the points by a hand that gathers everything and perpendicularly crushes it down to the axis.

enter image description here

What you're left with: Points on an axis

enter image description here

SAT says:

For 2 convex hulls to intersect, they have to overlap on every axis (where every normal on either shape counts as an axis we must check).

Take these 2 shapes:

enter image description here

You see they don't intersect, so lets try a few axes to show were an overlap doesn't happen.

Trying the top normal of the pentagon:

enter image description here

These are the extents. They do overlap.

enter image description here

Try left side of the rectangle. Now they do not overlap in this axis, therefore NO INTERSECTION.

enter image description here

Algorithm:

For each face normal on both shapes:

  • Find the minimum and maximum extents (largest and smallest value) of the projection of all the vertex corner points of both shapes onto that axis
  • If they don't overlap, no intersection.

And that's really it. The code to make SAT work is very short and simple.

Here is some code that demonstrates how to do an SAT axis projection:

void SATtest( const Vector3f& axis, const vector<Vector3f>& ptSet, float& minAlong, float& maxAlong )
{
  minAlong=HUGE, maxAlong=-HUGE;
  for( int i = 0 ; i < ptSet.size() ; i++ )
  {
    // just dot it to get the min/max along this axis.
    float dotVal = ptSet[i].dot( axis ) ;
    if( dotVal < minAlong )  minAlong=dotVal;
    if( dotVal > maxAlong )  maxAlong=dotVal;
  }
}

Calling code:

// Shape1 and Shape2 must be CONVEX HULLS
bool intersects( Shape shape1, Shape shape2 )
{
  // Get the normals for one of the shapes,
  for( int i = 0 ; i < shape1.normals.size() ; i++ )
  {
    float shape1Min, shape1Max, shape2Min, shape2Max ;
    SATtest( normals[i], shape1.corners, shape1Min, shape1Max ) ;
    SATtest( normals[i], shape2.corners, shape2Min, shape2Max ) ;
    if( !overlaps( shape1Min, shape1Max, shape2Min, shape2Max ) )
    {
      return 0 ; // NO INTERSECTION
    }

    // otherwise, go on with the next test
  }

  // TEST SHAPE2.normals as well

  // if overlap occurred in ALL AXES, then they do intersect
  return 1 ;
}

bool overlaps( float min1, float max1, float min2, float max2 )
{
  return isBetweenOrdered( min2, min1, max1 ) || isBetweenOrdered( min1, min2, max2 ) ;
}

inline bool isBetweenOrdered( float val, float lowerBound, float upperBound ) {
  return lowerBound <= val && val <= upperBound ;
}
\$\endgroup\$
  • \$\begingroup\$ Hullinator implements the SAT test for convex hulls \$\endgroup\$ – bobobobo Aug 8 '13 at 1:47
  • \$\begingroup\$ awesome explanation! thanks. I think you may have a typo in the line: "so lets try a few axes to show were an overlap doesn't happen.", because then you proceed to give examples where they do overlap. thanks again! \$\endgroup\$ – Joe Sep 12 '15 at 13:56
  • \$\begingroup\$ Don't you need to do the tests also for all the cross products of the normals? This article geometrictools.com/Documentation/DynamicCollisionDetection.pdf says so. \$\endgroup\$ – iNFINITEi Oct 17 '17 at 23:15
  • \$\begingroup\$ It's worth stating that this specific method of SAT only works in 2D. In 3D you need to get more than just the normals of each face. Once you have the right normals, though, the rest of the process (project, compare) is exactly the same. \$\endgroup\$ – Nic Hartley Apr 7 '18 at 17:56
  • \$\begingroup\$ Really hard to tell from your 2D pictures what direction the arrows are going. \$\endgroup\$ – WDUK Aug 18 '18 at 18:34
7
\$\begingroup\$

You should definitely look up Separating Axis Theorem. It's for convex objects. There is a rule: "If two convex objects don't intersect, then there is a plane where the projection of these two objects will not intersect".

You can find some examples on the wiki. But it's a little more complicated than for your case.

Something more suitable for your problem can be found here (two cars colliding).

\$\endgroup\$
1
\$\begingroup\$

More SAT articles.

The last article on this site comes with complete code, i think it's in FLASH, i've no idea, but i had exactly 0 issues converting it to C++ when i had to use SAT for the first time, shouldn't be hard to do the same for other languages. The only thing you'll have to add is storing of the displacement vector on each calculation (if it's the smallest, ofcourse, you'll understand this when you learn about SAT), the code in this tutorial doesn't do it, so you end up with the last calculated vector.

http://rocketmandevelopment.com/tag/separation-axis-theorem/

Good, old N-Game tutorials. Best SAT theory on the web.

http://www.metanetsoftware.com/technique/tutorialA.html

\$\endgroup\$
  • \$\begingroup\$ It's so irritating no one posts the full working source with all the required classes. I ported his code over into a demo of my own but it just doesn't work. :( This is my project so far if anyone could help me debug it that would be great. link \$\endgroup\$ – Joshua Barnett Mar 13 '12 at 10:35
  • \$\begingroup\$ what do you mean it doesn't work? pay attention to how you're storing your vertices, in the image you have them in a cartesian coordinate system, in the tutorial he stores the vertices as vectors relative to the centroid (all you have to do is subtract centroid from your own vertices or remove the lines where he modifies his own vertices), functions like dot product you can create yourself, you don't need a guide for those, rest should be straight forward, it's not a copy paste material, learn SAT before trying to implement it \$\endgroup\$ – dreta Mar 13 '12 at 12:11
  • \$\begingroup\$ This is how I've implemented it: SAT.as, Shape2D.as, What do you mean by centroid? The centre of the polygon such as (x, y)? \$\endgroup\$ – Joshua Barnett Mar 13 '12 at 13:03
  • \$\begingroup\$ At the moment I have a function getOBB() which returns vertices as detailed in my original image. This is calculated from the a Vector<b2Vec2> containing the vertices of the shape, a angle variable, and a position variable. \$\endgroup\$ – Joshua Barnett Mar 13 '12 at 13:07
  • \$\begingroup\$ yes, the center, the way this guy creates his polygons is by giving offsets from the center, idk AS3, but from what i see you project your vertices as they are, when calculating dot product try to subtract centroid from the vertices (vector subraction), beside this you aren't checking which separation vector is the smallest still, you only store the last one calculated \$\endgroup\$ – dreta Mar 13 '12 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.