• 11
• 9
• 10
• 9
• 11

# Oriented bounding box - finding overlap area

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

## 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 on other sites
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 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 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.

np :)