Oriented bounding box - finding overlap area
Author
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?
search for separating axis theorem in Google that will help you do OBB collision detection.
Author
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.
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.
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.
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.
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.
Author
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
