Jump to content
  • Advertisement
Sign in to follow this  
KaelisAsur

Oriented bounding box - finding overlap area

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

Greetings. I am researching collision detection (particularly pixel-perfect). There are many articles and resources on the net pertaining to this topic, however i am unable to find anything about finding the actual area of overlap (intersection) between two oriented bounding boxes. Does anyone know of any algorithm dealing with this problem?

Share this post


Link to post
Share on other sites
Advertisement
I am aware of the separating axis theorem, and i know how to detect if the bounding boxes collide. However, the point here is to find to find the area of intersection, to be more specific - the polygon created by intersection (could be approximated to AABB, i dont need it to be exact).

To illustrate:

http://cas.sdss.org/dr5/en/help/docs/images/sectorFig7.jpg

The green area is what i need to calculate. Of course, in this example the bounding boxes are axis aligned, whereas i need to calculate it for oriented bounding boxes. Or rather, aabb vs oob, since the two can be rotated so that one of them becomes an aabb.

Share this post


Link to post
Share on other sites
One of the easiest method to find the overlapped regions between two convex objects is by using a clipping method.

You use one of the polygon as a clipping region, and cut the other polygon. That can also be used for detecting collision.


Polygon intersect(const Polygon& A, const Polygon& B)
{
Polygon C = B; // copy polygon B to result C

for(int i = 0, j = A.vnum-1; i < A.vnum; j = i, i ++)
{
Vector E(A.v - A.v[j]); // edge of polygon A
Vector N(-E.y, E.x); // plane normal (use opposite if your vertex winding is clockwise).
Vector O(A.v); // plane origin

Plane P(N, O); // infinite plane passing through edge

C = clip(C, P); // 'cut' polygon C with plane P
}

return C; // return intersection region. if C has 0 vertices, then no intersection.
}

Polygon clip(const Polygon& A, const Plane& P)
{
Polygon R; // resulting polygon

for(int i = 0, j = A.vnum-1; i < A.vnum; j = i, i ++)
{
Vector V = A.v[j];
Vector W = A.v;

float sign_v = ((V - P.origin).dotProduct(P.normal));
float sign_w = ((W - P.origin).dotProduct(P.normal));

// both points outside the half-plane
if(sign_v > 0.0f && sign_w > 0.0f)
continue;

// edge start inside the half plane. add it.
if(sign_v <= 0.0f)
{
R.addVertex(V);
}

// edge intersected by plane.
if(sign_v < 0.0f && sign_w > 0.0f ||
sign_v > 0.0f && sign_w < 0.0f)
{
t = -sign_v / (sign_w - sign_v); // intersection param

Vector Q = V + t * (W - V); // intersection of edge with plane

R.addVertex(Q);
continue;
}
}
return R;
}


code untested. Note that the cutting depends on the winding order of the clutting polygon. If your winding order is opposite, then you'll need the opposite of the plane normal.

Share this post


Link to post
Share on other sites
Ah, of course, i should have looked for polygon intersection instead of bounding box intersection. In any case, thats exactly what i needed, thank you.

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!